משתמש:לחכםגל/למידת מכונה אינטראקטיבית

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

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

מבוא

במסגרת למידה מונחית, המטרה היא ללמוד פונקציה של $f:X\to Y$ , כאשר $X$ נחשב כמרחב המקור ו $Y$ כמרחב התוויות, שמנבא היטב מקרים שנלקחו מהתפלגות הסתברות משותפת $p(x,y)$ עַל $X\times Y$ . בפועל, לאלגוריתם הלומד לעולם אינו יודע את ההתפלגות האמיתית $p(x,y)$ עבור כל המרחב. במקום זאת, ללומד בדרך כלל יש גישה לסט אימון של דוגמאות $(x_{1},y_{1}),\ldots ,(x_{n},y_{n})$ . בהגדרה זו, פונקציית ההפסד או מחיר (loss function) ניתנת כ $V:Y\times Y\to \mathbb {R}$, כאשר $V(f(x),y)$ מודד את ההבדל בין הערך החזוי $f(x)$ והערך האמיתי $y$ .

המטרה הכוללת היא לייצר פונקציה המקרבת את $f:X\to Y$. על מנת לעשות זאת, עלינו לייצר אלגוריתם המסוגל, בהינתן סט האימון ופונקציית המחיר, לייצר קירוב טוב לפונקציה $f:X\to Y$ על ידי פונקציה אחרת, ${\bar {f}}:X\to Y$, כך (שבממוצע או בהסתברות גבוהה) המחיר על פני כל הדוגמאות ממוזער. empirical risk.

עם זאת, אנו רוצים כי הפונקציה ${\bar {f}}$ תהיה "לא מסובכת מדי", כלומר מתוך ${\mathcal {H}}$ כאשר ${\mathcal {H}}$ הוא מרחב של פונקציות מסוג מסוים הנקרא מרחב ההיפותזות (או השערות)

${\bar {f}}\in {\mathcal {H}}\subseteq \{f|f:X\longrightarrow Y\}$

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

הגישה הסטטיסטית

במודלים סטטיסטיים של למידה, מדגם האימון $(x_{i},y_{i})$ נמשך מההתפלגות האמיתית $D(x,y)$ והמטרה היא למזער את הסיכון הצפוי (בתוחלת)

$f(x_{j})=\langle w,x_{j}\rangle =w\cdot x_{j}$

גישה נפוצה במצב זה היא להעריך פונקציה ${\hat {f}}$ באמצעות מזעור הסיכון האמפירי או מזעור סיכון אמפירי מוסדר (בדרך כלל תקנון טיכונוב ). הבחירה בפונקציית ההפסד כאן מולידה כמה אלגוריתמי למידה ידועים כמו ריבועים קטנים מוסדרים ומכונות תמיכה וקטוריות . מודל אינטראקטיבי בלבד בקטגוריה זו ילמד רק על סמך הקלט החדש $(x_{t+1},y_{t+1})$, המנבא בשלב הנוכחי של האלגוריתם $f_{t}$ ומידע מהשלבים הקודמים (שלרוב צפויים להיות דרישות אחסון ללא תלות בגודל נתוני האימון). עבור ניסוחים רבים, למשל שיטות ליבה לא ליניאריות, למידה מקוונת אמיתית אינה אפשרית, אם כי ניתן להשתמש בצורה של למידה מקוונת היברידית עם אלגוריתמים רקורסיביים כאשר $f_{t+1}$ מותר לסמוך עליו $f_{t}$ וכל נקודות הנתונים הקודמות $(x_{1},y_{1}),\ldots ,(x_{t},y_{t})$ . במקרה זה, כבר לא מובטחת שדרישות השטח יהיו קבועות מכיוון שהיא דורשת אחסון של כל נקודות הנתונים הקודמות, אך הפתרון עשוי לקחת פחות זמן לחישוב עם הוספת נקודת נתונים חדשה, בהשוואה לטכניקות אימון באצוות (batched training)[1].

אסטרטגיה נפוצה להתגבר על הבעיות הנ"ל היא ללמוד באמצעות מיני-אצוות, אשר מעבדות אצווה קטנה של $b\geq 1$ נקודות נתונים בכל פעם, זה יכול להיחשב כלמידה פסאודו מקוונת עבור $b$ קטן בהרבה ממספר נקודות האימון הכולל. נעשה שימוש בטכניקות מיני-אצווה עם מעבר חוזר ונשנה של נתוני האימון כדי להשיג גרסאות אופטימליות מחוץ לליבה של אלגוריתמים של למידת מכונה, למשל, ירידה בשיפוע סטוכסטי . בשילוב עם התפשטות לאחור, זוהי כיום שיטת האימון דה פקטו לאימון רשתות עצביות מלאכותיות .

דוגמה: ריבועים קטנים ליניאריים

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

למידה באצוות

שקול את ההגדרה של למידה בפיקוח עם $f$ להיות פונקציה לינארית שיש ללמוד:

$I[f]={\underset {(x,y)\sim D}{\mathbb {E} }}[V(f(x),y)]=\int V(f(x),y)\,dp(x,y)\ .$

כאשר $x_{j}\in \mathbb {R} ^{d}$ הוא וקטור של קלטים (נקודות נתונים) ו $w\in \mathbb {R} ^{d}$ הוא וקטור סינון ליניארי. המטרה היא לחשב את וקטור המסנן $w$ . לשם כך, פונקציית אובדן ריבועי

$V(f(x_{j}),y_{j})=(f(x_{j})-y_{j})^{2}=(\langle w,x_{j}\rangle -y_{j})^{2}$

משמש לחישוב הווקטור $w$ שממזער את ההפסד האמפירי

$I_{n}[w]=\sum _{j=1}^{n}V(\langle w,x_{j}\rangle ,y_{j})=\sum _{j=1}^{n}(x_{j}^{T}w-y_{j})^{2}$

לפיכך ניתן להסתכל על שיטה זו כאלגוריתם חמדני . במקרה של אופטימיזציה ריבועית מקוונת (כאשר פונקציית ההפסד נמצאת $v_{t}(w)=||w-x_{t}||_{2}^{2}$ ), אפשר להראות חרטה קשורה שגדלה כמו $\log(T)$ . עם זאת, לא ניתן להשיג גבולות דומים עבור אלגוריתם FTL עבור משפחות חשובות אחרות של מודלים כמו אופטימיזציה ליניארית מקוונת. לשם כך, יש לשנות את FTL על ידי הוספת רגוליזציה.

אם $X$ היא מטריצת נתונים בגודל $i\times d$ ו $y\in \mathbb {R} ^{i}$ הוא וקטור העמודה של ערכי יעד לאחר הגעתן של $i$ נקודות מידע. בהנחה שמטריצת השונות המשותפת $\Sigma _{i}=X^{T}X$ הפיכה (אחרת עדיף להמשיך בצורה דומה עם הסדרת טיכונוב), הפתרון הטוב ביותר $f^{*}(x)=\langle w^{*},x\rangle$ לבעיה הריבועים הקטנים הליניאריים ניתנת על ידי נוסחה סגורה

$w^{*}=(X^{T}X)^{-1}X^{T}y=\Sigma _{i}^{-1}\sum _{j=1}^{i}x_{j}y_{j}$ .

במונחי סיבוכיות, חישוב מטריצת השונות $\Sigma _{i}=\sum _{j=1}^{i}x_{j}x_{j}^{T}$ כוללת זמן $O(id^{2})$, היפוך של $d\times d$ מטריצה לוקחת זמן $O(d^{3})$, בעוד ששאר הכפל לוקח זמן $O(d^{2})$, וזמן כולל של $O(id^{2}+d^{3})$ . כשיש $n$ סך הנקודות במערך הנתונים, כדי לחשב מחדש את הפתרון לאחר הגעת כל נקודת נתונים $i=1,\ldots ,n$, לגישה הנאיבית תהיה סיבוכיות זמן $O(n^{2}d^{2}+nd^{3})$ . שימו לב כי בעת אחסון המטריצה $\Sigma _{i}$, ועדכון שלה בכל שלב על ידי $x_{i+1}x_{i+1}^{T}$, אשר לוקח $O(d^{2})$ זמן, המאפשר לנו צמצום של הזמן הכולל הנדרש ל$O(nd^{2}+nd^{3})=O(nd^{3})$. מאידך,אבל עם שטח אחסון נוסף של $O(d^{2})$ לאחסן $\Sigma _{i}$ .

למידה מקוונת: ריבועים קטנים רקורסיביים

אלגוריתם הריבועים הקטנים הרקורסיבים (RLS) שוקל גישה מקוונת לבעיית הריבועים הקטנים ביותר. ניתן להראות זאת על ידי אתחול $\textstyle w_{0}=0\in \mathbb {R} ^{d}$ ו $\textstyle \Gamma _{0}=I\in \mathbb {R} ^{d\times d}$, ניתן לחשב את הפתרון של בעיית הריבועים הקטנים הליניאריים שניתנה בסעיף הקודם על ידי האיטרציה הבאה:

$w_{t}=\operatorname {arg\,min} _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)$

ניתן להוכיח את אלגוריתם האיטרציה שלעיל באמצעות אינדוקציה $i$ . גם ההוכחה מלמדת על כך $\Gamma _{i}=\Sigma _{i}^{-1}$ . אפשר להסתכל על RLS גם בהקשר של מסננים אדפטיביים (ראה RLS ).

המורכבות עבור $n$ שלבים של אלגוריתם זה הוא $O(nd^{2})$, שהוא מהיר יותר בסדר גודל ממורכבות הלמידה האצווה המקבילה. דרישות האחסון בכל שלב $i$ כאן כדי לאחסן את המטריצה $\Gamma _{i}$, שהוא קבוע ב $O(d^{2})$ . למקרה מתי $\Sigma _{i}$ אינו ניתן להפיכה, שקול את הגרסה המוסדרת של פונקציית אובדן הבעיה $\sum _{j=1}^{n}(x_{j}^{T}w-y_{j})^{2}+\lambda ||w||_{2}^{2}$ . לאחר מכן, קל להראות שאותו אלגוריתם עובד איתו $\Gamma _{0}=(I+\lambda I)^{-1}$, והאיטרציות ממשיכות לתת $\Gamma _{i}=(\Sigma _{i}+\lambda I)^{-1}$ .

$w_{t}=\operatorname {arg\,min} _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)+R(w)$

אופטימיזציה קמורה אינטראקטיבית

אופטימיזציה קמורה מקוונת (OCO) היא מסגרת כללית לקבלת החלטות המשתמשת באופטימיזציה קמורה. המסגרת היא של משחק חוזר:

לצורך האתחול, בוחרים קבוצה קמורה $S$

עבור $t=1,2,...,T$

• הלומד מקבל קלט $x_{t}$
• תפוקות מציע $w_{t}$ מקבוצה קמורה קבועה $S$
• הלומד מקבל פונקציית מחיר נוכחית $v_{t}:S\rightarrow \mathbb {R}$ .
• הלומד סובל מאובדן $v_{t}(w_{t})$ ומעדכן את האומד שלו

המטרה היא למזער חרטה, או את ההבדל בין הפסד מצטבר לאובדן הנקודה הקבועה הטובה ביותר $u\in S$ בדיעבד. כדוגמה, שקול את המקרה של רגרסיה ליניארית בריבועים קטנים מקוונים. כאן, וקטורי המשקל מגיעים מהקבוצה הקמורה $S=\mathbb {R} ^{d}$, והטבע שולח בחזרה את פונקציית האובדן הקמור $v_{t}(w)=(\langle w,x_{t}\rangle -y_{t})^{2}$ . שימו לב כאן $y_{t}$ נשלח במרומז עם $v_{t}$ .

עם זאת, כמה בעיות חיזוי מקוון אינן יכולות להתאים למסגרת של OCO. לדוגמה, בסיווג מקוון, תחום החיזוי ופונקציות ההפסד אינם קמורים. בתרחישים כאלה, נעשה שימוש בשתי טכניקות פשוטות לקמור : אקראי ופונקציות אובדן פונדקאיות
שגיאות פרמטריות בתבנית:מקור
שימוש בפרמטרים מיושנים [ תאריך ] ^{[דרוש מקור]}</link> .

כמה אלגוריתמי אופטימיזציה קמורים מקוונים פשוטים הם:

עקוב אחר המנהיג (FTL)

כלל הלמידה הפשוט ביותר לנסות הוא לבחור (בשלב הנוכחי) את ההשערה עם ההפסד הכי קטן בכל הסבבים שעברו. אלגוריתם זה נקרא Follow the leader, and round $t$ ניתן פשוט על ידי:

כדוגמה מיוחדת, שקול את המקרה של אופטימיזציה ליניארית מקוונת, כלומר שבו הטבע שולח בחזרה פונקציות אובדן של הטופס $v_{t}(w)=\langle w,z_{t}\rangle$ . כמו כן, תן $S=\mathbb {R} ^{d}$ . נניח שפונקציית הרגוליזציה $R(w)={\frac {1}{2\eta }}||w||_{2}^{2}$ נבחר למספר חיובי כלשהו $\eta$ . לאחר מכן, אפשר להראות שהחרטה הממזערת את האיטרציה הופכת

עקוב אחר המנהיג רגולרי (FTRL)

זהו שינוי טבעי של FTL המשמש לייצוב פתרונות FTL ולהשגת גבולות חרטה טובים יותר. פונקציית רגוליזציה $R:S\rightarrow \mathbb {R}$ נבחר והלמידה מתבצעת בסיבוב t כדלקמן: [[קטגוריה:דפים עם תרגומים שלא נסקרו]]