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

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

מכונת וקטורים תומכים (באנגלית Support Vector Machine, לרוב נכתב ונהגה כראשי-תבות SVM) היא טכניקה של למידה מונחית (supervised learning) המשמשת לניתוח נתונים לסיווג ולרגרסיה.

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

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

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

עבור שתי קבוצות שונות של נקודות (מלאות וריקות) נדרש על מישור שיפריד ביניהן לצורך סיווג. H1 אינו מפריד בין הנקודות, H2 מפריד ביניהן אך השוליים צרים. H3 מפריד ביניהן עם הגבול השוליים הרחבים ביותר האפשריים

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

באופן פורמלי יותר, בהינתן קבוצת אימון של n נקודות מהצורה כאשר:

  • הוא -1 או 1 ומייצג את הקבוצה לה שייכת דוגמה i.
  • הוא וקטור מאפיינים (פייצ'רים) המתארים את נקודה i.

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

את העל מישור ניתן לייצג באמצעות הנקודות המקיימות: כאשר הוא וקטור נורמלי של העל מישור (לאו דווקא מנורמל).

הפרדה קשיחה (Hard margin)[עריכת קוד מקור | עריכה]

המפריד בעל השוליים הרחבים ביותר

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

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

  • אם הדוגמה חיובית
  • עבור דוגמה שלילית

אילוצים אלו מחייבים שכל נקודה תימצא בצד הנכון של המפריד. לחלופין ניתן לכתוב אילוץ זהה המכסה את שני האילוצים:

.

הפרדה רכה (Soft margin)[עריכת קוד מקור | עריכה]

ניתן להרחיב את SVM לטיפול בבעיות שבהן אין הפרדה לינארית בין שתי הקבוצות באמצעות פונקציית hinge loss:

הפונקציה הנ"ל מתאפסת כאשר מתקיים התנאי שנדרש בהפרדה קשיחה, כלומר כאשר נמצא בצד הנכון של המפריד. עבור נקודות הנמצאות בצידו הלא נכון של המפריד, מקבלת הפונקציה ערך יחסי למרחב מהמפריד.

בגישה זו ממזערים את הביטוי:

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

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

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

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

חישוב המסווג נעשה באמצעות הקטנה (מינימיזציה) של הפונקציה: כאשר 0,1 הם תוצאות השיוך בפועל (מתוך דוגמאות הלמידה), ו y מייצגת את תוצאת פונקציית הגרעין. בדוגמה זו, y היא פונקציה לינארית, אולם ניתן להשתמש בפונקציות אחרות, דרך "תעלול הגרעין". הפונקציה שאותה ממזערים היא פונקציה קמורה של ושל , שאותה ניתן למזער למשל באמצעות גרדיאנט סטוכסטי (SGD).

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

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

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

Kernel Machine.png

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

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

פונקציות קרנל נפוצות:

  • פולינום הומוגני:
  • פולינום לא הומוגני:
  • פונקציית בסיס רדיאלי גאוסייני (RBF; radial basis function): כאשר . לעתים מסומן באמצעות . כך שכיוונון המערכת מתבצע דרך מציאת ערך לקבוע הענישה (C) ול
  • טנגנס היפרבולי: עבור ו-

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

  • ספריית libsvm, תומכת בסיווג ורגרסיה בעזרת סוגים שונים של SVM. הספרייה נכתבה במקור ב C++ וקיימות עבורה תוכנות מעטפת במגוון רב של שפות תכנות ופלטפורמות.
  • svmlight

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ 1.0 1.1 Bernhard E. Boser, Isabelle M. Guyon, Vladimir N. Vapnik, A Training Algorithm for Optimal Margin Classifiers, Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT '92, ACM, 1992, עמ' 144–152 doi: 10.1145/130385.130401
P Computer-science.svg ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.