Deep Mind הרחיבה את AlphaZero למתמטיקה כדי לפתוח אפשרויות חדשות עבור אלגוריתמי מחקר.
AlphaTensor, מתבססת על AlphaZero, סוכן שהראה ביצועים על אנושיים במשחקי לוח, כמו שחמט, Go ושוג'י, והעבודה הזו מציגה את המסע של AlphaZero ממשחקים ועד להתמודדות עם בעיות מתמטיות לא פתורות בפעם הראשונה.
המצרים הקדמונים יצרו אלגוריתם להכפלת שני מספרים ללא צורך בטבלת הכפל, והמתמטיקאי היווני אוקלידס תיאר אלגוריתם לחישוב המחלק המשותף הגדול ביותר, שנמצא עד היום בשימוש.
במהלך תור הזהב האסלאמי, המתמטיקאי הפרסי מוחמד בן מוסא אל-ח'ואריזמי עיצב אלגוריתמים חדשים לפתרון משוואות ליניאריות וריבועיות. למעשה, שמו של אל-חוואריזמי, שתורגם ללטינית כאלגוריטמי, הוביל למונח אלגוריתם. אבל, למרות ההיכרות עם האלגוריתמים כיום - המשמשים בכל החברה מהאלגברה בכיתה ועד למחקר מדעי חדשני - התהליך של גילוי אלגוריתמים חדשים הוא קשה להפליא, ודוגמה ליכולות החשיבה המדהימות של המוח האנושי.
הם פרסמו ב-Nature. AlphaTensor היא מערכת הבינה המלאכותית הראשונה (AI) לגילוי אלגוריתמים חדשים, יעילים ונכונים בעליל למשימות בסיסיות כמו כפל מטריצות. זה שופך אור על שאלה פתוחה בת 50 במתמטיקה על מציאת הדרך המהירה ביותר להכפיל שתי מטריצות.
מאומן מאפס, AlphaTensor מגלה אלגוריתמים של כפל מטריצות יעילים יותר מאלגוריתמים אנושיים ומחשבים קיימים. למרות שיפור ביחס לאלגוריתמים ידועים, הם מציינים שמגבלה של AlphaTensor היא הצורך להגדיר מראש קבוצה של ערכי גורמים פוטנציאליים F, מה שמבדיל את מרחב החיפוש אך עלול להוביל להחמצה של אלגוריתמים יעילים. כיוון מעניין למחקר עתידי הוא להתאים את AlphaTensor לחיפוש F. חוזק חשוב אחד של AlphaTensor הוא הגמישות שלו לתמוך בתגמולים סטוכסטיים מורכבים ובלתי ניתנים להבדלה (מדרגת הטנזור ועד ליעילות מעשית בחומרה ספציפית), בנוסף למציאת אלגוריתמים לפעולות מותאמות אישית במגוון רחב של חללים (כגון שדות סופיים). הם מאמינים שזה ידרבן יישומים של AlphaTensor לתכנן אלגוריתמים שמייעלים מדדים שלא שקלנו כאן, כמו יציבות מספרית או צריכת אנרגיה.
לגילוי אלגוריתמי הכפל המטריצה יש השלכות מרחיקות לכת, שכן כפל המטריצה עומד בליבת משימות חישוביות רבות, כגון היפוך מטריצה, מחשוב הקובע ופתרון מערכות ליניאריות.
התהליך וההתקדמות של אוטומציה של גילוי אלגוריתמי
ראשית, הם המירו את הבעיה של מציאת אלגוריתמים יעילים לכפל מטריצה למשחק של שחקן יחיד. במשחק זה, הלוח הוא טנזור תלת מימדי (מערך מספרים), הקולט עד כמה האלגוריתם הנוכחי רחוק מלהיות נכון. באמצעות סט של מהלכים מותרים, התואמים להוראות האלגוריתם, השחקן מנסה לשנות את הטנזור ולאפס את הערכים שלו. כאשר השחקן מצליח לעשות זאת, הדבר גורם לאלגוריתם של כפל מטריצה נכון להוכחה עבור כל זוג מטריצות, והיעילות שלו נתפסת על ידי מספר הצעדים שננקטו כדי לאפס את הטנזור.
המשחק הזה מאתגר להפליא - מספר האלגוריתמים האפשריים שיש לקחת בחשבון גדול בהרבה ממספר האטומים ביקום, אפילו במקרים קטנים של כפל מטריצה. בהשוואה למשחק Go, שנשאר אתגר עבור AI במשך עשרות שנים, מספר המהלכים האפשריים בכל שלב במשחק שלהם גדול ב-30 סדרי גודל (מעל 10^33 עבור אחת ההגדרות שהם מחשיבים).
בעיקרו של דבר, כדי לשחק את המשחק הזה היטב, צריך לזהות את המחטים הקטנות ביותר בערימת שחת ענקית של אפשרויות. כדי להתמודד עם האתגרים של תחום זה, החורג באופן משמעותי ממשחקים מסורתיים, פיתחנו מספר מרכיבים חיוניים, כולל ארכיטקטורת רשת עצבית חדשה המשלבת הטיות אינדוקטיביות ספציפיות לבעיה, הליך ליצירת נתונים סינתטיים שימושיים ומתכון למינוף סימטריות של בְּעָיָה.
לאחר מכן, הם הכשירו סוכן AlphaTensor באמצעות למידת חיזוק לשחק את המשחק, החל ללא כל ידע על אלגוריתמים קיימים של כפל מטריצות. באמצעות למידה, AlphaTensor משתפרת בהדרגה עם הזמן, מגלה מחדש אלגוריתמים היסטוריים של כפל מטריצה מהירה כמו זו של Strassen, בסופו של דבר עולה על תחום האינטואיציה האנושית ומגלה אלגוריתמים מהר יותר מהידוע בעבר.
בחינת ההשפעה על מחקר ויישומים עתידיים
מנקודת מבט מתמטית, התוצאות שלהם יכולות להנחות מחקר נוסף בתורת המורכבות, שמטרתה לקבוע את האלגוריתמים המהירים ביותר לפתרון בעיות חישוביות. על ידי חקר המרחב של אלגוריתמים אפשריים בצורה יעילה יותר מגישות קודמות, AlphaTensor עוזר לקדם את ההבנה שלנו לגבי העושר של אלגוריתמי הכפל המטריצות. הבנת המרחב הזה עשויה לפתוח תוצאות חדשות שיסייעו בקביעת המורכבות האסימפטוטית של כפל מטריצות, אחת הבעיות הפתוחות הבסיסיות ביותר במדעי המחשב.
מכיוון שכפל מטריצות הוא מרכיב ליבה במשימות חישוביות רבות, המתפרשות על גרפיקה ממוחשבת, תקשורת דיגיטלית, אימון ברשתות עצביות ומחשוב מדעי, אלגוריתמים שהתגלו ב-AlphaTensor יכולים להפוך את החישובים בתחומים אלה ליעילים משמעותית. הגמישות של AlphaTensor לשקול כל סוג של מטרה יכולה גם לדרבן יישומים חדשים לעיצוב אלגוריתמים המייעלים מדדים כמו צריכת אנרגיה ויציבות מספרית, ועוזרים למנוע שגיאות עיגול קטנות מכדור שלג כאשר אלגוריתם עובד.
בעוד שהם התמקדו כאן בבעיה המסוימת של כפל מטריצה, אנו מקווים שהמאמר שלנו יעורר השראה לאחרים בשימוש בבינה מלאכותית כדי להנחות גילוי אלגוריתמי עבור משימות חישוב בסיסיות אחרות. המחקר שלהם גם מראה כי AlphaZero הוא אלגוריתם רב עוצמה שניתן להרחיב הרבה מעבר לתחום המשחקים המסורתיים כדי לסייע בפתרון בעיות פתוחות במתמטיקה. בהתבסס על המחקר שלנו, הם מקווים לעודד מערך עבודה גדול יותר - יישום בינה מלאכותית כדי לעזור לחברה לפתור כמה מהאתגרים החשובים ביותר במתמטיקה ובכל המדעים.
טבע - גילוי אלגוריתמים מהירים יותר של כפל מטריצות עם למידת חיזוק
תַקצִיר
לשיפור היעילות של אלגוריתמים לחישובים בסיסיים יכולה להיות השפעה נרחבת, שכן היא יכולה להשפיע על המהירות הכוללת של כמות גדולה של חישובים. כפל מטריקס הוא משימה פרימיטיבית כזו, המתרחשת במערכות רבות - מרשתות עצביות ועד לשגרות מחשוב מדעיות. הגילוי האוטומטי של אלגוריתמים באמצעות למידת מכונה מציעה אפשרות להגיע אל מעבר לאינטואיציה האנושית ולהתעלות על האלגוריתמים הטובים ביותר המתוכננים כיום על ידי האדם. עם זאת, אוטומציה של הליך גילוי האלגוריתמים היא מורכבת, מכיוון שמרחב האלגוריתמים האפשריים הוא עצום. כאן אנו מדווחים על גישת למידת חיזוק עמוק המבוססת על AlphaZero1 לגילוי אלגוריתמים יעילים ונכונים להוכחה להכפלת מטריצות שרירותיות. הסוכן שלנו, AlphaTensor, מאומן לשחק משחק של שחקן יחיד שבו המטרה היא למצוא פירוק טנזור בתוך מרחב גורמים סופי. AlphaTensor גילתה אלגוריתמים שעולים על המורכבות העדכנית ביותר עבור גדלי מטריצות רבים. רלוונטי במיוחד הוא המקרה של מטריצות 4 × 4 בשדה סופי, שבו האלגוריתם של AlphaTensor משתפר באלגוריתם הדו-מפלסי של Strassen לראשונה, למיטב ידיעתנו, מאז גילויו לפני 50 שנה2. אנו מציגים עוד יותר את הגמישות של AlphaTensor באמצעות מקרי שימוש שונים: אלגוריתמים עם מורכבות עדכנית עבור כפל מטריצה מובנית ויעילות מעשית משופרת על ידי אופטימיזציה של כפל מטריצות עבור זמן ריצה על חומרה ספציפית. התוצאות שלנו מדגישות את היכולת של AlphaTensor להאיץ את תהליך הגילוי האלגוריתמי במגוון בעיות, ולבצע אופטימיזציה לקריטריונים שונים.
בריאן וואנג הוא מוביל מחשבה עתידני ובלוגר מדע פופולרי עם מיליון קוראים בחודש. הבלוג שלו Nextbigfuture.com מדורג במקום ה -1 בלוג חדשות המדע. הוא מכסה טכנולוגיות ומגמות משבשות רבות, כולל חלל, רובוטיקה, בינה מלאכותית, רפואה, ביוטכנולוגיה אנטי-אייג'ינג וננוטכנולוגיה.
הוא ידוע בזיהוי טכנולוגיות חדישות, כיום הוא מייסד שותף של סטארט-אפ וגיוס תרומות עבור חברות בשלב מוקדם פוטנציאלי. הוא ראש המחקר להקצאות השקעות טכנולוגיות עמוקות ומשקיע אנג'ל במלאכי חלל.
הוא היה דובר תכופים בתאגידים, הוא היה דובר TEDx, דובר באוניברסיטת סינגולריות והתארח בראיונות רבים לרדיו ולפודקאסטים. הוא פתוח לנאום וליווי התקשרויות בפומבי.
