מה זה Randomized SVD (RSVD)?

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

מדוע צריכים RSVD?

פירוק לערכים סינגולריים, SVD, קלאסי לוקח מטריצה A מסדר m × n ומפרק אותה ל:

A = UΣVᵀ

הבעיה היא שחישוב SVD מלא דורש זמן ריצה של (O(min(m²n, mn². עבור מטריצת נתונים מודרנית, למשל, מיליון משתמשים על מיליון סרטים במערכת המלצות, החישוב הזה ייקח חודשים וידרוש זיכרון שמחשב בודד לא יכול להכיל. בעולם האמיתי, רוב המטריצות הן בעלות רעש רב ורק מעט מידע חשוב. כלומר, יש להן דרגה אפקטיבית נמוכה. אנחנו כמעט תמיד איננו צריכים את כל הפירוק המלא, אלא רק את k הערכים הסינגולריים הגדולים ביותר ואת הווקטורים שלהם, כדי לבנות קירוב מדרגה k למטריצה.

המוטיבציה האלגברית של RSVD נשענת על שאלה פשוטה: אם היינו יודעים מראש מהו תת-המרחב שבו נמצאת רוב הפעולה של המטריצה, האם היינו יכולים לחסוך חישובים? התשובה היא כן. אם נמצא בסיס אורתוגונלי קטן, מטריצה Q עם k עמודות, שפורש בקירוב את מרחב העמודות החשובות של A, נוכל להטיל את המטריצה הענקית A על המרחב הקטן הזה, ולקבל מטריצה קטנה מאוד. על המטריצה הקטנה הזו, נוכל לבצע SVD קלאסי בשבריר שנייה.

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

אופן הפעולה של RSVD

האלגוריתם מורכב משני שלבים עיקריים: מציאת תת-המרחב הקטן, באופן אקראי, וביצוע הפירוק עליו, באופן דטרמיניסטי. נניח שאנחנו רוצים למצוא קירוב מדרגה k למטריצה A מסדר m × n. נגדיר פרמטר של דגימת יתר בשם p, לרוב ערך קטן כמו 5 או 10, כדי להבטיח יציבות סטטיסטית. נסמן r = k + p.

מציאת תת-המרחב

1. מגרילים מטריצה שבה כל איבר נדגם מהתפלגות נורמלית גאוסית Ω, בגודל n × r. כרגע יצרנו פילטר אקראי.

2. מחשבים את המכפלה Y = AΩ. זו הפעולה היחידה שדורשת מעבר על כל הנתונים, והיא קלה מאוד למקביליות, למשל ב-GPU. המטריצה Y היא כעת מסדר m × r. עמודות Y מהוות דגימה של מרחב העמודות של A, המוטה לכיוונים הדומיננטיים. מה שעשינו עכשיו זה דגימה של המרחב.

3. מוצאים בסיס אורתונורמלי לעמודות של Y. לרוב עושים זאת בעזרת פירוק QR, כך ש-Y = QR. המטריצה Q, בגודל m × r, היא כעת הבסיס האורתוגונלי שלנו. מתקיים בקירוב מצוין ש-A ≈ QQᵀA. מה שביצענו נקרא אורתוגונליזציה.

פירוק SVD במרחב הקטן

1. נתחיל בהטלה למרחב הקטן: מטילים את המטריצה המקורית הענקית A לתוך הבסיס הקטן Q, על ידי החישוב B = QᵀA. ועכשיו הקסם: המטריצה B היא מטריצה קטנה מאוד בגודל r × n.

2. ממשיכים בביצוע פירוק SVD קלאסי ומדויק על המטריצה הקטנה B:

   
   

   B = ŨΣVᵀ

   
   

   חישוב זה מהיר בצורה יוצאת דופן כי r קטן מאוד.

3. ונסיים בהרכבה חזרה: המטריצה Σ, הערכים הסינגולריים, ו-V, הווקטורים הסינגולריים הימניים, כבר נמצאו והם נכונים למטריצה המקורית! כדי למצוא את הווקטורים השמאליים, פשוט מרימים את Ũ חזרה למרחב המקורי:

   
   

   U = QŨ

   
   

   וקיבלנו את הפירוק המלא והמקורב: A ≈ UΣVᵀ.

האם RSVD זה בעצם SLQ?

אחרי שהבנו את כל זה ונהנינו אפשר לחזור לפוסט הקודם על חישוב העקבה שם הזכרתי את Hutch++ וגם SLQ וכשהסברתי איך עובד Hutch++ כתבתי שמבצעים בו RSVD. ניכר שהצלחתי לבלבל כמה מהקוראים ששאלו האם RSVD זה בעצם SLQ? התשובה היא לא. ממש לא. אלו שתי משפחות שונות של אלגוריתמים.

ההבדל המרכזי ביניהן טמון בדרך שבה הן חוקרות את המטריצה A:

ה-SLQ מבוסס לנצוש/קרילוב: עובד באופן טורי. הוא לוקח וקטור v, מכפיל ב-A, ואת התוצאה מכפיל שוב ב-A וכך הלאה (...v, Av, A²v).

לעומתו ה-RSVD שמבוסס אקראיות/סקיצות עובד באופן מקבילי. הוא לוקח אוסף של וקטורים אקראיים בלתי תלויים, למשל מטריצה אקראית רזה G, ומכפיל את כולם ב-A בבת אחת, AG.

הסבר נוסף לאופן העבודה של RSVD

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

1. מגרילים מטריצה גאוסית אקראית G בגודל n × k (כאשר k ≪ n, למשל 100). זאת הדגימה או הסקצ'ינג.

2. מחשבים את המכפלה Y = AG. הפעולה הזו למעשה דוגמת את מרחב העמודות של A. מכיוון ש-A מגבירה את הווקטורים העצמיים הגדולים שלה, Y תכיל בעיקר מידע עליהם. זאת הדחיסה.

3. מוצאים בסיס אורתוגונלי לעמודות של Y, למשל בעזרת פירוק QR. נקרא לבסיס הזה Q. המטריצה Q (בגודל n × k) פורשת בקירוב מצוין את התת-מרחב של הערכים העצמיים הגדולים. זאת האורתוגונליזציה

4. מטילים את A על המרחב הקטן הזה: B = QᵀAQ, ומבצעים SVD רגיל על המטריצה הקטנה והזולה B. כרגע ביצענו הטלה ופירוק.

איך ++Hutch משלב את הכל יחד?

עכשיו כשהבנו מה זה RSVD, אפשר להבין בדיוק איך ++Hutch עובד ולראות שאין שם SLQ. באלגוריתם ++Hutch הרשמי, מבצעים את השלבים הבאים כדי לחשב את (Tr(A:

1. מציאת החלק הדומיננטי (בעזרת RSVD): משתמשים באלגוריתם כמו Randomized SVD כדי למצוא את המטריצה המקרבת Aₖ המכילה את k הערכים העצמיים הגדולים ביותר ואת הווקטורים שלהם (הבסיס Q).

2. חישוב עקבה מדויק לחלק הדומיננטי: מכיוון שמצאנו את Aₖ באופן מפורש, אנחנו מחשבים את העקבה של החלק הזה בצורה מדויקת לגמרי, פשוט סוכמים את הערכים העצמיים שמצאנו ב-RSVD. בשלב זה אין שום שונות.

3. האצ'ינסון על השארית: כעת נשאר לנו לחשב את העקבה של השארית: (Tr(A − Aₖ. מכיוון ששאבנו מתוך המטריצה את כל הערכים העצמיים הגדולים, המטריצה (A − Aₖ) היא מטריצה שבה כל הערכים העצמיים הם קטנים ודומים בגודלם, הספקטרום שלה שטוח.

   
   

   על השארית הזו, אנחנו מפעילים את שיטת האצ'ינסון הסטנדרטית: [(E[zᵀ(A − Aₖ)z. בגלל שהספקטרום עכשיו שטוח, השונות של האצ'ינסון היא כמעט אפס!

אלגוריתם ++Hutch הוא שילוב חכם של Randomized SVD, כדי לנקות את הערכים העצמיים הגדולים שגורמים לשונות, יחד עם האצ'ינסון קלאסי, לחישוב השארית הזולה, מבלי להזדקק כלל לכלים מורכבים של אינטגרציה נומרית כמו SLQ.

מה זה Randomized SVD (RSVD)?

אנחנו במתמטיקאי מחקר ופיתוח בע"מ מספקים שירותים של מחקר אלגוריתמי יישומי, שירותים של Fractional CTO / Chief Scientist ומייעצים בנושאים של מתמטיקה שימושית, תכן ניתוח שיפור ופיתוח של אלגוריתמים ומבני נתונים. דברו איתי:

שלמה יונה

מייסד ומדען ראשי, מתמטיקאי מחקר ופיתוח בע"מ

053-7326360

shlomo.yona@mathematic.ai 

https://mathematic.ai

פודקאסט על החברה ועליי, שלמה יונה, ואופן העבודה שלנו ואיתנו: A technical deep dive about Mathematic.ai