ماشین بردار پشتیبان ساختاریافته
ماشین بردار پشتیبان ساختار یافته یک الگوریتم یادگیری ماشین است که دسته بند بردار پشتیبان ماشین (SVM) را تعمیم می‌دهد . درحالی که طبقه‌بندی کننده SVM، ، و رگرسیون را پشتیبانی می‌کند، SVM ساختار یافته به آموزش یک دسته بند برای به کار می رود.
به عنوان مثال، یک نمونه آماری ممکن است یک جمله به زبان طبیعی باشد و همچنین برچسب خروجی ما ممکن است یک درخت تجزیه با کیفیت باشد. آموزش مدل دسته‌بندی شامل نمایش جفت نمونه صحیح و جفت‌های برچسب خروجی است. پس از آموزش، مدل SVM ساختار یافته به فرد اجازه می‌دهد تا برای نمونه‌های جدید، برچسب خروجی متناظر را پیش‌بینی کند؛ یعنی با توجه به یک جمله زبان طبیعی، طبقه‌بندی کننده می‌تواند محتمل‌ترین درخت را جهت پیش بینی تولید کند.
فرض کنید formula_1 نمونه یادگیری formula_2, formula_3 داریم که در آن formula_4فضای نمونه (ورودی) و formula_5 فضای برچسب (خروجی) می باشد. در مرحله آموزش SVM ساختاریافته بردار وزن ها formula_6طوری انتخاب می شود که تابع هزینه زیر کمینه شود:
تابع هدف بالا محدب می باشد چون بیشینه تعدادی تابع تبدیل آفین است. تابع formula_8 یک فاصله در فضای برچسب را اندازه گیری می کند و این یک تابع دلخواه (و نه لزوماً یک متریک) می باشد که رابطه های formula_9 و formula_10 را ارضا می کند. تابع formula_11 یک تابع ویژگی است که یک بردار ویژگی از یک نمونه ورودی و برچسب داده‌شده را استخراج می‌کند. طراحی این تابع بستگی بسیار زیادی به کاربرد آن دارد.
از آنجایی که تابع هدف بالا مشتق پذیر نیست، اغلب، به صورت یک برنامه ریز درجه دوم فرموله می شود. این کار با معرفی یک متغیر formula_12 به ازای هر نمونه آموزشی بدست می آید که هر کدام در نهایت برابر با مقدار ماکزیمم نشان داده شده در فرمول بالا خواهد شد. با این کار مساله بهینه سازی بالا به صورت زیر در می آید:
در زمان تست، یک نمونه ورودی formula_14 به سیستم داده می شود و تابع پیش‌بینی formula_15 آن را به یک برچسب از فضای برچسب formula_5نگاشت می‌کند. برای SVM ساختار یافته، با توجه به بردار formula_6 به‌دست‌آمده از بخش آموزش، تابع پیش‌بینی به صورت زیر می باشد:
بنابراین, بیشینه کردن روی فضای برچسب، همان برچسب پیش‌بینی‌شده است. حل این مساله، مساله استنتاج نامیده می‌شود و مشابه برآوردگر بیشینه‌گر احتمال پسین (MAP) درمدل‌های احتمالی است. بسته به ساختار تابع formula_19، حل مساله بیشینه کردن می‌تواند سخت باشد.
برنامه درجه دوم فوق شامل محدودیت های نابرابر خطی بسیار زیاد و احتمالاً نامتناهی است. به طور کلی، تعداد نامساوی ها برای این که به طور ضمنی بهینه شود، بسیار زیاد است . به جای آن مسئله با استفاده از delayed constraint generation که در آن از زیر مجموعه ای از محدودیت های کوچک و متناهی استفاده شده است حل می‌شود. بهینه سازی بر روی یک زیرمجموعه ای از محدودیت‌ها، را توسعه داده و یک راه حلی ارائه می‌دهد که کران پایین تری را بر روی هدف فراهم می‌کند. برای آزمایش این که آیا جواب formula_6 محدودیت‌های مجموعه کامل نامساوی ها را نقض می‌کند یا نه، یک مساله جداسازی باید حل شود. به دلیل اینکه نامساوی ها بر روی نمونه‌ها تجزیه می‌شوند، برای هرنمونه formula_21 مساله زیر باید حل شود:
به منظور بیشینه کردن سمت راست تابع هدف بالا ثابت formula_23 از معادله خارج شده و یک عبارت وابسته به متغیرها، یعنی formula_24 بهینه می‌شود. اگر عبارت به‌دست‌آمده کوچک‌تر یا مساوی صفر باشد، برای نمونه های موجود هیچ محدودیتی نقض نمی‌شود. اگر اکیداً بزرگ‌تر از صفر باشد، محدودیت های نقض شده زیادی شناسایی می شود. این مسئله با این محدودیت توسعه داده شده و دوباره حل می شود. این فرایند تا زمانی ادامه می‌یابد که هیچ نامساوی نقض شده ای را نتوان شناسایی کرد.
اگر ثابت‌ها از مساله بالا حذف شوند، به رابطه زیر میرسیم:
این مسئله شبیه به مسائل استدلالی است. تنها تفاوت آن ها، افزودن عبارت formula_26است، که اغلب اوقات، formula_26 به گونه ای انتخاب می شود که در فضای برچسب تجزیه طبیعی داشته باشد. در این حالت، تاثیر دادن formula_28 مسئله را به یک مسئله استدلالی تبدیل می کند و حل بیش‌ترین محدودیت های نقض شده برابر با حل مساله استدلال خواهد بود.