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

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

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

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

इतिहास

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

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

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

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

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

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