Wydajne obliczanie lub przybliżanie wymiaru VC sieci neuronowej

Moim celem jest rozwiązanie następującego problemu, który opisałem na podstawie jego danych wejściowych i wyjściowych:

Wejście:

Kierunkowy wykres acykliczny z m węzłami, n źródłami i 1 ujściem ( m > n ≥ 1 ).$G$$m$$n$$1$$m > n \geq 1$

Wynik:

VC wymiar (lub zbliżanie niego) dla sieci neuronowej z topologii .$G$

Więcej szczegółów :

• Każdy węzeł w jest neuronem esicy. Topologia jest ustalona, ​​ale wagi na krawędziach można zmieniać za pomocą algorytmu uczenia się.$G$
• Algorytm uczenia się jest stały (powiedzmy propagacja wsteczna).
• Gdy węzły źródłowe są neurony wejściowe i może jedynie ciągi z { - 1 , 1 } n jako wejście.$n$$\{-1,1\}^n$
• Węzeł sink jest jednostką wyjściową. Wyprowadza rzeczywistą wartość z , którą zaokrąglamy w górę do 1 lub w dół do - 1, jeśli jest ona większa niż pewien ustalony próg δ od 0 .$[-1,1]$$1$$-1$$\delta$$0$

Naiwnym podejściem jest po prostu próba przełamania coraz większej liczby punktów, poprzez wyszkolenie sieci na nich. Jednak takie podejście symulacyjne nie jest wydajne.

Pytanie

Czy istnieje skuteczny sposób (tj. W po zmianie na problem decyzyjny: czy wymiar VC jest mniejszy niż parametr wejściowy k ?), Aby obliczyć tę funkcję? Jeśli nie, czy są wyniki twardości?$\mathsf{P}$$k$

Czy istnieje praktyczny sposób na obliczenie lub przybliżenie tej funkcji? Jeśli jest to przybliżenie, czy są jakieś gwarancje jego dokładności?

Notatki

Zadałem podobne pytanie na temat stats.SE, ale nie wzbudziło to zainteresowania.

Jeśli są chętni, aby ograniczyć ten problem, pozwalając dodatkowo sieć być warstwowe, to Tom Mitchell „Machine Learning” daje górną granicę ( ) (sekcja 7.4.4), gdzie s jest liczbą węzły wewnętrzne (które muszą być większe niż 2), d jest wymiarem VC poszczególnych węzłów, a e jest podstawą logarytmu naturalnego. Jeśli zależy ci na ograniczeniu liczby przykładów szkoleń, ta informacja powinna wystarczyć.$2ds \log(es)$$s$$d$$e$

To nie jest ściśle odpowiedź na twoje pytanie, ale może ci pomóc w drodze. Wynik wynika z Bauma i Hausslera (1989).