- 20,980
- 46
- 8 Ноя 2022
AlphaEvolve доказал, что машины могут участвовать в фундаментальной науке.
Google DeepMind представила систему AlphaEvolve, которая использует большие языковые модели для поиска и проверки новых комбинаторных структур. Эти структуры позволяют продвигать исследования в области теоретической информатики, в частности в сложности приближённых вычислений.
Исследователи отмечают, что современные языковые модели уже показывали сильные результаты в математике и программировании, однако в открытии новых теорем они до сих пор почти не участвовали. Главная проблема здесь — абсолютная корректность, которая необходима в математике. Любое утверждение должно быть либо формально доказано, либо проверено экспертом.
В статье «Reinforced Generation of Combinatorial Structures: Applications to Complexity Theory» авторы описывают, как AlphaEvolve помогает находить новые конструкции, которые затем автоматически проверяются компьютером. Система работает по принципу эволюции: генерирует множество программных фрагментов, отбирает наиболее удачные и постепенно улучшает их. Такой подход позволил добиться прогресса в двух направлениях — в задаче MAX-4-CUT и в исследовании свойств случайных графов.
Для задачи MAX-4-CUT ранее было известно, что её невозможно приближённо решить лучше, чем с коэффициентом 0,9883. AlphaEvolve нашла новый так называемый «гаджет» — специальную конструкцию с 19 переменными и сложной системой весов. Это позволило улучшить результат до 0,987. В области теории приближений такие шаги считаются значительным достижением, поскольку каждый новый барьер преодолевается с трудом.
Кроме того, система исследовала среднюю сложность задач на случайных графах, где ключевую роль играют графы Рамануджана. AlphaEvolve смогла находить такие графы на сотни вершин — значительно больше, чем удавалось ранее. Это помогло уточнить границы вычислительной трудности и приблизить нижние и верхние оценки почти вплотную друг к другу.
Главная особенность работы в том, что все найденные конструкции были проверены на корректность, причём не только ускоренными методами, но и исходным «грубым» алгоритмом. Это гарантировало надёжность результатов.
Авторы подчёркивают, что речь пока не идёт о том, что ИИ способен самостоятельно доказывать новые теоремы. Но уже сейчас такие системы способны создавать элементы доказательств, которые затем «поднимаются» в более общие универсальные результаты. В будущем ключевой проблемой станет именно проверка правильности, поскольку объём вычислений для этого будет расти вместе со сложностью задач.
Google DeepMind представила систему AlphaEvolve, которая использует большие языковые модели для поиска и проверки новых комбинаторных структур. Эти структуры позволяют продвигать исследования в области теоретической информатики, в частности в сложности приближённых вычислений.
Исследователи отмечают, что современные языковые модели уже показывали сильные результаты в математике и программировании, однако в открытии новых теорем они до сих пор почти не участвовали. Главная проблема здесь — абсолютная корректность, которая необходима в математике. Любое утверждение должно быть либо формально доказано, либо проверено экспертом.
В статье «Reinforced Generation of Combinatorial Structures: Applications to Complexity Theory» авторы описывают, как AlphaEvolve помогает находить новые конструкции, которые затем автоматически проверяются компьютером. Система работает по принципу эволюции: генерирует множество программных фрагментов, отбирает наиболее удачные и постепенно улучшает их. Такой подход позволил добиться прогресса в двух направлениях — в задаче MAX-4-CUT и в исследовании свойств случайных графов.
Для задачи MAX-4-CUT ранее было известно, что её невозможно приближённо решить лучше, чем с коэффициентом 0,9883. AlphaEvolve нашла новый так называемый «гаджет» — специальную конструкцию с 19 переменными и сложной системой весов. Это позволило улучшить результат до 0,987. В области теории приближений такие шаги считаются значительным достижением, поскольку каждый новый барьер преодолевается с трудом.
Кроме того, система исследовала среднюю сложность задач на случайных графах, где ключевую роль играют графы Рамануджана. AlphaEvolve смогла находить такие графы на сотни вершин — значительно больше, чем удавалось ранее. Это помогло уточнить границы вычислительной трудности и приблизить нижние и верхние оценки почти вплотную друг к другу.
Главная особенность работы в том, что все найденные конструкции были проверены на корректность, причём не только ускоренными методами, но и исходным «грубым» алгоритмом. Это гарантировало надёжность результатов.
Авторы подчёркивают, что речь пока не идёт о том, что ИИ способен самостоятельно доказывать новые теоремы. Но уже сейчас такие системы способны создавать элементы доказательств, которые затем «поднимаются» в более общие универсальные результаты. В будущем ключевой проблемой станет именно проверка правильности, поскольку объём вычислений для этого будет расти вместе со сложностью задач.
- Источник новости
- www.securitylab.ru
