חיפוש מעשי אקראי

יחידה זו מתמקדת בחיפוש אקראי למעין.

מדוע להשתמש בחיפוש מעין אקראי?

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

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

• דגימת מרחב החיפוש באופן לא מותאם מאפשרת לשנות את יעד הכוונון בניתוח פוסט-הוק בלי להפעיל שוב את הניסויים. לדוגמה, אנחנו בדרך כלל רוצים למצוא את הניסוי הטוב ביותר מבחינת שגיאת אימות שהושגה בכל שלב באימון. עם זאת, האופי הלא דינמי של חיפוש אקראי למחצה מאפשר למצוא את הניסוי הטוב ביותר על סמך שגיאת אימות סופית, שגיאת אימון או מדד הערכה חלופי כלשהו, בלי להפעיל מחדש ניסויים.
• חיפוש מעין אקראי מתנהג באופן עקבי שניתן לשחזור באופן סטטיסטי. צריכה להיות אפשרות לשחזר מחקר מלפני שישה חודשים גם אם ההטמעה של אלגוריתם החיפוש השתנתה, כל עוד הוא שומר על אותם מאפייני אחידות. אם משתמשים בתוכנה מתוחכמת לאופטימיזציה בייסיאנית, ההטמעה עשויה להשתנות באופן חשוב בין הגרסאות, מה שיקשה על שחזור חיפוש ישן. לא תמיד אפשר לחזור להטמעה ישנה (למשל, אם כלי האופטימיזציה פועל כשירות).
• החקירה האחידה של מרחב החיפוש מאפשרת לחשוב בקלות על התוצאות ועל מה שהן רומזות על מרחב החיפוש. לדוגמה, אם הנקודה הטובה ביותר במעבר של חיפוש אקראי למחצה היא הגבול של מרחב החיפוש, זה סימן טוב (אבל לא מובטח) שצריך לשנות את גבולות מרחב החיפוש. עם זאת, ייתכן שאלגוריתם אופטימיזציה של קופסה אדפטיבית הזנח את אמצע אזור החיפוש בגלל כמה ניסויים מוקדמים או מוצלחים, גם אם הוא מכיל נקודות טובות באותה מידה, מכיוון שאלגוריתם אופטימיזציה טוב צריך להשתמש בו כדי לזרז את החיפוש.
• הפעלת מספרים שונים של ניסויים במקביל לעומת ברצף לא מניבה תוצאות שונות מבחינה סטטיסטית כשמשתמשים בחיפוש מעין אקראי (או באלגוריתמים אחרים של חיפוש לא אדפטיבים), בניגוד לאלגוריתמים אדפטיביים.
• אלגוריתמים מתוחכמים יותר של חיפוש לא תמיד יטפלו בנקודות לא ניתנות לביצוע, במיוחד אם הם לא תוכננו מתוך מחשבה על כוונון היפר-פרמטר של רשת נוירונים.
• חיפוש מעין אקראי הוא פשוט ופועל טוב במיוחד כשניסיונות כוונון רבים פועלים במקביל. מבחינה אקראית¹, קשה מאוד לאלגוריתם גמיש לגבור על חיפוש אקראי גדול פי 2 מהתקציב, במיוחד כשצריך להפעיל הרבה ניסויים במקביל (ולכן יש סיכוי נמוך מאוד להשתמש בתוצאות של ניסויים קודמים כשמשיקים ניסויים חדשים). ללא התמחות באופטימיזציה בייסיאנית ובשיטות מתקדמות אחרות לאופטימיזציה של קופסאות שחורות, ייתכן שלא תוכלו להשיג את היתרונות שאפשר לספק באופן עקרוני. קשה כנקודת השוואה בין אלגוריתמים מתקדמים של אופטימיזציה של קופסה שחורות (blackbox) בתנאי כוונון מציאותיים של למידה עמוקה (Deep Learning). זהו תחום פעיל מאוד במחקר עכשווי, והאלגוריתמים המתוחכמים יותר כוללים מלכודות משלהם למשתמשים חסרי ניסיון. מומחים בשיטות האלה יכולים להשיג תוצאות טובות, אבל בתנאים של מקביליות גבוהה, מרחב החיפוש והתקציב נוטים להיות חשובים הרבה יותר.

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

איפה אפשר למצוא יישום של חיפוש אקראי לכאורה?

ל-Open-Source Vizier יש הטמעה של חיפוש אקראי מעין. מגדירים את algorithm="QUASI_RANDOM_SEARCH" בדוגמה הזו לשימוש ב-Vizer. קיימת הטמעה חלופית בדוגמה הזו של היפר-פרמטר לגרירה. שתי ההטמעות האלה יוצרות רצף Halton למרחב חיפוש נתון (שנועדה להטמיע רצף Halton הממוזג והמעורבל, כפי שהומלץ ב-Critical Hyper-Parameters: No Random, No Cry.

אם לא זמין אלגוריתם חיפוש מעין אקראי שמבוסס על רצף עם חוסר התאמה נמוך, אפשר להחליף במקום זאת חיפוש פסאודו אחיד אקראי, אבל סביר להניח שהחיפוש יהיה מעט פחות יעיל. במאפיינים 1-2 אפשר גם לבצע חיפוש ברשת, אבל לא במאפיינים גבוהים יותר. (ראו Bergstra & Bengio, 2012).

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

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

איור 3: בוצע כוונון ResNet-50 ב-ImageNet עם 100 ניסויים. באמצעות אתחול המגף בוצעה סימולציה של כמויות שונות של תקציב כוונון. המערכת מציגה בתרשים תרשימי ביצועים של הביצועים הטובים ביותר עבור כל תקציב לניסיון.

 

שימו לב לפרטים הבאים לגבי איור 3:

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

---

1. בן רכט וקווין ג'יימיסון ציינו עד כמה חיפוש אקראי בתקציב 2X הוא חזק בתור בסיס בסיסי (נייר ה-Hyperband מעלה טיעונים דומים), אבל בהחלט אפשר למצוא אזורי חיפוש ובעיות שבהן שיטות אופטימיזציה מתקדמות של בייסיאן מתנגשות עם חיפושים אקראיים שגדולים פי 2 מהתקציב. עם זאת, בניסיונות שלנו לגבור על חיפושים אקראיים פי 2 מהתקציב הנוכחי, הרבה יותר קשה להשתמש במקביליות גבוהה, מאחר שלאופטימיזציה של בייס אין הזדמנות לראות את התוצאות של תקופות ניסיון קודמות.↩