Stability (learning theory)
स्थिरता, जिसे एल्गोरिदमिक स्थिरता के रूप में भी जाना जाता है, कम्प्यूटेशनल लर्निंग थ्योरी में एक धारणा है कि कैसे एक मशीन लर्निंग एल्गोरिदम आउटपुट को इसके इनपुट में छोटी गड़बड़ी के साथ बदला जाता है। एक स्थिर शिक्षण एल्गोरिदम वह है जिसके लिए प्रशिक्षण डेटा को थोड़ा संशोधित करने पर भविष्यवाणी में ज्यादा बदलाव नहीं होता है। उदाहरण के लिए, एक मशीन लर्निंग एल्गोरिदम पर विचार करें जिसे एक प्रशिक्षण सेट के रूप में हस्तलिखित अक्षरों के 1000 उदाहरणों और उनके लेबल ("ए" से "जेड") का उपयोग करके वर्णमाला के हस्तलिखित अक्षरों को पहचानने के लिए प्रशिक्षित किया जा रहा है। इस प्रशिक्षण सेट को संशोधित करने का एक तरीका एक उदाहरण छोड़ना है, ताकि हस्तलिखित पत्रों और उनके लेबल के केवल 999 उदाहरण उपलब्ध हों। एक स्थिर शिक्षण एल्गोरिदम 1000-तत्व और 999-तत्व प्रशिक्षण सेट दोनों के साथ एक समान वर्गीकरण का उत्पादन करेगा। भाषा सीखने से लेकर भौतिकी और इंजीनियरिंग में व्युत्क्रम समस्याओं तक कई प्रकार की सीखने की समस्याओं के लिए स्थिरता का अध्ययन किया जा सकता है, क्योंकि यह सीखी जा रही जानकारी के प्रकार के बजाय सीखने की प्रक्रिया का एक गुण है। स्थिरता के अध्ययन ने 2000 के दशक में कम्प्यूटेशनल लर्निंग थ्योरी में महत्व प्राप्त किया जब इसे सामान्यीकरण के साथ संबंध दिखाया गया। यह दिखाया गया कि सीखने के एल्गोरिदम के बड़े वर्गों के लिए, विशेष रूप से अनुभवजन्य जोखिम न्यूनीकरण एल्गोरिदम, कुछ प्रकार की स्थिरता अच्छे सामान्यीकरण को सुनिश्चित करती है। मशीन लर्निंग सिस्टम को डिजाइन करने में एक केंद्रीय लक्ष्य यह सुनिश्चित करना है कि लर्निंग एल्गोरिदम सामान्यीकृत होगा, या उनमें से एक सीमित संख्या पर प्रशिक्षित होने के बाद नए उदाहरणों पर सटीक प्रदर्शन करेगा। 1990 के दशक में, पर्यवेक्षित शिक्षण एल्गोरिदम के लिए सामान्यीकरण सीमा प्राप्त करने में मील के पत्थर तक पहुँच गए थे। सामान्यीकरण को साबित करने के लिए ऐतिहासिक रूप से उपयोग की जाने वाली तकनीक यह दिखाने के लिए थी कि एक एल्गोरिथ्म सुसंगत था, जिसमें उनके साधनों के लिए अनुभवजन्य मात्राओं के समान अभिसरण गुणों का उपयोग किया गया था। इस तकनीक का उपयोग अनुभवजन्य जोखिम न्यूनीकरण (ई. आर. एम.) एल्गोरिदम के बड़े वर्ग के लिए सामान्यीकरण सीमा प्राप्त करने के लिए किया गया था। एक ई. आर. एम. एल्गोरिथ्म वह है जो एक प्रशिक्षण सेट पर अनुभवजन्य त्रुटि को कम करने के लिए एक परिकल्पना स्थान से एक समाधान का चयन करता है। ई. आर. एम. द्विआधारी वर्गीकरण एल्गोरिदम के लिए व्लादिमीर वापनिक द्वारा सिद्ध एक सामान्य परिणाम यह है कि किसी भी लक्ष्य कार्य और इनपुट वितरण के लिए, वी. सी.-आयाम और प्रशिक्षण उदाहरणों के साथ किसी भी परिकल्पना स्थान के लिए, एल्गोरिदम सुसंगत है और एक प्रशिक्षण त्रुटि उत्पन्न करेगा जो वास्तविक त्रुटि से अधिक से अधिक (प्लस लघुगणक कारक) है। परिणाम को बाद में फंक्शन वर्गों के साथ लगभग-ई. आर. एम. एल्गोरिदम तक बढ़ा दिया गया था जिसमें अद्वितीय मिनिमाइज़र नहीं हैं। वापनिक के काम ने, जिसे वी. सी. सिद्धांत के रूप में जाना जाने लगा, एक सीखने के एल्गोरिदम के सामान्यीकरण और सीखने वाले कार्यों के परिकल्पना स्थान के गुणों के बीच एक संबंध स्थापित किया। हालाँकि, इन परिणामों को असीमित वीसी-आयाम के परिकल्पना रिक्त स्थान वाले एल्गोरिदम पर लागू नहीं किया जा सका। दूसरे शब्दों में कहें तो इन परिणामों को तब लागू नहीं किया जा सका जब सीखी जा रही जानकारी में जटिलता थी जो मापने के लिए बहुत बड़ी थी। कुछ सबसे सरल मशीन लर्निंग एल्गोरिदम-उदाहरण के लिए, प्रतिगमन के लिए-में असीमित वीसी-आयाम के साथ परिकल्पना स्थान हैं। एक अन्य उदाहरण भाषा सीखने के एल्गोरिदम हैं जो मनमाने लंबाई के वाक्यों का उत्पादन कर सकते हैं। स्थिरता विश्लेषण को 2000 के दशक में कम्प्यूटेशनल लर्निंग थ्योरी के लिए विकसित किया गया था और यह सामान्यीकरण सीमा प्राप्त करने के लिए एक वैकल्पिक विधि है। एक एल्गोरिथ्म की स्थिरता परिकल्पना स्थान की प्रत्यक्ष संपत्ति के बजाय सीखने की प्रक्रिया की एक संपत्ति है, और इसका मूल्यांकन उन एल्गोरिदम में किया जा सकता है जिनमें असीम या अनिर्धारित वीसी-आयाम जैसे कि निकटतम पड़ोसी के साथ परिकल्पना स्थान होते हैं। एक स्थिर शिक्षण एल्गोरिथ्म वह है जिसके लिए प्रशिक्षण सेट को थोड़ा संशोधित करने पर सीखा गया कार्य बहुत अधिक नहीं बदलता है, उदाहरण के लिए एक उदाहरण छोड़कर। लीव वन आउट एरर के एक माप का उपयोग क्रॉस वैलिडेशन लीव वन आउट (सीवीलू) एल्गोरिदम में लॉस फंक्शन के संबंध में लर्निंग एल्गोरिदम की स्थिरता का मूल्यांकन करने के लिए किया जाता है। इस प्रकार, स्थिरता विश्लेषण मशीन सीखने के लिए संवेदनशीलता विश्लेषण का अनुप्रयोग है। क्लासिक परिणामों का सारांश 1900 के दशक की शुरुआत में-सीखने के सिद्धांत में स्थिरता को सबसे पहले सीखने के नक्शे की निरंतरता के संदर्भ में वर्णित किया गया था, जिसका पता आंद्रे निकोलायेविच तिखोनोव से लगाया गया था। 1979-देवरॉय और वैगनर ने देखा कि एक एल्गोरिथ्म का लीव-वन-आउट व्यवहार नमूने में छोटे परिवर्तनों के प्रति इसकी संवेदनशीलता से संबंधित है। 1999-केयर्न्स और रॉन ने सीमित वीसी-आयाम और स्थिरता के बीच एक संबंध की खोज की। 2002-एक ऐतिहासिक पेपर में, बौस्केट और एलिसीफ ने एक सीखने के एल्गोरिदम की समान परिकल्पना स्थिरता की धारणा का प्रस्ताव रखा और दिखाया कि यह कम सामान्यीकरण त्रुटि का संकेत देता है। समान परिकल्पना स्थिरता, हालांकि, एक मजबूत स्थिति है जो एल्गोरिदम के बड़े वर्गों पर लागू नहीं होती है, जिसमें केवल दो कार्यों के परिकल्पना स्थान के साथ ईआरएम एल्गोरिदम शामिल हैं। 2002-कुटिन और नियोगी ने स्थिरता के कई कमजोर रूपों के लिए सामान्यीकरण सीमा प्रदान करके बौस्केट और एलिसीफ के परिणामों का विस्तार किया, जिसे उन्होंने लगभग-हर जगह स्थिरता कहा। इसके अलावा, उन्होंने संभवतः लगभग सही (पी. ए. सी.) सेटिंग में ई. आर. एम. एल्गोरिदम में स्थिरता और स्थिरता के बीच संबंध स्थापित करने के लिए एक प्रारंभिक कदम उठाया। 2004-पोगियो एट अल। स्थिरता और ई. आर. एम. स्थिरता के बीच एक सामान्य संबंध साबित हुआ। उन्होंने लीव-वन-आउट-स्टेबिलिटी के एक सांख्यिकीय रूप का प्रस्ताव रखा, जिसे उन्होंने सीवीईईईलू स्थिरता कहा, और दिखाया कि यह ए) सीमित हानि वर्गों में सामान्यीकरण के लिए पर्याप्त है, और बी) वर्ग हानि, निरपेक्ष मूल्य और द्विआधारी वर्गीकरण हानि जैसे कुछ हानि कार्यों के लिए ईआरएम एल्गोरिदम की स्थिरता (और इस प्रकार सामान्यीकरण) के लिए आवश्यक और पर्याप्त है। 2010-शैलेव श्वार्ट्ज और अन्य। परिकल्पना स्थान और हानि वर्ग के बीच जटिल संबंधों के कारण वापनिक के मूल परिणामों के साथ समस्याओं को देखा। वे स्थिरता धारणाओं पर चर्चा करते हैं जो विभिन्न हानि वर्गों और विभिन्न प्रकार के सीखने, पर्यवेक्षित और गैर-पर्यवेक्षित को पकड़ते हैं। 2016-मॉरिट्ज़ हार्ड एट अल। परिकल्पना पर निश्चित धारणा और मॉडल को अद्यतन करने के लिए प्रत्येक उदाहरण का उपयोग करने की संख्या को देखते हुए ढाल वंश की स्थिरता साबित हुई। प्रारंभिक परिभाषाएँ हम सीखने के एल्गोरिदम प्रशिक्षण सेट से संबंधित कई शब्दों को परिभाषित करते हैं, ताकि हम तब कई तरीकों से स्थिरता को परिभाषित कर सकें और क्षेत्र से प्रमेय प्रस्तुत कर सकें। एक मशीन लर्निंग एल्गोरिथ्म, जिसे लर्निंग मैप के रूप में भी जाना जाता है, एक प्रशिक्षण डेटा सेट को मैप करता है, जो कि लेबल किए गए उदाहरणों का एक सेट है, जो प्रशिक्षण उदाहरणों के एक ही स्थान से, कहाँ और कहाँ हैं। फ़ंक्शंस को फ़ंक्शंस के एक परिकल्पना स्थान से चुना जाता है जिसे कहा जाता है। जिस प्रशिक्षण समूह से एक एल्गोरिथ्म सीखता है, उसे आकार के रूप में परिभाषित किया जाता है। इस प्रकार, सीखने के मानचित्र को एक मानचित्रण के रूप में परिभाषित किया गया है, जिसमें एक प्रशिक्षण सेट को एक कार्य पर मानचित्रण किया गया है। यहाँ, हम केवल नियतात्मक एल्गोरिदम पर विचार करते हैं जहाँ के संबंध में सममित है, अर्थात। यह प्रशिक्षण सेट में तत्वों के क्रम पर निर्भर नहीं करता है। इसके अलावा, हम मानते हैं कि सभी कार्य मापने योग्य हैं और सभी समूह गणना योग्य हैं। एक उदाहरण के संबंध में एक परिकल्पना के नुकसान को तब परिभाषित किया जाता है। की अनुभवजन्य त्रुटि है। वास्तविक त्रुटि यह है कि आकार m का एक प्रशिक्षण समुच्चय S दिए जाने पर, हम सभी i = 1., m के लिए, निम्नानुसार संशोधित प्रशिक्षण समुच्चय का निर्माण करेंगेः i-th तत्व को हटाकर स्थिरता की परिभाषा एक एल्गोरिथ्म में हानि फलन V के संबंध में परिकल्पना स्थिरता β होती है यदि निम्नलिखित धारण करता हैः बिंदु-वार परिकल्पना स्थिरता एक एल्गोरिथ्म में हानि फलन V के संबंध में बिंदु-वार परिकल्पना स्थिरता β होती है यदि निम्नलिखित धारण करता हैः त्रुटि स्थिरता एक एल्गोरिथ्म में हानि फलन V के संबंध में त्रुटि स्थिरता β होती है यदि निम्नलिखित धारण करता हैः समान स्थिरता एक एल्गोरिथ्म में हानि फलन V के संबंध में समान स्थिरता β होती है यदि निम्नलिखित धारण करता हैः एक संभाव्यता लीव-वन-आउट क्रॉस-वैलिडेशन (सी. वी. लू.) स्टेबिलिटी एक एल्गोरिथम में लॉस फंक्शन वी के संबंध में सी. वी. लू. स्टेबिलिटी β होती है यदि निम्नलिखित मानती हैः (सी. वी. लू.) स्टेबिलिटी की परिभाषा पहले देखी गई पॉइंटवाइज-हाइपोथिसिस स्टेबिलिटी के बराबर है। अपेक्षित-छोड़-एक-बाहर त्रुटि () स्थिरता एक एल्गोरिथ्म में स्थिरता होती है यदि प्रत्येक एन के लिए एक और ऐसा मौजूद हैः, बौस्केट और एलिसीफ से क्लासिक प्रमेयों के लिए शून्य के साथ और जा रहा है (02): सीमित हानि के साथ सममित शिक्षण एल्गोरिथ्म के लिए, यदि एल्गोरिथ्म में उपरोक्त संभावित परिभाषा के साथ समान स्थिरता है, तो एल्गोरिथ्म सामान्यीकृत होता है। समान स्थिरता एक मजबूत स्थिति है जो सभी एल्गोरिदम द्वारा पूरी नहीं की जाती है, लेकिन आश्चर्यजनक रूप से, नियमितकरण एल्गोरिदम के बड़े और महत्वपूर्ण वर्ग द्वारा पूरी की जाती है। सामान्यीकरण की सीमा लेख में दी गई है। मुखर्जी आदि से। (06): बाउंडेड लॉस के साथ सिमेट्रिक लर्निंग एल्गोरिदम के लिए, यदि एल्गोरिदम में लीव-वन-आउट क्रॉस-वैलिडेशन (सीवीलू) स्टेबिलिटी और एक्सपेक्टेड-लीव-वन-आउट एरर () स्टेबिलिटी दोनों हैं जैसा कि ऊपर परिभाषित किया गया है, तो एल्गोरिदम सामान्यीकृत होता है। सामान्यीकरण के लिए अकेले कोई भी शर्त पर्याप्त नहीं है। हालांकि, दोनों मिलकर सामान्यीकरण सुनिश्चित करते हैं (जबकि विपरीत सच नहीं है)। ई. आर. एम. एल्गोरिदम के लिए विशेष रूप से (स्क्वायर लॉस के लिए कहें), लीव-वन-आउट क्रॉस-वैलिडेशन (सी. वी. लू) स्थिरता स्थिरता और सामान्यीकरण के लिए आवश्यक और पर्याप्त दोनों है। यह सीखने के सिद्धांत की नींव के लिए एक महत्वपूर्ण परिणाम है, क्योंकि यह दर्शाता है कि एक एल्गोरिथ्म के दो पहले से असंबंधित गुण, स्थिरता और स्थिरता, ईआरएम (और कुछ हानि कार्यों) के लिए समकक्ष हैं। सामान्यीकरण की सीमा लेख में दी गई है। एल्गोरिदम जो स्थिर हैं यह एल्गोरिदम की एक सूची है जिसे स्थिर दिखाया गया है, और वह लेख जहां संबंधित सामान्यीकरण सीमाएं प्रदान की गई हैं। एक {0-1} हानि फलन के साथ रैखिक प्रतिगमन के-एन. एन. वर्गीकरण। वेक्टर मशीन (एस. वी. एम.) वर्गीकरण का समर्थन एक बंधी हुई कर्नेल के साथ करें और जहां रेग्युलराइज़र एक रिप्रोड्यूसिंग कर्नेल हिल्बर्ट स्पेस में एक मानक है। एक बड़ी नियमितता निरंतरता अच्छी स्थिरता की ओर ले जाती है। सॉफ्ट मार्जिन एसवीएम वर्गीकरण। नियमित न्यूनतम वर्ग प्रतिगमन। वर्गीकरण के लिए न्यूनतम सापेक्ष एन्ट्रापी एल्गोरिदम। बैगिंग रेगुलराइज़र का एक संस्करण जिसमें प्रतिगामी यंत्रों की संख्या बढ़ती जाती है। बहु-श्रेणी एस. वी. एम. वर्गीकरण। तिखोनोव नियमितकरण के साथ सभी सीखने के एल्गोरिदम समान स्थिरता मानदंडों को संतुष्ट करते हैं और इस प्रकार, सामान्यीकृत हैं। संदर्भ आगे पढ़ने के लिए 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, वीओएल 190, पेज 111-130 शैलेव श्वार्ट्ज, एस., शमीर, ओ., श्रेब्रो, एन., श्रीधरन, के.