למידת PAC

בלמידה חישובית, למידת PAC או Probably approximately correct learning (בתרגום חופשי: "למידת קרוב לוודאי בערך נכון") הוא מודל לניתוח מתמטי של בעיות מתחום הלמידה החישובית. המודל הוצג ב־1984 על ידי מדען המחשב הבריטי לסלי וליאנט.

במודל זה הלומד מקבל דוגמאות וצריך לבחור פונקציה מכלילה ("היפותזה") מתוך מחלקה מוגדרת של פונקציות אפשריות. המטרה היא שבהסתברות גבוהה ("קרוב לוודאי"), הפונקציה הנבחרת תהיה בעלת שגיאת הכללה ("בערך נכון") נמוכה. הלומד נדרש להיות מסוגל ללמוד פונקציה בהינתן בחירה של יחס קירוב נדרש, מידת וודאות או התפלגות של דוגמאות.

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

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

הגדרה וטרמינולוגיה

נניח כי $X$ הוא מרחב הדוגמאות (instance space), או קידוד של כל הדוגמאות, וכל דוגמה היא בעלת אורך מוגדר. לדוגמה בבעיית זיהוי תווים $X=\{0,1\}^{n}$. רעיון (concept) הוא תת-קבוצה $c\subset X$, למשל כל התבניות של צורות קידוד האפשריות של ביטים המקודדים את התמונה של האות "P" ב-$X=\{0,1\}^{n}$. מחלקת רעיונות (concept class) היא קבוצה של רעיונות $C$ מעל $X$.

$EX(c,D)$ היא פונקציה המייצרת דוגמה,$x$, מתוך התפלגות $D$ ונותנת לה את הסיווג הנכון $c(x)$, כלומר 1 אם $x\in c$ ו־0 אחרת.

נניח שיש אלגוריתם $A$ שיש לו גישה ל־$EX(c,D)$ והוא מקבל כקלט פרמטרים $\epsilon$ ו־$\delta$ שהם, בהסתברות של לפחות $1-\delta$, $A$ פולט היפותזה $h\in C$ שיש בה טעות השווה או הפחותה מ־$\epsilon$ עם דוגמאות מ־$X$ הבאות מהתפלגות $D$. אם יש אלגוריתם כזה לכל רעיון $c\in C$, לכל התפלגות $D$ מעל $X$, ולכל $0<\epsilon <1/2$ ו־$0<\delta <1/2$ אז $C$ הוא בר למידה לפי מודל PAC או "PAC learnable". ניתן גם להגיד כי $A$ הוא "אלגוריתם לומד PAC" עבור $C$.

האלגוריתם רץ בזמן $t$ אם הוא מייצר לכל היותר $t$ דוגמאות ודורש לכל היותר $t$ צעדים. מחלקת רעיונות היא "למידת PAC יעילה" (efficiently PAC learnable) אם היא למידת PAC באמצעות אלגוריתם שרץ בזמן פולינומי ב־$1/\epsilon$, $1/\delta$ ואורך קידוד הדוגמה.