نزدیک‌ترین همسایه حاشیه بزرگ کیست؟ توضیح بده.
طبقه‌بندی نزدیک‌ترین همسایه حاشیه بزرگ ، یک الگوریتم یادگیری ماشین آماری برای یادگیری متریک است. این یک شبه متریک طراحی شده برای طبقه‌بندی k-نزدیک‌ترین همسایه را می‌آموزد. این الگوریتم مبتنی بر برنامه‌نویسی نیمه معین است، یک زیرکلاس از بهینه‌سازی محدب است.هدف یادگیری نظارت شده (به‌طور خاص طبقه‌بندی) یادگیری یک قانون تصمیم‌گیری است که می‌تواند نمونه‌های داده را در کلاس‌های از پیش تعریف شده طبقه‌بندی کند. قانون k-نزدیکترین همسایه یک مجموعه داده "آموزشی" از نمونه‌های برچسب‌گذاری شده را فرض می‌کند (یعنی کلاس‌ها شناخته شده‌اند). این مدل یک نمونه داده جدید را با کلاس به دست آمده از رای اکثریت k نزدیک‌ترین نمونه‌های آموزشی (برچسب‌دار) طبقه‌بندی می‌کند. نزدیکی با یک متریک از پیش تعریف شده اندازه‌گیری می‌شود. نزدیک‌ترین همسایه‌های حاشیه بزرگ الگوریتمی است که این معیار کلی (شبه) را به صورت نظارت شده می‌آموزد تا دقت طبقه قانون k-نزدیک‌ترین همسایه را بهبود بخشد.راه‌اندازی.شهود اصلی پشت LMNN یادگیری یک شبه متری است که تحت آن تمام نمونه‌های داده در مجموعه آموزشی توسط حداقل k نمونه احاطه شده‌اند که برچسب کلاس یکسانی دارند. اگر این امر محقق شود، خطای باقی‌مانده (یک مورد خاص از اعتبارسنجی متقابل) به حداقل می‌رسد. فرض کنید داده‌های آموزشی از یک مجموعه داده تشکیل شده باشد formula_1 ، که در آن مجموعه دسته‌بندی‌های کلاس ممکن، formula_2 است.این الگوریتم یک شبه متریک از نوع را می‌آموزدبرای formula_4 به خوبی تعریف شود، ماتریس formula_5 باید نیمه قطعی مثبت باشد. معیار اقلیدسی یک مورد خاص است که در آن formula_5 ماتریس هویت است. این تعمیم اغلب (به غلط) به عنوان معیار ماهالانوبیس شناخته می‌شود.شکل ۱ اثر متریک تحت تغییر formula_5 را نشان می‌دهد. دو دایره مجموعه ای از نقاط با فاصله مساوی از مرکز را نشان می‌دهند formula_8 . در حالت اقلیدسی، این مجموعه یک دایره است، در حالی که تحت متریک اصلاح شده (ماهالانوبیس) به یک بیضی تبدیل می‌شود.این الگوریتم بین دو نوع نقاط داده خاص تمایز قائل می‌شود: "همسایه‌های هدف" و "فریبکارها".همسایه‌های هدف.همسایه‌های هدف قبل از یادگیری انتخاب می‌شوند. هر نمونه formula_8 دقیقاً formula_10 همسایه هدف مختلف داخل formula_11 دارد، که همه دارای یک برچسب کلاس formula_12 هستند. همسایه‌های هدف، نقاط داده‌ای هستند که "باید تحت متریک آموخته‌شده به" نزدیک‌ترین همسایه تبدیل شوند. فرض کنید مجموعه ای از همسایه‌های هدف را برای یک نقطه داده مشخص کنیم formula_8 مانند formula_14 .فریب دهنده‌ها.فریب دهنده یک نقطه داده formula_8 نقطه داده دیگری است formula_16 با برچسب کلاس متفاوت (به عنوان مثال formula_17) که یکی از نزدیک‌ترین همسایگان formula_8 است. در طول یادگیری، الگوریتم سعی می‌کند تعداد تقلب‌کننده‌ها را برای تمام نمونه‌های داده در مجموعه آموزشی به حداقل برساند.الگوریتم.حاشیه بزرگ نزدیک‌ترین همسایگان ماتریس formula_5 را به کمک برنامه‌نویسی نیمه معین بهینه می‌کند. هدف دوگانه است: برای هر نقطه داده formula_8 "همسایه‌های هدف" باید "نزدیک" و "متقلبها" باید "دور" باشند. شکل ۱ تأثیر چنین بهینه‌سازی را بر یک مثال گویا نشان می‌دهد. متریک آموخته‌شده سبب می‌شود بردار ورودی formula_8 توسط نمونه‌های آموزشی از همان کلاس احاطه شود. اگر یک نقطه تست بود، به درستی تحت قانون نزدیک‌ترین همسایه با formula_22 طبقه‌بندی می‌شد.اولین هدف بهینه‌سازی با کمینه کردن میانگین فاصله بین نمونه‌ها و همسایه‌های هدف آن‌ها به دست می‌آید.هدف دوم با جریمه کردن فاصله‌ها به فریبکاران formula_24 که کمتر از یک واحد دورتر از همسایه‌های هدف formula_16 هستند (و بنابراین آنها را از همسایگی محلی formula_8 خارج می‌کنند) به دست می‌آید. مقدار حاصل که باید به حداقل برسد را می‌توان به صورت زیر بیان کرد:با عملکرد از دست دادن لولا formula_28 ، که تضمین می‌کند نزدیکی متقلب در خارج از حاشیه جریمه نمی‌شود. حاشیه دقیقاً یک واحد مقیاس ماتریس formula_29 را اصلاح می‌کند. هر انتخاب جایگزین formula_30 منجر به تغییر مقیاس formula_29 با ضریب formula_32 می‌شود.مسئله بهینه‌سازی نهایی به صورت زیر است:هایپرپارامتر formula_38 یک ثابت مثبت است (معمولاً از طریق اعتبارسنجی متقابل تنظیم می‌شود). در اینجا متغیرهای formula_39 (در مجموع با دو نوع محدودیت) عبارت تابع هزینه را جایگزین می‌کنند. آن‌ها نقشی شبیه به متغیرهای سست برای جذب میزان نقض محدودیت‌های فریبنده ایفا می‌کنند. آخرین محدودیت تضمین می‌کند که m نیمه متناهی مثبت است. مسئله بهینه‌سازی نمونه ای از برنامه‌نویسی نیمه معین (SDP) است. اگرچه SDPها از پیچیدگی محاسباتی بالایی رنج می‌برند، این نمونه SDP خاص به دلیل ویژگی‌های هندسی اساسی مسئله به‌طور بسیار کارآمدی می‌تواند حل شود. به‌طور خاص، اکثر محدودیت‌های فریبنده به‌طور طبیعی برآورده می‌شوند و نیازی به اعمال آنها در طول زمان اجرا نیست (یعنی مجموعه متغیرها formula_39 تنک است). یک تکنیک حل‌کننده بسیار مناسب، روش مجموعه کاری است که مجموعه کوچکی از محدودیت‌ها را نگه می‌دارد که به‌طور فعال اعمال می‌شوند و محدودیت‌های باقی‌مانده (احتمالا ارضا شده) را تنها گاهی برای اطمینان از درستی نظارت می‌کند.برنامه‌های افزودنی و حل کننده‌های کارآمد.LMNN در مقاله سال ۲۰۰۸ به چندین معیار محلی تعمیم داده شد. این گسترش به‌طور قابل توجهی خطای طبقه‌بندی را بهبود می‌بخشد، اما شامل یک مسئله بهینه‌سازی گران‌تر است. واینبرگر و ساول در مقاله سال ۲۰۰۹ خود در مجله تحقیقات یادگیری ماشین یک حل کننده کارآمد برای برنامه نیمه معین استخراج کردند. این برنامه می‌تواند یک متریک برای مجموعه داده‌های رقمی دست‌نویس MNIST در چندین ساعت بیاموزد که شامل میلیاردها محدودیت جفتی است. یک پیاده‌سازی متن باز Matlab به صورت رایگان در صفحه وب نویسندگان در دسترس است.کومال و همکارانش این الگوریتم را گسترش دادند تا متغییرهای محلی را با تبدیل‌های چندجمله‌ای چندمتغیره ترکیب کرده و منظم‌سازی را بهبود بخشند.