ИИ раскрывает новые возможности умножения матриц

Математики любят хорошие головоломки. Даже такая абстрактная вещь, как умножение матриц (двумерные таблицы чисел) может показаться игрой, когда вы пытаетесь найти наиболее эффективный способ сделать это. Это немного похоже на попытку собрать кубик Рубика за минимальное количество ходов — сложно, но заманчиво. За исключением того, что для кубика Рубика количество возможных ходов на каждом шаге равно 18; для матричного умножения даже в относительно простых случаях каждый шаг может составлять более 10¹² настройки.

За последние 50 лет исследователи подходили к этой проблеме разными способами, и все они основывались на компьютерном поиске, которому помогала человеческая интуиция. В прошлом месяце команда компании DeepMind, занимающейся искусственным интеллектом, показала, как решить проблему с нового направления, сообщив в бумаги in природа что они успешно обучили нейронную сеть открывать новые быстрые алгоритмы умножения матриц. Как будто ИИ нашел неизвестную стратегию для сборки чудовищно сложного кубика Рубика.

«Это очень хороший результат, — сказал Джош Алман, ученый-компьютерщик Колумбийского университета. Но он и другие специалисты по умножению матриц также подчеркнули, что такая помощь ИИ будет дополнять, а не заменять существующие методы — по крайней мере, в ближайшем будущем. «Это похоже на доказательство концепции чего-то, что может стать прорывом», — сказал Алман. Результат просто поможет исследователям в их поисках.

Словно в доказательство этого, через три дня после природа Когда вышла статья, пара австрийских исследователей продемонстрировала, как новые и старые методы могут дополнять друг друга. Они использовали обычный компьютерный поиск, чтобы дальнейшее улучшение один из алгоритмов, обнаруженных нейронной сетью.

Результаты показывают, что, как и в процессе сборки кубика Рубика, путь к лучшим алгоритмам будет полон изгибов и поворотов.

Умножение матриц

Умножение матриц — одна из самых фундаментальных и распространенных операций во всей математике. Чтобы умножить пару 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. Затем каждую из этих матриц можно разделить на четыре блока размером XNUMX на XNUMX и так далее. Штрассен мог применить свой метод для умножения матриц XNUMX на XNUMX на каждом уровне этой вложенной иерархии. По мере увеличения размера матрицы растет экономия от меньшего количества умножений.

Открытие Штрассена привело к поиску эффективных алгоритмов умножения матриц, которые с тех пор вдохновили две отдельные области. Один фокусируется на принципиальном вопросе: если представить себе умножение двух n-На-n матрицы и пусть n стремится к бесконечности, как количество шагов умножения в самом быстром из возможных алгоритмов масштабируется с n? текущий рекорд для лучшего масштабирования, n^2.3728596, принадлежит Алману и Вирджиния Василевска Уильямс, ученый-компьютерщик из Массачусетского технологического института. (Недавняя неопубликованная препринт сообщил о крошечном улучшении с использованием новой техники.) Но эти алгоритмы представляют чисто теоретический интерес, выигрывая у методов, подобных Штрассену, только для абсурдно больших матриц.

Второе подполе мыслит в меньшем масштабе. Вскоре после работы Штрассена израильско-американский ученый-компьютерщик Шмуэль Виноград показал что Штрассен достиг теоретического предела: невозможно умножить матрицы 2 на 2 менее чем за семь шагов умножения. Но для всех других размеров матриц минимальное количество необходимых умножений остается открытым вопросом. И быстрые алгоритмы для небольших матриц могут иметь огромное влияние, поскольку повторные итерации такого алгоритма могут превзойти алгоритм Штрассена, когда перемножаются матрицы разумного размера.

К сожалению, количество возможностей огромно. Даже для матриц 3 на 3 «количество возможных алгоритмов превышает количество атомов во Вселенной», — сказал он. Альхуссейн Фавзи, исследователь DeepMind и один из руководителей новой работы.

Столкнувшись с этим головокружительным меню опций, исследователи добились прогресса, превратив умножение матриц в то, что кажется совершенно другой математической задачей, с которой компьютеру легче справиться. Можно представить абстрактную задачу умножения двух матриц как особый вид математического объекта: трехмерный массив чисел, называемый тензором. Затем исследователи могут разбить этот тензор на сумму элементарных компонентов, называемых тензорами «ранга 1»; каждый из них будет представлять другой шаг в соответствующем алгоритме умножения матриц. Это означает, что поиск эффективного алгоритма умножения сводится к минимизации количества членов в тензорной декомпозиции — чем меньше членов, тем меньше шагов.

Таким образом, исследователи обнаружили новые алгоритмы которые умножают n-На-n матрицы, использующие меньше стандартных n³ шаги умножения для многих малых размеров матриц. Но алгоритмы, которые превосходят не только стандартный, но и алгоритм Штрассена для малых матриц, оставались недоступными — до сих пор.

Игра на

Команда DeepMind подошла к проблеме, превратив тензорную декомпозицию в игру для одного игрока. Они начали с алгоритма глубокого обучения, происходящего от AlphaGo — еще одного ИИ DeepMind, который в 2016 году научился играть в настольную игру Го достаточно хорошо, чтобы победить лучших игроков-людей.

Все алгоритмы глубокого обучения построены на основе нейронных сетей: сетей искусственных нейронов, отсортированных по слоям, с соединениями, которые могут различаться по силе, отражающей, насколько каждый нейрон влияет на нейроны следующего слоя. Сила этих связей настраивается в течение многих итераций процедуры обучения, в ходе которой нейронная сеть учится преобразовывать каждый полученный вход в результат, который помогает алгоритму достичь своей общей цели.

В новом алгоритме 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, мы могли бы сделать это раньше», — сказал Кауэрс. — Но ладно, так оно и работает.

Литтман ожидает, что таких сюрпризов будет больше, сравнивая ситуацию с первым случаем, когда бегун пробежал милю менее чем за четыре минуты, подвиг, который многие считали невозможным. «Люди говорили: «О, подождите, мы можем это сделать», и теперь многие люди могут это сделать», — сказал он.

Заглядывая вперед, Фаузи надеется обобщить AlphaTensor для решения более широкого круга математических и вычислительных задач, точно так же, как его предок AlphaGo в конечном итоге расширился до других игр.

Кауэрс считает это настоящей лакмусовой бумажкой применения машинного обучения для открытия новых алгоритмов. Он указывает, что поиск быстрых алгоритмов умножения матриц — это комбинаторная задача, для решения которой хорошо подходит компьютерный поиск с помощью человека или без него. Но не все математические задачи так легко решить. По его словам, если машинное обучение сможет открыть качественно новую алгоритмическую идею, «это изменит правила игры».