Mathematical Models of Computation in Superposition

• URL: http://arxiv.org/abs/2408.05451v1
• Date: Sat, 10 Aug 2024 06:11:48 GMT
• Title: Mathematical Models of Computation in Superposition
• Authors: Kaarel Hänni, Jake Mendel, Dmitry Vaintrob, Lawrence Chan,
• Abstract summary: Superposition poses a serious challenge to mechanistically interpreting current AI systems. We present mathematical models of emphcomputation in superposition, where superposition is actively helpful for efficiently accomplishing the task. We conclude by providing some potential applications of our work for interpreting neural networks that implement computation in superposition.
• Score: 0.9374652839580183
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Superposition -- when a neural network represents more ``features'' than it has dimensions -- seems to pose a serious challenge to mechanistically interpreting current AI systems. Existing theory work studies \emph{representational} superposition, where superposition is only used when passing information through bottlenecks. In this work, we present mathematical models of \emph{computation} in superposition, where superposition is actively helpful for efficiently accomplishing the task. We first construct a task of efficiently emulating a circuit that takes the AND of the $\binom{m}{2}$ pairs of each of $m$ features. We construct a 1-layer MLP that uses superposition to perform this task up to $\varepsilon$-error, where the network only requires $\tilde{O}(m^{\frac{2}{3}})$ neurons, even when the input features are \emph{themselves in superposition}. We generalize this construction to arbitrary sparse boolean circuits of low depth, and then construct ``error correction'' layers that allow deep fully-connected networks of width $d$ to emulate circuits of width $\tilde{O}(d^{1.5})$ and \emph{any} polynomial depth. We conclude by providing some potential applications of our work for interpreting neural networks that implement computation in superposition.

Related papers

• Deep Neural Networks: Multi-Classification and Universal Approximation [0.0]
  We demonstrate that a ReLU deep neural network with a width of $2$ and a depth of $2N+4M-1$ layers can achieve finite sample memorization for any dataset comprising $N$ elements. We also provide depth estimates for approximating $W1,p$ functions and width estimates for approximating $Lp(Omega;mathbbRm)$ for $mgeq1$.
  arXiv  Detail & Related papers  (2024-09-10T14:31:21Z)
• On the Complexity of Neural Computation in Superposition [3.9803704378699103]
  Recent advances in the understanding of neural networks suggest that superposition is a key mechanism underlying the computational efficiency of large-scale networks. We show a nearly tight upper bound: logical operations like pairwise AND can be computed using $O(sqrtm' log m')$ neurons and $O(m' log2 m')$ parameters. Our results open a path for using complexity theoretic techniques in neural network interpretability research.
  arXiv  Detail & Related papers  (2024-09-05T18:58:59Z)
• Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations [40.77319247558742]
  We study the computational complexity of learning a target function $f_*:mathbbRdtomathbbR$ with additive structure. We prove that a large subset of $f_*$ can be efficiently learned by gradient training of a two-layer neural network.
  arXiv  Detail & Related papers  (2024-06-17T17:59:17Z)
• Hamiltonian Mechanics of Feature Learning: Bottleneck Structure in Leaky ResNets [58.460298576330835]
  We study Leaky ResNets, which interpolate between ResNets ($tildeLtoinfty$) and Fully-Connected nets ($tildeLtoinfty$) In the infinite depth limit, we study'representation geodesics' $A_p$: continuous paths in representation space (similar to NeuralODEs) We leverage this intuition to explain the emergence of a bottleneck structure, as observed in previous work.
  arXiv  Detail & Related papers  (2024-05-27T18:15:05Z)
• Learning Hierarchical Polynomials with Three-Layer Neural Networks [56.71223169861528]
  We study the problem of learning hierarchical functions over the standard Gaussian distribution with three-layer neural networks. For a large subclass of degree $k$s $p$, a three-layer neural network trained via layerwise gradientp descent on the square loss learns the target $h$ up to vanishing test error. This work demonstrates the ability of three-layer neural networks to learn complex features and as a result, learn a broad class of hierarchical functions.
  arXiv  Detail & Related papers  (2023-11-23T02:19:32Z)
• Why should autoencoders work? [1.6317061277457001]
  Deep neural network autoencoders are routinely used for model reduction. We show that the technique is found to "work" well, which leads one to ask if there is a way to explain this effectiveness.
  arXiv  Detail & Related papers  (2023-10-03T17:53:43Z)
• Understanding Deep Neural Function Approximation in Reinforcement Learning via $\epsilon$-Greedy Exploration [53.90873926758026]
  This paper provides a theoretical study of deep neural function approximation in reinforcement learning (RL) We focus on the value based algorithm with the $epsilon$-greedy exploration via deep (and two-layer) neural networks endowed by Besov (and Barron) function spaces. Our analysis reformulates the temporal difference error in an $L2(mathrmdmu)$-integrable space over a certain averaged measure $mu$, and transforms it to a generalization problem under the non-iid setting.
  arXiv  Detail & Related papers  (2022-09-15T15:42:47Z)
• On the Optimal Memorization Power of ReLU Neural Networks [53.15475693468925]
  We show that feedforward ReLU neural networks can memorization any $N$ points that satisfy a mild separability assumption. We prove that having such a large bit complexity is both necessary and sufficient for memorization with a sub-linear number of parameters.
  arXiv  Detail & Related papers  (2021-10-07T05:25:23Z)
• On the Modularity of Hypernetworks [103.1147622394852]
  We show that for a structured target function, the overall number of trainable parameters in a hypernetwork is smaller by orders of magnitude than the number of trainable parameters of a standard neural network and an embedding method.
  arXiv  Detail & Related papers  (2020-02-23T22:51:52Z)
• Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learning [66.05472746340142]
  This paper analyzes how multi-layer neural networks can perform hierarchical learning _efficiently_ and _automatically_ by SGD on the training objective. We establish a new principle called "backward feature correction", where the errors in the lower-level features can be automatically corrected when training together with the higher-level layers.
  arXiv  Detail & Related papers  (2020-01-13T17:28:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.