نزدیک‌ترین همسایه حاشیه بزرگ

**طبقه‌بندی نزدیک‌ترین همسایه حاشیه بزرگ** ، یک الگوریتم یادگیری ماشین آماری برای یادگیری متریک است. این یک شبه متریک طراحی شده برای طبقه‌بندی k-نزدیک‌ترین همسایه را می‌آموزد. این الگوریتم مبتنی بر برنامه‌نویسی نیمه معین است، یک زیرکلاس از بهینه‌سازی محدب است.

هدف یادگیری نظارت شده (به‌طور خاص طبقه‌بندی) یادگیری یک قانون تصمیم‌گیری است که می‌تواند نمونه‌های داده را در کلاس‌های از پیش تعریف شده طبقه‌بندی کند. قانون k-نزدیکترین همسایه یک مجموعه داده *آموزشی* از نمونه‌های برچسب‌گذاری شده را فرض می‌کند (یعنی کلاس‌ها شناخته شده‌اند). این مدل یک نمونه داده جدید را با کلاس به دست آمده از رای اکثریت k نزدیک‌ترین نمونه‌های آموزشی (برچسب‌دار) طبقه‌بندی می‌کند. نزدیکی با یک متریک از پیش تعریف شده اندازه‌گیری می‌شود. نزدیک‌ترین همسایه‌های حاشیه بزرگ الگوریتمی است که این معیار کلی (شبه) را به صورت نظارت شده می‌آموزد تا دقت طبقه قانون k-نزدیک‌ترین همسایه را بهبود بخشد.

## راه‌اندازی
شهود اصلی پشت LMNN یادگیری یک شبه متری است که تحت آن تمام نمونه‌های داده در مجموعه آموزشی توسط حداقل k نمونه احاطه شده‌اند که برچسب کلاس یکسانی دارند. اگر این امر محقق شود، خطای باقی‌مانده (یک مورد خاص از اعتبارسنجی متقابل) به حداقل می‌رسد. فرض کنید داده‌های آموزشی از یک مجموعه داده تشکیل شده باشد  D=\{(\vec x_1,y_1),\dots,(\vec x_n,y_n)\}\subset R^d\times C ، که در آن مجموعه دسته‌بندی‌های کلاس ممکن، C=\{1,\dots,c\} است.

این الگوریتم یک شبه متریک از نوع را می‌آموزد

: d(\vec x_i,\vec x_j)=(\vec x_i-\vec x_j)^\top\mathbf{M}(\vec x_i-\vec x_j) .

برای d(\cdot,\cdot) به خوبی تعریف شود، ماتریس \mathbf{M} باید نیمه قطعی مثبت باشد. معیار اقلیدسی یک مورد خاص است که در آن \mathbf{M} ماتریس هویت است. این تعمیم اغلب (به غلط) به عنوان معیار ماهالانوبیس شناخته می‌شود.

شکل ۱ اثر متریک تحت تغییر \mathbf{M} را نشان می‌دهد. دو دایره مجموعه ای از نقاط با فاصله مساوی از مرکز را نشان می‌دهند \vec x_i . در حالت اقلیدسی، این مجموعه یک دایره است، در حالی که تحت متریک اصلاح شده (ماهالانوبیس) به یک بیضی تبدیل می‌شود.
بندانگشتی|300x300پیکسل| شکل ۱: تصویر شماتیک LMNN.
این الگوریتم بین دو نوع نقاط داده خاص تمایز قائل می‌شود: *همسایه‌های هدف* و *فریبکارها*.

### همسایه‌های هدف
همسایه‌های هدف قبل از یادگیری انتخاب می‌شوند. هر نمونه \vec x_i دقیقاً k همسایه هدف مختلف داخل D دارد، که همه دارای یک برچسب کلاس y_i هستند. همسایه‌های هدف، نقاط داده‌ای هستند که *باید تحت متریک آموخته‌شده به* نزدیک‌ترین همسایه تبدیل شوند. فرض کنید مجموعه ای از همسایه‌های هدف را برای یک نقطه داده مشخص کنیم \vec x_i مانند N_i .

### فریب دهنده‌ها
فریب دهنده یک نقطه داده \vec x_i نقطه داده دیگری است \vec x_j با برچسب کلاس متفاوت (به عنوان مثال y_i\neq y_j) که یکی از نزدیک‌ترین همسایگان \vec x_i است. در طول یادگیری، الگوریتم سعی می‌کند تعداد تقلب‌کننده‌ها را برای تمام نمونه‌های داده در مجموعه آموزشی به حداقل برساند.

## الگوریتم
حاشیه بزرگ نزدیک‌ترین همسایگان ماتریس \mathbf{M}  را به کمک برنامه‌نویسی نیمه معین بهینه می‌کند. هدف دوگانه است: برای هر نقطه داده \vec x_i *همسایه‌های هدف* باید *نزدیک* و *متقلبها* باید *دور* باشند. شکل ۱ تأثیر چنین بهینه‌سازی را بر یک مثال گویا نشان می‌دهد. متریک آموخته‌شده سبب می‌شود بردار ورودی \vec x_i توسط نمونه‌های آموزشی از همان کلاس احاطه شود. اگر یک نقطه تست بود، به درستی تحت قانون نزدیک‌ترین همسایه با  k=3 طبقه‌بندی می‌شد.

اولین هدف بهینه‌سازی با کمینه کردن میانگین فاصله بین نمونه‌ها و همسایه‌های هدف آن‌ها به دست می‌آید.

: \sum_{i,j\in N_i} d(\vec x_i,\vec x_j) .

هدف دوم با جریمه کردن فاصله‌ها به فریبکاران  \vec x_l که کمتر از یک واحد دورتر از همسایه‌های هدف \vec x_j هستند (و بنابراین آنها را از همسایگی محلی \vec x_i  خارج می‌کنند) به دست می‌آید. مقدار حاصل که باید به حداقل برسد را می‌توان به صورت زیر بیان کرد:

: \sum_{i,j \in N_i,l, y_l\neq y_i}[d(\vec x_i,\vec x_j)+1-d(\vec x_i,\vec x_l)]_{+}

با عملکرد از دست دادن لولا [\cdot]_{+}=\max(\cdot,0) ، که تضمین می‌کند نزدیکی متقلب در خارج از حاشیه جریمه نمی‌شود. حاشیه دقیقاً یک واحد مقیاس ماتریس  M را اصلاح می‌کند. هر انتخاب جایگزین c>0 منجر به تغییر مقیاس  M با ضریب 1/c می‌شود.

مسئله بهینه‌سازی نهایی به صورت زیر است:

:  \min_{\mathbf{M}} \sum_{i,j\in N_i} d(\vec x_i,\vec x_j) + \lambda\sum_{i,j,l} \xi_{ijl}
: \forall_{i,j \in N_i,l, y_l\neq y_i} 
:   d(\vec x_i,\vec x_j)+1-d(\vec x_i,\vec x_l)\leq \xi_{ijl}
:  \xi_{ijl}\geq 0
:  \mathbf{M}\succeq 0

هایپرپارامتر \lambda>0 یک ثابت مثبت است (معمولاً از طریق اعتبارسنجی متقابل تنظیم می‌شود). در اینجا متغیرهای \xi_{ijl} (در مجموع با دو نوع محدودیت) عبارت تابع هزینه را جایگزین می‌کنند. آن‌ها نقشی شبیه به متغیرهای سست برای جذب میزان نقض محدودیت‌های فریبنده ایفا می‌کنند. آخرین محدودیت تضمین می‌کند که m نیمه متناهی مثبت است. مسئله بهینه‌سازی نمونه ای از برنامه‌نویسی نیمه معین (SDP) است. اگرچه SDPها از پیچیدگی محاسباتی بالایی رنج می‌برند، این نمونه SDP خاص به دلیل ویژگی‌های هندسی اساسی مسئله به‌طور بسیار کارآمدی می‌تواند حل شود. به‌طور خاص، اکثر محدودیت‌های فریبنده به‌طور طبیعی برآورده می‌شوند و نیازی به اعمال آنها در طول زمان اجرا نیست (یعنی مجموعه متغیرها \xi_{ijl} تنک است). یک تکنیک حل‌کننده بسیار مناسب، روش مجموعه کاری است که مجموعه کوچکی از محدودیت‌ها را نگه می‌دارد که به‌طور فعال اعمال می‌شوند و محدودیت‌های باقی‌مانده (احتمالا ارضا شده) را تنها گاهی برای اطمینان از درستی نظارت می‌کند.

## برنامه‌های افزودنی و حل کننده‌های کارآمد
LMNN در مقاله سال ۲۰۰۸ به چندین معیار محلی تعمیم داده شد. این گسترش به‌طور قابل توجهی خطای طبقه‌بندی را بهبود می‌بخشد، اما شامل یک مسئله بهینه‌سازی گران‌تر است. واینبرگر و ساول در مقاله سال ۲۰۰۹ خود در مجله تحقیقات یادگیری ماشین یک حل کننده کارآمد برای برنامه نیمه معین استخراج کردند. این برنامه می‌تواند یک متریک برای مجموعه داده‌های رقمی دست‌نویس MNIST در چندین ساعت بیاموزد که شامل میلیاردها محدودیت جفتی است. یک پیاده‌سازی متن باز Matlab به صورت رایگان در صفحه وب نویسندگان در دسترس است.

کومال و همکارانش این الگوریتم را گسترش دادند تا متغییرهای محلی را با تبدیل‌های چندجمله‌ای چندمتغیره ترکیب کرده و منظم‌سازی را بهبود بخشند.

## جستارهای وابسته

* یادگیری مشابه
* آنالیز افتراقی خطی
* شبه‌متریک
* جستجوی نزدیکترین همسایه
* خوشه‌بندی
* طبقه‌بندی آماری
* داده‌کاوی
* یادگیری ماشینی
* بازشناخت الگو
* تحلیل پیشگویانه
* کاهش ابعاد

## منابع


## پیوند به بیرون
* پیاده‌سازی متلب
* ICML 2010 Tutorial on Metric Learning

رده:الگوریتم‌های دسته‌بندی
رده:یادگیری ماشین