Cálculo de la dimensión VC de una red neuronal

Si tengo alguna topología fija no recurrente (DAG) (conjunto fijo de nodos y bordes, pero el algoritmo de aprendizaje puede variar el peso en los bordes) de las neuronas sigmoideas con neuronas de entrada que solo pueden tomar cadenas en como entrada y conduce a una salida (que genera un valor real que redondeamos a 1 o a -1 si está a un cierto umbral fijo lejos de 0). ¿Hay alguna forma rápida de calcular (o aproximar) la dimensión VC de esta red?$n$$\{-1,1\}^n$

Notas

Pedí una reformulación algorítmica un poco más precisa en CS.SE:

Computación eficiente o aproximación de la dimensión VC de una red neuronal

Me topé con tu publicación mientras buscaba una fórmula general para calcular las dimensiones de VC en redes neuronales, pero aparentemente no hay ninguna. Aparentemente solo tenemos una mezcla de ecuaciones de VC dispares que solo se aplican en ciertos casos estrechos. Precaución: estoy basando esto en investigaciones antiguas que apenas entiendo, en el concepto de VC Dimensions, del que solo ahora estoy aprendiendo. Sin embargo, puede valer la pena leer este artículo de Peter L. Bartlett y Wolfgang Maass 1sobre la calculabilidad de las dimensiones de VC. Observe cómo hacen todo lo posible para derivar fórmulas de CV en 13 teoremas, pero cuán diversas y numerosas son las condiciones necesarias para cada uno. Estos requisitos previos van desde la cantidad de operadores en las funciones de activación hasta los tipos de saltos permitidos, la cantidad de neuronas y sus posiciones, la profundidad de bits de la entrada, etc .; hay tantas de estas "trampas" dispersas que hacen que las fórmulas sean útiles solo para ciertas clases limitadas de problemas. Para empeorar las cosas, señalan en los Teoremas 5 y 8 que las funciones de activación sigmoidea son particularmente difíciles de calcular para las cifras de CV. En las páginas 6-7 escriben:

"Si bien la dimensión VC de las redes con funciones de activación polinómica por partes se entiende bien, la mayoría de las aplicaciones de redes neuronales usan la función sigmoidea logística o la función de base radial gaussiana. Desafortunadamente, no es posible calcular tales funciones usando un número finito de operaciones aritméticas enumeradas en el Teorema 5. Sin embargo, Karpinski y Macintyre [Karpinski y Macintyre, 1997] extendieron el Teorema 5 para permitir el cálculo de exponenciales. La prueba utiliza las mismas ideas, pero el límite en el número de soluciones de un sistema de ecuaciones es sustancialmente más difícil ".

También me encontré con este documento con el título alentador de "Dimensión VC vinculante para redes neuronales: progreso y perspectivas". 2Muchas de las matemáticas están sobre mi cabeza y no las hojeé lo suficiente como para superar mi falta de habilidades de traducción, pero sospecho que no ofrece ninguna solución revolucionaria, ya que es anterior a la segunda edición del libro Bartlett. y Maass, quienes citan un trabajo posterior de los mismos autores. Quizás una investigación posterior en los últimos 20 años ha mejorado la capacidad de cálculo de las dimensiones de VC para redes neuronales, pero la mayoría de las referencias que he encontrado parecen datarse de mediados de los 90; aparentemente hubo una gran cantidad de trabajo sobre el tema en ese entonces que desde entonces ha desaparecido. Si las capacidades no han sido extendidas por estudios más recientes mucho más allá de lo que eran en los años 90, entonces espero que alguien presente una solución más ampliamente aplicable pronto para que pueda comenzar a calcular las dimensiones de VC en mis redes neuronales también. Lo siento, no pude

1 Bartlett, Peter L. y Maass, Wolfgang, 2003, "Vapnik-Chervonenkis Dimension of Neural Nets", págs. 1188-1192 en The Handbook of Brain Theory and Neural Networks, Arbib, Michael A. ed. MIT Press: Cambridge, Mass.

2 Karpinski, Marek y Macintyre, Angus, 1995, "Bounding VC-Dimension for Neural Networks: Progress and Prospects", págs. 337–341 en Actas de la 2ª Conferencia Europea sobre Teoría del Aprendizaje Computacional, Barcelona, ​​España. Vitanyi, P. ed. Lecture Notes in Artificial Intelligence, No. 904. Springer: Berlín.

Aquí está el último trabajo: http://jmlr.org/papers/v20/17-612.html .

$W$$L$

$c$$C$