Ігровий штучний інтелект DeepMind побив рекорд 50-річної давності в інформатиці
DeepMind використав свою настільну гру AI AlphaZero , щоб відкрити швидший спосіб вирішення фундаментальної математичної проблеми в інформатиці, побивши рекорд, який тримався понад 50 років.
Проблема, матричне множення, є ключовим типом обчислення в основі багатьох різних програм, від відображення зображень на екрані до моделювання складної фізики. Це також є фундаментальним для самого машинного навчання. Прискорення цього обчислення може мати великий вплив на тисячі повсякденних комп’ютерних завдань, скоротивши витрати та заощадивши енергію.
«Це справді дивовижний результат», — каже Франсуа Ле Гал, математик з Університету Нагоя в Японії, який не брав участі в роботі. «Множення матриць використовується скрізь у техніці», — каже він. «Усе, що ви хочете вирішити чисельно, ви зазвичай використовуєте матриці».
Незважаючи на всюдисущість обчислень, вони все ще недостатньо вивчені. Матриця — це просто сітка чисел, яка представляє все, що завгодно. Множення двох матриць зазвичай передбачає множення рядків однієї на стовпці іншої. Основну техніку розв’язування задачі викладають у середній школі. «Це схоже на азбуку комп’ютерів», — каже Пушміт Колі, керівник команди DeepMind AI for Science.
Але все ускладнюється, коли ви намагаєтесь знайти швидший спосіб. «Ніхто не знає найкращого алгоритму для її вирішення», — каже Ле Галл. «Це одна з найбільших відкритих проблем у інформатиці».
Це пояснюється тим, що існує більше способів помножити дві матриці разом, ніж атомів у Всесвіті (10 у степені 33, для деяких випадків, які розглядали дослідники). «Кількість можливих дій майже нескінченна», — каже Томас Губерт, інженер DeepMind.
Хитрість полягала в тому, щоб перетворити проблему на своєрідну тривимірну настільну гру під назвою TensorGame. Дошка представляє задачу множення, яку потрібно розв’язати, і кожен хід означає наступний крок у розв’язанні цієї задачі. Отже, ряд ходів, зроблених у грі, представляє алгоритм.
Дослідники навчили нову версію AlphaZero під назвою AlphaTensor грати в цю гру. Замість того, щоб вивчати найкращі серії ходів у Го чи шахах, AlphaTensor вивчав найкращі серії кроків під час множення матриць. Винагороджували за перемогу в грі за якомога менше ходів.
«Ми перетворили це на гру, наш улюблений вид фреймворку», — каже Губерт, який був одним із провідних дослідників AlphaZero.
Дослідники описують свою роботу в статті, опублікованій сьогодні в Nature. Головний результат полягає в тому, що AlphaTensor виявив спосіб помножити разом дві матриці чотири на чотири, який є швидшим, ніж метод, розроблений у 1969 році німецьким математиком Фолькером Штрассеном, який з тих пір ніхто не міг вдосконалити. Метод базової середньої школи складається з 64 кроків; Штрассен робить 49 кроків. AlphaTensor знайшов спосіб зробити це за 47 кроків.
Загалом AlphaTensor перевершує найкращі існуючі алгоритми для понад 70 різних розмірів матриць. Це зменшило кількість кроків, необхідних для множення двох матриць 9 на 9, з 511 до 498, а кількість, необхідну для множення двох матриць 11 на 11, з 919 до 896. У багатьох інших випадках AlphaTensor заново відкрив найкращий існуючий алгоритм .
Дослідники були здивовані тим, скільки різних правильних алгоритмів AlphaTensor знайшов для кожного розміру матриці. «Приголомшливо бачити, що існує принаймні 14 000 способів множення матриць чотири на чотири», — каже Хусейн Фавзі, науковий співробітник DeepMind.
Шукаючи найшвидші алгоритми в теорії, команда DeepMind потім захотіла знати, які з них будуть швидкими на практиці. Різні алгоритми можуть працювати краще на різному обладнанні, оскільки комп’ютерні мікросхеми часто розроблені для певних типів обчислень. Команда DeepMind використовувала AlphaTensor для пошуку алгоритмів, адаптованих до процесорів Nvidia V100 GPU і Google TPU, двох найпоширеніших чіпів, які використовуються для навчання нейронних мереж. Алгоритми, які вони виявили, були на 10-20% швидшими при множенні матриць, ніж ті, які зазвичай використовуються з цими мікросхемами.
Вірджинія Вільямс, комп’ютерний науковець з лабораторії комп’ютерних наук і штучного інтелекту Массачусетського технологічного інституту, в захваті від результатів. Вона зазначає, що протягом деякого часу люди використовували обчислювальні підходи для пошуку нових алгоритмів множення матриць, і багато з існуючих найшвидших алгоритмів були розроблені таким чином. Але ніхто не зміг покращити давні результати, як Штрассен.
«Цей новий метод робить щось зовсім інше, ніж інші», — каже Вільямс. «Було б непогано з’ясувати, чи насправді цей новий метод включає в себе всі попередні, чи можна об’єднати їх і отримати щось ще краще».
Тепер DeepMind планує використовувати AlphaTensor для пошуку інших типів алгоритмів. «Це новий спосіб вивчення інформатики, — каже Колі.