ஆதாரம்:
நேரியல் பின்னடைவு என்பது தரவு பகுப்பாய்வு தொடர்பான பல பகுதிகளுக்கான அடிப்படை வழிமுறைகளில் ஒன்றாகும். இதற்கான காரணம் வெளிப்படையானது. இது மிகவும் எளிமையான மற்றும் புரிந்துகொள்ளக்கூடிய வழிமுறையாகும், இது நூற்றுக்கணக்கான ஆண்டுகளாக இல்லாவிட்டாலும், பல பத்து ஆண்டுகளாக அதன் பரவலான பயன்பாட்டிற்கு பங்களித்துள்ளது. மற்ற மாறிகளின் தொகுப்பில் ஒரு மாறியின் நேரியல் சார்புநிலையை நாம் கருதுகிறோம், பின்னர் இந்த சார்புநிலையை மீட்டெடுக்க முயற்சிக்கிறோம்.
ஆனால் இந்த கட்டுரை நடைமுறை சிக்கல்களைத் தீர்க்க நேரியல் பின்னடைவைப் பயன்படுத்துவது பற்றியது அல்ல. இயந்திர கற்றல் தொகுதியை எழுதும் போது நாம் சந்தித்த அதன் மீட்புக்கான விநியோகிக்கப்பட்ட அல்காரிதம்களை செயல்படுத்துவதற்கான சுவாரஸ்யமான அம்சங்களை இங்கே கருத்தில் கொள்வோம். . ஒரு சிறிய அடிப்படை கணிதம், இயந்திர கற்றல் மற்றும் விநியோகிக்கப்பட்ட கம்ப்யூட்டிங் உங்கள் தரவு ஆயிரக்கணக்கான முனைகளில் விநியோகிக்கப்படும்போதும் நேரியல் பின்னடைவை எவ்வாறு செய்வது என்பதைக் கண்டறிய உதவும்.
நாம் என்ன பேசுகிறோம்?
நேரியல் சார்புநிலையை மீட்டெடுக்கும் பணியை நாங்கள் எதிர்கொள்கிறோம். உள்ளீட்டுத் தரவாக, கூறப்படும் சார்பற்ற மாறிகளின் திசையன்களின் தொகுப்பு வழங்கப்படுகிறது, அவை ஒவ்வொன்றும் சார்பு மாறியின் ஒரு குறிப்பிட்ட மதிப்புடன் தொடர்புடையவை. இந்தத் தரவை இரண்டு மெட்ரிக்குகளின் வடிவத்தில் குறிப்பிடலாம்:
இப்போது, சார்பு கருதப்படுவதால், மேலும், நேரியல், நாங்கள் எங்கள் அனுமானத்தை மெட்ரிக்ஸின் தயாரிப்பு வடிவத்தில் எழுதுவோம் (பதிவை எளிதாக்க, இங்கே மற்றும் கீழே சமன்பாட்டின் இலவச சொல் பின்னால் மறைக்கப்பட்டுள்ளது என்று கருதப்படுகிறது. , மற்றும் மேட்ரிக்ஸின் கடைசி நெடுவரிசை அலகுகளைக் கொண்டுள்ளது):
நேரியல் சமன்பாடுகளின் அமைப்பு போல் தெரிகிறது, இல்லையா? இது தெரிகிறது, ஆனால் பெரும்பாலும் சமன்பாடுகளின் அத்தகைய அமைப்புக்கு தீர்வுகள் இருக்காது. இதற்குக் காரணம் சத்தம், இது கிட்டத்தட்ட எந்த உண்மையான தரவுகளிலும் உள்ளது. மற்றொரு காரணம் நேரியல் சார்பு இல்லாதது, இது அசல் ஒன்றைச் சார்ந்திருக்கும் கூடுதல் மாறிகளை அறிமுகப்படுத்துவதன் மூலம் எதிர்த்துப் போராடலாம். பின்வரும் உதாரணத்தைக் கவனியுங்கள்:
ஆதாரம்:
இது ஒரு மாறியின் உறவைக் காட்டும் நேரியல் பின்னடைவின் எளிய உதாரணம் (அச்சு வழியாக ) மற்றொரு மாறியிலிருந்து (அச்சு வழியாக ) இந்த எடுத்துக்காட்டுடன் தொடர்புடைய நேரியல் சமன்பாடுகளின் அமைப்பு ஒரு தீர்வைப் பெற, அனைத்து புள்ளிகளும் ஒரே நேர்கோட்டில் இருக்க வேண்டும். ஆனால் அது உண்மையல்ல. ஆனால் அவை சத்தம் காரணமாக (அல்லது நேரியல் உறவின் அனுமானம் தவறாக இருந்ததால்) துல்லியமாக ஒரே நேர்கோட்டில் கிடப்பதில்லை. எனவே, உண்மையான தரவுகளிலிருந்து ஒரு நேரியல் உறவை மீட்டெடுக்க, வழக்கமாக மேலும் ஒரு அனுமானத்தை அறிமுகப்படுத்துவது அவசியம்: உள்ளீட்டுத் தரவில் சத்தம் உள்ளது மற்றும் இந்த சத்தம் உள்ளது . மற்ற வகையான சத்தம் விநியோகம் பற்றி நீங்கள் அனுமானங்களைச் செய்யலாம், ஆனால் பெரும்பாலான சந்தர்ப்பங்களில் இது சாதாரண விநியோகமாக கருதப்படுகிறது, இது மேலும் விவாதிக்கப்படும்.
அதிகபட்ச சாத்தியக்கூறு முறை
எனவே, சீரற்ற சாதாரணமாக விநியோகிக்கப்பட்ட சத்தம் இருப்பதாக நாங்கள் கருதினோம். அத்தகைய சூழ்நிலையில் என்ன செய்வது? இந்த வழக்கில் கணிதத்தில் உள்ளது மற்றும் பரவலாகப் பயன்படுத்தப்படுகிறது . சுருக்கமாக, அதன் சாராம்சம் தேர்வில் உள்ளது மற்றும் அதன் அடுத்தடுத்த அதிகபட்சம்.
சாதாரண இரைச்சலுடன் தரவிலிருந்து நேரியல் உறவை மீட்டெடுப்பதற்கு நாங்கள் திரும்புகிறோம். அனுமானிக்கப்படும் நேரியல் உறவு என்பது கணித எதிர்பார்ப்பு என்பதை நினைவில் கொள்ளவும் தற்போதுள்ள இயல்பான விநியோகம். அதே நேரத்தில், நிகழ்தகவு கவனிக்கத்தக்கவைகளின் இருப்புக்கு உட்பட்டு, ஒரு மதிப்பு அல்லது மற்றொரு மதிப்பைப் பெறுகிறது , பின்வருமாறு:
இப்போது அதற்கு பதிலாக மாற்றுவோம் и நமக்கு தேவையான மாறிகள்:
வெக்டரைக் கண்டுபிடிப்பதே எஞ்சியுள்ளது , இந்த நிகழ்தகவு அதிகபட்சம். அத்தகைய செயல்பாட்டை அதிகரிக்க, முதலில் அதன் மடக்கையை எடுத்துக்கொள்வது வசதியானது (செயல்பாட்டின் மடக்கையானது செயல்பாட்டின் அதே புள்ளியில் அதிகபட்சத்தை எட்டும்):
இது, பின்வரும் செயல்பாட்டைக் குறைக்கிறது:
மூலம், இது ஒரு முறை என்று அழைக்கப்படுகிறது . பெரும்பாலும் மேலே உள்ள அனைத்து பரிசீலனைகளும் தவிர்க்கப்பட்டு, இந்த முறை வெறுமனே பயன்படுத்தப்படுகிறது.
QR சிதைவு
இந்தச் செயல்பாட்டின் சாய்வு பூஜ்ஜியமாக இருக்கும் புள்ளியைக் கண்டறிவதன் மூலம் மேற்கண்ட செயல்பாட்டின் குறைந்தபட்சத்தைக் கண்டறியலாம். மற்றும் சாய்வு பின்வருமாறு எழுதப்படும்:
குறைந்தபட்ச சதுரங்கள் முறையில் பயன்படுத்தப்படும் குறைத்தல் சிக்கலைத் தீர்ப்பதற்கான ஒரு அணி முறையாகும். இது சம்பந்தமாக, மேட்ரிக்ஸ் வடிவத்தில் சமன்பாட்டை மீண்டும் எழுதுகிறோம்:
எனவே நாம் அணியை சிதைக்கிறோம் மெட்ரிக்குகளுக்கு и மற்றும் தொடர்ச்சியான மாற்றங்களைச் செய்யவும் (QR சிதைவு அல்காரிதம் இங்கே பரிசீலிக்கப்படாது, கையில் உள்ள பணி தொடர்பாக மட்டுமே அதன் பயன்பாடு):
அணி ஆர்த்தோகனல் ஆகும். இது வேலையிலிருந்து விடுபட அனுமதிக்கிறது :
மற்றும் நீங்கள் மாற்றினால் மீது , பிறகு அது வேலை செய்யும் . என்று கருதி மேல் முக்கோண அணி, இது போல் தெரிகிறது:
மாற்று முறையைப் பயன்படுத்தி இதைத் தீர்க்கலாம். உறுப்பு என அமைந்துள்ளது , முந்தைய உறுப்பு என அமைந்துள்ளது மற்றும் பல.
QR சிதைவின் பயன்பாட்டின் காரணமாக விளைந்த அல்காரிதத்தின் சிக்கலானது சமம் என்பது இங்கே கவனிக்கத்தக்கது. . மேலும், மேட்ரிக்ஸ் பெருக்கல் செயல்பாடு நன்கு இணையாக இருந்தாலும், இந்த வழிமுறையின் பயனுள்ள விநியோகிக்கப்பட்ட பதிப்பை எழுதுவது சாத்தியமில்லை.
சாய்வு வம்சாவளி
ஒரு செயல்பாட்டைக் குறைப்பதைப் பற்றி பேசும்போது, (ஒற்றை) சாய்வு வம்சாவளியின் முறையை எப்போதும் நினைவில் கொள்வது மதிப்பு. இது ஒரு கட்டத்தில் ஒரு செயல்பாட்டின் சாய்வை மீண்டும் மீண்டும் கணக்கிட்டு, சாய்வுக்கு எதிர் திசையில் அதை மாற்றுவதன் அடிப்படையில் எளிமையான மற்றும் பயனுள்ள குறைத்தல் முறையாகும். அத்தகைய ஒவ்வொரு நடவடிக்கையும் குறைந்தபட்ச தீர்வைக் கொண்டுவருகிறது. சாய்வு இன்னும் அதே போல் தெரிகிறது:
சாய்வு ஆபரேட்டரின் நேரியல் பண்புகள் காரணமாக இந்த முறையும் நன்கு இணையாக மற்றும் விநியோகிக்கப்படுகிறது. மேலே உள்ள சூத்திரத்தில், கூட்டுக் குறியீட்டின் கீழ் சுயாதீனமான சொற்கள் உள்ளன என்பதை நினைவில் கொள்க. வேறு வார்த்தைகளில் கூறுவதானால், அனைத்து குறியீடுகளுக்கும் சாய்வை சுயாதீனமாக கணக்கிடலாம் முதலில் இருந்து , இதற்கு இணையாக, குறியீடுகளுக்கான சாய்வைக் கணக்கிடவும் செய்ய . பின்னர் விளைந்த சாய்வுகளைச் சேர்க்கவும். முதல் முதல் வரையிலான குறியீடுகளுக்கான சாய்வை நாம் உடனடியாகக் கணக்கிட்டால், கூட்டலின் முடிவு ஒரே மாதிரியாக இருக்கும் . இவ்வாறு, தரவு பல தரவுத் துண்டுகளுக்கு இடையில் விநியோகிக்கப்பட்டால், சாய்வு ஒவ்வொரு பகுதியிலும் சுயாதீனமாக கணக்கிடப்படலாம், பின்னர் இந்த கணக்கீடுகளின் முடிவுகளை இறுதி முடிவைப் பெற சுருக்கமாகக் கூறலாம்:
செயல்படுத்தல் பார்வையில், இது முன்னுதாரணத்திற்கு பொருந்துகிறது . சாய்வு வம்சாவளியின் ஒவ்வொரு படியிலும், சாய்வைக் கணக்கிட ஒவ்வொரு தரவு முனைக்கும் ஒரு பணி அனுப்பப்படுகிறது, பின்னர் கணக்கிடப்பட்ட சாய்வுகள் ஒன்றாக சேகரிக்கப்பட்டு, அவற்றின் கூட்டுத்தொகை முடிவை மேம்படுத்த பயன்படுத்தப்படுகிறது.
செயல்படுத்தல் எளிமை மற்றும் MapReduce முன்னுதாரணத்தில் செயல்படுத்தும் திறன் இருந்தபோதிலும், சாய்வு வம்சாவளி அதன் குறைபாடுகளையும் கொண்டுள்ளது. குறிப்பாக, மற்ற சிறப்பு முறைகளுடன் ஒப்பிடுகையில், ஒருங்கிணைப்பை அடைய தேவையான படிகளின் எண்ணிக்கை கணிசமாக அதிகமாக உள்ளது.
LSQR
சிக்கலைத் தீர்ப்பதற்கான மற்றொரு முறையாகும், இது நேரியல் பின்னடைவை மீட்டமைப்பதற்கும் நேரியல் சமன்பாடுகளின் அமைப்புகளைத் தீர்ப்பதற்கும் ஏற்றது. அதன் முக்கிய அம்சம் என்னவென்றால், இது மேட்ரிக்ஸ் முறைகளின் நன்மைகள் மற்றும் மீண்டும் செயல்படும் அணுகுமுறையை ஒருங்கிணைக்கிறது. இரண்டு நூலகங்களிலும் இம்முறையின் செயலாக்கங்களைக் காணலாம் , மற்றும் உள்ளே . இந்த முறையின் விளக்கம் இங்கே கொடுக்கப்படாது (அதை கட்டுரையில் காணலாம் ) அதற்கு பதிலாக, விநியோகிக்கப்பட்ட சூழலில் செயல்படுத்துவதற்கு LSQR ஐ மாற்றியமைப்பதற்கான அணுகுமுறை நிரூபிக்கப்படும்.
LSQR முறை அடிப்படையாக கொண்டது . இது ஒரு மறு செய்கை செயல்முறையாகும், ஒவ்வொரு மறு செய்கையும் பின்வரும் படிகளைக் கொண்டுள்ளது:
ஆனால் அணி என்று வைத்துக் கொண்டால் கிடைமட்டமாகப் பிரிக்கப்பட்டது, பின்னர் ஒவ்வொரு மறு செய்கையையும் இரண்டு MapReduce படிகளாகக் குறிப்பிடலாம். இந்த வழியில், ஒவ்வொரு மறு செய்கையின் போதும் தரவு பரிமாற்றங்களைக் குறைக்க முடியும் (தெரியாதவர்களின் எண்ணிக்கைக்கு சமமான நீளம் கொண்ட திசையன்கள் மட்டுமே):
நேரியல் பின்னடைவை செயல்படுத்தும்போது இந்த அணுகுமுறை பயன்படுத்தப்படுகிறது .
முடிவுக்கு
பல நேரியல் பின்னடைவு மீட்பு அல்காரிதம்கள் உள்ளன, ஆனால் அவை அனைத்தையும் எல்லா நிலைகளிலும் பயன்படுத்த முடியாது. எனவே சிறிய தரவுத் தொகுப்புகளில் துல்லியமான தீர்வுக்கு QR சிதைவு சிறந்தது. சாய்வு வம்சாவளியைச் செயல்படுத்த எளிதானது மற்றும் தோராயமான தீர்வை விரைவாகக் கண்டறிய உங்களை அனுமதிக்கிறது. LSQR முந்தைய இரண்டு வழிமுறைகளின் சிறந்த பண்புகளை ஒருங்கிணைக்கிறது, ஏனெனில் இது விநியோகிக்கப்படலாம், சாய்வு வம்சாவளியுடன் ஒப்பிடும்போது வேகமாக ஒன்றிணைகிறது, மேலும் QR சிதைவைப் போலன்றி, தோராயமான தீர்வைக் கண்டறிய அல்காரிதத்தை முன்கூட்டியே நிறுத்த அனுமதிக்கிறது.
ஆதாரம்: www.habr.com