Grokking Group Multiplication with Cosets

• URL: http://arxiv.org/abs/2312.06581v2
• Date: Mon, 17 Jun 2024 17:44:44 GMT
• Title: Grokking Group Multiplication with Cosets
• Authors: Dashiell Stander, Qinan Yu, Honglu Fan, Stella Biderman,
• Abstract summary: Algorithmic tasks have proven to be a fruitful test ground for interpreting a neural network end-to-end. We completely reverse engineer fully connected one-hidden layer networks that have grokked'' the arithmetic of the permutation groups $S_5$ and $S_6$. We relate how we reverse engineered the model's mechanisms and confirm our theory was a faithful description of the circuit's functionality.
• Score: 10.255744802963926
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The complex and unpredictable nature of deep neural networks prevents their safe use in many high-stakes applications. There have been many techniques developed to interpret deep neural networks, but all have substantial limitations. Algorithmic tasks have proven to be a fruitful test ground for interpreting a neural network end-to-end. Building on previous work, we completely reverse engineer fully connected one-hidden layer networks that have ``grokked'' the arithmetic of the permutation groups $S_5$ and $S_6$. The models discover the true subgroup structure of the full group and converge on neural circuits that decompose the group arithmetic using the permutation group's subgroups. We relate how we reverse engineered the model's mechanisms and confirmed our theory was a faithful description of the circuit's functionality. We also draw attention to current challenges in conducting interpretability research by comparing our work to Chughtai et al. [4] which alleges to find a different algorithm for this same problem.

Related papers

• Generating Interpretable Networks using Hypernetworks [16.876961991785507]
  We explore the possibility of using hypernetworks to generate interpretable networks whose underlying algorithms are not yet known. For the task of computing L1 norms, hypernetworks find three algorithms: (a) the double-sided algorithm, (b) the convexity algorithm, (c) the pudding algorithm. We show that a trained hypernetwork can correctly construct models for input dimensions not seen in training, demonstrating systematic generalization.
  arXiv  Detail & Related papers  (2023-12-05T18:55:32Z)
• The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networks [59.26515696183751]
  We show that algorithm discovery in neural networks is sometimes more complex. We show that even simple learning problems can admit a surprising diversity of solutions.
  arXiv  Detail & Related papers  (2023-06-30T17:59:13Z)
• A Toy Model of Universality: Reverse Engineering How Networks Learn Group Operations [0.0]
  We study the universality hypothesis by examining how small neural networks learn to implement group composition. We present a novel algorithm by which neural networks may implement composition for any finite group via mathematical representation theory.
  arXiv  Detail & Related papers  (2023-02-06T18:59:20Z)
• Robust Training and Verification of Implicit Neural Networks: A Non-Euclidean Contractive Approach [64.23331120621118]
  This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks. We introduce a related embedded network and show that the embedded network can be used to provide an $ell_infty$-norm box over-approximation of the reachable sets of the original network. We apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature.
  arXiv  Detail & Related papers  (2022-08-08T03:13:24Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  We show that a sufficiently large two-layer ReLU-network with standard Gaussian weights and uniformly distributed biases can solve this problem with high probability. We quantify the relevant structure of the data in terms of a novel notion of mutual complexity.
  arXiv  Detail & Related papers  (2021-07-31T10:25:26Z)
• A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups [115.58550697886987]
  We provide a completely general algorithm for solving for the equivariant layers of matrix groups. In addition to recovering solutions from other works as special cases, we construct multilayer perceptrons equivariant to multiple groups that have never been tackled before. Our approach outperforms non-equivariant baselines, with applications to particle physics and dynamical systems.
  arXiv  Detail & Related papers  (2021-04-19T17:21:54Z)
• Neural Contextual Bandits with Deep Representation and Shallow Exploration [105.8099566651448]
  We propose a novel learning algorithm that transforms the raw feature vector using the last hidden layer of a deep ReLU neural network. Compared with existing neural contextual bandit algorithms, our approach is computationally much more efficient since it only needs to explore in the last layer of the deep neural network.
  arXiv  Detail & Related papers  (2020-12-03T09:17:55Z)
• Neural Group Actions [0.0]
  We introduce an algorithm for designing Neural Group Actions, collections of deep neural network architectures which model symmetric transformations satisfying the laws of a given finite group. We demonstrate experimentally that a Neural Group Action for the quaternion group $Q_8$ can learn how a set of nonuniversal quantum gates satisfying the $Q_8$ group laws act on single qubit quantum states.
  arXiv  Detail & Related papers  (2020-10-08T02:27:05Z)
• Neural Thompson Sampling [94.82847209157494]
  We propose a new algorithm, called Neural Thompson Sampling, which adapts deep neural networks for both exploration and exploitation. At the core of our algorithm is a novel posterior distribution of the reward, where its mean is the neural network approximator, and its variance is built upon the neural tangent features of the corresponding neural network.
  arXiv  Detail & Related papers  (2020-10-02T07:44:09Z)
• Random Vector Functional Link Networks for Function Approximation on Manifolds [8.535815777849786]
  We show that single layer neural-networks with random input-to-hidden layer weights and biases have seen success in practice. We further adapt this randomized neural network architecture to approximate functions on smooth, compact submanifolds of Euclidean space.
  arXiv  Detail & Related papers  (2020-07-30T23:50:44Z)

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.