AlphaTensor базується на AlphaZero, агенті, який продемонстрував надлюдську ефективність у настільних іграх, таких як шахи, го та сьогі, і ця робота показує шлях AlphaZero від гри в ігри до вирішення нерозв’язаних математичних проблем уперше.
Стародавні єгиптяни створили алгоритм множення двох чисел без таблиці множення, а грецький математик Евклід описав алгоритм обчислення найбільшого спільного дільника, який використовується досі.
Під час ісламського золотого віку перський математик Мухаммад ібн Муса аль-Хорезмі розробив нові алгоритми для вирішення лінійних і квадратних рівнянь. Фактично, ім'я аль-Хорезмі, перекладене на латину як Algoritmi, призвело до терміну алгоритм. Але, незважаючи на сьогоднішнє знайомство з алгоритмами, які використовуються в усьому суспільстві, від алгебри в класі до передових наукових досліджень, процес відкриття нових алгоритмів неймовірно складний і є прикладом дивовижних міркувань людського розуму.
Вони опубліковані в Nature. AlphaTensor — це перша система штучного інтелекту (ШІ) для відкриття нових, ефективних і перевірено правильних алгоритмів для фундаментальних завдань, таких як множення матриць. Це проливає світло на 50-річне відкрите питання в математиці про пошук найшвидшого способу множення двох матриць.
Навчаючись з нуля, AlphaTensor відкриває алгоритми множення матриць, які є більш ефективними, ніж існуючі алгоритми, розроблені людиною та комп’ютером. Незважаючи на вдосконалення відомих алгоритмів, вони зазначають, що обмеженням AlphaTensor є необхідність попередньо визначити набір потенційних факторів F, що дискретизує простір пошуку, але може призвести до втрати ефективних алгоритмів. Цікавим напрямком майбутніх досліджень є адаптація AlphaTensor для пошуку F. Однією з важливих переваг AlphaTensor є його гнучкість у підтримці складних стохастичних і недиференційованих винагород (від рангу тензора до практичної ефективності на певному апаратному забезпеченні), на додаток до пошуку алгоритмів. для користувацьких операцій у різноманітних просторах (таких як кінцеві поля). Вони вважають, що це підштовхне застосування AlphaTensor до розробки алгоритмів, які оптимізують показники, які ми тут не розглядали, такі як чисельна стабільність або споживання енергії.
Відкриття алгоритмів множення матриць має далекосяжні наслідки, оскільки множення матриць лежить в основі багатьох обчислювальних завдань, таких як інверсія матриці, обчислення визначника та вирішення лінійних систем.
Процес і хід автоматизації алгоритмічного відкриття
По-перше, вони перетворили задачу пошуку ефективних алгоритмів множення матриць у гру для одного гравця. У цій грі дошка є тривимірним тензором (масивом чисел), який фіксує, наскільки далекий від правильності поточний алгоритм. За допомогою набору дозволених ходів, що відповідають інструкціям алгоритму, гравець намагається змінити тензор і обнулити його записи. Коли гравцеві вдається це зробити, це призводить до доведено правильного алгоритму множення матриці для будь-якої пари матриць, а його ефективність визначається кількістю кроків, зроблених для обнулення тензора.
Ця гра неймовірно складна – кількість можливих алгоритмів для розгляду набагато більша, ніж кількість атомів у Всесвіті, навіть для невеликих випадків множення матриць. Порівняно з грою Go, яка десятиліттями залишалася проблемою для ШІ, кількість можливих ходів на кожному кроці їхньої гри на 30 порядків більша (вище 10^33 для одного з налаштувань, які вони розглядають).
По суті, щоб добре грати в цю гру, потрібно визначити найменші голки в гігантському стозі можливостей. Щоб подолати виклики цієї області, яка значно відрізняється від традиційних ігор, ми розробили кілька важливих компонентів, включаючи нову архітектуру нейронної мережі, яка включає специфічні для проблеми індуктивні зміщення, процедуру генерації корисних синтетичних даних і рецепт для використання симетрії проблема.
Потім вони навчили агента AlphaTensor грати в гру за допомогою навчання з підкріпленням, не маючи жодних знань про існуючі алгоритми множення матриць. Завдяки навчанню AlphaTensor поступово вдосконалюється з часом, заново відкриваючи історичні швидкі алгоритми множення матриць, такі як Штрассена, зрештою перевершуючи сферу людської інтуїції та відкриваючи алгоритми швидше, ніж було відомо раніше.
Вивчення впливу на майбутні дослідження та застосування
З математичної точки зору, їхні результати можуть скеровувати подальші дослідження в теорії складності, яка спрямована на визначення найшвидших алгоритмів для вирішення обчислювальних задач. Досліджуючи простір можливих алгоритмів ефективніше, ніж попередні підходи, AlphaTensor допомагає покращити наше розуміння багатства алгоритмів множення матриць. Розуміння цього простору може відкрити нові результати для визначення асимптотичної складності множення матриці, однієї з найбільш фундаментальних відкритих проблем у інформатиці.
Оскільки множення матриць є основним компонентом багатьох обчислювальних завдань, що охоплюють комп’ютерну графіку, цифровий зв’язок, навчання нейронної мережі та наукові обчислення, алгоритми, відкриті AlphaTensor, можуть значно підвищити ефективність обчислень у цих областях. Гнучкість AlphaTensor для розгляду будь-яких цілей також може стимулювати нові програми для розробки алгоритмів, які оптимізують такі показники, як споживання енергії та чисельна стабільність, допомагаючи запобігти невеликим помилкам округлення, що виникають під час роботи алгоритму.
Хоча вони зосередилися тут на конкретній проблемі множення матриць, ми сподіваємося, що наша стаття надихне інших на використання штучного інтелекту для керування алгоритмічним відкриттям для інших фундаментальних обчислювальних завдань. Їхні дослідження також показують, що AlphaZero — це потужний алгоритм, який можна розширити далеко за межі традиційних ігор, щоб допомогти розв’язати відкриті математичні проблеми. Спираючись на наші дослідження, вони сподіваються підштовхнути до більшого обсягу роботи – застосувати штучний інтелект, щоб допомогти суспільству вирішити деякі з найважливіших проблем у математиці та інших науках.
Природа – відкриття швидших алгоритмів множення матриць із підкріпленим навчанням
абстрактний
Підвищення ефективності алгоритмів для фундаментальних обчислень може мати широкий вплив, оскільки це може вплинути на загальну швидкість великої кількості обчислень. Матричне множення — одне з таких примітивних завдань, яке виникає в багатьох системах — від нейронних мереж до наукових обчислювальних процедур. Автоматичне виявлення алгоритмів за допомогою машинного навчання пропонує перспективу вийти за межі людської інтуїції та перевершити поточні найкращі алгоритми, розроблені людиною. Однак автоматизувати процедуру виявлення алгоритму складно, оскільки простір можливих алгоритмів величезний. Тут ми повідомляємо про підхід глибокого підкріплення до навчання на основі AlphaZero1 для виявлення ефективних і доведено правильних алгоритмів для множення довільних матриць. Наш агент, AlphaTensor, навчений грати в гру для одного гравця, метою якої є пошук тензорних розкладів у скінченному факторному просторі. AlphaTensor виявив алгоритми, які перевершують сучасну складність для багатьох розмірів матриць. Особливо актуальним є випадок матриць 4 × 4 у скінченному полі, де алгоритм AlphaTensor вдосконалює дворівневий алгоритм Штрассена вперше, наскільки нам відомо, з моменту його відкриття 50 років тому2. Крім того, ми демонструємо гнучкість AlphaTensor через різні варіанти використання: алгоритми з найсучаснішою складністю для структурованого множення матриць і покращену практичну ефективність шляхом оптимізації множення матриць для виконання на певному обладнанні. Наші результати підкреслюють здатність AlphaTensor пришвидшувати процес алгоритмічного відкриття для ряду проблем і оптимізувати за різними критеріями.
Брайан Ванг - лідер думок футуристів та популярний науковий блогер із 1 мільйоном читачів на місяць. Його блог Nextbigfuture.com посідає перше місце у блозі «Наукові новини». Він охоплює багато руйнівних технологій та тенденцій, включаючи космос, робототехніку, штучний інтелект, медицину, біотехнології проти старіння та нанотехнології.
Відомий тим, що визначає передові технології, в даний час він є співзасновником стартапу та збирання коштів для потенційних компаній на ранніх етапах. Він є керівником досліджень з питань розподілу інвестицій у глибокі технології та інвестором -ангелом у Space Angels.
Частий доповідач у корпораціях, він був спікером TEDx, спікером Університету Сингулярності та гостем у численних інтерв'ю для радіо та подкастів. Він відкритий для публічних виступів та консультування.
