MetricLearning Part3

### یادگیری متریک: تطبیق معیار فاصله با داده #### خلاصه‌ای از یادگیری متریک در بسیاری از مسائل یادگیری ماشین، موفقیت الگوریتم به شدت به انتخاب یک معیار فاصله مناسب بستگی دارد. فاصله اقلیدسی معمولی، اگرچه ساده و پرکاربرد است، اغلب نمی‌تواند ساختار واقعی و معنایی داده‌ها را به خوبی منعکس کند. به عنوان مثال، در تشخیص چهره، ممکن است دو تصویر از یک شخص در شرایط نوری متفاوت از نظر فاصله اقلیدسی بسیار دور باشند، در حالی که دو تصویر از دو شخص متفاوت اما با لباس‌های مشابه، فاصله نزدیکی نشان دهند. یادگیری متریک (Metric Learning) دقیقاً برای حل این مشکل طراحی شده است. هدف آن «یاد گرفتن» یک معیار فاصله سفارشی از روی داده‌ها است، به گونه‌ای که این معیار جدید، شباهت‌های معنایی مورد نظر ما را منعکس کند. این کار معمولاً با استفاده از «اطلاعات جانبی» انجام می‌شود. این اطلاعات یا به شکل جفت‌های «باید-مشابه» (نمونه‌هایی که باید به هم نزدیک باشند) و «نباید-نامشابه» (نمونه‌هایی که باید از هم دور باشند) هستند، یا به شکل قیود نسبی سه‌تایی (مثلاً «x به y شبیه‌تر است تا به z»). الگوریتم یادگیری متریک، پارامترهای یک تابع فاصله (مانند ماتریس در فاصله ماهالانوبیس) را طوری تنظیم می‌کند که بیشترین سازگاری را با این قیود داشته باشد. شکل زیر، این مفهوم را برای داده‌های چهره به خوبی نشان می‌دهد: در فضای اولیه، نقاط یک شخص (سبز) پراکنده و با نقاط شخص دیگر (قرمز) درهم هستند، اما پس از یادگیری متریک، نقاط هم‌کلاس به هم نزدیک و دسته‌های مجزا تشکیل می‌شوند. #### متریک‌ها و تعاریف پایه یک تابع فاصله واقعی باید چهار شرط اصلی را برآورده کند: نامنفی بودن (فاصله هرگز منفی نیست)، تشخص (فاصله دو نقطه فقط در صورت یکی بودنشان صفر است)، تقارن (فاصله a از b با فاصله b از a برابر است)، و نامساوی مثلث (رفتن مستقیم از a به c کوتاه‌تر یا مساوی رفتن از a به b و سپس b به c است). در مقابل، یک «شبه-فاصله» شرط دوم را کمی نادیده می‌گیرد و اجازه می‌دهد دو نقطه متفاوت نیز فاصله صفر داشته باشند. برای مثال، اگر فاصله را بر اساس «تعداد کفش‌های همرنگ» دو نفر تعریف کنیم، ممکن است دو فرد متفاوت فاصله صفر داشته باشند، در حالی که خودشان یکسان نیستند. در میان فاصله‌های مختلف، «فاصله ماهالانوبیس» محبوبیت ویژه‌ای در یادگیری متریک دارد. این فاصله، حالت تعمیم‌یافته فاصله اقلیدسی است و با یک ماتریس نیمه‌معین مثبت (به نام ماتریس M) پارامتری می‌شود. قدرت آن در این است که می‌تواند مقیاس و همبستگی بین ویژگی‌های مختلف داده را به طور خودکار یاد بگیرد. به طور شهودی، فاصله ماهالانوبیس معادل این است که ابتدا داده‌ها را با یک تبدیل خطی (مانند چرخش و مقیاس‌گذاری) به فضای جدیدی ببریم و سپس در آنجا فاصله اقلیدسی را محاسبه کنیم. ماتریس M می‌تواند «رتبه کامل» باشد، به این معنی که داده‌ها را در همان ابعاد اولیه تغییر شکل می‌دهد، یا «رتبه پایین» باشد که در این صورت، همزمان با یادگیری فاصله، ابعاد داده‌ها را نیز کاهش می‌دهد. #### الگوریتم‌های کلیدی یادگیری متریک خطی روش «تحلیل مؤلفه‌های همسایگی» (NCA) گام مهمی بود، زیرا به طور مستقیم عملکرد طبقه‌بند «k-نزدیک‌ترین همسایه» (k-NN) را بهینه می‌کند. ایده اصلی NCA این است که به جای انتخاب قطعی همسایه‌ها، یک قانون تصادفی بر اساس فاصله ماهالانوبیس تعریف کند: هر نقطه با احتمالی که به فاصله آن از نقطه مورد نظر بستگی دارد، به عنوان همسایه انتخاب می‌شود. سپس هدف، بیشینه‌سازی احتمال این است که همسایه‌های انتخاب‌شده، برچسب درستی داشته باشند. مزیت NCA، بهینه‌سازی مستقیم دقت طبقه‌بندی و قابلیت کاهش ابعاد ذاتی آن است. عیب اصلی‌اش، غیرمحدب بودن تابع هدف است؛ به این معنی که ممکن است الگوریتم در یک پاسخ خوب محلی گیر کند و به مقدار اولیه پارامترها حساس باشد. اما محبوب‌ترین و تأثیرگذارترین الگوریتم در این حوزه، «همسایگان نزدیک با حاشیه بزرگ» (LMNN) است. LMNN نیز برای بهبود کارایی طبقه‌بند k-NN طراحی شده، اما از یک ایده متفاوت و مبتنی بر «حاشیه» استفاده می‌کند. برای هر نقطه، ابتدا تعدادی «همسایه هدف» (چند نقطه نزدیک از همان کلاس) تعیین می‌شود. سپس، الگوریتم سعی می‌کند فاصله نقاط تا همسایه‌های هدف خود را کمینه کند، در حالی که شرط می‌کند که نقاط کلاس‌های دیگر (مهاجمان) با یک حاشیه اطمینان (مثلاً یک واحد) از این همسایه‌های هدف دورتر باشند. این کار از طریق یک مسئله بهینه‌سازی محدب حل می‌شود که تضمین می‌کند پاسخ نهایی، پاسخ سراسری بهینه است. شکل LMNN در متن، این مفهوم را به خوبی نشان می‌دهد: هر نمونه سعی می‌کند همسایگان هدف خود را جذب کند و مهاجمان را دفع نماید. #### منظم‌سازی و کارایی محاسباتی علاوه بر مسئله بیش‌برازش، چالش عمده دیگر، هزینه بالای محاسباتی اطمینان از «نیمه‌معین مثبت» بودن ماتریس M در حین بهینه‌سازی است. روش‌های معمولی برای این کار نیاز به انجام تجزیه مقدار ویژه (محاسباتی با درجه سه نسبت به ابعاد داده) در هر گام بهینه‌سازی دارند که برای ابعاد بالا (مثلاً بیش از ۱۰۰۰ ویژگی) بسیار گران است. روش S&J یک راه حل هوشمندانه ارائه می‌دهد: به جای بهینه‌سازی مستقیم ماتریس M، آن را به صورت حاصلضرب سه ماتریس پارامتری می‌کند که در آن، ماتریس میانی، قطری و با درایه‌های نامنفی است. با این کار، شرط نیمه‌معین مثبت بودن ماتریس M به طور خودکار برقرار می‌شود و دیگر نیازی به عملیات پرهزینه تجزیه مقدار ویژه در هر تکرار نیست. این تکنیک که «اجتناب از تصویر روی مخروط» نامیده می‌شود، یک پیشرفت محاسباتی بزرگ محسوب می‌شود و یادگیری متریک را برای مسائل با ابعاد بالا عملی می‌سازد.