Skip to content
بازگشت به نتایج جست‌وجو

یادگیری فعال با نزدیک‌ترین همسایگان (K-Nearest Neighbors)

معرفی‌شده توسط
Settles, B. (active learning framework); Fix & Hodges (KNN base)
سال
1951–2010
نوع
Active learning with KNN base learner
خانواده
Machine learning

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

یادگیری فعال با نزدیک‌ترین همسایگان، پیش‌بینی مبتنی بر نمونه‌ی KNN را با یک استراتژی پرس‌وجوی تکراری ترکیب می‌کند که آموزنده‌ترین نمونه‌های بدون برچسب را برای حاشیه‌نویسی انتخاب می‌کند. این مدل تنها برای نمونه‌هایی که حاشیه‌های رأی‌گیری همسایگی در آن‌ها کمترین است، برچسب درخواست می‌کند و با تعداد بسیار کمتری از نمونه‌های برچسب‌دار نسبت به KNN کاملاً نظارت‌شده در داده‌های جدولی، به دقت رقابتی دست می‌یابد.

شهود پشت روش

KNN با بررسی k نزدیک‌ترین همسایگان برچسب‌دار خود و رأی اکثریت، یک نقطه را طبقه‌بندی می‌کند. هنگامی که این همسایگان تقریباً به طور مساوی بین کلاس‌ها تقسیم شده‌اند، مدل واقعاً نامطمئن است - و این عدم قطعیت مشخص می‌کند که کدام نمونه بدون برچسب بیشترین ارزش را برای برچسب‌گذاری دارد. یادگیری فعال از این سیگنال بهره می‌برد: در هر تکرار، الگوریتم نقطه‌ی بدون برچسبی را پیدا می‌کند که همسایگی آن بیشترین تقسیم‌بندی را دارد، از یک اوراکل می‌خواهد آن را برچسب‌گذاری کند، آن را به مجموعه‌ی برچسب‌دار اضافه می‌کند و تکرار می‌کند. نتیجه این است که تلاش برچسب‌گذاری در نزدیکی مرزهای تصمیم‌گیری متمرکز می‌شود، جایی که برچسب‌های جدید بیشترین آموزش را می‌دهند.

تاریخ

طبقه‌بند K-نزدیک‌ترین همسایگان ریشه در Fix و Hodges (1951) دارد و توسط Cover و Hart (1967) رسمی شد. یادگیری فعال به عنوان یک چارچوب اصولی به طور سیستماتیک توسط Burr Settles (2010) بررسی شد، که نمونه‌برداری عدم قطعیت مبتنی بر مجموعه، پرس‌وجو-توسط-کمیته، و استراتژی‌های وزن‌دار چگالی را مستند کرد. KNN از زمان کار بنیادی Cohn، Atlas و Ladner (1994) به عنوان یک یادگیرنده‌ی پایه در معیارهای یادگیری فعال مبتنی بر مجموعه حضور داشته است، که به دلیل سیگنال عدم قطعیت شفاف و هزینه‌ی صفر بازآموزی در هر تکرار ارزشمند است.

چه زمانی استفاده شود

هنگامی که داده‌های برچسب‌دار کمیاب یا به دست آوردن آن‌ها پرهزینه است، نمونه‌های بدون برچسب فراوان هستند، فضای ویژگی دارای ابعاد متوسط است و انتظار می‌رود مرز تصمیم‌گیری به صورت محلی هموار باشد، از یادگیری فعال با KNN استفاده کنید. این روش به ویژه در پروژه‌های طبقه‌بندی در مراحل اولیه که برچسب‌گذاری باید سهمیه‌بندی شود، عملی است. از آن در مواردی که مجموعه داده دارای ابعاد بسیار بالا است (معیارهای فاصله KNN در ابعاد بالا به دلیل نفرین ابعاد تخریب می‌شوند)، زمانی که مجموعه‌ی برچسب‌دار از قبل بزرگ است (KNN منفعل کافی است)، زمانی که پیش‌بینی با تأخیر کم در مقیاس مورد نیاز است (پیش‌بینی KNN برای اندازه‌ی مجموعه‌ی برچسب‌دار O(n) است)، یا زمانی که بودجه‌ی برچسب‌گذاری آنقدر کوچک است که تخمین‌های همسایگی قابل اعتماد نیستند، اجتناب کنید.

محدودیت‌ها و ملاحظات

  • هزینه‌ی پیش‌بینی با اندازه‌ی مجموعه‌ی برچسب‌دار به صورت خطی مقیاس می‌شود و باعث می‌شود استنتاج با رشد مجموعه در طول تکرارها کند شود.
  • تخمین عدم قطعیت مبتنی بر فاصله به دلیل نفرین ابعاد در فضاهای با ابعاد بالا به شدت تخریب می‌شود.
  • سقف دقت KNN پایین‌تر از روش‌های گروهی است؛ استراتژی فعال نمی‌تواند ظرفیت محدود یادگیرنده‌ی پایه را جبران کند.
  • به انتخاب k و معیار فاصله حساس است؛ پیش‌فرض‌های ضعیف منجر به تخمین‌های عدم قطعیت غیرقابل اعتماد می‌شود.
  • تمام نقاط برچسب‌دار در حافظه ذخیره می‌شوند؛ بودجه‌های بزرگ منجر به مصرف بالای حافظه می‌شوند.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • غیر پارامتری و بدون فرض: هیچ فرض توزیعی در مورد داده‌ها لازم نیست.
  • تخمین عدم قطعیت طبیعی و قابل تفسیر است - مستقیماً تقسیم آراء در میان نزدیک‌ترین همسایگان را منعکس می‌کند.
  • یادگیری تنبل به معنای عدم وجود هزینه‌ی بازآموزی در هر تکرار است؛ افزودن یک نقطه‌ی برچسب‌دار جدید بلافاصله مدل را به‌روز می‌کند.
  • در متمرکز کردن برچسب‌ها در نزدیکی مرزهای تصمیم‌گیری مؤثر است و وضوح مرزی خوبی با حاشیه‌نویسی‌های کم به دست می‌آورد.
  • در داده‌های جدولی با ابعاد متوسط با ویژگی‌های پیوسته و دودویی به خوبی کار می‌کند.

کاربردها

  • حاشیه‌نویسی سوابق پزشکی یا تصاویر که در آن زمان برچسب‌گذاری متخصص محدود است و مرزهای تصمیم‌گیری به صورت محلی هموار هستند.
  • طبقه‌بندی متن یا سند با مجموعه‌های کوچک برچسب‌دار و اسناد بدون برچسب فراوان با استفاده از فاصله‌های مبتنی بر جاسازی.
  • وظایف تشخیص خطا در سنسورها و صنعتی که تنها کسری از رویدادها قابل تأیید دستی هستند.
  • پیمایش‌های زیست‌محیطی که در آن تأیید میدانی برچسب‌های گونه‌ها پرهزینه و به صورت محلی خوشه‌بندی شده است.
  • طبقه‌بندهای نمونه‌ی اولیه در مراحل اولیه قبل از تغییر به یک مدل با ظرفیت بالاتر پس از جمع‌آوری برچسب‌های کافی.

چگونه کار می‌کند

چگونه کار می‌کند

1

مجموعه‌ی کوچکی از نمونه‌های برچسب‌دار اولیه برای شروع فرآیند، همراه با مجموعه‌ی بزرگ‌تری از نمونه‌های بدون برچسب، جمع‌آوری می‌شود. انتخاب تصادفی طبقه‌بندی‌شده توصیه می‌شود تا اطمینان حاصل شود که حداقل یک نمونه برای هر کلاس وجود دارد و به KNN یک همسایگی معنادار قبل از شروع حلقه‌ی فعال می‌دهد.

2

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

3

هر نمونه‌ی بدون برچسب با یک معیار اطلاع‌رسانی امتیازدهی می‌شود. نمونه‌برداری حاشیه‌ای، شکاف بین سهم آراء دو کلاس برتر را در میان k همسایه محاسبه می‌کند؛ نمونه‌برداری آنتروپی H(y-hat | x) را بر روی تمام نسبت‌های کلاس محاسبه می‌کند. نمونه با کمترین حاشیه یا بیشترین آنتروپی پرسیده می‌شود: x* = argmax H(y-hat | x).

فرمول
x^* = \arg\max_{x \in U} H(\hat{y} \mid x)
4

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

5

از آنجایی که KNN یک یادگیرنده‌ی تنبل است، هیچ بازآموزی صریحی لازم نیست؛ مجموعه‌ی برچسب‌دار گسترش‌یافته بلافاصله مدل جدید را تشکیل می‌دهد. حلقه‌ی پرسش-امتیازدهی-برچسب‌گذاری تکرار می‌شود تا زمانی که بودجه‌ی برچسب‌گذاری تمام شود، یک آستانه‌ی دقت اعتبارسنجی برآورده شود، یا حداکثر تعداد تکرار به دست آید. عملکرد نهایی بر روی یک مجموعه‌ی آزمون مستقل نگهداری‌شده گزارش می‌شود.

دام‌های رایج

  • عدم نرمال‌سازی ویژگی‌ها قبل از محاسبه‌ی فاصله‌ها، که باعث می‌شود ویژگی‌های با مقیاس بزرگ بر همسایگی غالب شوند.
  • استفاده از مجموعه‌ی آزمون برای هدایت یا ارزیابی انتخاب پرس‌وجو، که نشت داده محسوب می‌شود.
  • تنظیم k خیلی کوچک (k=1) در نزدیکی مرز تصمیم‌گیری، که امتیازات عدم قطعیت بسیار متغیری تولید می‌کند که ابهام واقعی را منعکس نمی‌کند.
  • نادیده گرفتن عدم تعادل کلاس در مجموعه‌ی اولیه، که باعث سوگیری پرس‌وجوهای اولیه به سمت مرزهای کلاس اکثریت می‌شود.
  • برابری دقت یادگیری فعال با یک خط پایه کاملاً نظارت‌شده بدون گزارش تعداد برچسب استفاده‌شده.

پرسش‌های متداول

چرا به جای یک مدل قدرتمندتر از KNN به عنوان یادگیرنده‌ی فعال استفاده کنیم؟

عدم قطعیت تقسیم آراء KNN ارزان است و نیازی به بازآموزی ندارد - افزودن یک نقطه‌ی برچسب‌دار جدید بلافاصله مدل را به‌روز می‌کند. این امر آن را زمانی که هزینه‌ی محاسباتی در هر تکرار مهم است، جذاب می‌کند. برای حداکثر دقت در یک بودجه‌ی برچسب ثابت، یادگیرنده‌های پایه گروهی مانند جنگل تصادفی یا تقویت گرادیان معمولاً از KNN بهتر عمل می‌کنند.

چگونه k را برای یادگیری فعال انتخاب کنم؟

یک محدوده‌ی شروع رایج k = 5 تا 15 است. مقادیر کوچک‌تر k تخمین‌های عدم قطعیت پرنویزتری تولید می‌کنند؛ مقادیر بزرگ‌تر k مرز را هموار می‌کنند اما ممکن است ابهام دقیق را از دست بدهند. k را بر روی مجموعه‌ی اولیه‌ی برچسب‌دار با اعتبارسنجی متقابل ارزیابی کنید و با رشد مجموعه‌ی برچسب‌دار آن را تنظیم کنید.

آیا مقیاس‌بندی ویژگی‌ها اهمیت دارد؟

بله، به طور حیاتی. فاصله‌ی KNN اگر ویژگی‌ها نرمال‌سازی نشوند، تحت سلطه‌ی ویژگی‌های با مقیاس بزرگ قرار می‌گیرد. همیشه قبل از محاسبه‌ی فاصله‌ها و امتیازات عدم قطعیت، از مقیاس‌بندی min-max یا استانداردسازی z-score استفاده کنید.

چه تعداد نمونه‌ی برچسب‌دار اولیه مورد نیاز است؟

حداقل، یک یا دو نمونه‌ی برچسب‌دار برای هر کلاس لازم است تا KNN بتواند برای همه‌ی کلاس‌ها همسایگی تشکیل دهد. در عمل، 5 تا 20 نمونه‌ی برچسب‌دار تخمین‌های عدم قطعیت اولیه‌ی پایدارتری را فراهم می‌کنند؛ تعداد کمتر، خطر همسایگی‌های تخریب‌شده را دارد که پرس‌وجوهای اولیه‌ی غیرمطلع‌کننده تولید می‌کنند.

چه زمانی باید حلقه‌ی فعال را متوقف کنم؟

بودجه‌ی برچسب‌گذاری را از قبل تعیین کنید، یا دقت اعتبارسنجی را نظارت کنید و زمانی که بهبود به ازای هر برچسب جدید زیر یک آستانه‌ی معنی‌دار افت کرد، متوقف شوید. هرگز از مجموعه‌ی آزمون به عنوان سیگنال توقف استفاده نکنید، زیرا این کار اطلاعات را به فرآیند پرس‌وجو نشت می‌دهد.

روش‌های مرتبط

منابع

  1. Settles, B. (2010). Active Learning Literature Survey. Computer Sciences Technical Report 1648, University of Wisconsin-Madison.

    باز کردن مرجع انتشار
    کپی شد.
  2. Zhu, X., Lafferty, J., & Ghahramani, Z. (2003). Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions. Proceedings of the ICML 2003 Workshop on the Continuum from Labeled to Unlabeled Data, 58–65.

    باز کردن مرجع انتشار
    کپی شد.