تنظيم متعدد الأبعاد

التنظيم المتعدد الأبعاد هو نوع من أنواع التنظيم ، وهو مجموعة من التقنيات التي تقلل من فرط التخصيص وتضمن أن تكون المسألة محددة جيدًا من خلال معاقبة الحلول المعقدة. على وجه الخصوص، يُوسّع التنظيم المتعدد الأبعاد تقنية تنظيم تيخونوف كما تُطبق على فضاءات هيلبرت ذات النواة المُستنسخة (RKHSs). في ظل تنظيم تيخونوف القياسي على فضاءات هيلبرت ذات النواة المُستنسخة، تحاول خوارزمية التعلم تعلم دالة.${\displaystyle f}$من بين فضاء الفرضيات للدوال${\displaystyle {\mathcal {H}}}$فضاء الفرضيات هو فضاء هيلبرت ذو النواة المقلوبة (RKHS)، مما يعني أنه مرتبط بنواة .${\displaystyle K}$وبالتالي كل دالة مرشحة${\displaystyle f}$له معيار${\displaystyle \left\|f\right\|_{K}}$يمثل هذا المعامل تعقيد الدالة المرشحة في فضاء الفرضيات. وعندما تنظر الخوارزمية في دالة مرشحة، فإنها تأخذ معيارها في الاعتبار لمعاقبة الدوال المعقدة.

بصورة رسمية، بالنظر إلى مجموعة من بيانات التدريب المصنفة${\displaystyle (x_{1},y_{1}),\ldots ,(x_{\ell },y_{\ell })}$مع${\displaystyle x_{i}\in X,y_{i}\in Y}$ودالة الخسارة${\displaystyle V}$ستحاول خوارزمية التعلم التي تستخدم تنظيم تيكهونوف حل التعبير

${\displaystyle {\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }V(f(x_{i}),y_{i})+\gamma \left\|f\right\|_{K}^{2}}$

أين${\displaystyle \gamma }$هو مُعامل فائق يتحكم في مدى تفضيل الخوارزمية للوظائف الأبسط على الوظائف التي تتناسب مع البيانات بشكل أفضل.

يُضيف تنظيم التشعب حدًا تنظيميًا ثانيًا، وهو المنظم الجوهري ، إلى المنظم المحيطي المستخدم في تنظيم تيخونوف القياسي. وبافتراض التشعب في التعلم الآلي، فإن البيانات المعنية لا تأتي من فضاء الإدخال بأكمله.${\displaystyle X}$ولكن بدلاً من ذلك من متعدد شعب غير خطي${\displaystyle M\subset X}$تُستخدم هندسة هذا الفضاء المتشعب، أي الفضاء الجوهري، لتحديد معيار التنظيم. ^{[ 1 ]}

توجد العديد من الخيارات الممكنة للمنظم الداخلي${\displaystyle \left\|f\right\|_{I}}$تتضمن العديد من الخيارات الطبيعية التدرج على المتشعب${\displaystyle \nabla _{M}}$وهذا يوفر مقياسًا لمدى سلاسة الدالة المستهدفة. يجب أن تتغير الدالة السلسة ببطء حيث تكون بيانات الإدخال كثيفة؛ أي في التدرج.${\displaystyle \nabla _{M}f(x)}$ينبغي أن تكون صغيرة حيث كثافة الاحتمال الهامشي${\displaystyle {\mathcal {P}}_{X}(x)}$، كثافة الاحتمال لظهور نقطة بيانات مسحوبة عشوائياً عند${\displaystyle x}$، كبيرة. وهذا يعطي خيارًا مناسبًا للمنظم الداخلي:

${\displaystyle \left\|f\right\|_{I}^{2}=\int _{x\in M}\left\|\nabla _{M}f(x)\right\|^{2}\,d{\mathcal {P}}_{X}(x)}$

عمليًا، لا يمكن حساب هذا المعيار بشكل مباشر لأن التوزيع الهامشي${\displaystyle {\mathcal {P}}_{X}}$غير معروف، ولكن يمكن تقديره من البيانات المتوفرة.

عندما تُفسَّر المسافات بين نقاط الإدخال على أنها رسم بياني، فإن مصفوفة لابلاس لهذا الرسم البياني يمكن أن تساعد في تقدير التوزيع الهامشي . لنفترض أن بيانات الإدخال تتضمن${\displaystyle \ell }$أمثلة مصنفة (أزواج من المدخلات)${\displaystyle x}$وملصق${\displaystyle y}$) و${\displaystyle u}$أمثلة غير مصنفة (مدخلات بدون تصنيفات مرتبطة بها). تعريف${\displaystyle W}$أن تكون مصفوفة لأوزان الحواف للرسم البياني، حيث${\displaystyle W_{ij}}$التشابه مبني على قياس المسافة بين نقاط البيانات${\displaystyle x_{i}}$و${\displaystyle x_{j}}$(بحيث يشير القرب إلى ارتفاع)${\displaystyle W_{ij}}$). يُعرِّف${\displaystyle D}$أن تكون مصفوفة قطرية مع${\displaystyle D_{ii}=\sum _{j=1}^{\ell +u}W_{ij}}$و${\displaystyle L}$أن تكون مصفوفة لابلاس${\displaystyle D-W}$ثم، مع عدد نقاط البيانات${\displaystyle \ell +u}$يزداد،${\displaystyle L}$يتقارب مع مؤثر لابلاس-بيلترامي${\displaystyle \Delta _{M}}$، وهو تباعد التدرج${\displaystyle \nabla _{M}}$[ ^{2 ] [ 3 ]} ثم، ^إذا${\displaystyle \mathbf {f} }$هو متجه لقيم${\displaystyle f}$في البيانات،${\displaystyle \mathbf {f} =[f(x_{1}),\ldots ,f(x_{l+u})]^{\mathrm {T} }}$، ويمكن تقدير المعيار الجوهري:

${\displaystyle \left\|f\right\|_{I}^{2}={\frac {1}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f} }$

مع ازدياد عدد نقاط البيانات${\displaystyle \ell +u}$يزداد هذا التعريف التجريبي لـ${\displaystyle \left\|f\right\|_{I}^{2}}$يتقارب مع التعريف عندما${\displaystyle {\mathcal {P}}_{X}}$معروف. ^{[ 1 ]}

باستخدام الأوزان${\displaystyle \gamma _{A}}$و${\displaystyle \gamma _{I}}$بالنسبة للمنظمات المحيطة والداخلية، يصبح التعبير النهائي المطلوب حله كما يلي:

${\displaystyle {\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }V(f(x_{i}),y_{i})+\gamma _{A}\left\|f\right\|_{K}^{2}+{\frac {\gamma _{I}}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f} }$

كما هو الحال مع طرق النواة الأخرى ،${\displaystyle {\mathcal {H}}}$قد يكون الفضاء لانهائي الأبعاد، لذا إذا تعذر حل تعبير التنظيم بشكل صريح، فمن المستحيل البحث في الفضاء بأكمله عن حل. بدلاً من ذلك، تُظهر نظرية التمثيل أنه في ظل شروط معينة على اختيار المعيار، يمكن${\displaystyle \left\|f\right\|_{I}}$الحل الأمثل${\displaystyle f^{*}}$يجب أن يكون مزيجًا خطيًا من النواة متمركزًا عند كل نقطة من نقاط الإدخال: لبعض الأوزان${\displaystyle \alpha _{i}}$،

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell +u}\alpha _{i}K(x_{i},x)}$

باستخدام هذه النتيجة، يمكن البحث عن الحل الأمثل${\displaystyle f^{*}}$من خلال البحث في الفضاء ذي الأبعاد المحدودة المحدد بالخيارات الممكنة لـ${\displaystyle \alpha _{i}}$[ ^{1 ]​}

تتجاوز فكرة لابلاس الرسم البياني استخدام الجيران لتقدير لابلاس. تشبه هذه الطريقة طرق المتوسطات المحلية ، المعروفة بضعف أدائها في المسائل عالية الأبعاد. في الواقع، من المعروف أن لابلاس الرسم البياني يعاني من لعنة الأبعاد . ^{[ 2 ]} لحسن الحظ، من الممكن الاستفادة من السلاسة المتوقعة للدالة لتقديرها بفضل التحليل الوظيفي الأكثر تقدمًا. تتكون هذه الطريقة من تقدير مؤثر لابلاس باستخدام مشتقات قراءة النواة.${\displaystyle \partial _{1,j}K(x_{i},x)}$أين${\displaystyle \partial _{1,j}}$تشير إلى المشتقات الجزئية وفقًا للإحداثي j للمتغير الأول. ^{[ 4 ]} يتمثل هذا النهج الثاني لمعيار لابلاس في ربطه بالطرق غير الشبكية ، وهو ما يتناقض مع طريقة الفروق المحدودة في المعادلات التفاضلية الجزئية.

المربعات الصغرى المنتظمة (RLS) هي عائلة من خوارزميات الانحدار : وهي خوارزميات تتنبأ بقيمة${\displaystyle y=f(x)}$وذلك لمساهماتها${\displaystyle x}$يهدف هذا الأسلوب إلى جعل القيم المتوقعة قريبة من التصنيفات الحقيقية للبيانات. وعلى وجه الخصوص، صُممت طريقة المربعات الصغرى المتكررة (RLS) لتقليل متوسط ​​مربع الخطأ بين القيم المتوقعة والتصنيفات الحقيقية، مع مراعاة التنظيم. يُعد انحدار ريدج أحد أشكال RLS؛ وبشكل عام، فإن RLS هي نفسها انحدار ريدج مُدمجة مع طريقة النواة . وتنتج مسألة RLS من اختيار دالة الخسارة.${\displaystyle V}$في تنظيم تيخونوف ليكون متوسط ​​مربع الخطأ:

${\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }(f(x_{i})-y_{i})^{2}+\gamma \left\|f\right\|_{K}^{2}}$

بفضل نظرية التمثيل ، يمكن كتابة الحل كمجموع مرجح للنواة المحسوبة عند نقاط البيانات:

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell }\alpha _{i}^{*}K(x_{i},x)}$

وحل لـ${\displaystyle \alpha ^{*}}$أعطِ:

${\displaystyle \alpha ^{*}=(K+\gamma \ell I)^{-1}Y}$

أين${\displaystyle K}$تُعرَّف بأنها مصفوفة النواة، مع${\displaystyle K_{ij}=K(x_{i},x_{j})}$، و${\displaystyle Y}$هو متجه تسميات البيانات.

إضافة حد لابلاس لتنظيم المتشعب يعطينا عبارة لابلاس RLS:

${\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }(f(x_{i})-y_{i})^{2}+\gamma _{A}\left\|f\right\|_{K}^{2}+{\frac {\gamma _{I}}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f} }$

تُعطي نظرية التمثيل لتنظيم المتشعب مرة أخرى

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell +u}\alpha _{i}^{*}K(x_{i},x)}$

وهذا ينتج عنه تعبير للمتجه${\displaystyle \alpha ^{*}}$تأجير${\displaystyle K}$لتكن مصفوفة النواة كما هو موضح أعلاه،${\displaystyle Y}$ليكن متجه تسميات البيانات، و${\displaystyle J}$كن${\displaystyle (\ell +u)\times (\ell +u)}$مصفوفة كتلية${\displaystyle {\begin{bmatrix}I_{\ell }&0\\0&0_{u}\end{bmatrix}}}$:

${\displaystyle \alpha ^{*}={\underset {\alpha \in \mathbf {R} ^{\ell +u}}{\arg \!\min }}{\frac {1}{\ell }}(Y-JK\alpha )^{\mathrm {T} }(Y-JK\alpha )+\gamma _{A}\alpha ^{\mathrm {T} }K\alpha +{\frac {\gamma _{I}}{(\ell +u)^{2}}}\alpha ^{\mathrm {T} }KLK\alpha }$

بمحلول من

${\displaystyle \alpha ^{*}=\left(JK+\gamma _{A}\ell I+{\frac {\gamma _{I}\ell }{(\ell +u)^{2}}}LK\right)^{-1}Y}$^{[ 1 ]}

تم تطبيق خوارزمية LapRLS على مشاكل تشمل شبكات الاستشعار، ^{[ 7 ]} والتصوير الطبي ، ^{[ 8 ] [ 9 ]} واكتشاف الأجسام ، ^{[ 10 ]} والتحليل الطيفي ، ^{[ 11 ]} وتصنيف المستندات ، ^{[ 12 ]} وتفاعلات الأدوية مع البروتينات، ^{[ 13 ]} وضغط الصور والفيديوهات. ^{[ 14 ]}

آلات المتجهات الداعمة (SVMs) هي مجموعة من الخوارزميات تُستخدم غالبًا لتصنيف البيانات إلى مجموعتين أو أكثر، أو فئات . وبشكلٍ بديهي، ترسم آلة المتجهات الداعمة حدًا فاصلًا بين الفئات بحيث تكون أقرب الأمثلة المصنفة إلى الحد الفاصل أبعد ما يمكن. يمكن التعبير عن ذلك مباشرةً كبرنامج خطي ، ولكنه يُعادل أيضًا تنظيم تيكهونوف مع دالة خسارة المفصلة .${\displaystyle V(f(x),y)=\max(0,1-yf(x))}$:

${\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }\max(0,1-y_{i}f(x_{i}))+\gamma \left\|f\right\|_{K}^{2}}$^{[ 15 ] [ 16 ]}

بإضافة مصطلح التنظيم الجوهري إلى هذا التعبير، نحصل على بيان مشكلة LapSVM:

${\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }\max(0,1-y_{i}f(x_{i}))+\gamma _{A}\left\|f\right\|_{K}^{2}+{\frac {\gamma _{I}}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f} }$

مرة أخرى، تسمح نظرية التمثيل بالتعبير عن الحل بدلالة النواة التي يتم تقييمها عند نقاط البيانات:

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell +u}\alpha _{i}^{*}K(x_{i},x)}$

${\displaystyle \alpha }$يمكن إيجاد الحل عن طريق كتابة المسألة كبرنامج خطي وحل المسألة الثنائية . مرة أخرى، لنفترض أن${\displaystyle K}$لتكن مصفوفة النواة و${\displaystyle J}$لتكن مصفوفة الكتل${\displaystyle {\begin{bmatrix}I_{\ell }&0\\0&0_{u}\end{bmatrix}}}$، ويمكن إثبات أن الحل هو

${\displaystyle \alpha =\left(2\gamma _{A}I+2{\frac {\gamma _{I}}{(\ell +u)^{2}}}LK\right)^{-1}J^{\mathrm {T} }Y\beta ^{*}}$

أين${\displaystyle \beta ^{*}}$هو حل للمشكلة المزدوجة

${\displaystyle {\begin{aligned}&&\beta ^{*}=\max _{\beta \in \mathbf {R} ^{\ell }}&\sum _{i=1}^{\ell }\beta _{i}-{\frac {1}{2}}\beta ^{\mathrm {T} }Q\beta \\&{\text{subject to}}&&\sum _{i=1}^{\ell }\beta _{i}y_{i}=0\\&&&0\leq \beta _{i}\leq {\frac {1}{\ell }}\;i=1,\ldots ,\ell \end{aligned}}}$

و${\displaystyle Q}$يتم تعريفها بواسطة

${\displaystyle Q=YJK\left(2\gamma _{A}I+2{\frac {\gamma _{I}}{(\ell +u)^{2}}}LK\right)^{-1}J^{\mathrm {T} }Y}$^{[ 1 ]}

تم تطبيق LapSVM على مشاكل تشمل التصوير الجغرافي، ^{[ 17 ] [ 18 ] [ 19 ]} والتصوير الطبي، ^{[ 20 ] [ 21 ] [ 22 ]} والتعرف على الوجوه، ^{[ 23 ]} وصيانة الآلات، ^{[ 24 ]} وواجهات الدماغ والحاسوب . ^{[ 25 ]}

• تقوم مكتبة ManifoldLearn ومكتبة Primal LapSVM بتنفيذ LapRLS و LapSVM في MATLAB .
• تتضمن مكتبة Dlib للغة C++ دالة تنظيم متعددة الأبعاد خطية.