ادامهٔ رگرسیون با SVM
برای رگرسیون خطی SVM میتوان از کلاس LinearSVR استفاده کرد. کد زیر مدل خطی شکل ۵-۱۰ را با ε = 0.5 میسازد:
from sklearn.svm import LinearSVR
X, y = [...] # a linear dataset
svm_reg = make_pipeline(
StandardScaler(),
LinearSVR(epsilon=0.5, random_state=42)
)
svm_reg.fit(X, y)
برای مسائل رگرسیون غیرخطی میتوان از SVM هستهای استفاده کرد. شکل ۵-۱۱ رگرسیون SVM را روی یک مجموعهٔ آموزشی تصادفی درجهٔ دوم با هستهٔ چندجملهای درجهٔ ۲ نشان میدهد. نمودار سمت چپ منظمسازی بیشتری دارد، یعنی C کوچکتر است؛ در نمودار سمت راست C بزرگتر و منظمسازی کمتر است.
شکل 5-11. رگرسیون SVM با هستهٔ چندجملهای درجهٔ ۲
کد زیر با کلاس SVR ــ که ترفند هسته را پشتیبانی میکند ــ مدل سمت چپ شکل ۵-۱۱ را ایجاد میکند:
from sklearn.svm import SVR
X, y = [...] # a quadratic dataset
svm_poly_reg = make_pipeline(
StandardScaler(),
SVR(kernel="poly", degree=2, C=0.01, epsilon=0.1)
)
svm_poly_reg.fit(X, y)
SVR همتای رگرسیونی SVC است و LinearSVR نقش مشابه LinearSVC را برای رگرسیون دارد. LinearSVR با اندازهٔ مجموعهٔ آموزشی تقریباً خطی مقیاس میشود، اما SVR با بزرگشدن شدید مجموعهٔ آموزشی بسیار کند میشود. SVMها برای تشخیص تازگی نیز قابل استفادهاند؛ این موضوع در فصل ۹ بررسی میشود.
درون طبقهبندهای خطی SVM
بخش باقیماندهٔ فصل توضیح میدهد SVM چگونه پیشبینی میکند و الگوریتمهای آموزش آن چگونه کار میکنند. اگر تازه یادگیری ماشین را آغاز کردهاید، میتوانید این بخش نظری را فعلاً رد کنید و بعداً برای درک عمیقتر به آن بازگردید.
طبقهبند خطی SVM برای نمونهٔ جدید x ابتدا تابع تصمیم زیر را محاسبه میکند:
θᵀx = θ₀x₀ + ⋯ + θₙxₙ
در این نمایش، x₀ ویژگی بایاس و همیشه برابر ۱ است. اگر مقدار تابع تصمیم مثبت باشد، کلاس پیشبینیشده کلاس مثبت یعنی ۱ خواهد بود؛ در غیر این صورت کلاس منفی یعنی ۰ پیشبینی میشود. این منطق شبیه LogisticRegression در فصل ۴ است.
تا اینجا همهٔ پارامترهای مدل در بردار θ قرار میگرفتند و θ₀ جملهٔ بایاس بود؛ بنابراین لازم بود x₀ = 1 به همهٔ نمونهها افزوده شود. قرارداد رایج دیگری بایاس را بهصورت b = θ₀ از بردار وزنها w = (θ₁,…,θₙ) جدا میکند. در این قرارداد تابع تصمیم wᵀx + b است و دیگر نیازی به افزودن ویژگی بایاس نیست. در ادامهٔ کتاب از همین قرارداد استفاده میشود.
پیشبینی با SVM خطی ساده است؛ مسئلهٔ اصلی آموزش است. باید بردار وزن w و بایاس b طوری پیدا شوند که حاشیه تا حد ممکن پهن باشد و همزمان نقضهای حاشیه محدود شوند. برای پهنتر شدن خیابان لازم است اندازهٔ w کوچکتر شود.
در شکل ۵-۱۲ مرزهای حاشیه نقاطی هستند که تابع تصمیم مقدار ۱- یا ۱+ دارد. در سمت چپ w₁ = 1 است؛ بنابراین مرزها در x₁ = -1 و x₁ = +1 قرار میگیرند و عرض حاشیه ۲ است. در سمت راست w₁ = 0.5 است، پس مرزها در ۲- و ۲+ قرار میگیرند و عرض حاشیه ۴ میشود. بایاس b بر عرض حاشیه اثر ندارد و فقط کل حاشیه را جابهجا میکند.
شکل 5-12. بردار وزن کوچکتر به حاشیهٔ بزرگتر منجر میشود
هدف حاشیهٔ سخت
برای جلوگیری از نقض حاشیه، میخواهیم خروجی تابع تصمیم برای همهٔ نمونههای مثبت بیشتر یا مساوی ۱ و برای نمونههای منفی کمتر یا مساوی ۱- باشد. اگر برای نمونههای منفی t⁽ⁱ⁾ = -1 و برای نمونههای مثبت t⁽ⁱ⁾ = +1 تعریف کنیم، قید همهٔ نمونهها چنین نوشته میشود:
t⁽ⁱ⁾(wᵀx⁽ⁱ⁾ + b) ≥ 1
بنابراین مسئلهٔ بهینهسازی حاشیهٔ سخت بهصورت زیر بیان میشود:
معادلهٔ ۵-۱ ــ هدف طبقهبند خطی SVM با حاشیهٔ سخت
minimizew,b ½ wᵀw
subject to: t⁽ⁱ⁾(wᵀx⁽ⁱ⁾ + b) ≥ 1 برای i = 1,…,m
بهجای کمینهکردن مستقیم نرم ∥w∥، مقدار ½∥w∥² = ½wᵀw کمینه میشود؛ زیرا مشتق آن ساده و برابر w است، در حالی که نرم در w = 0 مشتقپذیر نیست. الگوریتمهای بهینهسازی معمولاً با توابع مشتقپذیر بسیار بهتر کار میکنند.
هدف حاشیهٔ نرم و متغیرهای Slack
برای حاشیهٔ نرم، برای هر نمونه یک متغیر Slack با نماد ζ⁽ⁱ⁾ ≥ 0 معرفی میشود. این مقدار مشخص میکند نمونهٔ i تا چه اندازه اجازه دارد حاشیه را نقض کند. حال دو هدف متضاد داریم: Slackها باید کوچک بمانند تا نقض حاشیه کم شود، و همزمان ½wᵀw نیز کوچک شود تا حاشیه پهن گردد. فراپارامتر C موازنهٔ این دو هدف را تعیین میکند.
معادلهٔ ۵-۲ ــ هدف طبقهبند خطی SVM با حاشیهٔ نرم
minimizew,b,ζ ½ wᵀw + C Σᵢ ζ⁽ⁱ⁾
subject to: t⁽ⁱ⁾(wᵀx⁽ⁱ⁾ + b) ≥ 1 − ζ⁽ⁱ⁾
and ζ⁽ⁱ⁾ ≥ 0 برای i = 1,…,m
مسائل حاشیهٔ سخت و نرم هر دو مسائل بهینهسازی درجهٔ دوم محدب با قیود خطی هستند و به آنها Quadratic Programming (QP) گفته میشود. حلگرهای آمادهٔ متعددی برای QP وجود دارند.
یک راه آموزش SVM استفاده از حلگر QP است. راه دیگر، کمینهکردن زیان Hinge یا زیان Hinge مربعی با گرادیان کاهشی است. برای نمونهٔ مثبت با t=1 اگر امتیاز s = wᵀx+b ≥ 1 باشد، زیان صفر است؛ یعنی نمونه در بیرون حاشیه و سمت صحیح قرار دارد. برای نمونهٔ منفی با t=-1 نیز اگر s ≤ -1 باشد زیان صفر است. هرچه نمونه از سمت صحیح حاشیه دورتر شود، زیان بیشتر میشود. در Hinge معمولی رشد زیان خطی است و در Hinge مربعی رشد آن درجهٔ دوم است؛ بنابراین نوع مربعی نسبت به دادههای پرت حساستر است، اما روی دادهٔ تمیز معمولاً سریعتر همگرا میشود.
شکل 5-13. زیان Hinge و زیان Hinge مربعی
LinearSVC بهطور پیشفرض از squared_hinge و SGDClassifier از hinge استفاده میکند؛ در هر دو میتوان با فراپارامتر loss نوع زیان را تعیین کرد. الگوریتم بهینهسازی SVC نیز به راهحلی شبیه کمینهکردن زیان Hinge میرسد.
مسئلهٔ دوگان
برای یک مسئلهٔ بهینهسازی مقید که مسئلهٔ اولیه یا Primal نام دارد، میتوان مسئلهای متفاوت اما مرتبط به نام مسئلهٔ دوگان یا Dual تعریف کرد. جواب مسئلهٔ دوگان معمولاً کران پایینی برای جواب اولیه فراهم میکند؛ اما تحت شرایطی خاص میتواند دقیقاً همان جواب را داشته باشد. مسئلهٔ SVM این شرایط را دارد، بنابراین میتوان Primal یا Dual را حل کرد و به پاسخ یکسان رسید.
معادلهٔ ۵-۳ ــ فرم دوگان هدف SVM خطی
minimizeα ½ Σᵢ Σⱼ α⁽ⁱ⁾α⁽ʲ⁾t⁽ⁱ⁾t⁽ʲ⁾ x⁽ⁱ⁾ᵀx⁽ʲ⁾ − Σᵢ α⁽ⁱ⁾
subject to: α⁽ⁱ⁾ ≥ 0 برای همهٔ i، و Σᵢ α⁽ⁱ⁾t⁽ⁱ⁾ = 0
پس از یافتن بردار α با یک حلگر QP، پارامترهای مسئلهٔ اولیه را میتوان از رابطهٔ زیر به دست آورد. در اینجا nₛ تعداد بردارهای پشتیبان است:
معادلهٔ ۵-۴ ــ تبدیل جواب دوگان به جواب اولیه
w = Σᵢ α⁽ⁱ⁾ t⁽ⁱ⁾ x⁽ⁱ⁾
b = (1/nₛ) Σi: α⁽ⁱ⁾>0 [t⁽ⁱ⁾ − wᵀx⁽ⁱ⁾]
وقتی تعداد نمونههای آموزشی از تعداد ویژگیها کمتر باشد، حل مسئلهٔ دوگان از حل Primal سریعتر است. مهمتر از آن، ترفند هسته از فرم دوگان ممکن میشود، در حالی که از فرم اولیه چنین امکانی وجود ندارد.
SVM هستهای و ترفند هسته
فرض کنید یک تبدیل چندجملهای درجهٔ ۲ را به یک مجموعهٔ دوبعدی اعمال کنید و سپس روی دادهٔ تبدیلشده SVM خطی آموزش دهید. نگاشت زیر یک نمونهٔ دوبعدی را به برداری سهبعدی میبرد:
معادلهٔ ۵-۵ ــ نگاشت چندجملهای درجهٔ ۲
φ([x₁,x₂]ᵀ) = [x₁², √2 x₁x₂, x₂²]ᵀ
اگر این نگاشت روی دو بردار a و b اعمال شود، ضرب داخلی بردارهای تبدیلشده برابر مربع ضرب داخلی بردارهای اصلی خواهد شد:
معادلهٔ ۵-۶
φ(a)ᵀφ(b) = (aᵀb)²
نکتهٔ کلیدی اینجاست: اگر تبدیل φ روی همهٔ نمونههای آموزشی اعمال شود، مسئلهٔ دوگان شامل ضربهای داخلی φ(x⁽ⁱ⁾)ᵀφ(x⁽ʲ⁾) خواهد بود. برای این نگاشت خاص میتوان این عبارت را مستقیماً با (x⁽ⁱ⁾ᵀx⁽ʲ⁾)² جایگزین کرد. بنابراین لازم نیست نمونهها را واقعاً به فضای جدید تبدیل کنیم؛ کافی است ضرب داخلی را در مسئلهٔ دوگان با تابع هسته جایگزین کنیم. نتیجه دقیقاً همان نتیجهٔ تبدیل صریح داده و سپس آموزش SVM خطی است، اما از نظر محاسباتی بسیار کارآمدتر.
تابع K(a,b) = (aᵀb)² نمونهای از هستهٔ چندجملهای درجهٔ ۲ است. بهطور کلی هسته تابعی است که مقدار φ(a)ᵀφ(b) را فقط از روی بردارهای اصلی a و b محاسبه میکند، بدون آنکه لازم باشد خود φ را محاسبه یا حتی بهطور صریح بشناسیم.
معادلهٔ ۵-۷. چند هستهٔ رایج
| خطی | K(a,b) = aᵀb |
|---|
| چندجملهای | K(a,b) = (γaᵀb + r)ᵈ |
|---|
| RBF گاوسی | K(a,b) = exp(-γ∥a-b∥²) |
|---|
| سیگموید | K(a,b) = tanh(γaᵀb + r) |
|---|
قضیهٔ مرسر
بر اساس قضیهٔ Mercer، اگر تابع K(a,b) چند شرط ریاضی ــ از جمله پیوستگی و تقارن K(a,b)=K(b,a) ــ را برآورده کند، تابع نگاشتی φ وجود دارد که بردارهای a و b را به فضای دیگری، احتمالاً با ابعاد بسیار بیشتر، میبرد و رابطهٔ K(a,b)=φ(a)ᵀφ(b) برقرار است. بنابراین حتی اگر خود نگاشت را ندانیم، میتوانیم K را بهعنوان هسته به کار ببریم.
در مورد هستهٔ RBF گاوسی میتوان نشان داد که φ هر نمونه را به فضایی با بینهایت بُعد نگاشت میکند؛ خوشبختانه ترفند هسته باعث میشود هیچ نیازی به ساخت واقعی آن فضای نامتناهی نداشته باشیم. بعضی هستههای پرکاربرد، مانند هستهٔ سیگموید، تمام شروط Mercer را برآورده نمیکنند، اما در عمل اغلب خوب کار میکنند.
پیشبینی بدون محاسبهٔ صریح w
در SVM هستهای، بردار w باید بهاندازهٔ فضای تبدیلشده بعد داشته باشد؛ این فضا ممکن است بسیار بزرگ یا حتی بینهایتبعدی باشد، پس محاسبهٔ مستقیم w ممکن نیست. راهحل آن است که رابطهٔ w از معادلهٔ ۵-۴ را داخل تابع تصمیم جایگذاری کنیم. در نتیجه فقط ضربهای داخلی میان بردارهای ورودی باقی میماند و میتوان از هسته استفاده کرد:
معادلهٔ ۵-۸ ــ پیشبینی با SVM هستهای
hw,b(φ(x⁽ⁿ⁾)) = Σi: α⁽ⁱ⁾>0 α⁽ⁱ⁾t⁽ⁱ⁾K(x⁽ⁱ⁾,x⁽ⁿ⁾) + b
چون α⁽ⁱ⁾ فقط برای بردارهای پشتیبان غیرصفر است، هنگام پیشبینی لازم نیست ورودی جدید با همهٔ نمونههای آموزشی مقایسه شود؛ فقط هسته میان نمونهٔ جدید و بردارهای پشتیبان محاسبه میشود. برای محاسبهٔ بایاس نیز از ترفند مشابه استفاده میشود:
معادلهٔ ۵-۹ ــ محاسبهٔ بایاس با ترفند هسته
b = (1/nₛ) Σi: α⁽ⁱ⁾>0 [t⁽ⁱ⁾ − Σj: α⁽ʲ⁾>0 α⁽ʲ⁾t⁽ʲ⁾K(x⁽ⁱ⁾,x⁽ʲ⁾)]
پیچیدگی ریاضی این قسمت طبیعی است؛ هدف اصلی آن نشاندادن این نکته است که ترفند هسته چگونه بدون ساخت فضای ویژگی با ابعاد بسیار بالا، همان محاسبات لازم برای SVM غیرخطی را ممکن میکند.
SVM هستهای برخط و دارای یادگیری افزایشی نیز در پژوهشها پیادهسازی شده است. منابع ذکرشده در کتاب نمونههایی در Matlab و C++ ارائه میکنند. برای مسائل غیرخطی در مقیاس بسیار بزرگ، جنگلهای تصادفی یا شبکههای عصبی نیز گزینههای مهمی هستند.
تمرینهای فصل ۵
- ایدهٔ بنیادی ماشینهای بردار پشتیبان چیست؟
- بردار پشتیبان چیست؟
- چرا هنگام استفاده از SVM مقیاسبندی ورودیها اهمیت دارد؟
- آیا طبقهبند SVM میتواند هنگام طبقهبندی یک نمونه، امتیاز اطمینان خروجی بدهد؟ احتمال کلاس چطور؟
- چگونه میان
LinearSVC، SVC و SGDClassifier انتخاب میکنید؟
- فرض کنید SVM با هستهٔ RBF آموزش دادهاید اما مدل روی مجموعهٔ آموزشی کمبرازش دارد. γ را باید افزایش دهید یا کاهش؟ دربارهٔ
C چه میکنید؟
- بیحساسیت نسبت به ε برای یک مدل چه معنایی دارد؟
- هدف استفاده از ترفند هسته چیست؟
- روی یک مجموعهدادهٔ خطی جداییپذیر ابتدا
LinearSVC و سپس SVC و SGDClassifier را آموزش دهید و تلاش کنید تقریباً مدل یکسانی تولید کنند.
- با
sklearn.datasets.load_wine() طبقهبند SVMای روی مجموعهٔ Wine آموزش دهید. این مجموعه تحلیل شیمیایی ۱۷۸ نمونه شراب از سه تولیدکننده را دارد و هدف پیشبینی تولیدکننده بر اساس ویژگیهای شیمیایی است. برای سه کلاس از راهبرد One-versus-All استفاده کنید و دقت نهایی را بررسی کنید.
- یک رگرسور SVM را روی مجموعهدادهٔ California Housing آموزش و تنظیم کنید. میتوانید از
sklearn.datasets.fetch_california_housing() استفاده کنید. چون بیش از ۲۰٬۰۰۰ نمونه وجود دارد و SVM میتواند کند باشد، برای جستوجوی فراپارامترها ابتدا روی تعداد بسیار کمتری، مثلاً ۲٬۰۰۰ نمونه، ترکیبهای بیشتری را آزمایش کنید. بهترین RMSE شما چقدر میشود؟
راهحل تمرینها در انتهای Notebook همین فصل در منبع تکمیلی کتاب ارائه شده است.