මූලාශ්රය:
රේඛීය ප්‍රතිගාමීත්වය දත්ත විශ්ලේෂණයට අදාළ බොහෝ ක්ෂේත්‍ර සඳහා මූලික ඇල්ගොරිතමයකි. මෙයට හේතුව පැහැදිලිය. මෙය ඉතා සරල සහ තේරුම්ගත හැකි ඇල්ගොරිතමයක් වන අතර, එය වසර සිය ගණනක් නොවේ නම් දස දහස් ගණනක් පුරා පැතිරී ඇති භාවිතයට දායක වී ඇත. අදහස නම්, අපි වෙනත් විචල්‍ය සමූහයක් මත එක් විචල්‍යයක රේඛීය රඳා පැවැත්මක් උපකල්පනය කර, පසුව මෙම යැපීම ප්රතිස්ථාපනය කිරීමට උත්සාහ කරමු.
නමුත් මෙම ලිපිය ප්‍රායෝගික ගැටළු විසඳීම සඳහා රේඛීය ප්‍රතිගාමීත්වය භාවිතා කිරීම ගැන නොවේ. යන්ත්‍ර ඉගෙනුම් මොඩියුලයක් ලිවීමේදී අපට හමු වූ එහි ප්රතිසාධනය සඳහා බෙදා හරින ලද ඇල්ගොරිතම ක්රියාත්මක කිරීමේ සිත්ගන්නාසුලු ලක්ෂණ අපි මෙහිදී සලකා බලමු. . කුඩා මූලික ගණිතය, යන්ත්‍ර ඉගෙනීම සහ බෙදා හරින ලද පරිගණනය මඟින් ඔබේ දත්ත නෝඩ් දහස් ගණනක් හරහා බෙදා හරින විට පවා රේඛීය ප්‍රතිගාමීත්වය සිදු කරන්නේ කෙසේදැයි සොයා ගැනීමට ඔබට උපකාර කළ හැක.
අපි කතා කරන්නේ කුමක් ගැනද?
රේඛීය යැපීම යථා තත්ත්වයට පත් කිරීමේ කාර්යයට අප මුහුණ දී සිටිමු. ආදාන දත්ත ලෙස, ස්වාධීන යැයි කියනු ලබන විචල්‍යවල දෛශික කට්ටලයක් ලබා දී ඇති අතර, ඒ සෑම එකක්ම රඳා පවතින විචල්‍යයේ නිශ්චිත අගයක් සමඟ සම්බන්ධ වේ. මෙම දත්ත matrices දෙකක ස්වරූපයෙන් නිරූපණය කළ හැක:
දැන්, යැපීම උපකල්පනය කර, එපමනක් නොව, රේඛීය බැවින්, අපි අපගේ උපකල්පනය න්‍යාසවල නිෂ්පාදනයක් ලෙස ලියන්නෙමු (පටිගත කිරීම සරල කිරීම සඳහා, මෙහි සහ පහළින් සමීකරණයේ නිදහස් පදය පිටුපස සැඟවී ඇතැයි උපකල්පනය කෙරේ. , සහ matrix හි අවසාන තීරුව ඒකක අඩංගු වේ):
රේඛීය සමීකරණ පද්ධතියක් වගේ නේද? එය පෙනේ, නමුත් බොහෝ විට එවැනි සමීකරණ පද්ධතියකට විසඳුම් නොලැබෙනු ඇත. මෙයට හේතුව ඕනෑම සැබෑ දත්තයක පාහේ පවතින ශබ්දයයි. තවත් හේතුවක් වන්නේ රේඛීය යැපීම නොමැතිකම විය හැකි අතර, මුල් ඒවා මත රේඛීය නොවන ලෙස රඳා පවතින අතිරේක විචල්‍යයන් හඳුන්වා දීමෙන් සටන් කළ හැකිය. පහත උදාහරණය සලකා බලන්න:
මූලාශ්රය:
මෙය එක් විචල්‍යයක (අක්ෂය දිගේ) සම්බන්ධතාවය පෙන්වන රේඛීය ප්‍රතිගාමීත්වයේ සරල උදාහරණයකි ) වෙනත් විචල්‍යයකින් (අක්ෂය දිගේ ) මෙම උදාහරණයට අනුරූප වන රේඛීය සමීකරණ පද්ධතියට විසඳුමක් ලබා ගැනීම සඳහා, සියලුම ලක්ෂ්‍ය හරියටම එකම සරල රේඛාවක පිහිටා තිබිය යුතුය. නමුත් එය සත්‍ය නොවේ. නමුත් ඒවා හරියටම ඝෝෂාව නිසා (හෝ රේඛීය සම්බන්ධතාවයක උපකල්පනය වැරදි නිසා) එකම සරල රේඛාවක වැතිරෙන්නේ නැත. මේ අනුව, සැබෑ දත්ත වලින් රේඛීය සම්බන්ධතාවයක් යථා තත්ත්වයට පත් කිරීම සඳහා, සාමාන්යයෙන් තවත් එක් උපකල්පනයක් හඳුන්වා දීම අවශ්ය වේ: ආදාන දත්තවල ශබ්දය අඩංගු වන අතර මෙම ශබ්දය ඇත. . වෙනත් ආකාරයේ ශබ්ද බෙදාහැරීම් පිළිබඳව ඔබට උපකල්පන කළ හැකිය, නමුත් බොහෝ අවස්ථාවලදී එය සලකා බලනු ලබන සාමාන්ය ව්යාප්තිය, එය තවදුරටත් සාකච්ඡා කරනු ඇත.
උපරිම සම්භාවිතා ක්රමය
එබැවින්, අහඹු ලෙස බෙදා හරින ලද ශබ්දයක් ඇති බව අපි උපකල්පනය කළෙමු. එවැනි තත්වයක් තුළ කුමක් කළ යුතුද? මෙම අවස්ථාව සඳහා ගණිතයේ ඇති අතර එය බහුලව භාවිතා වේ . කෙටියෙන් කිවහොත්, එහි සාරය තේරීම තුළ පවතී සහ එහි පසුව උපරිම කිරීම.
අපි සාමාන්ය ශබ්දය සමඟ දත්ත වලින් රේඛීය සම්බන්ධතාවයක් ප්රතිෂ්ඨාපනය කිරීමට නැවත පැමිණෙමු. උපකල්පනය කරන ලද රේඛීය සම්බන්ධතාවය ගණිතමය අපේක්ෂාව බව සලකන්න පවතින සාමාන්ය ව්යාප්තිය. ඒ සමගම, සම්භාවිතාව නිරීක්ෂණය කළ හැකි දේවලට යටත්ව එක් හෝ තවත් අගයක් ගනී , පහත පරිදි:
අපි දැන් ඒ වෙනුවට ආදේශ කරමු и අපට අවශ්ය විචල්‍ය වන්නේ:
ඉතිරිව ඇත්තේ දෛශිකය සොයා ගැනීමයි , මෙම සම්භාවිතාව උපරිම වේ. එවැනි ශ්‍රිතයක් උපරිම කිරීම සඳහා, ප්‍රථමයෙන් එහි ලඝුගණකයක් ගැනීම පහසුය (ශ්‍රිතයේ ලඝුගණකය ශ්‍රිතයේම එම ලක්ෂ්‍යයේදීම උපරිමයට ළඟා වේ):
එය, පහත සඳහන් කාර්යය අවම කිරීම දක්වා පැමිණේ:
මාර්ගය වන විට, මෙය ක්රමයක් ලෙස හැඳින්වේ . බොහෝ විට ඉහත සඳහන් සියලු කරුණු නොසලකා හරින අතර මෙම ක්රමය සරලව භාවිතා වේ.
QR වියෝජනය
මෙම ශ්‍රිතයේ අනුක්රමණය ශුන්‍ය වන ලක්ෂ්‍යය සොයා ගැනීමෙන් ඉහත ශ්‍රිතයේ අවම අගය සොයාගත හැක. සහ අනුක්‍රමය පහත පරිදි ලියා ඇත:
අවම කොටු ක්‍රමයේදී භාවිතා වන අවම කිරීමේ ගැටලුව විසඳීම සඳහා matrix ක්‍රමයකි. මේ සම්බන්ධයෙන්, අපි සමීකරණය අනුකෘති ආකාරයෙන් නැවත ලියන්නෙමු:
එබැවින් අපි matrix දිරාපත් කරමු matrices වලට и සහ පරිවර්තන මාලාවක් සිදු කරන්න (QR විසංයෝජන ඇල්ගොරිතම මෙහි සලකා බලනු නොලැබේ, එය පැවරී ඇති කාර්යයට අදාළව එය භාවිතා කිරීම පමණි):
අනුකෘතිය විකලාංග වේ. මෙය අපට කාර්යයෙන් මිදීමට ඉඩ සලසයි :
සහ ඔබ ප්රතිස්ථාපනය කරන්නේ නම් මත , එවිට එය සාර්ථක වනු ඇත . ඒ ගැන සලකා බලමින් ඉහළ ත්‍රිකෝණාකාර න්‍යාසයකි, එය මේ ආකාරයෙන් පෙනේ:
ආදේශන ක්රමය භාවිතයෙන් මෙය විසඳිය හැක. මූලද්රව්යය ලෙස පිහිටා ඇත , පෙර අංගය ලෙස පිහිටා ඇත සහ යනාදි.
QR වියෝජනය භාවිතා කිරීම නිසා ඇතිවන ඇල්ගොරිතමයේ සංකීර්ණත්වය සමාන බව මෙහිදී සඳහන් කිරීම වටී. . එපමනක් නොව, matrix ගුණ කිරීමේ මෙහෙයුම හොඳින් සමාන්තරගත වුවද, මෙම ඇල්ගොරිතමයේ ඵලදායී බෙදාහැරීමේ අනුවාදයක් ලිවීමට නොහැකිය.
Gradient Descent
ශ්‍රිතයක් අවම කිරීම ගැන කතා කරන විට, (ස්ටෝචස්ටික්) අනුක්‍රමණ සම්භවය පිළිබඳ ක්රමය සැමවිටම මතක තබා ගැනීම වටී. මෙය ලක්ෂ්‍යයක ශ්‍රිතයක අනුක්‍රමය පුනරාවර්තන ලෙස ගණනය කර එය අනුක්‍රමණයට ප්‍රතිවිරුද්ධ දිශාවට මාරු කිරීම මත පදනම් වූ සරල හා ඵලදායී අවම කිරීමේ ක්‍රමයකි. එවැනි සෑම පියවරක්ම විසඳුම අවම මට්ටමට සමීප කරයි. අනුක්රමණය තවමත් එලෙසම පෙනේ:
ශ්‍රේණියේ ක්‍රියාකරුගේ රේඛීය ගුණාංග හේතුවෙන් මෙම ක්රමය ද හොඳින් සමාන්තරව බෙදා හැරේ. ඉහත සූත්‍රයේ එකතු ලකුණ යටතේ ස්වාධීන නියමයන් ඇති බව සලකන්න. වෙනත් වචන වලින් කිවහොත්, අපට සියලු දර්ශක සඳහා ස්වාධීනව අනුක්රමණය ගණනය කළ හැකිය පළමු සිට දක්වා , මෙයට සමාන්තරව, සමඟ දර්ශක සඳහා අනුක්රමණය ගණනය කරන්න කිරීමට . එවිට ප්රතිඵලය අනුක්රමණය එකතු කරන්න. එකතු කිරීමේ ප්‍රති result ලය අපි පළමු සිට දර්ශක සඳහා අනුක්රමණය වහාම ගණනය කළහොත් සමාන වේ . මේ අනුව, දත්ත කොටස් කිහිපයක් අතර දත්ත බෙදා හරිනු ලැබුවහොත්, එක් එක් කැබැල්ල මත අනුක්රමණය ස්වාධීනව ගණනය කළ හැකි අතර, අවසාන ප්‍රති result ලය ලබා ගැනීම සඳහා මෙම ගණනය කිරීම් වල ප්‍රති results ල සාරාංශ කළ හැකිය:
ක්රියාත්මක කිරීමේ දෘෂ්ටි කෝණයෙන්, මෙය සුසමාදර්ශයට ගැලපේ . අනුක්‍රමික සම්භවයේ සෑම පියවරකදීම, අනුක්‍රමය ගණනය කිරීම සඳහා එක් එක් දත්ත නෝඩය වෙත කාර්යයක් යවනු ලැබේ, පසුව ගණනය කරන ලද අනුක්‍රමිකයන් එකට එකතු කරනු ලබන අතර, ඒවායේ එකතුවේ ප්රතිඵලය ප්රතිඵලය වැඩි දියුණු කිරීමට භාවිතා කරයි.
ක්‍රියාවට නැංවීමේ පහසුව සහ MapReduce සුසමාදර්ශය තුළ ක්රියාත්මක කිරීමේ හැකියාව තිබියදීත්, ශ්‍රේණිගත සම්භවය ද එහි අවාසි ඇත. විශේෂයෙන්ම, අභිසාරීත්වය සාක්ෂාත් කර ගැනීම සඳහා අවශ්ය පියවර ගණන අනෙකුත් වඩාත් විශේෂිත ක්රමවලට සාපේක්ෂව සැලකිය යුතු ලෙස වැඩි වේ.
LSQR
රේඛීය ප්‍රතිගාමීත්වය ප්රතිස්ථාපනය කිරීමට සහ රේඛීය සමීකරණ පද්ධති විසඳීමට යන දෙකටම ගැලපෙන ගැටළුව විසඳීම සඳහා තවත් ක්රමයක් වේ. එහි ප්රධාන ලක්ෂණය වන්නේ එය matrix ක්රමවල වාසි සහ පුනරාවර්තන ප්රවේශය ඒකාබද්ධ කිරීමයි. මෙම ක්රමය ක්රියාත්මක කිරීම පුස්තකාල දෙකෙහිම සොයාගත හැකිය , සහ . මෙම ක්රමය පිළිබඳ විස්තරයක් මෙහි ලබා නොදෙනු ඇත (එය ලිපියෙන් සොයාගත හැකිය ) ඒ වෙනුවට, බෙදා හරින ලද පරිසරයක ක්රියාත්මක කිරීමට LSQR අනුවර්තනය කිරීමට ප්‍රවේශයක් පෙන්වනු ඇත.
LSQR ක්රමය පදනම් වී ඇත . මෙය පුනරාවර්තන ක්රියා පටිපාටියකි, එක් එක් පුනරාවර්තනය පහත පියවර වලින් සමන්විත වේ:
නමුත් අපි උපකල්පනය කළහොත් matrix තිරස් අතට කොටස් කර ඇත, එවිට එක් එක් පුනරාවර්තනය MapReduce පියවර දෙකක් ලෙස නිරූපණය කළ හැක. මේ ආකාරයෙන්, එක් එක් පුනරාවර්තනය අතරතුර දත්ත හුවමාරුව අවම කළ හැකිය (නොදන්නා ගණනට සමාන දිගක් ඇති දෛශික පමණි):
රේඛීය ප්‍රතිගාමීත්වය ක්රියාත්මක කිරීමේදී භාවිතා කරනුයේ මෙම ප්‍රවේශයයි .
නිගමනය
රේඛීය ප්‍රතිසාධන ප්‍රතිසාධන ඇල්ගොරිතම බොහොමයක් ඇත, නමුත් ඒවා සියල්ලම සියලු තත්වයන් තුළ යෙදිය නොහැක. එබැවින් කුඩා දත්ත කට්ටලවල නිවැරදි විසඳුම සඳහා QR වියෝජනය විශිෂ්ටයි. Gradient descent ක්රියාත්මක කිරීම සරල වන අතර ඔබට ඉක්මනින් ආසන්න විසඳුමක් සොයා ගැනීමට ඉඩ සලසයි. තවද LSQR පෙර ඇල්ගොරිතම දෙකෙහි හොඳම ගුණාංග ඒකාබද්ධ කරයි, එය බෙදා හැරිය හැකි බැවින්, අනුක්‍රමය බැසීමට සාපේක්ෂව වේගයෙන් අභිසාරී වන අතර, QR වියෝජනය මෙන් නොව, ආසන්න විසඳුමක් සෙවීමට ඇල්ගොරිතම ඉක්මනින් නැවැත්වීමට ඉඩ සලසයි.
මූලාශ්රය: www.habr.com