स्थिरता (सीखने का सिद्धांत): Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(12 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Short description|Change in a machine learning algorithm's accuracy when the training data is modified}}
{{Short description|Change in a machine learning algorithm's accuracy when the training data is modified}}
स्थिरता, जिसे एल्गोरिथम स्थिरता भी कहा जाता है, [[कम्प्यूटेशनल शिक्षण सिद्धांत|संगणनात्मक शिक्षण सिद्धांत]] में एक अनुमान है, जिसमें बताया जाता है कि मशीन लर्निंग एल्गोरिदम का आउटपुट अपने इनपुट के छोटे से परिवर्तनों के साथ कैसे बदलता है। एक स्थिर लर्निंग एल्गोरिदम वह होता है जिसके द्वारा पूर्वानुमान किए गए परिणाम में कम बदलाव होता है जब प्रशिक्षण डेटा में थोड़े से संशोधन किया जाता है।
'''स्टेबिलिटी''', जिसे एल्गोरिथम स्टेबिलिटी भी कहा जाता है, [[कम्प्यूटेशनल शिक्षण सिद्धांत|संगणनात्मक शिक्षण सिद्धांत]] में एक अनुमान है, जिसमें बताया जाता है कि मशीन लर्निंग एल्गोरिदम का आउटपुट अपने इनपुट के छोटे से परिवर्तनों के साथ कैसे बदलता है। एक स्टेबल लर्निंग एल्गोरिदम वह होता है जिसके द्वारा पूर्वानुमान किए गए परिणाम में कम बदलाव होता है जब प्रशिक्षण डेटा में थोड़े से संशोधन किया जाता है।


उदाहरण के रूप में, एक मशीन लर्निंग एल्गोरिदम को समझने के लिए, हम एक यांत्रिकी वर्णमाला के हस्तलिखित अक्षरों को पहचानने के लिए प्रशिक्षण देने के लिए उपयुक्त हैं, जिसमें 1000 हस्तलिखित अक्षरों के उदाहरण और उनके लेबल ("A" से "Z" तक) होते हैं। यह प्रशिक्षण सेट है। इस प्रशिक्षण सेट को संशोधित करने का एक तरीका एक उदाहरण छोड़ देना है, जिससे हस्तलिखित पत्रों और उनके लेबल के केवल 999 उदाहरण उपलब्ध हों। एक स्थिर शिक्षण एल्गोरिदम 1000-तत्व और 999-तत्व प्रशिक्षण सेट दोनों के साथ एक समान [[सांख्यिकीय वर्गीकरण]] तैयार करेगा।
उदाहरण के रूप में, एक मशीन लर्निंग एल्गोरिदम को समझने के लिए, हम एक यांत्रिकी वर्णमाला के हस्तलिखित अक्षरों को पहचानने के लिए प्रशिक्षण देने के लिए उपयुक्त हैं, जिसमें 1000 हस्तलिखित अक्षरों के उदाहरण और उनके लेबल "A" से "Z" तक होते हैं। यह प्रशिक्षण सेट है। इस प्रशिक्षण सेट को संशोधित करने का विधि एक उदाहरण छोड़ देना है, जिससे हस्तलिखित पत्रों और उनके लेबल के केवल 999 उदाहरण उपलब्ध हों। एक स्टेबल लर्निंग एल्गोरिदम द्वारा उत्पन्न किया गया विश्लेषक दोनों 1000-घटक और 999-घटक प्रशिक्षण सेट के साथ एक समान विश्लेषक उत्पन्न करेगा।


[[प्राकृतिक भाषा प्रसंस्करण]] से लेकर भौतिकी और इंजीनियरिंग में व्युत्क्रम समस्याओं तक, कई प्रकार की सीखने की समस्याओं के लिए स्थिरता का अध्ययन किया जा सकता है, क्योंकि यह सीखी जा रही जानकारी के प्रकार के बजाय सीखने की प्रक्रिया की एक संपत्ति है। 2000 के दशक में कम्प्यूटेशनल लर्निंग सिद्धांत में स्थिरता के अध्ययन को महत्व मिला जब इसे मशीन लर्निंग के साथ संबंध दिखाया गया#सामान्यीकरण. यह दिखाया गया कि सीखने के एल्गोरिदम के बड़े वर्गों के लिए, विशेष रूप से अनुभवजन्य जोखिम न्यूनतमकरण एल्गोरिदम, कुछ प्रकार की स्थिरता अच्छा सामान्यीकरण सुनिश्चित करती है।
[[प्राकृतिक भाषा प्रसंस्करण]] से लेकर भौतिकी और इंजीनियरिंग में व्युत्क्रम समस्याओं तक, कई प्रकार की सीखने की समस्याओं के लिए स्टेबिलिटी का अध्ययन किया जा सकता है, क्योंकि यह सीखी जा रही जानकारी के प्रकार के अतिरिक्त सीखने की प्रक्रिया का एक गुण है। 2000 के दशक में कम्प्यूटेशनल शिक्षण सिद्धांत में स्टेबिलिटी के अध्ययन को महत्व मिला जब इसे सामान्यीकरण के साथ संबंध दिखाया गया कि सीखने के एल्गोरिदम के बड़े वर्गों के लिए, विशेष रूप से अनुभवजन्य जोखिम न्यूनतमकरण एल्गोरिदम, के लिए कुछ प्रकार की स्टेबिलिटी अच्छे सामान्यीकरण को सुनिश्चित करती है।


== इतिहास ==
== इतिहास ==


मशीन लर्निंग को डिज़ाइन करने का एक केंद्रीय लक्ष्य यह गारंटी देना है कि लर्निंग एल्गोरिदम मशीन लर्निंग # सामान्यीकरण करेगा, या उनमें से एक सीमित संख्या में प्रशिक्षित होने के बाद नए उदाहरणों पर सटीक प्रदर्शन करेगा। 1990 के दशक में, पर्यवेक्षित शिक्षण के लिए सामान्यीकरण सीमा प्राप्त करने में मील के पत्थर हासिल किए गए। सामान्यीकरण को सिद्ध करने के लिए ऐतिहासिक रूप से उपयोग की जाने वाली तकनीक यह दिखाने के लिए थी कि एक एल्गोरिदम [[सुसंगत अनुमानक]] था, जो अनुभवजन्य मात्राओं के समान अभिसरण गुणों को उनके साधनों में उपयोग करता था। इस तकनीक का उपयोग अनुभवजन्य जोखिम न्यूनीकरण (ईआरएम) एल्गोरिदम के बड़े वर्ग के लिए सामान्यीकरण सीमा प्राप्त करने के लिए किया गया था। ईआरएम एल्गोरिदम वह है जो एक परिकल्पना स्थान से एक समाधान का चयन करता है <math>H</math> इस तरह से प्रशिक्षण सेट पर अनुभवजन्य त्रुटि को कम किया जा सके <math>S</math>.
मशीन लर्निंग सिस्टम के डिज़ाइन में एक मुख्य लक्ष्य है कि लर्निंग एल्गोरिदम नए उदाहरणों पर भी सही विधि से प्रदर्शन करे, या उसके बाद भी सही पूर्वानुमानित कर सके, जब उसे एक सीमित संख्या के उदाहरणों पर प्रशिक्षित किया जाता है। 1990 के दशक में, पर्यवेक्षित शिक्षण एल्गोरिदम के लिए सामान्यीकरण सीमा प्राप्त करने में मील के पत्थर प्राप्त किए गए। सामान्यीकरण को सिद्ध करने के लिए ऐतिहासिक रूप से उपयोग की जाने वाली तकनीक यह दिखाने के लिए थी कि एक एल्गोरिदम [[सुसंगत अनुमानक]] था, जो अनुभवजन्य मात्राओं के समान अभिसरण गुणों को उनके साधनों में उपयोग करता था। इस तकनीक का उपयोग अनुभवजन्य जोखिम न्यूनीकरण ईआरएम एल्गोरिदम के बड़े वर्ग के लिए सामान्यीकरण सीमा प्राप्त करने के लिए किया गया था। ईआरएम एल्गोरिदम वह है जो एक परिकल्पना समष्टि से एक समाधान <math>H</math> का चयन करता है। इस तरह से प्रशिक्षण सेट <math>S</math> पर अनुभवजन्य त्रुटि को कम किया जा सके।


ईआरएम बाइनरी वर्गीकरण एल्गोरिदम के लिए [[व्लादिमीर वापनिक]] द्वारा सिद्ध किया गया एक सामान्य परिणाम यह है कि किसी भी लक्ष्य फ़ंक्शन और इनपुट वितरण के लिए, किसी भी परिकल्पना स्थान <math>H</math> [[वीसी आयाम]] के साथ|वीसी-आयाम <math>d</math>, और <math>n</math> प्रशिक्षण उदाहरणों में, एल्गोरिथ्म सुसंगत है और अधिकतम एक प्रशिक्षण त्रुटि उत्पन्न करेगा <math>O\left(\sqrt{\frac{d}{n}}\right)</math> (प्लस लॉगरिदमिक कारक) सच्ची त्रुटि से। परिणाम को बाद में फ़ंक्शन वर्गों के साथ लगभग-ईआरएम एल्गोरिदम तक बढ़ा दिया गया, जिनमें अद्वितीय मिनिमाइज़र नहीं हैं।
ईआरएम बाइनरी वर्गीकरण एल्गोरिदम के लिए [[व्लादिमीर वापनिक]] द्वारा सिद्ध किया गया एक सामान्य परिणाम यह है कि किसी भी लक्ष्य फ़ंक्शन और इनपुट वितरण के लिए, किसी भी परिकल्पना समष्टि <math>H</math> [[वीसी आयाम]] के साथ वीसी-आयाम <math>d</math>, और <math>n</math> प्रशिक्षण उदाहरणों में, यदि एक एल्गोरिदम सत्यापनशील है तो वह प्रशिक्षण त्रुटि को सच्ची त्रुटि से अधिकतम  <math>O\left(\sqrt{\frac{d}{n}}\right)</math> उत्पन्न सकता है। परिणाम को बाद में फ़ंक्शन वर्गों के साथ लगभग-ईआरएम एल्गोरिदम तक बढ़ा दिया गया, जिनमें अद्वितीय मिनिमाइज़र नहीं हैं।


वापनिक के काम ने, जिसे [[वीसी सिद्धांत]] के रूप में जाना जाता है, का उपयोग करते हुए एक सीखने के एल्गोरिदम के सामान्यीकरण और परिकल्पना स्थान के गुणों के बीच एक संबंध स्थापित किया। <math>H</math> सीखे जा रहे कार्यों के बारे में। हालाँकि, इन परिणामों को असीमित वीसी-आयाम के परिकल्पना स्थानों वाले एल्गोरिदम पर लागू नहीं किया जा सका। दूसरे शब्दों में कहें तो, इन परिणामों को तब लागू नहीं किया जा सकता था जब सीखी जा रही जानकारी इतनी जटिल थी कि मापने के लिए बहुत बड़ी थी। कुछ सबसे सरल मशीन लर्निंग एल्गोरिदम में - उदाहरण के लिए, प्रतिगमन के लिए - असीमित वीसी-आयाम के साथ परिकल्पना स्थान होते हैं। एक अन्य उदाहरण भाषा सीखने के एल्गोरिदम का है जो मनमानी लंबाई के वाक्य तैयार कर सकता है।
वापनिक के काम में, जिसे जिन्हें वीसी सिद्धांत के रूप में जाना गया, एक सीखने वाले एल्गोरिदम के सामान्यीकरण और सीखने जा रहे फ़ंक्शन के विश्वासयोग्यता समष्टि <math>H</math> के गुणों के बीच एक संबंध स्थापित किया गया। यद्यपि, इन परिणामों को असीमित वीसी-आयाम के परिकल्पना समष्टिों वाले एल्गोरिदम पर लागू नहीं किया जा सका। दूसरे शब्दों मे कहें तो, ये परिणाम उस समय लागू नहीं किए जा सकते थे जब शिक्षित हो रही जानकारी की जटिलता बहुत ज्यादा थी और उसे मापने की संभावना नहीं थी। कुछ सबसे सरल मशीन लर्निंग एल्गोरिदम, जैसे रीज्रेशन के लिए, हिपोथिसिस स्पेस का वीसी आयाम अनिश्चित होता है। दूसरा उदाहरण है भाषा शिक्षण एल्गोरिदम जो असीमित लंबाई के वाक्यों को प्रस्तुत कर सकते हैं।


स्थिरता विश्लेषण 2000 के दशक में कम्प्यूटेशनल शिक्षण सिद्धांत के लिए विकसित किया गया था और यह सामान्यीकरण सीमा प्राप्त करने के लिए एक वैकल्पिक तरीका है। एल्गोरिदम की स्थिरता परिकल्पना स्थान की प्रत्यक्ष संपत्ति के बजाय सीखने की प्रक्रिया की एक संपत्ति है <math>H</math>, और इसका मूल्यांकन उन एल्गोरिदम में किया जा सकता है जिनमें असीमित या अपरिभाषित वीसी-आयाम जैसे कि निकटतम पड़ोसी के साथ परिकल्पना स्थान हैं। एक स्थिर शिक्षण एल्गोरिदम वह है जिसके लिए प्रशिक्षण सेट को थोड़ा संशोधित करने पर सीखा हुआ कार्य बहुत अधिक नहीं बदलता है, उदाहरण के लिए एक उदाहरण को छोड़कर। हानि फ़ंक्शन के संबंध में सीखने के एल्गोरिदम की स्थिरता का मूल्यांकन करने के लिए क्रॉस वैलिडेशन [[एक त्रुटि छोड़ें]]सीवीलू) एल्गोरिदम में लीव वन आउट त्रुटि का एक माप उपयोग किया जाता है। जैसे, स्थिरता विश्लेषण मशीन सीखने के लिए संवेदनशीलता विश्लेषण का अनुप्रयोग है।
स्टेबिलिटी विश्लेषण 2000 के दशक में कम्प्यूटेशनल शिक्षण सिद्धांत के लिए विकसित किया गया था और यह सामान्यीकरण सीमा प्राप्त करने के लिए एक वैकल्पिक विधि है। एक एल्गोरिदम की स्टेबिलिटी शिक्षण प्रक्रिया की एक गुणवत्ता है, जो कि सीधे हिपोथिसिस स्पेस  <math>H</math>, की एक प्रत्यक्ष गुणवत्ता नहीं है, और वीसी-आयाम के साथ असीमित या अनिर्दिष्ट हिपोथिसिस स्पेस के एल्गोरिदमों में मूल्यांकन किया जा सकता है, जैसे जैसे कि नियरेस्ट नेबर। एक स्टेबल लर्निंग एल्गोरिदम वह होता है जिसमें प्रशिक्षण सेट को थोड़े से संशोधित करने पर अधिगत फ़ंक्शन में अत्यधिक परिवर्तित  नहीं होता है, उदाहरण के लिए किसी उदाहरण को छोड़ देने से लीव वन आउट त्रुटि के माप का उपयोग क्रॉस वैलिडेशन लीव वन आउट  एल्गोरिदम में एक एल्गोरिदम की स्टेबिलिटी का मूल्यांकन करने के लिए किया जाता है, जिससे की लॉस फ़ंक्शन के संबंध में इस तरह, स्टेबिलिटी विश्लेषण मशीन लर्निंग में संवेदनशीलता विश्लेषण का एक अनुप्रयोग है।


== क्लासिक परिणामों का सारांश ==
== क्लासिक परिणामों का सारांश ==


* 1900 के आरंभ में - सीखने के सिद्धांत में स्थिरता को सबसे पहले सीखने के मानचित्र की निरंतरता के संदर्भ में वर्णित किया गया था <math>L</math>, फिर [[एंड्री निकोलाइविच तिखोनोव]]{{citation needed|date=May 2021}}.
* शिक्षण सिद्धांत में स्टेबिलिटी की प्रारंभिक विवरण [[एंड्री निकोलाइविच तिखोनोव]] द्वारा शिक्षण मैप <math>L</math>, की सततता के संबंध में की गई थी। यह उनके काम का एक महत्वपूर्ण भाग था जो उन्होंने शिक्षण सिद्धांत के क्षेत्र में किया था।
* 1979 - डेवरोय और वैगनर ने देखा कि एल्गोरिदम का लीव-वन-आउट व्यवहार नमूने में छोटे बदलावों के प्रति इसकी संवेदनशीलता से संबंधित है।<ref name="devroye1979">L. Devroye and Wagner, Distribution-free performance bounds for potential function rules, IEEE Trans. Inf. Theory 25(5) (1979) 601–604.</ref>
* 1979 में डेव्रोय और वाग्नर ने देखा कि एक एल्गोरिदम का लीव-वन-आउट व्यवहार संख्या में छोटे परिवर्तनों के प्रति उसकी संवेदनशीलता से संबंधित होता है।<ref name="devroye1979">L. Devroye and Wagner, Distribution-free performance bounds for potential function rules, IEEE Trans. Inf. Theory 25(5) (1979) 601–604.</ref>
* 1999 - किर्न्स और रॉन ने परिमित वीसी-आयाम और स्थिरता के बीच संबंध की खोज की।<ref>M. Kearns and [[Dana Ron|D. Ron]], Algorithmic stability and sanity-check bounds for leave-one-out cross-validation, Neural Comput. 11(6) (1999) 1427–1453.</ref>
* 1999 - किर्न्स और रॉन ने परिमित वीसी-आयाम और स्टेबिलिटी के बीच संबंध की खोज की।<ref>M. Kearns and [[Dana Ron|D. Ron]], Algorithmic stability and sanity-check bounds for leave-one-out cross-validation, Neural Comput. 11(6) (1999) 1427–1453.</ref>
* 2002 - एक ऐतिहासिक पेपर में, बाउस्केट और एलिसिफ़ ने एक सीखने के एल्गोरिदम की ''समान परिकल्पना स्थिरता'' की धारणा का प्रस्ताव रखा और दिखाया कि यह कम सामान्यीकरण त्रुटि का संकेत देता है। हालाँकि, समान परिकल्पना स्थिरता एक मजबूत स्थिति है जो एल्गोरिदम के बड़े वर्गों पर लागू नहीं होती है, जिसमें केवल दो कार्यों की परिकल्पना स्थान के साथ ईआरएम एल्गोरिदम भी शामिल है।<ref name="bousquet2002">O. Bousquet and A. Elisseeff. Stability and generalization. J. Mach. Learn. Res., 2:499–526, 2002.</ref>
* 2002 - एक ऐतिहासिक पेपर में, बाउस्केट और एलिसिफ़ ने एक सीखने के एल्गोरिदम की समान परिकल्पना स्टेबिलिटी की धारणा का प्रस्ताव रखा और दिखाया कि यह कम सामान्यीकरण त्रुटि का संकेत देता है। यद्यपि, समान परिकल्पना स्टेबिलिटी एक मजबूत स्थिति है जो एल्गोरिदम के बड़े वर्गों पर लागू नहीं होती है, जिसमें केवल दो कार्यों की परिकल्पना समष्टि के साथ ईआरएम एल्गोरिदम भी सम्मिलित है।<ref name="bousquet2002">O. Bousquet and A. Elisseeff. Stability and generalization. J. Mach. Learn. Res., 2:499–526, 2002.</ref>
* 2002 - कुटिन और नियोगी ने स्थिरता के कई कमजोर रूपों के लिए सामान्यीकरण सीमाएं प्रदान करके बाउस्केट और एलिसिफ़ के परिणामों को बढ़ाया, जिसे उन्होंने ''लगभग-हर जगह स्थिरता'' कहा। इसके अलावा, उन्होंने संभवतः अनुमानित रूप से सही (पीएसी) सेटिंग में ईआरएम एल्गोरिदम में स्थिरता और स्थिरता के बीच संबंध स्थापित करने में प्रारंभिक कदम उठाया।<ref>S. Kutin and P. Niyogi, Almost-everywhere algorithmic stability and generalization error, Technical Report TR-2002-03, University of Chicago (2002).</ref>
* 2002 - कुटिन और नियोगी ने स्टेबिलिटी के कई कमजोर रूपों के लिए सामान्यीकरण सीमाएं प्रदान करके बाउस्केट और एलिसिफ़ के परिणामों को बढ़ाया, जिसे उन्होंने लगभग-हर जगह स्टेबिलिटी कहा। इसके अतिरिक्त, उन्होंने संभवतः अनुमानित रूप से सही सेटिंग में ईआरएम एल्गोरिदम में स्टेबिलिटी और स्टेबिलिटी के बीच संबंध स्थापित करने में प्रारंभिक कदम उठाया।<ref>S. Kutin and P. Niyogi, Almost-everywhere algorithmic stability and generalization error, Technical Report TR-2002-03, University of Chicago (2002).</ref>
* 2004 - पोगियो एट अल। स्थिरता और ईआरएम स्थिरता के बीच एक सामान्य संबंध साबित हुआ। उन्होंने लीव-वन-आउट-स्थिरता का एक सांख्यिकीय रूप प्रस्तावित किया, जिसे उन्होंने ''सीवीईईलू स्थिरता'' कहा, और दिखाया कि यह ए) सीमित हानि वर्गों में सामान्यीकरण के लिए पर्याप्त है, और बी) वर्ग हानि, पूर्ण मूल्य और बाइनरी वर्गीकरण हानि जैसे कुछ हानि कार्यों के लिए ईआरएम एल्गोरिदम की स्थिरता (और इस प्रकार सामान्यीकरण) के लिए आवश्यक और पर्याप्त है।<ref>S. Mukherjee, P. Niyogi, T. Poggio, and R. M. Rifkin. Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization. Adv. Comput. Math., 25(1-3):161–193, 2006.</ref>
* 2004 - पोगियो एट अल।स्टेबिलिटी और ईआरएम स्टेबिलिटी के बीच एक सामान्य संबंध स्थापित हुआ। उन्होंने लीव-वन-आउट-स्टेबिलिटी का एक सांख्यिकीय रूप प्रस्तावित किया, जिसे उन्होंने सीवीईईलू स्टेबिलिटी कहा, और दिखाया कि यह a सीमित लॉसवर्गों में सामान्यीकरण के लिए पर्याप्त है, और b वर्ग हानि, पूर्ण मूल्य और बाइनरी वर्गीकरण लॉसजैसे कुछ लॉसकार्यों के लिए ईआरएम एल्गोरिदम की स्टेबिलिटी के लिए पर्याप्त है।<ref>S. Mukherjee, P. Niyogi, T. Poggio, and R. M. Rifkin. Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization. Adv. Comput. Math., 25(1-3):161–193, 2006.</ref>
* 2010 - शैलेव श्वार्ट्ज एट अल। परिकल्पना स्थान और हानि वर्ग के बीच जटिल संबंधों के कारण वाप्निक के मूल परिणामों में समस्याएं देखी गईं। वे स्थिरता की धारणाओं पर चर्चा करते हैं जो विभिन्न हानि वर्गों और पर्यवेक्षित और गैर-पर्यवेक्षित सीखने के विभिन्न प्रकारों को पकड़ती हैं।<ref>Shalev Shwartz, S., Shamir, O., Srebro, N., Sridharan, K.,  Learnability, Stability and Uniform Convergence, Journal of Machine Learning Research, 11(Oct):2635-2670, 2010.</ref>
* 2010 - शैलेव श्वार्ट्ज एट अल ने परिकल्पना समष्टि और लॉसवर्ग के बीच जटिल संबंधों के कारण वाप्निक के मूल परिणामों में समस्याएं देखी गईं। वे स्टेबिलिटी की धारणाओं पर चर्चा करते हैं जो विभिन्न लॉसवर्गों और पर्यवेक्षित और गैर-पर्यवेक्षित सीखने के विभिन्न प्रकारों का समावेश करती हैं।।<ref>Shalev Shwartz, S., Shamir, O., Srebro, N., Sridharan, K.,  Learnability, Stability and Uniform Convergence, Journal of Machine Learning Research, 11(Oct):2635-2670, 2010.</ref>
* 2016 - मोरित्ज़ हार्ड्ट एट अल। परिकल्पना पर निश्चित धारणा और मॉडल को अद्यतन करने के लिए प्रत्येक उदाहरण का उपयोग करने की संख्या को देखते हुए ग्रेडिएंट डिसेंट की सिद्ध स्थिरता।<ref>Moritz Hardt, Benjamin Recht, Yoram Singer, Train faster, generalize better: Stability of stochastic gradient descent, ICML 2016.</ref>
* 2016 - मोरिट्ज हार्ट और सहकर्मियों ने निश्चित धारणाओं पर आधारित हिपोथिसिस और प्रत्येक इंस्टेंस को मॉडल को अपडेट करने के लिए कितनी बार उपयोग किया जाता है, इसे मध्यस्थता का सिद्धांत सिद्ध किया है। वे ग्रैडिएंट डिसेंट की स्थिरता को सिद्ध करने में सफल रहे। <ref>Moritz Hardt, Benjamin Recht, Yoram Singer, Train faster, generalize better: Stability of stochastic gradient descent, ICML 2016.</ref>




== प्रारंभिक परिभाषाएँ ==
== प्रारंभिक परिभाषाएँ ==


हम सीखने के एल्गोरिदम प्रशिक्षण सेट से संबंधित कई शब्दों को परिभाषित करते हैं, ताकि हम स्थिरता को कई तरीकों से परिभाषित कर सकें और क्षेत्र से प्रमेय प्रस्तुत कर सकें।
हम सीखने के एल्गोरिदम प्रशिक्षण सेट से संबंधित कई शब्दों को परिभाषित करते हैं, ताकि हम स्टेबिलिटी को कई तरीकों से परिभाषित कर सकें और क्षेत्र से प्रमेय प्रस्तुत कर सकें।


एक मशीन लर्निंग एल्गोरिदम, जिसे लर्निंग मैप के रूप में भी जाना जाता है <math>L</math>, एक प्रशिक्षण डेटा सेट को मैप करता है, जो लेबल किए गए उदाहरणों का एक सेट है <math>(x,y)</math>, एक फ़ंक्शन पर <math>f</math> से <math>X</math> को <math>Y</math>, कहाँ <math>X</math> और <math>Y</math> प्रशिक्षण उदाहरणों के एक ही स्थान पर हैं। कार्य <math>f</math> कार्यों के एक परिकल्पना स्थान से चुने गए हैं जिन्हें कहा जाता है <math>H</math>.
एक मशीन लर्निंग एल्गोरिदम, जिसे लर्निंग मैप <math>L</math>के रूप में भी जाना जाता है , एक प्रशिक्षण डेटा सेट को मैप करता है, जो एक फ़ंक्शन पर <math>f</math> से <math>X</math> को <math>Y</math> लेबल किए गए उदाहरणों का एक सेट <math>(x,y)</math> है, जहाँ <math>X</math> और <math>Y</math> प्रशिक्षण उदाहरणों के एक ही समष्टि पर हैं। फलन <math>f</math> फलनों के एक परिकल्पना समष्टि से चुने गए हैं जिन्हें <math>H</math> कहा जाता है .


वह प्रशिक्षण सेट जिससे एक एल्गोरिदम सीखता है उसे इस प्रकार परिभाषित किया गया है
एक एल्गोरिदम जिससे सिखाई जाती है, उसके प्रशिक्षण सेट को निर्धारित किया जाता है जिसे निम्नलिखित रूप में प्रस्तुत किया जा सकता है:


<math>S = \{z_1 = (x_1,\ y_1)\ ,..,\ z_m = (x_m,\ y_m)\}</math>
<math>S = {z_1 = (x_1,\ y_1)\ ,..,\ z_m = (x_m,\ y_m)}</math>
और आकार का है <math>m</math> में <math>Z = X \times Y</math>
तैयार आई.आई.डी. एक अज्ञात वितरण से डी.


इस प्रकार, सीखने का नक्शा <math>L</math> से मैपिंग के रूप में परिभाषित किया गया है <math>Z_m</math> में <math>H</math>, एक प्रशिक्षण सेट का मानचित्रण <math>S</math> एक समारोह पर <math>f_S</math> से <math>X</math> को <math>Y</math>. यहां, हम केवल नियतात्मक एल्गोरिदम पर विचार करते हैं <math>L</math> के संबंध में सममित है <math>S</math>, यानी यह प्रशिक्षण सेट में तत्वों के क्रम पर निर्भर नहीं करता है। इसके अलावा, हम मानते हैं कि सभी फ़ंक्शन मापने योग्य हैं और सभी सेट गणनीय हैं।
जहां <math>m</math> विशेष और <math>Z = X \times Y</math> हैं। यह नामांकन एक अज्ञात वितरण D से आपसी स्वतंत्र और एक साथ प्राप्त किए गए हैं।


हानि <math>V</math> एक परिकल्पना का <math>f</math> एक उदाहरण के संबंध में <math>z = (x,y)</math> फिर परिभाषित किया गया है <math>V(f,z) = V(f(x),y)</math>.
इस प्रकार, शिक्षण मानचित्र <math>L</math> को <math>Z_m</math> से <math>H</math> तक एक मैपिंग के रूप में परिभाषित किया जाता है, जो एक प्रशिक्षण सेट <math>S</math> को एक फ़ंक्शन <math>f_S</math> से मानचित्रित करता है, जो <math>X</math> से <math>Y</math> तक है। यहां, हम केवल स्टैटिक एल्गोरिदम को ध्यान में रखते हैं जिसमें <math>L</math> <math>S</math> के संबंध में सममितिक है, अर्थात् यह प्रशिक्षण सेट में तत्वों के क्रम पर निर्भर नहीं करता है। इसके अतिरिक्त, हम मानते हैं कि सभी फ़ंक्शन मापनीय हैं और सभी सेट गणनीय हैं।


की अनुभवजन्य त्रुटि <math>f</math> है <math>I_S[f] = \frac{1}{n}\sum V(f,z_i)</math>.
<math>f</math> परिकल्पना की हानि <math>V</math> एक उदाहरण <math>z = (x,y)</math> के संबंध में पुनः <math>V(f,z) = V(f(x),y)</math> के रूप में परिभाषित किया गया है


की सच्ची त्रुटि <math>f</math> है <math>I[f] = \mathbb{E}_z V(f,z)</math>
<math>f</math> की अनुभवजन्य त्रुटि <math>I_S[f] = \frac{1}{n}\sum V(f,z_i)</math> है।
 
<math>f</math> की वास्तविक त्रुटि <math>I[f] = \mathbb{E}_z V(f,z)</math> है।
आकार m के एक प्रशिक्षण सेट S को देखते हुए, हम सभी i = 1....m के लिए, निम्नानुसार संशोधित प्रशिक्षण सेट बनाएंगे:
आकार m के एक प्रशिक्षण सेट S को देखते हुए, हम सभी i = 1....m के लिए, निम्नानुसार संशोधित प्रशिक्षण सेट बनाएंगे:
* i-वें तत्व को हटाकर
* i-वें तत्व को हटाकर
Line 54: Line 54:




==स्थिरता की परिभाषाएँ==


===परिकल्पना स्थिरता===
 
एक एल्गोरिदम <math>L</math> हानि फ़ंक्शन V के संबंध में परिकल्पना स्थिरता β है यदि निम्नलिखित मान्य है:
 
 
 
 
 
 
 
 
==स्टेबिलिटी की परिभाषाएँ==
 
===परिकल्पना स्टेबिलिटी===
एक एल्गोरिदम <math>L</math> लॉसफ़ंक्शन V के संबंध में परिकल्पना स्टेबिलिटी β है यदि निम्नलिखित मान्य है:


<math>\forall i\in \{1,...,m\}, \mathbb{E}_{S,z} [|V(f_S,z)-V(f_{S^{|i}},z)|]\leq\beta.</math>
<math>\forall i\in \{1,...,m\}, \mathbb{E}_{S,z} [|V(f_S,z)-V(f_{S^{|i}},z)|]\leq\beta.</math>




===बिंदुवार परिकल्पना स्थिरता===
===बिंदुवार परिकल्पना स्टेबिलिटी===
एक एल्गोरिदम <math>L</math> हानि फ़ंक्शन V के संबंध में बिंदु-वार परिकल्पना स्थिरता β है यदि निम्नलिखित मान्य है:
एक एल्गोरिदम <math>L</math> का लॉसफ़ंक्शन V के संबंध में बिंदु-वार परिकल्पना स्टेबिलिटी β है यदि निम्नलिखित मान्य है:


<math>\forall i\in\ \{1,...,m\}, \mathbb{E}_{S} [|V(f_S,z_i)-V(f_{S^{|i}},z_i)|]\leq\beta.</math>
<math>\forall i\in\ \{1,...,m\}, \mathbb{E}_{S} [|V(f_S,z_i)-V(f_{S^{|i}},z_i)|]\leq\beta.</math>




===त्रुटि स्थिरता===
===त्रुटि स्टेबिलिटी===
एक एल्गोरिदम <math>L</math> हानि फ़ंक्शन V के संबंध में त्रुटि स्थिरता β है यदि निम्नलिखित मान्य है:
एक एल्गोरिदम <math>L</math> का लॉसफ़ंक्शन V के संबंध में त्रुटि स्टेबिलिटी β है यदि निम्नलिखित मान्य है:


<math>\forall S\in Z^m, \forall i\in\{1,...,m\}, |\mathbb{E}_z[V(f_S,z)]-\mathbb{E}_z[V(f_{S^{|i}},z)]|\leq\beta</math>
<math>\forall S\in Z^m, \forall i\in\{1,...,m\}, |\mathbb{E}_z[V(f_S,z)]-\mathbb{E}_z[V(f_{S^{|i}},z)]|\leq\beta</math>




===समान स्थिरता===
===समरूप स्टेबिलिटी===
एक एल्गोरिदम <math>L</math> हानि फ़ंक्शन V के संबंध में एकसमान स्थिरता β है यदि निम्नलिखित मान्य है:
एक एल्गोरिदम <math>L</math> का लॉसफ़ंक्शन V के संबंध में समरूप स्टेबिलिटी β है यदि निम्नलिखित मान्य है:


<math>\forall S\in Z^m, \forall i\in\{1,...,m\}, \sup_{z\in Z}|V(f_S,z)-V(f_{S^{|i}},z)|\leq\beta</math>
<math>\forall S\in Z^m, \forall i\in\{1,...,m\}, \sup_{z\in Z}|V(f_S,z)-V(f_{S^{|i}},z)|\leq\beta</math>
एक समान स्थिरता β का एक संभाव्य संस्करण है:
 
एक समान स्टेबिलिटी β का एक संभाव्य संस्करण है:


<math>\forall S\in Z^m, \forall i\in\{1,...,m\}, \mathbb{P}_S\{\sup_{z\in Z}|V(f_S,z)-V(f_{S^{|i}},z)|\leq\beta\}\geq1-\delta</math>
<math>\forall S\in Z^m, \forall i\in\{1,...,m\}, \mathbb{P}_S\{\sup_{z\in Z}|V(f_S,z)-V(f_{S^{|i}},z)|\leq\beta\}\geq1-\delta</math>
एक एल्गोरिदम को स्थिर कहा जाता है, जब का मान <math>\beta</math> के रूप में घटता है <math>O(\frac{1}{m})</math>.


===लीव-वन-आउट क्रॉस-वैलिडेशन (सीवीलू) स्थिरता===
एक एल्गोरिदम को स्टेबल कहा जाता है, जब <math>\beta</math> का मान  <math>O(\frac{1}{m})</math> के रूप में घटता है।
एक एल्गोरिदम <math>L</math> हानि फ़ंक्शन V के संबंध में CVloo स्थिरता β है यदि निम्नलिखित मान्य है:
 
===लीव-वन-आउट क्रॉस-वैलिडेशन (सीवीलू) स्टेबिलिटी===
एक एल्गोरिदम <math>L</math> के लॉसफ़ंक्शन V के संबंध में सीवीलू स्टेबिलिटी β है यदि निम्नलिखित मान्य है:


<math>\forall i\in\{1,...,m\}, \mathbb{P}_S\{ |V(f_S,z_i) - V(f_{S^{|i}},z_i)|\leq\beta_{CV}\}\geq1 - \delta_{CV}</math>
<math>\forall i\in\{1,...,m\}, \mathbb{P}_S\{ |V(f_S,z_i) - V(f_{S^{|i}},z_i)|\leq\beta_{CV}\}\geq1 - \delta_{CV}</math>
(सीवीलू) स्थिरता की परिभाषा पहले देखी गई बिंदुवार-परिकल्पना स्थिरता के बराबर है।


===अपेक्षित-छोड़ें-एक-बाहर त्रुटि (<math>Eloo_{err}</math>) स्थिरता===
(सीवीलू) स्टेबिलिटी की परिभाषा पहले देखी गई बिंदुवार-परिकल्पना स्टेबिलिटी के समान है।
एक एल्गोरिदम <math>L</math> है <math>Eloo_{err}</math> स्थिरता यदि प्रत्येक n के लिए a मौजूद है <math>\beta_{EL}^m</math> और <math>\delta_{EL}^m</math> ऐसा है कि:
 
===अपेक्षित-लीव-वन-आउट त्रुटि (<math>Eloo_{err}</math>) स्टेबिलिटी===
एक एल्गोरिदम <math>L</math> में <math>Eloo_{err}</math> स्टेबिलिटी है  यदि <math>\beta_{EL}^m</math> और A <math>\delta_{EL}^m</math> में  प्रत्येक n के लिए a उपलब्ध है:
 
<math>\forall i\in\{1,...,m\}, \mathbb{P}_S\{|I[f_S]-\frac{1}{m}\sum_{i=1}^m V(f_{S^{|i}},z_i)|\leq\beta_{EL}^m\}\geq1-\delta_{EL}^m</math>, के लिए  <math>\beta_{EL}^m</math> और <math>\delta_{EL}^m</math>, शून्य पर अग्रसित है <math>m,\rightarrow\infty</math>।


<math>\forall i\in\{1,...,m\}, \mathbb{P}_S\{|I[f_S]-\frac{1}{m}\sum_{i=1}^m V(f_{S^{|i}},z_i)|\leq\beta_{EL}^m\}\geq1-\delta_{EL}^m</math>, साथ <math>\beta_{EL}^m</math> और <math>\delta_{EL}^m</math> के लिए शून्य पर जा रहा हूँ <math>m,\rightarrow\infty</math>




== क्लासिक प्रमेय ==
== पारम्परिक  प्रमेय ==


बाउस्केट और एलिसिफ़ (02) से:
'''बाउस्केट और एलिसिफ़ (02) से:'''


सीमित हानि वाले सममित शिक्षण एल्गोरिदम के लिए, यदि एल्गोरिदम में उपरोक्त संभाव्य परिभाषा के साथ समान स्थिरता है, तो एल्गोरिदम सामान्यीकृत होता है।
सममित लर्निंग एल्गोरिदम जिनमें सीमित लॉस होता है, यदि एल्गोरिदम के पास पहले दिए गए सामान्यीकरण के साथ उचित संभावनात्मक परिभाषा है, तो वे एल्गोरिदम सामान्यीकरण करते हैं।


समान स्थिरता एक मजबूत स्थिति है जो सभी एल्गोरिदम द्वारा पूरी नहीं की जाती है, लेकिन आश्चर्यजनक रूप से, नियमितीकरण एल्गोरिदम के बड़े और महत्वपूर्ण वर्ग द्वारा पूरी की जाती है।
समान स्टेबिलिटी एक मजबूत स्थिति है जो सभी एल्गोरिदम द्वारा पूरी नहीं की जाती है, लेकिन आश्चर्यजनक रूप से, नियमितीकरण एल्गोरिदम के बड़े और महत्वपूर्ण वर्ग द्वारा पूरी की जाती है। सामान्यीकरण की सीमा लेख में दी गई है।
सामान्यीकरण की सीमा लेख में दी गई है।


मुखर्जी एट अल से. (06):
'''मुखर्जी एट अल से. (06):'''


*सीमाबद्ध हानि वाले सममित शिक्षण एल्गोरिदम के लिए, यदि एल्गोरिदम में ''दोनों'' लीव-वन-आउट क्रॉस-वैलिडेशन (सीवीलू) स्थिरता और अपेक्षित-लीव-वन-आउट त्रुटि है (<math>Eloo_{err}</math>) स्थिरता जैसा कि ऊपर परिभाषित किया गया है, फिर एल्गोरिदम सामान्यीकृत होता है।
*सममित लर्निंग एल्गोरिदम्स जिनमें सीमित लॉस होता है, यदि एल्गोरिदम के पास ऊपर दिए गए दोनों समष्टिीय आंतरिक समीकरण और अपेक्षित आंतरिक त्रुटि <math>Eloo_{err}</math>) स्टेबिलिटी है, तो वे एल्गोरिदम सामान्यीकरण करते हैं।,
*सामान्यीकरण के लिए कोई भी स्थिति अकेली पर्याप्त नहीं है। हालाँकि, दोनों मिलकर सामान्यीकरण सुनिश्चित करते हैं (जबकि इसका विपरीत सत्य नहीं है)।
*केवल एक स्थिरता शर्त से सामान्यीकरण होना पर्याप्त नहीं है, परंतु दोनों स्थिरता शर्तों का साथ मिलकर सामान्यीकरण सुनिश्चित करता है
*ईआरएम एल्गोरिदम के लिए विशेष रूप से (वर्ग हानि के लिए कहें), लीव-वन-आउट क्रॉस-वैलिडेशन (सीवीलू) स्थिरता और सामान्यीकरण के लिए स्थिरता आवश्यक और पर्याप्त दोनों है।
*विशेष रूप से ईआरएम एल्गोरिदम के लिए, लीव-वन-आउट क्रॉस-वैलिडेशन स्टेबिलिटी और सामान्यीकरण के लिए स्टेबिलिटी आवश्यक और पर्याप्त दोनों है।


यह सीखने के सिद्धांत की नींव के लिए एक महत्वपूर्ण परिणाम है, क्योंकि यह दर्शाता है कि एल्गोरिदम के दो पहले से असंबंधित गुण, स्थिरता और स्थिरता, ईआरएम (और कुछ हानि कार्यों) के लिए समतुल्य हैं।
यह सीखने के सिद्धांत की नींव के लिए एक महत्वपूर्ण परिणाम है, क्योंकि यह दर्शाता है कि एल्गोरिदम के दो पहले से असंबंधित गुण, एल्गोरिदम और स्टेबिलिटी, ईआरएम के लिए समतुल्य हैं। सामान्यीकरण की सीमा लेख में दी गई है
सामान्यीकरण की सीमा लेख में दी गई है।


==एल्गोरिदम जो स्थिर हैं==
==स्टेबल एल्गोरिदम==
यह उन एल्गोरिदम की एक सूची है जिन्हें स्थिर दिखाया गया है, और वह लेख जहां संबंधित सामान्यीकरण सीमाएँ प्रदान की गई हैं।
यह उन एल्गोरिदम की एक सूची है जिन्हें स्टेबल दिखाया गया है, और वह लेख जहां संबंधित सामान्यीकरण सीमाएँ प्रदान की गई हैं।


* [[रेखीय प्रतिगमन]]<ref>Elisseeff, A. A study about algorithmic stability and
* [[रेखीय प्रतिगमन]]<ref>Elisseeff, A. A study about algorithmic stability and
Line 120: Line 132:
  report. (2000)
  report. (2000)
</ref>
</ref>
*के-एनएन क्लासिफायरियर {0-1} हानि फ़ंक्शन के साथ।<ref name="devroye1979" />*बाउंडेड कर्नेल के [[समर्थन वेक्टर यंत्र]] (एसवीएम) वर्गीकरण का समर्थन करें और जहां रिप्रोड्यूसिंग कर्नेल हिल्बर्ट स्पेस में रेग्युलराइज़र एक मानक है। एक बड़ा नियमितीकरण स्थिरांक <math>C</math> अच्छी स्थिरता की ओर ले जाता है.<ref name="bousquet2002" />*सॉफ्ट मार्जिन एसवीएम वर्गीकरण।<ref name="bousquet2002"/>*[[नियमितीकरण (मशीन लर्निंग)]] न्यूनतम वर्ग प्रतिगमन।<ref name="bousquet2002" />*वर्गीकरण के लिए न्यूनतम सापेक्ष एन्ट्रापी एल्गोरिथ्म।<ref name="bousquet2002" />*संख्या के साथ नियमितीकरणकर्ताओं को एकत्रित करने वाले बूटस्ट्रैप का एक संस्करण <math>k</math> प्रतिगामी की संख्या बढ़ रही है <math>n</math>.<ref name="rifkin2002">Rifkin, R. Everything Old is New Again: A fresh
*{0-1} लॉसफ़ंक्शन के साथ के -एनएन क्लासिफायरियर।<ref name="devroye1979" />
*बाउंडेड कर्नेल के [[समर्थन वेक्टर यंत्र]] एसवीएम वर्गीकरण का समर्थन करें और जहां रिप्रोड्यूसिंग कर्नेल हिल्बर्ट स्पेस में रेग्युलराइज़र एक मानक है। एक बड़ा नियमितीकरण स्टेबलांक <math>C</math> अच्छी स्टेबिलिटी की ओर ले जाता है.<ref name="bousquet2002" />
*सॉफ्ट मार्जिन एसवीएम वर्गीकरण।<ref name="bousquet2002" />
*[[नियमितीकरण (मशीन लर्निंग)|नियमितीकरण]] न्यूनतम वर्ग प्रतिगमन।<ref name="bousquet2002" />
*वर्गीकरण के लिए न्यूनतम सापेक्ष एन्ट्रापी एल्गोरिथ्म।<ref name="bousquet2002" />
*बैगिंग रेगुलराइज़र्स का एक संस्करण है जिसमें रिग्रेसर्स की संख्या <math>k</math> नियंत्रित है और <math>n</math> के साथ बढ़ती है।.<ref name="rifkin2002">Rifkin, R. Everything Old is New Again: A fresh
  look at historical approaches in machine learning. Ph.D. Thesis, MIT, 2002</ref>
  look at historical approaches in machine learning. Ph.D. Thesis, MIT, 2002</ref>
*मल्टी-क्लास एसवीएम वर्गीकरण।<ref name="rifkin2002" />*तिखोनोव नियमितीकरण के साथ सभी शिक्षण एल्गोरिदम समान स्थिरता मानदंडों को पूरा करते हैं और इस प्रकार, सामान्यीकरण योग्य हैं।<ref>Rosasco, L. and Poggio, T. [http://www.mit.edu/~9.520/spring09/Classes/class10_stability.pdf Stability of Tikhonov Regularization], 2009</ref>
*मल्टी-क्लास एसवीएम वर्गीकरण।<ref name="rifkin2002" />
*सभी लर्निंग एल्गोरिदम जो टिखोनोव रेगुलराइज़ेशन के साथ हैं, वे समान स्टेबिलिटी मानदंड को पूरा करते हैं और इसलिए वे सार्वभौमिक होते हैं।<ref>Rosasco, L. and Poggio, T. [http://www.mit.edu/~9.520/spring09/Classes/class10_stability.pdf Stability of Tikhonov Regularization], 2009</ref>




Line 140: Line 158:
*Shalev Shwartz, S., Shamir, O., Srebro, N., Sridharan, K.,  Learnability, Stability and Uniform Convergence, Journal of Machine Learning Research, 11(Oct):2635-2670, 2010
*Shalev Shwartz, S., Shamir, O., Srebro, N., Sridharan, K.,  Learnability, Stability and Uniform Convergence, Journal of Machine Learning Research, 11(Oct):2635-2670, 2010
{{Refend}}
{{Refend}}
[[Category: यंत्र अधिगम]] [[Category: सीखना]]


[[Category: Machine Translated Page]]
[[Category:Created On 26/07/2023]]
[[Category:Created On 26/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Template documentation pages|Short description/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:यंत्र अधिगम]]
[[Category:सीखना]]

Latest revision as of 14:08, 14 August 2023

स्टेबिलिटी, जिसे एल्गोरिथम स्टेबिलिटी भी कहा जाता है, संगणनात्मक शिक्षण सिद्धांत में एक अनुमान है, जिसमें बताया जाता है कि मशीन लर्निंग एल्गोरिदम का आउटपुट अपने इनपुट के छोटे से परिवर्तनों के साथ कैसे बदलता है। एक स्टेबल लर्निंग एल्गोरिदम वह होता है जिसके द्वारा पूर्वानुमान किए गए परिणाम में कम बदलाव होता है जब प्रशिक्षण डेटा में थोड़े से संशोधन किया जाता है।

उदाहरण के रूप में, एक मशीन लर्निंग एल्गोरिदम को समझने के लिए, हम एक यांत्रिकी वर्णमाला के हस्तलिखित अक्षरों को पहचानने के लिए प्रशिक्षण देने के लिए उपयुक्त हैं, जिसमें 1000 हस्तलिखित अक्षरों के उदाहरण और उनके लेबल "A" से "Z" तक होते हैं। यह प्रशिक्षण सेट है। इस प्रशिक्षण सेट को संशोधित करने का विधि एक उदाहरण छोड़ देना है, जिससे हस्तलिखित पत्रों और उनके लेबल के केवल 999 उदाहरण उपलब्ध हों। एक स्टेबल लर्निंग एल्गोरिदम द्वारा उत्पन्न किया गया विश्लेषक दोनों 1000-घटक और 999-घटक प्रशिक्षण सेट के साथ एक समान विश्लेषक उत्पन्न करेगा।

प्राकृतिक भाषा प्रसंस्करण से लेकर भौतिकी और इंजीनियरिंग में व्युत्क्रम समस्याओं तक, कई प्रकार की सीखने की समस्याओं के लिए स्टेबिलिटी का अध्ययन किया जा सकता है, क्योंकि यह सीखी जा रही जानकारी के प्रकार के अतिरिक्त सीखने की प्रक्रिया का एक गुण है। 2000 के दशक में कम्प्यूटेशनल शिक्षण सिद्धांत में स्टेबिलिटी के अध्ययन को महत्व मिला जब इसे सामान्यीकरण के साथ संबंध दिखाया गया कि सीखने के एल्गोरिदम के बड़े वर्गों के लिए, विशेष रूप से अनुभवजन्य जोखिम न्यूनतमकरण एल्गोरिदम, के लिए कुछ प्रकार की स्टेबिलिटी अच्छे सामान्यीकरण को सुनिश्चित करती है।

इतिहास

मशीन लर्निंग सिस्टम के डिज़ाइन में एक मुख्य लक्ष्य है कि लर्निंग एल्गोरिदम नए उदाहरणों पर भी सही विधि से प्रदर्शन करे, या उसके बाद भी सही पूर्वानुमानित कर सके, जब उसे एक सीमित संख्या के उदाहरणों पर प्रशिक्षित किया जाता है। 1990 के दशक में, पर्यवेक्षित शिक्षण एल्गोरिदम के लिए सामान्यीकरण सीमा प्राप्त करने में मील के पत्थर प्राप्त किए गए। सामान्यीकरण को सिद्ध करने के लिए ऐतिहासिक रूप से उपयोग की जाने वाली तकनीक यह दिखाने के लिए थी कि एक एल्गोरिदम सुसंगत अनुमानक था, जो अनुभवजन्य मात्राओं के समान अभिसरण गुणों को उनके साधनों में उपयोग करता था। इस तकनीक का उपयोग अनुभवजन्य जोखिम न्यूनीकरण ईआरएम एल्गोरिदम के बड़े वर्ग के लिए सामान्यीकरण सीमा प्राप्त करने के लिए किया गया था। ईआरएम एल्गोरिदम वह है जो एक परिकल्पना समष्टि से एक समाधान का चयन करता है। इस तरह से प्रशिक्षण सेट पर अनुभवजन्य त्रुटि को कम किया जा सके।

ईआरएम बाइनरी वर्गीकरण एल्गोरिदम के लिए व्लादिमीर वापनिक द्वारा सिद्ध किया गया एक सामान्य परिणाम यह है कि किसी भी लक्ष्य फ़ंक्शन और इनपुट वितरण के लिए, किसी भी परिकल्पना समष्टि वीसी आयाम के साथ वीसी-आयाम , और प्रशिक्षण उदाहरणों में, यदि एक एल्गोरिदम सत्यापनशील है तो वह प्रशिक्षण त्रुटि को सच्ची त्रुटि से अधिकतम उत्पन्न सकता है। परिणाम को बाद में फ़ंक्शन वर्गों के साथ लगभग-ईआरएम एल्गोरिदम तक बढ़ा दिया गया, जिनमें अद्वितीय मिनिमाइज़र नहीं हैं।

वापनिक के काम में, जिसे जिन्हें वीसी सिद्धांत के रूप में जाना गया, एक सीखने वाले एल्गोरिदम के सामान्यीकरण और सीखने जा रहे फ़ंक्शन के विश्वासयोग्यता समष्टि के गुणों के बीच एक संबंध स्थापित किया गया। यद्यपि, इन परिणामों को असीमित वीसी-आयाम के परिकल्पना समष्टिों वाले एल्गोरिदम पर लागू नहीं किया जा सका। दूसरे शब्दों मे कहें तो, ये परिणाम उस समय लागू नहीं किए जा सकते थे जब शिक्षित हो रही जानकारी की जटिलता बहुत ज्यादा थी और उसे मापने की संभावना नहीं थी। कुछ सबसे सरल मशीन लर्निंग एल्गोरिदम, जैसे रीज्रेशन के लिए, हिपोथिसिस स्पेस का वीसी आयाम अनिश्चित होता है। दूसरा उदाहरण है भाषा शिक्षण एल्गोरिदम जो असीमित लंबाई के वाक्यों को प्रस्तुत कर सकते हैं।

स्टेबिलिटी विश्लेषण 2000 के दशक में कम्प्यूटेशनल शिक्षण सिद्धांत के लिए विकसित किया गया था और यह सामान्यीकरण सीमा प्राप्त करने के लिए एक वैकल्पिक विधि है। एक एल्गोरिदम की स्टेबिलिटी शिक्षण प्रक्रिया की एक गुणवत्ता है, जो कि सीधे हिपोथिसिस स्पेस , की एक प्रत्यक्ष गुणवत्ता नहीं है, और वीसी-आयाम के साथ असीमित या अनिर्दिष्ट हिपोथिसिस स्पेस के एल्गोरिदमों में मूल्यांकन किया जा सकता है, जैसे जैसे कि नियरेस्ट नेबर। एक स्टेबल लर्निंग एल्गोरिदम वह होता है जिसमें प्रशिक्षण सेट को थोड़े से संशोधित करने पर अधिगत फ़ंक्शन में अत्यधिक परिवर्तित नहीं होता है, उदाहरण के लिए किसी उदाहरण को छोड़ देने से लीव वन आउट त्रुटि के माप का उपयोग क्रॉस वैलिडेशन लीव वन आउट एल्गोरिदम में एक एल्गोरिदम की स्टेबिलिटी का मूल्यांकन करने के लिए किया जाता है, जिससे की लॉस फ़ंक्शन के संबंध में इस तरह, स्टेबिलिटी विश्लेषण मशीन लर्निंग में संवेदनशीलता विश्लेषण का एक अनुप्रयोग है।

क्लासिक परिणामों का सारांश

  • शिक्षण सिद्धांत में स्टेबिलिटी की प्रारंभिक विवरण एंड्री निकोलाइविच तिखोनोव द्वारा शिक्षण मैप , की सततता के संबंध में की गई थी। यह उनके काम का एक महत्वपूर्ण भाग था जो उन्होंने शिक्षण सिद्धांत के क्षेत्र में किया था।
  • 1979 में डेव्रोय और वाग्नर ने देखा कि एक एल्गोरिदम का लीव-वन-आउट व्यवहार संख्या में छोटे परिवर्तनों के प्रति उसकी संवेदनशीलता से संबंधित होता है।[1]
  • 1999 - किर्न्स और रॉन ने परिमित वीसी-आयाम और स्टेबिलिटी के बीच संबंध की खोज की।[2]
  • 2002 - एक ऐतिहासिक पेपर में, बाउस्केट और एलिसिफ़ ने एक सीखने के एल्गोरिदम की समान परिकल्पना स्टेबिलिटी की धारणा का प्रस्ताव रखा और दिखाया कि यह कम सामान्यीकरण त्रुटि का संकेत देता है। यद्यपि, समान परिकल्पना स्टेबिलिटी एक मजबूत स्थिति है जो एल्गोरिदम के बड़े वर्गों पर लागू नहीं होती है, जिसमें केवल दो कार्यों की परिकल्पना समष्टि के साथ ईआरएम एल्गोरिदम भी सम्मिलित है।[3]
  • 2002 - कुटिन और नियोगी ने स्टेबिलिटी के कई कमजोर रूपों के लिए सामान्यीकरण सीमाएं प्रदान करके बाउस्केट और एलिसिफ़ के परिणामों को बढ़ाया, जिसे उन्होंने लगभग-हर जगह स्टेबिलिटी कहा। इसके अतिरिक्त, उन्होंने संभवतः अनुमानित रूप से सही सेटिंग में ईआरएम एल्गोरिदम में स्टेबिलिटी और स्टेबिलिटी के बीच संबंध स्थापित करने में प्रारंभिक कदम उठाया।[4]
  • 2004 - पोगियो एट अल।स्टेबिलिटी और ईआरएम स्टेबिलिटी के बीच एक सामान्य संबंध स्थापित हुआ। उन्होंने लीव-वन-आउट-स्टेबिलिटी का एक सांख्यिकीय रूप प्रस्तावित किया, जिसे उन्होंने सीवीईईलू स्टेबिलिटी कहा, और दिखाया कि यह a सीमित लॉसवर्गों में सामान्यीकरण के लिए पर्याप्त है, और b वर्ग हानि, पूर्ण मूल्य और बाइनरी वर्गीकरण लॉसजैसे कुछ लॉसकार्यों के लिए ईआरएम एल्गोरिदम की स्टेबिलिटी के लिए पर्याप्त है।[5]
  • 2010 - शैलेव श्वार्ट्ज एट अल ने परिकल्पना समष्टि और लॉसवर्ग के बीच जटिल संबंधों के कारण वाप्निक के मूल परिणामों में समस्याएं देखी गईं। वे स्टेबिलिटी की धारणाओं पर चर्चा करते हैं जो विभिन्न लॉसवर्गों और पर्यवेक्षित और गैर-पर्यवेक्षित सीखने के विभिन्न प्रकारों का समावेश करती हैं।।[6]
  • 2016 - मोरिट्ज हार्ट और सहकर्मियों ने निश्चित धारणाओं पर आधारित हिपोथिसिस और प्रत्येक इंस्टेंस को मॉडल को अपडेट करने के लिए कितनी बार उपयोग किया जाता है, इसे मध्यस्थता का सिद्धांत सिद्ध किया है। वे ग्रैडिएंट डिसेंट की स्थिरता को सिद्ध करने में सफल रहे। [7]


प्रारंभिक परिभाषाएँ

हम सीखने के एल्गोरिदम प्रशिक्षण सेट से संबंधित कई शब्दों को परिभाषित करते हैं, ताकि हम स्टेबिलिटी को कई तरीकों से परिभाषित कर सकें और क्षेत्र से प्रमेय प्रस्तुत कर सकें।

एक मशीन लर्निंग एल्गोरिदम, जिसे लर्निंग मैप के रूप में भी जाना जाता है , एक प्रशिक्षण डेटा सेट को मैप करता है, जो एक फ़ंक्शन पर से को लेबल किए गए उदाहरणों का एक सेट है, जहाँ और प्रशिक्षण उदाहरणों के एक ही समष्टि पर हैं। फलन फलनों के एक परिकल्पना समष्टि से चुने गए हैं जिन्हें कहा जाता है .

एक एल्गोरिदम जिससे सिखाई जाती है, उसके प्रशिक्षण सेट को निर्धारित किया जाता है जिसे निम्नलिखित रूप में प्रस्तुत किया जा सकता है:

जहां विशेष और हैं। यह नामांकन एक अज्ञात वितरण D से आपसी स्वतंत्र और एक साथ प्राप्त किए गए हैं।

इस प्रकार, शिक्षण मानचित्र को से तक एक मैपिंग के रूप में परिभाषित किया जाता है, जो एक प्रशिक्षण सेट को एक फ़ंक्शन से मानचित्रित करता है, जो से तक है। यहां, हम केवल स्टैटिक एल्गोरिदम को ध्यान में रखते हैं जिसमें के संबंध में सममितिक है, अर्थात् यह प्रशिक्षण सेट में तत्वों के क्रम पर निर्भर नहीं करता है। इसके अतिरिक्त, हम मानते हैं कि सभी फ़ंक्शन मापनीय हैं और सभी सेट गणनीय हैं।

परिकल्पना की हानि एक उदाहरण के संबंध में पुनः के रूप में परिभाषित किया गया है

की अनुभवजन्य त्रुटि है।

की वास्तविक त्रुटि है। आकार m के एक प्रशिक्षण सेट S को देखते हुए, हम सभी i = 1....m के लिए, निम्नानुसार संशोधित प्रशिक्षण सेट बनाएंगे:

  • i-वें तत्व को हटाकर

  • i-वें तत्व को प्रतिस्थापित करके







स्टेबिलिटी की परिभाषाएँ

परिकल्पना स्टेबिलिटी

एक एल्गोरिदम लॉसफ़ंक्शन V के संबंध में परिकल्पना स्टेबिलिटी β है यदि निम्नलिखित मान्य है:


बिंदुवार परिकल्पना स्टेबिलिटी

एक एल्गोरिदम का लॉसफ़ंक्शन V के संबंध में बिंदु-वार परिकल्पना स्टेबिलिटी β है यदि निम्नलिखित मान्य है:


त्रुटि स्टेबिलिटी

एक एल्गोरिदम का लॉसफ़ंक्शन V के संबंध में त्रुटि स्टेबिलिटी β है यदि निम्नलिखित मान्य है:


समरूप स्टेबिलिटी

एक एल्गोरिदम का लॉसफ़ंक्शन V के संबंध में समरूप स्टेबिलिटी β है यदि निम्नलिखित मान्य है:

एक समान स्टेबिलिटी β का एक संभाव्य संस्करण है:

एक एल्गोरिदम को स्टेबल कहा जाता है, जब का मान के रूप में घटता है।

लीव-वन-आउट क्रॉस-वैलिडेशन (सीवीलू) स्टेबिलिटी

एक एल्गोरिदम के लॉसफ़ंक्शन V के संबंध में सीवीलू स्टेबिलिटी β है यदि निम्नलिखित मान्य है:

(सीवीलू) स्टेबिलिटी की परिभाषा पहले देखी गई बिंदुवार-परिकल्पना स्टेबिलिटी के समान है।

अपेक्षित-लीव-वन-आउट त्रुटि () स्टेबिलिटी

एक एल्गोरिदम में स्टेबिलिटी है यदि और A में प्रत्येक n के लिए a उपलब्ध है:

, के लिए और , शून्य पर अग्रसित है


पारम्परिक प्रमेय

बाउस्केट और एलिसिफ़ (02) से:

सममित लर्निंग एल्गोरिदम जिनमें सीमित लॉस होता है, यदि एल्गोरिदम के पास पहले दिए गए सामान्यीकरण के साथ उचित संभावनात्मक परिभाषा है, तो वे एल्गोरिदम सामान्यीकरण करते हैं।

समान स्टेबिलिटी एक मजबूत स्थिति है जो सभी एल्गोरिदम द्वारा पूरी नहीं की जाती है, लेकिन आश्चर्यजनक रूप से, नियमितीकरण एल्गोरिदम के बड़े और महत्वपूर्ण वर्ग द्वारा पूरी की जाती है। सामान्यीकरण की सीमा लेख में दी गई है।

मुखर्जी एट अल से. (06):

  • सममित लर्निंग एल्गोरिदम्स जिनमें सीमित लॉस होता है, यदि एल्गोरिदम के पास ऊपर दिए गए दोनों समष्टिीय आंतरिक समीकरण और अपेक्षित आंतरिक त्रुटि ) स्टेबिलिटी है, तो वे एल्गोरिदम सामान्यीकरण करते हैं।,
  • केवल एक स्थिरता शर्त से सामान्यीकरण होना पर्याप्त नहीं है, परंतु दोनों स्थिरता शर्तों का साथ मिलकर सामान्यीकरण सुनिश्चित करता है
  • विशेष रूप से ईआरएम एल्गोरिदम के लिए, लीव-वन-आउट क्रॉस-वैलिडेशन स्टेबिलिटी और सामान्यीकरण के लिए स्टेबिलिटी आवश्यक और पर्याप्त दोनों है।

यह सीखने के सिद्धांत की नींव के लिए एक महत्वपूर्ण परिणाम है, क्योंकि यह दर्शाता है कि एल्गोरिदम के दो पहले से असंबंधित गुण, एल्गोरिदम और स्टेबिलिटी, ईआरएम के लिए समतुल्य हैं। सामान्यीकरण की सीमा लेख में दी गई है

स्टेबल एल्गोरिदम

यह उन एल्गोरिदम की एक सूची है जिन्हें स्टेबल दिखाया गया है, और वह लेख जहां संबंधित सामान्यीकरण सीमाएँ प्रदान की गई हैं।

  • रेखीय प्रतिगमन[8]
  • {0-1} लॉसफ़ंक्शन के साथ के -एनएन क्लासिफायरियर।[1]
  • बाउंडेड कर्नेल के समर्थन वेक्टर यंत्र एसवीएम वर्गीकरण का समर्थन करें और जहां रिप्रोड्यूसिंग कर्नेल हिल्बर्ट स्पेस में रेग्युलराइज़र एक मानक है। एक बड़ा नियमितीकरण स्टेबलांक अच्छी स्टेबिलिटी की ओर ले जाता है.[3]
  • सॉफ्ट मार्जिन एसवीएम वर्गीकरण।[3]
  • नियमितीकरण न्यूनतम वर्ग प्रतिगमन।[3]
  • वर्गीकरण के लिए न्यूनतम सापेक्ष एन्ट्रापी एल्गोरिथ्म।[3]
  • बैगिंग रेगुलराइज़र्स का एक संस्करण है जिसमें रिग्रेसर्स की संख्या नियंत्रित है और के साथ बढ़ती है।.[9]
  • मल्टी-क्लास एसवीएम वर्गीकरण।[9]
  • सभी लर्निंग एल्गोरिदम जो टिखोनोव रेगुलराइज़ेशन के साथ हैं, वे समान स्टेबिलिटी मानदंड को पूरा करते हैं और इसलिए वे सार्वभौमिक होते हैं।[10]


संदर्भ

  1. 1.0 1.1 L. Devroye and Wagner, Distribution-free performance bounds for potential function rules, IEEE Trans. Inf. Theory 25(5) (1979) 601–604.
  2. M. Kearns and D. Ron, Algorithmic stability and sanity-check bounds for leave-one-out cross-validation, Neural Comput. 11(6) (1999) 1427–1453.
  3. 3.0 3.1 3.2 3.3 3.4 O. Bousquet and A. Elisseeff. Stability and generalization. J. Mach. Learn. Res., 2:499–526, 2002.
  4. S. Kutin and P. Niyogi, Almost-everywhere algorithmic stability and generalization error, Technical Report TR-2002-03, University of Chicago (2002).
  5. S. Mukherjee, P. Niyogi, T. Poggio, and R. M. Rifkin. Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization. Adv. Comput. Math., 25(1-3):161–193, 2006.
  6. Shalev Shwartz, S., Shamir, O., Srebro, N., Sridharan, K., Learnability, Stability and Uniform Convergence, Journal of Machine Learning Research, 11(Oct):2635-2670, 2010.
  7. Moritz Hardt, Benjamin Recht, Yoram Singer, Train faster, generalize better: Stability of stochastic gradient descent, ICML 2016.
  8. Elisseeff, A. A study about algorithmic stability and their relation to generalization performances. Technical report. (2000)
  9. 9.0 9.1 Rifkin, R. Everything Old is New Again: A fresh look at historical approaches in machine learning. Ph.D. Thesis, MIT, 2002
  10. Rosasco, L. and Poggio, T. Stability of Tikhonov Regularization, 2009


अग्रिम पठन

  • S.Kutin and P.Niyogi.Almost-everywhere algorithmic stability and generalization error. In Proc. of UAI 18, 2002
  • S. Rakhlin, S. Mukherjee, and T. Poggio. Stability results in learning theory. Analysis and Applications, 3(4):397–419, 2005
  • V.N. Vapnik. The Nature of Statistical Learning Theory. Springer, 1995
  • Vapnik, V., Statistical Learning Theory. Wiley, New York, 1998
  • Poggio, T., Rifkin, R., Mukherjee, S. and Niyogi, P., "Learning Theory: general conditions for predictivity", Nature, Vol. 428, 419-422, 2004
  • Andre Elisseeff, Theodoros Evgeniou, Massimiliano Pontil, Stability of Randomized Learning Algorithms, Journal of Machine Learning Research 6, 55–79, 2010
  • Elisseeff, A. Pontil, M., Leave-one-out Error and Stability of Learning Algorithms with Applications, NATO SCIENCE SERIES SUB SERIES III COMPUTER AND SYSTEMS SCIENCES, 2003, VOL 190, pages 111-130
  • Shalev Shwartz, S., Shamir, O., Srebro, N., Sridharan, K., Learnability, Stability and Uniform Convergence, Journal of Machine Learning Research, 11(Oct):2635-2670, 2010