نمایش مبدأ برای ال پی بوست

ال پی بوست یا تقویت [[برنامه‌ریزی خطی]] {{به انگلیسی| LPBoost}} یک روش [[یادگیری ماشینی|یادگیری ماشین]] و از دسته الگوریتم‌های [[یادگیری با نظارت|یادگیری نظارتی]] تقویتی ([[بوستینگ]]) برای مسئله [[طبقه‌بندی آماری|طبقه‌بندی]] است. این الگوریتم خصوصاً در مسائل انتخاب ویژگی و طبقه‌بندی مشترک، کاربرد دارد. در الگوریتم ال پی بوست، سعی می‌شود که در مرحله آموزش، حاشیه بین نمونه‌های طبقه‌های مختلف، بیشینه شود. به‌طور مثال، تابع طبقه‌بندی f را به صورت زیر در نظر بگیرید:<math display="block">f: \chi \rightarrow \{-1, 1\}, </math>این تابع، نمونه‌هایی را از فضای <math>\chi </math> به دو طبقه با برچسب‌های <math>-1 </math> و <math>1 </math> طبقه‌بندی می‌کند. در الگوریتم ال پی بوست، تابع طبقه‌بندی f طوری یادگرفته می‌شود حاشیه بین داده‌های با برچسب <math>-1 </math> و داده‌های با برچسب <math>1 </math> بیشینه شود.

== کلیت الگوریتم ==
مشابه تمامی طبقه‌بندهای تقویتی، تابع طبقه‌بندی نهایی به شکل زیر است:<math display="block">f(x)=\sum_{j=1}^{J} \alpha_j h_j (x), </math>که <math>\alpha_j </math> وزن‌های غیر صفر برای طبقه‌بندهای ضعیف <math>h_j : \chi \rightarrow \{-1, 1\} </math> هستند. هر طبقه‌بند ضعیف <math>h_j </math> ممکن است یک مقدار بهتر از انتخاب تصادفی عمل کند، اما ترکیب خطی حاصل از تعداد زیادی طبقه‌بند ضعیف می‌تواند عملکرد خیلی خوبی داشته باشد.

ال پی بوست با شروع از یک مجموعه طبقه‌بندهای ضعیف، تابع <math>f </math> را می‌سازد. در هر مرحله، یک طبقه‌بند ضعیف انتخاب شده و به مجموعه طبقه‌بندها اضافه می‌شود. سپس همه وزن‌های <math>\alpha </math> برای مجموعه کنونی طبقه‌بندهای ضعیف به‌روزرسانی و تنظیم می‌شوند. این مرحله آن قدر تکرار می‌شود تا در نهایت هیچ طبقه‌بند ضعیف دیگری برای اضافه شدن باقی نمانده باشد.

این ویژگی که همه وزن‌های طبقه‌بندها در هر مرحله تنظیم و به‌روزرسانی می‌شوند، با نام ویژگی کاملاً اصلاحی شناخته می‌شود. روش‌های اولیه بوستینگ، به‌طور مثال [[آدابوست]]، این ویژگی را نداشتند و بنابراین دیرتر به حد بهینه همگرا می‌شدند.

== برنامه‌ریز خطی ==
مجموعه نامتناهی طبقه‌بندهای محتمل ضعیف را به صورت <math>\mathcal{H}=\{h(. ; \omega) | \omega \in \Omega\} </math> در نظر می‌گیریم و آن را به عنوان مجموعه فرضیه‌ها نامگذاری می‌کنیم. یک راه نوشتن مسئله ال پی بوست، به صورت یک مسئله برنامه‌ریزی خطی با تعداد نامتناهی متغیر است.

برنامه‌ریز خطی پرایمال ال پی بوست، که بردار وزن ناصفر <math>\alpha </math>، بردار ناصفر متغیرهای ضعیف <math>\xi </math>، و حاشیه <math>\rho </math> را بهینه می‌کند، به صورت زیر تعریف می‌شود:<math display="block">\min_{\alpha, \xi, \rho} -\rho + D \sum_{n=1}^{l} \xi_n </math><math display="block">sb.t. \sum_{\omega \in \Omega} y_n \alpha_\omega h(x_n ; \omega) + \xi_n \geq \rho ,  n=1, ..., l, </math><math display="block">\sum_{\omega \in \Omega} \alpha_\omega = 1, </math><math display="block">\xi_n \geq 0,  n=1, ..., l </math><math display="block">\xi_n \geq 0,  \omega \in \Omega </math><math display="block">\alpha_\omega \geq 0,  \omega \in \Omega </math><math display="block">\rho \in \real. </math>به تأثیر متغیرهای ضعیف <math>\xi \geq 0 </math> توجه کنید: نرم ۱ این مقادیر در تابع هزینه به همراه ثابت <math>D </math> به عنوان عبارت پنالتی آورده شده‌است، که اگر به اندازه کافی کوچک باشد همواره به یک برنامه‌ریز خطی قابل دستیابی منجر می‌شود.

در اینجا ما فضای پارامتر <math>\Omega </math> را به کار گرفتیم، طوری که برای انتخاب <math>\omega \in \Omega </math>، طبقه‌بند ضعیف <math>h(.; \omega) : \chi \rightarrow \{-1, 1\} </math> به صورت یکتا تعریف می‌شود.

هنگامی که برنامه‌ریز خطی بالا در مقالات اولیه روش‌های بوستینگ نوشته شده بود، به دلیل وجود تعداد زیادی متغیر <math>\alpha </math>، به عنوان یک الگوریتم غیرقابل کنترل شناخته می‌شد. بعدها فهمیده شد برنامه‌ریزهای خطی می‌توانند به صورت مؤثر و با استفاده از تکنیک کلاسیک [[تولید ستون]] حل شود.<ref>{{Cite journal|last=Demiriz|first=Ayhan|last2=Bennett|first2=Kristin P.|last3=Shawe-Taylor|first3=John|date=2002-01-01|title=Linear Programming Boosting via Column Generation|url=https://doi.org/10.1023/A:1012470815092|journal=Machine Learning|language=en|volume=46|issue=1|pages=225–254|doi=10.1023/A:1012470815092|issn=1573-0565}}</ref>

=== تولید ستون برای ال پی بوست ===
در یک برنامه‌ریز خطی، یک ستون با یک متغیر پرایمال متناظر است. تولید ستون یک روش برای حل برنامه‌ریزهای خطی بزرگ است. این روش معمولاً در مسائل با متغیرهای محدود به کار می‌رود. با تولید متغیرهای پرایمال مرحله به مرحله و وابسته به نیاز، نهایتاً مسئله نامحدود اولیه با همه متغیرها دوباره ساخته می‌شود. با انتخاب هوشمندانه ستون‌های مورد نیاز، مسئله می‌تواند طوری حل شود که با وجود تولید بخش کوچکی از ستون‌ها، تضمین شود که حل به‌دست آمده از آن، برای مسئله کامل اولیه بهینه است.

==== مسئله دوگان ال پی بوست ====
ستون‌های مسئله برنامه‌ریز خطی پرایمال، با سطرهای مسئله دوگان خطی آن متناظر هستند. معادل دوگان مسئله برنامه‌ریز خطی ال پی بوست به صورت زیر است:<math display="block">\max_{\lambda, \gamma} \gamma </math><math display="block">sb.t. \sum_{n=1}^{l} y_n h(x_n; \omega) + \gamma \leq 0, \omega \in \Omega </math><math display="block">0 \leq \lambda_n \leq D,   n = 1, ..., l, </math><math display="block">\sum_{n=1}^{l} \lambda_n = 1, </math><math display="block">\gamma \in \real </math>
برای برنامه‌ریزهای خطی، مقدار بهینه مسئله پرایمال و دوگان آن با یکدیگر برابرند. برای مسائل پرایمال و دوگان بالا، مقدار بهینه برابر است با حاشیه نرم منفی. اگر مقادیر منفی نمونه‌های آموزش را به غیر از متغیرهای ضعیف مثبت که حاوی پنالتی‌ها برای نمونه‌های ناقض حاشیه هستند، را در نظر بگیریم، اندازه حاشیه‌ای که این مقادیر را از مقادیر مثبت نمونه‌های آموزش جدا می‌کند به عنوان حاشیه نرم (soft margin) شناخته می‌شود؛ بنابراین، حاشیه نرم ممکن است مثبت باشد گرچه همه نمونه‌ها توسط تابع طبقه‌بندی به صورت خطی جداپذیر نیستند. حالتی که همه نمونه‌ها توسط تابع طبقه‌بندی بتوانند جدا شوند، به عنوان حاشیه سخت (hard margin) شناخته می‌شود.

==== معیار همگرایی ====
یک زیرمجموعه از شرایط ارضا شده در مسئله دوگان را در نظر بگیرید. برای هر زیرمجموعه محدود، می‌توانیم برنامه‌ریز خطی را حل کنیم و بنابراین همه شرایط را برآورده کنیم. اگر بتوانیم ثابت کنیم که از بین همه شرایطی که ما به مسئله دوگان اضافه نکردیم، هیچ شرطی نقض نشده‌است، می‌توانیم ثابت کنیم که حل کردن مسئله محدودشده ما معادل است با حل کردن مسئله اولیه. اگر <math>\gamma^* </math> مقدار بهینه تابع هدف برای هر نمونه محدود باشد، می‌توانیم در فضای مسئله اولیه، یک مسئله جست و جو برای بیشترین شرط نقض شده در فضای مسئله اولیه، تعریف کنیم. به عبارتی دیگر می‌خواهیم <math>\omega^* \in \Omega </math> را طوری پیدا کنیم که شرط زیر برقرار باشد:<math display="block">\omega^* = argmax_{\omega \in \Omega} \sum_{n=1}^{l} y_n h(x_n ; \omega) \lambda_n </math>بنابراین، ما در فضای <math>\mathcal{H} </math> دنبال یک تابع تصمیم <math>h(.; \omega^*) </math> می‌گردیم که سمت چپ شرط دوگان را بیشینه کند. اگر شرط نتواند توسط هیچ تابع تصمیمی نقض شود، هیچ‌یک از شرط‌های متناظر آن نمی‌توانند در مسئله اولیه فعال باشند و مسئله محدود معادل است.

=== ثابت پنالتی <math>D </math> ===
مقدار ثابت مثبت <math>D </math> می‌تواند توسط روش‌های انتخاب مدل پیدا شود. با این وجود، اگر این ثابت را به صورت <math>D=\frac{1}{lv} </math> در نظر بگیریم، که <math>l </math> تعداد نمونه‌های یادگیری، و <math>0<v<1 </math> است، پارامتر جدید <math>v </math> خواص زیر را خواهد داشت:
* <math>v </math> یک کران بالا برای کسر خطاهای یادگیری است. به عبارتی دیگر، اگر <math>k </math> نمایانگر تعداد نمونه‌های یادگیری با طبقه‌بندی اشتباه باشد، آنگاه شرط <math>\frac{k}{l} \leq v </math> برقرار است.
* <math>v </math> یک کران پایین روی کسر نمونه‌های یادگیری خارج از حاشیه است.

== الگوریتم ==
* ورودی:
** مجموعه یادگیری <math>X={x_1, ..., x_l}, x_i \in \chi </math>
** برچسب‌های یادگیری <math>Y={y_1, ..., y_l}, y_i \in \{-1, 1\} </math>
** آستانه همگرایی <math>\theta \geq 0 </math>
* خروجی:

== جستارهای وابسته ==
* [[بوستینگ]]
* [[آدابوست]]

== منابع ==
{{پانویس}}