فصل ۵: ماشین‌های بردار پشتیبان

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

در این فصل مفاهیم اساسی SVM، شیوهٔ استفاده از آن و سازوکار درونی آن بررسی می‌شود.

طبقه‌بندی خطی با SVM

ایدهٔ اصلی SVM با نمایش تصویری بهتر درک می‌شود. شکل ۵-۱ بخشی از مجموعه‌دادهٔ Iris را نشان می‌دهد که در انتهای فصل ۴ معرفی شد. دو کلاس موجود را می‌توان به‌وضوح با یک خط مستقیم از یکدیگر جدا کرد؛ بنابراین داده‌ها به‌صورت خطی جدایی‌پذیر هستند.

در نمودار سمت چپ شکل ۵-۱، مرز تصمیم سه طبقه‌بند خطی ممکن نمایش داده شده است. مدلی که مرزش با خط‌چین نشان داده شده آن‌قدر نامناسب است که حتی دو کلاس را درست از هم جدا نمی‌کند. دو مدل دیگر روی مجموعهٔ آموزشی به‌طور کامل درست عمل می‌کنند، اما مرز تصمیم آن‌ها بیش از حد به نمونه‌های آموزشی نزدیک است و احتمالاً روی نمونه‌های جدید عملکرد ضعیف‌تری خواهند داشت. در مقابل، خط پیوسته در نمودار سمت راست مرز تصمیم یک طبقه‌بند SVM است: این خط هم دو کلاس را جدا می‌کند و هم تا حد ممکن از نزدیک‌ترین نمونه‌های آموزشی فاصله می‌گیرد. می‌توان SVM را مانند الگوریتمی تصور کرد که میان دو کلاس، پهن‌ترین «خیابان» ممکن را ایجاد می‌کند؛ خطوط خط‌چین موازی دو سوی این خیابان را مشخص می‌کنند. این روش طبقه‌بندی با حاشیهٔ بزرگ نام دارد.

افزودن نمونه‌های آموزشی جدید که خارج از این خیابان قرار دارند، مرز تصمیم را تغییر نمی‌دهد؛ زیرا مرز کاملاً به نمونه‌هایی وابسته است که در لبه‌های خیابان قرار دارند. این نمونه‌ها بردارهای پشتیبان نامیده می‌شوند و در شکل ۵-۱ مشخص شده‌اند.

طبقه‌بندی با حاشیهٔ نرم

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

در شکل ۵-۳ تنها یک دادهٔ پرت به مجموعهٔ Iris افزوده شده است. در نمودار سمت چپ دیگر ساختن یک حاشیهٔ سخت ممکن نیست. در سمت راست، مرز تصمیم در مقایسه با شکل ۵-۱ به‌شدت تغییر کرده است و احتمال تعمیم ضعیف‌تر مدل وجود دارد.

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

هنگام ساخت مدل SVM در Scikit-Learn می‌توان فراپارامترهای گوناگونی تعیین کرد که یکی از مهم‌ترین آن‌ها فراپارامتر منظم‌سازی C است. اگر C کوچک باشد، مدلی شبیه نمودار سمت چپ شکل ۵-۴ به دست می‌آید؛ اگر C بزرگ باشد، مدل سمت راست ایجاد می‌شود. کاهش C حاشیه را پهن‌تر می‌کند، اما نقض‌های حاشیه نیز بیشتر می‌شوند. به بیان دیگر، با کم شدن C نمونه‌های بیشتری در تعیین خیابان نقش پشتیبان دارند و خطر بیش‌برازش کمتر می‌شود. البته اگر مقدار آن بیش از حد کاهش یابد، مدل دچار کم‌برازش می‌شود. در مثال شکل، به نظر می‌رسد مدل با C=100 نسبت به مدل C=1 تعمیم بهتری داشته باشد.

کد زیر مجموعه‌دادهٔ Iris را بارگذاری و یک طبقه‌بند خطی SVM برای تشخیص گل‌های Iris virginica آموزش می‌دهد. Pipeline ابتدا ویژگی‌ها را مقیاس‌بندی می‌کند و سپس از LinearSVC با C=1 استفاده می‌کند:

from sklearn.datasets import load_iris
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import LinearSVC

iris = load_iris(as_frame=True)
X = iris.data[["petal length (cm)", "petal width (cm)"]].values
y = (iris.target == 2)  # Iris virginica

svm_clf = make_pipeline(StandardScaler(),
                        LinearSVC(C=1, random_state=42))
svm_clf.fit(X, y)

مدل حاصل همان مدلی است که در سمت چپ شکل ۵-۴ دیده می‌شود. اکنون مثل همیشه می‌توان برای دادهٔ جدید پیش‌بینی انجام داد:

>>> X_new = [[5.5, 1.7], [5.0, 1.5]]
>>> svm_clf.predict(X_new)
array([ True, False])

نمونهٔ نخست به‌عنوان Iris virginica طبقه‌بندی می‌شود و نمونهٔ دوم نه. امتیازهایی که SVM برای این تصمیم‌ها استفاده کرده است، فاصلهٔ علامت‌دار هر نمونه از مرز تصمیم را اندازه می‌گیرند:

>>> svm_clf.decision_function(X_new)
array([ 0.66163411, -0.22036063])

برخلاف LogisticRegression، کلاس LinearSVC متد predict_proba() برای برآورد احتمال کلاس‌ها ندارد. اگر به‌جای آن از کلاس SVC استفاده کنید و فراپارامتر probability=True را فعال کنید، در پایان آموزش یک مدل اضافی ساخته می‌شود تا امتیازهای تابع تصمیم SVM را به احتمال‌های برآوردی نگاشت کند. برای این کار در پشت صحنه از Cross-Validation پنج‌بخشی استفاده می‌شود تا برای همهٔ نمونه‌های آموزشی پیش‌بینی خارج از نمونه ایجاد شود و سپس یک مدل LogisticRegression آموزش داده شود. بنابراین زمان آموزش به‌طور محسوسی بیشتر خواهد شد. پس از آن متدهای predict_proba() و predict_log_proba() در دسترس خواهند بود.

طبقه‌بندی غیرخطی با SVM

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

نمودار سمت چپ شکل ۵-۵ یک مجموعه‌دادهٔ ساده با فقط یک ویژگی x₁ را نشان می‌دهد که جدایی خطی ندارد. اگر ویژگی دوم x₂ = (x₁)² را اضافه کنیم، مجموعه‌دادهٔ دوبعدی حاصل کاملاً با یک خط قابل جداسازی می‌شود.

برای اجرای این ایده در Scikit-Learn می‌توان Pipelineای ساخت که شامل تبدیل‌کنندهٔ PolynomialFeatures، سپس StandardScaler و در نهایت LinearSVC باشد. این روش را روی مجموعه‌دادهٔ مصنوعی moons آزمایش می‌کنیم؛ در این داده نقاط به شکل دو هلال درهم‌رفته‌اند:

from sklearn.datasets import make_moons
from sklearn.preprocessing import PolynomialFeatures

X, y = make_moons(n_samples=100, noise=0.15, random_state=42)

polynomial_svm_clf = make_pipeline(
    PolynomialFeatures(degree=3),
    StandardScaler(),
    LinearSVC(C=10, max_iter=10_000, random_state=42)
)
polynomial_svm_clf.fit(X, y)

هستهٔ چندجمله‌ای

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

در SVM می‌توان از تکنیکی ریاضی به نام ترفند هسته استفاده کرد. این ترفند امکان می‌دهد نتیجه‌ای معادل افزودن تعداد زیادی ویژگی چندجمله‌ای ــ حتی با درجهٔ بالا ــ به دست آید، بدون آنکه واقعاً آن ویژگی‌ها ایجاد شوند. در نتیجه انفجار ترکیبی تعداد ویژگی‌ها رخ نمی‌دهد. کلاس SVC این قابلیت را پیاده‌سازی می‌کند:

from sklearn.svm import SVC

poly_kernel_svm_clf = make_pipeline(
    StandardScaler(),
    SVC(kernel="poly", degree=3, coef0=1, C=5)
)
poly_kernel_svm_clf.fit(X, y)

این کد یک SVM با هستهٔ چندجمله‌ای درجهٔ ۳ آموزش می‌دهد که در سمت چپ شکل ۵-۷ دیده می‌شود. سمت راست نمونه‌ای با هستهٔ درجهٔ ۱۰ است. اگر مدل بیش‌برازش دارد می‌توان درجهٔ چندجمله‌ای را کاهش داد و اگر کم‌برازش دارد، افزایش درجه می‌تواند مفید باشد. فراپارامتر coef0 تعیین می‌کند مدل تا چه اندازه تحت تأثیر جمله‌های درجات بالا در برابر جمله‌های درجات پایین باشد.

ویژگی‌های شباهت

روش دیگری برای حل مسائل غیرخطی، افزودن ویژگی‌هایی است که با یک تابع شباهت محاسبه می‌شوند. تابع شباهت میزان شباهت هر نمونه به یک نقطهٔ مرجع یا Landmark را اندازه می‌گیرد؛ مشابه ویژگی‌های شباهت جغرافیایی که در فصل ۲ ساخته شد.

در مثال شکل ۵-۸، به مجموعهٔ یک‌بعدی پیشین دو Landmark در x₁ = -2 و x₁ = 1 اضافه می‌شود. تابع شباهت را RBF گاوسی با γ = 0.3 در نظر می‌گیریم؛ تابعی زنگوله‌ای که از ۰ در فاصله‌های زیاد تا ۱ دقیقاً روی Landmark تغییر می‌کند.

برای نمونهٔ x₁ = -1 فاصله تا Landmark نخست برابر ۱ و تا Landmark دوم برابر ۲ است. بنابراین دو ویژگی تازه چنین‌اند:

نمودار سمت راست شکل ۵-۸ مجموعه‌دادهٔ تبدیل‌شده را پس از حذف ویژگی اصلی نشان می‌دهد. دادهٔ جدید اکنون به‌صورت خطی جدایی‌پذیر است.

یک پرسش مهم این است که Landmarkها چگونه انتخاب شوند. ساده‌ترین روش آن است که در محل تک‌تک نمونه‌های مجموعهٔ آموزشی یک Landmark قرار دهیم. این کار ابعاد زیادی ایجاد می‌کند و احتمال جدایی خطی دادهٔ تبدیل‌شده را افزایش می‌دهد. اما هزینهٔ آن زیاد است: مجموعه‌ای با m نمونه و n ویژگی، با فرض حذف ویژگی‌های اصلی، به مجموعه‌ای با m نمونه و m ویژگی تبدیل می‌شود. بنابراین روی داده‌های بزرگ تعداد ویژگی‌ها نیز بسیار بزرگ خواهد شد.

هستهٔ RBF گاوسی

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

rbf_kernel_svm_clf = make_pipeline(
    StandardScaler(),
    SVC(kernel="rbf", gamma=5, C=0.001)
)
rbf_kernel_svm_clf.fit(X, y)

این مدل در پایینِ سمت چپ شکل ۵-۹ نمایش داده شده است. سایر نمودارها مدل‌هایی با مقادیر مختلف γ و C را نشان می‌دهند. افزایش γ تابع زنگوله‌ای را باریک‌تر می‌کند؛ در نتیجه دامنهٔ اثر هر نمونه کوچک‌تر می‌شود و مرز تصمیم با پیچ‌وخم بیشتری به دور نمونه‌های منفرد حرکت می‌کند. کاهش γ تابع را پهن‌تر می‌سازد، دامنهٔ اثر نمونه‌ها را گسترش می‌دهد و مرز تصمیم نرم‌تر می‌شود. بنابراین γ نیز نقش یک فراپارامتر منظم‌سازی را دارد: در بیش‌برازش آن را کاهش دهید و در کم‌برازش افزایش دهید؛ رفتاری مشابه C.

هسته‌های دیگری نیز وجود دارند، اما بسیار کمتر استفاده می‌شوند. بعضی هسته‌ها برای ساختارهای خاص داده طراحی شده‌اند؛ مثلاً هسته‌های رشته‌ای در طبقه‌بندی اسناد متنی یا توالی‌های DNA کاربرد دارند، مانند هستهٔ زیرتوالی رشته یا هسته‌های مبتنی بر فاصلهٔ Levenshtein.

کلاس‌های SVM و پیچیدگی محاسباتی

کلاس LinearSVC بر کتابخانهٔ liblinear متکی است که الگوریتمی بهینه برای SVM خطی دارد. این کلاس ترفند هسته را پشتیبانی نمی‌کند، اما زمان آموزش آن تقریباً به‌صورت خطی با تعداد نمونه‌ها و ویژگی‌ها افزایش می‌یابد و حدود O(m × n) است. اگر دقت عددی بسیار بالا بخواهید، آموزش بیشتر طول می‌کشد؛ این موضوع با فراپارامتر تحمل tol یا ε کنترل می‌شود. مقدار پیش‌فرض در بیشتر مسائل طبقه‌بندی مناسب است.

کلاس SVC بر کتابخانهٔ libsvm بنا شده و ترفند هسته را پشتیبانی می‌کند. پیچیدگی زمانی آموزش آن معمولاً میان O(m² × n) و O(m³ × n) قرار دارد. بنابراین وقتی تعداد نمونه‌ها بسیار زیاد شود ــ مثلاً صدها هزار نمونه ــ به‌شدت کند می‌شود و بیشتر برای مجموعه‌های غیرخطی کوچک یا متوسط مناسب است. از نظر تعداد ویژگی‌ها بهتر مقیاس می‌شود، خصوصاً وقتی ویژگی‌ها Sparse باشند؛ در این حالت هزینه بیشتر به میانگین تعداد ویژگی‌های غیرصفر هر نمونه وابسته است.

کلاس SGDClassifier نیز به‌طور پیش‌فرض طبقه‌بندی با حاشیهٔ بزرگ انجام می‌دهد. با تنظیم فراپارامترهایی مانند alpha، penalty و learning_rate می‌توان نتیجه‌ای شبیه SVM خطی به دست آورد. آموزش آن با گرادیان کاهشی تصادفی انجام می‌شود؛ بنابراین یادگیری افزایشی را پشتیبانی می‌کند، حافظهٔ کمی می‌خواهد و می‌تواند روی مجموعه‌داده‌ای که در RAM جا نمی‌شود به‌صورت Out-of-Core آموزش ببیند. پیچیدگی آن نیز تقریباً O(m × n) است.

رگرسیون با SVM

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

شکل ۵-۱۰ دو مدل رگرسیون خطی SVM را نشان می‌دهد: یکی با حاشیهٔ کوچک ε = 0.5 و دیگری با حاشیهٔ بزرگ‌تر ε = 1.2. کاهش ε تعداد بردارهای پشتیبان را افزایش می‌دهد و مدل را منظم‌تر می‌کند. همچنین اگر نمونه‌های آموزشی جدیدی داخل حاشیه اضافه شوند، پیش‌بینی مدل تغییر نمی‌کند؛ ازاین‌رو گفته می‌شود مدل نسبت به ε بی‌حساسیت است.

برای رگرسیون خطی SVM می‌توان از کلاس LinearSVR استفاده کرد. پیاده‌سازی این مدل در بخش بعد ادامه پیدا می‌کند.