פירוק למטריצה הוא מודל פשוט להטמעה. בהינתן מטריצת המשוב A \(\in R^{m \times n}\), כאשר \(m\) הוא מספר המשתמשים (או השאילתות) ו \(n\) הוא מספר הפריטים, המודל לומד:
- מטריצת הטמעה של משתמש \(U \in \mathbb R^{m \times d}\), שבה שורה i היא ההטמעה של משתמש i.
- מטריצה של פריט \(V \in \mathbb R^{n \times d}\), שבה שורה j היא ההטמעה של פריט j.
ההטמעה נלמדת כך שהמוצר \(U V^T\) הוא הערכה טובה של מטריצת המשוב א'. שימו לב:\((i, j)\) הכניסה אל \(U . V^T\) היא פשוט מוצר הנקודה \(\langle U_i, V_j\rangle\) בהטמעות של המשתמש \(i\) ופריט \(j\)שאתם רוצים להיות קרובים אליו \(A_{i, j}\).
בחירת הפונקציה האובייקטית
פונקציה אינטואיטיבית אחת היא המרחק הריבועי. כדי לעשות זאת, צריך לצמצם את מספר השגיאות הריבועיות בכל זוגות של רשומות שזוהו:
\[\min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} \sum_{(i, j) \in \text{obs}} (A_{ij} - \langle U_{i}, V_{j} \rangle)^2.\]
בפונקציית היעד הזו, אתם מסכמים רק את הזוגות שנצפו (i, j), כלומר, על ערכים שאינם אפס במטריצת המשוב. עם זאת, לא ניתן רק לסכם את הערכים של אחד מהם – כך ש
אולי אפשר להתייחס לערכים שלא תועדו כאפס ולסכם את כל המטריצה. זאת כדי למזער את המרחק המרובע של Frobenius בין \(A\) להערכה \(U V^T\):
\[\min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} \|A - U V^T\|_F^2.\]
כדי לפתור את הבעיה המרובעת הזו, אפשר להשתמש בפירוק ערך יחיד (SVD) של המטריצה. עם זאת, פתרון ה-SVD הוא לא פתרון נהדר, מאחר שבאפליקציות אמיתיות המטריצ'יה \(A\) מצומצמת מאוד. לדוגמה, נסו לחשוב על כל הסרטונים ב-YouTube בהשוואה לכל הסרטונים שבהם משתמש מסוים צפה. סביר להניח שהפתרון \(UV^T\) (המתאים לדגם של מטריצת הקלט) קרוב לאפס, מה שיוביל לביצועים נמוכים של הכללה.
לעומת זאת, החישוב של מטריצת מטריצות מחלק את המטרה לשני הסכומים הבאים:
- סכום מעל רשומות שנצפו.
- סכום מעל רשומות שלא תועדו (מטופלות כאפסים).
\[\min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} \sum_{(i, j) \in \text{obs}} (A_{ij} - \langle U_{i}, V_{j} \rangle)^2 + w_0 \sum_{(i, j) \not \in \text{obs}} (\langle U_i, V_j\rangle)^2.\]
כאן \(w_0\) יש היפר-פרמטר שמשקלל את שני המונחים כדי שהמטרה לא תהיה הושגה על ידי אחד או יותר. כוונון ההיפר-פרמטר הזה חשוב מאוד.
\[\sum_{(i, j) \in \text{obs}} w_{i, j} (A_{i, j} - \langle U_i, V_j \rangle)^2 + w_0 \sum_{i, j \not \in \text{obs}} \langle U_i, V_j \rangle^2\]
כאשר \(w_{i, j}\) היא פונקציה של תדירות השאילתה i ופריט j.
צמצום הפונקציה האובייקטיבית
האלגוריתמים הנפוצים מצמצמים את הפונקציה האובייקטיבית:
ירידה מדרגית אקראית (SGD) היא שיטה כללית למזעור פונקציות אובדן.
מטרה ריבועית מתחלפת (WALS) שמיועדת למטרה הזו.
המטרה היא ריבועית בכל אחת משתי המטריצות ה-V וה-V. (עם זאת, יש לשים לב שהבעיה אינה המרה משותפת.) פעולת WALS מתחילה באתחול באופן אקראי, ואז מתחלפת בין:
- תיקון \(U\) ופתרון עבור \(V\).
- תיקון \(V\) ופתרון עבור \(U\).
ניתן לפתור כל שלב באופן מדויק (באמצעות פתרון של מערכת לינארית) וניתן להפיץ אותו. השיטה הזאת מובטחת כי כל שלב מובטח כדי להפחית את ההפסד.
SGD לעומת WALS
ל-SGD ול-WALS יש יתרונות וחסרונות. כדי לראות מה השווי שלהם:
SGD
גמישות מאוד – יכולת להשתמש בפונקציות אחרות שאבדו.
ניתן ליצור במקביל אירועים.
איטית יותר – לא מתבצעת כל כך מהר.
קשה יותר להתמודד עם הערכים שלא ניתן לתעד (יש להשתמש בדגימה שלילית או בכוח המשיכה).
WALS
סומכים על כיכרות כאלה בלבד.
ניתן ליצור במקביל אירועים.
מתבצע המרה מהר יותר מ-SGD.
יותר קל לטפל בערכים שלא זוהו.