ממד VC
קפיצה לניווט
קפיצה לחיפוש
ממד VC (באנגלית: VC Dimension או Vapnik–Chervonenkis dimension; קרוי על שם הוגיו ולדימיר ופניק ואלכסיי צ'רבוננקיס) הוא מדד בתחום הלמידה החישובית המתאר את רמת כושר ההפרדה של מסווג הנוצר על ידי אלגוריתם למידה.
ממד VC של מסווג כלשהו C מוגדר כגודל הקבוצה הגדולה ביותר של דוגמאות למידה ש C יכול לנפץ (shatter). ניפוץ, או shattering, לצורך הגדרה זו מתקיים כאשר בהינתן קבוצה H המכילה דוגמאות למידה, לכל חלוקה אפשרית שלה לשתי מחלקות סוג, קיים פרמטר α עבור מסווג C כך ש (C(α מסוגל להפריד בהתאם את הדוגמאות שב-H. יש לשים לב שעל פי ההגדרות הנ"ל מתקיים שמימד VC של מסווג C הוא לפחות n אם קיימת קבוצת דוגמאות H כלשהי בגודל n כך שלכל חלוקה אפשרית שלה לשני סוגי דוגמאות, מסווג C מסוגל להפריד נכונה את הדוגמאות שב-H בהתאם.
דוגמאות
- ממד ה-VC של פרספטרון במרחב דו ממדי הוא 3. לא ניתן לפזר במרחב הווקטורי 4 נקודות אשר קו ישר יכול לנפץ תמיד. מאידך, קיים סידור של 3 נקודות שאותן פרספטרון יכול לסווג בהצלחה, עבור כל הקצאה של ערכי מחלקת סוג (class).
- בהכללה - ממד ה-VC של מפריד לינארי במרחב d-ממדי הוא d+1.
- ממד ה-VC של עצי החלטה הוא אינסוף.
