ال پی بوست کیست؟ توضیح بده.
ال پی بوست یا تقویت برنامه‌ریزی خطی یک روش یادگیری ماشین و از دسته الگوریتم‌های یادگیری نظارتی تقویتی (بوستینگ) برای مسئله طبقه‌بندی است. این الگوریتم خصوصاً در مسائل انتخاب ویژگی و طبقه‌بندی مشترک، کاربرد دارد. در الگوریتم ال پی بوست، سعی می‌شود که در مرحله آموزش، حاشیه بین نمونه‌های طبقه‌های مختلف، بیشینه شود. به‌طور مثال، تابع طبقه‌بندی f را به صورت زیر در نظر بگیرید:formula_1این تابع، نمونه‌هایی را از فضای formula_2 به دو طبقه با برچسب‌های formula_3 و formula_4 طبقه‌بندی می‌کند. در الگوریتم ال پی بوست، تابع طبقه‌بندی f طوری یادگرفته می‌شود حاشیه بین داده‌های با برچسب formula_3 و داده‌های با برچسب formula_4 بیشینه شود.کلیت الگوریتم.مشابه تمامی طبقه‌بندهای تقویتی، تابع طبقه‌بندی نهایی به شکل زیر است:formula_7که formula_8 وزن‌های غیر صفر برای طبقه‌بندهای ضعیف formula_9 هستند. هر طبقه‌بند ضعیف formula_10 ممکن است یک مقدار بهتر از انتخاب تصادفی عمل کند، اما ترکیب خطی حاصل از تعداد زیادی طبقه‌بند ضعیف می‌تواند عملکرد خیلی خوبی داشته باشد.ال پی بوست با شروع از یک مجموعه طبقه‌بندهای ضعیف، تابع formula_11 را می‌سازد. در هر مرحله، یک طبقه‌بند ضعیف انتخاب شده و به مجموعه طبقه‌بندها اضافه می‌شود. سپس همه وزن‌های formula_12 برای مجموعه کنونی طبقه‌بندهای ضعیف به‌روزرسانی و تنظیم می‌شوند. این مرحله آن قدر تکرار می‌شود تا در نهایت هیچ طبقه‌بند ضعیف دیگری برای اضافه شدن باقی نمانده باشد.این ویژگی که همه وزن‌های طبقه‌بندها در هر مرحله تنظیم و به‌روزرسانی می‌شوند، با نام ویژگی کاملاً اصلاحی شناخته می‌شود. روش‌های اولیه بوستینگ، به‌طور مثال آدابوست، این ویژگی را نداشتند و بنابراین دیرتر به حد بهینه همگرا می‌شدند.برنامه‌ریز خطی.مجموعه نامتناهی طبقه‌بندهای محتمل ضعیف را به صورت formula_13 در نظر می‌گیریم و آن را به عنوان مجموعه فرضیه‌ها نامگذاری می‌کنیم. یک راه نوشتن مسئله ال پی بوست، به صورت یک مسئله برنامه‌ریزی خطی با تعداد نامتناهی متغیر است.برنامه‌ریز خطی پرایمال ال پی بوست، که بردار وزن ناصفر formula_12، بردار ناصفر متغیرهای ضعیف formula_15، و حاشیه formula_16 را بهینه می‌کند، به صورت زیر تعریف می‌شود:formula_17formula_18formula_19formula_20formula_21formula_22formula_23به تأثیر متغیرهای ضعیف formula_24 توجه کنید: نرم ۱ این مقادیر در تابع هزینه به همراه ثابت formula_25 به عنوان عبارت پنالتی آورده شده‌است، که اگر به اندازه کافی کوچک باشد همواره به یک برنامه‌ریز خطی قابل دستیابی منجر می‌شود.در اینجا ما فضای پارامتر formula_26 را به کار گرفتیم، طوری که برای انتخاب formula_27، طبقه‌بند ضعیف formula_28 به صورت یکتا تعریف می‌شود.هنگامی که برنامه‌ریز خطی بالا در مقالات اولیه روش‌های بوستینگ نوشته شده بود، به دلیل وجود تعداد زیادی متغیر formula_12، به عنوان یک الگوریتم غیرقابل کنترل شناخته می‌شد. بعدها فهمیده شد برنامه‌ریزهای خطی می‌توانند به صورت مؤثر و با استفاده از تکنیک کلاسیک تولید ستون حل شود.تولید ستون برای ال پی بوست.در یک برنامه‌ریز خطی، یک ستون با یک متغیر پرایمال متناظر است. تولید ستون یک روش برای حل برنامه‌ریزهای خطی بزرگ است. این روش معمولاً در مسائل با متغیرهای محدود به کار می‌رود. با تولید متغیرهای پرایمال مرحله به مرحله و وابسته به نیاز، نهایتاً مسئله نامحدود اولیه با همه متغیرها دوباره ساخته می‌شود. با انتخاب هوشمندانه ستون‌های مورد نیاز، مسئله می‌تواند طوری حل شود که با وجود تولید بخش کوچکی از ستون‌ها، تضمین شود که حل به‌دست آمده از آن، برای مسئله کامل اولیه بهینه است.مسئله دوگان ال پی بوست.ستون‌های مسئله برنامه‌ریز خطی پرایمال، با سطرهای مسئله دوگان خطی آن متناظر هستند. معادل دوگان مسئله برنامه‌ریز خطی ال پی بوست به صورت زیر است:formula_30formula_31formula_32formula_33formula_34برای برنامه‌ریزهای خطی، مقدار بهینه مسئله پرایمال و دوگان آن با یکدیگر برابرند. برای مسائل پرایمال و دوگان بالا، مقدار بهینه برابر است با حاشیه نرم منفی. اگر مقادیر منفی نمونه‌های آموزش را به غیر از متغیرهای ضعیف مثبت که حاوی پنالتی‌ها برای نمونه‌های ناقض حاشیه هستند، را در نظر بگیریم، اندازه حاشیه‌ای که این مقادیر را از مقادیر مثبت نمونه‌های آموزش جدا می‌کند به عنوان حاشیه نرم (soft margin) شناخته می‌شود؛ بنابراین، حاشیه نرم ممکن است مثبت باشد گرچه همه نمونه‌ها توسط تابع طبقه‌بندی به صورت خطی جداپذیر نیستند. حالتی که همه نمونه‌ها توسط تابع طبقه‌بندی بتوانند جدا شوند، به عنوان حاشیه سخت (hard margin) شناخته می‌شود.معیار همگرایی.یک زیرمجموعه از شرایط ارضا شده در مسئله دوگان را در نظر بگیرید. برای هر زیرمجموعه محدود، می‌توانیم برنامه‌ریز خطی را حل کنیم و بنابراین همه شرایط را برآورده کنیم. اگر بتوانیم ثابت کنیم که از بین همه شرایطی که ما به مسئله دوگان اضافه نکردیم، هیچ شرطی نقض نشده‌است، می‌توانیم ثابت کنیم که حل کردن مسئله محدودشده ما معادل است با حل کردن مسئله اولیه. اگر formula_35 مقدار بهینه تابع هدف برای هر نمونه محدود باشد، می‌توانیم در فضای مسئله اولیه، یک مسئله جست و جو برای بیشترین شرط نقض شده در فضای مسئله اولیه، تعریف کنیم. به عبارتی دیگر می‌خواهیم formula_36 را طوری پیدا کنیم که شرط زیر برقرار باشد:formula_37بنابراین، ما در فضای formula_38 دنبال یک تابع تصمیم formula_39 می‌گردیم که سمت چپ شرط دوگان را بیشینه کند. اگر شرط نتواند توسط هیچ تابع تصمیمی نقض شود، هیچ‌یک از شرط‌های متناظر آن نمی‌توانند در مسئله اولیه فعال باشند و مسئله محدود معادل است.ثابت پنالتی formula_25.مقدار ثابت مثبت formula_25 می‌تواند توسط روش‌های انتخاب مدل پیدا شود. با این وجود، اگر این ثابت را به صورت formula_42 در نظر بگیریم، که formula_43 تعداد نمونه‌های یادگیری، و formula_44 است، پارامتر جدید formula_45 خواص زیر را خواهد داشت: