ماشین بردار پشتیبان ساختاریافته

ماشین بردار پشتیبان ساختار یافته یک الگوریتم یادگیری ماشین است که دسته بند بردار پشتیبان ماشین (SVM) را تعمیم می‌دهد . درحالی که طبقه‌بندی کننده SVM، دسته‌بندی دوتایی ، دسته‌بندی چندکلاسه و رگرسیون را پشتیبانی می‌کند، SVM ساختار یافته به آموزش یک دسته بند برای برچسب‌های خروجی با ساختار کلی به کار می رود.

به عنوان مثال، یک نمونه آماری ممکن است یک جمله به زبان طبیعی باشد و همچنین برچسب خروجی ما ممکن است یک درخت تجزیه با کیفیت باشد. آموزش مدل دسته‌بندی شامل نمایش جفت نمونه صحیح و جفت‌های برچسب خروجی است. پس از آموزش، مدل SVM ساختار یافته به فرد اجازه می‌دهد تا برای نمونه‌های جدید، برچسب خروجی متناظر را پیش‌بینی کند؛ یعنی با توجه به یک جمله زبان طبیعی، طبقه‌بندی کننده می‌تواند محتمل‌ترین درخت را جهت پیش بینی تولید کند.

آموزش

فرض کنید $\ell$ نمونه یادگیری $({\boldsymbol {x}}_{n},y_{n})\in {\mathcal {X}}\times {\mathcal {Y}}$, $n=1,\dots ,\ell$ داریم که در آن ${\mathcal {X}}$فضای نمونه (ورودی) و ${\mathcal {Y}}$ فضای برچسب (خروجی) می باشد. در مرحله آموزش SVM ساختاریافته بردار وزن ها ${\boldsymbol {w}}$طوری انتخاب می شود که تابع هزینه زیر کمینه شود:

${\underset {\boldsymbol {w}}{\min }}\quad \|{\boldsymbol {w}}\|^{2}+C\sum _{n=1}^{\ell }{\underset {y\in {\mathcal {Y}}}{\max }}\left(0,\Delta (y_{n},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{n},y)\rangle -\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{n},y_{n})\rangle \right)$

تابع هدف بالا محدب می باشد چون بیشینه تعدادی تابع تبدیل آفین است. تابع $\Delta :{\mathcal {Y}}\times {\mathcal {Y}}\to \mathbb {R} _{+}$ یک فاصله در فضای برچسب را اندازه گیری می کند و این یک تابع دلخواه (و نه لزوماً یک متریک) می باشد که رابطه های $\Delta (y,z)\geq 0$ و $\Delta (y,y)=0\;\;\forall y,z\in {\mathcal {Y}}$ را ارضا می کند. تابع $\Psi :{\mathcal {X}}\times {\mathcal {Y}}\to \mathbb {R} ^{d}$ یک تابع ویژگی است که یک بردار ویژگی از یک نمونه ورودی و برچسب داده‌شده را استخراج می‌کند. طراحی این تابع بستگی بسیار زیادی به کاربرد آن دارد.

از آنجایی که تابع هدف بالا مشتق پذیر نیست، اغلب، به صورت یک برنامه ریز درجه دوم فرموله می شود. این کار با معرفی یک متغیر $\xi _{n}$ به ازای هر نمونه آموزشی بدست می آید که هر کدام در نهایت برابر با مقدار ماکزیمم نشان داده شده در فرمول بالا خواهد شد. با این کار مساله بهینه سازی بالا به صورت زیر در می آید:

${\begin{array}{cl}{\underset {{\boldsymbol {w}},{\boldsymbol {\xi }}}{\min }}&\|{\boldsymbol {w}}\|^{2}+C\sum _{n=1}^{\ell }\xi _{n}\\{\textrm {s.t.}}&\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{n},y_{n})\rangle -\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{n},y)\rangle +\xi _{n}\geq \Delta (y_{n},y),\qquad n=1,\dots ,\ell ,\quad \forall y\in {\mathcal {Y}}\end{array}}$

استنتاج

در زمان تست، یک نمونه ورودی ${\boldsymbol {x}}\in {\mathcal {X}}$ به سیستم داده می شود و تابع پیش‌بینی $f:{\mathcal {X}}\to {\mathcal {Y}}$ آن را به یک برچسب از فضای برچسب ${\mathcal {Y}}$نگاشت می‌کند. برای SVM ساختار یافته، با توجه به بردار ${\boldsymbol {w}}$ به‌دست‌آمده از بخش آموزش، تابع پیش‌بینی به صورت زیر می باشد:

$f({\boldsymbol {x}})={\underset {y\in {\mathcal {Y}}}{\textrm {argmax}}}\quad \langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}},y)\rangle$

بنابراین, بیشینه کردن روی فضای برچسب، همان برچسب پیش‌بینی‌شده است. حل این مساله، مساله استنتاج نامیده می‌شود و مشابه برآوردگر بیشینه‌گر احتمال پسین (MAP) درمدل‌های احتمالی است. بسته به ساختار تابع $\Psi$، حل مساله بیشینه کردن می‌تواند سخت باشد.

جداسازی

برنامه درجه دوم فوق شامل محدودیت های نابرابر خطی بسیار زیاد و احتمالاً نامتناهی است. به طور کلی، تعداد نامساوی ها برای این که به طور ضمنی بهینه شود، بسیار زیاد است . به جای آن مسئله با استفاده از delayed constraint generation که در آن از زیر مجموعه ای از محدودیت های کوچک و متناهی استفاده شده است حل می‌شود. بهینه سازی بر روی یک زیرمجموعه ای از محدودیت‌ها، مجموعه جواب مطلوب را توسعه داده و یک راه حلی ارائه می‌دهد که کران پایین تری را بر روی هدف فراهم می‌کند. برای آزمایش این که آیا جواب ${\boldsymbol {w}}$ محدودیت‌های مجموعه کامل نامساوی ها را نقض می‌کند یا نه، یک مساله جداسازی باید حل شود. به دلیل اینکه نامساوی ها بر روی نمونه‌ها تجزیه می‌شوند، برای هرنمونه $({\boldsymbol {x}}_{n},y_{n})$ مساله زیر باید حل شود:

$y_{n}^{*}={\underset {y\in {\mathcal {Y}}}{\textrm {argmax}}}\left(\Delta (y_{n},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{n},y)\rangle -\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{n},y_{n})\rangle -\xi _{n}\right)$

به منظور بیشینه کردن سمت راست تابع هدف بالا ثابت $-\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{n},y_{n})\rangle -\xi _{n}$ از معادله خارج شده و یک عبارت وابسته به متغیرها، یعنی $\Delta (y_{n},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{n},y)\rangle$ بهینه می‌شود. اگر عبارت به‌دست‌آمده کوچک‌تر یا مساوی صفر باشد، برای نمونه های موجود هیچ محدودیتی نقض نمی‌شود. اگر اکیداً بزرگ‌تر از صفر باشد، محدودیت های نقض شده زیادی شناسایی می شود. این مسئله با این محدودیت توسعه داده شده و دوباره حل می شود. این فرایند تا زمانی ادامه می‌یابد که هیچ نامساوی نقض شده ای را نتوان شناسایی کرد.

اگر ثابت‌ها از مساله بالا حذف شوند، به رابطه زیر میرسیم:

$y_{n}^{*}={\underset {y\in {\mathcal {Y}}}{\textrm {argmax}}}\left(\Delta (y_{n},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{n},y)\rangle \right)$

این مسئله شبیه به مسائل استدلالی است. تنها تفاوت آن ها، افزودن عبارت $\Delta (y_{n},y)$است، که اغلب اوقات، $\Delta (y_{n},y)$ به گونه ای انتخاب می شود که در فضای برچسب تجزیه طبیعی داشته باشد. در این حالت، تاثیر دادن $\Delta$ مسئله را به یک مسئله استدلالی تبدیل می کند و حل بیش‌ترین محدودیت های نقض شده برابر با حل مساله استدلال خواهد بود.

منابع

• Ioannis Tsochantaridis, Thorsten Joachims, Thomas Hofmann and Yasemin Altun (2005), Large Margin Methods for Structured and Interdependent Output Variables, JMLR, Vol. 6, pages 1453-1484.
• Thomas Finley and Thorsten Joachims (2008), Training Structural SVMs when Exact Inference is Intractable, ICML 2008.
• Sunita Sarawagi and Rahul Gupta (2008), Accurate Max-margin Training for Structured Output Spaces, ICML 2008.
• Gökhan BakIr, Ben Taskar, Thomas Hofmann, Bernhard Schölkopf, Alex Smola and SVN Vishwanathan (2007), Predicting Structured Data, MIT Press.
• Vojtěch Franc and Bogdan Savchynskyy Discriminative Learning of Max-Sum Classifiers, Journal of Machine Learning Research, 9(Jan):67—104, 2008, Microtome Publishing
• Kevin Murphy [۱] Machine Learning, MIT Press