حاشیه‌ی بیشینه و مسئله‌ی دوگان SVM

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

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

کدام ابرصفحه؟ آن‌که حاشیه‌ی بیشتری دارد

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

فاصله‌ی نقطه‌ی xx از ابرصفحه‌ی w⊤x+b=0w^\top x + b = 0 برابر است با:

∣w⊤x+b∣∥w∥\frac{|w^\top x + b|}{\|w\|}

چون (w,b)(w, b) را می‌شود با هر عدد مثبتی مقیاس کرد، قرارداد می‌کنیم min⁡iyi(w⊤xi+b)=1\min_i y_i(w^\top x_i + b) = 1. آن‌وقت پهنای کل حاشیه (فاصله‌ی دو ابرصفحه‌ی w⊤x+b=±1w^\top x + b = \pm 1) می‌شود 2/∥w∥2/\|w\|. بیشینه کردن حاشیه یعنی:

min⁡w,b 12∥w∥2s.t.yi(w⊤xi+b)≥1,  i=1,…,n\min_{w,b}\ \tfrac12\|w\|^2 \quad \text{s.t.}\quad y_i(w^\top x_i + b) \ge 1,\ \ i = 1,\dots,n

این یک مسئله‌ی برنامه‌ریزی درجه‌دو (QP) محدب است و جواب یکتا دارد.

از لاگرانژین تا مسئله‌ی دوگان

برای هر قید یک ضریب لاگرانژ αi≥0\alpha_i \ge 0 در نظر می‌گیریم:

L(w,b,α)=12∥w∥2−∑iαi[yi(w⊤xi+b)−1]\mathcal L(w, b, \alpha) = \tfrac12\|w\|^2 - \sum_i \alpha_i\big[y_i(w^\top x_i + b) - 1\big]

با صفر کردن مشتق نسبت به ww و bb:

w=∑iαiyixi,∑iαiyi=0w = \sum_i \alpha_i y_i x_i, \qquad \sum_i \alpha_i y_i = 0

با جایگذاری در L\mathcal L، مسئله‌ی دوگان به دست می‌آید:

max⁡α ∑iαi−12∑i,jαiαjyiyj xi⊤xjs.t.  αi≥0,  ∑iαiyi=0\max_{\alpha}\ \sum_i \alpha_i - \tfrac12 \sum_{i,j} \alpha_i \alpha_j y_i y_j\, x_i^\top x_j \quad \text{s.t.}\ \ \alpha_i \ge 0,\ \ \sum_i \alpha_i y_i = 0

نکته‌ی کلیدی: داده‌ها در دوگان فقط از طریق ضرب داخلی xi⊤xjx_i^\top x_j ظاهر می‌شوند. این همان دری است که ترفند کرنل در درس بعد از آن وارد می‌شود.

شرط‌های KKT و بردارهای پشتیبان

چون مسئله محدب است و قیدها خطی‌اند، جواب بهینه در شرط‌های KKT صدق می‌کند. مهم‌ترینشان مکمل بودن (Complementary Slackness) است:

αi[yi(w⊤xi+b)−1]=0\alpha_i\big[y_i(w^\top x_i + b) - 1\big] = 0

یعنی برای هر نقطه یا αi=0\alpha_i = 0 است، یا نقطه دقیقاً روی مرز حاشیه قرار دارد. نقاطی که αi>0\alpha_i > 0 دارند بردار پشتیبان (Support Vector) نامیده می‌شوند.

  • ww فقط ترکیبی از بردارهای پشتیبان است. بقیه‌ی نقاط را می‌شود حذف کرد و جواب تغییر نمی‌کند.
  • bb از هر بردار پشتیبان ss به دست می‌آید: b=ys−w⊤xsb = y_s - w^\top x_s.
  • پیش‌بینی: f(x)=∑iαiyi xi⊤x+bf(x) = \sum_i \alpha_i y_i\, x_i^\top x + b که فقط روی بردارهای پشتیبان جمع زده می‌شود.

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