Расчет VC-размерности нейронной сети

Если у меня есть некоторая фиксированная неповторяющаяся (DAG) топология (фиксированный набор узлов и ребер, но алгоритм обучения может варьировать вес по ребрам) сигмоидных нейронов с входными нейронами, которые могут принимать строки только в { - 1 , 1 } n в качестве входных данных и приводит к одному выходному сигналу (который выводит реальное значение, которое мы округляем до 1 или до -1, если это определенный фиксированный порог, отличный от 0). Есть ли быстрый способ вычислить (или приблизить) VC-размерность этой сети?$n$$\{-1,1\}^n$

Ноты

Я попросил немного более точную алгоритмическую переформулировку на CS.SE:

Эффективное вычисление или аппроксимация VC-измерения нейронной сети

Я наткнулся на ваш пост, когда искал общую формулу для расчета размеров VC в нейронных сетях, но, видимо, ее нет. По-видимому, у нас есть только мешанина разрозненных уравнений ВК, которые применяются только в определенных узких случаях. Внимание: я основываю это на старых исследованиях, которые я едва понимаю, на концепции VC Dimensions, о которой я только сейчас узнаю. Тем не менее, возможно, стоит просмотреть эту статью Питера Л. Бартлетта и Вольфганга Маасса 1на вычислимость размеров VC. Обратите внимание, как они идут на многое, чтобы получить формулы VC в 13 теоремах, но насколько разнообразны и многочисленны необходимые условия для каждой. Эти предварительные условия варьируются от количества операторов в функциях активации до разрешенных типов переходов, количества нейронов и их положений, битовой глубины ввода и т. Д .; Есть так много разрозненных «ошибок», что они делают формулы полезными только для определенных узких классов задач. Что еще хуже, они указывают в теоремах 5 и 8, что сигмоидальные функции активации особенно трудно рассчитать для показателей VC. На стр. 6-7 пишут:

«Хотя VC-размерность сетей с кусочно-полиномиальными функциями активации хорошо понятна, в большинстве приложений нейронных сетей используется функция логистической сигмоиды или радиальная базисная функция Гаусса. К сожалению, невозможно вычислить такие функции с использованием конечного числа арифметические операции, перечисленные в теореме 5. Однако Карпински и Макинтайр [Karpinski and Macintyre, 1997] расширили теорему 5, чтобы позволить вычисление экспонент. В доказательстве используются те же идеи, но оценка числа решений системы уравнений существенно сложнее.

Я также натолкнулся на эту статью с обнадеживающим названием «Ограничение VC-измерения для нейронных сетей: прогресс и перспективы». 2Много математики у меня над головой, и я не занимался этим достаточно долго, чтобы преодолеть недостаток навыков перевода, но я подозреваю, что он не предлагает никаких потрясающих решений, поскольку он предшествует второму изданию книги Бартлетт и Маасс, который цитирует более позднюю работу тех же авторов. Возможно, более поздние исследования, проведенные за последние 20 лет, улучшили вычисляемость размеров VC для нейронных сетей, но большинство ссылок, которые я нашел, датируются серединой 90-х годов; по-видимому, тогда была бурная работа по этому вопросу, которая с тех пор утихла. Если эти возможности не были расширены более поздними исследованиями, чем те, что были в 90-х годах, то я надеюсь, что кто-то скоро найдет более широко применимое решение, чтобы я мог также начать вычислять измерения VC на своих нейронных сетях. Извините я не смог

1 Бартлетт, Питер Л. и Маасс, Вольфганг, 2003, «Измерение нейронных сетей Вапника-Червоненкиса», с. 1188-1192, «Справочник по теории мозга и нейронным сетям», Арбиб, Майкл А., ред. MIT Press: Кембридж, Массачусетс

2 Karpinski, Marek and Macintyre, Angus, 1995, «Ограничение VC-измерения для нейронных сетей: прогресс и перспективы», стр. 337–341 в материалах 2-й Европейской конференции по теории вычислительного обучения, Барселона, Испания. Vitanyi, P. ed. Конспект лекций по искусственному интеллекту, № 904. Спрингер: Берлин.

Вот последняя работа: http://jmlr.org/papers/v20/17-612.html .

$W$$L$

$c$$C$