ממד VC

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

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

דוגמאות

 ממד ה-VC של מחלקה המכילה מסווג יחיד הוא 0, וזאת מכיוון שהיא איננה מנפצת אפילו נקודה אחת. באופן כללי ממד ה-VC של מחלקה חסום מלמעלה על ידי לוג (בבסיס 2) של גודל המחלקה.

ממד ה-VC של מחלקת מפרידים ליניאריים במרחב d-ממדי הוא d+1.
לדוגמה, ממד ה-VC של מחלקת מפרידים ליניאריים במרחב דו־ממדי הוא 3. לא ניתן לפזר במרחב הווקטורי 4 נקודות אשר קו ישר יכול לנפץ תמיד. מאידך, קיים סידור של 3 נקודות שאותן מפריד ליניארי יכול לסווג בהצלחה, עבור כל סיווג.
ממד ה-VC של מחלקת עצי החלטה עם מספר צמתים בלתי מוגבל, מעל קבוצה אינסופית, הוא אינסוף.
ממד ה-VC של מחלקת כל המסווגים האפשריים, מעל קבוצה אינסופית, הוא אינסופי, וזאת מכיוון שהיא מנפצת כל קבוצה סופית של דוגמאות.

קישורים חיצוניים

למידת מכונה