The Vapnik-Chervonenkis dimensions of different neural network architectures

Abstract

Die Vapnik-Chervonenkis-Dimension, kurz VC-Dimension, ist ein Maß für die Expressivität einer Menge von Funktionen. In dieser Arbeit untersuchen wir dieses Konzept in Bezug auf verschiedene neuronale Netzwerke, die die Sigmoidfunktion als Aktivierungsfunktion verwenden. Genauer gesagt betrachten wir klassische Multilayered Feed-forward Netzwerke und zwei NeuralODE-Architekturen, nämlich Liquid Time Constant(LTC) Netzwerke und Continuous-Time Recurrent Neural Networks(CT-RNNs). In den NeuralODE-Architekturen wird die Ausgabe durch numerisches Lösen einer gewöhnlichen Differentialgleichung berechnet, wovon sich auch der Name ableitet. Für diese Netzwerkklassen leiten wir obere Schranken für die VC Dimension ab, und zwar in Abhängigkeit von der Anzahl der Neuronen, und im Falle der NeuralODE Modelle auch in Abhängigkeit von der Anzahl der Diskretisierungsschritte. Hierzu verwenden wir eine Methode, bei der die Anzahl der Komponenten der Nullmengen von Funktionen - die von den Parametern des Netzwerks abhängen - eine wesentliche Rolle spielt. Dabei finden verschiedene Methoden aus Topologie und Geometrischer Analysis Anwendung. Wir finden einen starken Zusammenhang zwischen der VC-Dimensions-Schranke und der Anzahl der Neuronen im Netzwerk. Die Abhängigkeit von der Anzahl der Diskreditierungsschritte ist auch gegeben, allerdings in geringerem Ausmaß. Die Schranke der NeuralODE-Netze ist etwas höher als die der klassischen Netze bei gleicher Anzahl an Neuronen, was zum Teil darauf zurückzuführen ist, dass die NeuralODE Netze mehr Parameter haben.

The Vapnik-Chervonenkis dimension, VC dimension in short, is a measure of expressivity or richness of a set of functions. In this thesis, we explore this concept in relation to different neural network architectures that use sigmoid activation functions. More specifically, we will take a look at classical multilayered feed-forward neural networks and at two NeuralODE architectures, namely Liquid Time Constant (LTC) networks and Continuous-Time Recurrent Neural Networks (CT-RNNs). In the latter two, the output of the network is computed by numerically solving an ordinary differential equation. For these networks, we derived upper bounds on the VC dimension, depending on the number of neurons, and in case of the recurrent models (LTC and CT-RNN), discretization steps. This was done through a method involving the number of components of the zero-set of functions that are dependent on the network parameters. Here various techniques relating to topology and geometrical analysis were used. We find a very strong dependence of the VC dimension bound on the number of neurons and a sizeable dependence on the number of discretization steps. The recurrent models had a higher bound than the classical network for the same number of neurons, which is partly due to the recurrent models having more parameters than the classical network.