Algebraic Signatures for Structural Learning in Probability Tensors

• URL: http://arxiv.org/abs/2607.18817v1
• Date: Tue, 21 Jul 2026 07:54:12 GMT
• Title: Algebraic Signatures for Structural Learning in Probability Tensors
• Abstract summary: This paper studies the inverse problem: identifying probabilistic structure from vanishing binomials observed in empirical probability tensors.<n>We treat the vanishing binomials of a toric model as its algebraic signature, and turn the ideal-variety correspondence of algebraic statistics into an operational procedure for structural learning.
• Score: 2.5489046505746704
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Algebraic statistics characterizes statistical models through polynomial constraints, but it has mainly been used for analytically specified model classes. This paper studies the inverse problem: identifying probabilistic structure from vanishing binomials observed in empirical probability tensors. We treat the vanishing binomials of a toric model as its algebraic signature, and turn the ideal-variety correspondence of algebraic statistics into an operational procedure for structural learning that identifies a model by signature matching without parameter estimation. By restricting attention to a computationally tractable class of configuration matrices, which we call {\it the Kronecker-stack class}, we make these signatures explicitly enumerable. Within this class we define minimum invariant constraint (MIC) as the atomic unit characterizing each signature and generalizing the notion of independence. We tested this approach employing MICs on synthetic data as well as on corpus-scale real language data. The results suggested the utility of the method, revealing that the identified rank-one structures correspond to interpretable sets of words. These results open up a new avenue for applying algebraic statistics to computational linguistics.

Related papers

• Statistical and structural identifiability in representation learning [31.990445585569688]
  We formalize two distinct concepts: statistical identifiability and structural identifiability.<n>We prove a statistical $$-near-identifiability result for the representations of models with nonlinear decoders.<n>With additional assumptions on the data-generating process, statistical identifiability extends to structural identifiability.
  arXiv  Detail & Related papers  (2026-03-12T14:19:58Z)
• Constructions are Revealed in Word Distributions [13.67250184093456]
  Construction grammar posits that constructions, or form-meaning pairings, are acquired through experience with language.<n>How much information about constructions does this distribution actually contain?<n>We use a RoBERTa model as a proxy for this distribution and hypothesize that constructions will be revealed within it as patterns of statistical affinity.
  arXiv  Detail & Related papers  (2025-03-08T04:22:28Z)
• The Foundations of Tokenization: Statistical and Computational Concerns [51.370165245628975]
  Tokenization is a critical step in the NLP pipeline.<n>Despite its recognized importance as a standard representation method in NLP, the theoretical underpinnings of tokenization are not yet fully understood.<n>The present paper contributes to addressing this theoretical gap by proposing a unified formal framework for representing and analyzing tokenizer models.
  arXiv  Detail & Related papers  (2024-07-16T11:12:28Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• Function Classes for Identifiable Nonlinear Independent Component Analysis [10.828616610785524]
  Unsupervised learning of latent variable models (LVMs) is widely used to represent data in machine learning. Recent work suggests that constraining the function class of such models may promote identifiability. We prove that a subclass of these transformations, conformal maps, is identifiable and provide novel theoretical results.
  arXiv  Detail & Related papers  (2022-08-12T17:58:31Z)
• Low-Rank Constraints for Fast Inference in Structured Models [110.38427965904266]
  This work demonstrates a simple approach to reduce the computational and memory complexity of a large class of structured models. Experiments with neural parameterized structured models for language modeling, polyphonic music modeling, unsupervised grammar induction, and video modeling show that our approach matches the accuracy of standard models at large state spaces.
  arXiv  Detail & Related papers  (2022-01-08T00:47:50Z)
• Test Set Sizing Via Random Matrix Theory [91.3755431537592]
  This paper uses techniques from Random Matrix Theory to find the ideal training-testing data split for a simple linear regression. It defines "ideal" as satisfying the integrity metric, i.e. the empirical model error is the actual measurement noise. This paper is the first to solve for the training and test size for any model in a way that is truly optimal.
  arXiv  Detail & Related papers  (2021-12-11T13:18:33Z)
• Learning with Density Matrices and Random Features [44.98964870180375]
  A density matrix describes the statistical state of a quantum system. It is a powerful formalism to represent both the quantum and classical uncertainty of quantum systems. This paper explores how density matrices can be used as a building block for machine learning models.
  arXiv  Detail & Related papers  (2021-02-08T17:54:59Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers. We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model. Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
  arXiv  Detail & Related papers  (2020-06-22T21:12:31Z)
• An Epistemic Approach to the Formal Specification of Statistical Machine Learning [1.599072005190786]
  We introduce a formal model for supervised learning based on a Kripke model. We then formalize various notions of the classification performance, robustness, and fairness of statistical classifiers.
  arXiv  Detail & Related papers  (2020-04-27T12:16:45Z)
• A Complete Characterization of Projectivity for Statistical Relational Models [20.833623839057097]
  We introduce a class of directed latent graphical variable models that precisely correspond to the class of projective relational models. We also obtain a characterization for when a given distribution over size-$k$ structures is the statistical frequency distribution of size-$k$ sub-structures in much larger size-$n$ structures.
  arXiv  Detail & Related papers  (2020-04-23T05:58:27Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  In [1], an ensemble of randomly projected linear discriminants is used to classify datasets. We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator. We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
  arXiv  Detail & Related papers  (2020-04-17T12:47:04Z)

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.