АльфаДев
| Разработчик(и) | ДипМайнд |
|---|---|
| Тип | Обучение с подкреплением |
| Часть серии о |
| Искусственный интеллект |
|---|
 |
AlphaDev — это система искусственного интеллекта , разработанная Google DeepMind для обнаружения усовершенствованных алгоритмов информатики с использованием обучения с подкреплением . AlphaDev основан на AlphaZero , системе, которая позволяет играть в шахматы , сёги и го самостоятельно . AlphaDev применяет тот же подход для поиска более быстрых алгоритмов для фундаментальных задач, таких как сортировка и хеширование . [1] [2] [3]
Разработка
[ редактировать ]статью, в 7 июня 2023 года Google DeepMind опубликовал в журнале Nature которой представил AlphaDev, в которой были обнаружены новые алгоритмы, которые превосходят современные методы для алгоритмов мелкой сортировки. [1] Например, AlphaDev нашла более быструю последовательность ассемблера для сортировки последовательностей из 5 элементов. [4] После углубленного анализа алгоритмов AlphaDev обнаружила две уникальные последовательности инструкций ассемблера, называемые ходами замены и копирования AlphaDev, которые позволяют избежать использования одной ассемблерной инструкции при каждом их применении. [1] [3] Для алгоритмов сортировки переменных AlphaDev обнаружила принципиально иные структуры алгоритмов. Например, для VarSort4 (сортировка до 4 элементов) AlphaDev обнаружил алгоритм на 29 ассемблерных инструкций короче, чем человеческий тест. [1] AlphaDev также улучшила скорость алгоритмов хеширования в некоторых случаях до 30%. [2]
В январе 2022 года Google DeepMind представила свои новые алгоритмы сортировки организации, управляющей C++ , одним из самых популярных языков программирования в мире, и после независимой проверки алгоритмы AlphaDev были добавлены в библиотеку. [5] Это было первое изменение в стандартной библиотеки C++ алгоритмах сортировки за более чем десятилетие и первое обновление, включающее алгоритм, обнаруженный с помощью ИИ. [5] В январе 2023 года DeepMind также добавила свой алгоритм хеширования для входных данных от 9 до 16 байт в Abseil, коллекцию готовых алгоритмов C++ с открытым исходным кодом, которые может использовать любой, кто пишет код на C++. [6] [5] По оценкам Google, эти два алгоритма используются триллионы раз каждый день. [7]
Дизайн
[ редактировать ]AlphaDev построен на основе AlphaZero, модели обучения с подкреплением, которую DeepMind обучила для освоения таких игр, как го и шахматы. [5] Прорыв компании заключался в том, что она решила проблему поиска более быстрого алгоритма как игру, а затем обучила свой ИИ победе в ней. [2] AlphaDev играет в однопользовательскую игру, цель которой — итеративно построить алгоритм на языке ассемблера, который будет одновременно быстрым и правильным. [1] AlphaDev использует нейронную сеть для поиска оптимальных ходов и учится на собственном опыте и синтетических демонстрациях. [1]
AlphaDev демонстрирует потенциал ИИ для развития основ вычислений и оптимизации кода по различным критериям. Google DeepMind надеется, что AlphaDev вдохновит на дальнейшие исследования по использованию ИИ для открытия новых алгоритмов и улучшения существующих. [2]
Алгоритм
[ редактировать ]Основной алгоритм обучения в AlphaDev является расширением AlphaZero .
Кодирование ассемблерного программирования в игру
[ редактировать ]Чтобы использовать AlphaZero при программировании на ассемблере, авторы создали на основе Transformer векторное представление ассемблерных программ , предназначенное для отражения их базовой структуры. [1] Это конечное представление позволяет нейронной сети играть в программирование на ассемблере как в игру с конечным числом возможных ходов (например, в Го).
В представлении используются следующие компоненты:
- Сеть Transformer для кодирования кодов операций сборки преобразуется в горячее кодирование и объединяется для формирования необработанной входной последовательности.
- Многослойная сеть перцептрона , которая кодирует «состояние процессора», то есть состояния каждого регистра и ячейки памяти для заданного набора входов.
Игра в игру
[ редактировать ]игры Состояние — это ассемблерная программа, сгенерированная до данного момента.
Игровой ход — это дополнительная инструкция, добавляемая к текущей ассемблерной программе.
в игре Награда зависит от корректности и задержки программы сборки. Чтобы снизить затраты, AlphaDev вычисляет фактическую измеренную задержку только для менее чем 0,002% созданных программ, поскольку она не оценивает задержку в процессе поиска. Вместо этого он использует две функции, которые оценивают правильность и задержку путем обучения с учителем с использованием реальных измеренных значений правильности и задержки.
Результат
[ редактировать ]Хеширование
[ редактировать ]AlphaDev разработала алгоритмы хеширования для входных данных от 9 до 16 байт для Abseil, коллекции готовых алгоритмов C++ с открытым исходным кодом. [8]
Стандартная библиотека сортировки LLVM
[ редактировать ]AlphaDev обнаружила новые алгоритмы сортировки, которые привели к улучшению библиотеки сортировки libc++ LLVM на 70 % для более коротких последовательностей и примерно на 1,7 % для последовательностей, превышающих 250 000 элементов. Эти улучшения применимы к типам данных uint32, uint64 и float для архитектур ЦП ARMv8, Intel Skylake и AMD Zen 2. Условная сборка без ветвей AlphaDev и новый механизм подкачки способствовали повышению производительности. Обнаруженные алгоритмы были преобразованы из низкоуровневой сборки в C++ и официально включены в стандартную библиотеку сортировки libc++. [6]
Улучшена десериализация в protobuf.
[ редактировать ]AlphaDev изучил оптимизированную функцию десериализации VarInt в protobuf , [9] превосходя человеческий тест для однозначных входных данных примерно в три раза с точки зрения скорости. AlphaDev также обнаружила новый прием назначения VarInt, объединяющий две операции в одну инструкцию для экономии задержек.
Сравнение с логическим подходом ИИ
[ редактировать ]Производительность AlphaDev сравнивали со стохастической супероптимизацией. [10] логический подход ИИ. Последний работал как минимум с тем же количеством ресурсов и времени, что и AlphaDev. Результаты показали, что AlphaDev-S требуется непомерно много времени для непосредственной оптимизации задержки, поскольку задержку необходимо вычислять после каждой мутации. Таким образом, AlphaDev-S оптимизирует прокси-сервер задержки, в частности длину алгоритма, а затем, в конце обучения, выполняется поиск всех правильных программ, сгенерированных AlphaDev-S.
Ссылки
[ редактировать ]- ^ Jump up to: а б с д и ж г Манковиц, Дэниел Дж.; Мичи, Андреа; Жернов, Антон; Гельми, Марко; Сельви, Марко; Падурару, Космин; Леран, Эдуард; Икбал, Шарик; Леспио, Жан-Батист; Ахерн, Алекс; Коппе, Томас; Милликин, Кевин; Гаффни, Стивен; Эльстер, Софи; Брошир, Джексон; Гэмбл, Крис; Милан, Киран; Тунг, Роберт; Хван, Минджэ; Джемгил, Тайлан; Барекатаин, Мохаммадамин; Ли, Юцзя; Мандане, Амол; Юбер, Томас; Шритвизер, Джулиан; Хассабис, Демис; Кохли, Пушмит; Ридмиллер, Мартин; Виньялс, Ориол; Сильвер, Дэвид (2023). «Алгоритмы более быстрой сортировки обнаружены с помощью глубокого обучения с подкреплением» . Природа . 618 : 257–263. дои : 10.1038/s41586-023-06004-9 . ПМЦ 10247365 .
- ^ Jump up to: а б с д «AlphaDev открывает более быстрые алгоритмы сортировки» . Блог . Гугл ДипМайнд. 7 июня 2023 г. Архивировано из оригинала 20 июня 2023 г. Проверено 20 июня 2023 г.
- ^ Jump up to: а б Танни, Жюстин (20 июня 2023 г.). «Понимание алгоритма сортировки DeepMind» . Жюстин. лол . Архивировано из оригинала 18 июня 2023 г. Проверено 20 июня 2023 г.
- ^ Github — AlphaDev , DeepMind, 21 июня 2023 г. , получено 21 июня 2023 г.
- ^ Jump up to: а б с д Небеса, Уилл Дуглас (7 июня 2023 г.). «Игровой ИИ Google DeepMind только что нашел еще один способ ускорить кодирование» . Обзор технологий Массачусетского технологического института . Архивировано из оригинала 14 июня 2023 г. Проверено 20 июня 2023 г.
- ^ Jump up to: а б «⚙ D118029 Внедрение функций безветвевой сортировки для sort3, sort4 и sort5» . Reviews.llvm.org . Проверено 21 июня 2023 г.
- ^ Спаркс, Мэтью (7 июня 2023 г.). «Новый способ сортировки объектов DeepMind AI может ускорить глобальные вычисления» . Новый учёный . Проверено 20 июня 2024 г.
- ^ «Замените absl::Hash для входных данных от 9 до 16 байтов в соответствии с выводами AlphaZero, выполненными командой Abseil · abseil/abseil-cpp@74eeee2a» . Гитхаб . Проверено 24 июня 2023 г.
- ^ «Сериализация и десериализация буфера протокола VarInt» . protobuf.dev . Проверено 24 июня 2023 г.
- ^ Шкуфза, Эрик; Шарма, Рахул; Эйкен, Алекс (16 марта 2013 г.). «Стохастическая супероптимизация» . Новости компьютерной архитектуры ACM SIGARCH . 41 (1): 305–316. arXiv : 1211.0557 . дои : 10.1145/2490301.2451150 . ISSN 0163-5964 .
Внешние ссылки
[ редактировать ]- Понимание прорыва DeepMind AlphaDev в оптимизации алгоритмов сортировки
- Понимание алгоритма сортировки DeepMind
Дифференцируемые вычисления |
|---|
