פתיחת התפריט הראשי

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

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

דוגמאותעריכה

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

קישורים חיצונייםעריכה

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