Аннотация:
Существует серия результатов, показывающих, что для различных архитектур неглубоких нейронных сетей множество решаемых ими задач совпадает с классом схемной сложности TC⁰, который имеет удобные описания как в терминах логики, так и в терминах комбинаторных алгоритмов. Однако это не отвечает на вопрос о том, как найти набор параметров нейросети, решающий данную задачу. Более того, существование эффективного алгоритма обучения для всех задач из класса TC⁰ означало бы, например, что криптографический протокол RSA ненадёжен.
Мы определяем принципиально новый класс сложности BPC⁰, для которого не только сохраняется эквивалентность с неглубокими нейросетями (с дополнительным ограничением на нормы весов), но и существует полиномиальный алгоритм обучения. Для этого класса удаётся найти похожие описания в логических и комбинаторно-алгоритмических терминах. Также для каждой задачи из класса BPC⁰ существуют примеры нейросетей полиномиального размера с одним скрытым слоем, для которых сходится обучение методом стохастического градиентного спуска, но степень полинома для этой нейросети велика и зависит от глубины.
|
