A toric model is a discrete exponential family whose sufficient statistics are integer vectors: , a monomial in the parameters. As a factor it is a log-linear potential over discrete channels, and every slot of the statistical game is exact: messages are finite sums, the free energy is closed-form, the likelihood is concave with a moment-matching optimum, and the model’s implicit equations are known binomials. It is the easiest member of the algebraic family to build, and it is implemented as
AlgebraicFactors.ToricFactorover several discrete variables (§1.1–§1.7: finite sums, Newton/IPF fitting, positive membership and supplied binomials; fitting and membership checks are recorded in fit). L-SPEC-004 Algebraic Factors Toric and Grassmannian is the plan.
Sources: Sullivant, Algebraic Statistics, AMS GSM 194, 2018; Drton, Sturmfels & Sullivant, Lectures on Algebraic Statistics, 2009; Sturmfels, Gröbner Bases and Convex Polytopes, AMS ULECT 8, 1996; Diaconis & Sturmfels, Algebraic Algorithms for Sampling from Conditional Distributions, Ann. Statist. 26(1), 1998; Geiger, Meek & Sturmfels, On the Toric Algebra of Graphical Models, Ann. Statist. 34(3), 2006; Lauritzen, Graphical Models, 1996; Darroch & Ratcliff, Generalized Iterative Scaling for Log-Linear Models, Ann. Math. Statist. 43(5), 1972; Fienberg & Rinaldo, Maximum Likelihood Estimation in Log-Linear Models, Ann. Statist. 40(2), 2012; Craciun, Dickenstein, Shiu & Sturmfels, Toric Dynamical Systems, J. Symbolic Comput. 44(11), 2009; the factor-level statements are derivations original to this vault; code:
lib/AlgebraicFactors.jl/src/toric.jl,fit.jl; enumeration, tree-BP, closed-form fitting and membership checks inlib/AlgebraicFactors.jl/test/runtests.jl.Bibliography: Sullivant 2018 · Drton et al. 2009 · Sturmfels 1996 · Diaconis & Sturmfels 1998 · Geiger et al. 2006 · Lauritzen 1996 · Darroch & Ratcliff 1972 · Fienberg & Rinaldo 2012 · Craciun et al. 2009
Theory (CT-ML wiki): Statistical Game · Conditional Independence
The model
Let the factor’s channels be discrete variables with finite alphabets, and let range over the joint states (the product of the alphabets). A design matrix gives each state a column . With natural parameter ,
With this is , a monomial: hence toric. The model is the closure of in the probability simplex.
- Independence of two variables with alphabets : , and stacks the indicator of row and the indicator of column .
- Hierarchical log-linear models: one block of rows per generator (a set of variables), each the indicator of ‘s cell in that generator’s marginal table. Discrete undirected graphical models are the case whose generators are the cliques; their positive part is toric (Geiger, Meek & Sturmfels 2006). Bayesian networks with hidden variables are not toric in general; see Algebraic Statistics Bridge §“The semialgebraic gap”.
A gauge, again. iff : the parameter is identified only modulo that subspace, which contains the null space of and, when is in the row space of , a constant-logit shift. As for The Parameter is a Grassmannian, the identifiable parameter is a quotient; independent logit differences are a chart. For the unnormalised potential in a graph, a constant-logit shift rescales the potential and shifts its energy by a constant.
The all-ones vector. Several statements below need in the row space of (constant nonzero column sums suffice). For arbitrary , replace by throughout; this does not change the model.
Its implicit equations are binomials
When lies in the row space of , is the simplex part of the variety of the toric ideal
(Sturmfels 1996; Sullivant 2018). For independence these are the minors of Algebraic Statistics Bridge. So the two views of an algebraic factor, a relation and a statistical model, coincide here with the relation known in closed form: no nullspace fit is needed to find it.
Two practical points:
- A finite set of integer moves is a Markov basis iff its binomials generate ; Diaconis & Sturmfels (1998) use one to sample tables with fixed sufficient statistics (exact conditional tests). A lattice basis of is in general not a Markov basis, and computing one needs specialised software (4ti2 and similar).
- Membership needs no generators. For positive (and in the row space of ): iff lies in the row space of , a linear least-squares test (derivation: ; conversely gives , since sums to one).
As a factor every slot is exact
The factor’s potential is in a graph (the graph’s partition function normalises), and when the factor stands alone as a game. All derivations:
- Pointwise energy: , plus when normalised; scalar.
- Message to a channel : , an exact categorical belief, with clamped channels entering as indicators. The cost is per message, exponential in the factor’s arity as for any table factor; a hierarchical model is better split into one factor per generator, which is a junction-tree question (LP-010 Where the graph of a problem comes from).
- Bethe term: with the factor belief , the energy part is and the entropy part , both finite sums.
- Learning: for counts with total , . is convex, so the log-likelihood is concave; its Hessian is . Birch’s theorem: for there is a unique (the closure) with , the extended MLE (Sullivant 2018; Fienberg & Rinaldo 2012, Theorem 9 in the numbering of arXiv:1104.3618). The ordinary MLE, at a finite , exists iff is strictly positive, equivalently iff lies in the relative interior of the convex hull of the columns (Fienberg & Rinaldo 2012: Theorem 9 states it as a facial-set condition on the marginal cone, Theorem 13 for general exponential families as in the relative interior of the convex support). So zero counts can make it fail: for independence on a full table it fails exactly when a row or column total is zero, and the extended MLE is still the outer product of the empirical margins. (Counterexample to the cone version: , .)
- Algorithms: iterative proportional fitting for hierarchical models; generalised iterative scaling (Darroch & Ratcliff 1972), which needs non-negative features with constant positive column sums (a correction row is added when they are not); Newton with the Hessian above, after removing the gauge directions.
- Implemented fitting:
fit_mleremoves the full gauge and returns a finite minimum-norm parameter; moment convergence is separate from:exists(all-positive counts only),:suspected_boundary(a numerical heuristic) or:unknown.convergedcan hold at an approximation to the extended MLE without a finite-MLE certificate.inmodeluses the augmented row space;binomial_residualschecks supplied integer moves exactly. See fit for the IPF endpoint approximation and the small-table tests. - Closed form: for a decomposable graphical model with strictly positive empirical clique margins, the MLE is , one separator factor per edge of a junction tree (Lauritzen 1996); for the extended MLE, states with a zero separator margin get probability zero. On the junction tree the entropy is exactly ; the Bethe counting on the original variables need not be exact for the clique factorisation. A test oracle, and the setting of RQ-004 Is the Bethe Criterion Consistent for Structure Learning.
Why it is the easy case
Against Open Problems in Algebraic Implicit Learning:
| problem there | for a toric factor |
|---|---|
| §1 the real locus may be tiny | the positive part is the image of a parametrisation: nonempty, of dimension |
| §2 the wall | the support is the columns of , chosen by the model’s structure |
| §4 model selection jumps between manifolds | it is the choice of generators, i.e. classical log-linear model selection; still discrete |
| §5 approximate vanishing ideals | not needed: the ideal is known |
| §7 the discriminant | none: is smooth, and injective modulo the gauge |
What it does not escape: tables grow exponentially with arity, and Markov bases can be large.
Beyond tables
For a mass-action reaction network whose rate constants admit a complex-balanced equilibrium, the strictly positive steady states are the positive points of a toric variety (Craciun, Dickenstein, Shiu & Sturmfels 2009, Theorem 7 in the numbering of arXiv:0708.3431); boundary steady states are not covered. A route from this note to Differential Algebra and DAE Factors. Not planned yet.
Related: Algebraic Statistics Bridge, Algebraic Implicit Learners, The Algebraic Factor as a Statistical Game, Grassmann Mixing and Plücker Coordinates, L-SPEC-004 Algebraic Factors Toric and Grassmannian