Sequential minimal optimization
સિક્વન્સિયલ મિનિમલ ઓપ્ટિમાઇઝેશન (એસ. એમ. ઓ.) એ સપોર્ટ-વેક્ટર મશીનો (એસ. વી. એમ.) ની તાલીમ દરમિયાન ઊભી થતી ક્વોડ્રેટિક પ્રોગ્રામિંગ (ક્યુ. પી.) સમસ્યાને ઉકેલવા માટેનું એક અલ્ગોરિધમ છે. તેની શોધ 1998માં માઇક્રોસોફ્ટ રિસર્ચ ખાતે જ્હોન પ્લેટ દ્વારા કરવામાં આવી હતી. એસ. એમ. ઓ. નો ઉપયોગ સપોર્ટ વેક્ટર મશીનોની તાલીમ માટે વ્યાપકપણે થાય છે અને તેનો અમલ લોકપ્રિય એલ. આઈ. બી. એસ. વી. એમ. ટૂલ દ્વારા કરવામાં આવે છે. 1998માં એસ. એમ. ઓ. અલ્ગોરિધમના પ્રકાશનથી એસ. વી. એમ. સમુદાયમાં ઘણો ઉત્સાહ પેદા થયો છે, કારણ કે એસ. વી. એમ. તાલીમ માટે અગાઉ ઉપલબ્ધ પદ્ધતિઓ વધુ જટિલ હતી અને તેના માટે ખર્ચાળ તૃતીય-પક્ષ ક્યુ. પી. સોલવર્સની જરૂર હતી. ઓપ્ટિમાઇઝેશન સમસ્યા ડેટાસેટ (x1, y1),., (xn, yn) સાથે દ્વિસંગી વર્ગીકરણ સમસ્યાનો વિચાર કરો, જ્યાં xi એ ઇનપુટ વેક્ટર છે અને તેને અનુરૂપ દ્વિસંગી લેબલ છે. સોફ્ટ-માર્જિન સપોર્ટ વેક્ટર મશીનને ચતુર્ભુજ પ્રોગ્રામિંગ સમસ્યાનું સમાધાન કરીને તાલીમ આપવામાં આવે છે, જે નીચે પ્રમાણે બેવડા સ્વરૂપમાં વ્યક્ત કરવામાં આવે છેઃ આ બાબતને આધીન છેઃ જ્યાં C એ SVM હાયપરપેરામીટર છે અને K (xi, xj) એ કર્નલ ફંક્શન છે, જે બંને વપરાશકર્તા દ્વારા પૂરા પાડવામાં આવે છે; અને ચલો લેગ્રેન્જ મલ્ટિપ્લાયર છે. એલ્ગોરિધમ એસ. એમ. ઓ. એ ઉપર વર્ણવેલ ઓપ્ટિમાઇઝેશન સમસ્યાને ઉકેલવા માટે એક પુનરાવર્તિત અલ્ગોરિધમ છે. એસ. એમ. ઓ. આ સમસ્યાને નાની શક્ય પેટા-સમસ્યાઓની શ્રેણીમાં વિભાજિત કરે છે, જે પછી વિશ્લેષણાત્મક રીતે હલ કરવામાં આવે છે. લેગ્રેન્જ મલ્ટિપ્લાયરને સંડોવતા રેખીય સમાનતાના અવરોધને કારણે, સૌથી નાની સંભવિત સમસ્યામાં આવા બે મલ્ટિપ્લાયરનો સમાવેશ થાય છે. પછી, કોઈપણ બે ગુણક માટે અને, અવરોધો ઘટાડીનેઃ કરવામાં આવે છે અને આ ઘટાડેલી સમસ્યાને વિશ્લેષણાત્મક રીતે ઉકેલી શકાય છેઃ વ્યક્તિએ ઓછામાં ઓછું એક-પરિમાણીય દ્વિઘાત કાર્ય શોધવાની જરૂર છે. તે સમાનતાની મર્યાદામાં બાકીની શરતો પરના સરવાળાનું નકારાત્મક છે, જે દરેક પુનરાવર્તનમાં નિશ્ચિત છે. અલ્ગોરિધમ નીચે પ્રમાણે આગળ વધે છેઃ એક લેગ્રેન્જ ગુણક શોધો જે ઓપ્ટિમાઇઝેશન સમસ્યા માટે કરુશ-કુહ્ન-ટકર (કેકેટી) શરતોનું ઉલ્લંઘન કરે છે. બીજો ગુણક પસંદ કરો અને જોડીને શ્રેષ્ઠ બનાવો. અભિસરણ થાય ત્યાં સુધી 1 અને 2 પગલાંઓનું પુનરાવર્તન કરો. જ્યારે તમામ લેગ્રેન્જ મલ્ટિપ્લાયર કેકેટી શરતોને સંતોષે છે (વપરાશકર્તા-નિર્ધારિત સહિષ્ણુતામાં), ત્યારે સમસ્યાનું સમાધાન થઈ ગયું છે. જો કે આ અલ્ગોરિધમને કન્વર્જ કરવાની ખાતરી આપવામાં આવી છે, હ્યુરિસ્ટિક્સનો ઉપયોગ મલ્ટિપ્લાયરની જોડી પસંદ કરવા માટે થાય છે જેથી કન્વર્જન્સના દરને વેગ મળે. મોટા ડેટા સમૂહો માટે આ મહત્વપૂર્ણ છે કારણ કે અને માટે સંભવિત પસંદગીઓ છે. સંબંધિત કાર્ય મોટી એસ. વી. એમ. શીખવાની સમસ્યાઓને નાના ઓપ્ટિમાઇઝેશન કાર્યોની શ્રેણીમાં વિભાજિત કરવાનો પ્રથમ અભિગમ બર્નહાર્ડ બોસર, ઇસાબેલ ગુયોન, વ્લાદિમીર વાપનિક દ્વારા પ્રસ્તાવિત કરવામાં આવ્યો હતો. તેને "ચંકિંગ અલ્ગોરિધમ" તરીકે ઓળખવામાં આવે છે. અલ્ગોરિધમ ડેટાના રેન્ડમ સબસેટથી શરૂ થાય છે, આ સમસ્યાનું સમાધાન કરે છે અને પુનરાવર્તિત રીતે એવા ઉદાહરણો ઉમેરે છે જે શ્રેષ્ઠતાની શરતોનું ઉલ્લંઘન કરે છે. આ અલ્ગોરિધમનો એક ગેરલાભ એ છે કે એસ. વી. ની સંખ્યા સાથે ક્યુ. પી.-સમસ્યાઓ સ્કેલિંગને હલ કરવી જરૂરી છે. વાસ્તવિક દુનિયાના વિરલ ડેટા સમૂહો પર, એસ. એમ. ઓ. ચન્કિંગ અલ્ગોરિધમ કરતાં 1000 ગણી વધુ ઝડપી હોઈ શકે છે. 1997 માં, ઇ. ઓસુના, આર. ફ્રોન્ડ અને એફ. ગિરોસીએ એક પ્રમેય સાબિત કર્યો જે એસવીએમ માટે ક્યુપી અલ્ગોરિધમ્સનો સંપૂર્ણ નવો સમૂહ સૂચવે છે. આ પ્રમેયના આધારે મોટી ક્યુ. પી. સમસ્યાને નાની ક્યુ. પી. પેટા સમસ્યાઓની શ્રેણીમાં વિભાજિત કરી શકાય છે. ક્યુ. પી. પેટા-સમસ્યાઓનો ક્રમ કે જે હંમેશા કરુશ-કુહ્ન-ટકર (કે. કે. ટી.) શરતોનું ઉલ્લંઘન કરનાર ઓછામાં ઓછો એક વ્યક્તિને ઉમેરે છે તે એકરૂપ થવાની ખાતરી આપે છે. ચન્કિંગ અલ્ગોરિધમ પ્રમેયની શરતોનું પાલન કરે છે, અને તેથી તે એકરૂપ થશે. એસ. એમ. ઓ. અલ્ગોરિધમને ઓસુના અલ્ગોરિધમનો એક વિશેષ કેસ ગણી શકાય, જ્યાં ઓપ્ટિમાઇઝેશનનું કદ બે છે અને બંને લેગ્રેન્જ મલ્ટિપ્લાયરને દરેક તબક્કે નવા મલ્ટિપ્લાયર સાથે બદલવામાં આવે છે જે સારા હ્યુરિસ્ટિક્સ દ્વારા પસંદ કરવામાં આવે છે. એસ. એમ. ઓ. અલ્ગોરિધમ બ્રેગમેન પદ્ધતિઓ અથવા રો-એક્શન પદ્ધતિઓ તરીકે ઓળખાતા ઓપ્ટિમાઇઝેશન અલ્ગોરિધમ્સના પરિવાર સાથે નજીકથી સંબંધિત છે. આ પદ્ધતિઓ રેખીય અવરોધો સાથે બહિર્મુખ પ્રોગ્રામિંગ સમસ્યાઓ હલ કરે છે. તે પુનરાવર્તિત પદ્ધતિઓ છે જ્યાં દરેક પગલું દરેક અવરોધ પર વર્તમાન પ્રાથમિક બિંદુને રજૂ કરે છે. કર્નલ પર્સેપ્ટ્રોન સંદર્ભો ઓપ્ટિમાઇઝેશન અલ્ગોરિધમ્સ અને પદ્ધતિઓ સપોર્ટ વેક્ટર મશીનો પણ જુઓ.