Let F and H be two (compatible) classes of functions. We observe that even when both F and H have small capacities as measured by their uniform covering numbers, the capacity of the composition class H o F={h o f| f in F, h in H} can become prohibitively large or even unbounded. To this end, in this thesis we provide a framework for controlling the capacity of composition and extend our results to bound the capacity of neural networks.
Composition of Random Classes: We show that adding a small amount of Gaussian noise to the output of cF before composing it with H can effectively control the capacity of H o F, offering a general recipe for modular design. To prove our results, we define new notions of uniform covering number of random functions with respect to the total variation and Wasserstein distances. The bounds for composition then come naturally through the use of data processing inequality.
Capacity of Neural Networks: We instantiate our results for the case of sigmoid neural networks. We start by finding a bound for the single-layer noisy neural network by estimating input distributions with mixtures of Gaussians and covering them. Next, we use our composition theorems to propose a novel bound for the covering number of a multi-layer network. This bound does not require Lipschitz assumption and works for networks with potentially large weights.
Empirical Investigation of Generalization Bounds: We include preliminary empirical results on MNIST dataset to compare several covering number bounds based on their suggested generalization bounds. To compare these bounds, we propose a new metric (NVAC) that measures the minimum number of samples required to make the bound non-vacuous. The empirical results indicate that the amount of noise required to improve over existing uniform bounds can be numerically negligible. The source codes are available at https://github.com/fathollahpour/composition_noise / Thesis / Master of Science (MSc) / Given two classes of functions with bounded capacity, is there a systematic way to bound the capacity of their composition? We show that this is not generally true. Capacity of a class of functions is a learning-theoretic quantity that may be used to explain its sample complexity and generalization behaviour. In other words, bounding the capacity of a class can be used to ensure that given enough samples, with high probability, the deviation between training and expected errors is small.
In this thesis, we show that adding a small amount of Gaussian noise to the output of functions can effectively control the capacity of composition, introducing a general framework for modular design. We instantiate our results for sigmoid neural networks and derive capacity bounds that work for networks with large weights. Our empirical results show that the amount of Gaussian noise required to improve over existing bounds is negligible.
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/27752 |
| Date | January 2022 |
| Creators | Fathollah Pour, Alireza |
| Contributors | Ashtiani, Hassan, Computing and Software |
| Source Sets | McMaster University |
| Language | English |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0022 seconds