A Galois theorem for machine learning: Functions on symmetric matrices and point clouds via lightweight invariant features

• URL: http://arxiv.org/abs/2405.08097v3
• Date: Thu, 13 Feb 2025 15:53:59 GMT
• Title: A Galois theorem for machine learning: Functions on symmetric matrices and point clouds via lightweight invariant features
• Authors: Ben Blum-Smith, Ningyuan Huang, Marco Cuturi, Soledad Villar,
• Abstract summary: We present a mathematical formulation for machine learning of functions on symmetric matrices and point clouds. We provide a general construction of generically separating invariant features using ideas inspired by Galois theory. We prove that the number of invariant features can be reduced, generically without losing expressivity, to $O(n)$, where $n$ is the number of points.
• Score: 26.619014249559942
• License:
• Abstract: In this work, we present a mathematical formulation for machine learning of (1) functions on symmetric matrices that are invariant with respect to the action of permutations by conjugation, and (2) functions on point clouds that are invariant with respect to rotations, reflections, and permutations of the points. To achieve this, we provide a general construction of generically separating invariant features using ideas inspired by Galois theory. We construct $O(n^2)$ invariant features derived from generators for the field of rational functions on $n\times n$ symmetric matrices that are invariant under joint permutations of rows and columns. We show that these invariant features can separate all distinct orbits of symmetric matrices except for a measure zero set; such features can be used to universally approximate invariant functions on almost all weighted graphs. For point clouds in a fixed dimension, we prove that the number of invariant features can be reduced, generically without losing expressivity, to $O(n)$, where $n$ is the number of points. We combine these invariant features with DeepSets to learn functions on symmetric matrices and point clouds with varying sizes. We empirically demonstrate the feasibility of our approach on molecule property regression and point cloud distance prediction.

Related papers

• Entrywise application of non-linear functions on orthogonally invariant matrices [44.99833362998488]
  We investigate how the entrywise application of a non-linear function to symmetric invariant random matrix ensembles alters the spectral distribution. We find that in all those cases a Gaussian equivalence principle holds, that is, the effect of the non-linear function is the same as taking a linear combination of the involved matrices and an additional independent GOE.
  arXiv  Detail & Related papers  (2024-12-09T19:41:09Z)
• Equivariant Manifold Neural ODEs and Differential Invariants [1.6073704837297416]
  We develop a manifestly geometric framework for equivariant manifold neural ordinary differential equations (NODEs) We use it to analyse their modelling capabilities for symmetric data.
  arXiv  Detail & Related papers  (2024-01-25T12:23:22Z)
• Algebras of actions in an agent's representations of the world [51.06229789727133]
  We use our framework to reproduce the symmetry-based representations from the symmetry-based disentangled representation learning formalism. We then study the algebras of the transformations of worlds with features that occur in simple reinforcement learning scenarios. Using computational methods, that we developed, we extract the algebras of the transformations of these worlds and classify them according to their properties.
  arXiv  Detail & Related papers  (2023-10-02T18:24:51Z)
• Geometry of Linear Neural Networks: Equivariance and Invariance under Permutation Groups [1.8434042562191815]
  We investigate the subvariety of functions that are equivariant or invariant under the action of a permutation group. We draw conclusions for the parameterization and the design of equivariant and invariant linear networks.
  arXiv  Detail & Related papers  (2023-09-24T19:40:15Z)
• Deep Learning Symmetries and Their Lie Groups, Algebras, and Subalgebras from First Principles [55.41644538483948]
  We design a deep-learning algorithm for the discovery and identification of the continuous group of symmetries present in a labeled dataset. We use fully connected neural networks to model the transformations symmetry and the corresponding generators. Our study also opens the door for using a machine learning approach in the mathematical study of Lie groups and their properties.
  arXiv  Detail & Related papers  (2023-01-13T16:25:25Z)
• Machine learning and invariant theory [10.178220223515956]
  We introduce the topic and explain a couple of methods to explicitly parameterize equivariant functions. We explicate a general procedure, attributed to Malgrange, to express all maps between linear spaces that are equivariant under the action of a group $G$.
  arXiv  Detail & Related papers  (2022-09-29T17:52:17Z)
• Permutation symmetry in large N Matrix Quantum Mechanics and Partition Algebras [0.0]
  We describe the implications of permutation symmetry for the state space and dynamics of quantum mechanical systems of general size $N$. A symmetry-based mechanism for quantum many body scars discussed in the literature can be realised in these matrix systems with permutation symmetry.
  arXiv  Detail & Related papers  (2022-07-05T16:47:10Z)
• $O(N^2)$ Universal Antisymmetry in Fermionic Neural Networks [107.86545461433616]
  We propose permutation-equivariant architectures, on which a determinant Slater is applied to induce antisymmetry. FermiNet is proved to have universal approximation capability with a single determinant, namely, it suffices to represent any antisymmetric function. We substitute the Slater with a pairwise antisymmetry construction, which is easy to implement and can reduce the computational cost to $O(N2)$.
  arXiv  Detail & Related papers  (2022-05-26T07:44:54Z)
• 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)
• Invariant Feature Coding using Tensor Product Representation [75.62232699377877]
  We prove that the group-invariant feature vector contains sufficient discriminative information when learning a linear classifier. A novel feature model that explicitly consider group action is proposed for principal component analysis and k-means clustering.
  arXiv  Detail & Related papers  (2019-06-05T07:15:17Z)

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.