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

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

उदाहरण के रूप में, एक मशीन लर्निंग एल्गोरिदम को समझने के लिए, हम एक यांत्रिकी वर्णमाला के हस्तलिखित अक्षरों को पहचानने के लिए प्रशिक्षण देने के लिए उपयुक्त हैं, जिसमें 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$, फिर एंड्री निकोलाइविच तिखोनोव.
• 1979 - डेवरोय और वैगनर ने देखा कि एल्गोरिदम का लीव-वन-आउट व्यवहार नमूने में छोटे बदलावों के प्रति इसकी संवेदनशीलता से संबंधित है।
• 1999 - किर्न्स और रॉन ने परिमित वीसी-आयाम और स्थिरता के बीच संबंध की खोज की।
• 2002 - एक ऐतिहासिक पेपर में, बाउस्केट और एलिसिफ़ ने एक सीखने के एल्गोरिदम की समान परिकल्पना स्थिरता की धारणा का प्रस्ताव रखा और दिखाया कि यह कम सामान्यीकरण त्रुटि का संकेत देता है। हालाँकि, समान परिकल्पना स्थिरता एक मजबूत स्थिति है जो एल्गोरिदम के बड़े वर्गों पर लागू नहीं होती है, जिसमें केवल दो कार्यों की परिकल्पना स्थान के साथ ईआरएम एल्गोरिदम भी शामिल है।
• 2002 - कुटिन और नियोगी ने स्थिरता के कई कमजोर रूपों के लिए सामान्यीकरण सीमाएं प्रदान करके बाउस्केट और एलिसिफ़ के परिणामों को बढ़ाया, जिसे उन्होंने लगभग-हर जगह स्थिरता कहा। इसके अलावा, उन्होंने संभवतः अनुमानित रूप से सही (पीएसी) सेटिंग में ईआरएम एल्गोरिदम में स्थिरता और स्थिरता के बीच संबंध स्थापित करने में प्रारंभिक कदम उठाया।
• 2004 - पोगियो एट अल। स्थिरता और ईआरएम स्थिरता के बीच एक सामान्य संबंध साबित हुआ। उन्होंने लीव-वन-आउट-स्थिरता का एक सांख्यिकीय रूप प्रस्तावित किया, जिसे उन्होंने सीवीईईलू स्थिरता कहा, और दिखाया कि यह ए) सीमित हानि वर्गों में सामान्यीकरण के लिए पर्याप्त है, और बी) वर्ग हानि, पूर्ण मूल्य और बाइनरी वर्गीकरण हानि जैसे कुछ हानि कार्यों के लिए ईआरएम एल्गोरिदम की स्थिरता (और इस प्रकार सामान्यीकरण) के लिए आवश्यक और पर्याप्त है।
• 2010 - शैलेव श्वार्ट्ज एट अल। परिकल्पना स्थान और हानि वर्ग के बीच जटिल संबंधों के कारण वाप्निक के मूल परिणामों में समस्याएं देखी गईं। वे स्थिरता की धारणाओं पर चर्चा करते हैं जो विभिन्न हानि वर्गों और पर्यवेक्षित और गैर-पर्यवेक्षित सीखने के विभिन्न प्रकारों को पकड़ती हैं।
• 2016 - मोरित्ज़ हार्ड्ट एट अल। परिकल्पना पर निश्चित धारणा और मॉडल को अद्यतन करने के लिए प्रत्येक उदाहरण का उपयोग करने की संख्या को देखते हुए ग्रेडिएंट डिसेंट की सिद्ध स्थिरता।

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

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

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

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

एल्गोरिदम जो स्थिर हैं

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

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

अग्रिम पठन

• 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