ИИ AlphaDev придумал более быстрый алгоритм сортировки

В области информатики, пожалуй, нет более фундаментальной задачи, чем сортировка. Пузырьковая, вставками, слиянием — выбирайте сами. Методы упорядочивания данных в компьютере были до смерти теоретизированы, служили практическими упражнениями для миллионов новичков и десятилетиями оптимизировались опытными разработчиками. Наберите функцию sort() в любом языке программирования, и это код, на который вы можете положиться. Не трогайте его. Он и так отлично работает.

Но в прошлом году система искусственного интеллекта, разработанная инженерами из Deepmind компании Google, улучшила великолепную работу ровно настолько, чтобы это имело значение. Перед системой, которую Deepmind называет AlphaDev, была поставлена задача придумать новый способ сортировки коротких последовательностей чисел на C++, популярном языке программирования. Это означало, что нужно было залезть под капот и заставить ИИ создавать новые алгоритмы с применением  ассемблера, который устраняет разрыв между языками программирования, такими как C++, и компьютерным железом.

Эксперимент удался. С апреля прошлого года C++ стал работать немного быстрее благодаря новому набору алгоритмов сортировки, разработанных ИИ. Но, по словам инженеров AlphaDev, которые описали свою работу сегодня в журнале Nature, это только первый шаг. «Мы хотим оптимизировать весь вычислительный стек», — говорит Дэниел Манковиц, штатный научный сотрудник Deepmind, возглавлявший проект по сортировке. Манковиц говорит, что AlphaDev уже улучшил алгоритмы не только для сортировки, но и для других базовых задач, таких как хеширование.

«Я считаю эту работу невероятно интересной, — говорит Армандо Солар-Лезама, эксперт по синтезу программ в Массачусетском технологическом институте, который не принимал участия в исследовании. Полезно, чтобы ИИ придумал новый алгоритм сортировки, но гораздо важнее создать ИИ, который научится писать самый современный код для различных задач, говорит он. Это означает, что AlphaDev начал изучать нечто более фундаментальное в искусстве написания кода.

Конечно, это связано со значительными ограничениями. «Это крошечные, крошечные программы, — добавляет он, — в общей сложности не более нескольких десятков инструкций в ассемблерном коде. Но эти крошечные программы часто представляют собой значительные узкие места в производительности компьютера, будучи оптимизированными настолько, насколько люди могут их понять». В целом, новые алгоритмы сортировки AlphaDev на C++ на 1.7% эффективнее предыдущих методов при сортировке длинных последовательностей чисел и на 70% быстрее для последовательностей из пяти элементов. По словам Манковица, при масштабировании эти улучшения возрастают. С тех пор как код, написанный ИИ, был представлен в Libc++, крупной библиотеке с открытым исходным кодом для C++, по его оценкам, алгоритмы использовались триллионы раз в день.

Эти улучшения были достигнуты благодаря технике, называемой обучением с подкреплением, которая используется для того, чтобы помочь ИИ Deepmind освоить такие игры, как шахматы и го. Этот тип ИИ учится на практике. Он работает, рассматривая поставленную задачу, например, написание программы на ассемблере, как игру, в которой ИИ получает вознаграждение за умные ходы, повышающие эффективность программы. Со временем система работает над тем, чтобы максимизировать это вознаграждение, что приводит к созданию выигрышной стратегии игры в го или более быстрой программы сборки. Это отличается от того типа ИИ, который используется в больших языковых моделях, таких как GPT-4, которые опираются на огромные объемы данных, чтобы узнать, как писать слова или код. Это отлично подходит для создания текста, который отражает тон Интернета, или для создания общих сегментов кода. Но это не так хорошо для создания новых, самых современных решений проблем программирования, с которыми ИИ никогда раньше не сталкивался.

Как и игра в шахматы или го, написание ассемблерного кода — это сложная, открытая задача, с множеством потенциальных ходов и множеством способов ошибиться. Современные языки программирования, такие как C++ или Python, маскируют тонкости перемещения данных с помощью коротких команд, которые отражают человеческий язык. В 1950-х годах, когда появились такие «высокоуровневые» языки, некоторые считали, что проблема программирования в принципе решена. До тех пор программирование было, по сути, просто копанием в ассемблере — настолько, что Fortran, один из первых языков высокого уровня, изначально продавался как «автоматическая система кодирования Fortran», потому что его команды всегда переводились в рабочий код на ассемблере. «Fortran должен был писать код лучше, чем человек, и без ошибок», — говорит Солар-Лезама. «Сегодня это звучит смешно. Но это было правдой».

Совершенствование таких языков, как C++ или Fortran, по-прежнему часто требует доработки базы на ассемблере — поиска способов заставить работать язык быстрее, обычно за счет сокращения лишних шагов. Поскольку в ассемблере отсутствуют формальные структуры и абстракции программирования более высокого уровня, и поскольку одна ошибка может привести к поломке алгоритма, игра, в которую должен играть ИИ, не приносит удовольствия. «Он будет терпеть неудачи снова, снова и снова», — объясняет Солар-Лезама.

Инновация AlphaDev заключается в том, что она улучшает то, как структура работающей ассемблерной программы представляется в ИИ коде. Это позволяет его системе вознаграждения лучше сузить круг возможностей. ИИ становится лучше и быстрее.

На высоком уровне решение ИИ по сортировке выглядит знакомым. Есть много способов расположить несколько чисел в порядке возрастания. Но ИИ удалось сэкономить несколько инструкций в последовательности, используя некоторые нетрадиционные инструкции — такие, которые человек, вероятно, не стал бы пробовать. Манковиц сравнивает эти действия с ходом 37, печально известным ходом, который AlphaGo сыграла в 2016 году в выставочном матче против гроссмейстера Ли Седоля. Этот ход был настолько странным, что наблюдатели сначала решили, что компьютер провалил матч. Но в итоге этот ход стал решающим для победы компьютера, и с тех пор он изменил подход к игре.

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

Манковиц признает, что текущие программы, которые может создавать AlphaDev, невелики, и что, вероятно, потребуются новые прорывы в развитии ИИ, чтобы генерировать более крупные и сложные алгоритмы, превосходящие лучшие попытки человека. Но для таких экспертов по генерации кода, как Солар-Лезама, это исследование — важный шаг на пути к более обобщенному ИИ-программированию, который заставил его задуматься о Фортране и его системе «автоматического программирования». Вытеснила ли она программистов из бизнеса? Ни в малейшей степени. Изменило ли это то, что значит быть программистом? Полностью.

Источник