מכונת וקטורים תומכים

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

מכונת וקטורים תומכים (באנגלית Support Vector Machine, לרוב נכתב ונהגה כראשי-תבות SVM) היא טכניקה של למידה מונחית (supervised learning) המשמשת לניתוח נתונים דרך סיווג. האלגוריתם משמש לסיווג נתונים בין שתי קטגוריות: חיובי ושלילי / שייכות לקבוצה או אי-שייכות. כנהוג בתחום זה, דוגמאות האימון מיוצגות כווקטורים במרחב לינארי. אך ניתן לדמיין את פעולת האלגוריתם כמעין סיווג של נקודות בחלל לשתי קבוצות, כך שנוצר קו הפרדה בין הנקודות. שלב האימון תכליתו בניית מסווג (classifier) אשר מפריד נכון ככל האפשר בין דוגמאות אימון חיוביות ושליליות. המסווג שנוצר ב SVM הוא המפריד הלינארי אשר יוצר מרווח גדול ככל האפשר בינו לבין הדוגמאות הקרובות לו ביותר בשתי הקטגוריות. כאשר מוצגת נקודה חדשה, האלגוריתם יזהה האם היא ממוקמת בתוך הקו המגדיר את הקבוצה, או מחוצה לו.

רציונל[עריכת קוד מקור | עריכה]

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

היסטוריה[עריכת קוד מקור | עריכה]

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

מוטיבציה[עריכת קוד מקור | עריכה]

סיווג מידע היא פעולה נפוצה בלמידת מכונה (Machine Learning). בהינתן אוסף נתונים אשר צריך להפריד אותם לשתי קבוצות על סמך ניסיון קודם (דוגמאות - האם אימייל הוא ספאם או לא; האם מוטצית גן מסוימת מסרטנת או לא) כאשר המטרה היא להחליט לאיזו משתי הקבוצות לשייך נקודה חדשה. כל נקודה באוסף הנתונים מיוצגת על ידי וקטור בגודל מסוים, כלומר אוסף של נתונים מספריים בגודל קבוע. אנו רוצים לחלק את הנקודות במרחב הווקטורי, באמצעות על מישור (Hyperplane) כך שהמרווח, המרחק, בין אותו על-מישור המחלק את הנקודות לבין הנקודות הממוקמות הכי קרוב אליו, יהיה המרחק המקסימלי האפשרי.

חישוב המסווג[עריכת קוד מקור | עריכה]

חישוב המסווג נעשה באמצעות הקטנה (מינימיזציה) של הפונקציה:\left[\frac 1 n \sum_{i=1}^n \max\left(0, 1 - y_i(w\cdot x_i + b)\right) \right] + \lambda\lVert w \rVert^2. כאשר 0,1 הם תוצאות השיוך בפועל (מתוך דוגמאות הלמידה), ו y מייצגת את תוצאת פונקציית הגרעין. בדוגמה זו, y היא פונקציה לינארית, אולם ניתן להשתמש בפונקציות אחרות, דרך "תעלול הגרעין".

penalty[עריכת קוד מקור | עריכה]

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

Kernel Trick[עריכת קוד מקור | עריכה]

צעד נוסף וחשוב אותו נוקטים מדעני המחשב מכונה "תעלול הגרעין" (Kernel Trick). מהלך זה מעתיק את דוגמאות האימון מהמרחב הלינארי המקורי למרחב במימד גבוה יותר, מתוך הנחה שבמרחב החדש ימצא מפריד לינארי טוב יותר מאשר במרחב המקורי. ההעתקה נעשית בעזרת התעלול - מחליפים את המכפלה הפנימית בה משתמשים עבור המפריד הלינארי, בפונקציית kernel אשר מדמה את פיזורם מחדש של הווקטורים המקוריים במרחב עשיר יותר, ללא עלות חישובית משמעותית. המפריד הלינארי במרחב הווקטורי החדש הוא מפריד לא לינארי במרחב המקורי. את מלאכת הסיווג מבצעים אף היא בעזרת אופרטור הגרעין.

הפרדה לא לינארית[עריכת קוד מקור | עריכה]

לעתים קרובות בעיות בעולם האמיתי לא ניתנות לסווג בעזרת מפריד לינארי. במקרים כאלו, משתמשים באותו Kernel Trick. במקום להשתמש במשוואה לינארית על הנקודות (הווקטורים), ניתן להשתמש במשוואות פולינומיות או במרחק גאוסיאני: k(\vec{x_i},\vec{x_j})=\exp(-\gamma \|\vec{x_i} - \vec{x_j}\|^2), כאשר \gamma > 0. לעתים, ניתן להשתמש ב - \gamma=1/{2 \sigma^2} כך שכיוונון המערכת מתבצע דרך מציאת ערך לקבוע הענישה (C) ול \sigma

מימושים נבחרים[עריכת קוד מקור | עריכה]

  • ספריית libsvm , תומכת בסיווג ורגרסיה בעזרת סוגים שונים של SVM. הספרייה נכתבה במקור ב C++ וקיימות עבורה תוכנות מעטפת במגוון רב של שפות תכנות ופלטפורמות.
  • svmlight
P Computer-science.png ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.