લીનિયર રીગ્રેસન અને તેની પુનઃપ્રાપ્તિ માટેની પદ્ધતિઓ

સોર્સ: xkcd

રેખીય રીગ્રેસન એ ડેટા વિશ્લેષણ સાથે સંબંધિત ઘણા ક્ષેત્રો માટે મૂળભૂત ગાણિતીક નિયમોમાંનું એક છે. આનું કારણ સ્પષ્ટ છે. આ એક ખૂબ જ સરળ અને સમજી શકાય તેવું અલ્ગોરિધમ છે, જેણે સેંકડો નહીં તો ઘણા વર્ષોથી તેના વ્યાપક ઉપયોગમાં ફાળો આપ્યો છે. વિચાર એ છે કે આપણે અન્ય ચલોના સમૂહ પર એક ચલની રેખીય અવલંબન ધારીએ છીએ, અને પછી આ અવલંબનને પુનઃસ્થાપિત કરવાનો પ્રયાસ કરીએ છીએ.

પરંતુ આ લેખ વ્યવહારિક સમસ્યાઓ ઉકેલવા માટે રેખીય રીગ્રેશનનો ઉપયોગ કરવા વિશે નથી. અહીં આપણે તેની પુનઃપ્રાપ્તિ માટે વિતરિત અલ્ગોરિધમ્સના અમલીકરણની રસપ્રદ સુવિધાઓને ધ્યાનમાં લઈશું, જેનો અમને મશીન લર્નિંગ મોડ્યુલ લખતી વખતે સામનો કરવો પડ્યો હતો. અપાચે ઇગ્નાઇટ. થોડું મૂળભૂત ગણિત, મશીન લર્નિંગ અને ડિસ્ટ્રિબ્યુટેડ કમ્પ્યુટિંગ તમને હજારો નોડ્સમાં તમારો ડેટા વિતરિત કરવામાં આવે ત્યારે પણ રેખીય રીગ્રેસન કેવી રીતે કરવું તે સમજવામાં મદદ કરી શકે છે.

આપણે શું વાત કરી રહ્યા છીએ?

અમે રેખીય અવલંબનને પુનઃસ્થાપિત કરવાના કાર્યનો સામનો કરી રહ્યા છીએ. ઇનપુટ ડેટા તરીકે, માનવામાં આવે છે કે સ્વતંત્ર ચલોના વેક્ટરનો સમૂહ આપવામાં આવે છે, જેમાંથી દરેક આશ્રિત ચલના ચોક્કસ મૂલ્ય સાથે સંકળાયેલ છે. આ ડેટાને બે મેટ્રિસિસના સ્વરૂપમાં રજૂ કરી શકાય છે:

હવે, કારણ કે અવલંબન ધારવામાં આવ્યું છે, અને વધુમાં, રેખીય, અમે અમારી ધારણાને મેટ્રિસિસના ઉત્પાદનના સ્વરૂપમાં લખીશું (રેકોર્ડિંગને સરળ બનાવવા માટે, અહીં અને નીચે એવું માનવામાં આવે છે કે સમીકરણનો મુક્ત શબ્દ પાછળ છુપાયેલ છે. , અને મેટ્રિક્સની છેલ્લી કૉલમ એકમો સમાવે છે):

રેખીય સમીકરણોની સિસ્ટમ જેવું લાગે છે, તે નથી? એવું લાગે છે, પરંતુ સંભવતઃ આવી સમીકરણોની સિસ્ટમ માટે કોઈ ઉકેલો નહીં હોય. આનું કારણ ઘોંઘાટ છે, જે લગભગ કોઈપણ વાસ્તવિક ડેટામાં હાજર છે. અન્ય કારણ રેખીય અવલંબનનો અભાવ હોઈ શકે છે, જેને વધારાના ચલો રજૂ કરીને લડી શકાય છે જે મૂળ પર બિનરેખીય રીતે આધાર રાખે છે. નીચેના ઉદાહરણને ધ્યાનમાં લો:

સોર્સ: વિકિપીડિયા

આ રેખીય રીગ્રેસનનું એક સરળ ઉદાહરણ છે જે એક ચલનો સંબંધ દર્શાવે છે (અક્ષ સાથે ) અન્ય ચલમાંથી (અક્ષ સાથે ). આ ઉદાહરણને અનુરૂપ રેખીય સમીકરણોની સિસ્ટમ માટે ઉકેલ મેળવવા માટે, બધા બિંદુઓ બરાબર એ જ સીધી રેખા પર આવેલા હોવા જોઈએ. પરંતુ તે સાચું નથી. પરંતુ તેઓ અવાજને કારણે (અથવા કારણ કે રેખીય સંબંધની ધારણા ભૂલભરેલી હતી). આમ, વાસ્તવિક ડેટામાંથી રેખીય સંબંધ પુનઃસ્થાપિત કરવા માટે, સામાન્ય રીતે એક વધુ ધારણા રજૂ કરવી જરૂરી છે: ઇનપુટ ડેટામાં અવાજ હોય ​​છે અને આ અવાજ હોય ​​છે. સામાન્ય વિતરણ. તમે અન્ય પ્રકારના અવાજ વિતરણ વિશે ધારણાઓ કરી શકો છો, પરંતુ મોટા ભાગના કિસ્સાઓમાં તે સામાન્ય વિતરણ માનવામાં આવે છે, જેની આગળ ચર્ચા કરવામાં આવશે.

મહત્તમ સંભાવના પદ્ધતિ

તેથી, અમે રેન્ડમ સામાન્ય રીતે વિતરિત અવાજની હાજરી ધારી. આવી સ્થિતિમાં શું કરવું? ગણિતમાં આ કેસ માટે છે અને તેનો વ્યાપકપણે ઉપયોગ થાય છે મહત્તમ સંભાવના પદ્ધતિ. ટૂંકમાં, તેનો સાર પસંદગીમાં રહેલો છે સંભાવના કાર્યો અને તેનું અનુગામી મહત્તમકરણ.

અમે સામાન્ય અવાજ સાથે ડેટામાંથી રેખીય સંબંધને પુનઃસ્થાપિત કરવા પર પાછા આવીએ છીએ. નોંધ કરો કે ધારવામાં આવેલ રેખીય સંબંધ એ ગાણિતિક અપેક્ષા છે વર્તમાન સામાન્ય વિતરણ. તે જ સમયે, સંભાવના છે કે અવલોકનક્ષમ પદાર્થોની હાજરીને આધીન, એક અથવા બીજું મૂલ્ય લે છે , નીચે પ્રમાણે:

ચાલો હવે તેના બદલે બદલીએ и અમને જે ચલોની જરૂર છે તે છે:

જે બાકી છે તે વેક્ટર શોધવાનું છે , જેના પર આ સંભાવના મહત્તમ છે. આવા ફંક્શનને મહત્તમ કરવા માટે, સૌપ્રથમ તેનો લઘુગણક લેવો અનુકૂળ છે (ફંક્શનનો લઘુગણક ફંક્શનના જ બિંદુએ મહત્તમ પહોંચશે):

જે, બદલામાં, નીચેના કાર્યને ઘટાડવા માટે નીચે આવે છે:

માર્ગ દ્વારા, આને પદ્ધતિ કહેવામાં આવે છે ઓછામાં ઓછા ચોરસ. ઘણીવાર ઉપરોક્ત તમામ બાબતોને અવગણવામાં આવે છે અને આ પદ્ધતિનો ઉપયોગ સરળ રીતે કરવામાં આવે છે.

QR વિઘટન

ઉપરોક્ત ફંક્શનનું ન્યૂનતમ એ બિંદુ શોધીને શોધી શકાય છે કે જેના પર આ ફંક્શનનો ગ્રેડિયન્ટ શૂન્ય છે. અને ઢાળ નીચે પ્રમાણે લખવામાં આવશે:

QR વિઘટન ઓછામાં ઓછા ચોરસ પદ્ધતિમાં વપરાતી લઘુત્તમ સમસ્યાને ઉકેલવા માટેની મેટ્રિક્સ પદ્ધતિ છે. આ સંદર્ભે, અમે સમીકરણને મેટ્રિક્સ સ્વરૂપમાં ફરીથી લખીએ છીએ:

તેથી આપણે મેટ્રિક્સનું વિઘટન કરીએ છીએ મેટ્રિસિસ માટે и અને રૂપાંતરણોની શ્રેણી કરો (QR વિઘટન અલ્ગોરિધમ પોતે અહીં ધ્યાનમાં લેવામાં આવશે નહીં, ફક્ત હાથમાં રહેલા કાર્યના સંબંધમાં તેનો ઉપયોગ):

મેટ્રિક્સ ઓર્થોગોનલ છે. આ અમને કામમાંથી છુટકારો મેળવવાની મંજૂરી આપે છે :

અને જો તમે બદલો પર , પછી તે કામ કરશે . તે ધ્યાનમાં લેતા ઉપલા ત્રિકોણાકાર મેટ્રિક્સ છે, તે આના જેવો દેખાય છે:

આ અવેજી પદ્ધતિનો ઉપયોગ કરીને ઉકેલી શકાય છે. તત્વ તરીકે સ્થિત છે , અગાઉનું તત્વ તરીકે સ્થિત છે અને તેથી પર.

અહીં એ નોંધવું યોગ્ય છે કે QR વિઘટનના ઉપયોગને કારણે પરિણામી અલ્ગોરિધમની જટિલતા સમાન છે. . તદુપરાંત, મેટ્રિક્સ ગુણાકાર કામગીરી સારી રીતે સમાંતર હોવા છતાં, આ અલ્ગોરિધમનું અસરકારક વિતરિત સંસ્કરણ લખવું શક્ય નથી.

ગ્રેડિયન્ટ ડિસેન્ટ

ફંક્શનને ન્યૂનતમ કરવા વિશે વાત કરતી વખતે, તે હંમેશા (સ્ટોચેસ્ટિક) ગ્રેડિએન્ટ ડિસેન્ટની પદ્ધતિને યાદ રાખવા યોગ્ય છે. આ એક સરળ અને અસરકારક લઘુત્તમ પદ્ધતિ છે જે એક બિંદુ પર ફંક્શનના ઢાળની પુનરાવર્તિત ગણતરી પર આધારિત છે અને પછી તેને ઢાળની વિરુદ્ધ દિશામાં ખસેડવા પર આધારિત છે. આવા દરેક પગલા સોલ્યુશનને ન્યૂનતમની નજીક લાવે છે. ઢાળ હજુ પણ સમાન દેખાય છે:

ગ્રેડિયન્ટ ઓપરેટરના રેખીય ગુણધર્મોને કારણે આ પદ્ધતિ સારી રીતે સમાંતર અને વિતરિત પણ છે. નોંધ કરો કે ઉપરોક્ત સૂત્રમાં, સરવાળા ચિહ્ન હેઠળ સ્વતંત્ર શબ્દો છે. બીજા શબ્દોમાં કહીએ તો, આપણે બધા સૂચકાંકો માટે સ્વતંત્ર રીતે ઢાળની ગણતરી કરી શકીએ છીએ પ્રથમ થી , આની સાથે સમાંતર, સાથે સૂચકાંકો માટે ઢાળની ગણતરી કરો માટે . પછી પરિણામી ઢાળ ઉમેરો. ઉમેરાનું પરિણામ એ જ હશે કે જો આપણે તરત જ પ્રથમથી સૂચકાંકો માટેના ઢાળની ગણતરી કરીએ . આમ, જો ડેટાને ડેટાના કેટલાક ટુકડાઓ વચ્ચે વિતરિત કરવામાં આવે છે, તો દરેક ભાગ પર ઢાળની સ્વતંત્ર રીતે ગણતરી કરી શકાય છે, અને પછી અંતિમ પરિણામ મેળવવા માટે આ ગણતરીઓના પરિણામોનો સરવાળો કરી શકાય છે:

અમલીકરણના દૃષ્ટિકોણથી, આ દાખલા સાથે બંધબેસે છે નકશો. ગ્રેડિયન્ટ ડિસેન્ટના દરેક સ્ટેપ પર, દરેક ડેટા નોડને ગ્રેડિયન્ટની ગણતરી કરવા માટે એક ટાસ્ક મોકલવામાં આવે છે, પછી ગણતરી કરેલ ગ્રેડિયન્ટ એકસાથે એકત્રિત કરવામાં આવે છે, અને તેમના સરવાળાના પરિણામનો ઉપયોગ પરિણામને સુધારવા માટે થાય છે.

અમલીકરણની સરળતા અને મેપરેડ્યુસ પેરાડાઈમમાં અમલ કરવાની ક્ષમતા હોવા છતાં, ગ્રેડિયન્ટ ડિસેન્ટમાં પણ તેની ખામીઓ છે. ખાસ કરીને, કન્વર્જન્સ હાંસલ કરવા માટે જરૂરી પગલાંઓની સંખ્યા અન્ય વધુ વિશિષ્ટ પદ્ધતિઓની તુલનામાં નોંધપાત્ર રીતે વધારે છે.

LSQRLanguage

LSQRLanguage સમસ્યાને ઉકેલવા માટેની બીજી પદ્ધતિ છે, જે રેખીય રીગ્રેસનને પુનઃસ્થાપિત કરવા અને રેખીય સમીકરણોની સિસ્ટમોને ઉકેલવા માટે બંને માટે યોગ્ય છે. તેની મુખ્ય વિશેષતા એ છે કે તે મેટ્રિક્સ પદ્ધતિઓના ફાયદા અને પુનરાવર્તિત અભિગમને જોડે છે. આ પદ્ધતિના અમલીકરણો બંને પુસ્તકાલયોમાં મળી શકે છે સાયપી, અને માં મેટલેબ Language. આ પદ્ધતિનું વર્ણન અહીં આપવામાં આવશે નહીં (તે લેખમાં મળી શકે છે LSQR: છૂટાછવાયા રેખીય સમીકરણો અને છૂટાછવાયા લઘુત્તમ ચોરસ માટેનું અલ્ગોરિધમ). તેના બદલે, વિતરિત વાતાવરણમાં LSQR ને અમલમાં મૂકવા માટે એક અભિગમ દર્શાવવામાં આવશે.

LSQR પદ્ધતિ પર આધારિત છે દ્વિકોણીકરણ પ્રક્રિયા. આ એક પુનરાવર્તિત પ્રક્રિયા છે, દરેક પુનરાવર્તનમાં નીચેના પગલાંઓનો સમાવેશ થાય છે:


પરંતુ જો આપણે ધારીએ કે મેટ્રિક્સ આડી રીતે વિભાજિત કરવામાં આવે છે, પછી દરેક પુનરાવર્તનને બે MapReduce પગલાં તરીકે રજૂ કરી શકાય છે. આ રીતે, દરેક પુનરાવૃત્તિ દરમિયાન ડેટા ટ્રાન્સફર ઘટાડવાનું શક્ય છે (ફક્ત અજાણ્યાઓની સંખ્યા જેટલી લંબાઈ ધરાવતા વેક્ટર):

માં રેખીય રીગ્રેસન અમલમાં મૂકતી વખતે આ અભિગમનો ઉપયોગ થાય છે અપાચે ઇગ્નાઇટ એમએલ.

નિષ્કર્ષ

ત્યાં ઘણા રેખીય રીગ્રેસન પુનઃપ્રાપ્તિ અલ્ગોરિધમ્સ છે, પરંતુ તે બધાને બધી પરિસ્થિતિઓમાં લાગુ કરી શકાતા નથી. તેથી નાના ડેટા સેટ્સ પર સચોટ ઉકેલ માટે QR વિઘટન ઉત્તમ છે. ગ્રેડિયન્ટ ડિસેન્ટ અમલમાં મૂકવું સરળ છે અને તમને ઝડપથી અંદાજિત ઉકેલ શોધવાની મંજૂરી આપે છે. અને LSQR એ અગાઉના બે અલ્ગોરિધમ્સના શ્રેષ્ઠ ગુણધર્મોને જોડે છે, કારણ કે તે વિતરિત કરી શકાય છે, તે ગ્રેડિયન્ટ ડિસેન્ટની સરખામણીમાં ઝડપથી કન્વર્જ થાય છે, અને અંદાજિત ઉકેલ શોધવા માટે, QR વિઘટનથી વિપરીત, અલ્ગોરિધમને વહેલા બંધ કરવાની મંજૂરી આપે છે.

સોર્સ: www.habr.com