הצגת המקור של הדף "ממד VC"

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

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

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

<math display="block">\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}\}</math>גודלה המרבי של קבוצה כזאת, כקבוצת פונקציות בין שתי קבוצות סופיות, הוא '''לכל היותר''' <math>2^{|C|}</math>  (תלוי באילו היפותזות מחלקת ההיפותזות שלנו כוללת). כאשר גודלה הוא '''בדיוק <math>2^{|C|}</math>''', אנו אומרים כי <math>\mathcal{H}</math> מנפצת את <math>C</math>. במילים אחרות, כאשר <math>\mathcal{H}</math>  מנפצת קבוצה כלשהי, פירוש הדבר הוא שהיא מכילה את כל התיוגים האפשריים על האיברים שלה (כאשר התיוגים נלקחים מ <math>\pm 1</math>).

ממד VC הוא גודלה של הקבוצה הגדולה ביותר ש <math>\mathcal{H}</math> מנפצת, כלומר

<math display="block">VCdim(\mathcal{H}) = max \{ |C|: \mathcal{H} \text{ shatters } C \} = max\{|C| : |\mathcal{H}_{c}| = 2^{|C|}\}</math>כאשר <math>\mathcal{H}</math> מנפצת כל קבוצה סופית, נאמר כי ממד VC הוא אינסופי ונסמן

<math display="block">VCdim(\mathcal{H}) = \infty</math>

==דוגמאות==
[[קובץ:Vc_linear.jpg|שמאל|ממוזער|250px|דוגמה לניפוץ עבור 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) עבור סיווג בינארי

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

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

# ל <math>\mathcal{H}</math> יש [[התכנסות במידה שווה]] (uniform convergence)
# <math>\mathcal{H}</math> ניתנת ללמידה באמצעות אלגוריתם [[Empirical risk minimization|ERM]]
# <math>\mathcal{H}</math> ניתנת ללמידה באמצעות PAC (כלומר היא PAC learnable)
# ל <math>\mathcal{H}</math> יש ממד VC סופי



==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* {{MathWorld}}

{{קצרמר|מדעי המחשב}}
[[קטגוריה:למידת מכונה]]