Programs as Singularities

• URL: http://arxiv.org/abs/2504.08075v1
• Date: Thu, 10 Apr 2025 19:04:31 GMT
• Title: Programs as Singularities
• Authors: Daniel Murfet, Will Troiani,
• Abstract summary: We develop a correspondence between the structure of Turing machines and the structure of singularities of real analytic functions.<n>Our results point to a more nuanced understanding of Occam's razor and the meaning of simplicity in inductive inference.
• Score: 0.6906005491572401
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We develop a correspondence between the structure of Turing machines and the structure of singularities of real analytic functions, based on connecting the Ehrhard-Regnier derivative from linear logic with the role of geometry in Watanabe's singular learning theory. The correspondence works by embedding ordinary (discrete) Turing machine codes into a family of noisy codes which form a smooth parameter space. On this parameter space we consider a potential function which has Turing machines as critical points. By relating the Taylor series expansion of this potential at such a critical point to combinatorics of error syndromes, we relate the local geometry to internal structure of the Turing machine. The potential in question is the negative log-likelihood for a statistical model, so that the structure of the Turing machine and its associated singularity is further related to Bayesian inference. Two algorithms that produce the same predictive function can nonetheless correspond to singularities with different geometries, which implies that the Bayesian posterior can discriminate between distinct algorithmic implementations, contrary to a purely functional view of inference. In the context of singular learning theory our results point to a more nuanced understanding of Occam's razor and the meaning of simplicity in inductive inference.

Related papers

• On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning [87.73401758641089]
  Chain-of-thought (CoT) reasoning has improved the performance of modern language models (LMs)<n>We show that LMs can represent the same family of distributions over strings as probabilistic Turing machines.
  arXiv  Detail & Related papers  (2024-06-20T10:59:02Z)
• Approximation of relation functions and attention mechanisms [2.5322020135765464]
  Inner products of neural network feature maps arise as a method of modeling relations between inputs. This work studies the approximation properties of inner products of neural networks.
  arXiv  Detail & Related papers  (2024-02-13T23:53:47Z)
• Nonparametric Partial Disentanglement via Mechanism Sparsity: Sparse Actions, Interventions and Sparse Temporal Dependencies [58.179981892921056]
  This work introduces a novel principle for disentanglement we call mechanism sparsity regularization. We propose a representation learning method that induces disentanglement by simultaneously learning the latent factors. We show that the latent factors can be recovered by regularizing the learned causal graph to be sparse.
  arXiv  Detail & Related papers  (2024-01-10T02:38:21Z)
• Going Beyond Neural Network Feature Similarity: The Network Feature Complexity and Its Interpretation Using Category Theory [64.06519549649495]
  We provide the definition of what we call functionally equivalent features. These features produce equivalent output under certain transformations. We propose an efficient algorithm named Iterative Feature Merging.
  arXiv  Detail & Related papers  (2023-10-10T16:27:12Z)
• Probabilistic unifying relations for modelling epistemic and aleatoric uncertainty: semantics and automated reasoning with theorem proving [0.3441021278275805]
  Probabilistic programming combines general computer programming, statistical inference, and formal semantics. ProbURel is based on Hehner's predicative probabilistic programming, but there are several obstacles to the broader adoption of his work. Our contributions include the formalisation of relations using Unifying Theories of Programming (UTP) and probabilities outside the brackets. We demonstrate our work with six examples, including problems in robot localisation, classification in machine learning, and the termination of probabilistic loops.
  arXiv  Detail & Related papers  (2023-03-16T23:36:57Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)
• A supervised learning algorithm for interacting topological insulators based on local curvature [6.281776745576886]
  We introduce a supervised machine learning scheme that uses only the curvature function at the high symmetry points as input data. We show that an artificial neural network trained with the noninteracting data can accurately predict all topological phases in the interacting cases. Intriguingly, the method uncovers a ubiquitous interaction-induced topological quantum multicriticality.
  arXiv  Detail & Related papers  (2021-04-22T18:00:00Z)
• Adding machine learning within Hamiltonians: Renormalization group transformations, symmetry breaking and restoration [0.0]
  We include the predictive function of a neural network, designed for phase classification, as a conjugate variable coupled to an external field within the Hamiltonian of a system. Results show that the field can induce an order-disorder phase transition by breaking or restoring the symmetry. We conclude by discussing how the method provides an essential step toward bridging machine learning and physics.
  arXiv  Detail & Related papers  (2020-09-30T18:44:18Z)
• The role of feature space in atomistic learning [62.997667081978825]
  Physically-inspired descriptors play a key role in the application of machine-learning techniques to atomistic simulations. We introduce a framework to compare different sets of descriptors, and different ways of transforming them by means of metrics and kernels. We compare representations built in terms of n-body correlations of the atom density, quantitatively assessing the information loss associated with the use of low-order features.
  arXiv  Detail & Related papers  (2020-09-06T14:12:09Z)
• Geometric Formulation for Discrete Points and its Applications [0.0]
  We introduce a novel formulation for geometry on discrete points. It is based on a universal differential calculus, which gives a geometric description of a discrete set by the algebra of functions.
  arXiv  Detail & Related papers  (2020-02-07T01:12:57Z)

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.