ऑनलाइन मशीन लर्निंग

Not to be confused with ऑनलाइन और ऑफलाइन.

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

परिचय

पर्यवेक्षित शिक्षण की सेटिंग में, $f:X\to Y$ का एक फ़ंक्शन सीखा जाना है, जहां $X$ को इनपुट के स्थान के रूप में और $Y$ को एक स्थान के रूप में माना जाता है आउटपुट का, जो उन उदाहरणों पर अच्छी तरह से भविष्यवाणी करता है जो $X\times Y$ पर संयुक्त संभाव्यता वितरण $p(x,y)$ से निकाले गए हैं। वास्तव में, सीखने वाले को कभी भी उदाहरणों पर सही वितरण $p(x,y)$ का पता नहीं चलता है। इसके अतिरिक्त, शिक्षार्थी के पास समान्यत: उदाहरणों $(x_{1},y_{1}),\ldots ,(x_{n},y_{n})$ के प्रशिक्षण सेट तक पहुंच होती है। इस सेटिंग में, हानि फ़ंक्शन को $V:Y\times Y\to \mathbb {R}$ के रूप में दिया गया है, जैसे कि $V(f(x),y)$ अनुमानित मान $f(x)$ और वास्तविक मान के बीच अंतर को मापता है जो की $y$ आदर्श लक्ष्य एक फ़ंक्शन $f\in {\mathcal {H}}$ का चयन करना है, जहां ${\mathcal {H}}$ फ़ंक्शन का एक स्थान है जिसे परिकल्पना स्थान कहा जाता है, जिससे कुल हानि की कुछ धारणा कम से कम हो। मॉडल के प्रकार (सांख्यिकीय या प्रतिकूल) के आधार पर, कोई हानि की विभिन्न धारणाओं को तैयार कर सकता है, जो विभिन्न शिक्षण एल्गोरिदम को उत्पन्न करता है।

ऑनलाइन शिक्षण का सांख्यिकीय दृष्टिकोण

सांख्यिकीय शिक्षण मॉडल में, प्रशिक्षण नमूना $(x_{i},y_{i})$ को वास्तविक वितरण $p(x,y)$ से लिया गया माना जाता है और इसका उद्देश्य अपेक्षित "खतरा" को कम करना है।

$I[f]=\mathbb {E} [V(f(x),y)]=\int V(f(x),y)\,dp(x,y)\ .$

इस स्थिति में एक सामान्य प्रतिमान अनुभवजन्य आपत्तिपूर्ण न्यूनतमकरण या नियमित अनुभवजन्य आपत्तिपूर्ण न्यूनतमकरण (समान्यत: तिखोनोव नियमितीकरण) के माध्यम से एक फ़ंक्शन ${\hat {f}}$ का अनुमान लगाना है। यहां हानि फ़ंक्शन का विकल्प अनेक प्रसिद्ध शिक्षण एल्गोरिदम को उत्पन्न करता है जैसे कि नियमित न्यूनतम वर्ग और समर्थन वेक्टर मशीनें इस श्रेणी में एक विशुद्ध रूप से ऑनलाइन मॉडल केवल नए इनपुट $(x_{t+1},y_{t+1})$, वर्तमान सर्वोत्तम भविष्यवक्ता $f_{t}$ और कुछ अतिरिक्त संग्रहीत जानकारी (जिसमें समान्यत: प्रशिक्षण डेटा आकार से स्वतंत्र संचयन आवश्यकताओं की अपेक्षा की जाती है) के आधार पर सीखेगा अनेक फॉर्मूलेशन के लिए, उदाहरण के लिए नॉनलाइनियर कर्नेल विधियां, वास्तविक ऑनलाइन सीखना संभव नहीं है, चूँकि पुनरावर्ती एल्गोरिदम के साथ हाइब्रिड ऑनलाइन सीखने का एक रूप उपयोग किया जा सकता है जहां $f_{t+1}$ को $f_{t}$ और सभी पिछले डेटा पर निर्भर होने की अनुमति है अंक $(x_{1},y_{1}),\ldots ,(x_{t},y_{t})$ इस स्थिति में, स्थान की आवश्यकताओं के स्थिर रहने की अब आश्वासन नहीं है क्योंकि इसके लिए सभी पिछले डेटा बिंदुओं को संग्रहीत करने की आवश्यकता होती है, किंतु बैच सीखने की तकनीकों की तुलना में समाधान में नए डेटा बिंदु को जोड़ने के साथ गणना करने में कम समय लग सकता है।

उपरोक्त उद्देश्यों पर नियंत्रण पाने के लिए एक सामान्य रणनीति मिनी-बैचों का उपयोग करके सीखना है, जो एक समय में $b\geq 1$ डेटा बिंदुओं के एक छोटे बैच को संसाधित करता है, इसे प्रशिक्षण की कुल संख्या से बहुत कम $b$ के लिए छद्म-ऑनलाइन शिक्षण माना जा सकता है। अंक. मशीन लर्निंग एल्गोरिदम के अनुकूलित आउट-ऑफ-कोर वर्जन प्राप्त करने के लिए प्रशिक्षण डेटा को बार-बार पास करने के साथ मिनी-बैच तकनीकों का उपयोग किया जाता है, उदाहरण के लिए, स्टोकेस्टिक ग्रेडिएंट डिसेंट बैकप्रॉपैगेशन के साथ संयुक्त होने पर, यह वर्तमान में कृत्रिम तंत्रिका नेटवर्क के प्रशिक्षण के लिए वास्तविक प्रशिक्षण पद्धति है।

उदाहरण: रैखिक न्यूनतम वर्ग

Main article: रैखिक लघुतम वर्ग (गणित)

ऑनलाइन शिक्षण में विभिन्न प्रकार के विचारों को समझाने के लिए रैखिक न्यूनतम वर्गों का सरल उदाहरण उपयोग किया जाता है। विचार इतने सामान्य हैं कि उन्हें अन्य सेटिंग्स पर प्रयुक्त किया जा सकता है, उदाहरण के लिए अन्य उत्तल हानि कार्यों के साथ है।

बैच सीखना

$f$ के साथ पर्यवेक्षित शिक्षण की सेटिंग पर विचार करें, जो कि सीखा जाने वाला एक रैखिक कार्य है:

$f(x_{j})=\langle w,x_{j}\rangle =w\cdot x_{j}$

जहां $x_{j}\in \mathbb {R} ^{d}$ इनपुट (डेटा बिंदु) का एक वेक्टर है और $w\in \mathbb {R} ^{d}$ एक रैखिक फ़िल्टर वेक्टर है। लक्ष्य फ़िल्टर वेक्टर $w$ की गणना करना है। इस प्रयोजन के लिए, एक वर्ग हानि फ़ंक्शन है

$V(f(x_{j}),y_{j})=(f(x_{j})-y_{j})^{2}=(\langle w,x_{j}\rangle -y_{j})^{2}$

वेक्टर की गणना करने के लिए उपयोग किया जाता है $w$ जो अनुभवजन्य हानि को कम करता है

$I_{n}[w]=\sum _{j=1}^{n}V(\langle w,x_{j}\rangle ,y_{j})=\sum _{j=1}^{n}(x_{j}^{T}w-y_{j})^{2}$ कहाँ

$y_{j}\in \mathbb {R}$.

होने देना $X$ हो $i\times d$ डेटा मैट्रिक्स और $y\in \mathbb {R} ^{i}$ पहले के आगमन के बाद लक्ष्य मानों का कॉलम वेक्टर है $i$ डेटा अंक। यह मानते हुए कि सहप्रसरण मैट्रिक्स $\Sigma _{i}=X^{T}X$ उलटा है (अन्यथा तिखोनोव नियमितीकरण के समान तरीके से आगे बढ़ना प्राथमिकता है), सबसे अच्छा समाधान $f^{*}(x)=\langle w^{*},x\rangle$ रैखिक न्यूनतम वर्ग समस्या द्वारा दी गई है

$w^{*}=(X^{T}X)^{-1}X^{T}y=\Sigma _{i}^{-1}\sum _{j=1}^{i}x_{j}y_{j}$.

अब, सहप्रसरण मैट्रिक्स की गणना $\Sigma _{i}=\sum _{j=1}^{i}x_{j}x_{j}^{T}$ समय लेता है $O(id^{2})$, उलटा करना $d\times d$ मैट्रिक्स में समय लगता है $O(d^{3})$, जबकि बाकी गुणन में समय लगता है $O(d^{2})$, का कुल समय दे रहे हैं $O(id^{2}+d^{3})$. जब वहाँ हैं $n$ प्रत्येक डेटापॉइंट के आने के बाद समाधान की पुन: गणना करने के लिए डेटासेट में कुल अंक $i=1,\ldots ,n$, अनुभवहीन दृष्टिकोण में पूरी जटिलता होगी $O(n^{2}d^{2}+nd^{3})$. ध्यान दें कि मैट्रिक्स को संग्रहीत करते समय $\Sigma _{i}$, फिर इसे प्रत्येक चरण पर अद्यतन करने के लिए केवल जोड़ने की आवश्यकता है $x_{i+1}x_{i+1}^{T}$, जो लेता है $O(d^{2})$ समय, कुल समय को घटाकर $O(nd^{2}+nd^{3})=O(nd^{3})$, किंतु अतिरिक्त संचयन स्थान के साथ $O(d^{2})$ संचय करना $\Sigma _{i}$.

ऑनलाइन शिक्षण: पुनरावर्ती न्यूनतम वर्ग

पुनरावर्ती न्यूनतम वर्ग (आरएलएस) एल्गोरिदम न्यूनतम वर्ग समस्या के लिए एक ऑनलाइन दृष्टिकोण पर विचार करता है। इसे इनिशियलाइज़ करके दिखाया जा सकता है $\textstyle w_{0}=0\in \mathbb {R} ^{d}$ और $\textstyle \Gamma _{0}=I\in \mathbb {R} ^{d\times d}$, पिछले अनुभाग में दी गई रैखिक न्यूनतम वर्ग समस्या का समाधान निम्नलिखित पुनरावृत्ति द्वारा गणना की जा सकती है:

$\Gamma _{i}=\Gamma _{i-1}-{\frac {\Gamma _{i-1}x_{i}x_{i}^{T}\Gamma _{i-1}}{1+x_{i}^{T}\Gamma _{i-1}x_{i}}}$

$w_{i}=w_{i-1}-\Gamma _{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})$

उपरोक्त पुनरावृत्ति एल्गोरिथ्म को इंडक्शन ऑन का उपयोग करके सिद्ध किया जा सकता है $i$. प्रमाण भी यही बताते हैं $\Gamma _{i}=\Sigma _{i}^{-1}$. कोई आरएलएस को अनुकूली फिल्टर के संदर्भ में भी देख सकता है (पुनरावर्ती न्यूनतम वर्ग देखें)।

के लिए जटिलता $n$ इस एल्गोरिदम के चरण हैं $O(nd^{2})$, जो संगत बैच सीखने की जटिलता से अधिक तेज़ परिमाण का एक क्रम है। हर कदम पर संचयन की आवश्यकताएँ $i$ यहां मैट्रिक्स को स्टोर करना है $\Gamma _{i}$, जो स्थिर है $O(d^{2})$. स्थिति के लिए जब $\Sigma _{i}$ उलटा नहीं है, समस्या के नियमित वर्जन पर विचार करें लॉस फंकशन $\sum _{j=1}^{n}(x_{j}^{T}w-y_{j})^{2}+\lambda ||w||_{2}^{2}$. फिर, यह दिखाना आसान है कि वही एल्गोरिदम काम करता है $\Gamma _{0}=(I+\lambda I)^{-1}$, और पुनरावृत्तियाँ देने के लिए आगे बढ़ती हैं $\Gamma _{i}=(\Sigma _{i}+\lambda I)^{-1}$.

स्टोकेस्टिक ग्रेडिएंट डिसेंट

Main article: Stochastic gradient descent

जब यह

$\textstyle w_{i}=w_{i-1}-\Gamma _{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})$ द्वारा प्रतिस्थापित किया जाता है

$\textstyle w_{i}=w_{i-1}-\gamma _{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})=w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{i}\rangle ,y_{i})$ या $\Gamma _{i}\in \mathbb {R} ^{d\times d}$ द्वारा $\gamma _{i}\in \mathbb {R}$, यह स्टोकेस्टिक ग्रेडिएंट डिसेंट एल्गोरिदम बन जाता है। इस स्थिति में, के लिए जटिलता $n$ इस एल्गोरिथम के चरण कम हो जाते हैं $O(nd)$. हर कदम पर संचयन की आवश्यकताएँ $i$ पर स्थिर हैं $O(d)$.

हालाँकि, चरण आकार $\gamma _{i}$ जैसा कि ऊपर बताया गया है, अपेक्षित आपत्तिपूर्ण न्यूनीकरण समस्या को हल करने के लिए सावधानी से चुने जाने की आवश्यकता है। एक क्षयकारी चरण आकार का चयन करके $\gamma _{i}\approx {\frac {1}{\sqrt {i}}},$ कोई औसत पुनरावृत्त के अभिसरण को सिद्ध कर सकता है ${\overline {w}}_{n}={\frac {1}{n}}\sum _{i=1}^{n}w_{i}$. यह सेटिंग स्टोकेस्टिक अनुकूलन का एक विशेष मामला है, जो अनुकूलन में एक प्रसिद्ध समस्या है।

वृद्धिशील स्टोकेस्टिक ग्रेडिएंट वंश

व्यवहार में, कोई डेटा पर अनेक स्टोकेस्टिक ग्रेडिएंट पास (जिन्हें चक्र या युग भी कहा जाता है) निष्पादित कर सकता है। इस प्रकार प्राप्त एल्गोरिदम है वृद्धिशील ग्रेडिएंट विधि कहलाती है और एक पुनरावृत्ति से मेल खाती है

$\textstyle w_{i}=w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{t_{i}}\rangle ,y_{t_{i}})$ स्टोकेस्टिक ग्रेडिएंट विधि के साथ मुख्य अंतर यह है कि यहां एक अनुक्रम है $t_{i}$ यह तय करने के लिए चुना जाता है कि किस प्रशिक्षण बिंदु का दौरा किया जाए $i$-वां चरण. ऐसा क्रम स्टोकेस्टिक या नियतिवादी हो सकता है। फिर पुनरावृत्तियों की संख्या को अंकों की संख्या से अलग कर दिया जाता है (प्रत्येक बिंदु पर एक से अधिक बार विचार किया जा सकता है)। अनुभवजन्य आपत्तिपूर्ण को न्यूनतम प्रदान करने के लिए वृद्धिशील ढाल विधि को दिखाया जा सकता है। अनेक शब्दों के योग से बने वस्तुनिष्ठ कार्यों पर विचार करते समय वृद्धिशील तकनीकें फायदेमंद हो सकती हैं। एक बहुत बड़े डेटासेट से संबंधित एक अनुभवजन्य त्रुटि।

कर्नेल विधियाँ

See also: Kernel method

उपरोक्त एल्गोरिदम को गैर-पैरामीट्रिक मॉडल (या ऐसे मॉडल जहां पैरामीटर एक अनंत आयामी स्थान बनाते हैं) तक विस्तारित करने के लिए कर्नेल का उपयोग किया जा सकता है। संबंधित प्रक्रिया अब वास्तव में ऑनलाइन नहीं होगी और इसमें सभी डेटा बिंदुओं को संग्रहीत करना शामिल होगा, किंतु यह अभी भी ब्रूट फोर्स विधि से तेज़ है। यह चर्चा वर्ग हानि के स्थिति तक ही सीमित है, हालाँकि इसे किसी भी उत्तल हानि तक बढ़ाया जा सकता है। इसे एक आसान प्रेरण द्वारा दिखाया जा सकता है कि अगर $X_{i}$ डेटा मैट्रिक्स है और $w_{i}$ के बाद आउटपुट है $i$ SGD एल्गोरिथ्म के चरण, फिर,

$w_{i}=X_{i}^{T}c_{i}$ कहाँ $\textstyle c_{i}=((c_{i})_{1},(c_{i})_{2},...,(c_{i})_{i})\in \mathbb {R} ^{i}$ और क्रम $c_{i}$ प्रत्यावर्तन को संतुष्ट करता है:

$c_{0}=0$

$(c_{i})_{j}=(c_{i-1})_{j},j=1,2,...,i-1$ और

$(c_{i})_{i}=\gamma _{i}{\Big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x_{i}\rangle {\Big )}$

उस पर यहां ध्यान दें $\langle x_{j},x_{i}\rangle$ केवल मानक कर्नेल चालू है $\mathbb {R} ^{d}$, और भविष्यवक्ता रूप का है

$f_{i}(x)=\langle w_{i-1},x\rangle =\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x\rangle$.

अब, यदि एक सामान्य कर्नेल $K$ इसके अतिरिक्त पेश किया गया है और भविष्यवक्ता को रहने दिया जाए

$f_{i}(x)=\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x)$

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

$(c_{i})_{i}=\gamma _{i}{\Big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x_{i}){\Big )}$

उपरोक्त अभिव्यक्ति को अद्यतन करने के लिए सभी डेटा संग्रहीत करने की आवश्यकता है $c_{i}$. मूल्यांकन करते समय पुनरावृत्ति के लिए कुल समय जटिलता $n$-डेटा बिंदु है $O(n^{2}dk)$, कहाँ $k$ बिंदुओं की एक जोड़ी पर कर्नेल का मूल्यांकन करने की लागत है।इस प्रकार, कर्नेल के उपयोग ने एक सीमित आयामी पैरामीटर स्थान से आंदोलन की अनुमति दी है $\textstyle w_{i}\in \mathbb {R} ^{d}$ एक कर्नेल द्वारा प्रदर्शित संभवतः अनंत आयामी सुविधा के लिए $K$ इसके अतिरिक्त पैरामीटर के स्थान पर रिकर्सन निष्पादित करके $\textstyle c_{i}\in \mathbb {R} ^{i}$, जिसका आयाम प्रशिक्षण डेटासेट के आकार के समान है। सामान्य तौर पर, यह निरूपक प्रमेय का परिणाम है।

ऑनलाइन उत्तल अनुकूलन

ऑनलाइन उत्तल अनुकूलन (OCO) निर्णय लेने के लिए एक सामान्य रूपरेखा है जो कुशल एल्गोरिदम की अनुमति देने के लिए उत्तल अनुकूलन का लाभ उठाती है। बार-बार गेम खेलने की रूपरेखा इस प्रकार है:

के लिए $t=1,2,...,T$

• शिक्षार्थी को इनपुट प्राप्त होता है $x_{t}$
• शिक्षार्थी आउटपुट $w_{t}$ एक निश्चित उत्तल सेट से $S$
• प्रकृति एक उत्तल हानि फ़ंक्शन वापस भेजती है $v_{t}:S\rightarrow \mathbb {R}$.
• शिक्षार्थी को हानि उठानी पड़ती है $v_{t}(w_{t})$ और अपने मॉडल को अपडेट करता है

लक्ष्य अफसोस को कम करना है, या संचयी हानि और सर्वोत्तम निश्चित बिंदु के हानि के बीच अंतर को कम करना है $u\in S$ मसा में। उदाहरण के तौर पर, ऑनलाइन न्यूनतम वर्ग रैखिक प्रतिगमन के स्थिति पर विचार करें। यहां, भार सदिश उत्तल सेट से आते हैं $S=\mathbb {R} ^{d}$, और प्रकृति उत्तल हानि फ़ंक्शन को वापस भेजती है $v_{t}(w)=(\langle w,x_{t}\rangle -y_{t})^{2}$. यहां ध्यान दें कि $y_{t}$ परोक्ष रूप से साथ भेजा गया है $v_{t}$.

हालाँकि, कुछ ऑनलाइन भविष्यवाणी समस्याएं OCO के ढांचे में फिट नहीं हो सकती हैं। उदाहरण के लिए, ऑनलाइन वर्गीकरण में, पूर्वानुमान डोमेन और हानि फ़ंक्शन उत्तल नहीं होते हैं। ऐसे परिदृश्यों में, अवतलीकरण के लिए दो सरल तकनीकों का उपयोग किया जाता है: यादृच्छिकीकरण और सरोगेट लॉस फ़ंक्शन.

कुछ सरल ऑनलाइन उत्तल अनुकूलन एल्गोरिदम हैं:

नेता का अनुसरण करें (एफटीएल)

सीखने का सबसे सरल नियम यह है कि (वर्तमान चरण में) उस परिकल्पना का चयन किया जाए जिसमें पिछले सभी दौरों की तुलना में सबसे कम हानि हो। इस एल्गोरिदम को फॉलो द लीडर कहा जाता है, और इसे बस राउंड दिया जाता है $t$ द्वारा:

$w_{t}=\operatorname {arg\,min} _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)$

इस प्रकार इस पद्धति को एक लालची एल्गोरिदम के रूप में देखा जा सकता है। ऑनलाइन द्विघात अनुकूलन के स्थिति में (जहां हानि फ़ंक्शन है $v_{t}(w)=||w-x_{t}||_{2}^{2}$), कोई पछतावा दिखा सकता है जो बढ़ता है $\log(T)$. हालाँकि, ऑनलाइन रैखिक अनुकूलन जैसे मॉडलों के अन्य महत्वपूर्ण परिवारों के लिए एफटीएल एल्गोरिदम के लिए समान सीमाएं प्राप्त नहीं की जा सकती हैं। ऐसा करने के लिए, कोई नियमितीकरण जोड़कर एफटीएल को संशोधित करता है।

नियमित नेता का अनुसरण करें (एफटीआरएल)

यह एफटीएल का एक प्राकृतिक संशोधन है जिसका उपयोग एफटीएल समाधानों को स्थिर करने और बेहतर अफसोस सीमाएं प्राप्त करने के लिए किया जाता है। एक नियमितीकरण समारोह $R:S\rightarrow \mathbb {R}$ चुना जाता है और सीखने का कार्य चक्र में किया जाता है t निम्नलिखित नुसार:

$w_{t}=\operatorname {arg\,min} _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)+R(w)$

एक विशेष उदाहरण के रूप में, ऑनलाइन रैखिक अनुकूलन के स्थिति पर विचार करें, जहां प्रकृति फॉर्म के हानि कार्यों को वापस भेजती है $v_{t}(w)=\langle w,z_{t}\rangle$. चलो भी $S=\mathbb {R} ^{d}$. मान लीजिए नियमितीकरण समारोह $R(w)={\frac {1}{2\eta }}||w||_{2}^{2}$ किसी धनात्मक संख्या के लिए चुना गया है $\eta$. फिर, कोई यह दिखा सकता है कि पछतावा कम से कम पुनरावृत्ति बन जाता है

$w_{t+1}=-\eta \sum _{i=1}^{t}z_{i}=w_{t}-\eta z_{t}$

ध्यान दें कि इसे इस प्रकार पुनः लिखा जा सकता है $w_{t+1}=w_{t}-\eta \nabla v_{t}(w_{t})$, जो बिल्कुल ऑनलाइन ग्रेडिएंट डिसेंट जैसा दिखता है।

अगर S इसके अतिरिक्त कुछ उत्तल उपसमष्टि है $\mathbb {R} ^{d}$, S को प्रक्षेपित करने की आवश्यकता होगी, जिससे संशोधित अद्यतन नियम प्राप्त होगा

$w_{t+1}=\Pi _{S}(-\eta \sum _{i=1}^{t}z_{i})=\Pi _{S}(\eta \theta _{t+1})$

इस एल्गोरिदम को वेक्टर के रूप में आलसी प्रक्षेपण के रूप में जाना जाता है $\theta _{t+1}$ ग्रेडियेंट जमा करता है। इसे नेस्टरोव के दोहरे औसत एल्गोरिथ्म के रूप में भी जाना जाता है। रैखिक हानि कार्यों और द्विघात नियमितीकरण के इस परिदृश्य में, अफसोस की सीमा है $O({\sqrt {T}})$, और इस प्रकार औसत पछतावा होता है 0 जैसी इच्छा थी।

ऑनलाइन सबग्रेडिएंट डिसेंट (ओएसडी)

See also: Subgradient method

उपरोक्त रैखिक हानि कार्यों के लिए खेदजनक साबित हुआ $v_{t}(w)=\langle w,z_{t}\rangle$. किसी भी उत्तल हानि फ़ंक्शन के लिए एल्गोरिदम को सामान्य बनाने के लिए, उपग्रेडिएंट $\partial v_{t}(w_{t})$ का $v_{t}$ के रैखिक सन्निकटन के रूप में उपयोग किया जाता है $v_{t}$ पास में $w_{t}$, ऑनलाइन सबग्रेडिएंट डिसेंट एल्गोरिदम की ओर अग्रसर:

प्रारंभिक पैरामीटर $\eta ,w_{1}=0$ के लिए $t=1,2,...,T$

• प्रयोग करके भविष्यवाणी करें $w_{t}$, पाना $f_{t}$ प्रकृति से.
• चुनना $z_{t}\in \partial v_{t}(w_{t})$ * अगर $S=\mathbb {R} ^{d}$, के रूप में अद्यतन करें $w_{t+1}=w_{t}-\eta z_{t}$
• अगर $S\subset \mathbb {R} ^{d}$, संचयी ग्रेडिएंट्स को प्रोजेक्ट करें $S$ अर्थात। $w_{t+1}=\Pi _{S}(\eta \theta _{t+1}),\theta _{t+1}=\theta _{t}+z_{t}$ प्राप्त करने के लिए कोई ओएसडी एल्गोरिदम का उपयोग कर सकता है $O({\sqrt {T}})$ वर्गीकरण के लिए सपोर्ट वेक्टर मशीन|एसवीएम के ऑनलाइन वर्जन के लिए अफसोस की सीमा, जो काज हानि का उपयोग करती है$v_{t}(w)=\max\{0,1-y_{t}(w\cdot x_{t})\}$

अन्य एल्गोरिदम

जैसा कि ऊपर वर्णित है, द्विघात रूप से नियमित किए गए एफटीआरएल एल्गोरिदम आलसी प्रक्षेपित ग्रेडिएंट एल्गोरिदम की ओर ले जाते हैं। मनमाने ढंग से उत्तल कार्यों और नियमितकर्ताओं के लिए उपरोक्त का उपयोग करने के लिए, कोई ऑनलाइन दर्पण वंश का उपयोग करता है। रैखिक हानि कार्यों के लिए पश्चदृष्टि में इष्टतम नियमितीकरण प्राप्त किया जा सकता है, यह AdaGrad एल्गोरिथ्म की ओर ले जाता है। यूक्लिडियन नियमितीकरण के लिए, कोई भी पछतावा दिखा सकता है $O({\sqrt {T}})$, जिसे और बेहतर बनाया जा सकता है $O(\log T)$ दृढ़ता से उत्तल और क्स्प-अवतल हानि कार्यों के लिए।

निरंतर सीखना

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

ऑनलाइन शिक्षण की व्याख्या

ऑनलाइन शिक्षण के प्रतिमान की शिक्षण मॉडल की पसंद के आधार पर अलग-अलग व्याख्याएं हैं, जिनमें से प्रत्येक के कार्यों के अनुक्रम की पूर्वानुमानित गुणवत्ता के बारे में अलग-अलग निहितार्थ हैं। $f_{1},f_{2},\ldots ,f_{n}$. इस चर्चा के लिए प्रोटोटाइपिकल स्टोचैस्टिक ग्रेडिएंट डिसेंट एल्गोरिदम का उपयोग किया जाता है। जैसा कि ऊपर उल्लेख किया गया है, इसकी पुनरावृत्ति द्वारा दी गई है

$\textstyle w_{t}=w_{t-1}-\gamma _{t}\nabla V(\langle w_{t-1},x_{t}\rangle ,y_{t})$

पहली व्याख्या अपेक्षित आपत्तिपूर्ण को कम करने की समस्या के लिए प्रयुक्त स्टोकेस्टिक ग्रेडिएंट डिसेंट पद्धति पर विचार करती है $I[w]$ ऊपर परिभाषित. दरअसल, डेटा की अनंत धारा के स्थिति में, उदाहरणों के बाद से $(x_{1},y_{1}),(x_{2},y_{2}),\ldots$ माना जाता है कि i.i.d खींचा गया है वितरण से $p(x,y)$, के ग्रेडियेंट का क्रम $V(\cdot ,\cdot )$ उपरोक्त पुनरावृत्ति में एक आई.आई.डी. है अपेक्षित आपत्तिपूर्ण की प्रवणता के स्टोकेस्टिक अनुमान का नमूना $I[w]$ और इसलिए कोई विचलन को सीमित करने के लिए स्टोकेस्टिक ग्रेडिएंट डीसेंट विधि के लिए जटिलता परिणाम प्रयुक्त कर सकता है $I[w_{t}]-I[w^{\ast }]$, कहाँ $w^{\ast }$ का मिनिमाइज़र है $I[w]$. यह व्याख्या एक सीमित प्रशिक्षण सेट के स्थिति में भी मान्य है; हालाँकि डेटा के माध्यम से एकाधिक पास के साथ ग्रेडिएंट अब स्वतंत्र नहीं हैं, फिर भी विशेष मामलों में जटिलता परिणाम प्राप्त किए जा सकते हैं।

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

$I_{n}[w]={\frac {1}{n}}\sum _{i=1}^{n}V(\langle w,x_{i}\rangle ,y_{i})\ .$

के ढ़ाल के बाद से $V(\cdot ,\cdot )$ वृद्धिशील ग्रेडिएंट डिसेंट पुनरावृत्तियों में ग्रेडिएंट का स्टोकेस्टिक अनुमान भी होता है $I_{n}[w]$, यह व्याख्या स्टोकेस्टिक ग्रेडिएंट डिसेंट पद्धति से भी संबंधित है, किंतु अपेक्षित आपत्तिपूर्ण के विपरीत अनुभवजन्य आपत्तिपूर्ण को कम करने के लिए प्रयुक्त की जाती है। चूंकि यह व्याख्या अनुभवजन्य आपत्तिपूर्ण की चिंता करती है न कि अपेक्षित आपत्तिपूर्ण की, इसलिए डेटा के माध्यम से अनेक बार गुजरने की आसानी से अनुमति दी जाती है और वास्तव में विचलन पर कड़ी सीमाएं लगती हैं। $I_{n}[w_{t}]-I_{n}[w_{n}^{\ast }]$, कहाँ $w_{n}^{\ast }$ का मिनिमाइज़र है $I_{n}[w]$.

कार्यान्वयन

• वोवपल वैबिट: ओपन-सोर्स फास्ट आउट-ऑफ-कोर ऑनलाइन लर्निंग सिस्टम जो अनेक मशीन लर्निंग कटौती, महत्व भार और विभिन्न हानि कार्यों और अनुकूलन एल्गोरिदम के चयन का समर्थन करने के लिए उल्लेखनीय है। यह प्रशिक्षण डेटा की मात्रा से स्वतंत्र सुविधाओं के सेट के आकार को सीमित करने के लिए फ़ीचर हैशिंग का उपयोग करता है।
• स्किकिट-लर्न: एल्गोरिदम के आउट-ऑफ-कोर कार्यान्वयन प्रदान करता है
  • वर्गीकरण: परसेप्ट्रॉन, स्टोकेस्टिक ग्रेडिएंट डिसेंट, नाइव बेयस क्लासिफायरियर
  • प्रतिगमन: एसजीडी प्रतिगामी, निष्क्रिय आक्रामक प्रतिगामी।
  • क्लस्टरिंग: K- का अर्थ है क्लस्टरिंग |मिनी-बैच के-मीन्स।
  • फ़ीचर निष्कर्षण: शब्दकोश सीखना | मिनी-बैच शब्दकोश सीखना, प्रमुख घटक विश्लेषण।

यह भी देखें

सीखने के प्रतिमान

• वृद्धिशील शिक्षा
• आलसी सीखना
• ऑफ़लाइन शिक्षण, विपरीत मॉडल
• सुदृढीकरण सीखना
• बहु-सशस्त्र डाकू
• पर्यवेक्षित अध्ययन

सामान्य एल्गोरिदम

• ऑनलाइन एल्गोरिदम
• ऑनलाइन अनुकूलन
• स्ट्रीमिंग एल्गोरिदम
• स्टोकेस्टिक ग्रेडिएंट डिसेंट

सीखने के मॉडल

• अनुकूली अनुनाद सिद्धांत
• पदानुक्रमित लौकिक स्मृति
• k-निकटतम पड़ोसी एल्गोरिथ्म
• वेक्टर परिमाणीकरण सीखना
• परसेप्ट्रॉन

बाहरी संबंध

• 6.883: Online Methods in Machine Learning: Theory and Applications. Alexander Rakhlin. MIT