Модель ИИ FunSearch сделала математическое открытие
Команда Google DeepMind впервые использовала большую языковую модель (LLM) для решения важной нерешенной проблемы чистой математики.
Разработанная учеными модель ИИ, получившая название FunSearch, работает с Codey — версией LLM Google PaLM, специально обученной для программирования на языке программирования Python. FunSearch построила более эффективный алгоритм, чем удавалось математикам, для поиска специальной последовательности, известной как оценка «шапочного множества».
Большие языковые модели имеют сегодня не слишком хорошую репутацию. Они часто выдумывают ответы — галлюцинируют (о галлюцинациях ИИ мы писали). Google DeepMind разработала новый инструмент под названием FunSearch, который может поправить ситуацию. Работа показывает, что большие языковые модели действительно могут делать открытия, если научатся оптимизировать свои ответы и выбрасывать большую часть того, что они придумали.
FunSearch названа так, потому что ищет математические функции (function), а не потому, что это fun (хотя…). Она продолжает серию работ DeepMind, посвященную разным видам ускорения и оптимизации алгоритмов. Сначала DeepMind разработана систему AlphaTensor, которая ускоряет перемножение матриц. Это важнейший момент большинства вычислений, например, при обработке компьютерной графике. Затем была разработана система AlphaDev — способ ускорить ключевые алгоритмы, используемые триллионы раз в день (об AlphaDev мы рассказывали).
Однако эти инструменты не использовали большие языковые модели. Оба приложения были созданы на основе игрового искусственного интеллекта AlphaZero. AlphaTensor и AlphaDev решали математические задачи, рассматривая их так, как если бы они были игрой в го или шахматы. Но круг задач, которые решают эти системы, довольно ограничен. Бернардино Ромера-Паредес, исследователь компании, работавший и над AlphaTensor, и над FunSearch говорит: «AlphaTensor отлично справляется с умножением матриц, но, по сути, ничего больше не умеет». FunSearch использует другой подход.
Как ИИ ищет новые знания
FunSearch сочетает в себе LLM Codey, версию Google PaLM 2, которая настроена на создание компьютерного кода, с другими системами, которые умеют отклонять неправильные или бессмысленные ответы и выбирают эффективные.
Исследователи начали с наброска проблемы, которую они хотели решить с помощью Python. Но они исключили из программы строки, описывающие само решение. Была поставлена проблема, а найти решение ученые предложили Codey.
Затем к работе подключился второй алгоритм: он проверял и оценивал код, созданный Codey. Работа происходит по шагам: лучшие предложения — даже если они еще не верны — сохраняются и возвращаются Codey, и система пытается исправить и оптимизировать программу. «Многие фрагменты кода будут бессмысленными, некоторые — интересными, а некоторые — по-настоящему вдохновляющими», — говорит соавтор работы Пушмит Кохли, вице-президент по исследованиям Google DeepMind. — «Вы берете самые лучшие и говорите Codey: «Хорошо, возьми это и повтори»».
Одним из главных критериев отбора наилучших вариантов является оценка колмогоровской сложности алгоритма: грубо говоря, если есть две программы, получающие близкие результаты, лучшей будет та, что короче.
После пары миллионов строк кода и нескольких десятков итераций всего процесса (это заняло несколько дней счета) FunSearch смог придумать код, который дал правильное и ранее неизвестное решение поиска «шапочного множества» (Сap set).
Процесс FunSearch. LLM показывают подборку лучших программ, которые он сгенерировал до сих пор (взятых из базы данных программ), и предлагают их улучшить. Программы, предложенные LLM, автоматически выполняются и оцениваются. Лучшие программы добавляются в базу данных для выбора в последующих циклах. Пользователь может в любой момент получить из базы данных программы, получившие наибольшее количество баллов.
Нерешенная задача о «шапочном множестве»
Представьте себе, что у вас есть квадрат 3х3 на бумаге в клеточку. Какое максимальное число точек можно разместить в этом квадрате, чтобы никакие три из них на лежали на одной прямой? Здесь ответ достаточно легко найти — максимум 4. Но проблема состоит в том, чтобы найти максимальное множество точек (это и есть «шапочное множество») для куба любой размерности. Уже для трехмерного куба — 3х3х3 — ответ совершенно неочевиден. Он был получен в 1971 году: максимальное число точек, никакие из которых не лежат на одной прямой на трехмерном кубе равно 9. Для четырех измерений — это число равно 20. Найти его еще труднее. И чем больше размерность, тем труднее строить «шапочные множества» или оценивать их объем.
Шапочное множество для размерности 2 (слева) и 3 (справа).
Алгоритм, который вычисляет количество точек в шапочном множестве размерности N, построил Джордан Элленберг в 2019 году. Алгоритм имеет экспоненциальную сложность, то есть число шагов при поиске шапочного множества размерности N растет очень быстро. Фактически для больших размерностей задача ставится нерешаемой. Но можно попытаться отыскать оценочный алгоритм, который за гораздо меньшее время покажет пусть и неточную, по близкую оценку верхней границы количества точек в шапочном множестве размерности N. Вот этим и занялась FunSearch.
Математики любят эту задачу и много ей занимаются не только потому, что она трудная и красивая. Система перемножения матриц AlphaTensor, разработанная DeepMind, и имеющая огромное количество приложений, тесно связана с шапочной проблемой. Математики доказали, что количество точек в шапочном множестве размерности N показывает, где оптимизацию алгоритма перемножения матриц нужно останавливать, потому его уже нельзя улучшить. Это может сэкономить большие вычислительные ресурсы при работе AlphaTensor.
Так что поиск оценочного быстрого алгоритма для шапочного множества — полезен даже в чисто прикладном смысле.
И FunSearch такой оценочный алгоритм построила. И он эффективнее всех алгоритмов, построенных людьми. DeepMind считает, что это — математическое открытие.
Теренс Тао из Калифорнийского университета в Лос-Анджелесе, получивший множество высших наград в области математики, в том числе медаль Филдса, говорит, что «шапочная проблема»: «возможно, моя любимая открытая проблема».
Люди и машины говорят друг с другом на Python
Ключевое преимущество FunSearch перед AlphaTensor или AlphaDev заключается в том, что FunSearch можно использовать для поиска решений широкого круга проблем. Например, систему использовали для решения задачи упаковки в контейнер.
Слева упаковка цветных прямоугольников в серые контейнеры, выполненная лучшим эвристическим алгоритмом, справа — упаковка, найденная FunSearch. Ей понадобилось на один контейнер меньше.
Это задача важна для целого ряда приложений в области информатики, от управления центрами обработки данных до электронной коммерции. FunSearch нашла способ решить эту проблему быстрее, чем те, которые придумал человек.
Система может создать код для решения разных проблем. И что еще важнее результаты FunSearch может понять человек. Сегодня многие системы ИИ просто выдают ответ — иногда приемлемый, иногда отличный, иногда такой, до которого человек никогда бы не додумался. Но как ИИ пришел к этому ответу — непонятно. А вот FunSearch выдает программу на Python, которую при некотором усилии человек понять может.
Поговорим?
Разработчики FunSearch пишут в препринте статьи: «Научный прогресс всегда опирался на способность делиться новыми знаниями. Что делает FunSearch особенно мощным научным инструментом, так это то, что он выдает программы, которые показывают, как построены его решения, а не только результаты. Мы надеемся, что это вдохновит ученых, использующих FunSearch, на дальнейшие открытия».
Математики «все еще пытаются найти лучший способ включить большие языковые модели в исследовательский рабочий процесс таким образом, чтобы использовать их возможности и одновременно смягчить их недостатки», — говорит Тао. — «FunSearch, безусловно, указывает на один из возможных путей вперед».
Источник: www.techinsider.ru
