AI חושף אפשרויות חדשות בכפל מטריקס

מתמטיקאים אוהבים פאזל טוב. אפילו משהו מופשט כמו הכפלת מטריצות (טבלאות דו-ממדיות של מספרים) יכול להרגיש כמו משחק כשאתה מנסה למצוא את הדרך היעילה ביותר לעשות זאת. זה קצת כמו לנסות לפתור את הקובייה של רוביק בכמה שפחות מהלכים - מאתגר, אבל מפתה. אלא שעבור קוביית רוביק, מספר המהלכים האפשריים בכל צעד הוא 18; עבור כפל מטריצה, אפילו במקרים פשוטים יחסית, כל שלב יכול להציג יותר מ-10¹² אפשרויות.

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

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

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

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

הכפלת מטריצות

כפל מטריצה ​​היא אחת הפעולות הבסיסיות והנפוצות ביותר בכל המתמטיקה. כדי להכפיל זוג של n-על ידי-n מטריצות, כל אחת עם n² אלמנטים, אתה מכפיל ומוסיף את האלמנטים האלה יחד בשילובים מסוימים כדי ליצור את המוצר, שלישי n-על ידי-n מַטרִיצָה. המתכון הסטנדרטי להכפלת שניים n-על ידי-n מטריצות דורשות n³ פעולות כפל, כך שמטריצה ​​של 2 על 2, למשל, דורשת שמונה הכפלות.

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

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

התגלית של שטראסן הובילה לחיפוש אחר אלגוריתמים יעילים להכפלת מטריצות, אשר מאז היוו השראה לשני תתי-שדות נפרדים. האחד מתמקד בשאלה עקרונית: אם אתה מדמיין להכפיל שניים n-על ידי-n מטריצות ולתת n לרוץ לקראת האינסוף, איך מספר שלבי הכפל בסולם האלגוריתם המהיר ביותר האפשרי עם n? ה השיא הנוכחי עבור קנה המידה הטוב ביותר, n^2.3728596, שייך לאלמן ו וירג'יניה וסילבסקה וויליאמס, מדען מחשבים במכון הטכנולוגי של מסצ'וסטס. (לא פורסם לאחרונה הדפסה מראש דיווחו על שיפור זעיר באמצעות טכניקה חדשה.) אבל האלגוריתמים האלה הם בעלי עניין תיאורטי בלבד, והם מנצחים על שיטות כמו זו של Strassen רק עבור מטריצות גדולות באופן אבסורדי.

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

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

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

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

המשחק מתחיל

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

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

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

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

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

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

שבילים חדשים

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

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

צוות DeepMind אימן את AlphaTensor לפרק טנסורים המייצגים את הכפל של מטריצות עד 12 על 12. הוא חיפש אלגוריתמים מהירים להכפלת מטריצות של מספרים ממשיים רגילים וגם אלגוריתמים ספציפיים להגדרה מוגבלת יותר המכונה מודולו 2 אריתמטיקה. (זוהי מתמטיקה המבוססת על שני מספרים בלבד, כך שרכיבי מטריצה ​​יכולים להיות רק 0 או 1, ו-1 + 1 = 0.) חוקרים לרוב מתחילים עם המרחב המצומצם יותר אך עדיין העצום הזה, בתקווה שניתן יהיה להתאים אלגוריתמים שהתגלו כאן עבודה על מטריצות של מספרים ממשיים.

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

במקרים בודדים, AlphaTensor אפילו ניצחה שיאים קיימים. התגליות המפתיעות ביותר שלו אירעו באריתמטיקה מודולו 2, שם היא מצאה אלגוריתם חדש להכפלת מטריצות של 4 על 4 ב-47 שלבי כפל, שיפור ביחס ל-49 השלבים הנדרשים עבור שתי איטרציות של האלגוריתם של שטראסן. הוא גם ניצח את האלגוריתם הידוע ביותר עבור מטריצות מודולו 5 של 5 על 2, והפחית את מספר הכפלות הנדרשות מהשיא הקודם של 98 ל-96. (אבל השיא החדש הזה עדיין מפגר אחרי 91 השלבים שידרשו כדי לנצח האלגוריתם של שטראסן באמצעות מטריצות של 5 על 5.)

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

החוקרים גם הדגישו שיישומים מיידיים של האלגוריתם שובר השיאים של 4 על 4 יהיו מוגבלים: לא רק שהוא תקף רק בחשבון מודולו 2, אלא שבחיים האמיתיים יש שיקולים חשובים מלבד מהירות.

פאוזי הסכים שבאמת, זו רק ההתחלה. "יש הרבה מקום לשיפור ולמחקר, וזה דבר טוב", אמר.

טוויסט אחרון

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

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

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

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

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

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

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