SVM با حاشیه‌ی نرم و زیان هینج

نقش $C$ را در SVM با حاشیه‌ی نرم توضیح بدهی، زیان هینج را حساب کنی و از روی $lpha_i$ بفهمی هر نقطه کجای حاشیه است.

14 دقیقه مطالعه · 5 سؤال تمرینی · یادگیری ماشین میانی و پیشرفته

وقتی داده جدایی‌پذیر نیست

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

راه‌حل: به هر نقطه یک متغیر کمکی (Slack) ξi≥0\xi_i \ge 0 می‌دهیم که اجازه‌ی تخطی از حاشیه را می‌دهد و آن را جریمه می‌کنیم:

min⁡w,b,ξ 12∥w∥2+C∑iξis.t.  yi(w⊤xi+b)≥1−ξi,  ξi≥0\min_{w,b,\xi}\ \tfrac12\|w\|^2 + C\sum_i \xi_i \quad \text{s.t.}\ \ y_i(w^\top x_i + b) \ge 1 - \xi_i,\ \ \xi_i \ge 0
  • 0<ξi<10 < \xi_i < 1: نقطه داخل حاشیه است ولی درست دسته‌بندی شده.
  • ξi=1\xi_i = 1: نقطه روی مرز تصمیم است.
  • ξi>1\xi_i > 1: نقطه اشتباه دسته‌بندی شده.

ضریب CC بده‌بستان بین پهنای حاشیه و تخطی‌ها را تنظیم می‌کند. CC بزرگ تخطی را گران می‌کند و به حاشیه‌ی سخت نزدیک می‌شود (بایاس کم، واریانس زیاد). CC کوچک حاشیه‌ی پهن‌تری با تخطی‌های بیشتر می‌دهد.

همان مسئله با زبان تابع زیان

در جواب بهینه، هر ξi\xi_i تا جایی که قید اجازه بدهد کوچک می‌شود:

ξi=max⁡(0, 1−yif(xi))\xi_i = \max\big(0,\ 1 - y_i f(x_i)\big)

که در آن f(x)=w⊤x+bf(x) = w^\top x + b. با جایگذاری، قیدها حذف می‌شوند و یک مسئله‌ی کمینه‌سازی ریسک تجربی منظم‌شده به دست می‌آید:

min⁡w,b 12∥w∥2+C∑imax⁡(0, 1−yif(xi))⏟hinge\min_{w,b}\ \tfrac12\|w\|^2 + C\sum_i \underbrace{\max\big(0,\ 1 - y_i f(x_i)\big)}_{\text{hinge}}

زیان هینج ℓ(z)=max⁡(0,1−z)\ell(z) = \max(0, 1 - z) با z=yf(x)z = y f(x):

  • برای z≥1z \ge 1 صفر است: نقاطی که با اطمینان کافی درست‌اند هیچ اثری ندارند. ریشه‌ی تُنُکی SVM همین است.
  • محدب است و یک کران بالا برای زیان ۰-۱ است، پس جانشین مناسبی برای آن است.
  • در z=1z = 1 مشتق‌پذیر نیست و برای بهینه‌سازی مستقیم از زیرگرادیان استفاده می‌شود.

زیان لجستیک log⁡(1+e−z)\log(1 + e^{-z}) هم محدب است، ولی هیچ‌وقت دقیقاً صفر نمی‌شود.

دوگان حاشیه‌ی نرم و سه نوع نقطه

دوگان حاشیه‌ی نرم تقریباً همان دوگان حاشیه‌ی سخت است. تنها تفاوت این است که αi\alpha_i از بالا هم محدود می‌شود (قید جعبه‌ای):

0≤αi≤C,∑iαiyi=00 \le \alpha_i \le C, \qquad \sum_i \alpha_i y_i = 0

از شرط‌های KKT، هر نقطه در یکی از سه دسته قرار می‌گیرد:

  • αi=0\alpha_i = 0:   yif(xi)≥1\;y_i f(x_i) \ge 1، یعنی بیرون از حاشیه یا روی آن. در جواب اثری ندارد.
  • 0<αi<C0 < \alpha_i < C:   yif(xi)=1\;y_i f(x_i) = 1، دقیقاً روی مرز حاشیه. bb را از این نقاط حساب می‌کنیم.
  • αi=C\alpha_i = C:   yif(xi)≤1\;y_i f(x_i) \le 1، یعنی داخل حاشیه یا اشتباه دسته‌بندی شده (ξi≥0\xi_i \ge 0).

یک نکته‌ی عملی: خروجی f(x)f(x) در SVM احتمال نیست. اگر احتمال لازم است، باید آن را کالیبره کرد، مثلاً با روش Platt.

تمرین‌های این درس را حل کن (رایگان)