रैखिक प्रतिगमन र यसको रिकभरीको लागि विधिहरू

स्रोत: xkcd

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

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

हामी के कुरा गर्दैछौं?

हामी रैखिक निर्भरता पुनर्स्थापित गर्ने कार्यको सामना गरिरहेका छौं। इनपुट डेटाको रूपमा, कथित स्वतन्त्र चरहरूको भेक्टरहरूको सेट दिइएको छ, जसमध्ये प्रत्येक निर्भर चलको निश्चित मानसँग सम्बन्धित छ। यो डाटा दुई matrices को रूप मा प्रतिनिधित्व गर्न सकिन्छ:

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

रैखिक समीकरणहरूको प्रणाली जस्तो धेरै सुनिन्छ, हैन? यस्तो देखिन्छ, तर सम्भवतः यस्तो समीकरण प्रणालीको लागि कुनै समाधान हुनेछैन। यसको कारण शोर हो, जुन लगभग कुनै पनि वास्तविक डाटा मा उपस्थित छ। अर्को कारण रैखिक निर्भरताको अनुपस्थिति हुन सक्छ, जसलाई अतिरिक्त चरहरू परिचय गरेर लड्न सकिन्छ जुन गैर-रेखीय रूपमा मूलमा निर्भर हुन्छ। निम्न उदाहरणलाई विचार गर्नुहोस्:

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

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

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

त्यसोभए, हामीले अनियमित सामान्य रूपमा वितरित आवाजको उपस्थिति मानेका छौं। यस्तो अवस्थामा के गर्ने ? गणित मा यस मामला को लागी त्यहाँ छ र व्यापक रूपमा प्रयोग गरिन्छ अधिकतम सम्भावना विधि। छोटकरीमा, यसको सार छनोटमा निहित छ सम्भावना कार्यहरू र यसको पछिल्लो अधिकतमीकरण।

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

अब यसको सट्टा प्रतिस्थापन गरौं и हामीलाई चाहिने चरहरू हुन्:

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

जुन, बारीमा, निम्न प्रकार्यलाई कम गर्न तल आउँछ:

वैसे, यो एक विधि भनिन्छ कम से कम वर्गहरू। प्रायः सबै माथिका विचारहरू हटाइएको छ र यो विधि मात्र प्रयोग गरिन्छ।

QR विघटन

यस प्रकार्यको ग्रेडियन्ट शून्य भएको बिन्दु पत्ता लगाएर माथिको कार्यको न्यूनतम फेला पार्न सकिन्छ। र ग्रेडियन्ट निम्नानुसार लेखिनेछ:

QR विघटन न्यूनतम वर्ग विधिमा प्रयोग गरिएको न्यूनीकरण समस्या समाधान गर्ने म्याट्रिक्स विधि हो। यस सन्दर्भमा, हामी म्याट्रिक्स फारममा समीकरण पुन: लेख्छौं:

त्यसैले हामी म्याट्रिक्स विघटन गर्छौं म्याट्रिक्स सम्म и र रूपान्तरणहरूको श्रृंखला प्रदर्शन गर्नुहोस् (QR विघटन एल्गोरिदम आफैंलाई यहाँ विचार गरिने छैन, हातमा रहेको कार्यको सम्बन्धमा मात्र यसको प्रयोग):

म्याट्रिक्स अर्थोगोनल छ। यसले हामीलाई कामबाट छुटकारा पाउन अनुमति दिन्छ :

र यदि तपाइँ प्रतिस्थापन गर्नुहुन्छ मा , त्यसपछि यो काम हुनेछ । भन्ने कुरालाई ध्यानमा राखेर माथिल्लो त्रिकोणीय म्याट्रिक्स हो, यो यस्तो देखिन्छ:

यो प्रतिस्थापन विधि प्रयोग गरेर समाधान गर्न सकिन्छ। तत्व को रूपमा अवस्थित छ , अघिल्लो तत्व को रूपमा अवस्थित छ र यति मा।

यहाँ ध्यान दिन लायक छ कि QR विघटन को उपयोग को कारण परिणाम एल्गोरिथ्म को जटिलता बराबर छ । यसबाहेक, म्याट्रिक्स गुणन सञ्चालन राम्रोसँग समानान्तर गरिएको तथ्यको बावजुद, यो एल्गोरिथ्मको कुशल वितरित संस्करण लेख्न सम्भव छैन।

ग्रेडियन्ट डिसेन्ट

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

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

कार्यान्वयनको दृष्टिकोणबाट, यो प्रतिमान फिट हुन्छ मानचित्र। ढाँचा वंशको प्रत्येक चरणमा, ग्रेडियन्ट गणना गर्न प्रत्येक डेटा नोडमा एउटा कार्य पठाइन्छ, त्यसपछि गणना गरिएको ढाँचाहरू सँगै सङ्कलन गरिन्छ, र तिनीहरूको योगफलको नतिजालाई सुधार गर्न प्रयोग गरिन्छ।

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

LSQR

LSQR समस्या समाधानको लागि अर्को विधि हो, जुन रैखिक प्रतिगमन पुनर्स्थापना र रैखिक समीकरणहरूको प्रणालीहरू समाधान गर्नका लागि उपयुक्त छ। यसको मुख्य विशेषता यो हो कि यसले म्याट्रिक्स विधिहरू र पुनरावृत्ति दृष्टिकोणको फाइदाहरू संयोजन गर्दछ। यस विधिको कार्यान्वयन दुवै पुस्तकालयहरूमा फेला पार्न सकिन्छ साइपी, र मा MATLAB। यस विधिको विवरण यहाँ दिइने छैन (यो लेखमा फेला पार्न सकिन्छ LSQR: स्प्यार्स रैखिक समीकरणहरू र स्प्यार्स न्यूनतम वर्गहरूको लागि एल्गोरिदम)। यसको सट्टा, LSQR लाई वितरण गरिएको वातावरणमा कार्यान्वयन गर्न अनुकूलन गर्नको लागि एक दृष्टिकोण प्रदर्शन गरिनेछ।

LSQR विधि मा आधारित छ द्विभुजीकरण प्रक्रिया। यो एक पुनरावृत्ति प्रक्रिया हो, प्रत्येक पुनरावृत्ति निम्न चरणहरू समावेश गर्दछ:


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

यो यो दृष्टिकोण हो जुन रैखिक प्रतिगमन लागू गर्दा प्रयोग गरिन्छ Apache Ignite ML.

निष्कर्षमा

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

स्रोत: www.habr.com