موضوع مقاله: ال پی بوست | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # ال پی بوست | مقدمه: ال پی بوست یا تقویت برنامه‌ریزی خطی یک روش یادگیری ماشین و از دسته الگوریتم‌های یادگیری نظارتی تقویتی (بوستینگ) برای مسئله طبقه‌بندی است. | ## بخش 1: ال پی بوست | در الگوریتم ال پی بوست، سعی می‌شود که در مرحله آموزش، حاشیه بین نمونه‌های طبقه‌های مختلف، بیشینه شود. به‌طور مثال، تابع طبقه‌بندی f را به صورت زیر در نظر بگیرید:این تابع، نمونه‌هایی را از فضای به دو طبقه با برچسب‌های و طبقه‌بندی می‌کند. در الگوریتم ال پی بوست، تابع طبقه‌بندی f طوری یادگرفته می‌شود حاشیه بین داده‌های با برچسب و داده‌های با برچسب بیشینه شود. کلیت الگوریتم مشابه تمامی طبقه‌بندهای تقویتی، تابع طبقه‌بندی نهایی به شکل زیر است:که وزن‌های غیر صفر برای طبقه‌بندهای ضعیف هستند. هر طبقه‌بند ضعیف ممکن است یک مقدار بهتر از انتخاب تصادفی عمل کند، اما ترکیب خطی حاصل از تعداد زیادی طبقه‌بند ضعیف می‌تواند عملکرد خیلی خوبی داشته باشد. این مرحله آن قدر تکرار می‌شود تا در نهایت هیچ طبقه‌بند ضعیف دیگری برای اضافه شدن باقی نمانده باشد. این ویژگی که همه وزن‌های طبقه‌بندها در هر مرحله تنظیم و به‌روزرسانی می‌شوند، با نام ویژگی کاملاً اصلاحی شناخته می‌شود. روش‌های اولیه بوستینگ، به‌طور مثال آدابوست، این ویژگی را نداشتند و بنابراین دیرتر به حد بهینه همگرا می‌شدند. برنامه‌ریز خطی مجموعه نامتناهی طبقه‌بندهای محتمل ضعیف را به صورت در نظر می‌گیریم و آن را به عنوان مجموعه فرضیه‌ها نامگذاری می‌کنیم. | ## بخش 2: ال پی بوست | یک راه نوشتن مسئله ال پی بوست، به صورت یک مسئله برنامه‌ریزی خطی با تعداد نامتناهی متغیر است. برنامه‌ریز خطی پرایمال ال پی بوست، که بردار وزن ناصفر ، بردار ناصفر متغیرهای ضعیف ، و حاشیه را بهینه می‌کند، به صورت زیر تعریف می‌شود:به تأثیر متغیرهای ضعیف توجه کنید: نرم ۱ این مقادیر در تابع هزینه به همراه ثابت به عنوان عبارت پنالتی آورده شده‌است، که اگر به اندازه کافی کوچک باشد همواره به یک برنامه‌ریز خطی قابل دستیابی منجر می‌شود. در اینجا ما فضای پارامتر را به کار گرفتیم، طوری که برای انتخاب ، طبقه‌بند ضعیف به صورت یکتا تعریف می‌شود. هنگامی که برنامه‌ریز خطی بالا در مقالات اولیه روش‌های بوستینگ نوشته شده بود، به دلیل وجود تعداد زیادی متغیر ، به عنوان یک الگوریتم غیرقابل کنترل شناخته می‌شد. بعدها فهمیده شد برنامه‌ریزهای خطی می‌توانند به صورت مؤثر و با استفاده از تکنیک کلاسیک تولید ستون حل شود. تولید ستون برای ال پی بوست در یک برنامه‌ریز خطی، یک ستون با یک متغیر پرایمال متناظر است. با تولید متغیرهای پرایمال مرحله به مرحله و وابسته به نیاز، نهایتاً مسئله نامحدود اولیه با همه متغیرها دوباره ساخته می‌شود. با انتخاب هوشمندانه ستون‌های مورد نیاز، مسئله می‌تواند طوری حل شود که با وجود تولید بخش کوچکی از ستون‌ها، تضمین شود که حل به‌دست آمده از آن، برای مسئله کامل اولیه بهینه است. مسئله دوگان ال پی بوست ستون‌های مسئله برنامه‌ریز خطی پرایمال، با سطرهای مسئله دوگان خطی آن متناظر هستند. | ## بخش 3: ال پی بوست | معادل دوگان مسئله برنامه‌ریز خطی ال پی بوست به صورت زیر است: برای برنامه‌ریزهای خطی، مقدار بهینه مسئله پرایمال و دوگان آن با یکدیگر برابرند. اگر مقادیر منفی نمونه‌های آموزش را به غیر از متغیرهای ضعیف مثبت که حاوی پنالتی‌ها برای نمونه‌های ناقض حاشیه هستند، را در نظر بگیریم، اندازه حاشیه‌ای که این مقادیر را از مقادیر مثبت نمونه‌های آموزش جدا می‌کند به عنوان حاشیه نرم (soft margin) شناخته می‌شود؛ بنابراین، حاشیه نرم ممکن است مثبت باشد گرچه همه نمونه‌ها توسط تابع طبقه‌بندی به صورت خطی جداپذیر نیستند. برای هر زیرمجموعه محدود، می‌توانیم برنامه‌ریز خطی را حل کنیم و بنابراین همه شرایط را برآورده کنیم. اگر بتوانیم ثابت کنیم که از بین همه شرایطی که ما به مسئله دوگان اضافه نکردیم، هیچ شرطی نقض نشده‌است، می‌توانیم ثابت کنیم که حل کردن مسئله محدودشده ما معادل است با حل کردن مسئله اولیه. اگر مقدار بهینه تابع هدف برای هر نمونه محدود باشد، می‌توانیم در فضای مسئله اولیه، یک مسئله جست و جو برای بیشترین شرط نقض شده در فضای مسئله اولیه، تعریف کنیم. به عبارتی دیگر می‌خواهیم را طوری پیدا کنیم که شرط زیر برقرار باشد:بنابراین، ما در فضای دنبال یک تابع تصمیم می‌گردیم که سمت چپ شرط دوگان را بیشینه کند. اگر شرط نتواند توسط هیچ تابع تصمیمی نقض شود، هیچ‌یک از شرط‌های متناظر آن نمی‌توانند در مسئله اولیه فعال باشند و مسئله محدود معادل است. با این وجود، اگر این ثابت را به صورت در نظر بگیریم، که تعداد نمونه‌های یادگیری، و است، پارامتر جدید خواص زیر را خواهد داشت: یک کران بالا برای کسر خطاهای یادگیری است. | ## جمع‌بندی | به عبارتی دیگر، اگر نمایانگر تعداد نمونه‌های یادگیری با طبقه‌بندی اشتباه باشد، آنگاه شرط برقرار است.