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

Not to be confused with online and offline.

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

परिचय

पर्यवेक्षित शिक्षण की सेटिंग में, का एक कार्य $f:X\to Y$ सीखना है, कहाँ $X$ इनपुट के स्थान के रूप में सोचा जाता है और $Y$ आउटपुट के एक स्थान के रूप में, जो संयुक्त संभाव्यता वितरण से निकाले गए उदाहरणों पर अच्छी तरह से भविष्यवाणी करता है $p(x,y)$ पर $X\times 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: Linear least squares (mathematics)

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

बैच सीखना

पर्यवेक्षित शिक्षण की सेटिंग पर विचार करें $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