С помощью глубокого обучения с подкреплением обнаружены более быстрые алгоритмы сортировки

Nature, том 618, страницы 257–263 (2023 г.) Процитировать эту статью

88 тысяч доступов

952 Альтметрический

Подробности о метриках

Фундаментальные алгоритмы, такие как сортировка или хеширование, используются триллионы раз в день1. Поскольку спрос на вычисления растет, становится критически важным, чтобы эти алгоритмы были максимально производительными. Несмотря на то, что в прошлом был достигнут значительный прогресс2, дальнейшее повышение эффективности этих процедур оказалось сложной задачей как для ученых-людей, так и для вычислительных подходов. Здесь мы покажем, как искусственный интеллект может выйти за рамки нынешнего состояния техники, открыв до сих пор неизвестные процедуры. Чтобы реализовать это, мы сформулировали задачу найти лучшую процедуру сортировки в виде однопользовательской игры. Затем мы обучили новому агенту глубокого обучения AlphaDev играть в эту игру. AlphaDev с нуля разработала небольшие алгоритмы сортировки, которые превзошли ранее известные человеческие тесты. Эти алгоритмы были интегрированы в стандартную библиотеку сортировки C++ LLVM3. Это изменение в этой части библиотеки сортировки представляет собой замену компонента алгоритмом, который был автоматически обнаружен с помощью обучения с подкреплением. Мы также представляем результаты в дополнительных областях, демонстрируя общность подхода.

Человеческая интуиция и ноу-хау сыграли решающую роль в совершенствовании алгоритмов. Однако многие алгоритмы достигли стадии, когда люди-эксперты не могут их оптимизировать дальше, что приводит к постоянно растущим вычислительным узким местам. Работы в классической литературе по синтезу программ, охватывающие многие десятилетия, направлены на создание правильных программ и/или оптимизацию программ с использованием прокси-серверов для уменьшения задержки. К ним относятся методы перечислительного поиска4,5,6,7 и стохастический поиск5,6,8,9,10, а также более поздняя тенденция использования глубокого обучения в синтезе программ для создания правильных программ11,12,13,14,15,16 . Используя глубокое обучение с подкреплением (DRL), мы можем сделать еще один шаг вперед, генерируя правильные и производительные алгоритмы, оптимизируя фактическую измеренную задержку на уровне инструкций ЦП, более эффективно находя и рассматривая пространство правильных и быстрых программ по сравнению с предыдущей работой. .

Один из фундаментальных вопросов информатики — как отсортировать последовательность17,18,19,20. Этому преподают на уроках начальной информатики по всему миру21,22 и повсеместно используют в широком спектре приложений23,24,25. Десятилетия исследований в области информатики были сосредоточены на открытии и оптимизации алгоритмов сортировки26,27,28. Ключевым компонентом практических решений является небольшая сортировка по короткой последовательности элементов; этот алгоритм вызывается повторно при сортировке больших массивов, использующих подход «разделяй и властвуй»29. В этой работе мы фокусируемся на двух типах алгоритмов мелкой сортировки: (1) фиксированная сортировка и (2) сортировка переменной. Алгоритмы фиксированной сортировки сортируют последовательности фиксированной длины (например, сортировка 3 может сортировать только последовательности длины 3), тогда как алгоритмы сортировки переменной могут сортировать последовательности переменного размера (например, сортировка переменной 5 может сортировать последовательности от одной до пяти). элементы).

Задачу открытия новых эффективных алгоритмов сортировки мы сформулируем как однопользовательскую игру, которую назовем AssemblyGame. В этой игре игрок выбирает серию инструкций ЦП низкого уровня, которые мы называем ассемблерными инструкциями30, чтобы объединить их в новый и эффективный алгоритм сортировки. Это сложная задача, поскольку игроку необходимо учитывать комбинаторное пространство инструкций ассемблера, чтобы создать алгоритм, который был бы доказуемо правильным и быстрым. Сложность игры-сборки обусловлена не только размером пространства поиска, который аналогичен чрезвычайно сложным играм, таким как шахматы (10120 игр)31 и Го (10700 игр)32, но и характером функции вознаграждения. Одна неверная инструкция в AssemblyGame потенциально может сделать недействительным весь алгоритм, что сделает исследование этого игрового пространства невероятно сложным.

) to the current algorithm generated thus far. A reward rtis received that comprises both a measure of algorithm correctness and latency. Algorithm correctness (Fig. 2b) involves inputting a set of N test sequences into the current algorithm Pt to generate N outputs. These outputs are then compared to the expected outputs and a correctness reward rt is computed. Latency rewards can be generated by either (1) penalizing the agent for increasing the length of the algorithm (when length and latency are highly correlated) that we refer to as the algorithm length reward, or (2) measuring the actual latency of the algorithm. The game is executed for a limited number of steps, after which the game is terminated. Winning the game corresponds to generating a correct, low-latency algorithm using assembly instructions. Losing the game corresponds to generating an incorrect algorithm or a correct but inefficient algorithm./p> assembly instruction, which is appended to the current algorithm. The agent receives a reward that is a function of the algorithm's correctness, discussed in b, as well as the algorithm's latency. The game is won by the player discovering a low latency, correct algorithm. b, The program correctness and latency computations are used to compute the reward rt. In this example, test sequences are input to the algorithm; for example, in the case of sorting three elements, test inputs comprise all sequences of unsorted elements of length 3. For each sequence, the algorithm output is compared to the expected output (in the case of sorting, the expected output is the sorted elements). In this example, the output \({\bf{D}}{\boldsymbol{{\prime} }}\) does not match the expected output \({\bf{B}}{\boldsymbol{{\prime} }}\) and the algorithm is therefore incorrect./p>