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 węzłami, źródłami i ujściem ( ). $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 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 lub w dół do jeśli jest ona większa niż pewien ustalony próg od . $[-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 ?), 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.

algorithms complexity-theory machine-learning neural-networks vc-dimension Artem Kaznatcheev
źródło

To mogłoby uczynić pytanie bardziej samodzielnym, gdybyś mógł uczynić funkcję przesyłania bardziej wyraźną. To znaczy określ rzeczywiste formuły dotyczące sposobu rozpowszechniania informacji.

Suresh,

Wydajne obliczanie lub przybliżanie wymiaru VC sieci neuronowej

Pytanie

Notatki

Odpowiedzi: