آلة المتجهات الداعمة المهيكلة

📅 آخر تحديث: ٢٢ يوليو ٢٠٢٦
✍️ نُشر في: ٢٢ يوليو ٢٠٢٦
📷 يحتوي على 24 صور
الموسوعة الحرة

آلة المتجهات الداعمة المهيكلة هي خوارزمية تعلم آلي تُعمم مصنف آلة المتجهات الداعمة (SVM). فبينما يدعم مصنف SVM التصنيف الثنائي والتصنيف متعدد الفئات والانحدار ، تسمح آلة المتجهات الداعمة المهيكلة بتدريب مصنف لتصنيفات الإخراج المهيكلة العامة .

على سبيل المثال، قد تكون عينة البيانات جملةً بلغة طبيعية، ويكون تصنيف الناتج شجرة تحليل مُعَلَّمة . يتضمن تدريب المصنف عرض أزواج من عينات البيانات الصحيحة وتصنيفات الناتج. بعد التدريب، يسمح نموذج SVM المُهيكل بالتنبؤ بتصنيف الناتج المناسب لعينات البيانات الجديدة؛ أي أنه عند إعطاء جملة بلغة طبيعية، يمكن للمصنف إنتاج شجرة التحليل الأكثر احتمالاً.

تمرين

لمجموعة منن{\displaystyle n}حالات التدريب(xأنا،yأنا)∈X×Y{\displaystyle ({\boldsymbol {x}}_{i},y_{i})\in {\mathcal {X}}\times {\mathcal {Y}}}،أنا=1،...،ن{\displaystyle i=1,\dots ,n}من فضاء العينةX{\displaystyle {\mathcal {X}}}ومساحة التسميةY{\displaystyle {\mathcal {Y}}}، تعمل آلة المتجهات الداعمة المهيكلة على تقليل دالة المخاطرة المنتظمة التالية.

مينw‖w‖2+ج∑أنا=1نالأعلىy∈Y(0،Δ(yأنا،y)+⟨w،Ψ(xأنا،y)⟩-⟨w،Ψ(xأنا،yأنا)⟩)\begin{{\displaystyle {\underset {\boldsymbol {w}}{\min }}\quad \|{\boldsymbol {w}}\|^{2}+C\sum _{i=1}^{n}{\underset {y\in {\mathcal {Y}}}{\max }}\left(0,\Delta (y_{i},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle -\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y_{i})\rangle \right)}

الدالة محدبة فيw{\displaystyle {\boldsymbol {w}}}لأن القيمة القصوى لمجموعة من الدوال الأفينية تكون محدبة.Δ:Y×Y→R+{\displaystyle \Delta يقيس الرمز `:\mathcal {Y}}\times {\mathcal {Y}}\to \mathbb {R} _{+}}` المسافة في فضاء التصنيفات، وهو دالة اختيارية (ليست بالضرورة مقياسًا ) تحقق الشرط التاليΔ(y،z)≥0{\displaystyle \Delta (y,z)\geq 0}وΔ(y،y)=0∀y،z∈Y{\displaystyle \Delta (y,y)=0\;\;\forall y,z\in {\mathcal {Y}}}الوظيفةΨ:X×Y→Rد{\displaystyle \Psi الدالة `:{\mathcal {X}}\times {\mathcal {Y}}\to \mathbb {R} ^{d}}` هي دالة مميزة، تستخرج متجهًا مميزًا من عينة وتصنيف معينين. ويعتمد تصميم هذه الدالة بشكل كبير على التطبيق.

نظرًا لأن دالة المخاطرة المنتظمة المذكورة أعلاه غير قابلة للتفاضل، فغالبًا ما يُعاد صياغتها في شكل برنامج تربيعي عن طريق إدخال متغير ركود واحدξأنا{\displaystyle \xi _{i}}لكل عينة، تمثل كل منها القيمة القصوى. الصيغة الأولية القياسية لـ SVM المهيكلة موضحة أدناه.

مينw،ξ‖w‖2+ج∑أنا=1نξأناشارع⟨w،Ψ(xأنا،yأنا)⟩-⟨w،Ψ(xأنا،y)⟩+ξأنا≥Δ(yأنا،y)،أنا=1،...،ن،∀y∈Y\begin{array}{cl}{\underset {{\boldsymbol {w}},{\boldsymbol {\xi }}}{\min }}&\|{\boldsymbol {w}}\|^{2}+C\sum _{i=1}^{n}\xi _{i}\\{\textrm {st}}&\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y_{i})\rangle -\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle +\xi _{i}\geq \Delta (y_{i},y),\qquad i=1,\dots ,n,\quad \forall y\in {\mathcal {Y}}\end{array}}}

الاستدلال

في وقت الاختبار، عينة واحدة فقطx∈X{\displaystyle {\boldsymbol {x}}\in {\mathcal {X}}}معروف، ووظيفة التنبؤو:X→Y{\displaystyle f:{\mathcal {X}}\to {\mathcal {Y}}}يرسمها إلى تصنيف متوقع من فضاء التصنيفاتY{\displaystyle {\mathcal {Y}}}بالنسبة لآلات المتجهات الداعمة المهيكلة، بالنظر إلى المتجهw{\displaystyle {\boldsymbol {w}}}بناءً على التدريب، تكون دالة التنبؤ كما يلي.

و(x)=argmaxy∈Y⟨w،Ψ(x،y)⟩{\displaystyle f({\boldsymbol {x}})={\underset {y\in {\mathcal {Y}}}{\textrm {argmax}}}\quad \langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}},y)\rangle }

لذا، فإن القيمة العظمى في فضاء التصنيفات هي التصنيف المتوقع. ويُعرف إيجاد هذه القيمة العظمى بمسألة الاستدلال، وهي مشابهة لمسألة التنبؤ بأقصى احتمال لاحق (MAP) في النماذج الاحتمالية. ويعتمد ذلك على بنية الدالة.Ψ{\displaystyle \Psi }قد يكون إيجاد الحل الأمثل مشكلة صعبة.

الانفصال

يتضمن البرنامج التربيعي المذكور أعلاه عددًا كبيرًا جدًا، وربما لا نهائيًا، من قيود المتباينات الخطية . وبشكل عام، يكون عدد المتباينات كبيرًا جدًا بحيث لا يمكن تحسينه بشكل صريح. بدلًا من ذلك، تُحل المشكلة باستخدام توليد القيود المؤجل، حيث تُستخدم مجموعة فرعية محدودة وصغيرة فقط من القيود. يؤدي التحسين على مجموعة فرعية من القيود إلى توسيع مجموعة الحلول الممكنة ، وسينتج عنه حل يوفر حدًا أدنى للدالة الهدف. لاختبار ما إذا كان الحلw{\displaystyle {\boldsymbol {w}}}بما أن هذه المسألة تنتهك قيود متباينات المجموعة الكاملة، فإنه يلزم حل مشكلة فصل. وبما أن المتباينات تتحلل على العينات، فلكل عينة(xأنا،yأنا){\displaystyle ({\boldsymbol {x}}_{i},y_{i})}يجب حل المشكلة التالية.

yن*=argmaxy∈Y(Δ(yأنا،y)+⟨w،Ψ(xأنا،y)⟩-⟨w،Ψ(xأنا،yأنا)⟩-ξأنا){\displaystyle y_{n}^{*}={\underset {y\in {\mathcal {Y}}}{\textrm {argmax}}}\left(\Delta (y_{i},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle -\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y_{i})\rangle -\xi _{i}\right)}

يتكون الهدف الموجود على الجانب الأيمن والذي يجب تعظيمه من الثابت-⟨w،Ψ(xأنا،yأنا)⟩-ξأنا{\displaystyle -\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y_{i})\rangle -\xi _{i}}ومصطلح يعتمد على المتغيرات التي تم تحسينها، وهي:Δ(yأنا،y)+⟨w،Ψ(xأنا،y)⟩{\displaystyle \Delta (y_{i},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle }إذا كانت قيمة الهدف المحققة في الطرف الأيمن أصغر من أو تساوي الصفر، فلا توجد قيود منتهكة لهذه العينة. أما إذا كانت أكبر من الصفر، فقد تم تحديد القيد الأكثر انتهاكًا لهذه العينة. يتم توسيع نطاق المسألة بهذا القيد وحلها. وتستمر هذه العملية حتى لا يتم تحديد أي متباينات منتهكة.

إذا تم حذف الثوابت من المسألة المذكورة أعلاه، فسنحصل على المسألة التالية التي يتعين حلها.

yأنا*=argmaxy∈Y(Δ(yأنا،y)+⟨w،Ψ(xأنا،y)⟩){\displaystyle y_{i}^{*}={\underset {y\in {\mathcal {Y}}}{\textrm {argmax}}}\left(\Delta (y_{i},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle \right)}

تبدو هذه المسألة مشابهة جدًا لمسألة الاستدلال. والفرق الوحيد هو إضافة الحدΔ(yأنا،y){\displaystyle \Delta (y_{i},y)}في أغلب الأحيان، يتم اختيارها بحيث يكون لها تفكيك طبيعي في فضاء التصنيفات. في هذه الحالة، يكون تأثيرΔ{\displaystyle \Delta }يمكن ترميزها في مشكلة الاستدلال، وحل القيد الأكثر انتهاكًا يعادل حل مشكلة الاستدلال.

مراجع