סיבוכיות ראדמאכר

בתורת הלמידה, סיבוכיות ראדמאכר, הקרויה על שמו של הנס ראדמאכר, מודדת את העושר של קבוצת וקטורים ב-  או של מחלקת פונקציות עם ערכים ממשיים. בדרך כלל משתמשים בסיבוכיות ראדמאכר כדי לחקור מחלקות של פונקציות עם ערכים ב - , כלומר בעיות סיווג עם שתי מחלקות. אינטואיטיבית, ככל שעושר של קבוצה של וקטורים או של מחלקה של פונקציות גבוה יותר, כך סיבוכיות ראדמאכר תהיה גבוהה יותר.

 הגדרות 
 סיבוכיות ראדמאכר של קבוצה 
בהינתן קבוצה , סיבוכיות ראדמאכר של  מוגדרת באופן הבא:

כאשר , ו  הם משתנים מקריים בלתי תלויים שמתפלגים בהתפלגות ראדמאכר:

.

 סיבוכיות ראדמאכר של משפחת פונקציות 
יהיו מרחב  והתפלגות  עליו. נניח ש -  היא קבוצה שנדגמה מ -  באופן בלתי תלוי לפי ההתפלגות . בנוסף, תהי  משפחת פונקציות מהצורה .

 סיבוכיות ראדמאכר אמפירית 
סיבוכיות ראדמאכר האמפירית של  מוגדרת להיות:

כאשר גם כאן,  בלתי תלויים ומתפלגים לפי התפלגות ראדמאכר.

אפשר גם להסתכל על  כקבוצה ב -  ולקבל שההגדרה של סיבוכיות ראדמאכר של קבוצה מכלילה את הגדרת סיבוכיות ראדמאכר אמפירית.

 סיבוכיות ראדמאכר 
סיבוכיות ראדמאכר של  מוגדרת להיות:

 דוגמאות 

 עבור , מתקיים: 
 עבור  ו - , נקבל: 

 תכונות 
לסיבוכיות ראדמאכר יש מספר תכונות שעוזרות בחישוב או במציאת חסם:

 לכל ,  ו -  מתקיים .
 לכל , הקמור של  הוא בעל אותה סיבוכיות ראדמאכר כמו של .
 (למת מסאר) תהי  ו - , אז מתקיים .
 (למת הכיווץ) לכל , תהיינה  פונקציות -ליפשיץ, כלומר לכל  מתקיים . עבור  נסמן  ו - , אז מתקיים .

 שימושים 
 לחסום את תוחלת היציגות 
נגדיר את היציגות של קבוצה  סופית של דגימות בלתי תלויות מהתפלגות , ביחס למשפחת פונקציות , על ידי

כאשר  עבור .

ניתן לחסום את תוחלת היציגות על ידי החסם הבא:

 לחסום את שגיאת ההכללה 
נניח ש -  קבוצה סופית של זוגות מהצורה , כאשר  זה דגימה ו -  זה הלייבל של , ונניח ש -  היא פונקציית loss, כך שלכל  ו -  מתקיים . אזי, בהסתברות  לפחות, לכל  מתקיים:




מהחסם האחרון אפשר לראות שאם הגודל  קטן, שגיאת ההכללה  לא תהיה רחוקה מדי משגיאת האימון . במקרה של החסם האחרון, משתמשים ב -  גם בזמן הלמידה וגם בזמן בדיקת איכות הלמידה.

 חסמים על הסיבוכיות 
 חסמים הקשורים למחלקות ליניאריות 
נרצה לחסום את סיבוכיות ראדמאכר של מחלקות הפונקציות הבאות:

 ו - .

עבור , יש לנו את הלמה הבאה:

תהי  קבוצה של וקטורים במרחב הילברט. נסמן , אז מתקיים .

ההוכחה מתבססת על שימוש באי-שוויון קושי-שוורץ ובאי-שוויון ינסן.

עבור  יש לנו למה דומה:

תהי  קבוצה של וקטורים ב - , אז מתקיים .

פה ההוכחה מתבססת על אי-שוויון הלדר ולמת מסאר.

 חסמים הקשורים למספר כיסוי של קבוצה 
 מספר כיסוי של קבוצה 
תהי . עבור , נקרא ל -  -רשת של  אם לכל  קיים  כך ש - . מספר הכיסוי  מוגדר להיות העוצמה המינימלית של -רשת של .

 חסם על הסיבוכיות 
אפשר לחסום את סיבוכיות ראדמאכר של קבוצה  על ידי הלמה הבאה:

נסמן . אז לכל שלם  מתקיים

בנוסף, אם נניח שיש  כך ש לכל  מתקיים , אז על ידי לקיחת  לאינסוף נקבל

, כאשר השתמשנו בעובדה ש -  ו - .

 סיבוכיות גאוסית 
 הגדרה 
עבור קבוצה , סיבוכיות גאוסית מוגדרת באופן הבא:

כאשר .

ניתן לראות שההגדרה מאוד דומה להגדרה של סיבוכיות ראדמאכר של קבוצה, כאשר השינוי העיקרי הוא ש -  הוא וקטור גאוסי ולא וקטור שרכיביו מתפלגים לפי התפלגות ראדמאכר. ניתן לחשב את הסיבוכיות הגאוסית של משפחת פונקציות באופן דומה לסיבוכיות ראדמאכר.

 דוגמאות 
להלן מספר דוגמאות בסיסיות לחישוב סיבוכיות גאוסית של קבוצה:
 עבור קבוצה סופית, , מתקיים .
 עבור הקבוצה  מתקיים .

 קשר לסיבוכיות ראדמאכר 
עבור קבוצה , בהתאם להגדרות בעמוד, מתקיים:

אז אפשר לומר שסיבוכיות גאוסית וסיבוכיות ראדמאכר (ליתר דיוק ) שקולות עד כדי גורם מסדר .

 הערות שוליים 

קטגוריה:למידת מכונה