موضوع مقاله: نزدیک‌ترین همسایه حاشیه بزرگ | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # نزدیک‌ترین همسایه حاشیه بزرگ | مقدمه: طبقه‌بندی نزدیک‌ترین همسایه حاشیه بزرگ ، یک الگوریتم یادگیری ماشین آماری برای یادگیری متریک است. | ## بخش 1: نزدیک‌ترین همسایه حاشیه بزرگ | این الگوریتم مبتنی بر برنامه‌نویسی نیمه معین است، یک زیرکلاس از بهینه‌سازی محدب است. هدف یادگیری نظارت شده (به‌طور خاص طبقه‌بندی) یادگیری یک قانون تصمیم‌گیری است که می‌تواند نمونه‌های داده را در کلاس‌های از پیش تعریف شده طبقه‌بندی کند. قانون k-نزدیکترین همسایه یک مجموعه داده آموزشی از نمونه‌های برچسب‌گذاری شده را فرض می‌کند (یعنی کلاس‌ها شناخته شده‌اند). این مدل یک نمونه داده جدید را با کلاس به دست آمده از رای اکثریت k نزدیک‌ترین نمونه‌های آموزشی (برچسب‌دار) طبقه‌بندی می‌کند. نزدیک‌ترین همسایه‌های حاشیه بزرگ الگوریتمی است که این معیار کلی (شبه) را به صورت نظارت شده می‌آموزد تا دقت طبقه قانون k-نزدیک‌ترین همسایه را بهبود بخشد. راه‌اندازی شهود اصلی پشت LMNN یادگیری یک شبه متری است که تحت آن تمام نمونه‌های داده در مجموعه آموزشی توسط حداقل k نمونه احاطه شده‌اند که برچسب کلاس یکسانی دارند. اگر این امر محقق شود، خطای باقی‌مانده (یک مورد خاص از اعتبارسنجی متقابل) به حداقل می‌رسد. فرض کنید داده‌های آموزشی از یک مجموعه داده تشکیل شده باشد ، که در آن مجموعه دسته‌بندی‌های کلاس ممکن، است. در حالت اقلیدسی، این مجموعه یک دایره است، در حالی که تحت متریک اصلاح شده (ماهالانوبیس) به یک بیضی تبدیل می‌شود. این الگوریتم بین دو نوع نقاط داده خاص تمایز قائل می‌شود: همسایه‌های هدف و فریبکارها. | ## بخش 2: نزدیک‌ترین همسایه حاشیه بزرگ | همسایه‌های هدف، نقاط داده‌ای هستند که باید تحت متریک آموخته‌شده به نزدیک‌ترین همسایه تبدیل شوند. فریب دهنده‌ها فریب دهنده یک نقطه داده نقطه داده دیگری است با برچسب کلاس متفاوت (به عنوان مثال ) که یکی از نزدیک‌ترین همسایگان است. در طول یادگیری، الگوریتم سعی می‌کند تعداد تقلب‌کننده‌ها را برای تمام نمونه‌های داده در مجموعه آموزشی به حداقل برساند. الگوریتم حاشیه بزرگ نزدیک‌ترین همسایگان ماتریس را به کمک برنامه‌نویسی نیمه معین بهینه می‌کند. هدف دوگانه است: برای هر نقطه داده همسایه‌های هدف باید نزدیک و متقلبها باید دور باشند. متریک آموخته‌شده سبب می‌شود بردار ورودی توسط نمونه‌های آموزشی از همان کلاس احاطه شود. اولین هدف بهینه‌سازی با کمینه کردن میانگین فاصله بین نمونه‌ها و همسایه‌های هدف آن‌ها به دست می‌آید. هدف دوم با جریمه کردن فاصله‌ها به فریبکاران که کمتر از یک واحد دورتر از همسایه‌های هدف هستند (و بنابراین آنها را از همسایگی محلی خارج می‌کنند) به دست می‌آید. مقدار حاصل که باید به حداقل برسد را می‌توان به صورت زیر بیان کرد: با عملکرد از دست دادن لولا ، که تضمین می‌کند نزدیکی متقلب در خارج از حاشیه جریمه نمی‌شود. مسئله بهینه‌سازی نهایی به صورت زیر است: هایپرپارامتر یک ثابت مثبت است (معمولاً از طریق اعتبارسنجی متقابل تنظیم می‌شود). | ## بخش 3: نزدیک‌ترین همسایه حاشیه بزرگ | در اینجا متغیرهای (در مجموع با دو نوع محدودیت) عبارت تابع هزینه را جایگزین می‌کنند. آن‌ها نقشی شبیه به متغیرهای سست برای جذب میزان نقض محدودیت‌های فریبنده ایفا می‌کنند. اگرچه SDPها از پیچیدگی محاسباتی بالایی رنج می‌برند، این نمونه SDP خاص به دلیل ویژگی‌های هندسی اساسی مسئله به‌طور بسیار کارآمدی می‌تواند حل شود. به‌طور خاص، اکثر محدودیت‌های فریبنده به‌طور طبیعی برآورده می‌شوند و نیازی به اعمال آنها در طول زمان اجرا نیست (یعنی مجموعه متغیرها تنک است). یک تکنیک حل‌کننده بسیار مناسب، روش مجموعه کاری است که مجموعه کوچکی از محدودیت‌ها را نگه می‌دارد که به‌طور فعال اعمال می‌شوند و محدودیت‌های باقی‌مانده (احتمالا ارضا شده) را تنها گاهی برای اطمینان از درستی نظارت می‌کند. برنامه‌های افزودنی و حل کننده‌های کارآمد LMNN در مقاله سال ۲۰۰۸ به چندین معیار محلی تعمیم داده شد. این گسترش به‌طور قابل توجهی خطای طبقه‌بندی را بهبود می‌بخشد، اما شامل یک مسئله بهینه‌سازی گران‌تر است. واینبرگر و ساول در مقاله سال ۲۰۰۹ خود در مجله تحقیقات یادگیری ماشین یک حل کننده کارآمد برای برنامه نیمه معین استخراج کردند. این برنامه می‌تواند یک متریک برای مجموعه داده‌های رقمی دست‌نویس MNIST در چندین ساعت بیاموزد که شامل میلیاردها محدودیت جفتی است. | ## جمع‌بندی | کومال و همکارانش این الگوریتم را گسترش دادند تا متغییرهای محلی را با تبدیل‌های چندجمله‌ای چندمتغیره ترکیب کرده و منظم‌سازی را بهبود بخشند.