Вступ
Математики люблять хороші головоломки. Навіть щось таке абстрактне, як множення матриць (двовимірних таблиць чисел), може здаватися грою, коли ви намагаєтеся знайти найефективніший спосіб зробити це. Це трохи схоже на спробу скласти кубик Рубіка за якомога менше рухів — складно, але привабливо. За винятком того, що для кубика Рубіка кількість можливих ходів на кожному кроці становить 18; для множення матриці, навіть у відносно простих випадках, кожен крок може представляти більше 1012 Варіанти.
Протягом останніх 50 років дослідники підходили до цієї проблеми багатьма способами, усі вони ґрунтувалися на комп’ютерному пошуку за допомогою людської інтуїції. Минулого місяця команда компанії зі штучного інтелекту DeepMind показала, як вирішувати проблему з нового напрямку, звітуючи в папір in природа що вони успішно навчили нейронну мережу відкривати нові швидкі алгоритми множення матриць. Це було так, ніби штучний інтелект знайшов невідому стратегію розгадування жахливо складного кубика Рубіка.
"Це дуже гарний результат", - сказав Джош Алман, фахівець з інформатики в Колумбійському університеті. Але він та інші фахівці з множення матриць також підкреслили, що така допомога ШІ доповнить, а не замінить існуючі методи — принаймні в найближчій перспективі. «Це як доказ концепції чогось, що може стати проривом», — сказав Алман. Результат просто допоможе дослідникам у їхніх пошуках.
Ніби на доказ того, через три дні після природа Вийшла стаття, пара австрійських дослідників проілюструвала, як нові та старі методи можуть доповнювати один одного. Для цього вони використовували звичайний комп’ютерний пошук далі покращувати один із алгоритмів, відкритих нейронною мережею.
Результати показують, що, як і процес збирання кубика Рубіка, шлях до кращих алгоритмів буде сповнений поворотів.
Множення матриць
Матричне множення є однією з найбільш фундаментальних і повсюдних операцій у всій математиці. Щоб помножити пару n-за-n матриці, кожна з n2 елементи, ви множите та додаєте ці елементи разом у певних комбінаціях, щоб створити продукт, третій n-за-n матриця. Стандартний рецепт множення на два n-за-n матриці вимагає n3 операції множення, тому, наприклад, матриця 2 на 2 потребує восьми множень.
Для великих матриць із тисячами рядків і стовпців цей процес швидко стає громіздким. Але в 1969 році математик Фолькер Штрассен виявив процедуру для множення пари матриць 2 на 2 із використанням семи, а не восьми кроків множення, ціною введення більшої кількості кроків додавання.
Алгоритм Штрассена непотрібно заплутаний, якщо ви просто хочете помножити пару матриць 2 на 2. Але він зрозумів, що це також працюватиме для більших матриць. Це тому, що елементи матриці самі можуть бути матрицями. Наприклад, матрицю з 20,000 20,000 рядків і 2 2 стовпців можна переосмислити як матрицю 10,000 на 10,000, чотири елементи якої є матрицями 5,000 5,000 на 2 2 кожен. Потім кожну з цих матриць можна розділити на чотири блоки розміром XNUMX на XNUMX і так далі. Штрассен міг застосувати свій метод для множення матриць XNUMX на XNUMX на кожному рівні цієї вкладеної ієрархії. Зі збільшенням розміру матриці зростає економія від меншої кількості множень.
Відкриття Штрассена призвело до пошуку ефективних алгоритмів для множення матриць, що з тих пір надихнуло на дві різні підсфери. Один зосереджується на принциповому питанні: якщо ви уявляєте множення на два n-за-n матриці і нехай n до нескінченності, як кількість кроків множення в найшвидшому можливому алгоритмі масштабується з n? поточний запис для найкращого масштабування, n2.3728596, належить Алман і Вірджинія Василевська Вільямс, спеціаліст з інформатики в Массачусетському технологічному інституті. (Останній неопублікований передрук повідомили про невелике покращення за допомогою нової методики.) Але ці алгоритми представляють суто теоретичний інтерес, перемагаючи такі методи, як Штрассен, лише для абсурдно великих матриць.
Друге підполе мислить у меншому масштабі. Незабаром після роботи Штрассена, ізраїльський американський комп'ютерник Шмуель Віноград показав що Штрассен досяг теоретичної межі: неможливо помножити матриці 2 на 2 менш ніж за сім кроків множення. Але для всіх інших розмірів матриць мінімальна кількість необхідних множень залишається відкритим. А швидкі алгоритми для малих матриць можуть мати надмірний вплив, оскільки повторні ітерації такого алгоритму можуть перевершити алгоритм Штрассена, коли матриці розумного розміру множаться.
На жаль, сама кількість можливостей величезна. Навіть для матриць 3 на 3 «кількість можливих алгоритмів перевищує кількість атомів у Всесвіті», сказав Альхусейн Фаузі, дослідник DeepMind і один із керівників нової роботи.
Зіткнувшись із цим запаморочливим набором опцій, дослідники досягли прогресу, перетворивши множення матриці на те, що здається зовсім іншою математичною задачею — такою, з якою комп’ютерам легше впоратися. Можна представити абстрактну задачу множення двох матриць як певний тип математичного об’єкта: тривимірний масив чисел, який називається тензором. Потім дослідники можуть розбити цей тензор на суму елементарних компонентів, які називаються тензорами рангу 1; кожен з них представлятиме інший крок у відповідному алгоритмі множення матриці. Це означає, що пошук ефективного алгоритму множення означає мінімізацію кількості доданків у тензорному розкладанні — чим менше доданків, тим менше кроків.
Таким чином дослідники відкрили нове алгоритми що розмножуються n-за-n матриць, що використовують менше стандарту n3 кроки множення для багатьох малих розмірів матриці. Але алгоритми, які перевершують не тільки стандарт, але й алгоритм Штрассена для малих матриць, залишалися недосяжними — досі.
Гра на
Команда DeepMind підійшла до проблеми, перетворивши розкладання тензорів на гру для одного гравця. Вони почали з алгоритму глибокого навчання, який походить від AlphaGo — іншого ШІ 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 за кілька хвилин заново відкрив алгоритм Штрассена. Потім було виявлено тисячі нових швидких алгоритмів для кожного розміру матриці. Вони відрізнялися від найвідоміших алгоритмів, але мали однакову кількість кроків множення.
У кількох випадках 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, ми могли б зробити це раніше», — сказав Кауерс. «Але гаразд, ну так це працює».
Літтман очікує більше подібних сюрпризів, порівнюючи ситуацію з першим випадком, коли бігун подолав милю менш ніж за чотири хвилини, подвиг, який багато хто вважав неможливим. «Люди казали: «Ой, зачекайте, ми можемо це зробити», а тепер багато людей можуть це зробити», — сказав він.
Заглядаючи вперед, Fawzi сподівається узагальнити AlphaTensor для вирішення ширшого спектру математичних і обчислювальних завдань, подібно до того, як його предок AlphaGo з часом розгалужився в інших іграх.
Кауерс вважає це справжнім лакмусовим папірцем для застосування машинного навчання для відкриття нових алгоритмів. Він зазначає, що пошук швидких алгоритмів множення матриць є комбінаторною проблемою, для вирішення якої добре підходять комп’ютерні пошуки, за допомогою чи без допомоги людини. Але не всі математичні проблеми так легко визначити. Якщо машинне навчання зможе виявити якісно нову алгоритмічну ідею, сказав він, «це змінить правила гри».
