По данным Google DeepMind, большинство вычислительных алгоритмов достигли той стадии, когда человеческие эксперты не могут оптимизировать их дальше. Эту проблему может решить AlphaDev, который обнаруживает алгоритмы сортировки. По мнению компании, это революция в основах вычислений. Ученые утверждают, что открыли более быстрые алгоритмы сортировки и хэширования, которые считаются важными процессами, ежедневно используемыми разработчиками по всему миру для сортировки, хранения и поиска данных. В статье расскажем об алгоритме AlphaDev, вспомним про AlphaZero и покажем, что об этом думает ИТ-сообщество.
Возможности AlphaDev
В научном журнале Nature опубликована статья, в которой DeepMind утверждает, что недавно открытый алгоритм AlphaDev достигает 70% увеличения эффективности сортировки коротких последовательностей элементов и приблизительно 1,7% для последовательностей, превышающих 250 000 элементов, по сравнению с алгоритмами из библиотеки C++. Следовательно, когда пользователь отправляет поисковый запрос, алгоритм AlphaDev способствует более быстрой сортировке результатов, что приводит к значительной экономии времени и энергии при использовании в больших масштабах.
Система также обнаружила более быстрый алгоритм хеширования информации, что привело к повышению эффективности на 30% при применении функций хеширования в диапазоне от 9 до 16 байт в центрах обработки данных.
Компания также объявила о своем намерении сделать новые алгоритмы доступными через стандартную библиотеку сортировки LLVM libc++. Примечательно, что это обновление представляет собой первый пересмотр этого раздела библиотеки сортировки более чем за десятилетие и первоначальное включение алгоритма, разработанного с помощью обучения с подкреплением.
Вернемся к истокам: как появился уникальный подход Deepmind к поиску более быстрых алгоритмов
Хотя оптимизация низкоуровневых инструкций оказалась чрезвычайно эффективной, компания заявила, что активно изучает потенциал AlphaDev для оптимизации алгоритмов непосредственно на языках высокого уровня, таких как C++, что было бы еще более ценным для разработчиков.
AlphaDev — это на самом деле специализированная версия AlphaZero. И тут стоит вспомнить про AlphaTensor. Эта система искусственного интеллекта от компании DeepMind нашла ускоренный способ умножения матриц, причем новых решений для которых не получалось найти более 50 лет.
Что сделали в DeepMind: взяли версию AlphaZero, названную AlphaTensor, и обучили ее играть не в AlphaGo, а в игру под названием TensorGame. Игра представляет собой задачу на умножение матриц, которую нужно решить, причем каждый ход — следующий шаг в решении задачи. Таким образом, серия ходов, сделанных в игре, представляет собой алгоритм перемножения этих матриц.
ИИ награждали за победу в игре за минимальное количество ходов. Вместо того, чтобы изучать выигрышные последовательности ходов в шахматах, AlphaTensor получал наилучшие последовательности шагов при умножении матриц.
Так AlphaTensor открыл способ умножения двух матриц 4х4, который работает быстрее, чем метод, разработанный в 1969 году немецким математиком Ф. Штрассеном, который с тех пор никто не мог улучшить. Учебный метод для первокурсников состоит из 64 шагов, у Ф. Штрассена — 49 шагов, а AlphaTensor нашел способ сделать всего 47 шагов.
Это уже не оптимизация алгоритмов или вычислительных методов, а, можно сказать, оптимизация мышления. Математика — это искусство красивых решений и формул, и ИИ в этом обогнал человека. ИИ определенно превосходит математиков в задаче оптимизации алгоритмов перемножения матриц. Теперь интересно, как ИИ сможет оптимизировать более высокоуровневые алгоритмы. Алгоритмы сортировки, по своей сути, способствуют систематическому расположению элементов в определенном порядке. Они служат основой обучения.
Что думают программисты на этот счет
После пресс-релиза от DeepMind про оптимизацию сортировки развернулась дискуссия на Ycombinator News между программистами. Некоторые отмечают, что в статье описаны очевидные вещи, и на самом деле другие компании уже используют такие приемы, но просто не хотели раскрывать свои карты. И вклад Google и DeepMind в том, что они раскрыли информацию, то есть появился примерный базовый уровень, с которым можно сравнить результаты. Также есть мнение, что это сделали для того, чтобы получить новые средства для дальнейших исследований.
Некоторые комментаторы критично относятся к заявлениям Deepmind о том, что «раскрыт новый алгоритм сортировки», а также к озвученным фактам про «до 70% быстрее» и «первое изменение за десятилетие». Они считают, что исследование было полезным, но его результаты специально раздуты. Чего на самом деле достигли исследователи, так это просто хорошо сгенерированный код в автоматическом режиме.
«Тот факт, что люди могут сделать то же самое вручную, на самом деле не имеет значения. Вклад заключается в том, что их метод вывел это улучшение автоматически, и именно в этом заключается его влияние. Никого не волнует, что человек может сделать сортировку на 2% быстрее, но если это может сделать программа, это вдруг становится интересным, поскольку это предполагает, что аналогичный подход может быть применен ко многим другим процедурам», — отметил пользователь с ником saiojd.
Любой, кто занимается базовыми алгоритмическими вещами в CS, сталкивался с алгоритмами сортировки, их вариациями, сортировочными сетями и пр. Уже существуют супероптимизаторы, которые используют алгоритмы для поиска наиболее оптимальной последовательности кода для небольших, легко проверяемых задач. Это тоже в некотором роде форма обучения с подкреплением.