ממד VC

ממד VC (באנגלית: VC Dimension או Vapnik–Chervonenkis dimension; קרוי על שם הוגיו ולדימיר ופניק ואלכסיי צ'רבוננקיס) הוא מדד בתחום הלמידה החישובית המתאר את רמת כושר ההפרדה של מסווג הנוצר על ידי אלגוריתם למידה.

ממד VC של מסווג כלשהו C מוגדר כגודל הקבוצה הגדולה ביותר של דוגמאות למידה ש C יכול לנפץ (shatter). ניפוץ, או shattering, לצורך הגדרה זו מתקיים כאשר בהינתן קבוצה H המכילה דוגמאות למידה, לכל חלוקה אפשרית שלה לשתי מחלקות סוג, קיים פרמטר α עבור מסווג C כך ש (C(α מסוגל להפריד בהתאם את הדוגמאות שב-H. יש לשים לב שעל פי ההגדרות הנ"ל מתקיים שמימד VC של מסווג C הוא לפחות n אם קיימת קבוצת דוגמאות H כלשהי בגודל n כך שלכל חלוקה אפשרית שלה לשני סוגי דוגמאות, מסווג C מסוגל להפריד נכונה את הדוגמאות שב-H בהתאם.

דוגמאות

דוגמה לניפוץ עבור 3 נקודות במרחב דו-ממדי בעזרת מפריד לינארי. עבור 4 נקודות לא ניתן לבצע ניפוץ.

• ממד ה-VC של פרספטרון במרחב דו ממדי הוא 3. לא ניתן לפזר במרחב הווקטורי 4 נקודות אשר קו ישר יכול לנפץ תמיד. מאידך, קיים סידור של 3 נקודות שאותן פרספטרון יכול לסווג בהצלחה, עבור כל הקצאה של ערכי מחלקת סוג (class).

• • בהכללה - ממד ה-VC של מפריד לינארי במרחב d-ממדי הוא d+1.
• ממד ה-VC של עצי החלטה הוא אינסוף.

ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.