Матричне множення лежить в основі багатьох проривів у машинному навчанні, і тепер воно отримало одразу два рекорди. Минулого тижня компанія DeepMind оголосила, що відкрила ефективніший спосіб виконання матричного множення, побивши 50-річний рекорд. Проте вже цього тижня двоє австрійських дослідників з Університету Йоганна Кеплера в Лінці заявили, що вони перевершили цей новий рекорд на один крок.

Матричне множення, яке передбачає множення двох прямокутних масивів чисел, часто лежить в основі розпізнавання мови, розпізнавання зображень, обробки зображень на смартфонах, стиснення і генерації комп’ютерної графіки. Графічні процесори особливо добре виконують множення матриць завдяки своїй масивно-паралельній природі. Вони можуть розбити велику матричну математичну задачу на багато частин і розв’язувати її одночасно за допомогою спеціального алгоритму.

У 1969 році німецький математик Фолькер Штрассен відкрив найкращий на той час алгоритм множення матриць 4×4, який зменшує кількість кроків, необхідних для виконання матричних обчислень. Наприклад, для перемноження двох матриць 4×4 традиційним шкільним методом знадобилося б 64 множення, тоді як алгоритм Штрассена може виконати ту саму роботу за 49 множень.

Використовуючи нейронну мережу AlphaTensor, компанія DeepMind знайшла спосіб скоротити цю кількість до 47 множень, а її дослідники опублікували статтю про це досягнення в журналі Nature минулого тижня.

Перехід від 49 кроків до 47 не здається чимось значним, але якщо врахувати, скільки трильйонів матричних обчислень відбувається в графічному процесорі щодня, навіть поступове поліпшення може призвести до значного підвищення ефективності, дозволяючи застосункам ШІ працювати швидше на наявному обладнанні.

AlphaTensor є нащадком AlphaGo (системи на основі ШІ, що обіграла чемпіонів світу з гри в Го у 2017 році) та AlphaZero, яка була натренована для гри у шахи та сьоґі (японські шахи). DeepMind називає AlphaTensor «першою системою ШІ для відкриття нових, ефективних і доказово правильних алгоритмів для фундаментальних завдань, таких як множення матриць».

Щоб виявити ефективніші алгоритми матричної математики, DeepMind поставила задачу у вигляді однокористувацької гри. Детальніше про процес компанія написала в блозі минулого тижня:

У цій грі дошка являє собою тривимірний тензор (масив чисел), що фіксує, наскільки далекий від правильного поточний алгоритм. За допомогою набору дозволених ходів, що відповідають інструкціям алгоритму, гравець намагається модифікувати тензор і обнулити його елементи. Коли гравцеві вдається це зробити, це призводить до доказово правильного алгоритму множення матриць для будь-якої пари матриць, а його ефективність вимірюється кількістю кроків, зроблених для обнулення тензора.

Потім DeepMind тренували AlphaTensor за допомогою навчання з підкріпленням грати в цю вигадану математичну гру – подібно до того, як AlphaGo вчився грати в Го, і з часом поступово покращував свої результати. Зрештою, за словами DeepMind, ШІ заново відкрив для себе роботу Штрассена та інших людей-математиків, а потім перевершив їх.

У складнішому прикладі AlphaTensor відкрив новий спосіб виконання множення матриці 5×5 за 96 кроків (проти 98 для старого методу). Цього тижня Мануель Кауерс і Якоб Моосбауер опублікували статтю, в якій стверджують, що їм вдалося скоротити цю кількість на один крок, до 95 множень. Не випадково, що цей рекордний новий алгоритм з’явився так швидко, оскільки він ґрунтується на роботі DeepMind.

У своїй статті Кауерс і Моосбауер пишуть: «Це рішення було отримано зі схеми дослідників DeepMind шляхом застосування послідовності перетворень, що призвели до схеми, з якої можна було виключити одне множення».

Технічний прогрес не стоїть на місці, і з урахуванням того, що ШІ зараз шукає нові алгоритми, цілком можливо, що інші давні математичні рекорди можуть незабаром впасти.