Исследователи проанализировали вычислительную сложность научного поиска с помощью символьной регрессии, используя аппарат PAC-обучения. Авторы доказали, что поиск закономерностей в виде композиционных деревьев функций из ограниченного набора операторов является статистически разрешимым. Работа устанавливает теоретические границы выборки, необходимые для эффективного восстановления сложных математических выражений, описывающих физические или научные явления.
Традиционно символьная регрессия считалась трудновыполнимой задачей из-за комбинаторного взрыва пространства гипотез при увеличении глубины деревьев выражений. В данной работе предложен новый подход к оценке сложности, который позволяет формализовать процесс «открытия» формул. Исследование фокусируется на деревьях, построенных из гладких операторов, таких как сложение, умножение, синус и экспонента, что приближает методы машинного обучения к задачам автоматизированного вывода физических законов.
Результаты работы показывают, что при соблюдении определенных условий на структуру дерева функций задача становится PAC-обучаемой (Probably Approximately Correct). Это означает, что для достижения высокой точности аппроксимации данных требуется полиномиальное, а не экспоненциальное количество примеров. Полученные выводы помогают лучше понять ограничения алгоритмов символьной регрессии и открывают путь к созданию более надежных систем для автоматического поиска научных закономерностей в экспериментальных данных.
Ключевые факты
- Исследование опирается на теорию PAC-обучения (Probably Approximately Correct) для анализа сложности символьной регрессии.
- Рассматриваются композиционные деревья функций, состоящие из базовых операторов: сложения, умножения, синуса и экспоненты.
- Доказано, что при ограничении глубины и сложности деревьев задача поиска выражений становится статистически разрешимой.
- Работа снимает часть опасений о «комбинаторной неразрешимости» автоматизированного научного поиска, предлагая математические гарантии сходимости алгоритмов.