הרחבה ראשונה של AlphaZero למתמטיקה פותחת אפשרויות חדשות למחקר
אלגוריתמים עזרו למתמטיקאים לבצע פעולות יסוד במשך אלפי שנים. המצרים הקדמונים יצרו אלגוריתם להכפלת שני מספרים ללא צורך בטבלת הכפל, והמתמטיקאי היווני אוקלידס תיאר אלגוריתם לחישוב המחלק המשותף הגדול ביותר, שנמצא עד היום בשימוש.
בתקופת תור הזהב האסלאמי, מתמטיקאי פרסי מוחמד בן מוסא אל-ח'ואריזמי עיצב אלגוריתמים חדשים כדי לפתור משוואות ליניאריות וריבועיות. למעשה, שמו של אל-ח'ואריזמי, תורגם ללטינית כ אלגוריטמי, הוביל למונח אלגוריתם. אבל, למרות ההיכרות עם האלגוריתמים כיום - המשמשים בכל החברה מהאלגברה בכיתה ועד למחקר מדעי חדשני - התהליך של גילוי אלגוריתמים חדשים הוא קשה להפליא, ודוגמה ליכולות החשיבה המדהימות של המוח האנושי.
בשלנו מאמר, פורסם היום ב-Nature, אנחנו מציגים AlphaTensor, מערכת הבינה המלאכותית הראשונה (AI) לגילוי אלגוריתמים חדישים, יעילים ונכונים בעליל למשימות בסיסיות כמו כפל מטריצה. זה שופך אור על שאלה פתוחה בת 50 במתמטיקה על מציאת הדרך המהירה ביותר להכפיל שתי מטריצות.
מאמר זה מהווה אבן דרך במשימתה של DeepMind לקדם את המדע ולפתוח את הבעיות הבסיסיות ביותר באמצעות AI. המערכת שלנו, AlphaTensor, מבוססת על AlphaZero, סוכן שיש לו הראו ביצועים על אנושיים במשחקי לוח, כמו שחמט, גו ושוגי, והעבודה הזו מציגה את המסע של AlphaZero ממשחקים להתמודדות עם בעיות מתמטיות לא פתורות בפעם הראשונה.
כפל מטריקס
כפל מטריצה היא אחת הפעולות הפשוטות ביותר באלגברה, הנלמדת בדרך כלל בשיעורי מתמטיקה בתיכון. אבל מחוץ לכיתה, לפעולה המתמטית הצנועה הזו יש השפעה עצומה בעולם הדיגיטלי העכשווי והיא נפוצה בכל מקום במחשוב המודרני.
פעולה זו משמשת לעיבוד תמונות בסמארטפונים, זיהוי פקודות דיבור, יצירת גרפיקה למשחקי מחשב, הפעלת סימולציות לניבוי מזג האוויר, דחיסת נתונים וסרטונים לשיתוף באינטרנט ועוד ועוד. חברות ברחבי העולם מוציאות כמויות גדולות של זמן וכסף בפיתוח חומרת מחשוב כדי להכפיל ביעילות מטריצות. לכן, אפילו לשיפורים קלים ביעילות הכפל המטריצה יכולים להיות השפעה נרחבת.
במשך מאות שנים, מתמטיקאים האמינו שאלגוריתם הכפל המטריצה הסטנדרטי הוא הטוב ביותר שניתן להשיג מבחינת יעילות. אבל בשנת 1969, המתמטיקאי הגרמני Volken Strassen זעזע את הקהילה המתמטית על ידי מראה שאלגוריתמים טובים יותר אכן קיימים.
באמצעות לימוד מטריצות קטנות מאוד (גודל 2×2), הוא גילה דרך גאונית לשלב את הערכים של המטריצות כדי להניב אלגוריתם מהיר יותר. למרות עשרות שנות מחקר בעקבות פריצת הדרך של שטראסן, גרסאות גדולות יותר של בעיה זו נותרו בלתי פתורות - עד כדי כך שלא ידוע באיזו יעילות אפשר להכפיל שתי מטריצות קטנות כמו 3×3.
במאמר שלנו, חקרנו כיצד טכניקות בינה מלאכותית מודרניות יכולות לקדם את הגילוי האוטומטי של אלגוריתמים חדשים לכפל מטריצות. בהתבסס על התקדמות האינטואיציה האנושית, AlphaTensor גילתה אלגוריתמים יעילים יותר מהטכנולוגיה המתקדמת עבור גדלי מטריצות רבים. האלגוריתמים שעוצבו בינה מלאכותית שלנו מתגברים על אלו שתוכננו על ידי אדם, וזה צעד גדול קדימה בתחום הגילוי האלגוריתמי.
התהליך וההתקדמות של אוטומציה של גילוי אלגוריתמי
ראשית, המרנו את הבעיה של מציאת אלגוריתמים יעילים לכפל מטריצה למשחק של שחקן יחיד. במשחק זה, הלוח הוא טנזור תלת מימדי (מערך מספרים), הקולט עד כמה האלגוריתם הנוכחי רחוק מלהיות נכון. באמצעות סט של מהלכים מותרים, התואמים להוראות האלגוריתם, השחקן מנסה לשנות את הטנזור ולאפס את הערכים שלו. כאשר השחקן מצליח לעשות זאת, הדבר גורם לאלגוריתם של כפל מטריצה נכון להוכחה עבור כל זוג מטריצות, והיעילות שלו נתפסת על ידי מספר הצעדים שננקטו כדי לאפס את הטנזור.
המשחק הזה מאתגר להפליא - מספר האלגוריתמים האפשריים שיש לקחת בחשבון גדול בהרבה ממספר האטומים ביקום, אפילו במקרים קטנים של כפל מטריצה. לעומת המשחק של גו, שנשאר אתגר עבור AI במשך עשרות שנים, מספר המהלכים האפשריים בכל שלב במשחק שלנו גדול ב-30 סדרי גודל (מעל 1033 עבור אחת ההגדרות שאנו רואים).
בעיקרו של דבר, כדי לשחק את המשחק הזה היטב, צריך לזהות את המחטים הקטנות ביותר בערימת שחת ענקית של אפשרויות. כדי להתמודד עם האתגרים של תחום זה, החורג באופן משמעותי ממשחקים מסורתיים, פיתחנו מספר מרכיבים חיוניים, כולל ארכיטקטורת רשת עצבית חדשה המשלבת הטיות אינדוקטיביות ספציפיות לבעיה, הליך ליצירת נתונים סינתטיים שימושיים ומתכון למינוף סימטריות של בְּעָיָה.
לאחר מכן אימנו סוכן AlphaTensor באמצעות למידת חיזוק לשחק את המשחק, החל ללא כל ידע על אלגוריתמים קיימים של כפל מטריצות. באמצעות למידה, AlphaTensor משתפרת בהדרגה עם הזמן, מגלה מחדש אלגוריתמים היסטוריים של כפל מטריצה מהירה כמו זו של Strassen, בסופו של דבר עולה על תחום האינטואיציה האנושית ומגלה אלגוריתמים מהר יותר מהידוע בעבר.
לדוגמה, אם האלגוריתם המסורתי הנלמד בבית הספר מכפיל מטריצה של 4×5 על 5×5 באמצעות 100 הכפלות, והמספר הזה הצטמצם ל-80 בעזרת כושר ההמצאה האנושי, AlphaTensor מצאה אלגוריתמים שעושים את אותה פעולה תוך שימוש ב-76 הכפלות בלבד.
מעבר לדוגמא הזו, האלגוריתם של AlphaTensor משפר את האלגוריתם הדו-מפלסי של Strassen בשדה סופי לראשונה מאז גילויו לפני 50 שנה. אלגוריתמים אלה להכפלת מטריצות קטנות יכולים לשמש כפרימיטיבים להכפלת מטריצות גדולות בהרבה בגודל שרירותי.
יתרה מכך, AlphaTensor מגלה גם קבוצה מגוונת של אלגוריתמים עם מורכבות מתקדמת - עד אלפי אלגוריתמים של כפל מטריצות לכל גודל, מה שמראה שהמרחב של אלגוריתמי כפל מטריצות עשיר יותר ממה שחשבו בעבר.
לאלגוריתמים במרחב העשיר הזה יש תכונות מתמטיות ומעשיות שונות. תוך מינוף הגיוון הזה, התאמנו את AlphaTensor כדי למצוא ספציפית אלגוריתמים מהירים בחומרה נתונה, כגון Nvidia V100 GPU ו-Google TPU v2. אלגוריתמים אלה מכפילים מטריצות גדולות ב-10-20% מהר יותר מהאלגוריתמים הנפוצים על אותה חומרה, מה שמציג את הגמישות של AlphaTensor באופטימיזציה של יעדים שרירותיים.
בחינת ההשפעה על מחקר ויישומים עתידיים
מנקודת מבט מתמטית, התוצאות שלנו יכולות להנחות מחקר נוסף בתורת המורכבות, שמטרתה לקבוע את האלגוריתמים המהירים ביותר לפתרון בעיות חישוביות. על ידי חקר המרחב של אלגוריתמים אפשריים בצורה יעילה יותר מגישות קודמות, AlphaTensor עוזר לקדם את ההבנה שלנו לגבי העושר של אלגוריתמי כפל מטריצות. הבנת המרחב הזה עשויה לפתוח תוצאות חדשות שיסייעו בקביעת המורכבות האסימפטוטית של כפל מטריצה, אחת הבעיות הפתוחות הבסיסיות ביותר במדעי המחשב.
מכיוון שכפל מטריצות הוא מרכיב ליבה במשימות חישוביות רבות, המתפרשות על גרפיקה ממוחשבת, תקשורת דיגיטלית, אימון ברשתות עצביות ומחשוב מדעי, אלגוריתמים שהתגלו ב-AlphaTensor יכולים להפוך את החישובים בתחומים אלה ליעילים משמעותית. הגמישות של AlphaTensor לשקול כל סוג של מטרה יכולה גם לדרבן יישומים חדשים לעיצוב אלגוריתמים המייעלים מדדים כמו צריכת אנרגיה ויציבות מספרית, ועוזרים למנוע שגיאות עיגול קטנות מכדור שלג כאשר אלגוריתם עובד.
בעוד שהתמקדנו כאן בבעיה הספציפית של כפל מטריצה, אנו מקווים שהמאמר שלנו יתן השראה לאחרים בשימוש בבינה מלאכותית כדי להנחות גילוי אלגוריתמי עבור משימות חישוב בסיסיות אחרות. המחקר שלנו גם מראה כי AlphaZero הוא אלגוריתם רב עוצמה שניתן להרחיב הרבה מעבר לתחום המשחקים המסורתיים כדי לעזור לפתור בעיות פתוחות במתמטיקה. בהתבסס על המחקר שלנו, אנו מקווים לעודד מערך עבודה גדול יותר - יישום בינה מלאכותית כדי לעזור לחברה לפתור כמה מהאתגרים החשובים ביותר במתמטיקה ובמדעים.
