التعلم الآلي عبر الإنترنت

يُستخدم مثال المربعات الصغرى الخطية البسيط لشرح مجموعة متنوعة من الأفكار في مجال التعلم الإلكتروني. هذه الأفكار عامة بما يكفي لتطبيقها على سياقات أخرى، على سبيل المثال، مع دوال الخسارة المحدبة الأخرى.

ضع في اعتبارك بيئة التعلم الخاضع للإشراف مع${\displaystyle f}$كونها دالة خطية يجب تعلمها: $${\displaystyle f(x_{j})=\langle w,x_{j}\rangle =w\cdot x_{j}}$$ أين${\displaystyle x_{j}\in \mathbb {R} ^{d}}$هو متجه من المدخلات (نقاط البيانات) و${\displaystyle w\in \mathbb {R} ^{d}}$هو متجه مرشح خطي. الهدف هو حساب متجه المرشح.${\displaystyle w}$ولتحقيق هذه الغاية، دالة خسارة مربعة $${\displaystyle V(f(x_{j}),y_{j})=(f(x_{j})-y_{j})^{2}=(\langle w,x_{j}\rangle -y_{j})^{2}}$$ تُستخدم لحساب المتجه${\displaystyle w}$ذلك يقلل من الخسارة التجريبية $${\displaystyle I_{n[w]=\sum _{j=1}^{n}V(\langle w,x_{j}\rangle ,y_{j})=\sum _{j=1}^{n}(x_{j}^{\mathsf {T}}w-y_{j})^{2}}$$ أين $${\displaystyle y_{j}\in \mathbb {R} .}$$

يترك${\displaystyle X}$كن${\displaystyle i\times d}$مصفوفة البيانات و${\displaystyle y\in \mathbb {R} ^{i}}$يمثل متجه العمود للقيم المستهدفة بعد وصول أول${\displaystyle i}$نقاط البيانات. بافتراض أن مصفوفة التغاير${\displaystyle \Sigma _{i}=X^{\mathsf {T}}X}$إذا كانت قابلة للعكس (وإلا فمن الأفضل اتباع أسلوب مماثل مع تنظيم تيخونوف)، فهذا هو الحل الأمثل${\displaystyle f^{*}(x)=\langle w^{*},x\rangle }$تُعطى معادلة مسألة المربعات الصغرى الخطية بالصيغة التالية: $${\displaystyle w^{*}=(X^{\mathsf {T}}X)^{-1}X^{\mathsf {T}}y=\Sigma _{i}^{-1}\sum _{j=1}^{i}x_{j}y_{j}.}$$

والآن، حساب مصفوفة التغاير${\displaystyle \Sigma _{i}=\sum _{j=1}^{i}x_{j}x_{j}^{\mathsf {T}}}$يستغرق الأمر وقتاً${\displaystyle O(id^{2})}$، عكس${\displaystyle d\times d}$تستغرق المصفوفة وقتًا${\displaystyle O(d^{3})}$بينما تستغرق بقية عملية الضرب وقتًا${\displaystyle O(d^{2})}$، مما يعطي إجمالي وقت قدره${\displaystyle O(id^{2}+d^{3})}$عندما يكون هناك${\displaystyle n}$إجمالي النقاط في مجموعة البيانات، لإعادة حساب الحل بعد وصول كل نقطة بيانات${\displaystyle i=1,\ldots ,n}$سيكون للنهج الساذج تعقيد كامل${\displaystyle O(n^{2}d^{2}+nd^{3})}$لاحظ أنه عند تخزين المصفوفة${\displaystyle \Sigma _{i}}$ثم تحديثه في كل خطوة لا يتطلب سوى إضافة${\displaystyle x_{i+1}x_{i+1}^{\mathsf {T}}}$، الأمر الذي يستغرق${\displaystyle O(d^{2})}$الوقت، مما يقلل الوقت الإجمالي إلى${\displaystyle O(nd^{2}+nd^{3})=O(nd^{3})}$ولكن مع مساحة تخزين إضافية تبلغ${\displaystyle O(d^{2})}$للتخزين${\displaystyle \Sigma _{i}}$[ ^{2 ]​}

تعتمد خوارزمية المربعات الصغرى المتكررة (RLS) على أسلوب فوري لحل مشكلة المربعات الصغرى. ويمكن إثبات ذلك من خلال التهيئة${\displaystyle \textstyle w_{0}=0\in \mathbb {R} ^{d}}$و${\displaystyle \textstyle \Gamma _{0}=I\in \mathbb {R} ^{d\times d}}$يمكن حساب حل مسألة المربعات الصغرى الخطية الواردة في القسم السابق من خلال التكرار التالي: $${\displaystyle \Gamma _{i}=\Gamma _{i-1}-{\frac {\Gamma _{i-1}x_{i}x_{i}^{\mathsf {T}}\Gamma _{i-1}}{1+x_{i}^{\mathsf {T}}\Gamma _{i-1}x_{i}}}}$$$${\displaystyle w_{i}=w_{i-1}-\Gamma _{i}x_{i}\left(x_{i}^{\mathsf {T}}w_{i-1}-y_{i}\right)}$$ يمكن إثبات خوارزمية التكرار المذكورة أعلاه باستخدام الاستقراء الرياضي.${\displaystyle i}$[ ^{3 ] يُظهر} البرهان أيضًا أن${\displaystyle \Gamma _{i}=\Sigma _{i}^{-1}}$يمكن للمرء أن ينظر إلى RLS أيضًا في سياق المرشحات التكيفية (انظر RLS ).

التعقيد لـ${\displaystyle n}$خطوات هذه الخوارزمية هي${\displaystyle O(nd^{2})}$وهو أسرع بعشر مرات من تعقيد التعلم الدفعي المقابل. متطلبات التخزين في كل خطوة${\displaystyle i}$هنا يتم تخزين المصفوفة${\displaystyle \Gamma _{i}}$، وهو ثابت عند${\displaystyle O(d^{2})}$في حالة عندما${\displaystyle \Sigma _{i}}$بما أنها غير قابلة للعكس، فلننظر في النسخة المنتظمة من دالة خسارة المسألة${\displaystyle \sum _{j=1}^{n}\left(x_{j}^{\mathsf {T}}w-y_{j}\right)^{2}+\lambda \left\|w\right\|_{2}^{2}}$بعد ذلك، من السهل إثبات أن الخوارزمية نفسها تعمل مع${\displaystyle \Gamma _{0}=(I+\lambda I)^{-1}}$وتستمر التكرارات في إعطاء${\displaystyle \Gamma _{i}=(\Sigma _{i}+\lambda I)^{-1}}$[ ^{2 ]​}

عندما هذا $${\displaystyle w_{i}=w_{i-1}-\Gamma _{i}x_{i}\left(x_{i}^{\mathsf {T}}w_{i-1}-y_{i}\right)}$$ يتم استبدالها بـ $${\displaystyle w_{i}=w_{i-1}-\gamma _{i}x_{i}\left(x_{i}^{\mathsf {T}}w_{i-1}-y_{i}\right)=w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{i}\rangle ,y_{i})}$$ أو${\displaystyle \Gamma _{i}\in \mathbb {R} ^{d\times d}}$بواسطة${\displaystyle \gamma _{i}\in \mathbb {R} }$، يصبح هذا خوارزمية التدرج العشوائي. في هذه الحالة، يكون التعقيد لـ${\displaystyle n}$تتلخص خطوات هذه الخوارزمية في:${\displaystyle O(nd)}$متطلبات التخزين في كل خطوة${\displaystyle i}$ثابتة عند${\displaystyle O(d)}$.

ومع ذلك، فإن حجم الخطوة${\displaystyle \gamma _{i}}$يجب اختيار حجم الخطوة بعناية لحل مشكلة تقليل المخاطر المتوقعة، كما هو موضح أعلاه. وذلك باختيار حجم خطوة متناقص.${\displaystyle \gamma _{i}\approx {\frac {1}{\sqrt {i}}},}$يمكن إثبات تقارب متوسط ​​التكرار${\textstyle {\overline {w}}_{n}={\frac {1}{n}}\sum _{i=1}^{n}w_{i}}$هذا الإعداد هو حالة خاصة من التحسين العشوائي ، وهي مشكلة معروفة في مجال التحسين. ^{[ 2 ]}

عمليًا، يمكن إجراء عدة دورات أو حقب من التدرج العشوائي على البيانات. تُسمى الخوارزمية الناتجة طريقة التدرج التزايدي، وهي تُقابل تكرارًا. $${\displaystyle w_{i}=w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{t_{i}}\rangle ,y_{t_{i}})}$$ الفرق الرئيسي مع طريقة التدرج العشوائي هو أن المتتالية هنا${\displaystyle t_{i}}$يتم اختيار نقطة التدريب التي سيتم زيارتها في${\displaystyle i}$الخطوة رقم n. يمكن أن يكون هذا التسلسل عشوائيًا أو حتميًا. يتم حينها فصل عدد التكرارات عن عدد النقاط (يمكن اعتبار كل نقطة أكثر من مرة). يمكن إثبات أن طريقة التدرج التزايدي توفر قيمة دنيا للمخاطرة التجريبية. ^{[ 4 ]} قد تكون التقنيات التزايدية مفيدة عند النظر في دوال الهدف المكونة من مجموع العديد من الحدود، مثل الخطأ التجريبي المقابل لمجموعة بيانات كبيرة جدًا. ^{[ 2 ]}

يمكن استخدام النوى لتوسيع الخوارزميات المذكورة أعلاه لتشمل النماذج غير البارامترية (أو النماذج التي تشكل فيها المعلمات فضاءً لا نهائي الأبعاد). لن يكون الإجراء المقابل متصلاً بالإنترنت بشكل كامل، بل سيتضمن تخزين جميع نقاط البيانات، ولكنه سيظل أسرع من طريقة البحث الشامل. يقتصر هذا النقاش على حالة الخسارة التربيعية، مع إمكانية توسيعه ليشمل أي خسارة محدبة. يمكن إثبات ذلك باستقراء بسيط ^{[ 2 ]} إذا${\displaystyle X_{i}}$هي مصفوفة البيانات و${\displaystyle w_{i}}$هذا هو الناتج بعد${\displaystyle i}$ثم خطوات خوارزمية التدرج العشوائي (SGD) ، $${\displaystyle w_{i}=X_{i}^{\mathsf {T}}c_{i}}$$ أين${\displaystyle c_{i}=((c_{i})_{1},(c_{i})_{2},...,(c_{i})_{i})\in \mathbb {R} ^{i}}$والتسلسل${\displaystyle c_{i}}$يفي بالتكرار: $${\displaystyle c_{0}=0}$$$${\displaystyle (c_{i})_{j}=(c_{i-1})_{j},j=1,2,...,i-1}$$و $${\displaystyle (c_{i})_{i}=\gamma _{i}{\Big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x_{i}\rangle {\Big )}}$$ لاحظ ذلك هنا${\displaystyle \langle x_{j},x_{i}\rangle }$هو مجرد النواة القياسية على${\displaystyle \mathbb {R} ^{d}}$ويكون المتنبئ على الشكل التالي: $${\displaystyle f_{i}(x)=\langle w_{i-1},x\rangle =\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x\rangle .}$$

الآن، إذا كانت النواة العامة${\displaystyle K}$يتم إدخالها بدلاً من ذلك، ولنفترض أن المتنبئ هو $${\displaystyle f_{i}(x)=\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x)}$$ ثم سيُظهر البرهان نفسه أيضًا أن المُتنبئ الذي يُقلل من خسارة المربعات الصغرى يُمكن الحصول عليه عن طريق تغيير التكرار أعلاه إلى $${\displaystyle (c_{i})_{i}=\gamma _{i}{\Big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x_{i}){\Big )}}$$ يتطلب التعبير أعلاه تخزين جميع البيانات اللازمة للتحديث${\displaystyle c_{i}}$. إجمالي التعقيد الزمني للاستدعاء الذاتي عند التقييم لـ${\displaystyle n}$نقطة البيانات رقم -th هي${\displaystyle O(n^{2}dk)}$، أين${\displaystyle k}$^{[ 2 ]} تمثل تكلفة تقييم النواة على زوج واحد من النقاط. وبالتالي، فقد سمح استخدام النواة بالانتقال من فضاء معلمات ذي أبعاد محدودة${\displaystyle \textstyle w_{i}\in \mathbb {R} ^{d}}$إلى ميزة ذات أبعاد لا نهائية محتملة ممثلة بنواة${\displaystyle K}$بدلاً من ذلك، يتم إجراء الاستدعاء الذاتي على فضاء المعاملات.${\displaystyle \textstyle c_{i}\in \mathbb {R} ^{i}}$، والتي يكون بُعدها مساوياً لحجم مجموعة بيانات التدريب. وبشكل عام، هذه نتيجة لنظرية المُمَثِّل . ^{[ 2 ]}

يُعدّ التحسين المحدب عبر الإنترنت (OCO) ^{[ 5 ]} إطارًا عامًا لاتخاذ القرارات، يستفيد من التحسين المحدب لتمكين خوارزميات فعّالة. ويتمثل هذا الإطار في تكرار لعب اللعبة على النحو التالي:

ل${\displaystyle t=1,2,...,T}$

• يتلقى المتعلم المدخلات${\displaystyle x_{t}}$
• مخرجات المتعلم${\displaystyle w_{t}}$من مجموعة محدبة ثابتة${\displaystyle S}$
• ترد الطبيعة بدالة خسارة محدبة${\displaystyle v_{t}:S\rightarrow \mathbb {R} }$.
• المتعلم يعاني من الخسارة${\displaystyle v_{t}(w_{t})}$ويقوم بتحديث نموذجه

الهدف هو تقليل الندم ، أو الفرق بين الخسارة التراكمية وفقدان أفضل نقطة ثابتة.${\displaystyle u\in S}$بالنظر إلى الماضي. على سبيل المثال، لنأخذ حالة الانحدار الخطي للمربعات الصغرى عبر الإنترنت. هنا، تأتي متجهات الأوزان من المجموعة المحدبة.${\displaystyle S=\mathbb {R} ^{d}}$وتعيد الطبيعة دالة الخسارة المحدبة.${\displaystyle v_{t}(w)=(\langle w,x_{t}\rangle -y_{t})^{2}}$لاحظ هنا أن${\displaystyle y_{t}}$يتم إرسالها ضمنيًا مع${\displaystyle v_{t}}$.

مع ذلك، لا تتناسب بعض مسائل التنبؤ عبر الإنترنت مع إطار عمل OCO. على سبيل المثال، في التصنيف عبر الإنترنت، لا يكون مجال التنبؤ ودوال الخسارة محدبة. في مثل هذه الحالات، تُستخدم تقنيتان بسيطتان للتحدب : العشوائية ودوال الخسارة البديلة ^{[ 6 ]} .

بعض خوارزميات التحسين المحدب البسيطة عبر الإنترنت هي:

أثبتت النتائج المذكورة أعلاه حدًا للندم بالنسبة لدوال الخسارة الخطية${\displaystyle v_{t}(w)=\langle w,z_{t}\rangle }$لتعميم الخوارزمية على أي دالة خسارة محدبة، يتم استخدام التدرج الفرعي${\displaystyle \partial v_{t}(w_{t})}$ل${\displaystyle v_{t}}$يُستخدم كتقريب خطي لـ${\displaystyle v_{t}}$قريب${\displaystyle w_{t}}$مما أدى إلى خوارزمية التدرج الفرعي عبر الإنترنت:

المعلمة الأولية${\displaystyle \eta ,w_{1}=0}$

ل${\displaystyle t=1,2,...,T}$

• التنبؤ باستخدام${\displaystyle w_{t}}$، يستلم${\displaystyle f_{t}}$من الطبيعة.
• يختار${\displaystyle z_{t}\in \partial v_{t}(w_{t})}$
• لو${\displaystyle S=\mathbb {R} ^{d}}$، تحديث حسب${\displaystyle w_{t+1}=w_{t}-\eta z_{t}}$
• لو${\displaystyle S\subset \mathbb {R} ^{d}}$إسقاط التدرجات التراكمية على${\displaystyle S}$أي${\displaystyle w_{t+1}=\Pi _{S}(\eta \theta _{t+1}),\theta _{t+1}=\theta _{t}+z_{t}}$

يمكن استخدام خوارزمية OSD لاستخلاص${\displaystyle O({\sqrt {T}})}$حدود الندم للنسخة الإلكترونية من خوارزمية SVM للتصنيف، والتي تستخدم دالة خسارة المفصلة.${\displaystyle v_{t}(w)=\max\{0,1-y_{t}(w\cdot x_{t})\}}$

تؤدي خوارزميات FTRL المُنتظمة تربيعيًا إلى خوارزميات التدرج المُسقطة على كسل كما هو موضح أعلاه. لاستخدام ما سبق مع الدوال المحدبة والمنظمات العشوائية، يُستخدم الهبوط المرآوي عبر الإنترنت . يمكن اشتقاق التنظيم الأمثل بأثر رجعي لدوال الخسارة الخطية، مما يؤدي إلى خوارزمية AdaGrad . بالنسبة للتنظيم الإقليدي، يمكن إثبات حد الندم.${\displaystyle O({\sqrt {T}})}$والتي يمكن تحسينها أكثر لتصبح${\displaystyle O(\log T)}$بالنسبة لدوال الخسارة المحدبة بقوة والمقعرة أسياً.