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

ماشین بردار پشتیبان نیمه‌نظارت‌شده

معرفی‌شده توسط
Joachims, T.
سال
1999
نوع
Semi-supervised classifier
خانواده
Machine learning

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

اندازه قلم

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

ماشین بردار پشتیبان نیمه‌نظارت‌شده (S3VM) با ترکیب مقادیر زیادی داده بدون برچسب در کنار مجموعه آموزشی کوچک برچسب‌دار، SVM کلاسیک را گسترش می‌دهد. این روش به دنبال یک ابرصفحه با حداکثر حاشیه است که نه تنها نمونه‌های برچسب‌دار را جدا می‌کند، بلکه از نواحی کم‌تراکم توزیع کامل داده‌ها عبور می‌کند و در صورت کمیاب بودن نمونه‌های برچسب‌دار، تعمیم‌پذیری بهتری را ارائه می‌دهد.

شهود پشت روش

یک SVM استاندارد، مرز را صرفاً از نقاط برچسب‌دار یاد می‌گیرد. S3VM مشاهده می‌کند که داده‌های بدون برچسب همچنان اطلاعات هندسی در مورد اینکه خوشه‌های داده در کجا متراکم و در کجا پراکنده هستند، حمل می‌کنند. با الزام اینکه مرز تصمیم از نواحی پر تراکم اجتناب کند — صرف نظر از اینکه آن نقاط برچسب دارند یا خیر — مدل می‌تواند از اکثریت بدون برچسب برای تیز کردن مرزی که در غیر این صورت فقط از تعداد انگشت شماری نمونه برچسب‌دار ترسیم می‌کند، بهره‌برداری کند. نتیجه، حاشیه‌ای است که ساختار داده زیربنایی را رعایت می‌کند، نه فقط برچسب‌های شناخته شده را.

تاریخ

مبانی S3VM توسط Vapnik در کارهای اولیه خود بر روی استنتاج انتقالی (transductive inference) پایه‌گذاری شد، اما این روش پس از اینکه Joachims (1999) اثربخشی آن را برای طبقه‌بندی متن تحت نام Transductive SVM نشان داد، به طور گسترده‌ای پذیرفته شد. درمان جامع در Chapelle، Scholkopf، و Zien (2006) S3VM را در کنار سایر رویکردهای نیمه‌نظارت‌شده ادغام کرد و همچنان مرجع استاندارد باقی مانده است. کارهای بعدی، آرام‌سازی‌های محدب (convex relaxations) و حل‌کننده‌های مقیاس‌پذیر را برای پرداختن به چالش‌های محاسباتی و بهینه‌های محلی روش اصلی معرفی کردند.

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

S3VM زمانی انتخاب درستی است که داده‌های برچسب‌دار گران یا کمیاب باشند (مثلاً کمتر از چند صد نمونه) اما داده‌های بدون برچسب فراوان در دسترس باشند — سناریوی رایج در طبقه‌بندی متن، بیوانفورماتیک، یا هر حوزه‌ای که در آن حاشیه‌نویسی پرهزینه است. این روش زمانی بهترین عملکرد را دارد که فرض خوشه برقرار باشد: کلاس‌ها خوشه‌های متمایزی را تشکیل می‌دهند و مرز تصمیم در یک ناحیه کم‌تراکم قرار دارد. از S3VM زمانی اجتناب کنید که داده‌های برچسب‌دار از قبل فراوان هستند (SVM استاندارد با هزینه کمتر به آن می‌رسد یا از آن فراتر می‌رود)، زمانی که فرض خوشه نقض می‌شود (کلاس‌ها به شدت در فضای ویژگی همپوشانی دارند)، یا زمانی که توزیع بدون برچسب از توزیع برچسب‌دار منحرف می‌شود، که می‌تواند مرز را در جهت اشتباه سوق دهد.

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

  • بهینه‌سازی به دلیل برچسب‌های کاذب غیرمحدب (non-convex) است، که آن را به مقداردهی اولیه حساس و مستعد بهینه‌های محلی می‌کند.
  • هزینه محاسباتی با تعداد نمونه‌های بدون برچسب به خوبی مقیاس‌پذیر نیست — مجموعه‌های بزرگ بدون برچسب پرهزینه می‌شوند.
  • به فرض خوشه متکی است؛ اگر کلاس‌ها خوشه‌های جدا از هم را تشکیل ندهند، داده‌های بدون برچسب می‌توانند عملکرد را تخریب کنند.
  • نیاز به تنظیم دقیق وزن زیان برچسب‌دار C و وزن زیان بدون برچسب C* دارد که به پیچیدگی انتخاب مدل می‌افزاید.

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

نقاط قوت

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

کاربردها

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

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

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

1

یک SVM اولیه بر روی نمونه‌های برچسب‌دار موجود برازش داده می‌شود و یک مرز تصمیم مقدماتی و حاشیه را یاد می‌گیرد. این یک مدل شروع و پیش‌بینی‌های اولیه را برای مجموعه بدون برچسب فراهم می‌کند و بهینه‌سازی نیمه‌نظارت‌شده بعدی را در یک راه‌حل نظارت‌شده زمینه‌سازی می‌کند.

2

SVM مقدماتی، برچسب‌های کلاس موقت (برچسب‌های کاذب) را بر اساس اینکه کدام طرف مرز فعلی قرار دارند، به تمام نمونه‌های بدون برچسب اختصاص می‌دهد. این برچسب‌های کاذب به نقاط بدون برچسب اجازه می‌دهند تا حتی با وجود ناشناخته بودن کلاس واقعی‌شان، در حداکثرسازی حاشیه شرکت کنند.

3

هدف اصلی S3VM به طور مشترک زیان لولایی (hinge loss) را بر روی نمونه‌های برچسب‌دار و زیان شبه-لولایی را بر روی نمونه‌های بدون برچسب کمینه می‌کند در حالی که حاشیه را حداکثر می‌کند. یک پارامتر تعادل C* کنترل می‌کند که نقاط بدون برچسب چقدر قوی بر مرز تأثیر می‌گذارند، و بین بهره‌برداری از ساختار در داده‌های بدون برچسب و برازش حقیقت زمینی برچسب‌دار، مبادله می‌کند.

فرمول
\min_{w,b,y^*} \frac{1}{2}\|w\|^2 + C\sum_{i}\xi_i + C^*\sum_{j}\xi_j^*
4

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

5

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

فرمول
f(x) = \text{sign}(w^\top x + b)

دام‌های رایج

  • فرض بر اینکه داده‌های بدون برچسب همیشه کمک می‌کنند — اگر فرض خوشه نقض شود، S3VM می‌تواند بدتر از یک SVM نظارت‌شده عمل کند.
  • استفاده از C* بسیار بزرگ نسبت به C، وزن‌دهی بیش از حد به نقاط بدون برچسب و اجازه دادن به مرز برای دور شدن از سیگنال برچسب‌دار.
  • نادیده گرفتن اعتبارسنجی بر روی یک مجموعه برچسب‌دار نگه‌داشته‌شده، که تشخیص اینکه داده‌های بدون برچسب چه زمانی به عملکرد آسیب رسانده‌اند را غیرممکن می‌سازد.
  • اعمال S3VM زمانی که داده‌های برچسب‌دار و بدون برچسب از توزیع‌های متفاوتی می‌آیند (جابجایی کوواریانس)، که مفروضات روش را نقض می‌کند.

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

S3VM چگونه با SVM استاندارد تفاوت دارد؟

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

فرض خوشه چیست و چرا اهمیت دارد؟

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

چگونه وزن بدون برچسب C* را انتخاب کنم؟

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

آیا S3VM می‌تواند مرزهای غیرخطی را مدیریت کند؟

بله. مانند SVMهای استاندارد، S3VM از توابع کرنل (RBF، چندجمله‌ای و غیره) پشتیبانی می‌کند که به طور ضمنی داده‌ها را به فضاهای با ابعاد بالاتر نگاشت می‌کنند که در آن یک مرز خطی در فضای ویژگی اصلی غیرخطی می‌شود.

چه زمانی باید خودآموزی (self-training) یا انتشار برچسب (label propagation) را به S3VM ترجیح دهم؟

خودآموزی پیاده‌سازی ساده‌تری دارد و به خوبی با مجموعه‌های بزرگ بدون برچسب مقیاس‌پذیر است؛ زمانی که محاسبات محدود است آن را ترجیح دهید. انتشار برچسب بر روی داده‌های ساختاریافته گراف به خوبی کار می‌کند. S3VM زمانی ترجیح داده می‌شود که تضمین‌های حداکثر حاشیه را بخواهید و فرض خوشه احتمالاً برآورده شده باشد.

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

منابع

  1. Joachims, T. (1999). Transductive Inference for Text Classification using Support Vector Machines. Proceedings of the 16th International Conference on Machine Learning (ICML), 200–209.

    باز کردن مرجع انتشار
    کپی شد.
  2. Chapelle, O., Scholkopf, B., & Zien, A. (Eds.). (2006). Semi-Supervised Learning. MIT Press.

    شابک: 978-0-262-03358-9
    کپی شد.