Berechnung der VC-Dimension eines neuronalen Netzwerks

Wenn ich eine feste nicht wiederkehrende (DAG) Topologie (fester Satz von Knoten und Kanten, aber der Lernalgorithmus kann das Gewicht an den Kanten variieren) von Sigmoidneuronen mit Eingangsneuronen habe, die nur Zeichenfolgen in als Eingabe und führt zu einer Ausgabe (die einen realen Wert ausgibt, den wir auf 1 oder auf -1 aufrunden, wenn es sich um einen bestimmten festen Schwellenwert von 0 handelt). Gibt es eine schnelle Möglichkeit, die VC-Dimension dieses Netzwerks zu berechnen (oder zu approximieren)?$n$$\{-1,1\}^n$

Anmerkungen

Ich fragte nach einer etwas genaueren algorithmischen Neuformulierung von CS.SE:

Effizientes Berechnen oder Annähern der VC-Dimension eines neuronalen Netzwerks

Ich bin auf der Suche nach einer allgemeinen Formel zur Berechnung der VC-Dimensionen auf neuronalen Netzen über Ihren Beitrag gestolpert, aber anscheinend gibt es keine. Anscheinend gibt es nur eine Vielzahl unterschiedlicher VC-Gleichungen, die nur in bestimmten engen Fällen gelten. Achtung: Ich stütze mich dabei auf alte Forschungsergebnisse, die ich kaum verstehe, auf das Konzept von VC Dimensions, über das ich erst jetzt lerne. Dennoch kann es sich lohnen, dieses Papier von Peter L. Bartlett und Wolfgang Maass 1 zu überfliegenzur Berechenbarkeit von VC-Dimensionen. Beachten Sie, wie weit sie gehen, um VC-Formeln in 13 Theoremen abzuleiten, aber wie vielfältig und zahlreich die notwendigen Bedingungen für jeden sind. Diese Voraussetzungen reichen von der Anzahl der Operatoren in Aktivierungsfunktionen bis zu den Arten der zulässigen Sprünge, der Anzahl der Neuronen und ihrer Positionen, der Bittiefe der Eingabe usw.; Es gibt so viele dieser verstreuten "Fallstricke", dass sie die Formeln nur für bestimmte enge Problemklassen nützlich machen. Um die Sache noch schlimmer zu machen, weisen sie in Satz 5 und 8 darauf hin, dass es besonders schwierig ist, VC-Zahlen für sigmoidale Aktivierungsfunktionen zu berechnen. Auf den Seiten 6-7 schreiben sie:

"Während die VC-Dimension von Netzwerken mit stückweisen Polynomaktivierungsfunktionen gut verstanden ist, verwenden die meisten Anwendungen neuronaler Netzwerke die logistische Sigmoidfunktion oder die Gaußsche radiale Basisfunktion. Leider ist es nicht möglich, solche Funktionen unter Verwendung einer endlichen Anzahl von Funktionen zu berechnen." In Satz 5 aufgeführte arithmetische Operationen Karpinski und Macintyre [Karpinski und Macintyre, 1997] haben Satz 5 jedoch erweitert, um die Berechnung von Exponentialen zu ermöglichen. Der Beweis verwendet dieselben Ideen, aber die Grenze für die Anzahl der Lösungen eines Gleichungssystems ist wesentlich schwieriger. "

Ich bin auch auf dieses Papier mit dem ermutigenden Titel "Bounding VC-Dimension for Neural Networks: Progress and Prospects" gestoßen. 2Ein Großteil der Mathematik geht mir über den Kopf und ich habe sie nicht lange genug überflogen, um meine mangelnden Übersetzungsfähigkeiten zu überwinden, aber ich vermute, dass sie keine weltbewegenden Lösungen bietet, da sie vor der zweiten Ausgabe des Buches Bartlett liegen und Maass, die eine spätere Arbeit derselben Autoren zitieren. Vielleicht haben spätere Forschungen in den letzten 20 Jahren die Berechenbarkeit der VC-Dimensionen für neuronale Netze verbessert, aber die meisten Referenzen, die ich gefunden habe, scheinen aus der Mitte der 90er Jahre zu stammen. Anscheinend gab es damals eine Flut von Arbeiten zu diesem Thema, die seitdem abgeklungen sind. Wenn die Fähigkeiten nicht durch neuere Stipendien weit über das der 90er Jahre hinaus erweitert wurden, hoffe ich, dass bald jemand eine allgemein anwendbare Lösung findet, damit ich auch mit der Berechnung der VC-Dimensionen auf meinen neuronalen Netzen beginnen kann. Entschuldigung, ich konnte nicht

1 Bartlett, Peter L. und Maass, Wolfgang, 2003, "Vapnik-Chervonenkis Dimension neuronaler Netze", S. 1188-1192 im Handbuch für Gehirntheorie und neuronale Netze, Arbib, Michael A. ed. MIT Press: Cambridge, Mass.

2 Karpinski, Marek und Macintyre, Angus, 1995, "Bounding VC-Dimension for Neural Networks: Fortschritt und Perspektiven", S. 337–341 in Proceedings of the 2nd European Conference on Computational Learning Theory, Barcelona, ​​Spanien. Vitanyi, P. ed. Lecture Notes in Artificial Intelligence, Nr. 904. Springer: Berlin.

Hier ist die neueste Arbeit: http://jmlr.org/papers/v20/17-612.html .

Grundsätzlich ist ein Netzwerk mit Gewichten, Schichten und relu Aktivierungen folgt: für einige Konstanten und .$W$$L$

Angesichts der Gültigkeit der Arbeit denke ich, dass es praktische Grenzen gibt. Ich bin mir jedoch nicht sicher, wie eng die Grenzen (und insbesondere die Konstanten und ) sind, da ich sie nicht vollständig gelesen habe.$c$$C$