התעמקות מתמטית בתופעת ה Double Descent

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

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

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

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

Model-based double descent

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

המודל המתמטי להמחשה

נניח מודל לינארי 𝑦 = 𝑋𝛽* + 𝜖, כאשר 𝑋 ∈ ℝ^(𝑁×𝑝) היא מטריצת התכונות, 𝑦 ∈ ℝ^𝑁 הוא וקטור התיוגים, ו-𝜖 ~ 𝒩(0, 𝜎²𝐼) הוא רעש.

נסמן ב-𝛾 = 𝑝/𝑁 את יחס המימדים, או רמת הפרמטריזציה. נבחן את שגיאת ההכללה של מודל שנלמד 𝛽̂ כאשר 𝑁, 𝑝 → ∞ אך היחס 𝛾 נשאר קבוע.

המשטר התת פרמטרי עבור 𝛾 < 1

במשטר זה 𝑝 < 𝑁, כלומר יש יותר דגימות מפרמטרים. המערכת מוגדרת יתר על המידה.

האומד הסביר ביותר הוא אומד הריבועים הפחותים, OLS:

𝛽̂ = (𝑋ᵀ𝑋)⁻¹𝑋ᵀ𝑦

כאשר 𝛾 גדל מ-0 לכיוון 1, ההטיה קטנה כי יש למודל יותר יכולת אקספרסיבית. עם זאת, השונות גדלה בקצב של 𝑝/(𝑁−𝑝) תחת הנחות מסוימות של פיזור גאוסי. זוהי העקומה בצורת יו שמוכרת לנו, שבה הסיכון עולה ככל שמתקרבים אל 𝛾 = 1.

נדון כעת במושג סיכון.

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

עבור בעיית רגרסיה עם שגיאה ריבועית ממוצעת, אפשר להגדיר סיכון, שנסמן באות 𝑅, בתור התוחלת של ריבוע השגיאה על דגימת מבחן חדשה:

𝑅(𝛽̂) = 𝔼[(𝑦_new − 𝑥_newᵀ𝛽̂)²]

לפי פירוק מתמטי שמוכר בתור פירוק הטיה ושונות, אפשר לחלק את הסיכון הזה לשלושה רכיבים:

סיכון = שונות + ריבוע של הטיה + רעש בלתי נמנע.

כדי להבין מדוע הסיכון עולה ככל שמתקרבים אל 𝛾 = 1, נסתכל על מה שקורה לשונות ומה שקורה להטיה כאשר משנים את מספר הפרמטרים במודל. היחס 𝛾 מייצג את מספר הפרמטרים 𝑝 חלקי מספר הדגימות 𝑁.

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

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

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

הביטוי המתמטי שמתאר את השונות של האומד 𝛽̂ מכיל את הגודל 𝑝/(𝑁−𝑝). קל לראות שכאשר 𝑝 שואף אל 𝑁 מלמטה, המכנה מתקרב לאפס. כתוצאה מכך, הביטוי של השונות שואף לאינסוף.

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

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

סף האינטרפולציה כאשר 𝛾 → 1

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

על פי תורת המטריצות האקראיות, השונות של אומד הריבועים הפחותים תלויה ישירות בעקבה של ההופכי של מטריצת השונות המשותפת האמפירית, Σ̂ = (1/𝑁)𝑋ᵀ𝑋.

נעצור לרגע להתעכב על כך כדי להסביר:

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

Var( β̂ ) = σ² (XᵀX)⁻¹

כדי להגיע למטריצת השונות המשותפת האמפירית Σ̂, אנו מבצעים נרמול לפי מספר התצפיות, כך שמתקיים הקשר: XᵀX = N Σ̂.

כאשר מציבים את הקשר הזה בתוך נוסחת השונות, מקבלים ששונות האומד שווה ל:

(σ²/N) * Σ̂⁻¹

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

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

(σ²/N) * Tr(Σ̂⁻¹)

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

ולכן, לסיכום:

Total Variance = (σ² / N) * Tr(Σ̂⁻¹)

ממשיכים,

לפי משפט מרצנקו-פסטור, ההתפלגות הספקטרלית, כלומר התפלגות הערכים העצמיים של Σ̂ ידועה. כאשר 𝛾 → 1, התמיכה של התפלגות הערכים העצמיים נוגעת באפס. כלומר, הערך העצמי המינימלי 𝜆_min(Σ̂) → 0. נקדיש אולי פוסט נפרד למשפט מרצנקו-פסטור.

מכיוון שהשונות פרופורציונלית אל Tr(Σ̂⁻¹) ≈ ∑ 1/𝜆_𝑖, כאשר ערכים עצמיים מתקרבים לאפס, ההופכי שלהם שואף לאינסוף. המטריצה הופכת להיות חולה. כתוצאה מכך, המודל רגיש באופן קיצוני לרעש 𝜖 שבדגימות האימון, והנורמה של 𝛽̂ מתפוצצת. זהו המקור לאותה קטסטרופה.

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

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

𝜅(Σ̂) = |λₘₐₓ(Σ̂)| / |λₘᵢₙ(Σ̂)|

כאשר הערך העצמי המינימלי מתקרב לאפס, כפי שמתרחש בסף האינטרפולציה שבו 𝛾 → 1, המכנה בשבר שואף לאפס. כתוצאה מכך, מספר המצב 𝜅 שואף לאינסוף. זהו המדד למצב שאותו אנו מכנים חולה. מטריצה שבה מספר המצב קרוב ל-1 נקראת מטריצה בריאה, או בעברית אקדמית, מטריצה בעלת התנייה טובה.

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

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

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

בבעיית הרגרסיה שלנו, וקטור התיוגים 𝑦 מכיל את הפונקציה האמיתית בתוספת רעש אקראי 𝜖.

כאשר אנו פותרים את מערכת המשוואות, אנו כופלים את הנתונים במטריצה ההופכית Σ̂⁻¹.

הערכים העצמיים של המטריצה ההופכית הם ההופכיים של הערכים המקוריים, כלומר

1/𝜆_𝑖

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

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

המשטר העל פרמטרי עבור 𝛾 > 1

כעת 𝑝 > 𝑁. למערכת משוואות 𝑋𝛽 = 𝑦 יש כעת אינסוף פתרונות, המערכת מוגדרת בחסר. באיזה פתרון נבחר?

לרוב אלגוריתמי האופטימיזציה יש הטיה מובלעת/נרמזת/משתמעת. לדוגמה, אלגוריתם SGD שמתחיל בראשית הצירים, או פתרון בעזרת הופכי מוכלל של מור-פנרוז (Moore-Penrose pseudoinverse) 𝑋†, ימצא תמיד את הפתרון בעל נורמת 𝐿₂ המינימלית שמבצע אינטרפולציה מלאה ושגיאת האימון שלו היא אפס:

𝛽̂ = 𝑋ᵀ(𝑋𝑋ᵀ)⁻¹𝑦

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

נשים לב שהפעם המטריצה שאותה אנו הופכים היא (1/𝑁)𝑋𝑋ᵀ, מטריצה בגודל 𝑁×𝑁. מתוך משפט מרצנקו-פסטור, ובאופן כללי מתוך ריכוז המידה במימדים גבוהים, ככל ש-𝑝 גדל, המרחק בין שורות 𝑋, כלומר הדגימות, במרחב שמימדו 𝑝 הולך וגדל, והן הופכות להיות כמעט אורתוגונליות זו לזו.

מבחינה ספקטרלית, ככל ש-𝛾 → ∞, הערך העצמי המינימלי של (1/𝑁)𝑋𝑋ᵀ הולך ומתרחק מאפס. המטריצה הופכת להיות בריאה מחדש.

יש לנו כל כך הרבה מימדים מיותרים או פרמטרים, שהמודל יכול לפזר את הרעש ואת ההתאמה לשגיאות 𝜖 על פני המון פרמטרים שונים. בגלל שאנו בוחרים את פתרון מינימום הנורמה, שעבורו ‖𝛽̂‖₂ מינימלי, המשקל של הרעש על כל פרמטר בודד הופך לזניח, והפתרון הופך להיות מאוד חלק, וזה מה שמוביל לירידה בשונות ולשגיאת הכללה נמוכה.

האם התופעה מובטחת תמיד? ואם לא, באילו תנאים מובטחת?

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

1. נוכחות של רעש או מפרט מודל שגוי:

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

2. היעדר רגולריזציה מפורשת:

   זהו אולי התנאי החשוב ביותר. Double Descent בולטת במיוחד כאשר מנסים לעשות אינטרפולציה חסרת תקנה. אם נוסיף רגולריזציית רכס עם עונש 𝐿₂ מתאימה, כלומר נפתור min ‖𝑋𝛽 − 𝑦‖₂² + 𝜆‖𝛽‖₂² ונבצע כוונון אופטימלי לפרמטר 𝜆, השיא בנקודה 𝛾 = 1 ייעלם לחלוטין. רגולריזציה אופטימלית תמיד תמנע מהשונות להתפוצץ דרך חסימת הערכים העצמיים הקטנים של ההופכי, על ידי כך שמוסיפים להם 𝜆 > 0. ההחלטה לרדת אל 𝜆 → 0 היא זו שמייצרת את התופעה.

3. הטיה מובלעת של האלגוריתם:

   במשטר העל פרמטרי, קיום אינסוף פתרונות מחייב את האלגוריתם לבחור. SGD בוחר אומד בעל נורמת 𝐿₂ מינימלית. נורמה קטנה פירושה פונקציה חלקה יותר, כלומר קבוע ליפשיץ קטן יותר של הפונקציה שנלמדת. אם נשתמש באלגוריתם רע שבוחר במכוון פתרונות אינטרפולציה עם נורמה גדולה, לא תהיה ירידה שנייה ושגיאת ההכללה תישאר אינסופית.

   
   

אנליזה פונקציונלית ושיטות גרעין

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

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

כאשר מרחיבים את מודל הרשת העצבית לאינסוף פרמטרים, כלומר 𝑝 → ∞, ניתן להראות שאימון על ידי מורד גרדיאנט, במשטר למידה מסוים, שקול לרגרסיית רכס עם פונקציית גרעין קבועה כאשר 𝜆 → 0.

המשמעות מאנליזה פונקציונלית: אנו מחפשים פונקציה 𝑓 ∈ ℋ, כאשר ℋ הוא המרחב שמוגדר על ידי פונקציית הגרעין, שמבצעת אינטרפולציה לנקודות 𝑓(𝑥_𝑖) = 𝑦_𝑖, ובו זמנית ממזערת את נורמת ההילברט שמושרה עליו:

min_{𝑓 ∈ ℋ} ‖𝑓‖_ℋ s.t. 𝑓(𝑥_𝑖) = 𝑦_𝑖 ∀𝑖

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

לסיכום

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

קריאה מומלצת:

• Hastie et al., “Surprises in High-Dimensional Ridgeless Least Squares Interpolation”

• Stein Ioushua et al., “Batches Stabilize the Minimum Norm Risk in High-Dimensional Overparametrized Linear Regression”

התעמקות מתמטית בתופעת ה Double Descent

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

דברו איתי:

שלמה יונה,

מייסד ומדען ראשי, 

מתמטיקאי מחקר ופיתוח בע"מ

053-7326360

shlomo.yona@mathematic.ai

https://mathematic.ai

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

A technical deep dive about Mathematic.ai