ماشین‌های بردار پشتیبان (SVM)؛ از فرمول‌بندی ریاضی تا پیاده‌سازی

در مسائل دسته‌بندی با بی‌نهایت خط یا ابرصفحه روبه‌رو می‌شویم که می‌توانند داده‌ها را جدا کنند؛ اما سوال اساسی این است که کدام مرز بهترین عملکرد را روی داده‌های آینده دارد؟ ماشین‌های بردار پشتیبان (Support Vector Machines یا SVM) با ایده‌ی ساده اما قدرتمند «پهن‌ترین خیابان ممکن بین دو کلاس»، این چالش را به‌صورت یک مسئله‌ی بهینه‌سازی دقیق و شفاف حل می‌کنند.

اگرچه با گسترش یادگیری عمیق تمرکز بسیاری از پروژه‌ها تغییر کرد، اما SVMها همچنان برای مجموعه‌داده‌های کوچک تا متوسط، داده‌های تنک و با ابعاد بالا (مانند متن‌های پردازش‌شده با TF-IDF) و سیستم‌هایی که نیاز به تضمین‌های ریاضی دارند، سریع‌ترین و بهینه‌ترین گزینه‌اند.

در این درس علاوه بر بررسی ریاضیات پایه‌ای نظیر بیشینه‌سازی حاشیه، زیان لولا و ترفند کرنل، یک دسته‌بند SVM خطی را با پایتون از صفر می‌سازید و نحوه‌ی استفاده‌ی اصولی از آن را در کتابخانه‌ی scikit-learn یاد می‌گیرید.

پهن‌ترین خیابان ممکن را بین دو کلاس پیدا کنید؛ کل ایده در همین خلاصه می‌شود.

اهداف یادگیری

• پیاده‌سازی یک SVM خطی از صفر با استفاده از تابع زیان لولا (hinge loss) و گرادیان کاهشی (gradient descent) روی فرم اولیه (primal formulation)
• توضیح اصل بیشینه‌سازی حاشیه (maximum margin) و شناسایی بردارهای پشتیبان (support vectors) در یک مدل آموزش‌دیده
• مقایسه‌ی کرنل‌های خطی، چندجمله‌ای و RBF و توضیح این‌که ترفند کرنل (kernel trick) چطور جلوی نگاشت صریح به فضاهای با ابعاد بالا را می‌گیرد
• ارزیابی مصالحه‌ی حاصل از پارامتر C بین عرض حاشیه و خطاهای دسته‌بندی

صورت مسئله

فرض کنید دو کلاس از نقاط داده دارید و می‌خواهید خطی (یا ابرصفحه‌ای) بکشید که آن‌ها را از هم جدا کند. بی‌نهایت خط مختلف می‌توانند این کار را انجام دهند؛ اما کدام‌یک را باید انتخاب کنید؟

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

این شهود ساده پایه و اساس ماشین‌های بردار پشتیبان (Support Vector Machines یا SVM) را می‌سازد؛ یکی از دقیق‌ترین و زیباترین الگوریتم‌های یادگیری ماشین از نظر ریاضیات. ماشین‌های بردار پشتیبان پیش از دوران یادگیری عمیق (deep learning)، روش غالب دسته‌بندی بودند. امروز هم برای مجموعه‌داده‌های کوچک، داده‌های با ابعاد بالا و مسائلی که به مدلی اصولی و شفاف با تضمین‌های نظری نیاز دارند، بهترین گزینه‌اند.

این مبحث پیوند مستقیمی با بخش 1 دوره دارد: بهینه‌سازی (optimization) در اینجا کوژ یا محدب (convex) است (درس 18)، اندازه‌گیری حاشیه با نُرم‌ها انجام می‌شود (درس 14) و ترفند کرنل با بهره‌گیری از ضرب‌های داخلی (dot products)، بدون نیاز به محاسبه در فضای چندبعدی، مرزهای غیرخطی را مدیریت می‌کند.

مفاهیم پایه

دسته‌بند با بیشینه‌ی حاشیه

فرض کنید داده‌هایی تفکیک‌پذیر به‌صورت خطی با برچسب‌های $y_i \in \lbrace -1, +1 \rbrace$ و بردارهای ویژگی $x_i$ داریم. هدف ما یافتن ابرصفحه‌ی $w^T x + b = 0$ است که این دو کلاس را از هم جدا کند.

فاصله‌ی نقطه‌ی $x_i$ تا این ابرصفحه برابر است با:

$$\text{distance} = \frac{\lvert w^T x_i + b \rvert}{\lVert w \rVert}$$

برای نقطه‌ای که درست دسته‌بندی شده باشد: $y_i (w^T x_i + b) > 0$. عرض حاشیه، دو برابرِ فاصله‌ی ابرصفحه تا نزدیک‌ترین نقطه در هر دو طرف است:

مسئله‌ی بهینه‌سازی به‌صورت زیر تعریف می‌شود:

$$\begin{aligned} \text{maximize} \quad & \frac{2}{\lVert w \rVert} \quad \text{(the margin width)} \\ \text{subject to} \quad & y_i (w^T x_i + b) \ge 1 \quad \text{for all } i \end{aligned}$$

به شکلی معادل (از آنجا که کمینه‌سازی $\lVert w \rVert^2$ از نظر بهینه‌سازی ساده‌تر است):

$$\begin{aligned} \text{minimize} \quad & \frac{1}{2} \lVert w \rVert^2 \\ \text{subject to} \quad & y_i (w^T x_i + b) \ge 1 \quad \text{for all } i \end{aligned}$$

این مسئله یک برنامه‌ریزی درجه‌دوم محدب (convex quadratic program) است و یک پاسخ بهینه‌ی سراسری یکتا دارد. نقاط داده‌ای که دقیقاً روی مرز حاشیه‌ها قرار می‌گیرند (جایی که $y_i (w^T x_i + b) = 1$)، بردارهای پشتیبان نام دارند. مرز تصمیم‌گیری فقط و فقط با این نقاط تعیین می‌شود. اگر نقطه‌ای غیر از بردارهای پشتیبان را جابه‌جا یا حذف کنید، مرز تغییری نمی‌کند.

بردارهای پشتیبان: اقلیت حیاتی

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

علاوه بر این، تعداد بردارهای پشتیبان کرانی برای خطای تعمیم مدل فراهم می‌کند. کمتر بودن تعداد این بردارها نسبت به کل داده‌ها، نشان‌دهنده‌ی تعمیم‌پذیری بهتر است.

حاشیه‌ی نرم: مهار نوفه با پارامتر C

داده‌های دنیای واقعی به‌ندرت کاملاً تفکیک‌پذیر خطی هستند. همیشه نقاطی پیدا می‌شوند که در سمت اشتباه مرز یا درون حاشیه بیفتند. فرمول‌بندی حاشیه‌ی نرم (soft margin) با معرفی متغیرهای متغیر شل یا کمکی (slack variables)، اجازه می‌دهد تخطی‌هایی رخ دهد:

$$\begin{aligned} \text{minimize} \quad & \frac{1}{2} \lVert w \rVert^2 + C \sum_i \xi_i \\ \text{subject to} \quad & y_i (w^T x_i + b) \ge 1 - \xi_i \\ & \xi_i \ge 0 \quad \text{for all } i \end{aligned}$$

متغیر کمکی $\xi_i$ نشان می‌دهد که نقطه‌ی $i$ چقدر از حاشیه تخطی کرده است. پارامتر $C$ تعادل بین دو هدف را تنظیم می‌کند:

در واقع $C$ معکوس شدت منظم‌سازی (regularization) است؛ یعنی $C$ بزرگ برابر با منظم‌سازی کمتر و $C$ کوچک برابر با منظم‌سازی بیشتر است.

تابع زیان لولا: تابع زیان SVM

می‌توان SVM با حاشیه‌ی نرم را به‌صورت یک مسئله‌ی بهینه‌سازی بدون قید بازنویسی کرد:

$$\text{minimize} \quad \frac{1}{2} \lVert w \rVert^2 + C \sum_i \max(0, 1 - y_i (w^T x_i + b))$$

عبارت $\max(0, 1 - y_i f(x_i))$ همان تابع زیان لولا (hinge loss) است. اگر نقطه‌ای درست دسته‌بندی شود و بیرون از حاشیه باشد، زیان آن صفر است؛ اما اگر درون حاشیه قرار بگیرد یا اشتباه دسته‌بندی شود، زیان به‌شکل خطی جریمه می‌شود.

Hinge loss for a single point:

loss
  |
  | \
  |  \
  |   \
  |    \
  |     \_______________
  |
  +-----|-----|-------->  y * f(x)
       0     1

Zero loss when y*f(x) >= 1 (correctly classified, outside margin).
Linear penalty when y*f(x) < 1.

آن را با تابع زیان لجستیک (در رگرسیون لجستیک) مقایسه کنید:

$$\begin{aligned} \text{Hinge:} \quad & \max(0, 1 - y f(x)) && \text{Hard cutoff at margin} \\ \text{Logistic:} \quad & \log(1 + \exp(-y f(x))) && \text{Smooth, never exactly zero} \end{aligned}$$

زیان لولا جواب‌هایی تنک یا اسپارس (sparse) تولید می‌کند (تنها بردارهای پشتیبان سهمی غیرصفر دارند). در مقابل، تابع زیان لجستیک از تک‌تک نقاط داده استفاده می‌کند. این ویژگی، مصرف حافظه‌ی SVM را هنگام پیش‌بینی بسیار کم می‌کند.

آموزش SVM خطی با گرادیان کاهشی

می‌توانید یک SVM خطی را مستقیماً با استفاده از گرادیان کاهشی روی زیان لولا به‌همراه منظم‌سازی L2 آموزش دهید، بدون اینکه نیازی به حل مسئله‌ی برنامه‌ریزی درجه‌دوم قیددار باشد:

$$\begin{aligned} & L(w, b) = \frac{\lambda}{2} \lVert w \rVert^2 + \frac{1}{n} \sum_i \max(0, 1 - y_i (w^T x_i + b)) \\[6pt] & \text{Gradient with respect to } w\text{:} \\ & \quad \text{If } y_i (w^T x_i + b) \ge 1\text{:} \quad \frac{\partial L}{\partial w} = \lambda w \\ & \quad \text{If } y_i (w^T x_i + b) < 1\text{:} \quad \frac{\partial L}{\partial w} = \lambda w - y_i x_i \\[6pt] & \text{Gradient with respect to } b\text{:} \\ & \quad \text{If } y_i (w^T x_i + b) \ge 1\text{:} \quad \frac{\partial L}{\partial b} = 0 \\ & \quad \text{If } y_i (w^T x_i + b) < 1\text{:} \quad \frac{\partial L}{\partial b} = -y_i \end{aligned}$$

به این ساختار فرم اولیه (primal formulation) می‌گویند. پیچیدگی زمانی آن در هر دور آموزش (epoch) برابر با $O(n \cdot d)$ است که در آن $n$ تعداد نمونه‌ها و $d$ تعداد ویژگی‌هاست. این روش برای داده‌های بسیار بزرگ، اسپارس و با ابعاد بالا (مانند دسته‌بندی متن) بسیار سریع عمل می‌کند.

فرم دوگان و ترفند کرنل

فرم دوگان لاگرانژی (Lagrangian dual) مسئله‌ی SVM (برگرفته از شرایط KKT در درس 18 بخش 1) عبارت است از:

$$\begin{aligned} \text{maximize} \quad & \sum_i \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) \\ \text{subject to} \quad & 0 \le \alpha_i \le C \\ & \sum_i \alpha_i y_i = 0 \end{aligned}$$

فرم دوگان فقط شامل ضرب‌های داخلی $x_i \cdot x_j$ بین نقاط داده است؛ نکته‌ی کلیدی در همین نهفته است. کافی است هر ضرب داخلی را با یک تابع کرنل (kernel) به نام $K(x_i, x_j)$ جایگزین کنید؛ با این کار، مدل مرزهای غیرخطی را یاد می‌گیرد بدون آنکه اصلاً نیازی به محاسبه‌ی صریح تبدیل داده‌ها در فضای ابعاد بالا باشد.

$$\begin{aligned} \text{Linear kernel:} \quad & K(x, z) = x \cdot z \\ \text{Polynomial kernel:} \quad & K(x, z) = (x \cdot z + c)^d \\ \text{RBF (Gaussian):} \quad & K(x, z) = \exp(-\gamma \lVert x - z \rVert^2) \end{aligned}$$

کرنل RBF داده‌ها را به فضایی با ابعاد بی‌نهایت نگاشت می‌کند. برای نقاطی که در فضای ورودی به هم نزدیک‌اند، مقدار کرنل نزدیک به 1 است و برای نقاط دور از هم، این مقدار به 0 میل می‌کند. به همین دلیل این کرنل توانایی یادگیری هر مرز تصمیم نرم و همواری را دارد.

ترفند کرنل ضرب داخلی را در فضای ابعاد بالا بدون پا گذاشتن به آن فضا محاسبه می‌کند. مثلاً در یک کرنل چندجمله‌ای با درجه‌ی $d$ در فضای $D$ بعدی، فضای ویژگی صریح عملاً $O(D^d)$ بُعد دارد؛ اما $K(x, z)$ در زمان $O(D)$ محاسبه می‌شود.

SVM برای رگرسیون (SVR)

رگرسیون بردار پشتیبان (Support Vector Regression یا SVR) یک لوله با عرض $\epsilon$ به دور داده‌ها برازش می‌دهد. نقاطی که درون این لوله قرار می‌گیرند هیچ زیانی ندارند و نقاط بیرون از لوله به‌شکل خطی جریمه می‌شوند.

$$\begin{aligned} \text{minimize} \quad & \frac{1}{2} \lVert w \rVert^2 + C \sum_i (\xi_i + \xi_i^*) \\ \text{subject to} \quad & y_i - (w^T x_i + b) \le \epsilon + \xi_i \\ & (w^T x_i + b) - y_i \le \epsilon + \xi_i^* \\ & \xi_i, \xi_i^* \ge 0 \end{aligned}$$

پارامتر $\epsilon$ عرض این لوله را کنترل می‌کند. لوله‌ی پهن‌تر یعنی بردارهای پشتیبان کمتر و برازش هموارتر؛ لوله‌ی باریک‌تر یعنی بردارهای پشتیبان بیشتر و برازش دقیق‌تر و محکم‌تر.

چرا یادگیری عمیق گوی سبقت را ربود؟ (و SVM هنوز کجا برنده است؟)

از اواخر دهه‌ی 1990 تا اوایل دهه‌ی 2010، SVM الگوریتم برتر یادگیری ماشین بود. اما یادگیری عمیق به چند دلیل از آن پیشی گرفت:

با این حال، SVM در این موقعیت‌ها همچنان برنده است:

• مجموعه‌داده‌های کم‌حجم (چند صد تا چند هزار نمونه)
• داده‌های اسپارس با ابعاد بالا (مثل متن با ویژگی‌های TF-IDF)
• مسائلی که به تضمین‌های ریاضی نیاز دارید (کران‌های حاشیه)
• شرایطی که زمان آموزش باید در کمترین حد باشد (SVM خطی بسیار سریع است)
• دسته‌بندی دوتایی با ساختار حاشیه‌ای شفاف
• تشخیص ناهنجاری (One-Class SVM)

ساخت مدل

گام 1: تابع زیان لولا و گرادیان

پایه‌ی کار: محاسبه‌ی تابع زیان لولا و گرادیان آن برای یک دسته (batch).

def hinge_loss(X, y, w, b):
    n = len(X)
    total_loss = 0.0
    for i in range(n):
        margin = y[i] * (dot(w, X[i]) + b)
        total_loss += max(0.0, 1.0 - margin)
    return total_loss / n

گام 2: SVM خطی با گرادیان کاهشی

آموزش از طریق کمینه‌سازی زیان لولای منظم‌شده، بدون نیاز به حل‌کننده‌ی برنامه‌ریزی درجه‌دوم.

class LinearSVM:
    def __init__(self, lr=0.001, lambda_param=0.01, n_epochs=1000):
        self.lr = lr
        self.lambda_param = lambda_param
        self.n_epochs = n_epochs
        self.w = None
        self.b = 0.0

    def fit(self, X, y):
        n_features = len(X[0])
        self.w = [0.0] * n_features
        self.b = 0.0

        for epoch in range(self.n_epochs):
            for i in range(len(X)):
                margin = y[i] * (dot(self.w, X[i]) + self.b)
                if margin >= 1:
                    self.w = [wj - self.lr * self.lambda_param * wj
                              for wj in self.w]
                else:
                    self.w = [wj - self.lr * (self.lambda_param * wj - y[i] * X[i][j])
                              for j, wj in enumerate(self.w)]
                    self.b -= self.lr * (-y[i])

    def predict(self, X):
        return [1 if dot(self.w, x) + self.b >= 0 else -1 for x in X]

گام 3: توابع کرنل

پیاده‌سازی کرنل‌های خطی، چندجمله‌ای و RBF.

def linear_kernel(x, z):
    return dot(x, z)

def polynomial_kernel(x, z, degree=3, c=1.0):
    return (dot(x, z) + c) ** degree

def rbf_kernel(x, z, gamma=0.5):
    diff = [xi - zi for xi, zi in zip(x, z)]
    return math.exp(-gamma * dot(diff, diff))

گام 4: شناسایی حاشیه و بردارهای پشتیبان

پس از آموزش، بردارهای پشتیبان را شناسایی کرده و عرض حاشیه را اندازه می‌گیریم.

def find_support_vectors(X, y, w, b, tol=1e-3):
    support_vectors = []
    for i in range(len(X)):
        margin = y[i] * (dot(w, X[i]) + b)
        if abs(margin - 1.0) < tol:
            support_vectors.append(i)
    return support_vectors

برای مشاهده‌ی پیاده‌سازی کامل به همراه همه‌ی مثال‌ها به فایل code/svm.py مراجعه کنید.

استفاده‌ی عملی

استفاده در scikit-learn:

from sklearn.svm import SVC, LinearSVC, SVR
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("svm", SVC(kernel="rbf", C=1.0, gamma="scale")),
])
clf.fit(X_train, y_train)
print(f"Accuracy: {clf.score(X_test, y_test):.4f}")
print(f"Support vectors: {clf['svm'].n_support_}")

نکته‌ی مهم: همیشه ویژگی‌های خود را قبل از آموزش SVM مقیاس‌بندی (scale) کنید. ماشین‌های بردار پشتیبان به‌شدت به بزرگی مقیاس ویژگی‌ها حساس‌اند؛ زیرا اندازه‌ی حاشیه به $\lVert w \rVert$ وابسته است و ویژگی‌های مقیاس‌بندی‌نشده هندسه‌ی فضا را به هم می‌ریزند.

برای مجموعه‌داده‌های بزرگ، به‌جای SVC (که از فرم دوگان استفاده می‌کند و پیچیدگی $O(n^2)$ تا $O(n^3){}$ دارد) از LinearSVC استفاده کنید که بر پایه‌ی فرم اولیه است و پیچیدگی خطی $O(n \cdot d)$ در هر دوره بر حسب $n$ دارد:

from sklearn.svm import LinearSVC

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("svm", LinearSVC(C=1.0, max_iter=10000)),
])

تمرین‌ها

1. یک مجموعه‌داده‌ی دوبعدی با تفکیک‌پذیری خطی تولید کنید. مدل LinearSVM خودتان را روی آن آموزش داده و بردارهای پشتیبان را شناسایی کنید. بررسی کنید که آیا این بردارهای پشتیبان واقعاً نزدیک‌ترین نقاط به مرز تصمیم‌گیری هستند یا نه.

2. روی یک مجموعه‌داده‌ی نوفه‌دار، مقدار $C$ را از 0.001 تا 1000 تغییر دهید. مرز تصمیم را برای هر مقدار $C$ رسم کنید. روند تغییر از حاشیه‌ی پهن (کم‌برازش) به حاشیه‌ی باریک (بیش‌برازش) را مشاهده و تحلیل کنید.

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

4. تابع زیان لولا و تابع زیان لجستیک را روی یک مجموعه‌داده مقایسه کنید. یک SVM خطی و یک رگرسیون لجستیک آموزش دهید. بشمارید چه تعداد از نقاط آموزشی در تعیین مرز تصمیم هر مدل نقش دارند (بردارهای پشتیبان در برابر تمام نقاط داده).

5. الگوریتم SVR را بر پایه‌ی تابع زیان نامتعصب به اپسیلون (epsilon-insensitive loss) پیاده‌سازی کنید. آن را روی $y = \sin(x) + \text{noise}$ برازش دهید. لوله‌ی اپسیلون را در اطراف پیش‌بینی‌ها رسم کنید و بردارهای پشتیبان (نقاط خارج از لوله) را با رنگ مشخص نشان دهید.

اصطلاحات کلیدی

برای مطالعه‌ی بیشتر

• Vapnik: The Nature of Statistical Learning Theory (1995) - اثر بنیادین درباره‌ی SVMها و یادگیری آماری
• Cortes & Vapnik: Support-vector networks (1995) - مقاله‌ی اصلی ماشین‌های بردار پشتیبان
• Platt: Sequential Minimal Optimization (1998) - الگوریتم SMO که آموزش SVM را کاربردی و مقیاس‌پذیر کرد
• مستندات SVM در scikit-learn - راهنمای عملی همراه با جزئیات پیاده‌سازی
• LIBSVM: A Library for Support Vector Machines - کتابخانه‌ی C++ در پسِ اکثر پیاده‌سازی‌های SVM