תרגול 6 - SVM ופונקציות גרעין (Kernels)

PDF

תקציר התיאוריה

הערה: בפרק זה נעסוק בסיווג בינארי ונסמן את התוויות של שתי המחלקות ב 11 ו −1-1.

תזכורת - גאומטריה של המישור

  • מישור מתואר באופן הבא w⊤x+b=0\boldsymbol{w}^{\top}\boldsymbol{x}+b=0.
  • המישור מחלק את המרחב ומגדיר צד חיובי וצד שלילי.
  • w\boldsymbol{w} הינו הנורמל למישור.
  • המרחק של המישור מהראשית הינו b∥w∥\frac{b}{\lVert\boldsymbol{w}\rVert}.
  • המרחק של נקודה x0\boldsymbol{x}_0 מהמישור הינה 1∥w∥(w⊤x0+b)\frac{1}{\lVert\boldsymbol{w}\rVert}(\boldsymbol{w}^{\top}\boldsymbol{x}_0+b).
  • w\boldsymbol{w} ו bb מוגדרים עד כדי קבוע.

מסווג לינארי

מסווג לינארי הוא מסווג מהצורה של

h(x)=sign(w⊤x+b)={1w⊤x+b>0−1elseh(\boldsymbol{x})= \text{sign}(\boldsymbol{w}^{\top}\boldsymbol{x}+b) =\begin{cases} 1 & \boldsymbol{w}^{\top}\boldsymbol{x}+b>0\\ -1 & \text{else} \end{cases}

עם w\boldsymbol{w} ו- bb כל שהם.

  • המסווג מחלק את המרחב לשני צידיו של המישור:

    • w⊤x+b=0\boldsymbol{w}^{\top}\boldsymbol{x}+b=0
    • מישור זה מכונה מישור ההפרדה.

Signed distance (מרחק מסומן)

נסתכל על בעיית סיווג בינארית עם תוויות y=±1\text{y}=\pm1.

  • נגדיר את ה- signed distance של דגימה כל שהיא ממשטח ההפרדה באופן הבא:
d=1∥w∥(w⊤x+b)yd=\frac{1}{\lVert\boldsymbol{w}\rVert}(\boldsymbol{w}^{\top}\boldsymbol{x}+b)y
  • זהו המרחק של נקודה מהמישור.
  • כאשר yy תואם למיקום הנקודה xx ביחס למישור, הערך חיובי.

פרידות לינארית (linear separability)

  • בבעיות סיווג בינארי, נאמר על המדגם שהוא פריד לינארית אם קיים מסווג לינארי אשר מסווג את המדגם בצורה מושלמת (בלי טעויות סיווג).
  • כאשר המדגם פריד לינארית יהיו יותר ממסווג לינארי אחד אשר יכול לסווג בצורה מושלמת את המדגם.

Support Vector Machine (SVM)

  • אלגוריתם דיסקרימינטיבי לסיווג בינארי אשר מחפש מסווג לינארי אשר יסווג בצורה טובה את המדגם.
  • אלגוריתם זה יבחר את המסווג בעל השוליים המירביות מכל המסווגים שמצליחים לסווג את המדגם.

Hard SVM

  • ניתן לשימוש אך ורק כאשר המדגם פריד לינארית.
  • נחפש את המסווג הלינארי אשר בעבורו ה signed distance המינימאלי על ה train set הוא המקסימאלי:
w∗,b∗=arg⁡max⁡w,bmin⁡i{1∥w∥(w⊤x(i)+b)y(i)}\boldsymbol{w}^*,b^*=\underset{\boldsymbol{w},b}{\arg\max}\quad \underset{i}{\min}\left\{\frac{1}{\lVert\boldsymbol{w}\rVert}(\boldsymbol{w}^{\top}\boldsymbol{x}^{(i)}+b)y^{(i)}\right\}
  • בעיה זו שקולה לבעיית האופטימיזציה הבאה:
w∗,b∗=arg⁡min⁡w,b12∥w∥2s.t.y(i)(w⊤x(i)+b)≥1∀i\begin{aligned} \boldsymbol{w}^*,b^*= \underset{\boldsymbol{w},b}{\arg\min}\quad&\frac{1}{2}\left\lVert\boldsymbol{w}\right\rVert^2 \\ \text{s.t.}\quad&y^{(i)}\left(\boldsymbol{w}^{\top}\boldsymbol{x}^{(i)}+b\right)\geq1\quad\forall i \end{aligned}

בעיית אופטימיזציה זו מכונה הבעיה הפרימאלית.

Margin - שוליים
  • בכדי להבין את המשמעות של בעיית האופטימיזציה שקיבלנו נגדיר את המושג שוליים (margin) של המסווג.
  • האיזור של ה margin מוגדר כאיזור סביב משטח ההפרדה אשר נמצא בתחום:
1≥w⊤x+b≥−11\geq\boldsymbol{w}^{\top}\boldsymbol{x}+b\geq-1

  • רוחב איזור זה נקבע על פי הגודל של הוקטור w\boldsymbol{w} ושווה ל 2∥w∥\frac{2}{\lVert\boldsymbol{w}\rVert}.
  • האילוץ y(i)(w⊤x(i)+b)≥1y^{(i)}\left(\boldsymbol{w}^{\top}\boldsymbol{x}^{(i)}+b\right)\geq1, אשר מופיע בבעיית האופטימיזציה הפרימאלית, דורש למעשה שכל הנקודות יסווגו נכונה וימצאו מחוץ ל margin.
  • בעיית האופטימיזציה מחפשת את הפרמטרים של המישור בעל ה margin הגדול ביותר אשר מקיים תנאי זה.

Support Vectors
  • ה- support vectors מוגדרים כנקודות אשר יושבות על השפה של ה margin, עבור פתרון של בעיית האופטימיזציה.
  • נקודות אלו מקיימות y(i)(w⊤x(i)+b)=1y^{(i)}\left(\boldsymbol{w}^{\top}\boldsymbol{x}^{(i)}+b\right)=1.
  • אלו הנקודות אשר ישפיעו על הפתרון של בעיית האופטימיזציה.
  • לכן, הסרה או הזזה קטנה של נקודות שאינן support vectors לא תשנה את הפתרון.

הבעיה הדואלית
  • דרך שקולה לרישום בעיית האופטימיזציה הינה על ידי הגדרת NN משתני עזר נוספים {αi}i=1N\{\alpha_i\}_{i=1}^N.
  • בעזרת משתנים אלו ניתן לרשום את בעיית האופטימיזציה באופן הבא:
{αi}∗=arg⁡max⁡{αi}∑iαi−12∑i,jy(i)y(j)αiαjx(i)⊤x(j)s.t.αi≥0∀i∑iαiy(i)=0\begin{aligned} \left\lbrace\alpha_i\right\rbrace^* =\underset{\left\lbrace\alpha_i\right\rbrace}{\arg\max}\quad&\sum_i\alpha_i-\frac{1}{2}\sum_{i,j}y^{(i)}y^{(j)}\alpha_i\alpha_j\boldsymbol{x}^{(i)\top}\boldsymbol{x}^{(j)} \\ \text{s.t.}\quad &\alpha_i\geq0\quad\forall i\\ &\sum_i\alpha_iy^{(i)}=0 \end{aligned}

מתוך המשתנים {αi}i=1N\{\alpha_i\}_{i=1}^N ניתן לשחזר את w\boldsymbol{w} אופן הבא:

w=∑iαiy(i)x(i)\boldsymbol{w}=\sum_i\alpha_iy^{(i)}\boldsymbol{x}^{(i)}

קשר בין הבעיה הדואלית והפרימאלית:

. . .
נקודות רחוקות מה margin y(i)(w⊤x(i)+b)>1y^{(i)}\left(\boldsymbol{w}^{\top}x^{(i)}+b\right)>1 αi=0\alpha_i=0
נקודות על ה margin (שהם support vectors) y(i)(w⊤x(i)+b)=1y^{(i)}\left(\boldsymbol{w}^{\top}x^{(i)}+b\right)=1 αi≥0\alpha_i\geq0
  • אם αi>0\alpha_i>0 אז y(i)(w⊤x(i)+b)=1y^{(i)}\left(\boldsymbol{w}^{\top}x^{(i)}+b\right)=1 (אבל לא להיפך)
  • אם y(i)(w⊤x(i)+b)>1y^{(i)}\left(\boldsymbol{w}^{\top}x^{(i)}+b\right)>1 אז αi=0\alpha_i=0 (אבל לא להיפך)
  • את bb נחשב על ידי בחירת SV ונחלץ אותו מתוך y(i)(w⊤x(i)+b)=1y^{(i)}\left(\boldsymbol{w}^{\top}x^{(i)}+b\right)=1.

Soft SVM

  • Soft SVM מתייחס למקרה שבו המדגם אינו פריד לינארית.
  • במקרה זה עדיין מגדירים את ה margin בצורה דומה אך מאפשרים למשתנים להיכנס לתוך ה margin ואף לחצות אותה לצד הלא נכון של מישור ההפרדה.
  • על כל חריגה כזו משלמים קנס ב objective שאותו מנסים למזער.

  • את החריגה של הדגימה ה ii נסמן ב 1∥w∥ξi\frac{1}{\lVert\boldsymbol{w}\rVert}\xi_i. לנקודות שהן בצד הנכון של המישור ומחוץ ל margin יהיה ξi=0\xi_{i}=0

  • המשתנים ξi\xi_i נקראים slack variables.

  • בעיית האופטימיזציה הפרימאלית תהיה:
w∗,b∗,{ξi}∗=arg⁡min⁡w,b,{ξi}12∥w∥2+C∑i=1Nξis.t.y(i)(w⊤x(i)+b)≥1−ξi∀iξi≥0∀i\begin{aligned} \boldsymbol{w}^*,b^*,\{\xi_i\}^*= \underset{\boldsymbol{w},b,\{\xi_i\}}{\arg\min}\quad&\frac{1}{2}\left\lVert\boldsymbol{w}\right\rVert^2+C\sum_{i=1}^N\xi_i \\ \text{s.t.}\quad &y^{(i)}\left(\boldsymbol{w}^{\top}\boldsymbol{x}^{(i)}+b\right)\geq1-\xi_i\quad\forall i\\ &\xi_i\geq0\quad\forall i \end{aligned}
  • CC הוא hyper-parameter שקובע את גודל הקנס על חריגה.
  • הבעיה הדואלית הינה:
{αi}∗=arg⁡max⁡{αi}∑iαi−12∑i,jy(i)y(j)αiαjx(i)⊤x(j)s.t.0≤αi≤C∀i∑iαiy(i)=0\begin{aligned} \left\lbrace\alpha_i\right\rbrace^* =\underset{\left\lbrace\alpha_i\right\rbrace}{\arg\max}\quad&\sum_i\alpha_i-\frac{1}{2}\sum_{i,j}y^{(i)}y^{(j)}\alpha_i\alpha_j\boldsymbol{x}^{(i)\top}\boldsymbol{x}^{(j)} \\ \text{s.t.}\quad &0\leq\alpha_i\leq C\quad\forall i\\ &\sum_i\alpha_iy^{(i)}=0 \end{aligned}

  • ה support vectors מוגדרים להיות הנקודות שמקיימות y(i)(w⊤x(i)+b)=1−ξiy^{(i)}\left(\boldsymbol{w}^{\top}\boldsymbol{x}^{(i)}+b\right)=1-\xi_i

תכונות:

. . .
נקודות שמסווגות נכון ורחוקות מה margin y(i)(w⊤x(i)+b)>1y^{(i)}\left(\boldsymbol{w}^{\top}x^{(i)}+b\right)>1 αi=0\alpha_i=0
נקודות על ה margin (שהם support vectors) y(i)(w⊤x(i)+b)=1y^{(i)}\left(\boldsymbol{w}^{\top}x^{(i)}+b\right)=1 0≤αi≤C0\leq\alpha_i\leq C
נקודות שחורגות מה margin (גם support vectors) y(i)(w⊤x(i)+b)=1−ξiy^{(i)}\left(\boldsymbol{w}^{\top}x^{(i)}+b\right)=1-\xi_i αi=C\alpha_i=C

פונקציות גרעין

מאפיינים: תזכורת

  • נוכל תמיד לחליף את וקטור המשתנים x\boldsymbol{x} שעליו פועל האלגוריתם בוקטור חדש xnew=Φ(x)\boldsymbol{x}_{\text{new}}=\Phi(\boldsymbol{x}).
  • Φ\Phi היא פונקציה אשר נבחרה מראש ונקראת פונקציית המאפיינים.

פונקציות גרעין

  • החישוב של Φ(x)\Phi(\boldsymbol{x}) יכול להיות יקר.

  • לעיתים, קיימת דרך לחשב בצורה יעילה את הפונקציה K(x1,x2)=Φ(x1)⊤Φ(x2)K(\boldsymbol{x}_1,\boldsymbol{x}_2)=\Phi(\boldsymbol{x}_1)^{\top}\Phi(\boldsymbol{x}_2) אשר נקראת פונקציית גרעין

    • ישנם אפילו מקרים שבהם וקטור המאפיינים אינסופי!
  • ישנם קריטריונים תחתם פונקציה מסויימת K(x1,x2)K(\boldsymbol{x}_1,\boldsymbol{x}_2) היא פונקציית גרעין בעבור וקטור מאפיינים מסויים. בקורס לא נכנס לכך.

נציג שתי פונקציות גרעין נפוצות:

  • גרעין גאוסי:
  • K(x1,x2)=exp⁡(−∥x1−x2∥222σ2)K(\boldsymbol{x}_1,\boldsymbol{x}_2)=\exp\left(-\frac{\lVert\boldsymbol{x}_1-\boldsymbol{x}_2\rVert_2^2}{2\sigma^2}\right)
  • כאשר σ\sigma פרמטר שיש לקבוע.

  • גרעין פולינומיאלי: K(x1,x2)=(1+x1⊤x2)pK(\boldsymbol{x}_1,\boldsymbol{x}_2)=(1+\boldsymbol{x}_1^{\top}\boldsymbol{x}_2)^p

    • כאשר p≥1p\geq1 פרמטר שיש לקבוע.

פונקציית המאפיינים שמתאימות לגרעינים אלו מסורבלות לכתיבה ולא נציג אותן כאן.

Kernel Trick in SVM

  • טריק זה מאפשר להשתמש ב SVM עם מאפיינים מבלי לחשב את Φ\Phi באופן ישיר באמצעות פונקציית גרעין.
  • עבור פונקציית מאפיינים Φ\Phi עם פונקציית גרעין KK הבעיה הדואלית של SVM הינה:
{αi}∗=arg⁡max⁡{αi}∑iαi−12∑i,jy(i)y(j)αiαjK(x(i),x(j))s.t.αi≥0∀i∑iαiy(i)=0\begin{aligned} \left\lbrace\alpha_i\right\rbrace^* =\underset{\left\lbrace\alpha_i\right\rbrace}{\arg\max}\quad&\sum_i\alpha_i-\frac{1}{2}\sum_{i,j}y^{(i)}y^{(j)}\alpha_i\alpha_jK(\boldsymbol{x}^{(i)},\boldsymbol{x}^{(j)}) \\ \text{s.t.}\quad &\alpha_i\geq0\quad\forall i\\ &\sum_i\alpha_iy^{(i)}=0 \end{aligned}
  • בעיית זו מגדירה את המשתנים {αi}\{\alpha_i\} בלי צורך לחשב את Φ\Phi באופן מפורש בשום שלב.

Kernel Trick in SVM

  • הפרמטר w\boldsymbol{w} נתון על ידי:
w=∑iαiy(i)Φ(x(i))\boldsymbol{w}=\sum_i\alpha_iy^{(i)}\Phi(\boldsymbol{x}^{(i)})
  • כדי לחשב את w\boldsymbol{w} באופן מפורש יש לחשב את Φ\Phi.
  • עם זאת, ניתן להמנע מכך

Kernel Trick in SVM

  • נציב את הנוסחא של w\boldsymbol{w} ישירות למסווג ובכך נוכל להינמע מלחשב את Φ\Phi:
h(x)=sign(w⊤Φ(x)+b)=sign(∑iαiy(i)Φ(x(i))⊤Φ(x)+b)=sign(∑iαiy(i)K(x(i),x)+b)\begin{aligned} h(\boldsymbol{x}) &=\text{sign}(\boldsymbol{w}^{\top}\Phi(\boldsymbol{x})+b)\\ &=\text{sign}(\sum_i\alpha_iy^{(i)}\Phi(\boldsymbol{x}^{(i)})^{\top}\Phi(\boldsymbol{x})+b)\\ &=\text{sign}(\sum_i\alpha_iy^{(i)}K(\boldsymbol{x}^{(i)},\boldsymbol{x})+b)\\ \end{aligned}
  • כך בעצם נוכל להשתמש במסווג מבלי לחשב את Φ\Phi מפורשות

תרגיל 6.1 - 2 Support Vectors

בשאלה זו נראה שבעבור מדגם המכיל 2 נקודות, אחת מכל מחלקה, הפתרון של בעיית hard SVM יהיה מישור הפרדה שיעבור בדיוק במרכז בין 2 הנקודות, ויהיה ניצב לוקטור המחבר את הנקודות

w=2∥x(1)−x(2)∥22(x(1)−x(2)),b=−12(x(1)+x(2))⊤w\boldsymbol{w}=\frac{2}{\lVert\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)}\rVert_2^2}\left(\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)}\right), \quad b=-\frac{1}{2}\left(\boldsymbol{x}^{(1)}+\boldsymbol{x}^{(2)}\right)^{\top}\boldsymbol{w}

1) הראו זאת על ידי פתרון הבעיה הדואלית.

פתרון:

הבעיה הדואלית הינה:

{αi}∗=arg⁡max⁡{αi}∑iαi−12∑i,jy(i)y(j)αiαjx(i)⊤x(j)s.t.αi≥0∀i∑iαiy(i)=0\begin{aligned} \left\lbrace\alpha_i\right\rbrace^* =\underset{\left\lbrace\alpha_i\right\rbrace}{\arg\max}\quad&\sum_i\alpha_i-\frac{1}{2}\sum_{i,j}y^{(i)}y^{(j)}\alpha_i\alpha_j\boldsymbol{x}^{(i)\top}\boldsymbol{x}^{(j)} \\ \text{s.t.}\quad &\alpha_i\geq0\quad\forall i\\ &\sum_i\alpha_iy^{(i)}=0 \end{aligned}
  • נניח בלי הגבלת הכלליות ש y(1)=1y^{(1)}=1 ו y(2)=−1y^{(2)}=-1.

נסתכל על האילוץ בשורה האחרונה:

∑i=12αiy(i)=0⇔α1−α2=0⇔α1=α2=α\begin{aligned} \sum_{i=1}^2\alpha_i y^{(i)}=0\\ \Leftrightarrow\alpha_1-\alpha_2=0\\ \Leftrightarrow\alpha_1=\alpha_2=\alpha \end{aligned}
  • מכאן שהמשתנה היחד בבעיה הינו α\alpha.
  • בעיית האופטימיזציה (ללא האילוצים) תהיה:
α=arg⁡max⁡α2α−α22∑i,jy(i)y(j)x(i)⊤x(j)s.t.α≥0=arg⁡max⁡α2α−α22(∥x(1)∥22−x(1)⊤x(2)−x(2)⊤x(1)+∥x(2)∥22)s.t.α≥0=arg⁡max⁡α2α−α22∥x(1)−x(2)∥22s.t.α≥0\begin{aligned} \alpha =\underset{\alpha}{\arg\max}\quad&2\alpha-\frac{\alpha^2}{2}\sum_{i,j}y^{(i)}y^{(j)}\boldsymbol{x}^{(i)\top}\boldsymbol{x}^{(j)} \\ \text{s.t.}\quad &\alpha\geq0\\ =\underset{\alpha}{\arg\max}\quad&2\alpha-\frac{\alpha^2}{2}\left( \lVert\boldsymbol{x}^{(1)}\rVert_2^2 -\boldsymbol{x}^{(1)\top}\boldsymbol{x}^{(2)} -\boldsymbol{x}^{(2)\top}\boldsymbol{x}^{(1)} +\lVert\boldsymbol{x}^{(2)}\rVert_2^2 \right)\\ \text{s.t.}\quad &\alpha\geq0\\ =\underset{\alpha}{\arg\max}\quad&2\alpha-\frac{\alpha^2}{2}\lVert\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)}\rVert_2^2\\ \text{s.t.}\quad &\alpha\geq0\\ \end{aligned}

ניתן לפתור את הבעיה על ידי גזירה והשוואה ל0:

ddα2α−α22∥x(1)−x(2)∥22=0⇔2=α∥x(1)−x(2)∥22⇔α=2∥x(1)−x(2)∥22\begin{aligned} &\frac{d}{d\alpha}2\alpha-\frac{\alpha^2}{2}\lVert\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)}\rVert_2^2=0\\ \Leftrightarrow&2=\alpha\lVert\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)}\rVert_2^2\\ \Leftrightarrow&\alpha=\frac{2}{\lVert\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)}\rVert_2^2}\\ \end{aligned}

את w\boldsymbol{w} נמצא על ידי:

w=∑iαiy(i)x(i)=α(x(1)−x(2))=2∥x(1)−x(2)∥22(x(1)−x(2))\boldsymbol{w} =\sum_i\alpha_iy^{(i)}\boldsymbol{x}^{(i)} =\alpha(\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)}) =\frac{2}{\lVert\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)}\rVert_2^2}\left(\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)}\right)

את bb מוצאים על ידי בחירת support vector אחד מתוך המשוואה y(i)(w⊤x(i)+b)=1y^{(i)}\left(\boldsymbol{w}^{\top}\boldsymbol{x}^{(i)}+b\right)=1.

  • נסתכל על הנקודה הראשונה:
y(1)(w⊤x(1)+b)=1⇔w⊤x(1)+b=1⇔b=1−w⊤x(1)=w⊤w∥w∥22−w⊤x(1)=w⊤(w∥w∥22−x(1))⇔b=w⊤(12(x(1)−x(2))−x(1))⇔b=−12(x(1)+x(2))⊤w\begin{aligned} &y^{(1)}\left(\boldsymbol{w}^{\top}\boldsymbol{x}^{(1)}+b\right)=1\\ \Leftrightarrow&\boldsymbol{w}^{\top}\boldsymbol{x}^{(1)}+b=1\\ \Leftrightarrow&b=1-\boldsymbol{w}^{\top}\boldsymbol{x}^{(1)} =\frac{\boldsymbol{w}^{\top}\boldsymbol{w}}{\lVert\boldsymbol{w}\rVert_2^2}-\boldsymbol{w}^{\top}\boldsymbol{x}^{(1)} =\boldsymbol{w}^{\top}\left(\frac{\boldsymbol{w}}{\lVert\boldsymbol{w}\rVert_2^2}-\boldsymbol{x}^{(1)}\right)\\ \Leftrightarrow&b=\boldsymbol{w}^{\top}\left(\frac{1}{2}\left(\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)}\right)-\boldsymbol{x}^{(1)}\right)\\ \Leftrightarrow&b=-\frac{1}{2}\left(\boldsymbol{x}^{(1)}+\boldsymbol{x}^{(2)}\right)^{\top}\boldsymbol{w} \end{aligned}

2) הראו זאת על ידי פתרון הבעיה הפרימאלית.

הבעיה הפרימלית הינה:

w∗,b∗=arg⁡min⁡w,b12∥w∥2s.t.y(i)(w⊤x(i)+b)≥1∀i\begin{aligned} \boldsymbol{w}^*,b^*= \underset{\boldsymbol{w},b}{\arg\min}\quad&\frac{1}{2}\left\lVert\boldsymbol{w}\right\rVert^2 \\ \text{s.t.}\quad&y^{(i)}\left(\boldsymbol{w}^{\top}\boldsymbol{x}^{(i)}+b\right)\geq1\quad\forall i \end{aligned}
  • במקרה שבו יש רק נקודה אחת מכל מחלקה, שתי הנקודות בהכרח יהיו support vectors ויקיימו y(i)(w⊤x(i)+b)=1y^{(i)}\left(\boldsymbol{w}^{\top}\boldsymbol{x}^{(i)}+b\right)=1.
  • נניח בלי הגבלת הכלליות ש y(1)=1y^{(1)}=1 ו y(2)=−1y^{(2)}=-1.

שני האילוצים שהנקודות אלו מגדירות הם:

{y(1)(w⊤x(1)+b)=1y(2)(w⊤x(2)+b)=1⇔{(w⊤x(1)+b)=1−(w⊤x(2)+b)=1⇔{w⊤x(1)+b=1w⊤x(2)+b=−1⇔{b=−12(x(1)+x(2))⊤ww⊤(x(1)−x(2))=2\begin{aligned} &\begin{cases} y^{(1)}\left(\boldsymbol{w}^{\top}\boldsymbol{x}^{(1)}+b\right)=1\\ y^{(2)}\left(\boldsymbol{w}^{\top}\boldsymbol{x}^{(2)}+b\right)=1 \end{cases}\\ \Leftrightarrow&\begin{cases} \left(\boldsymbol{w}^{\top}\boldsymbol{x}^{(1)}+b\right)=1\\ -\left(\boldsymbol{w}^{\top}\boldsymbol{x}^{(2)}+b\right)=1 \end{cases}\\ \Leftrightarrow&\begin{cases} \boldsymbol{w}^{\top}\boldsymbol{x}^{(1)}+b=1\\ \boldsymbol{w}^{\top}\boldsymbol{x}^{(2)}+b=-1 \end{cases}\\ \Leftrightarrow&\begin{cases} b=-\frac{1}{2}\left(\boldsymbol{x}^{(1)}+\boldsymbol{x}^{(2)}\right)^{\top}\boldsymbol{w}\\ \boldsymbol{w}^{\top}(\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)})=2 \end{cases}\\ \end{aligned}

נוכל להשתמש באילוץ השני ולכתוב בעזרתו את בעיית האופטימיזציה רק על w\boldsymbol{w}:

w∗=arg⁡min⁡w12∥w∥2s.t.w⊤(x(1)−x(2))=2\begin{aligned} \boldsymbol{w}^*= \underset{\boldsymbol{w}}{\arg\min}\quad&\frac{1}{2}\left\lVert\boldsymbol{w}\right\rVert^2 \\ \text{s.t.}\quad&\boldsymbol{w}^{\top}(\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)})=2 \end{aligned}
  • בעיה זו מחפשת את ה w\boldsymbol{w} בעל האורך המינימאלי כך שהמכפלה הסקלרית שלו עם (x(1)−x(2))(\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)}) היא 2. הוקטור הזה יהיה וקטור בכיוון של (x(1)−x(2))(\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)}) ובאורך של 2/∥x(1)−x(2)∥22/\lVert\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)}\rVert_2
  • מכאן:
w=2∥x(1)−x(2)∥22(x(1)−x(2))\boldsymbol{w} =\frac{2}{\lVert\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)}\rVert_2^2}\left(\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)}\right)

תרגיל 6.2 - Hard SVM

נתון המדגם הבא:

. 1 2 3 4 5 6
y\text{y} -1 -1 -1 1 1 1
x1\text{x}_1 1 1 4 6 7 10
x2\text{x}_2 6 10 11 1 6 4

1) מצא את מסווג ה hard SVM המתאים למדגם זה. מי הם וקטורי התמיכה?

  • בעיית האופטימיזציה הפרימאלית אותה נרצה לפתור הינה:
w∗,b∗=arg⁡min⁡w,b12∥w∥2s.t.y(i)(w⊤x(i)+b)≥1∀i\begin{aligned} \boldsymbol{w}^*,b^*= \underset{\boldsymbol{w},b}{\arg\min}\quad&\frac{1}{2}\left\lVert\boldsymbol{w}\right\rVert^2 \\ \text{s.t.}\quad&y^{(i)}\left(\boldsymbol{w}^{\top}\boldsymbol{x}^{(i)}+b\right)\geq1\quad\forall i \end{aligned}

  • באופן כללי פתרון בעיות מסוג זה באופן ידני הוא קשה, אך בעבור מקרים פשוטים נוכל לפתור זאת תוך שימוש בעיקרון הבא:

    • במידה ומצאנו את הפיתרון האופטימאלי על תת מדגם מתוך המדגם המלא, ומתקיים שבעבור הפתרון שמצאנו, הנקודות שאינן חלק מתת המדגם נמצאות מחוץ ל margin, אז הפתרון הוא בהכרח הפתרון האופטימאלי בעבור המדגם כולו.
  • עקרון זה נכון בגלל העובדה שהוספה של אילוצים לבעיית מינימיזציה יכולה רק להגדיל את ה objective המינימאלי.
  • המשמעות היא שניתן לנחש את ה support vectors ולפתור את הבעיה רק בעבור נקודות אלו תוך התעלמות משאר הנקודות.
  • לאחר שנפתור את הבעיה על הנקודות שניחשנו יהיה עלינו לבדוק אם שאר נקודות במדגם מחוץ ל margin.
  • אם אכן שאר הנקודות מחוץ ל margin אז פתרנו את הבעיה ואם לא אז עלינו לנחש נקודות אחרות.
  • בעבור ה support vectors האילוצים של y(i)(w⊤x(i)+b)≥1y^{(i)}\left(\boldsymbol{w}^{\top}\boldsymbol{x}^{(i)}+b\right)\geq1 הופכים להיות אילוצי שיוון שאיתם הרבה יותר קל לעבוד.

ננסה לנחש מהם ה support vectors. נתחיל ב 0 ונגדיל בהדרגה את כמות ה support vectors.

0 or 1 Support Vectors
  • באופן כללי בעבור מדגם "נורמלי" אשר מכיל נקודות משני המחלקות שאותן יש לסווג, מקרים אלו לא יוכלו להתקיים.
  • באופן תיאורטי במקרה המנוון שבו המדגם מכיל רק תוויות מסוג אחד אז ניתן להגדיר בצורות שונות את כמות ה support vectors, אך מקרים אלו לא מאד רלוונטיים

2 Support Vectors
  • על פי התרגיל הקודם בעבור שני support vectors שמישור ההפרדה יעבור בדיוק במרכז בין 2 הנקודות, יהיה ניצב לוקטור המחבר את שתי הנקודות והשוליים של ה- margin יעברו דרך הנקודות.
  • ננסה לחפש 2 נקודות שיכולות להיות support vectors.

  • נראה שכל בחירה של זוג נקודות יצור איזור של margin שמכיל נקודה אחרת ולכן לא מקיים את האילוצים.
  • לכן הפתרון לא יכול להכיל רק שני support vectors.

3 Support Vectors

ישנן שתי שלשות שיתכן שיהיו ה support vectors של הפתרון:

  • {1,3,5}\{1,3,5\}
  • {3,4,5}\{3,4,5\}
  • נסתכל ראשית על תת המדגם {3,4,5}\{3,4,5\}.

  • נשים לב שכאן הפתרון עבור תת המדגם {3,5}\{3,5\} מקיים את האילוץ שגם נקודה 4 מסווגת נכון.
  • אולם ראינו שפתרון כזה אינו מקיים את שאר האילוצים!

  • השלשה {1,3,5}\{1,3,5\} מגדירה איזור margin שאינו מכיל נקודות אחרות ולכן מקיים את האילוצים:

  • נקודות אלו יהיו שלושת ה support vectors שיגדיר את הפתרון לבעיה. נחשב את הפתרון המתקבל משלושת הנקודות האלה.

מתוך האילוצים נקבל 3 משוואות ב3 נעלמים. בעבור הנקודות {1,3,5}\{1,3,5\} משוואות אלו יהיו:

{−((1,6)w+b)=1−((4,11)w+b)=1((7,6)w+b)=1⇔{w1+6w2+b=−14w1+11w2+b=−17w1+6w2+b=1\begin{aligned} \begin{cases} -\left((1,6)\boldsymbol{w}+b\right)=1\\ -\left((4,11)\boldsymbol{w}+b\right)=1\\ \left((7,6)\boldsymbol{w}+b\right)=1 \end{cases}\\ \Leftrightarrow\begin{cases} w_1+6w_2+b=-1\\ 4w_1+11w_2+b=-1\\ 7w_1+6w_2+b=1 \end{cases} \end{aligned}

הפתרון של מערכת המשוואות הזו הינה w=115(5,−3)⊤\boldsymbol{w}=\frac{1}{15}(5,-3)^{\top} ו b=−215b=-\frac{2}{15}

2) מבלי לפתור את הבעיה הדואלית. אלו ערכים של {αi}\{\alpha_i\} בהכרח יתאפסו?

  • בעבור נקודות שאינן support vectors, נקבל ש-αi\alpha_{i} בהכרח יתאפס
  • בבעיה זו הנקודות שאינן support vectors הן {2,4,6}\{2,4,6\} ולכן α2=α4=α6=0\alpha_2=\alpha_4=\alpha_6=0.

3) מהו הרוחב של ה margin של הפתרון?

ה margin תלוי בגודל של הוקטור w\boldsymbol{w} והוא שווה ל:

2∥w∥=2⋅1552+32=5.145\frac{2}{\lVert\boldsymbol{w}\rVert}=\frac{2\cdot15}{\sqrt{5^2+3^2}}=5.145

תרגיל 6.3 - גרעין גאוסי

נתון מדגם המכיל 2 נקודות אחת מכל מחלקה:

x(1)=(1,1)⊤,y(1)=+1x(2)=(−1,−1)⊤,y(2)=−1\begin{aligned} &x^{(1)}=(1,1)^{\top},\quad & y^{(1)}=+1 \\ &x^{(2)}=(-1,-1)^{\top},\quad &y^{(2)}=-1 \\ \end{aligned}

חשבו את המסווג המתקבל מ hard SVM עם גרעין גאוסי מהצורה K(x1,x2)=exp⁡(−∥x1−x2∥2)K(\boldsymbol{x}_1,\boldsymbol{x}_2)=\exp\left(-\lVert\boldsymbol{x}_1-\boldsymbol{x}_2\rVert^2\right).

פתרון 6.3

הבעיה הדואלית עם הגרעין הגאוסי הינה:

{αi}∗=arg⁡max⁡{αi}∑iαi−12∑i,jy(i)y(j)αiαjK(x(i),x(j))s.t.αi≥0∀i∑iαiy(i)=0\begin{aligned} \left\lbrace\alpha_i\right\rbrace^* =\underset{\left\lbrace\alpha_i\right\rbrace}{\arg\max}\quad&\sum_i\alpha_i-\frac{1}{2}\sum_{i,j}y^{(i)}y^{(j)}\alpha_i\alpha_jK(\boldsymbol{x}^{(i)},\boldsymbol{x}^{(j)})\\ \text{s.t.}\quad &\alpha_i\geq0\quad\forall i\\ &\sum_i\alpha_iy^{(i)}=0 \end{aligned}

בדומה לתרגיל הראשון נקבל ש:

α1=α2=α\alpha_1=\alpha_2=\alpha

נחשב את הערכים של K(x(i),x(j))K(\boldsymbol{x}^{(i)},\boldsymbol{x}^{(j)}):

K(x(1),x(1))=exp⁡(0)=1K(x(2),x(2))=exp⁡(0)=1K(x(1),x(2))=exp⁡(−(22+22))=e−8\begin{aligned} K(\boldsymbol{x}^{(1)},\boldsymbol{x}^{(1)})=\exp(0)=1\\ K(\boldsymbol{x}^{(2)},\boldsymbol{x}^{(2)})=\exp(0)=1\\ K(\boldsymbol{x}^{(1)},\boldsymbol{x}^{(2)})=\exp(-(2^2+2^2))=e^{-8} \end{aligned}

בעיית האופטימיזציה הינה:

α∗=arg⁡max⁡α2α−α22(K(x(1),x(1))−2K(x(1),x(2))+K(x(2),x(2)))s.t.α≥0=arg⁡max⁡α2α−α2(1−e−8)s.t.α≥0\begin{aligned} \alpha^* =\underset{\alpha}{\arg\max}\quad&2\alpha-\frac{\alpha^2}{2}\left( K(\boldsymbol{x}^{(1)},\boldsymbol{x}^{(1)}) -2K(\boldsymbol{x}^{(1)},\boldsymbol{x}^{(2)}) +K(\boldsymbol{x}^{(2)},\boldsymbol{x}^{(2)}) \right)\\ \text{s.t.}\quad &\alpha\geq0\\ =\underset{\alpha}{\arg\max}\quad&2\alpha-\alpha^2(1-e^{-8})\\ \text{s.t.}\quad &\alpha\geq0\\ \end{aligned}

נגזור ונשווה ל-0:

ddα2α−α2(1−e−8)=0⇔1=α(1−e−8)⇔α=21−e−8\begin{aligned} &\frac{d}{d\alpha}2\alpha-\alpha^2(1-e^{-8})=0\\ \Leftrightarrow&1=\alpha(1-e^{-8})\\ \Leftrightarrow&\alpha=\frac{2}{1-e^{-8}} \end{aligned}

הוקטור w\boldsymbol{w} נתון על ידי: w=∑iαiy(i)Φ(x(i))\boldsymbol{w}=\sum_i\alpha_iy^{(i)}\Phi(\boldsymbol{x}^{(i)}). נכתוב את הביטוי w⊤Φ(x)\boldsymbol{w}^{\top}\Phi(\boldsymbol{x}) בעבור נקודה כל שהיא x\boldsymbol{x}:

w⊤Φ(x)=∑iαiy(i)Φ(x(i))⊤Φ(x)=∑iαiy(i)K(x(i),x)=11−e−8(K(x(1),x)−K(x(2),x))\begin{aligned} \boldsymbol{w}^{\top}\Phi(\boldsymbol{x}) &=\sum_i\alpha_iy^{(i)}\Phi(\boldsymbol{x}^{(i)})^{\top}\Phi(\boldsymbol{x})\\ &=\sum_i\alpha_iy^{(i)}K(\boldsymbol{x}^{(i)},\boldsymbol{x})\\ &=\frac{1}{1-e^{-8}}\left(K(\boldsymbol{x}^{(1)},\boldsymbol{x})-K(\boldsymbol{x}^{(2)},\boldsymbol{x})\right) \end{aligned}

נחשב את bb על ידי שימוש בנקודה הראשונה:

1=y(1)(w⊤Φ(x(1))+b)⇔b=1−w⊤Φ(x(1))⇔b=1−11−e−8(K(x(1),x(1))−K(x(2),x(1)))⇔b=1−11−e−8(1−e−8)=0\begin{aligned} 1&=y^{(1)}\left(\boldsymbol{w}^{\top}\Phi(\boldsymbol{x}^{(1)})+b\right)\\ \Leftrightarrow b&=1-\boldsymbol{w}^{\top}\Phi(\boldsymbol{x}^{(1)})\\ \Leftrightarrow b&=1-\frac{1}{1-e^{-8}}\left(K(\boldsymbol{x}^{(1)},\boldsymbol{x}^{(1)})-K(\boldsymbol{x}^{(2)},\boldsymbol{x}^{(1)})\right)\\ \Leftrightarrow b&=1-\frac{1}{1-e^{-8}}\left(1-e^{-8}\right)=0 \end{aligned}

המסווג הינו:

h(x)=sign(w⊤Φ(x)+b)=sign(11−e−8(K(x(1),x)−K(x(2),x)))=sign(K(x(1),x)−K(x(2),x))=sign(exp⁡(−∥x(1)−x∥2)−exp⁡(−∥x(2)−x∥2))=sign(∥x(2)−x∥2−∥x(1)−x∥2)=sign((x1+1)2+(x2+1)2−(x1−1)2−(x2−1)2)=sign(2x1+2x2)=sign(x1+x2)\begin{aligned} h(\boldsymbol{x}) &=\text{sign}(\boldsymbol{w}^{\top}\Phi(\boldsymbol{x})+b)\\ &=\text{sign}\left(\frac{1}{1-e^{-8}}\left(K(\boldsymbol{x}^{(1)},\boldsymbol{x})-K(\boldsymbol{x}^{(2)},\boldsymbol{x})\right)\right)\\ &=\text{sign}\left(K(\boldsymbol{x}^{(1)},\boldsymbol{x})-K(\boldsymbol{x}^{(2)},\boldsymbol{x})\right)\\ &=\text{sign}\left( \exp\left(-\lVert\boldsymbol{x}^{(1)}-\boldsymbol{x}\rVert^2\right) -\exp\left(-\lVert\boldsymbol{x}^{(2)}-\boldsymbol{x}\rVert^2\right) \right)\\ &=\text{sign}\left( \lVert\boldsymbol{x}^{(2)}-\boldsymbol{x}\rVert^2 -\lVert\boldsymbol{x}^{(1)}-\boldsymbol{x}\rVert^2 \right)\\ &=\text{sign}\left((x_1+1)^2+(x_2+1)^2-(x_1-1)^2-(x_2-1)^2\right)\\ &=\text{sign}\left(2x_1+2x_2\right)\\ &=\text{sign}\left(x_1+x_2\right)\\ \end{aligned}

חלק מעשי: זיהוי מין הדובר

בחלק זה, ננסה להשתמש ב- SVM כדי לזהות את מינו של הדובר באמצעות קולו. מוטיבציה למערכת כזאת יכולה להיות עוזר וירטואלי שרוצה לפנות לדובר לפי מינו. הרחבה לניסיון זה יכולה להיות זיהוי דובר על סמך קולו וכו'.

הרעיון וה- DATA נלקחו מ- Dataset והערכת ביצועים של קורי בקר, אשר נמצאים באתר הבא. בפרוייקט זה נאספו 3168 דגימות קול מתוייגות מהמקורות הבאים:

כל רצועת קול עברה עיבוד באמצעות כלי בשם WarbleR בכדי לייצר 20 Features לכל דגימה:

  • label: The label of each track: male/female
  • meanfreq: mean frequency (in kHz)
  • sd: standard deviation of frequency
  • median: median frequency (in kHz)
  • Q25: first quantile (in kHz)
  • Q75: third quantile (in kHz)
  • IQR: interquantile range (in kHz)
  • skew: skewness (see note in specprop description)
  • kurt: kurtosis (see note in specprop description)
  • sp.ent: spectral entropy
  • sfm: spectral flatness
  • mode: mode frequency
  • centroid: frequency centroid (see specprop)
  • meanfun: average of fundamental frequency measured across acoustic signal
  • minfun: minimum fundamental frequency measured across acoustic signal
  • maxfun: maximum fundamental frequency measured across acoustic signal
  • meandom: average of dominant frequency measured across acoustic signal
  • mindom: minimum of dominant frequency measured across acoustic signal
  • maxdom: maximum of dominant frequency measured across acoustic signal
  • dfrange: range of dominant frequency measured across acoustic signal
  • modindx: modulation index. Calculated as the accumulated absolute difference between

נציג מספר עמודות ושורות מן המדגם:

label meanfreq sd median Q25 Q75 IQR skew kurt
0 male 0.059781 0.0642413 0.0320269 0.0150715 0.0901934 0.075122 12.8635 274.403
1 male 0.0660087 0.06731 0.0402287 0.0194139 0.0926662 0.0732523 22.4233 634.614
2 male 0.0773155 0.0838294 0.0367185 0.00870106 0.131908 0.123207 30.7572 1024.93
3 male 0.151228 0.0721106 0.158011 0.0965817 0.207955 0.111374 1.23283 4.1773
4 male 0.13512 0.0791461 0.124656 0.0787202 0.206045 0.127325 1.10117 4.33371
5 male 0.132786 0.0795569 0.11909 0.067958 0.209592 0.141634 1.93256 8.3089
6 male 0.150762 0.0744632 0.160106 0.0928989 0.205718 0.112819 1.53064 5.9875
7 male 0.160514 0.0767669 0.144337 0.110532 0.231962 0.12143 1.39716 4.76661
8 male 0.142239 0.0780185 0.138587 0.0882063 0.208587 0.120381 1.09975 4.07028
9 male 0.134329 0.08035 0.121451 0.07558 0.201957 0.126377 1.19037 4.78731

הפילוג של התוויות (גברים נשים) במדגם הינו:

נציג את ההיסטוגרמה של כל אחד מהמאפיינים בעבור כל אחד מתוויות:

Soft SVM

ננסה לפתור את בעיית הסיווג של מין הדובר בעזרת soft SVM. נרצה לשם כך לפתור את בעיית האופטימיזציה הבאה (הבעיה הדואלית):

{αi}∗=arg⁡max⁡{αi}∑iαi−12∑i,jy(i)y(j)αiαjx(i)⊤x(j)s.t.0≤αi≤C∀i∑iαiy(i)=0\begin{aligned} \left\lbrace\alpha_i\right\rbrace^* =\underset{\left\lbrace\alpha_i\right\rbrace}{\arg\max}\quad&\sum_i\alpha_i-\frac{1}{2}\sum_{i,j}y^{(i)}y^{(j)}\alpha_i\alpha_j\boldsymbol{x}^{(i)\top}\boldsymbol{x}^{(j)} \\ \text{s.t.}\quad &0\leq\alpha_i\leq C\quad\forall i\\ &\sum_i\alpha_iy^{(i)}=0 \end{aligned}

  • נמצא את w\boldsymbol{w} בעזרת:
w=∑iαiyixi\boldsymbol{w}=\sum_i\alpha_iy_i\boldsymbol{x}_i
  • ניתן לחשב את bb על ידי בחירה של נקודה שעבורה 0<αi0<\alpha_i ולהשתמש במשוואה: yi(wTxi+b)=1−ξiy_i\left(\boldsymbol{w}^T\boldsymbol{x}_i+b\right)=1-\xi_i.
  • בכדי לפתור את הבעיה נצטרך לבחור פרמטר משקל CC אשר קובע את גודל הקנס לנקודות שחורגות מה margin. נתחיל ב C=1C=1 ואחר כך ננסה למצוא את הערך המיטבי.

חלוקת המדגם

כרגיל נחלק את המדגם ל 60%-20%-20% שהם train-validation-test.

נרמול

חשוב לנרמל את העמודות של המדגם לפני הרצת האלגוריתם משתי סיבות עיקריות:

  1. המדגם מכיל מאפיינים ביחידות וסקלות שונות.
  2. האלגוריתם מנסה למזער objective אשר מבוסס מרחק, מה שהופך אותו לרגיש לגודל של כל מאפיין. לדוגמא, אם נכפיל מאפיין מסויים בקבוע גדול מ-1 אנו ניתן לו חשיבות יתרה ב objective.

תוצאות

נשתמש באופטימיזציה נומרית על מנת למצוא את הפרמטרים של משטח ההפרדה. לשם המחשה נשרטט את הפילוג של ה signed distance של הנקודות בכל אחת מהמחלקות

ניתן לראות כי המשטח באמת מצליח לחלק את המדגם, עד כדי כמה נקודות שחורגות.

ה miscalssification rate שמתקבל על ה test set הינו 0.028.

מציאת ה CC האופטימאלי

נבחן סדרה של ערכי CC בתחום 10−310^{-3} עד 10310^3. כרגיל, בעבור כל ערך נבנה מסווג ונבחן אותו על ה validation set. נקבל את התוצאה הבאה:

קיבלנו כי הערך שאיתו התחלנו של C=1C=1 הוא האופטימאלי מבין הערכים שבחרנו.