ממד VC

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

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

הגדרה פורמלית

נניח כי ${\mathcal {H}}$ היא מחלקת מסווגים ממרחב כלשהו ${\mathcal {X}}$ לקבוצה בגודל 2 ( מקובל $\{\pm 1\}$, לעיתים גם $\{0,1\}$ ) . לכל $C=\{c_{1},..,c_{m}\}\subseteq {\mathcal {X}}$ סופית, נגדיר את

$${\mathcal {H}}_{C}=\{h|_{c}:C\rightarrow \{\pm 1\}\}=\{h\in {\mathcal {H}}|{\text{h is a function from }}C{\text{ to }}\pm {1}\}=\{(h(c_{1},..,h(c_{m})):h\in {\mathcal {H}}\}$$

גודלה המרבי של קבוצה כזאת, כקבוצת פונקציות בין שתי קבוצות סופיות, הוא לכל היותר $2^{|C|}$ (תלוי באילו היפותזות מחלקת ההיפותזות שלנו כוללת). כאשר גודלה הוא בדיוק $2^{|C|}$, אנו אומרים כי ${\mathcal {H}}$ מנתצת את $C$. במילים אחרות, כאשר ${\mathcal {H}}$ מנתצת קבוצה כלשהי, פירוש הדבר הוא שהיא מכילה את כל התיוגים האפשריים על האיברים שלה (כאשר התיוגים נלקחים מ $\pm 1$).

ממד VC הנו גודלה של הקבוצה הגדולה ביותר ש ${\mathcal {H}}$ מנתצת, כלומר

$$VCdim({\mathcal {H}})=max\{|C|:{\mathcal {H}}{\text{ shatters }}C\}=max\{|C|:|{\mathcal {H}}_{c}|=2^{|C|}\}$$

כאשר ${\mathcal {H}}$ מנתצת כל קבוצה סופית, נאמר כי ממד VC הוא אינסופי ונסמן

$$VCdim({\mathcal {H}})=\infty$$

דוגמאות

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

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

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

משפטים ומסקנות נוספים

קיים קשר הדוק בין ממד ה VC של מחלקת היפותזות לבין learnability של מחלקת היפותזות במודל הסטטיסטי (ראה למידת PAC). בפרט, ממד VC סופי הנו המדד לבחינה האם מחלקה של מסווגים בינארים היא נלמדת (learnable) במודל הזה בהסתברות גבוהה בלי תלות בהתפלגות הנתונים (Agnostic). למעשה נכונה תוצאה רחבה יותר, המכונה המשפט היסודי של למידה סטטיסטית ( The fundamental theorem of statistical learning) עבור סיווג בינארי

ניסוח המשפט

יהי ${\mathcal {X}}$ מרחב ותהא ${\mathcal {H}}\subseteq \{\pm 1\}^{\mathcal {X}}$ מחלקת מסווגים, ונניח שפונקציית ההפסד (loss function) היא 0/1, כלומר סופרת את מספר הטעויות $\sum _{(x,y)\sim {\mathcal {D}}}\mathbf {1} _{\{h(x)\neq y\}}$.

אזי התנאים הבאים שקולים:

1. ל ${\mathcal {H}}$ יש התכנסות במידה שווה (uniform convergence)
2. ${\mathcal {H}}$ ניתנת ללמידה באמצעות אלגוריתם ERM
3. ${\mathcal {H}}$ ניתנת ללמידה באמצעות PAC (כלומר היא PAC learnable)
4. ל ${\mathcal {H}}$ יש ממד VC סופי

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

מדיה וקבצים בנושא ממד VC בוויקישיתוף

• ממד VC, באתר MathWorld (באנגלית)

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