Stability (learning theory)
સ્થિરતા, જેને અલ્ગોરિધમિક સ્થિરતા તરીકે પણ ઓળખવામાં આવે છે, તે કોમ્પ્યુટેશનલ લર્નિંગ થિયરીમાં એક કલ્પના છે કે કેવી રીતે મશીન લર્નિંગ અલ્ગોરિધમ આઉટપુટ તેના ઇનપુટ્સમાં નાના વિક્ષેપો સાથે બદલવામાં આવે છે. એક સ્થિર શિક્ષણ અલ્ગોરિધમ એ છે કે જેના માટે જ્યારે તાલીમ ડેટામાં થોડો ફેરફાર કરવામાં આવે ત્યારે આગાહીમાં વધુ ફેરફાર થતો નથી. દાખલા તરીકે, એક મશીન લર્નિંગ અલ્ગોરિધમનો વિચાર કરો જે હસ્તલિખિત અક્ષરોના 1000 ઉદાહરણો અને તેમના લેબલ્સ ("એ" થી "ઝેડ") નો ઉપયોગ કરીને મૂળાક્ષરના હસ્તલિખિત અક્ષરોને ઓળખવા માટે તાલીમ આપવામાં આવી રહી છે. આ તાલીમ સમૂહમાં ફેરફાર કરવાની એક રીત એ છે કે એક ઉદાહરણ છોડી દેવું, જેથી હસ્તલિખિત પત્રો અને તેમના લેબલના માત્ર 999 ઉદાહરણો ઉપલબ્ધ હોય. એક સ્થિર શિક્ષણ અલ્ગોરિધમ 1000-તત્વ અને 999-તત્વ તાલીમ સમૂહો બંને સાથે સમાન વર્ગીકરણ તૈયાર કરશે. ભાષા શીખવાથી માંડીને ભૌતિકશાસ્ત્ર અને ઇજનેરીમાં ઊલટી સમસ્યાઓ સુધીની ઘણી પ્રકારની શીખવાની સમસ્યાઓ માટે સ્થિરતાનો અભ્યાસ કરી શકાય છે, કારણ કે તે શીખવામાં આવતી માહિતીના પ્રકારને બદલે શીખવાની પ્રક્રિયાની મિલકત છે. સ્થિરતાના અભ્યાસને 2000ના દાયકામાં કોમ્પ્યુટેશનલ લર્નિંગ થિયરીમાં મહત્વ મળ્યું હતું જ્યારે તેને સામાન્યીકરણ સાથે જોડાણ હોવાનું દર્શાવવામાં આવ્યું હતું. એવું દર્શાવવામાં આવ્યું હતું કે શીખવાના અલ્ગોરિધમ્સના મોટા વર્ગો માટે, ખાસ કરીને પ્રયોગમૂલક જોખમ ઘટાડવાના અલ્ગોરિધમ્સ, ચોક્કસ પ્રકારની સ્થિરતા સારા સામાન્યીકરણની ખાતરી આપે છે. મશીન લર્નિંગ સિસ્ટમની રચનામાં કેન્દ્રિય ધ્યેય એ ખાતરી આપવાનું છે કે લર્નિંગ અલ્ગોરિધમ તેમાંના મર્યાદિત સંખ્યામાં પ્રશિક્ષિત થયા પછી નવા ઉદાહરણો પર સામાન્યીકૃત અથવા સચોટ પ્રદર્શન કરશે. 1990 ના દાયકામાં, દેખરેખ હેઠળના શિક્ષણ અલ્ગોરિધમ્સ માટે સામાન્યીકરણની સીમાઓ મેળવવામાં સીમાચિહ્નો હાંસલ કરવામાં આવ્યા હતા. સામાન્યીકરણને સાબિત કરવા માટે ઐતિહાસિક રીતે ઉપયોગમાં લેવાતી તકનીક એ બતાવવા માટે હતી કે અલ્ગોરિધમ સુસંગત છે, તેમના માધ્યમોમાં પ્રયોગમૂલક જથ્થાના સમાન અભિસરણ ગુણધર્મોનો ઉપયોગ કરીને. આ તકનીકનો ઉપયોગ પ્રયોગમૂલક જોખમ ઘટાડવાના (ERM) અલ્ગોરિધમ્સના મોટા વર્ગ માટે સામાન્યીકરણની સીમા મેળવવા માટે કરવામાં આવ્યો હતો. ઇ. આર. એમ. અલ્ગોરિધમ એ છે કે જે તાલીમ સમૂહ પર પ્રયોગમૂલક ભૂલને ઘટાડવા માટે પૂર્વધારણાની જગ્યામાંથી ઉકેલ પસંદ કરે છે. વ્લાદિમીર વાપનિક દ્વારા ઇ. આર. એમ. દ્વિસંગી વર્ગીકરણ અલ્ગોરિધમ્સ માટે સાબિત થયેલું એક સામાન્ય પરિણામ એ છે કે કોઈપણ લક્ષ્ય કાર્ય અને ઇનપુટ વિતરણ માટે, વી. સી.-પરિમાણ અને તાલીમ ઉદાહરણો સાથેની કોઈપણ પૂર્વધારણાની જગ્યા, અલ્ગોરિધમ સુસંગત છે અને તાલીમની ભૂલ પેદા કરશે જે સાચી ભૂલમાંથી મહત્તમ (વત્તા લઘુગણક પરિબળો) છે. પરિણામ પછીથી ફંક્શન વર્ગો સાથે લગભગ-ERM અલ્ગોરિધમ્સ સુધી વિસ્તૃત કરવામાં આવ્યું હતું જેમાં અનન્ય મિનિમાઇઝર્સ નથી. વાપનિકનું કાર્ય, જે વી. સી. સિદ્ધાંત તરીકે જાણીતું બન્યું તેનો ઉપયોગ કરીને, શીખવાની અલ્ગોરિધમનો સામાન્યીકરણ અને શીખવામાં આવતા કાર્યોની પૂર્વધારણાની જગ્યાના ગુણધર્મો વચ્ચેનો સંબંધ સ્થાપિત કર્યો. જો કે, આ પરિણામો અમર્યાદિત વીસી-પરિમાણની પૂર્વધારણાની જગ્યાઓ સાથે અલ્ગોરિધમ્સ પર લાગુ કરી શકાયા નથી. બીજી રીતે કહીએ તો, જ્યારે શીખવામાં આવતી માહિતીમાં જટિલતા હતી જે માપવા માટે ખૂબ મોટી હતી ત્યારે આ પરિણામો લાગુ કરી શકાયા ન હતા. કેટલાક સૌથી સરળ મશીન લર્નિંગ અલ્ગોરિધમ્સ-ઉદાહરણ તરીકે, રીગ્રેસન માટે-અમર્યાદિત વીસી-પરિમાણ સાથે પૂર્વધારણાની જગ્યાઓ ધરાવે છે. બીજું ઉદાહરણ ભાષા શીખવાના અલ્ગોરિધમ્સ છે જે મનસ્વી લંબાઈના વાક્યો ઉત્પન્ન કરી શકે છે. સ્થિરતા વિશ્લેષણ 2000ના દાયકામાં કોમ્પ્યુટેશનલ લર્નિંગ થિયરી માટે વિકસાવવામાં આવ્યું હતું અને તે સામાન્યીકરણની સીમાઓ મેળવવા માટેની વૈકલ્પિક પદ્ધતિ છે. અલ્ગોરિધમની સ્થિરતા એ પૂર્વધારણાની જગ્યાના સીધા ગુણધર્મને બદલે શીખવાની પ્રક્રિયાની મિલકત છે, અને તેનું મૂલ્યાંકન એવા અલ્ગોરિધમ્સમાં કરી શકાય છે જેમાં નજીકના પાડોશી જેવા અમર્યાદિત અથવા અવ્યાખ્યાયિત વીસી-પરિમાણ સાથે પૂર્વધારણાની જગ્યાઓ હોય. એક સ્થિર શિક્ષણ અલ્ગોરિધમ એ છે કે જેના માટે જ્યારે તાલીમ સમૂહમાં થોડો ફેરફાર કરવામાં આવે છે ત્યારે શીખ્યા કાર્યમાં વધુ ફેરફાર થતો નથી, ઉદાહરણ તરીકે એક ઉદાહરણ છોડીને. લોસ ફંક્શનના સંદર્ભમાં લર્નિંગ અલ્ગોરિધમની સ્થિરતાનું મૂલ્યાંકન કરવા માટે ક્રોસ વેલિડેશન લીવ વન આઉટ (CVloo) અલ્ગોરિધમમાં લીવ વન આઉટ એરરના માપનો ઉપયોગ થાય છે. જેમ કે, સ્થિરતા વિશ્લેષણ એ મશીન લર્નિંગ માટે સંવેદનશીલતા વિશ્લેષણનો ઉપયોગ છે. ક્લાસિક પરિણામોનો સારાંશ 1900ના દાયકાની શરૂઆતમાં-શિક્ષણ સિદ્ધાંતમાં સ્થિરતાને શિક્ષણ નકશાની સાતત્યતાના સંદર્ભમાં સૌથી પહેલા વર્ણવવામાં આવી હતી, જે એન્ડ્રી નિકોલાયેવિચ તિખોનોવ દ્વારા શોધી કાઢવામાં આવી હતી. 1979-દેવરોય અને વેગનરએ અવલોકન કર્યું કે અલ્ગોરિધમનો લીવ-વન-આઉટ વર્તન નમૂનામાં નાના ફેરફારો પ્રત્યેની તેની સંવેદનશીલતા સાથે સંબંધિત છે. 1999-કેયર્ન્સ અને રોનએ મર્યાદિત વી. સી.-પરિમાણ અને સ્થિરતા વચ્ચેનું જોડાણ શોધ્યું. 2002-એક સીમાચિહ્નરૂપ પેપરમાં, બૌસ્કેટ અને એલિસીફે લર્નિંગ અલ્ગોરિધમની સમાન પૂર્વધારણા સ્થિરતાની કલ્પનાની દરખાસ્ત કરી અને દર્શાવ્યું કે તે ઓછી સામાન્યીકરણ ભૂલ સૂચવે છે. યુનિફોર્મ હાયપોથેસિસ સ્ટેબિલિટી, જોકે, એક મજબૂત સ્થિતિ છે જે એલ્ગોરિધમ્સના મોટા વર્ગોને લાગુ પડતી નથી, જેમાં માત્ર બે કાર્યોની હાયપોથેસિસ સ્પેસ સાથે ERM એલ્ગોરિધમ્સનો સમાવેશ થાય છે. 2002-કુટિન અને નિયોગીએ સ્થિરતાના કેટલાક નબળા સ્વરૂપો માટે સામાન્યીકરણની સીમા પૂરી પાડીને બૌસ્કેટ અને એલિસીફના પરિણામોને વિસ્તૃત કર્યા, જેને તેઓ લગભગ દરેક જગ્યાએ સ્થિરતા કહે છે. વધુમાં, તેઓએ સંભવતઃ લગભગ યોગ્ય (PAC) સેટિંગમાં ERM અલ્ગોરિધમ્સમાં સ્થિરતા અને સુસંગતતા વચ્ચેનો સંબંધ સ્થાપિત કરવા માટે પ્રારંભિક પગલું ભર્યું. 2004-પોગિયો એટ અલ. સ્થિરતા અને ERM સુસંગતતા વચ્ચેનો સામાન્ય સંબંધ સાબિત થયો. તેઓએ લીવ-વન-આઉટ-સ્ટેબિલિટીના આંકડાકીય સ્વરૂપની દરખાસ્ત કરી જેને તેઓ CVEEEloo સ્થિરતા કહે છે, અને દર્શાવ્યું કે તે a) બાઉન્ડેડ લોસ વર્ગોમાં સામાન્યીકરણ માટે પૂરતું છે, અને b) ચોરસ લોસ, સંપૂર્ણ મૂલ્ય અને દ્વિસંગી વર્ગીકરણ લોસ જેવા ચોક્કસ નુકસાન કાર્યો માટે ERM અલ્ગોરિધમ્સની સુસંગતતા (અને આમ સામાન્યીકરણ) માટે જરૂરી અને પૂરતું છે. 2010-શૈલેવ શ્વાર્ટઝ અને અન્ય. પૂર્વધારણા જગ્યા અને નુકસાન વર્ગ વચ્ચેના જટિલ સંબંધોને કારણે વાપનિકના મૂળ પરિણામો સાથે સમસ્યાઓ જોવા મળી. તેઓ સ્થિરતાની કલ્પનાઓની ચર્ચા કરે છે જે વિવિધ નુકસાનના વર્ગો અને વિવિધ પ્રકારના શિક્ષણ, નિરીક્ષણ અને દેખરેખ વગરના છે. 2016-મોરિટ્ઝ હાર્ડ એટ અલ. પૂર્વધારણા પર ચોક્કસ ધારણા આપવામાં આવે છે અને મોડેલને અપડેટ કરવા માટે દરેક ઉદાહરણનો ઉપયોગ કરવામાં આવે છે. પ્રારંભિક વ્યાખ્યાઓ આપણે શીખવાના અલ્ગોરિધમ્સ તાલીમ સમૂહોને લગતા કેટલાક શબ્દોને વ્યાખ્યાયિત કરીએ છીએ, જેથી આપણે પછી સ્થિરતાને બહુવિધ રીતે વ્યાખ્યાયિત કરી શકીએ અને ક્ષેત્રમાંથી પ્રમેયો રજૂ કરી શકીએ. મશીન લર્નિંગ અલ્ગોરિધમ, જેને લર્નિંગ મેપ તરીકે પણ ઓળખવામાં આવે છે, તે તાલીમ ડેટા સેટને મેપ કરે છે, જે લેબલ કરેલા ઉદાહરણોનો સમૂહ છે, જે તાલીમ ઉદાહરણોની સમાન જગ્યામાં ક્યાં, ક્યાં અને ક્યાં છે તે કાર્ય પર છે. વિધેયોને કહેવાતા વિધેયોની પૂર્વધારણા જગ્યામાંથી પસંદ કરવામાં આવે છે. તાલીમ સમૂહ કે જેમાંથી અલ્ગોરિધમ શીખે છે તેને દોરેલા એટલે કે ડી. માં કદ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. અજ્ઞાત વિતરણ ડી. આમ, શીખવાના નકશાને 'થી' ના મેપિંગ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે, જે 'થી' ના કાર્ય પર તાલીમ સમૂહને મેપિંગ કરે છે. અહીં, આપણે ફક્ત નિર્ધારક અલ્ગોરિધમ્સને ધ્યાનમાં લઈએ છીએ જ્યાં તેના સંદર્ભમાં સમપ્રમાણ હોય છે, એટલે કે. તે તાલીમ સમૂહમાં તત્વોના ક્રમ પર આધારિત નથી. વધુમાં, આપણે ધારીએ છીએ કે તમામ કાર્યો માપી શકાય તેવા છે અને તમામ સમૂહો ગણતરીપાત્ર છે. ઉદાહરણના સંદર્ભમાં પૂર્વધારણાની ખોટને પછી આ રીતે વ્યાખ્યાયિત કરવામાં આવે છે. ની પ્રયોગમૂલક ભૂલ છે. ની સાચી ભૂલ આપવામાં આવી છે કદ m નો તાલીમ સમૂહ S આપેલ છે, આપણે બધા i = 1., m માટે, સુધારેલા તાલીમ સમૂહો નીચે પ્રમાણે બનાવીશુંઃ i-th તત્વને દૂર કરીને સ્થિરતાની વ્યાખ્યાઓ એક અલ્ગોરિધમમાં લોસ ફંક્શન V ના સંદર્ભમાં પૂર્વધારણા સ્થિરતા β હોય છે જો નીચે મુજબ હોય તોઃ બિંદુ મુજબ પૂર્વધારણા સ્થિરતા એક અલ્ગોરિધમમાં લોસ ફંક્શન V ના સંદર્ભમાં બિંદુ મુજબ પૂર્વધારણા સ્થિરતા β હોય છે જો નીચે મુજબ હોય તોઃ ભૂલ સ્થિરતા એક અલ્ગોરિધમમાં લોસ ફંક્શન V ના સંદર્ભમાં ભૂલ સ્થિરતા β હોય છે જો નીચે મુજબ હોય તોઃ સમાન સ્થિરતા એક અલ્ગોરિધમમાં લોસ ફંક્શન V ના સંદર્ભમાં સમાન સ્થિરતા β હોય છે જો નીચે મુજબ હોય તોઃ એક સંભાવના લીવ-વન-આઉટ ક્રોસ-વેલિડેશન (CVloo) સ્થિરતા એક અલ્ગોરિધમમાં લોસ ફંક્શન V ના સંદર્ભમાં CVloo સ્થિરતા β હોય છે જો નીચે મુજબ હોય તોઃ (CVloo) સ્થિરતાની વ્યાખ્યા અગાઉ જોવા મળતી પોઇન્ટવાઇઝ-પૂર્વધારણા સ્થિરતાની સમકક્ષ છે. અપેક્ષિત-છોડો-એક-બહાર ભૂલ () સ્થિરતા અલ્ગોરિધમમાં સ્થિરતા હોય છે જો દરેક n માટે a અને એવું હોય કેઃ, સાથે અને શૂન્ય પર જવું ક્લાસિક પ્રમેયો માટે બૌસ્કેટ અને એલિસીફ તરફથી (02): બાઉન્ડેડ લોસ સાથે સિમેટ્રિક લર્નિંગ અલ્ગોરિધમ્સ માટે, જો અલ્ગોરિધમ ઉપરની સંભવિત વ્યાખ્યા સાથે સમાન સ્થિરતા ધરાવે છે, તો અલ્ગોરિધમ સામાન્યીકૃત થાય છે. યુનિફોર્મ સ્ટેબિલિટી એ એક મજબૂત સ્થિતિ છે જે તમામ અલ્ગોરિધમ્સ દ્વારા પૂરી થતી નથી પરંતુ આશ્ચર્યજનક રીતે, રેગ્યુલરાઇઝેશન અલ્ગોરિધમ્સના મોટા અને મહત્વપૂર્ણ વર્ગ દ્વારા પૂરી થાય છે. સામાન્યીકરણની મર્યાદા લેખમાં આપવામાં આવી છે. મુખર્જી વગેરે તરફથી. (06): બાઉન્ડેડ લોસ સાથે સિમેટ્રિક લર્નિંગ અલ્ગોરિધમ્સ માટે, જો અલ્ગોરિધમમાં લીવ-વન-આઉટ ક્રોસ-વેલિડેશન (CVloo) સ્ટેબિલિટી અને એક્સપેક્ટેડ-લીવ-વન-આઉટ એરર () સ્ટેબિલિટી બંને હોય, તો એલ્ગોરિધમ સામાન્યીકૃત થાય છે. સામાન્યીકરણ માટે એકલી શરત પૂરતી નથી. જો કે, બંને મળીને સામાન્યીકરણની ખાતરી કરે છે (જ્યારે વિપરીત સાચું નથી). ERM અલ્ગોરિધમ્સ માટે ખાસ કરીને (સ્ક્વેર લોસ માટે કહો), લીવ-વન-આઉટ ક્રોસ-વેલિડેશન (CVloo) સ્થિરતા સુસંગતતા અને સામાન્યીકરણ માટે જરૂરી અને પૂરતી બંને છે. શિક્ષણ સિદ્ધાંતના પાયા માટે આ એક મહત્વપૂર્ણ પરિણામ છે, કારણ કે તે દર્શાવે છે કે અલ્ગોરિધમનોના બે અગાઉ અસંબંધિત ગુણધર્મો, સ્થિરતા અને સુસંગતતા, ERM (અને ચોક્કસ નુકસાન કાર્યો) માટે સમકક્ષ છે. સામાન્યીકરણની મર્યાદા લેખમાં આપવામાં આવી છે. એલ્ગોરિધમ્સ કે જે સ્થિર છે આ એલ્ગોરિધમ્સની સૂચિ છે જે સ્થિર હોવાનું દર્શાવવામાં આવ્યું છે, અને તે લેખ જ્યાં સંકળાયેલ સામાન્યીકરણની સીમાઓ પ્રદાન કરવામાં આવી છે. {0-1} લોસ ફંક્શન સાથે લીનિયર રીગ્રેસન k-NN ક્લાસિફાયર. બંધાયેલ કર્નલ સાથે વેક્ટર મશીન (SVM) વર્ગીકરણને ટેકો આપો અને જ્યાં રેગ્યુલરાઇઝર એ રિપ્રોડ્યુસિંગ કર્નલ હિલ્બર્ટ સ્પેસમાં ધોરણ છે. મોટા પ્રમાણમાં નિયમિતતા સારી સ્થિરતા તરફ દોરી જાય છે. સોફ્ટ માર્જિન SVM વર્ગીકરણ. નિયમિત લઘુત્તમ ચોરસ રીગ્રેસન. વર્ગીકરણ માટે લઘુતમ સંબંધિત એન્ટ્રોપી અલ્ગોરિધમ. સાથે વધતા જતા રીગ્રેસરની સંખ્યા સાથે નિયમિત બેગની એક આવૃત્તિ. બહુ-વર્ગ SVM વર્ગીકરણ. ટિખોનોવ નિયમિતકરણ સાથેના તમામ શિક્ષણ અલ્ગોરિધમ્સ સમાન સ્થિરતાના માપદંડને સંતોષે છે અને આમ, સામાન્ય કરી શકાય તેવા છે. સંદર્ભો વધુ વાંચન S.Kutin અને P.Niyogi.Almost-everywhere અલ્ગોરિધમિક સ્થિરતા અને સામાન્યીકરણ ભૂલ. પ્રોસી માં. યુ. એ. આઈ. 18,2002 ના એસ. રાખલિન, એસ. મુખર્જી અને ટી. પોગિયો. સ્થિરતા શીખવાના સિદ્ધાંતમાં પરિણમે છે. વિશ્લેષણ અને એપ્લિકેશન્સ, 3 (4): 397-419,2005 વી. એન. વાપનિક. આંકડાકીય શિક્ષણ સિદ્ધાંતની પ્રકૃતિ. સ્પ્રિંગર, 1995 વાપનિક, વી., આંકડાકીય શિક્ષણ સિદ્ધાંત. વિલી, ન્યૂ યોર્ક, 1998 પોગિયો, ટી., રિફ્કિન, આર., મુખર્જી, એસ. અને નિયોગી, પી., "લર્નિંગ થિયરીઃ જનરલ કન્ડીશન્સ ફોર પ્રેડિક્ટિવિટી", નેચર, વોલ્યુમ. 428, 419-422,2004 આન્દ્રે એલિસીફ, થિયોડોરોસ એવગેનિઓ, માસિમિલિયાનો પોન્ટિલ, સ્ટેબિલિટી ઓફ રેન્ડમાઇઝ્ડ લર્નિંગ અલ્ગોરિધમ્સ, જર્નલ ઓફ મશીન લર્નિંગ રિસર્ચ 6,55-79,2010 એલિસીફ, એ. પોન્ટિલ, એમ., લીવ-વન-આઉટ એરર એન્ડ સ્ટેબિલિટી ઓફ લર્નિંગ અલ્ગોરિધમ્સ વિથ એપ્લિકેશન્સ, નાટો સાયન્સ સિરીઝ સબ સિરીઝ III કમ્પ્યુટર એન્ડ સિસ્ટમ્સ સાયન્સ, 2003, VOL 190, પૃષ્ઠો 111-130 શૈલેવ શ્વાર્ટઝ, S., શમીર, O., શ્રેબ્રો, N., શ્રીધરન, K.