रेखीय प्रतिगमन और इसकी पुनर्प्राप्ति के तरीके

स्रोत: एक्सकेसीडी

डेटा विश्लेषण से संबंधित कई क्षेत्रों के लिए रैखिक प्रतिगमन बुनियादी एल्गोरिदम में से एक है। इसका कारण स्पष्ट है. यह एक बहुत ही सरल और समझने योग्य एल्गोरिदम है, जिसने सैकड़ों नहीं तो कई दसियों वर्षों तक इसके व्यापक उपयोग में योगदान दिया है। विचार यह है कि हम अन्य चर के सेट पर एक चर की रैखिक निर्भरता मानते हैं, और फिर इस निर्भरता को बहाल करने का प्रयास करते हैं।

लेकिन यह लेख व्यावहारिक समस्याओं को हल करने के लिए रैखिक प्रतिगमन का उपयोग करने के बारे में नहीं है। यहां हम इसकी पुनर्प्राप्ति के लिए वितरित एल्गोरिदम के कार्यान्वयन की दिलचस्प विशेषताओं पर विचार करेंगे, जिसका सामना हमें मशीन लर्निंग मॉड्यूल लिखते समय हुआ था अपाचे इग्नाइट. थोड़ा बुनियादी गणित, मशीन लर्निंग और वितरित कंप्यूटिंग आपको यह पता लगाने में मदद कर सकती है कि आपका डेटा हजारों नोड्स में वितरित होने पर भी रैखिक प्रतिगमन कैसे किया जाए।

हम किस बारे में बात कर रहे हैं?

हमारे सामने रैखिक निर्भरता बहाल करने का कार्य है। इनपुट डेटा के रूप में, कथित रूप से स्वतंत्र चर के वैक्टर का एक सेट दिया जाता है, जिनमें से प्रत्येक आश्रित चर के एक निश्चित मूल्य से जुड़ा होता है। इस डेटा को दो मैट्रिक्स के रूप में दर्शाया जा सकता है:

अब, चूंकि निर्भरता मान ली गई है, और, इसके अलावा, रैखिक, हम अपनी धारणा को आव्यूहों के उत्पाद के रूप में लिखेंगे (रिकॉर्डिंग को सरल बनाने के लिए, यहां और नीचे यह माना जाता है कि समीकरण का मुक्त पद पीछे छिपा हुआ है) , और मैट्रिक्स का अंतिम कॉलम इकाइयाँ शामिल हैं):

यह काफी हद तक रैखिक समीकरणों की प्रणाली जैसा लगता है, है ना? ऐसा लगता है, लेकिन सबसे अधिक संभावना है कि समीकरणों की ऐसी प्रणाली का कोई समाधान नहीं होगा। इसका कारण शोर है, जो लगभग किसी भी वास्तविक डेटा में मौजूद होता है। एक अन्य कारण रैखिक निर्भरता की कमी हो सकती है, जिसका मुकाबला अतिरिक्त चर पेश करके किया जा सकता है जो गैर-रेखीय रूप से मूल पर निर्भर करते हैं। निम्नलिखित उदाहरण पर विचार करें:

स्रोत: विकिपीडिया

यह रैखिक प्रतिगमन का एक सरल उदाहरण है जो एक चर (अक्ष के अनुदिश) के संबंध को दर्शाता है ) दूसरे चर से (अक्ष के अनुदिश ). इस उदाहरण के अनुरूप रैखिक समीकरणों की प्रणाली के समाधान के लिए, सभी बिंदुओं को बिल्कुल एक ही सीधी रेखा पर स्थित होना चाहिए। लेकिन यह सच नहीं है. लेकिन शोर के कारण (या क्योंकि रैखिक संबंध की धारणा गलत थी) वे एक ही सीधी रेखा पर नहीं होते हैं। इस प्रकार, वास्तविक डेटा से एक रैखिक संबंध को बहाल करने के लिए, आमतौर पर एक और धारणा पेश करना आवश्यक होता है: इनपुट डेटा में शोर होता है और इस शोर में शोर होता है। सामान्य वितरण. आप अन्य प्रकार के शोर वितरण के बारे में धारणाएँ बना सकते हैं, लेकिन अधिकांश मामलों में सामान्य वितरण पर ही विचार किया जाता है, जिस पर आगे चर्चा की जाएगी।

अधिकतम संभावना विधि

इसलिए, हमने यादृच्छिक सामान्य रूप से वितरित शोर की उपस्थिति मान ली। ऐसी स्थिति में क्या करें? गणित में इस मामले के लिए इसका व्यापक रूप से उपयोग किया जाता है अधिकतम संभावना विधि. संक्षेप में, इसका सार चुनाव में निहित है संभाव्यता कार्य और इसके बाद का अधिकतमीकरण।

हम सामान्य शोर के साथ डेटा से एक रैखिक संबंध बहाल करने पर लौटते हैं। ध्यान दें कि कल्पित रैखिक संबंध गणितीय अपेक्षा है मौजूदा सामान्य वितरण. उसी समय, संभावना है कि अवलोकन योग्य वस्तुओं की उपस्थिति के अधीन, एक या दूसरा मान लेता है , इस तरह दिखता है:

आइए अब इसके स्थान पर स्थानापन्न करें и हमें जिन वेरिएबल्स की आवश्यकता है वे हैं:

जो कुछ बचा है वह वेक्टर ढूंढना है , जिस पर यह संभावना अधिकतम है। ऐसे फ़ंक्शन को अधिकतम करने के लिए, पहले इसका लघुगणक लेना सुविधाजनक होता है (फ़ंक्शन का लघुगणक फ़ंक्शन के समान बिंदु पर अधिकतम तक पहुंच जाएगा):

जो, बदले में, निम्नलिखित फ़ंक्शन को छोटा करने के लिए आता है:

वैसे इसे एक विधि कहा जाता है कम से कम वर्गों. अक्सर उपरोक्त सभी बातों को छोड़ दिया जाता है और इस पद्धति का उपयोग सरलता से किया जाता है।

क्यूआर अपघटन

उपरोक्त फ़ंक्शन का न्यूनतम उस बिंदु को ढूंढकर पाया जा सकता है जिस पर इस फ़ंक्शन का ग्रेडिएंट शून्य है। और ग्रेडिएंट इस प्रकार लिखा जाएगा:

क्यूआर अपघटन न्यूनतम वर्ग विधि में उपयोग की जाने वाली न्यूनतम समस्या को हल करने के लिए एक मैट्रिक्स विधि है। इस संबंध में, हम समीकरण को मैट्रिक्स रूप में फिर से लिखते हैं:

तो हम मैट्रिक्स को विघटित करते हैं मैट्रिक्स के लिए и और परिवर्तनों की एक श्रृंखला निष्पादित करें (क्यूआर अपघटन एल्गोरिदम पर यहां विचार नहीं किया जाएगा, केवल कार्य के संबंध में इसका उपयोग किया जाएगा):

मैट्रिक्स ऑर्थोगोनल है. इससे हमें काम से छुटकारा मिल जाता है :

और यदि आप प्रतिस्थापित करते हैं पर , तो यह काम करेगा . ध्यान में रख कर एक ऊपरी त्रिकोणीय मैट्रिक्स है, यह इस तरह दिखता है:

इसे प्रतिस्थापन विधि का उपयोग करके हल किया जा सकता है। तत्व के रूप में स्थित है , पिछला तत्व के रूप में स्थित है और इतने पर.

यहां यह ध्यान देने योग्य है कि क्यूआर अपघटन के उपयोग के कारण परिणामी एल्गोरिदम की जटिलता बराबर है . इसके अलावा, इस तथ्य के बावजूद कि मैट्रिक्स गुणन ऑपरेशन अच्छी तरह से समानांतर है, इस एल्गोरिदम का एक प्रभावी वितरित संस्करण लिखना संभव नहीं है।

ढतला हुआ वंश

जब किसी फ़ंक्शन को छोटा करने के बारे में बात की जाती है, तो (स्टोकेस्टिक) ग्रेडिएंट डिसेंट की विधि को हमेशा याद रखना उचित होता है। यह एक सरल और प्रभावी न्यूनतमकरण विधि है जो एक बिंदु पर किसी फ़ंक्शन के ग्रेडिएंट की पुनरावृत्तीय गणना करने और फिर इसे ग्रेडिएंट के विपरीत दिशा में स्थानांतरित करने पर आधारित है। ऐसा प्रत्येक कदम समाधान को न्यूनतम के करीब लाता है। ग्रेडिएंट अभी भी वैसा ही दिखता है:

ग्रेडिएंट ऑपरेटर के रैखिक गुणों के कारण यह विधि भी अच्छी तरह से समानांतर और वितरित है। ध्यान दें कि उपरोक्त सूत्र में, योग चिह्न के नीचे स्वतंत्र पद हैं। दूसरे शब्दों में, हम सभी सूचकांकों के लिए स्वतंत्र रूप से ग्रेडिएंट की गणना कर सकते हैं पहले से , इसके समानांतर, सूचकांकों के लिए ग्रेडिएंट की गणना करें से . फिर परिणामी ग्रेडिएंट्स जोड़ें। जोड़ का परिणाम वैसा ही होगा जैसे कि हमने तुरंत पहले से सूचकांकों के लिए ग्रेडिएंट की गणना की हो . इस प्रकार, यदि डेटा को डेटा के कई टुकड़ों में वितरित किया जाता है, तो प्रत्येक टुकड़े पर ग्रेडिएंट की स्वतंत्र रूप से गणना की जा सकती है, और फिर अंतिम परिणाम प्राप्त करने के लिए इन गणनाओं के परिणामों को संक्षेप में प्रस्तुत किया जा सकता है:

कार्यान्वयन के दृष्टिकोण से, यह प्रतिमान के अनुकूल है मानचित्र छोटा करना. ग्रेडिएंट डिसेंट के प्रत्येक चरण में, ग्रेडिएंट की गणना करने के लिए प्रत्येक डेटा नोड पर एक कार्य भेजा जाता है, फिर गणना किए गए ग्रेडिएंट को एक साथ एकत्र किया जाता है, और उनके योग के परिणाम का उपयोग परिणाम को बेहतर बनाने के लिए किया जाता है।

कार्यान्वयन में आसानी और MapReduce प्रतिमान में निष्पादित करने की क्षमता के बावजूद, ग्रेडिएंट डिसेंट में इसकी कमियां भी हैं। विशेष रूप से, अभिसरण प्राप्त करने के लिए आवश्यक चरणों की संख्या अन्य अधिक विशिष्ट तरीकों की तुलना में काफी अधिक है।

एलएसक्यूआर

एलएसक्यूआर समस्या को हल करने का एक और तरीका है, जो रैखिक प्रतिगमन को बहाल करने और रैखिक समीकरणों की प्रणालियों को हल करने के लिए उपयुक्त है। इसकी मुख्य विशेषता यह है कि यह मैट्रिक्स विधियों और पुनरावृत्त दृष्टिकोण के लाभों को जोड़ती है। इस पद्धति का कार्यान्वयन दोनों पुस्तकालयों में पाया जा सकता है SciPy, और में MATLAB. इस विधि का विवरण यहां नहीं दिया जाएगा (यह लेख में पाया जा सकता है एलएसक्यूआर: विरल रैखिक समीकरणों और विरल न्यूनतम वर्गों के लिए एक एल्गोरिदम). इसके बजाय, वितरित वातावरण में निष्पादन के लिए एलएसक्यूआर को अनुकूलित करने के लिए एक दृष्टिकोण का प्रदर्शन किया जाएगा।

LSQR विधि पर आधारित है द्विविकर्णीकरण प्रक्रिया. यह एक पुनरावृत्तीय प्रक्रिया है, प्रत्येक पुनरावृत्ति में निम्नलिखित चरण शामिल हैं:


लेकिन अगर हम मान लें कि मैट्रिक्स क्षैतिज रूप से विभाजित किया गया है, तो प्रत्येक पुनरावृत्ति को दो MapReduce चरणों के रूप में दर्शाया जा सकता है। इस तरह, प्रत्येक पुनरावृत्ति के दौरान डेटा स्थानांतरण को कम करना संभव है (केवल अज्ञात की संख्या के बराबर लंबाई वाले वेक्टर):

यह वह दृष्टिकोण है जिसका उपयोग रैखिक प्रतिगमन को लागू करते समय किया जाता है अपाचे इग्नाइट एमएल.

निष्कर्ष

कई रैखिक प्रतिगमन पुनर्प्राप्ति एल्गोरिदम हैं, लेकिन उनमें से सभी को सभी स्थितियों में लागू नहीं किया जा सकता है। इसलिए छोटे डेटा सेट पर सटीक समाधान के लिए क्यूआर अपघटन उत्कृष्ट है। ग्रेडिएंट डिसेंट को लागू करना सरल है और आपको तुरंत एक अनुमानित समाधान ढूंढने की अनुमति देता है। और एलएसक्यूआर पिछले दो एल्गोरिदम के सर्वोत्तम गुणों को जोड़ता है, क्योंकि इसे वितरित किया जा सकता है, ग्रेडिएंट डिसेंट की तुलना में तेजी से परिवर्तित होता है, और अनुमानित समाधान खोजने के लिए, क्यूआर अपघटन के विपरीत, एल्गोरिदम को जल्दी रोकने की भी अनुमति देता है।

स्रोत: www.habr.com