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

Mi objetivo es resolver el siguiente problema, que he descrito por su entrada y salida:

Entrada:

Un gráfico acíclico dirigido con nodos, fuentes y sumidero ( ).$G$$m$$n$$1$$m > n \geq 1$

Salida:

El VC-dimensión (o una aproximación de la misma) para la red neuronal con topología .$G$

Más detalles :

• Cada nodo en es una neurona sigmoidea. La topología es fija, pero el algoritmo de aprendizaje puede variar los pesos en los bordes.$G$
• El algoritmo de aprendizaje es fijo (por ejemplo, propagación hacia atrás).
• Los nodos fuente son las neuronas de entrada y solo pueden tomar cadenas de como entrada.$n$$\{-1,1\}^n$
• El nodo sumidero es la unidad de salida. Produce un valor real desde que redondeamos hacia arriba a o hacia abajo a si está a más de un cierto umbral fijo lejos de .$[-1,1]$$1$$-1$$\delta$$0$

El enfoque ingenuo es simplemente tratar de romper más y más puntos, tratando de entrenar a la red en ellos. Sin embargo, este tipo de enfoque de simulación no es eficiente.

Pregunta

¿Existe una manera eficiente (es decir, en cuando se cambia al problema de decisión: ¿es la dimensión VC menor que el parámetro de entrada ?) Para calcular esta función? Si no, ¿hay resultados de dureza?$\mathsf{P}$$k$

¿Existe una manera que funcione bien en la práctica para calcular o aproximar esta función? Si se trata de una aproximación, ¿hay alguna garantía sobre su precisión?

Notas

Hice una pregunta similar sobre stats.SE pero no generó interés.

$2ds \log(es)$$s$$d$$e$

No es estrictamente una respuesta a su pregunta, pero podría ayudarlo en el camino. El resultado se debe a Baum y Haussler (1989).