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

Revision as of 23:50, 6 August 2023

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

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

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

इतिहास

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

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

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

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

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

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

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

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

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

वह प्रशिक्षण सेट जिससे एक एल्गोरिदम सीखता है उसे इस प्रकार परिभाषित किया गया है

$S=\{z_{1}=(x_{1},\ y_{1})\ ,..,\ z_{m}=(x_{m},\ y_{m})\}$ और आकार का है $m$ में $Z=X\times Y$ तैयार आई.आई.डी. एक अज्ञात वितरण से डी.

इस प्रकार, सीखने का नक्शा $L$ से मैपिंग के रूप में परिभाषित किया गया है $Z_{m}$ में $H$ , एक प्रशिक्षण सेट का मानचित्रण $S$ एक समारोह पर $f_{S}$ से $X$ को $Y$ . यहां, हम केवल नियतात्मक एल्गोरिदम पर विचार करते हैं $L$ के संबंध में सममित है $S$ , यानी यह प्रशिक्षण सेट में तत्वों के क्रम पर निर्भर नहीं करता है। इसके अलावा, हम मानते हैं कि सभी फ़ंक्शन मापने योग्य हैं और सभी सेट गणनीय हैं।

हानि $V$ एक परिकल्पना का $f$ एक उदाहरण के संबंध में $z=(x,y)$ फिर परिभाषित किया गया है $V(f,z)=V(f(x),y)$ .

की अनुभवजन्य त्रुटि $f$ है $I_{S}[f]={\frac {1}{n}}\sum V(f,z_{i})$ .

की सच्ची त्रुटि $f$ है $I[f]=\mathbb {E} _{z}V(f,z)$ आकार m के एक प्रशिक्षण सेट S को देखते हुए, हम सभी i = 1....m के लिए, निम्नानुसार संशोधित प्रशिक्षण सेट बनाएंगे:

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

$S^{|i}=\{z_{1},...,\ z_{i-1},\ z_{i+1},...,\ z_{m}\}$

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

$S^{i}=\{z_{1},...,\ z_{i-1},\ z_{i}',\ z_{i+1},...,\ z_{m}\}$

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

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

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

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

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

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

$\forall i\in \ \{1,...,m\},\mathbb {E} _{S}[|V(f_{S},z_{i})-V(f_{S^{|i}},z_{i})|]\leq \beta .$

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

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

$\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$

समान स्टेबिलिटी

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

$\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$ एक समान स्टेबिलिटी β का एक संभाव्य संस्करण है:

$\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 \}\geq 1-\delta$ एक एल्गोरिदम को स्टेबल कहा जाता है, जब का मान $\beta$ के रूप में घटता है $O({\frac {1}{m}})$ .

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

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

$\forall i\in \{1,...,m\},\mathbb {P} _{S}\{|V(f_{S},z_{i})-V(f_{S^{|i}},z_{i})|\leq \beta _{CV}\}\geq 1-\delta _{CV}$ (सीवीलू) स्टेबिलिटी की परिभाषा पहले देखी गई बिंदुवार-परिकल्पना स्टेबिलिटी के बराबर है।

अपेक्षित-छोड़ें-एक-बाहर त्रुटि ( $Eloo_{err}$ ) स्टेबिलिटी

एक एल्गोरिदम $L$ है $Eloo_{err}$ स्टेबिलिटी यदि प्रत्येक n के लिए a मौजूद है $\beta _{EL}^{m}$ और ए $\delta _{EL}^{m}$ ऐसा है कि:

$\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}\}\geq 1-\delta _{EL}^{m}$ , साथ $\beta _{EL}^{m}$ और $\delta _{EL}^{m}$ के लिए शून्य पर जा रहा हूँ $m,\rightarrow \infty$

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

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

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

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

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

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

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

एल्गोरिदम जो स्टेबल हैं

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

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

संदर्भ

↑ ^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.
↑ 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.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.
↑ S. Kutin and P. Niyogi, Almost-everywhere algorithmic stability and generalization error, Technical Report TR-2002-03, University of Chicago (2002).
↑ 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.
↑ Shalev Shwartz, S., Shamir, O., Srebro, N., Sridharan, K., Learnability, Stability and Uniform Convergence, Journal of Machine Learning Research, 11(Oct):2635-2670, 2010.
↑ Moritz Hardt, Benjamin Recht, Yoram Singer, Train faster, generalize better: Stability of stochastic gradient descent, ICML 2016.
↑ Elisseeff, A. A study about algorithmic stability and their relation to generalization performances. Technical report. (2000)
↑ ^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
↑ 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

[devroye1979-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.

[bousquet2002-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)

[rifkin2002-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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Line 1: / Line 1: @@
 {{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}}.
+* 1900 के आरंभ में - सीखने के सिद्धांत में स्टेबिलिटी को सबसे पहले सीखने के मानचित्र की निरंतरता के संदर्भ में वर्णित किया गया था <math>L</math>, फिर [[एंड्री निकोलाइविच तिखोनोव]]{{citation needed|date=May 2021}}.
 * 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 - पोगियो एट अल। स्टेबिलिटी और ईआरएम स्टेबिलिटी के बीच एक सामान्य संबंध साबित हुआ। उन्होंने लीव-वन-आउट-स्टेबिलिटी का एक सांख्यिकीय रूप प्रस्तावित किया, जिसे उन्होंने ''सीवीईईलू स्टेबिलिटी'' कहा, और दिखाया कि यह ए) सीमित हानि वर्गों में सामान्यीकरण के लिए पर्याप्त है, और बी) वर्ग हानि, पूर्ण मूल्य और बाइनरी वर्गीकरण हानि जैसे कुछ हानि कार्यों के लिए ईआरएम एल्गोरिदम की स्टेबिलिटी (और इस प्रकार सामान्यीकरण) के लिए आवश्यक और पर्याप्त है।<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>.
@@ 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>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>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>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\}, \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 के संबंध में CVloo स्टेबिलिटी β है यदि निम्नलिखित मान्य है:
 <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>Eloo_{err}</math>) स्टेबिलिटी===
-एक एल्गोरिदम <math>L</math> है <math>Eloo_{err}</math> स्थिरता यदि प्रत्येक n के लिए a मौजूद है <math>\beta_{EL}^m</math> और ए <math>\delta_{EL}^m</math> ऐसा है कि:
+एक एल्गोरिदम <math>L</math> है <math>Eloo_{err}</math> स्टेबिलिटी यदि प्रत्येक n के लिए a मौजूद है <math>\beta_{EL}^m</math> और ए <math>\delta_{EL}^m</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>
@@ Line 99: / Line 99: @@
 बाउस्केट और एलिसिफ़ (02) से:
-सीमित हानि वाले सममित शिक्षण एल्गोरिदम के लिए, यदि एल्गोरिदम में उपरोक्त संभाव्य परिभाषा के साथ समान स्थिरता है, तो एल्गोरिदम सामान्यीकृत होता है।
+सीमित हानि वाले सममित शिक्षण एल्गोरिदम के लिए, यदि एल्गोरिदम में उपरोक्त संभाव्य परिभाषा के साथ समान स्टेबिलिटी है, तो एल्गोरिदम सामान्यीकृत होता है।
-समान स्थिरता एक मजबूत स्थिति है जो सभी एल्गोरिदम द्वारा पूरी नहीं की जाती है, लेकिन आश्चर्यजनक रूप से, नियमितीकरण एल्गोरिदम के बड़े और महत्वपूर्ण वर्ग द्वारा पूरी की जाती है।
+समान स्टेबिलिटी एक मजबूत स्थिति है जो सभी एल्गोरिदम द्वारा पूरी नहीं की जाती है, लेकिन आश्चर्यजनक रूप से, नियमितीकरण एल्गोरिदम के बड़े और महत्वपूर्ण वर्ग द्वारा पूरी की जाती है।
 सामान्यीकरण की सीमा लेख में दी गई है।
 मुखर्जी एट अल से. (06):
-*सीमाबद्ध हानि वाले सममित शिक्षण एल्गोरिदम के लिए, यदि एल्गोरिदम में ''दोनों'' लीव-वन-आउट क्रॉस-वैलिडेशन (सीवीलू) स्थिरता और अपेक्षित-लीव-वन-आउट त्रुटि है (<math>Eloo_{err}</math>) स्थिरता जैसा कि ऊपर परिभाषित किया गया है, फिर एल्गोरिदम सामान्यीकृत होता है।
+*सीमाबद्ध हानि वाले सममित शिक्षण एल्गोरिदम के लिए, यदि एल्गोरिदम में ''दोनों'' लीव-वन-आउट क्रॉस-वैलिडेशन (सीवीलू) स्टेबिलिटी और अपेक्षित-लीव-वन-आउट त्रुटि है (<math>Eloo_{err}</math>) स्टेबिलिटी जैसा कि ऊपर परिभाषित किया गया है, फिर एल्गोरिदम सामान्यीकृत होता है।
 *सामान्यीकरण के लिए कोई भी स्थिति अकेली पर्याप्त नहीं है। हालाँकि, दोनों मिलकर सामान्यीकरण सुनिश्चित करते हैं (जबकि इसका विपरीत सत्य नहीं है)।
-*ईआरएम एल्गोरिदम के लिए विशेष रूप से (वर्ग हानि के लिए कहें), लीव-वन-आउट क्रॉस-वैलिडेशन (सीवीलू) स्थिरता और सामान्यीकरण के लिए स्थिरता आवश्यक और पर्याप्त दोनों है।
+*ईआरएम एल्गोरिदम के लिए विशेष रूप से (वर्ग हानि के लिए कहें), लीव-वन-आउट क्रॉस-वैलिडेशन (सीवीलू) स्टेबिलिटी और सामान्यीकरण के लिए स्टेबिलिटी आवश्यक और पर्याप्त दोनों है।
-यह सीखने के सिद्धांत की नींव के लिए एक महत्वपूर्ण परिणाम है, क्योंकि यह दर्शाता है कि एल्गोरिदम के दो पहले से असंबंधित गुण, स्थिरता और स्थिरता, ईआरएम (और कुछ हानि कार्यों) के लिए समतुल्य हैं।
+यह सीखने के सिद्धांत की नींव के लिए एक महत्वपूर्ण परिणाम है, क्योंकि यह दर्शाता है कि एल्गोरिदम के दो पहले से असंबंधित गुण, स्टेबिलिटी और स्टेबिलिटी, ईआरएम (और कुछ हानि कार्यों) के लिए समतुल्य हैं।
 सामान्यीकरण की सीमा लेख में दी गई है।
-==एल्गोरिदम जो स्थिर हैं==
+==एल्गोरिदम जो स्टेबल हैं==
-यह उन एल्गोरिदम की एक सूची है जिन्हें स्थिर दिखाया गया है, और वह लेख जहां संबंधित सामान्यीकरण सीमाएँ प्रदान की गई हैं।
+यह उन एल्गोरिदम की एक सूची है जिन्हें स्टेबल दिखाया गया है, और वह लेख जहां संबंधित सामान्यीकरण सीमाएँ प्रदान की गई हैं।
 * [[रेखीय प्रतिगमन]]<ref>Elisseeff, A. A study about algorithmic stability and
@@ Line 120: / Line 120: @@
   report. (2000)
 </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>
-*मल्टी-क्लास एसवीएम वर्गीकरण।<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>

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 23:50, 6 August 2023

Contents

इतिहास

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

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