Machines of Finite Depth: Towards a Formalization of Neural Networks

Pietro Vertechi, Mattia G. BergomiAAAI 2023 · DOI

TL;DR

This paper introduces "machines of finite depth," a unified mathematical framework to formally define neural networks and their architectures. This framework allows for a precise definition of neural networks, enabling efficient computation and differentiation, and generalizing various existing architectures like dense, convolutional, and recurrent networks.

What Problem Does This Paper Address?

The paper addresses the increasing ambiguity in the definition of modern neural networks. While early neural networks could be easily represented as directed graphs, contemporary architectures exhibit diverse structures that lack a precise mathematical definition. This ambiguity poses challenges for software libraries, research in automated architecture search, and the formal sharing of models. Existing approaches, like domain-specific languages or differentiable programming, have limitations: domain-specific languages can be restrictive, while differentiable programming can lead to difficulties in optimizing runtime and a lack of a well-defined mathematical space for models.

Methods

The core of the paper is the introduction of "parametric machines," a unified mathematical construction that generalizes neural networks. A machine is defined as an endofunction $f: X \to X$ on a normed vector space $X$, satisfying the machine equation $h = g + fh$, where $g$ is the input function and $h$ is the output function. This equation is equivalent to $(id - f)h = g$, meaning $id - f$ must be an isomorphism. The paper proves that if $f$ admits a "depth cofiltration," it is a machine of finite depth. This framework allows for the composition of machines, where the sum of machines of finite depth is also a machine of finite depth, provided they satisfy an "independence" condition. Backpropagation is framed as computing the resolvent of the dual machine, which is shown to be computationally comparable to the forward pass.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unified Framework: The concept of "machines of finite depth" provides a single mathematical lens through which to view diverse neural network architectures, including those with complex shortcut connections.
  • Resolvent as the Core Operation: The forward pass of a neural network is elegantly reframed as computing the resolvent of the $id - f$ operator, offering a more robust mathematical foundation than simple function composition.
  • Backpropagation as Dual Machine Computation: The paper demonstrates that the backward pass (backpropagation) can be naturally formulated as computing the resolvent of the dual machine, ensuring computational efficiency and a unified approach to forward and backward passes.
  • Independence for Composability: The introduction of an "independence" condition between machines is crucial for their composition. This condition dictates how machines can be combined, especially in the presence of shortcuts, and ensures that the sum of finite-depth machines remains a finite-depth machine.
  • Finite Depth as a Computability Guarantee: Machines of finite depth are shown to be efficiently computable, with their resolvents (forward pass) and derivatives (backward pass) having comparable computational costs.

Key Results

  • The paper provides a formal definition of neural networks as "machines of finite depth" that are modular, efficiently computable, and differentiable.
  • It proves that the backward pass of a machine is also a machine and can be computed efficiently using the same procedure as the forward pass.
  • The framework unifies classical architectures like dense, convolutional, and recurrent neural networks, along with those featuring shortcut connections.
  • The paper demonstrates that the computational cost of the backward pass is comparable to the forward pass, as illustrated by experimental results showing a runtime ratio close to 1 for various architectures (Figure 2).

Limitations and Future Work

  • Practical Implementation of Independence: While the theoretical framework establishes independence for composability, practically ensuring this condition for arbitrary machines might require further investigation.
  • Exploration of Regularization: The paper suggests that the proposed framework offers new avenues for regularization beyond simply setting parameters to zero, such as penalizing parameter differences or using kernel methods. Investigating the merits of these approaches is a direction for future work.
  • Generalization of Architectures: The paper focuses on a specific way to define machines of finite depth by combining linear and nonlinear components. Further exploration into other methods of constructing machines and their properties is implied.

Summary updated

BibTeX
@inproceedings{vertechi2023machines,
  author = {Pietro Vertechi and Mattia G. Bergomi},
  title = {{Machines of Finite Depth: Towards a Formalization of Neural Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i8.26199},
}
Figure