פירוק לגורמים של מטריצות

פירוק לגורמים של מטריצות הוא מודל הטמעה פשוט. בהינתן מטריצת משוב 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\) ו-item \(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.\]

אפשר לפתור את הבעיה הריבועית הזו באמצעות פירוק ערך Singular (SVD) של המטריצה. אבל, לפעמים גם SVD הוא לא פתרון מעולה, כי באפליקציות אמיתיות, Matrix \(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) מתמחים בנושא הזה למטרה מסוימת.

המטרה היא ריבועית בכל אחת משתי המטריצות U ו-V. (שימו לב, עם זאת, שהבעיה אינה קמורות ביחד). WALS פועל באמצעות אתחול של הטמעות באופן אקראי, ולאחר מכן מתחלפות בין:

• מתקנים \(U\) ופותרים את הבעיה \(V\).
• מתקנים \(V\) ופותרים את הבעיה \(U\).

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

SGD לעומת WALS

ל-SGD ול-WALS יש יתרונות וחסרונות. עיינו במידע שבהמשך כדי להשוות בין המדדים האלה:

SGD

גמיש מאוד — יכול להשתמש פונקציות שונות.

אפשר לבצע במקביל.

איטי יותר – לא מתכנס במהירות.

קשה יותר לטפל ברשומות שלא נצפו (יש צורך לצורך שימוש בדגימה שלילית או בכוח הכבידה).

WALS

מבוססים על 'ריבועי הפסד' בלבד.

אפשר לבצע במקביל.

ההמרות מתבצעות מהר יותר מ-SGD.

קל יותר לטפל ברשומות שלא תועדו.