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

طبقه‌بندی نزدیک‌ترین همسایه حاشیه بزرگ (به انگلیسی: Large Margin Nearest Neighbor Classification)^[۱]، یک الگوریتم یادگیری ماشین آماری برای یادگیری متریک است. این یک شبه متریک طراحی شده برای طبقه‌بندی 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}$ . در حالت اقلیدسی، این مجموعه یک دایره است، در حالی که تحت متریک اصلاح شده (ماهالانوبیس) به یک بیضی تبدیل می‌شود.

شکل ۱: تصویر شماتیک 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})]_{+}

با عملکرد از دست دادن لولا ${\textstyle [\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

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

برنامه‌های افزودنی و حل کننده‌های کارآمد

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

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

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

منابع

↑ Weinberger, K. Q.; Blitzer J. C.; Saul L. K. (2006). "Distance Metric Learning for Large Margin Nearest Neighbor Classification". Advances in Neural Information Processing Systems. 18: 1473–1480.
↑ Weinberger, K. Q.; Saul L. K. (2008). "Fast solvers and efficient implementations for distance metric learning" (PDF). Proceedings of International Conference on Machine Learning: 1160–1167. Archived from the original (PDF) on 2011-07-24. Retrieved 2010-07-14.
↑ Weinberger, K. Q.; Saul L. K. (2009). "Distance Metric Learning for Large Margin Classification" (PDF). Journal of Machine Learning Research. 10: 207–244.
↑ Kumar, M.P.; Torr P.H.S.; Zisserman A. (2007). "An invariant large margin nearest neighbour classifier". IEEE 11th International Conference on Computer Vision (ICCV), 2007: 1–8. doi:10.1109/ICCV.2007.4409041. ISBN 978-1-4244-1630-1.

پیوند به بیرون

[Weinberger05-1] Weinberger, K. Q.; Blitzer J. C.; Saul L. K. (2006). "Distance Metric Learning for Large Margin Nearest Neighbor Classification". Advances in Neural Information Processing Systems. 18: 1473–1480.

[Weinberger08-2] Weinberger, K. Q.; Saul L. K. (2008). "Fast solvers and efficient implementations for distance metric learning" (PDF). Proceedings of International Conference on Machine Learning: 1160–1167. Archived from the original (PDF) on 2011-07-24. Retrieved 2010-07-14.

[Weinberger09-3] Weinberger, K. Q.; Saul L. K. (2009). "Distance Metric Learning for Large Margin Classification" (PDF). Journal of Machine Learning Research. 10: 207–244.

[kumar07-4] Kumar, M.P.; Torr P.H.S.; Zisserman A. (2007). "An invariant large margin nearest neighbour classifier". IEEE 11th International Conference on Computer Vision (ICCV), 2007: 1–8. doi:10.1109/ICCV.2007.4409041. ISBN 978-1-4244-1630-1.

[۱]

[۲]

[۳]

[۴]