ലീനിയർ റിഗ്രഷനും അതിന്റെ വീണ്ടെടുക്കലിനുള്ള രീതികളും

അവലംബം: xkcd

ഡാറ്റ വിശകലനവുമായി ബന്ധപ്പെട്ട നിരവധി മേഖലകൾക്കുള്ള അടിസ്ഥാന അൽഗോരിതങ്ങളിൽ ഒന്നാണ് ലീനിയർ റിഗ്രഷൻ. ഇതിന്റെ കാരണം വ്യക്തമാണ്. ഇത് വളരെ ലളിതവും മനസ്സിലാക്കാവുന്നതുമായ അൽഗോരിതം ആണ്, ഇത് നൂറുകണക്കിന് വർഷങ്ങളല്ലെങ്കിൽ നൂറുകണക്കിന് വർഷങ്ങളായി അതിന്റെ വ്യാപകമായ ഉപയോഗത്തിന് സംഭാവന നൽകിയിട്ടുണ്ട്. മറ്റ് വേരിയബിളുകളുടെ ഒരു കൂട്ടത്തിൽ ഒരു വേരിയബിളിന്റെ രേഖീയ ആശ്രിതത്വം ഞങ്ങൾ അനുമാനിക്കുന്നു, തുടർന്ന് ഈ ആശ്രിതത്വം പുനഃസ്ഥാപിക്കാൻ ശ്രമിക്കുക എന്നതാണ് ആശയം.

എന്നാൽ ഈ ലേഖനം പ്രായോഗിക പ്രശ്നങ്ങൾ പരിഹരിക്കാൻ ലീനിയർ റിഗ്രഷൻ ഉപയോഗിക്കുന്നതിനെക്കുറിച്ചല്ല. ഒരു മെഷീൻ ലേണിംഗ് മൊഡ്യൂൾ എഴുതുമ്പോൾ ഞങ്ങൾ നേരിട്ട അതിന്റെ വീണ്ടെടുക്കലിനായി വിതരണം ചെയ്ത അൽഗോരിതങ്ങൾ നടപ്പിലാക്കുന്നതിന്റെ രസകരമായ സവിശേഷതകൾ ഇവിടെ ഞങ്ങൾ പരിഗണിക്കും. അപ്പാച്ചെ ഇഗ്നൈറ്റ്. നിങ്ങളുടെ ഡാറ്റ ആയിരക്കണക്കിന് നോഡുകളിൽ വിതരണം ചെയ്യുമ്പോൾ പോലും ലീനിയർ റിഗ്രഷൻ എങ്ങനെ നിർവഹിക്കാമെന്ന് മനസിലാക്കാൻ ഒരു ചെറിയ അടിസ്ഥാന ഗണിതം, മെഷീൻ ലേണിംഗ്, വിതരണം ചെയ്ത കമ്പ്യൂട്ടിംഗ് എന്നിവ നിങ്ങളെ സഹായിക്കും.

നമ്മൾ എന്തിനെക്കുറിച്ചാണ് സംസാരിക്കുന്നത്?

രേഖീയ ആശ്രിതത്വം പുനഃസ്ഥാപിക്കുന്നതിനുള്ള ചുമതലയാണ് ഞങ്ങൾ നേരിടുന്നത്. ഇൻപുട്ട് ഡാറ്റ എന്ന നിലയിൽ, സ്വതന്ത്ര വേരിയബിളുകളുടെ ഒരു കൂട്ടം വെക്റ്ററുകൾ നൽകിയിരിക്കുന്നു, അവ ഓരോന്നും ആശ്രിത വേരിയബിളിന്റെ ഒരു നിശ്ചിത മൂല്യവുമായി ബന്ധപ്പെട്ടിരിക്കുന്നു. ഈ ഡാറ്റ രണ്ട് മെട്രിക്സുകളുടെ രൂപത്തിൽ പ്രതിനിധീകരിക്കാം:

ഇപ്പോൾ, ആശ്രിതത്വം അനുമാനിക്കപ്പെടുന്നതിനാൽ, കൂടാതെ, രേഖീയമായതിനാൽ, മെട്രിക്സുകളുടെ ഒരു ഉൽപ്പന്നത്തിന്റെ രൂപത്തിൽ ഞങ്ങൾ നമ്മുടെ അനുമാനം എഴുതും (റെക്കോർഡിംഗ് ലളിതമാക്കാൻ, ഇവിടെയും താഴെയും സമവാക്യത്തിന്റെ സ്വതന്ത്ര പദം പിന്നിൽ മറഞ്ഞിരിക്കുന്നുവെന്ന് അനുമാനിക്കുന്നു. , കൂടാതെ മാട്രിക്സിന്റെ അവസാന നിരയും യൂണിറ്റുകൾ അടങ്ങിയിരിക്കുന്നു):

രേഖീയ സമവാക്യങ്ങളുടെ ഒരു സിസ്റ്റം പോലെ തോന്നുന്നു, അല്ലേ? ഇത് തോന്നുന്നു, പക്ഷേ മിക്കവാറും അത്തരമൊരു സമവാക്യ സംവിധാനത്തിന് പരിഹാരങ്ങളൊന്നും ഉണ്ടാകില്ല. മിക്കവാറും എല്ലാ യഥാർത്ഥ ഡാറ്റയിലും ഉള്ള ശബ്ദമാണ് ഇതിനുള്ള കാരണം. രേഖീയ ആശ്രിതത്വത്തിന്റെ അഭാവമാണ് മറ്റൊരു കാരണം, യഥാർത്ഥമായവയെ രേഖീയമായി ആശ്രയിക്കാത്ത അധിക വേരിയബിളുകൾ അവതരിപ്പിച്ചുകൊണ്ട് ഇതിനെ ചെറുക്കാനാകും. ഇനിപ്പറയുന്ന ഉദാഹരണം പരിഗണിക്കുക:

അവലംബം: വിക്കിപീഡിയ

ഒരു വേരിയബിളിന്റെ (അക്ഷത്തിനൊപ്പം) ബന്ധം കാണിക്കുന്ന ലീനിയർ റിഗ്രഷന്റെ ലളിതമായ ഉദാഹരണമാണിത് ) മറ്റൊരു വേരിയബിളിൽ നിന്ന് (അക്ഷത്തിനൊപ്പം ). ഈ ഉദാഹരണവുമായി പൊരുത്തപ്പെടുന്ന രേഖീയ സമവാക്യങ്ങളുടെ സിസ്റ്റത്തിന് ഒരു പരിഹാരം ലഭിക്കുന്നതിന്, എല്ലാ പോയിന്റുകളും ഒരേ നേർരേഖയിൽ തന്നെ കിടക്കണം. എന്നാൽ അത് സത്യമല്ല. എന്നാൽ അവർ ഒരേ നേർരേഖയിൽ കിടക്കുന്നില്ല, ശബ്ദം കാരണം (അല്ലെങ്കിൽ ഒരു രേഖീയ ബന്ധത്തിന്റെ അനുമാനം തെറ്റായിരുന്നു). അതിനാൽ, യഥാർത്ഥ ഡാറ്റയിൽ നിന്ന് ഒരു രേഖീയ ബന്ധം പുനഃസ്ഥാപിക്കുന്നതിന്, സാധാരണയായി ഒരു അനുമാനം കൂടി അവതരിപ്പിക്കേണ്ടത് ആവശ്യമാണ്: ഇൻപുട്ട് ഡാറ്റയിൽ ശബ്ദവും ഈ ശബ്ദവും അടങ്ങിയിരിക്കുന്നു. സാധാരണ വിതരണം. മറ്റ് തരത്തിലുള്ള ശബ്ദ വിതരണത്തെക്കുറിച്ച് നിങ്ങൾക്ക് അനുമാനങ്ങൾ നടത്താം, എന്നാൽ ബഹുഭൂരിപക്ഷം കേസുകളിലും ഇത് പരിഗണിക്കപ്പെടുന്ന സാധാരണ വിതരണമാണ്, അത് കൂടുതൽ ചർച്ച ചെയ്യപ്പെടും.

പരമാവധി സാധ്യതയുള്ള രീതി

അതിനാൽ, ക്രമരഹിതമായി സാധാരണ വിതരണം ചെയ്യുന്ന ശബ്ദത്തിന്റെ സാന്നിധ്യം ഞങ്ങൾ അനുമാനിച്ചു. അത്തരമൊരു സാഹചര്യത്തിൽ എന്തുചെയ്യണം? ഗണിതശാസ്ത്രത്തിൽ ഈ കേസിൽ വ്യാപകമായി ഉപയോഗിക്കപ്പെടുന്നു പരമാവധി സാധ്യത രീതി. ചുരുക്കത്തിൽ, അതിന്റെ സാരാംശം തിരഞ്ഞെടുപ്പിലാണ് സാധ്യതാ പ്രവർത്തനങ്ങൾ അതിന്റെ തുടർന്നുള്ള മാക്സിമൈസേഷനും.

സാധാരണ ശബ്ദമുള്ള ഡാറ്റയിൽ നിന്ന് ഒരു രേഖീയ ബന്ധം പുനഃസ്ഥാപിക്കുന്നതിലേക്ക് ഞങ്ങൾ മടങ്ങുന്നു. അനുമാനിക്കപ്പെടുന്ന രേഖീയ ബന്ധം ഗണിതശാസ്ത്ര പ്രതീക്ഷയാണെന്ന് ശ്രദ്ധിക്കുക നിലവിലുള്ള സാധാരണ വിതരണം. അതേ സമയം, സാധ്യത നിരീക്ഷിക്കാവുന്നവയുടെ സാന്നിധ്യത്തിന് വിധേയമായി ഒരു മൂല്യം അല്ലെങ്കിൽ മറ്റൊന്ന് എടുക്കുന്നു , ഇനിപ്പറയുന്ന രീതിയിൽ:

പകരം നമുക്ക് ഇപ്പോൾ പകരം വയ്ക്കാം и നമുക്ക് ആവശ്യമുള്ള വേരിയബിളുകൾ ഇവയാണ്:

വെക്റ്റർ കണ്ടെത്തുക മാത്രമാണ് അവശേഷിക്കുന്നത് , ഈ പ്രോബബിലിറ്റി പരമാവധി ആണ്. അത്തരമൊരു ഫംഗ്‌ഷൻ പരമാവധിയാക്കുന്നതിന്, ആദ്യം അതിന്റെ ഒരു ലോഗരിതം എടുക്കുന്നത് സൗകര്യപ്രദമാണ് (ഫംഗ്‌ഷന്റെ ലോഗരിതം ഫംഗ്‌ഷന്റെ അതേ പോയിന്റിൽ പരമാവധി എത്തും):

ഇത്, ഇനിപ്പറയുന്ന ഫംഗ്ഷൻ ചെറുതാക്കുന്നതിലേക്ക് വരുന്നു:

വഴിയിൽ, ഇതിനെ ഒരു രീതി എന്ന് വിളിക്കുന്നു കുറഞ്ഞ ചതുരങ്ങൾ. പലപ്പോഴും മുകളിലുള്ള എല്ലാ പരിഗണനകളും ഒഴിവാക്കുകയും ഈ രീതി ലളിതമായി ഉപയോഗിക്കുകയും ചെയ്യുന്നു.

ക്യുആർ വിഘടനം

ഈ ഫംഗ്‌ഷന്റെ ഗ്രേഡിയന്റ് പൂജ്യമായിരിക്കുന്ന പോയിന്റ് കണ്ടെത്തുന്നതിലൂടെ മുകളിലുള്ള ഫംഗ്‌ഷന്റെ ഏറ്റവും കുറഞ്ഞത് കണ്ടെത്താനാകും. ഗ്രേഡിയന്റ് ഇനിപ്പറയുന്ന രീതിയിൽ എഴുതപ്പെടും:

ക്യുആർ വിഘടനം മിനിമൈസേഷൻ പ്രശ്നം പരിഹരിക്കുന്നതിനുള്ള ഒരു മാട്രിക്സ് രീതിയാണ് ഏറ്റവും കുറഞ്ഞ സ്ക്വയർ രീതി. ഇക്കാര്യത്തിൽ, ഞങ്ങൾ സമവാക്യം മാട്രിക്സ് രൂപത്തിൽ മാറ്റിയെഴുതുന്നു:

അതിനാൽ ഞങ്ങൾ മാട്രിക്സ് വിഘടിപ്പിക്കുന്നു മെട്രിക്സുകളിലേക്ക് и കൂടാതെ പരിവർത്തനങ്ങളുടെ ഒരു പരമ്പര നടത്തുക (ക്യുആർ വിഘടിപ്പിക്കൽ അൽഗോരിതം തന്നെ ഇവിടെ പരിഗണിക്കില്ല, ചുമതലയുമായി ബന്ധപ്പെട്ട് അതിന്റെ ഉപയോഗം മാത്രം):

മാട്രിക്സ് ഓർത്തോഗണൽ ആണ്. ജോലിയിൽ നിന്ന് രക്ഷപ്പെടാൻ ഇത് ഞങ്ങളെ അനുവദിക്കുന്നു :

നിങ്ങൾ മാറ്റിസ്ഥാപിക്കുകയാണെങ്കിൽ ഓൺ , അപ്പോൾ അത് പ്രവർത്തിക്കും . അത് കണക്കിലെടുക്കുമ്പോൾ ഒരു മുകളിലെ ത്രികോണ മാട്രിക്സ് ആണ്, ഇത് ഇതുപോലെ കാണപ്പെടുന്നു:

സബ്സ്റ്റിറ്റ്യൂഷൻ രീതി ഉപയോഗിച്ച് ഇത് പരിഹരിക്കാവുന്നതാണ്. ഘടകം ആയി സ്ഥിതി ചെയ്യുന്നു , മുമ്പത്തെ ഘടകം ആയി സ്ഥിതി ചെയ്യുന്നു അങ്ങനെ പോകുന്നു.

ക്യുആർ വിഘടനത്തിന്റെ ഉപയോഗം മൂലം ഉണ്ടാകുന്ന അൽഗോരിതത്തിന്റെ സങ്കീർണ്ണത തുല്യമാണെന്നത് ഇവിടെ ശ്രദ്ധിക്കേണ്ടതാണ്. . മാത്രമല്ല, മാട്രിക്സ് ഗുണന പ്രവർത്തനം നന്നായി സമാന്തരമായിട്ടും, ഈ അൽഗോരിതത്തിന്റെ കാര്യക്ഷമമായ വിതരണം ചെയ്ത പതിപ്പ് എഴുതാൻ സാധ്യമല്ല.

ഗ്രേഡിയന്റ് ഡിസന്റ്

ഒരു ഫംഗ്‌ഷൻ ചെറുതാക്കുന്നതിനെക്കുറിച്ച് സംസാരിക്കുമ്പോൾ, (സ്‌റ്റോക്കാസ്റ്റിക്) ഗ്രേഡിയന്റ് ഇറക്കത്തിന്റെ രീതി എപ്പോഴും ഓർമ്മിക്കുന്നത് മൂല്യവത്താണ്. ഒരു ഘട്ടത്തിൽ ഒരു ഫംഗ്‌ഷന്റെ ഗ്രേഡിയന്റ് ആവർത്തിച്ച് കണക്കാക്കുകയും അതിനെ ഗ്രേഡിയന്റിന് വിപരീത ദിശയിലേക്ക് മാറ്റുകയും ചെയ്യുന്നതിനെ അടിസ്ഥാനമാക്കിയുള്ള ലളിതവും ഫലപ്രദവുമായ മിനിമൈസേഷൻ രീതിയാണിത്. അത്തരം ഓരോ ഘട്ടവും പരിഹാരത്തെ ഏറ്റവും കുറഞ്ഞതിലേക്ക് അടുപ്പിക്കുന്നു. ഗ്രേഡിയന്റ് ഇപ്പോഴും സമാനമാണ്:

ഗ്രേഡിയന്റ് ഓപ്പറേറ്ററുടെ ലീനിയർ പ്രോപ്പർട്ടികൾ കാരണം ഈ രീതിയും നന്നായി സമാന്തരമായി വിതരണം ചെയ്യപ്പെടുന്നു. മുകളിലുള്ള ഫോർമുലയിൽ, സം ചിഹ്നത്തിന് കീഴിൽ സ്വതന്ത്ര നിബന്ധനകൾ ഉണ്ടെന്ന് ശ്രദ്ധിക്കുക. മറ്റൊരു വിധത്തിൽ പറഞ്ഞാൽ, എല്ലാ സൂചികകൾക്കും നമുക്ക് സ്വതന്ത്രമായി ഗ്രേഡിയന്റ് കണക്കാക്കാം ആദ്യം മുതൽ , ഇതിന് സമാന്തരമായി, സൂചികകൾക്കുള്ള ഗ്രേഡിയന്റ് കണക്കാക്കുക ഇതിനായി . തുടർന്ന് തത്ഫലമായുണ്ടാകുന്ന ഗ്രേഡിയന്റുകൾ ചേർക്കുക. ആദ്യം മുതൽ സൂചികകൾക്കുള്ള ഗ്രേഡിയന്റ് ഞങ്ങൾ ഉടൻ കണക്കാക്കിയതിന് തുല്യമായിരിക്കും കൂട്ടിച്ചേർക്കലിന്റെ ഫലം . അതിനാൽ, ഡാറ്റയുടെ നിരവധി കഷണങ്ങൾക്കിടയിൽ ഡാറ്റ വിതരണം ചെയ്യുകയാണെങ്കിൽ, ഓരോ ഭാഗത്തിലും ഗ്രേഡിയന്റ് സ്വതന്ത്രമായി കണക്കാക്കാം, തുടർന്ന് അന്തിമഫലം ലഭിക്കുന്നതിന് ഈ കണക്കുകൂട്ടലുകളുടെ ഫലങ്ങൾ സംഗ്രഹിക്കാം:

നടപ്പാക്കൽ വീക്ഷണകോണിൽ നിന്ന്, ഇത് മാതൃകയ്ക്ക് അനുയോജ്യമാണ് മാപ്പ് റിഡ്യൂസ്. ഗ്രേഡിയന്റ് ഇറക്കത്തിന്റെ ഓരോ ഘട്ടത്തിലും, ഗ്രേഡിയന്റ് കണക്കാക്കാൻ ഓരോ ഡാറ്റ നോഡിലേക്കും ഒരു ടാസ്‌ക് അയയ്‌ക്കുന്നു, തുടർന്ന് കണക്കാക്കിയ ഗ്രേഡിയന്റുകൾ ഒരുമിച്ച് ശേഖരിക്കുകയും അവയുടെ തുകയുടെ ഫലം ഫലം മെച്ചപ്പെടുത്താൻ ഉപയോഗിക്കുകയും ചെയ്യുന്നു.

നടപ്പിലാക്കുന്നതിന്റെ എളുപ്പവും MapReduce മാതൃകയിൽ എക്സിക്യൂട്ട് ചെയ്യാനുള്ള കഴിവും ഉണ്ടെങ്കിലും, ഗ്രേഡിയന്റ് ഡിസെന്റിന് അതിന്റെ പോരായ്മകളുണ്ട്. പ്രത്യേകിച്ചും, മറ്റ് പ്രത്യേക രീതികളുമായി താരതമ്യപ്പെടുത്തുമ്പോൾ ഒത്തുചേരൽ നേടുന്നതിന് ആവശ്യമായ ഘട്ടങ്ങളുടെ എണ്ണം വളരെ കൂടുതലാണ്.

LSQR

LSQR പ്രശ്നം പരിഹരിക്കുന്നതിനുള്ള മറ്റൊരു രീതിയാണ്, ഇത് ലീനിയർ റിഗ്രഷൻ പുനഃസ്ഥാപിക്കുന്നതിനും ലീനിയർ സമവാക്യങ്ങളുടെ സിസ്റ്റങ്ങൾ പരിഹരിക്കുന്നതിനും അനുയോജ്യമാണ്. മാട്രിക്സ് രീതികളുടെ ഗുണങ്ങളും ഒരു ആവർത്തന സമീപനവും സംയോജിപ്പിക്കുന്നു എന്നതാണ് ഇതിന്റെ പ്രധാന സവിശേഷത. ഈ രീതിയുടെ പ്രയോഗങ്ങൾ രണ്ട് ലൈബ്രറികളിലും കാണാം SciPy, കൂടാതെ മാറ്റ്‌ലാബ്. ഈ രീതിയുടെ ഒരു വിവരണം ഇവിടെ നൽകില്ല (ഇത് ലേഖനത്തിൽ കാണാം LSQR: വിരളമായ രേഖീയ സമവാക്യങ്ങൾക്കും വിരളമായ ഏറ്റവും കുറഞ്ഞ ചതുരങ്ങൾക്കുമുള്ള ഒരു അൽഗോരിതം). പകരം, ഒരു വിതരണം ചെയ്ത പരിതസ്ഥിതിയിൽ എൽഎസ്‌ക്യുആർ നടപ്പിലാക്കുന്നതിനുള്ള ഒരു സമീപനം പ്രദർശിപ്പിക്കും.

LSQR രീതി അടിസ്ഥാനമാക്കിയുള്ളതാണ് bidiagonalization നടപടിക്രമം. ഇതൊരു ആവർത്തന പ്രക്രിയയാണ്, ഓരോ ആവർത്തനവും ഇനിപ്പറയുന്ന ഘട്ടങ്ങൾ ഉൾക്കൊള്ളുന്നു:


എന്നാൽ ഞങ്ങൾ മാട്രിക്സ് എന്ന് കരുതുകയാണെങ്കിൽ തിരശ്ചീനമായി വിഭജിച്ചിരിക്കുന്നു, തുടർന്ന് ഓരോ ആവർത്തനവും രണ്ട് MapReduce ഘട്ടങ്ങളായി പ്രതിനിധീകരിക്കാം. ഈ രീതിയിൽ, ഓരോ ആവർത്തന സമയത്തും ഡാറ്റ കൈമാറ്റം കുറയ്ക്കാൻ സാധിക്കും (അജ്ഞാതരുടെ എണ്ണത്തിന് തുല്യമായ നീളമുള്ള വെക്റ്ററുകൾ മാത്രം):

ലീനിയർ റിഗ്രഷൻ നടപ്പിലാക്കുമ്പോൾ ഈ സമീപനമാണ് ഉപയോഗിക്കുന്നത് അപ്പാച്ചെ ഇഗ്നൈറ്റ് എം.എൽ.

തീരുമാനം

നിരവധി ലീനിയർ റിഗ്രഷൻ വീണ്ടെടുക്കൽ അൽഗോരിതങ്ങൾ ഉണ്ട്, എന്നാൽ അവയെല്ലാം എല്ലാ സാഹചര്യങ്ങളിലും പ്രയോഗിക്കാൻ കഴിയില്ല. അതിനാൽ ചെറിയ ഡാറ്റാ സെറ്റുകളിൽ കൃത്യമായ പരിഹാരത്തിന് QR വിഘടിപ്പിക്കൽ മികച്ചതാണ്. ഗ്രേഡിയന്റ് ഡിസെന്റ് നടപ്പിലാക്കാൻ ലളിതമാണ് കൂടാതെ ഒരു ഏകദേശ പരിഹാരം വേഗത്തിൽ കണ്ടെത്താൻ നിങ്ങളെ അനുവദിക്കുന്നു. LSQR മുമ്പത്തെ രണ്ട് അൽഗരിതങ്ങളുടെ മികച്ച ഗുണങ്ങളെ സംയോജിപ്പിക്കുന്നു, കാരണം ഇത് വിതരണം ചെയ്യാൻ കഴിയും, ഗ്രേഡിയന്റ് ഡിസൻറുമായി താരതമ്യപ്പെടുത്തുമ്പോൾ വേഗത്തിൽ ഒത്തുചേരുന്നു, കൂടാതെ ഏകദേശ പരിഹാരം കണ്ടെത്തുന്നതിന് QR വിഘടനത്തിൽ നിന്ന് വ്യത്യസ്തമായി അൽഗോരിതം നേരത്തെ നിർത്താൻ അനുവദിക്കുന്നു.

അവലംബം: www.habr.com