שיטת האצ'ינסון

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

מה המוטיבציה ולמה אנחנו צריכים את זה בכלל?

העקבה של מטריצה ריבועית A בגודל n × n מוגדרת כסכום איברי האלכסון שלה: Tr(A) = Σ Aᵢᵢ. אם המטריצה קטנה או נתונה לנו מפורשות בזיכרון, החישוב הוא פשוט ודורש חישוב ליניארי ביחס לגודל המטריצה. הבעיה מתחילה בשני תרחישים נפוצים בעולמות הבינה המלאכותית, הנתונים והפיזיקה:

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

• המטריצה מרומזת: לעיתים קרובות אין לנו את המטריצה A כישות נתונים ממשית, אלא רק כפעולה מתמטית. אנחנו לא יכולים לשלוף איבר ספציפי Aᵢᵢ, אבל אנחנו כן יכולים לקבל וקטור v, לכפול אותו במטריצה, ולהחזיר את התוצאה Av. דוגמה קלאסית היא מכפלת מטריצת הסיאן בווקטור. חישוב כל מטריצת הסיאן מפורשות ייקח זמן וזיכרון ריבועיים, אבל חישוב המכפלה שלה בווקטור יכול להתבצע בזמן ליניארי בלבד בעזרת גזירה אוטומטית.
  

כאן בדיוק נכנסת שיטת האצ'ינסון: היא מאפשרת להעריך את סכום האלכסון של מטריצה אך ורק באמצעות מכפלות של המטריצה בווקטורים.

מי המציא את השיטה ואיך?

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

איך זה עובד והאינטואיציה המתמטית

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

העיקרון:

נדגום וקטור אקראי z בגודל n, שבו כל איבר zᵢ נדגם באופן בלתי תלוי מתוך התפלגות המקיימת תוחלת E[zᵢ] = 0 ושונות Var(zᵢ) = 1. הבחירה הנפוצה ביותר והמיטבית מבחינת שונות השיערוך היא התפלגות רדמאכר, שבה כל איבר הוא 1 או מינוס 1 בהסתברות שווה.

הפיתוח המתמטי שלב אחר שלב:

1. המכפלה zᵀAz מייצרת סקלר שהוא מספר בודד.

2. העקבה של סקלר היא הסקלר עצמו, לכן מתקיים: zᵀAz = Tr(zᵀAz)

3. העקבה מקיימת תכונה מחזורית, כלומר Tr(XYZ) = Tr(ZXY). נפעיל תכונה זו ונקבל: Tr(zᵀAz) = Tr(Azzᵀ)

4. כעת, נבדוק מהי התוחלת של הביטוי הזה. העקבה היא אופרטור ליניארי, ולכן התוחלת יכולה להיכנס פנימה: E[zᵀAz] = E[Tr(Azzᵀ)] = Tr(A · E[zzᵀ])

5. המטריצה E[zzᵀ] היא מטריצת השונות המשותפת של z. מכיוון שהאיברים ב-z בלתי תלויים זה בזה ויש להם שונות 1 ותוחלת 0, הערכים מחוץ לאלכסון יתאפסו, והערכים על האלכסון יהיו 1. כלומר, מקבלים בדיוק את מטריצת היחידה I, ולכן מתקיים: E[zzᵀ] = I

6. נציב חזרה את התוצאה: Tr(A · I) = Tr(A)

המסקנה: התוחלת של הביטוי zᵀAz שווה בדיוק לעקבה של A.

האלגוריתם בשיטת מונטה קרלו בפועל

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

Tr(A) ≈ (1/m) Σ zₖᵀAzₖ

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

למה זה כל כך טוב ומה השימושים?

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

• מקביליות: קיימת יכולת להריץ את כל הדגימות במקביל בצורה מושלמת על מעבדים גרפיים.

שימושים מרכזיים כיום

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

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

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

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

שיטת האצ'ינסון

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

דברו איתי:

שלמה יונה

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

053-7326360

shlomo.yona@mathematic.ai 

https://mathematic.ai

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