Исследовать
В поисках «функций», записанных в компьютерном коде, FunSearch сделала первые открытия в открытых задачах математических наук с использованием LLM.
Большие языковые модели (LLM) являются полезными помощниками: они превосходно комбинируют концепции и могут читать, писать и программировать, помогая людям решать проблемы. Но смогут ли они открыть совершенно новые знания?
Поскольку было показано, что LLM «галлюцинируют» фактически неверную информацию, их использование для создания проверяемых правильных открытий является сложной задачей. Но что, если бы мы могли использовать творческий потенциал студентов-магистров права, выявляя и развивая только их лучшие идеи?
Сегодня в статья, опубликованная в журнале Nature, мы представляем FunSearch — метод поиска новых решений в области математики и информатики. FunSearch работает путем объединения предварительно обученного LLM, целью которого является предоставление творческих решений в форме компьютерного кода, с автоматическим «оценщиком», который защищает от галлюцинаций и неправильных идей. Путем повторения этих двух компонентов первоначальные решения «превращаются» в новые знания. Система ищет «функции», записанные в компьютерном коде; отсюда и название FunSearch.
Эта работа представляет собой первый случай, когда было сделано новое открытие для решения открытых проблем в области науки или математики с использованием LLM. FunSearch обнаружила новые решения проблемы набора ограничений, давней открытой проблемы в математике. Кроме того, чтобы продемонстрировать практическую полезность FunSearch, мы использовали его для обнаружения более эффективных алгоритмов решения проблемы «упаковки мусора», которая имеет повсеместное применение, например, для повышения эффективности центров обработки данных.
Научный прогресс всегда опирался на способность делиться новыми знаниями. Что делает FunSearch особенно мощным научным инструментом, так это то, что он выводит программы, раскрывающие как его решения конструируются, а не просто сами решения. Мы надеемся, что это может вдохновить ученых, использующих FunSearch, на дальнейшее понимание, стимулируя благотворный цикл улучшений и открытий.
Содействие открытиям посредством эволюции с помощью языковых моделей
FunSearch использует эволюционный метод, основанный на LLM, который продвигает и развивает идеи, получившие самые высокие оценки. Эти идеи выражаются в виде компьютерных программ, поэтому их можно запускать и оценивать автоматически. Сначала пользователь пишет описание проблемы в виде кода. Это описание включает процедуру оценки программ и начальную программу, используемую для инициализации пула программ.
FunSearch — итеративная процедура; на каждой итерации система выбирает некоторые программы из текущего пула программ, которые передаются в LLM. LLM творчески опирается на них и создает новые программы, которые автоматически оцениваются. Лучшие из них добавляются обратно в пул существующих программ, создавая цикл самосовершенствования. FunSearch использует Google PaLM 2.но он совместим с другими LLM, обученными на коде.
Открытие новых математических знаний и алгоритмов в различных областях — общеизвестно сложная задача, которая во многом не под силу самым продвинутым системам искусственного интеллекта. Чтобы решить такие сложные проблемы с помощью FunSearch, мы представили несколько ключевых компонентов. Вместо того, чтобы начинать с нуля, мы начинаем эволюционный процесс с общих знаний о проблеме и позволяем FunSearch сосредоточиться на поиске наиболее важных идей для достижения новых открытий. Кроме того, наш эволюционный процесс использует стратегию улучшения разнообразия идей, чтобы избежать застоя. Наконец, мы запускаем эволюционный процесс параллельно, чтобы повысить эффективность системы.
Открывая новые горизонты в математике
Сначала мы обращаемся к проблема с набором шапок, открытый вызов, который десятилетиями раздражал математиков во многих областях исследований. Известный математик Теренс Тао однажды назвал это своей любимый открытый вопрос. Мы сотрудничали с Джорданом Элленбергом, профессором математики Университета Висконсин-Мэдисон и автором важный прорыв в проблеме ограничения ограничений.
Задача состоит в нахождении наибольшего набора точек (называемого набор кепок) в многомерной сетке, где никакие три точки не лежат на прямой. Эта проблема важна, поскольку она служит моделью для других задач экстремальной комбинаторики — исследования того, насколько большим или маленьким может быть набор чисел, графиков или других объектов. Грубые вычислительные подходы к этой проблеме не работают – количество рассматриваемых возможностей быстро становится больше, чем количество атомов во Вселенной.
FunSearch разработала решения в виде программ, которые в некоторых местах обнаружили самые большие наборы крышек, когда-либо найденные. Это представляет собой наибольшее увеличение по размеру наборов кепок за последние 20 лет. Более того, FunSearch превзошла по производительности самые современные вычислительные решения, поскольку масштабы этой задачи значительно превышают их текущие возможности.
Эти результаты показывают, что метод FunSearch может вывести нас за пределы установленных результатов в решении сложных комбинаторных задач, где интуицию может быть сложно развить. Мы ожидаем, что этот подход сыграет роль в новых открытиях аналогичных теоретических проблем комбинаторики, а в будущем он может открыть новые возможности в таких областях, как теория связи.
FunSearch предпочитает краткие и понятные человеку программы.
Хотя открытие новых математических знаний само по себе важно, подход FunSearch предлагает дополнительное преимущество по сравнению с традиционными методами компьютерного поиска. Это потому, что FunSearch — это не черный ящик, который просто генерирует решения проблем. Вместо этого он генерирует программы, описывающие как такие решения были найдены. Этот подход «покажи свою работу» — это то, как обычно работают ученые: новые открытия или явления объясняются посредством процесса, используемого для их создания.
FunSearch предпочитает находить решения, представленные очень компактными программами — решениями с низкой колмогоровской сложностью†. Короткие программы могут описывать очень большие объекты, что позволяет FunSearch масштабироваться для решения больших задач, связанных с «иголкой в стоге сена». Более того, это облегчает понимание результатов программы FunSearch исследователями. Элленберг сказал: «FunSearch предлагает совершенно новый механизм разработки стратегий атаки. Решения, созданные FunSearch, концептуально гораздо богаче, чем простой список чисел. Когда я их изучаю, я чему-то учусь».
Более того, интерпретируемость программ FunSearch может дать исследователям ценную информацию. Когда мы использовали FunSearch, мы заметили, например, интригующую симметрию в коде некоторых из его результатов с высокими оценками. Это дало нам новое понимание проблемы, и мы использовали это понимание для уточнения проблемы, представленной в FunSearch, что привело к еще лучшим решениям. Мы рассматриваем это как образец совместной процедуры между людьми и FunSearch для решения многих математических задач.
Решение общеизвестно сложной задачи в области вычислений
Воодушевленные успехом в решении теоретической задачи о максимальном наборе значений, мы решили изучить гибкость FunSearch, применив ее к важной практической задаче в области информатики. Задача «упаковки корзин» заключается в том, как упаковать предметы разного размера в наименьшее количество корзин. Он лежит в основе многих реальных проблем: от загрузки контейнеров с элементами до распределения вычислительных заданий в центрах обработки данных для минимизации затрат.
Проблема онлайн-упаковки корзин обычно решается с использованием алгоритмических эмпирических правил (эвристики), основанных на человеческом опыте. Но найти набор правил для каждой конкретной ситуации – с разными размерами, сроками или возможностями – может оказаться непростой задачей. Несмотря на то, что проблема с набором ограничений сильно отличается от проблемы с набором ограничений, настроить FunSearch для этой задачи было легко. FunSearch предоставила автоматически адаптируемую программу (адаптирующуюся к специфике данных), которая превзошла общепринятые эвристики – использовала меньшее количество корзин для упаковки того же количества предметов.
Сложные комбинаторные задачи, такие как онлайн-упаковка корзин, можно решать с помощью других подходов ИИ, таких как нейронные сети и обучение с подкреплением. Такие подходы также доказали свою эффективность, но для их реализации могут потребоваться значительные ресурсы. FunSearch, с другой стороны, выдает код, который можно легко проверить и развернуть, а это означает, что ее решения потенциально могут быть внедрены в различные реальные промышленные системы, что принесет быстрые выгоды.
Открытия, основанные на LLM, для науки и не только
FunSearch демонстрирует, что если мы защитимся от галлюцинаций студентов-магистров, то мощь этих моделей можно будет использовать не только для создания новых математических открытий, но и для выявления потенциально эффективных решений важных проблем реального мира.
Мы полагаем, что для многих проблем в науке и промышленности – как давних, так и новых – создание эффективных и адаптированных алгоритмов с использованием подходов, основанных на LLM, станет обычной практикой.
Действительно, это только начало. FunSearch будет совершенствоваться как естественное следствие более широкого прогресса LLM, и мы также будем работать над расширением его возможностей для решения различных насущных научных и инженерных проблем общества.