הסבר מבוסס תורת האינפורמציה של TurboQuant

הנה ניסיון להסביר את אופן הפעולה של TurboQuant מנקודת מבט של תורת האינפורמציה.

מה עושה האלגוריתם?

האלגוריתם מקודד ווקטורים אוקלידיים. תורת האינפורמציה של שאנון מגדירה חסם תחתון לשגיאת שחזור, MSE, שניתנת להשגה בתקציב נתון של b ביטים.עבור וקטור מנורמל, חסם ה-MSE התיאורטי הוא 1/4ᵇ וחסם המכפלה הפנימית הוא

||y||² / (d * 4ᵇ)

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

איך האלגוריתם עושה את זה? איך הוא עובד?

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

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

ב. הקצאת ביט בודד מהתקציב לביצוע התמרת Quantized Johnson-Lindenstrauss על וקטור שארית השגיאה, ההפרש בין הקלט המקורי לוקטור ששוחזר בשלב הראשון.

למה זה עובד? מה מבטיח שזה יעבוד?

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

הרוטציה האקראית היא טרנספורמציית הדמר רנדומלית: y = H·D·x, כאשר H היא מטריצת הדמר ו-D היא מטריצה אלכסונית של היפוכי סימן, פלוס מינוס 1, אקראיים. גם יש אי-תלות וגם יש מהירות.  H היא אורתוגונלית, D מבצעת רנדומיזציה של הפאזה. קואורדינטות הפלט הופכות בקירוב לבלתי תלויות ובעלות התפלגות זהה. משום שלהדמר יש מבנה פרפר בדומה ל-FFT אז  H·D·x עולה (O(d log d ולא (O(d². תודה ל-Guy Regev.

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

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

למה פקטור 2.7? עבור מקור גאוסי, שאליו הנתונים שואפים לאחר הרוטציה, ידוע שקוונטיזציה סקלרית סטטית, Lloyd-Max, בקצב קבוע, ללא קידוד אנטרופיה, משיגה שגיאה שגדולה מהגבול התחתון של שאנון

D_SLB = 2⁻²ᵇ = 1/4ᵇ

בדיוק בפקטור של

(π * √3) / 2

שזה בערך 2.72.

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

Var(X̃) < Var(X)

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

הוספת רכיב ה-Quantized Johnson-Lindenstrauss על שארית השגיאה כתוספת אקראית נועדה להחזיר את תוחלת השגיאה לאפס ובכך להבטיח שתוחלת המכפלה הפנימית תשמר בדיוק את הערך המקורי

E[⟨y, x̃⟩] = ⟨y, x⟩

עוזר להבין? אני אנסה לתאר ולהסביר מנקודות מבט מתמטיות אחרות בתקווה שאצליח.

הסבר מבוסס תורת האינפורמציה של TurboQuant

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

שלמה יונה

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

053-7326360

shlomo.yona@mathematic.ai 

https://mathematic.ai

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