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