Sequential minimal optimization
अनुक्रमिक न्यूनतम अनुकूलन (एस. एम. ओ.) समर्थन-वाहक मशीनों (एस. वी. एम.) के प्रशिक्षण के दौरान उत्पन्न होने वाली द्विघात प्रोग्रामिंग (क्यू. पी.) समस्या को हल करने के लिए एक एल्गोरिथ्म है। इसका आविष्कार 1998 में माइक्रोसॉफ्ट रिसर्च में जॉन प्लाट द्वारा किया गया था। एस. एम. ओ. का व्यापक रूप से प्रशिक्षण समर्थन वेक्टर मशीनों के लिए उपयोग किया जाता है और इसे लोकप्रिय एल. आई. बी. एस. वी. एम. उपकरण द्वारा लागू किया जाता है। 1998 में एस. एम. ओ. एल्गोरिदम के प्रकाशन ने एस. वी. एम. समुदाय में बहुत उत्साह पैदा किया है, क्योंकि एस. वी. एम. प्रशिक्षण के लिए पहले से उपलब्ध तरीके बहुत अधिक जटिल थे और महंगे तृतीय-पक्ष क्यू. पी. समाधानकों की आवश्यकता थी। अनुकूलन समस्या एक डेटासेट (x1, y1),., (xn, yn) के साथ एक द्विआधारी वर्गीकरण समस्या पर विचार करें, जहां xi एक इनपुट वेक्टर है और इसके अनुरूप एक द्विआधारी लेबल है। एक सॉफ्ट-मार्जिन सपोर्ट वेक्टर मशीन को एक द्विघात प्रोग्रामिंग समस्या को हल करके प्रशिक्षित किया जाता है, जिसे दोहरे रूप में निम्नानुसार व्यक्त किया जाता हैः जहां सी एक एसवीएम हाइपरपैरामीटर है और के (xi, xj) कर्नेल फ़ंक्शन है, दोनों उपयोगकर्ता द्वारा आपूर्ति की जाती है; और चर लैग्रेंज गुणक हैं। एल्गोरिदम एस. एम. ओ. ऊपर वर्णित अनुकूलन समस्या को हल करने के लिए एक पुनरावृत्ति एल्गोरिदम है। एस. एम. ओ. इस समस्या को सबसे छोटी संभव उप-समस्याओं की एक श्रृंखला में विभाजित करता है, जिन्हें फिर विश्लेषणात्मक रूप से हल किया जाता है। लैग्रेंज गुणकों को शामिल करने वाली रैखिक समानता बाधा के कारण, सबसे छोटी संभव समस्या में ऐसे दो गुणक शामिल हैं। फिर, किसी भी दो गुणकों के लिए और, बाधाओं को कम कर दिया जाता हैः और इस कम की गई समस्या को विश्लेषणात्मक रूप से हल किया जा सकता हैः किसी को कम से कम एक आयामी द्विघात फलन खोजने की आवश्यकता होती है। समानता बाधा में शेष शब्दों पर योग का ऋणात्मक है, जो प्रत्येक पुनरावृत्ति में तय किया जाता है। एल्गोरिथ्म इस प्रकार आगे बढ़ता हैः एक लैग्रेंज गुणक खोजें जो अनुकूलन समस्या के लिए करुश-कुह्न-टकर (केकेटी) शर्तों का उल्लंघन करता है। दूसरा गुणक चुनें और जोड़ी को अनुकूलित करें। अभिसरण तक चरण 1 और 2 को दोहराएं। जब सभी लैग्रेंज गुणक केकेटी शर्तों (उपयोगकर्ता-परिभाषित सहिष्णुता के भीतर) को पूरा करते हैं, तो समस्या हल हो जाती है। हालाँकि इस एल्गोरिथ्म के अभिसरण की गारंटी है, लेकिन शोध का उपयोग गुणकों की जोड़ी चुनने के लिए किया जाता है ताकि अभिसरण की दर को तेज किया जा सके। यह बड़े डेटा सेटों के लिए महत्वपूर्ण है क्योंकि और के लिए संभावित विकल्प हैं। संबंधित कार्य बड़ी एस. वी. एम. सीखने की समस्याओं को छोटे अनुकूलन कार्यों की एक श्रृंखला में विभाजित करने का पहला दृष्टिकोण बर्नहार्ड बोसर, इसाबेल गुयोन, व्लादिमीर वापनिक द्वारा प्रस्तावित किया गया था। इसे "चन्किंग एल्गोरिदम" के रूप में जाना जाता है। एल्गोरिथ्म डेटा के यादृच्छिक उपसमुच्चय के साथ शुरू होता है, इस समस्या को हल करता है, और पुनरावृत्त रूप से ऐसे उदाहरण जोड़ता है जो इष्टतम स्थितियों का उल्लंघन करते हैं। इस एल्गोरिथ्म का एक नुकसान यह है कि एस. वी. की संख्या के साथ क्यू. पी.-समस्याओं को हल करना आवश्यक है। वास्तविक दुनिया के विरल डेटा सेटों पर, एस. एम. ओ. चन्किंग एल्गोरिदम की तुलना में 1000 गुना से अधिक तेज हो सकता है। 1997 में, ई. ओसुना, आर. फ्रायंड और एफ. गिरॉसी ने एक प्रमेय साबित किया जो एसवीएम के लिए क्यूपी एल्गोरिदम के एक पूरे नए सेट का सुझाव देता है। इस प्रमेय के आधार पर एक बड़ी क्यू. पी. समस्या को छोटी क्यू. पी. उप-समस्याओं की एक श्रृंखला में विभाजित किया जा सकता है। क्यू. पी. उप-समस्याओं का एक क्रम जो हमेशा करुश-कुह्न-टकर (के. के. टी.) शर्तों के कम से कम एक उल्लंघनकर्ता को जोड़ता है, के अभिसरण की गारंटी है। चंक एल्गोरिथ्म प्रमेय की शर्तों का पालन करता है, और इसलिए अभिसरण करेगा। एस. एम. ओ. एल्गोरिदम को ओसुना एल्गोरिदम का एक विशेष मामला माना जा सकता है, जहां अनुकूलन का आकार दो है और दोनों लैग्रेंज गुणकों को हर चरण में नए गुणकों के साथ बदल दिया जाता है जिन्हें अच्छे शोध के माध्यम से चुना जाता है। एस. एम. ओ. एल्गोरिदम अनुकूलन एल्गोरिदम के एक परिवार से निकटता से संबंधित है जिसे ब्रेगमैन विधियाँ या पंक्ति-क्रिया विधियाँ कहा जाता है। ये विधियाँ उत्तल प्रोग्रामिंग समस्याओं को रैखिक बाधाओं के साथ हल करती हैं। वे पुनरावृत्ति विधियाँ हैं जहाँ प्रत्येक चरण प्रत्येक बाधा पर वर्तमान प्राथमिक बिंदु को प्रक्षेपित करता है। कर्नेल परसेप्ट्रॉन संदर्भ अनुकूलन एल्गोरिदम और विधियाँ भी देखें वेक्टर मशीनों का समर्थन करें