AutoNumerics-Zero: Automated Discovery of State-of-the-Art Mathematical Functions [2023] - ещё одно AI-открытие уходящего года

Продолжаем тему оптимизации программ. Почти одновременно с FunSearch вышла другая работа от Deepmind, правда, не применяющая LLM, и поэтому попавшая только в Just Links. Идеологически она похожа на AutoML-Zero, про который я уже тоже писал пост.

Итак, мы умеем легко и быстро производить на компьютере 4 базовые арифметические операции. Однако, "трансцендентные" функции, например, экспоненту, нельзя легко посчитать. Компьютер их считает приближённо, например, с помощью ряда Тейлора. При этом, нам достаточно уметь приближать её на промежутке [0;1], т.к. в целую степень мы умеем легко возводить и таким образом получить любую степень.

Итак, задача - найти как можно более короткую / быструю программу, вычисляющую экспоненту на отрезке с заданной точностью. Авторы представляют программу в виде графа вычислений (см. картинку). Вершинами является вход x, выход f, константы и математические операции, в которые по направленным рёбрам попадают входные данные.

Генетический алгоритм поддерживает популяцию графов, случайно добавляет мутации в них - добавление вершин, удаление, замена ребра и т.д. Оптимизируется одновременно точность и скорость (кол-во операций или время исполнения). Так как у нас 2 важных критерия отбора, используется специальный алгоритм сортировки популяции, выбирающий программы, сбалансированные по-разному с точки зрения критериев.

В результате, алгоритм не оставляет камня на камне от бейзлайнов, созданных приматами. Количество операций сокращается примерно в 2 раза, но это не самое крутое. Алгоритм подбирает функции так, чтобы компилятор оптимизировал их наиболее выгодно, в итоге скорость возрастает в >3 раза.

И вновь кожанные мешки показывают свою несостоятельность в сложных многослойных задачах, которые нельзя разбить на изолированные кусочки. End-to-end алгоритмическая оптимизация не оставляет нам никаких шансов.

@knowledge_accumulator