On the Complexity of Neural Network Representations

Citation

Kiliç, Kordağ Mehmet (2024) On the Complexity of Neural Network Representations. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/trse-ff38. https://resolver.caltech.edu/CaltechTHESIS:06032024-055145735

Abstract

The evolution of the human brain was one of the milestones in the history of information after the emergence of life. The underlying biological, chemical, and physical processes of the brain have amazed scientists for a long time. It is still a mystery how the human brain computes a simple arithmetical operation like 2 + 2 = 4. This enigma has spurred investigations into understanding the intrinsic architecture of the brain.

This thesis delves into two primary models for brain architecture: Feedforward Neural Networks and Nearest Neighbor (NN) Representations. Both models are treated under the hypothesis that our brain does not work with "large" numbers and expressive power is derived from connectivity. Thus, when examining a network or, more precisely, a single neuron model, we strive to minimize the bit resolution of weights, potentially increasing depth or circuit complexity.

For the NN representations, the memory is defined by a set of vectors in Rⁿ (that we call anchors), computation is performed by convergence from an input vector to a nearest neighbor anchor, and the output is a label associated with an anchor. Limited bit resolution in the anchor entries may result in an increase of the size of the NN representation.

In the digital age, computers universally employ the binary numeral system, ensuring the enduring relevance of Boolean functions. This study specifically explores the trade-off between resolution and size for the computation models for Boolean functions. It is established that "low resolution" models may require a polynomial or even an exponential increase in the size complexity of the "high resolution" model, potentially making the practical implementation infeasible. Building upon prior research, our goal is to optimize these blow-ups by narrowing the gaps between theoretical upper and lower bounds under various constraints. Additionally, we aim to establish connections between NN representations and neural network models by providing explicit NN representations for well-known Boolean functions in Circuit Complexity Theory.

Thesis Files