SVM – درک مفاهیم ریاضی مورد نیاز – قسمت سوم

این قسمت سوم از آموزش‌های ریاضی مربوط به ماشین‌های بردار پشتیبان است. اگر قسمت‌های قبلی را هنوز مطالعه نکرده‌اید، می‌توانید آموزش را از قسمت اول با مطالعه مقاله:SVM – درک مفاهیم ریاضی مورد نیاز – قسمت اول شروع کنید.

اما این مقاله در مورد چیست؟

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

در زیر به خلاصه‌ای از مواردی که در ادامه خواهیم دید اشاره شده است:

چطور می‌توان ابرصفحه بهینه را پیدا کرد؟
چطور فاصله بین دو ابرصفحه را محاسبه کنیم؟
مسأله بهینه‌سازی SVM چیست؟

نحوه پیدا کردن ابرصفحه بهینه:

در پایان قسمت دوم فاصله $\|p\|$ بین یک نقطه A و ابرصفحه را محاسبه کردیم. پس مقدار حاشیه که برابر با $2\|p\|$ بود را محاسبه کردیم.

با این که آن حاشیه در جدا کردن داده‌ها، عملکرد خوبی را داشت، ابرصفحه بهینه نبود.

شکل ۱: حاشیه‌ای که در قسمت دوم محاسبه کردیم به صورت M1 نمایش داده شده است.

همان‌طور که در قسمت اول مشاهده کردیم، ابرصفحه‌ای بهینه است که حاشیه داده‌های آموزشی را حداکثر کند.

در شکل ۱ می‌توانیم مشاهده کنیم که حاشیه M1 که با ۲ خط آبی رنگ مشخص شده است(بین ۲ خط آبی قرار دارد)، بزرگ‌ترین حاشیه‌ای که داده‌ها را تفکیک می‌کند نیست. بزرگ‌ترین حاشیه M2 است که در شکل ۲ نمایش داده شده است.

شکل ۲: ابرصفحه بهینه مقداری سمت چپ ابرصفحه‌ای که در قسمت دوم استفاده کردیم قرار دارد.

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

الآن باید متوجه شده باشید که ابرصفحه‌ها و حاشیه‌ها، ارتباط نزدیکی باهم دارند و درست هم متوجه شدید!

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

پیدا کردن بزرگ‌ترین حاشیه در واقع همان پیدا کردن ابرصفحه بهینه است.

چطور می‌توان بزرگ‌ترین حاشیه را پیدا کرد؟

این کار نسبتا ساده است:

شما یک مجموعه داده در اختیار دارید
دو ابرصفحه‌ای که داده را تفکیک می‌کند و هیچ نقطه‌ای بین آن‌ها نیست را انتخاب کنید.
فاصله بین آن‌ها(حاشیه) را به حداکثر برسانید

ناحیه محصور بین دو ابرصفحه، بزرگ‌ترین حاشیه موجود خواهد بود.

اگر به همین سادگی هست، پس چطور اغلب در فهمیدن SVM مشکل دارند؟

به این دلیل که معمولا سادگی به مقداری انتزاع و اصطلاحات ریاضی نیاز دارد تا خوب فهمیده شود.

در ادامه این دستورالعمل را قدم‌به‌قدم بررسی خواهیم کرد.

قدم اول: مجموعه داده‌ای داریم (D) و می‌خواهیم آن را طبقه‌بندی کنیم.

بیشتر وقت‌ها داده ما از $n$ بردار $x_i$ تشکیل می‌شوند.

به هر $x_i$ مقداری مانند $y_i$ انتساب داده می‌شود که مشخص می‌کند این المان (بردار) متعلق به کلاس $+1$ است یا کلاس $-1$ .

توجه کنید که $y_i$ تنها می‌تواند مقدارهای $+1$ یا $-1$ را داشته باشد.

مورد دیگر این‌که، بیشتر وقت‌ها برای مثال وقتی که می‌خواهیم طبقه‌بندی متن را انجام دهیم، بردار $x_i$ ما دارای تعداد زیادی بعد خواهد بود. پس اگر بردار $ٓx_i$ ، $p$ داشته باشد، می‌توانیم آن را یک بردار $p$ -بعدی بنامیم.

پس مجموعه داده شما (D)، یک مجموعه $n$ تایی از زوج‌های مرتب $(x_i, y_i)$ است.

تعریف رسمی‌تر یک مجموعه داده ابتدایی در مجموعه نظریه‌ها به صورت زیر است:

$D = \{(x_i, y_i) | x_i \in \mathbb{R}^p , y_i \in \{-1,1\} \}_i ^ n$

قدم دوم: ما نیاز داریم که دو ابرصفحه جداکننده که داده‌ را تفکیک کند و داده‌ای بین آن نباشد را انتخاب کنیم

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

علاوه بر آن، حتی اگر داده ما ۲-بعدی باشد، پیدا کردن ابرصفحه جداکننده، ممکن نخواهد بود! شما در صورتی می‌توانید این ابرصفحه را رسم کنید که داده به صورت خطی تفکیک‌پذیر باشد.

شکل ۳: داده شکل سمت چپ به کمک یک صفحه قابل تفکیک است، درحالی که داده شکل سمت راست این‌گونه نیست.

پس فرض کنیم که داده ما D به‌صورت خطی تفکیک‌پذیر باشد. می‌خواهیم دو ابرصفحه پیدا کنیم که داده‌ای بین آن‌ها نباشد، اما راهی برای نمایش آن‌ها نداریم.

نگاهی دیگر به معادله ابرصفحه

قبلا دیدیم که معادله ابرصفحه به‌صورت زیر می‌تواند نوشته شود.

$w^Tx=0$

همچنین، در ویکی‌پدیا مقاله‌ای در مورد ماشین بردار پشتیبان گفته‌شده که:

هر ابرصفحه می‌تواند به‌صورت مجموعه‌ای از نقطه‌های $x$ که در معادله $w.x+b=0$ صدق می‌کنند، نشان داده شود.

اول، علامت دیگری برای ضرب نقطه‌ای می‌بینیم. در مقاله از $w.x$ به‌جای $w^Tx$ استفاده شده‌است.

ممکن است که تعجب کنید… $+b$ از کجا آمده است؟ آیا تعریف قبلی ما نادرست بوده‌است؟ جواب خیر است. همه‌چیز به نحوه استفاده از علامت‌ها برمی‌گردد. در تعریف ما بردارهای $w$ و $x$ سه بعد دارند، درحالی که در ویکی‌پدیا دو بعد دارند:

با داشتن دو بردار سه-بعدی $w(b, -a, 1)$ و $x(1, x, y)$ داریم:

$w.x = b \times (1) + (-a) \times x + 1 \times y$

$w.x = y - ax + b\quad (1)$

با داشتن دو بردار دو-بعدی $w^{\prime}(-a, 1)$ و $x^{\prime}(x, y)$ داریم:

$w^{\prime}.x^{\prime} = (-a) \times x + 1 \times y$

$w^{\prime} . x^{\prime} = y - ax \quad (2)$

حالا اگر $b$ را به دو طرف معادله (۲) اضافه کنیم خواهیم داشت:

$w^{\prime} . x^{\prime} + b = y -ax + b$

$w^{\prime}.x^{\prime} + b = w.x \quad (3)$

در ادامه این آموزش از بردارهای دو-بعدی استفاده خواهیم کرد.(مانند معادله (۲)).

با داشتن ابرصفحه $H_0$ که داده را تفکیک و در معادله زیر صدق می‌کند:

$w.x + b = 0$

می‌توانیم دو ابرصفحه دیگر مثل $H_1$ و $H_2$ که ‌آن‌ها هم داده را تفکیک می‌کنند و دارای معادله زیر هستند را انتخاب کنیم:

$w.x + b = \delta$

$w.x + b = -\delta$

در نتیجه فاصله $H_0$ از $H_1$ و $H_2$ برابر است.

همچنین در این‌جا متغیر $\delta$ ضروری نیست، پس ما می‌توانیم برای ساده‌تر شدن مسأله، $\delta = 1$ در نظر بگیریم.

$w.x + b =1$

$w.x + b = -1$

حال می‌خواهیم مطمئن شویم که نقطه‌ای(داده‌ای) بین آن‌ها نیست.

ما هر ابرصفحه‌ای را انتخاب نمی‌کنیم. تنها آن‌هایی را انتخاب می‌کنیم که از قیدهای(محدودیت‌های) زیر پیروی می‌کنند:

برای هر بردار $x_i$ :

$w.x_i+b \geq 1 \quad(4)$ برای $x_i$ هایی که دارای کلاس ۱ هستند

یا

$w.x_i+b \leq -1 \quad(5)$ برای $x_i$ هایی که دارای کلاس ۱- هستند

درک قیدها (محدودیت‌ها)

در شکل‌های زیر، نقطه‌های قرمز متعلق به کلاس ۱ و نقطه‌های آبی متعلق به کلاس ۱- هستند.

به شکل ۴ توجه کنید و نقطه A را در نظر بگیرید. رنگ آن قرمز است، پس متعلق به کلاس ۱ است و ما باید از این‌که قید $w.x_i + b \geq 1$ را نقض نکند، اطمینان حاصل کنیم.

زمانی که $x_i = A$ باشد، می‌بینیم که نقطه روی ابرصفحه وجود دارد. پس $w.x_i + =1$ و قید مسأله نیز نقض نشده است. همین عبارت برای نقطه B هم صادق است.

زمانی که $x_i=c$ باشد، می‌بینیم که نقطه در بالای ابرصفحه است. پس $w.x_i + b > 1$ و قید مسأله نیز نقض نشده است. همین عبارت برای نقطه‌های G, F, E, و D نیز صادق است.

به دلیل‌های مشابه، متوجه خواهیم شد که قید دوم نیز برای کلاس -۱ صادق است.

شکل ۴: دو ابرصفحه با توجه به قیدهای مسأله

در شکل ۵ یک جفت ابرصفحه دیگر را با توجه به قیدهای مسأله را مشاهده می‌کنیم:

شکل ۵: دو ابرصفحه دیگر با توجه به قیدهای مسأله

حال موردهایی را ارزیابی می‌کنیم که قیدهای مسأله را نقض می‌کنند:

شکل ۶: ابرصفحه سمت راست قید اول مسأله را نقض می‌کند

شکل ۷: ابرصفحه سمت چپ قید دوم مسأله را نقض می‌کند

شکل ۸: هر دو قید مسأله نقض شده‌اند

ولی این که قید مسأله نقض شود به چه معنی هست؟ به این معنی که ما نمی‌توانیم این دو ابرصفحه را انتخاب کنبم. در این حالت می‌توانیم مشاهده کنیم که هربار قیدها نقض شده‌اند (شکل‌ ۶، ۷ و ۸) نقطه‌های بین ابرصفحه‌ها قرار گرفته‌اند.

با تعریف کردن این قیدها، راهی پیدا کردیم که به هدف اولیه که همان انتخاب دو ابرصفحه بدون نقطه‌ای بین آن‌ها بود، برسیم و این نه تنها برای مثال‌های ما بلکه برای فضاهای p-بعدی هم کار می‌کند!

ترکیب هر دو قید

در ریاضی، همه دوست دارند که چیزها را به صورت ساده نمایش دهند.

معادله‌های (۴) و (۵) می‌توانند به صورت یک قید تکی باهم ترکیب شوند:

با معادله (۵) شروع می‌کنیم

برای $x_i$ که دارای کلاس ۱- هستند

$w.x_i+b\leq-1$

و ضرب هر دو طرف آن در $y_i$ (که همیشه در این معادله برابر ۱- است)

$y_i(w.x_i+b) \geq y_i(-1)$

که یعنی معادله (۵) می‌تواند به صورت زیر نوشته شود:

$y_i(w.x_i+b) \geq 1 \quad(6)$ برای $x_i$ هایی که دارای کلاس ۱- هستند

در معادله (۴) چون $y_i=1$ علامت نامساوی را تغییر نمی‌دهد.

$y_i(w.x_i+b) \geq 1 \quad (7)$ برای $x_i$ هایی که دارای کلاس ۱ هستند

معادله‌های (۶) و (۷) را ترکیب می‌کنیم:

$y_i(w.x_i+b) \geq 1 \quad (8)$ برای همه $1 \leq i \leq n$

حال به‌جای دو قید (معادله‌های ۴ و ۵)، یک قید واحد (معادله ۸) را داریم، ولی آن‌ها از نظر ریاظی مساوی هستند. پس اثر آن‌ها نیز مثل هم است (هیچ نقطه‌ای بین دو ابرصفحه نخواهد بود).

قدم سوم: بیشینه کردن فاصله بین دو ابرصفحه

این احتمالا مشکل‌ترین قسمت مسأله است. ولی جای نگرانی نیست، همه چیز را توضیح خواهم داد.

الف) فاصله بین دو ابرصفحه چقدر است؟

قبل از سعی کردن برای بیشینه کردن فاصله بین ۲ ابرصفحه، باید از خودمان بپرسیم که چطور باید این کار را انجام دهیم؟

فرض کنیم:

$H_0$ ابرصفحه‌ای با معادله $w.x+b = -1$ باشد
$H_1$ ابرصفحه‌ای با معادله $w.x+b =1$ باشد
$x_0$ یک نقطه روی ابرصفحه $H_0$ باشد

m را فاصله خط عمود از $x_0$ تا ابرصفحه $H_1$ می‌نامیم. بنا به تعریف، m چیزی است که ما آن را حاشیه می‌نامیم.

و چون $x_0$ روی $H_0$ است، m همان فاصله بین ابرصفحه‌های $H_0$ و $H_1$ است.

حال سعی خواهیم کرد که مقدار m را پیدا کنیم.

شکل ۹: m فاصله بین دو ابرصفحه است

ممکن است فکر کنید که اگر m را $x_0$ اضافه کنیم، نقطه دیگری به دست خواهد آمد و این نقطه روی ابرصفحه دیگر خواهد بود!

ولی این ایده کار نخواهد کرد. دلیلش هم این است که m یک اسکالر و $x_0$ یک بردار است و به همین دلیل جمع این دو باهم امکان‌پذیر نیست. می‌دانیم که جمع دو بردار امکان‌پذیر است، پس اگر m را به فرم یک بردار در بیاوریم، می‌توانیم آن‌ها را باهم جمع کنیم.

می‌توانیم مجموعه‌ای از نقطه‌ها را پیدا کنیم که در فاصله m از $x_0$ باشند. این را می‌توان به‌صورت یک دایره نمایش داد.

شکل ۱۰: همه نقطه‌های روی دایره، در فاصله m از $x_0$ قرار دارند

با مشاهده عکس ضرورت تبدیل کردن به بردار مشخص خواهد شد. ما فقط طول m را محاسبه کردیم و هنوز یک مورد مهم دیگر را نداریم: جهت. (با توجه به قسمت دوم، هر بردار یک جهت و یک اندازه دارد).

ما نمی‌توانیم یک اسکالر را با یک بردار جمع کنیم، ولی می‌دانیم که اگر یک اسکالر را در یک بردار ضرب کنیم، بردار دیگری به دست خواهد آمد.

با توجه به صورت مسأله، برداری که ما درنظر داریم:

دارای اندازه m است
بر ابرصفحه $H_1$ عمود است

خوشبختانه از قبل یک بردار عمود بر $H_1$ را داریم و آن هم w است. (به این دلیل که $H_1 = w.x+b = 1$ است)

شکل ۱۱: w بر ابرصفحه $H_1$ عمود است

$u=\frac{w}{\|w\|}$ را بردار واحد w تعریف می‌کنیم. از آن‌جایی که این یک بردار واحد است: $\|u\| = 1$ و هم جهت با بردار w است، پس آن هم بر ابرصفحه عمود است.

شکل ۱۲: u نیز بر ابرصفحه $H_1$ عمود است

اگر u را در w ضرب کنیم، بردار $k = mu$ به دست می‌آید و:

$\|k\| = m$
k بر ابرصفحه $H_1$ عمود است (چون با u هم‌جهت است)

با توجه به این خاصیت‌ها می‌توانیم مشاهده کنیم k برداری است که دنبال آن می‌گشتیم.

شکل ۱۳: k برداری به طول m و عمود بر ابرصفحه $H_1$ است

$k=mu=m\frac{w}{\|w\|} \quad(9)$

انجام شد! اسکالر m را به بردار k تبدیل کردیم که می‌توانیم از آن استفاده کنیم تا عمل جمع با بردار $x_0$ را انجام دهیم.

اگر از نقطه $x_0$ شروع کنیم و مقدار k را به آن اضافه کنیم، نقطه $z_0=x_0+k$ به دست می‌آید که روی ابرصفحه $H_1$ قرار دارد و در شکل ۱۴ نمایش داده‌شده‌ است.

شکل ۱۴: $z_0$ یک نقطه روی $H_1$ است

این واقعیت که $z_0$ روی $H_1$ است، همچنین به معنی عبارت زیر است:

$w.z_0+b=1 \quad(10)$

می‌توانیم $z_0$ را با $x_0+k$ جایگزین کنیم.

$w.(x_0+k)+b=1 \quad(11)$

می‌توانیم k را با استفاده از معادله (۹) جایگزین کنیم

$w.(x_0+m\frac{w}{\|w\|})+b=1 \quad(12)$

حال معادله (۱۲) را باز می‌کنیم

$w.x_0+m\frac{w.w}{\|w\|}+b=1 \quad(13)$

ضرب نقطه‌ای یک بردار در خودش، برابر با مربع اندازه‌اش است. پس:

$w.x_0+m\frac{\|w\|^2}{\|w\|}+b=1 \quad(14)$

$w.x_0+m\|w\|+b=1 \quad(15)$

$w.x_0+b=1-m\|w\| \quad(16)$

چون $x_0$ روی $H_0$ است، پس: $w.x_0+b=-1$

$-1=1-m\|w\| \quad(17)$

$m\|w\|=2 \quad(18)$

$m=\frac{2}{\|w\|} \quad(19)$

به این ترتیب راهی برای محاسبه m پیدا کردیم.

ب) چطور فاصله بین دو ابرصفحه را بیشینه کنیم

حال فرمولی برای محاسبه حاشیه داریم:

$m=\frac{2}{\|w\|}$

تنها متغیری که در این فرمول می‌توانیم تغییر دهیم، اندازه w است.

این فرمول را برای مقدارهای مختلف بررسی می‌کنیم:

زمانی که $\|w\|=1$ باشد، $m=2$ است
زمانی که $\|w\|=2$ باشد، $m=1$ است
زمانی که $\|w\|=4$ باشد، $m=\frac{1}{2}$ است

می‌توان مشاهده کرد که اندازه (نرم) بیشتر، مقدار حاشیه کمتر را به همراه خواهد داشت.

بیشینه کردن حاشیه درواقع همان کمینه کردن نرم w است

هدف ما به حداکثر رساندن مقدار حاشیه است. در میان همه ابرصفحه‌های ممکن که قیدهای مسأله را رعایت می‌کنند، ابرصفحه‌ای با کوچک‌ترین $\|w\|$ را انتخاب می‌کنیم، به این دلیل که بیشترین حاشیه را خواهد داشت،

این برای ما مسأله بهینه‌سازی زیر را به وجود می‌آورد:

کمینه کردن با توجه به (w, b)

$\|w\|$

با توجه به $y_i(w.x_i+b) \geq 1$

(برای هر $i=1, ..., n$ )

حل این مسأله مشابه حل کردن یک معادله است. زمانی که آن را حل کردیم، زوج (w, b) را برای $\|w\|$ خواهیم داشت که کوچک‌ترینمقدار ممکن است و همچنین قیدهای مسأله نیز درنظر گرفته خواهند شد. و این یعنی معادله ابرصفحه بهینه را خواهیم داشت!

نتیجه‌گیری

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

اشتراک‌گذاری

لایه‌های مخفی یک داده پرت

روزنوشته‌های یک علاقمند به یادگیری انسان، ماشین و علم داده