Tropical Geometry of Statistical Models

Algebraic statistics

• Graphical models are represented as algebraic varieties whose observed probabilities are polynomial functions of model parameters.Directed graphical models use transition-matrix parameters, and each observed probability is a polynomial of degree equal to the number of graph edges.Source: §1 · pp. 1–2

Tropical geometry

• Tropicalization replaces (+,×) with (min,+), producing a piecewise-linear model in logarithmic probability coordinates.This transformation captures the behavior of joint probabilities after taking negative logarithms.Source: §1 · p. 1

Inference problems

• Standard sum-product efficiently computes marginal and MAP quantities for individual probability coordinates, but not their dependence on parameters across the model.The paper therefore distinguishes ordinary inference from parametric inference, which analyzes how inference varies with parameters.Source: §1 · p. 2

Parametric questions

• The paper studies parameter identification, parameter regions selecting the most likely hidden explanation, polynomial invariants, and tropicalizations of graphical models.These questions include finding parameters yielding the same observed probabilities and parameters for which specified hidden data are most likely.Source: §1 · p. 2

Contributions

• Its primary algorithmic result is an efficient polytopal analogue of sum-product for parametric inference, based on complexity estimates for Newton polytopes.The framework is demonstrated on hidden Markov models and the general Markov model on a binary tree.Source: §1 · p. 2

HMM representation

• An HMM maps d=k(k+l) parameters to l^n observed probabilities, with coordinate polynomials bi-homogeneous of degree n−1 in transitions and n in emissions.The model uses a uniform initial distribution and homogeneous transition and emission matrices, while nonnegativity and row-sum constraints are disregarded for simplicity.Source: §2 · p. 3
• For the binary length-three example, the parameter and probability spaces are both R8, and each observed probability is a polynomial obtained by summing over hidden-state sequences.The hidden Markov model image is characterized by a quartic polynomial invariant computed using a Gröbner basis.Source: §2 · pp. 3–4

Tropical HMM

• Tropicalizing the HMM map replaces products with sums and sums with minima, so the minimum selects the Viterbi hidden sequence for fixed observations and parameters.The resulting piecewise-linear map solves the MAP inference problem in logarithmic coordinates.Source: §2 · p. 4

Newton polytopes

• For fixed observations, parameter regions selecting a Viterbi sequence are normal cones at vertices of the coordinate polynomial’s Newton polytope.In the binary example, this polytope is 4-dimensional with 8 vertices, and its normal fan describes the solution to the corresponding parametric inference problem.Source: §2 · p. 4

All observations

• Considering all observations simultaneously yields a 5-dimensional Newton polytope with 398 vertices, whose associated 398 cones form the parametric solution.The tropical HMM is the union of their piecewise-linear images; the selected cone maps to a 7-dimensional cone, while most others map to lower-dimensional cones.Source: §2 · p. 4

Positivity and tropical morphisms

• Surjective positivity makes the tropical morphism image equal the positive tropical variety; positivity alone guarantees only containment, generally without a polyhedral-subcomplex structure.The image is always a fan contained in the tropical variety, while surjective positivity gives exact equality.Source: §3 · p. 5

Newton polytopes

• The tropical morphism is piecewise linear because each coordinate’s support function is linear on cones of its Newton polytope’s normal fan.The normal fan of the Minkowski-sum Newton polytope is the common refinement of the coordinate normal fans.Source: §3 · p. 5

Examples

• A linear-map example shows that a positive tropical variety can contain an entire four-cycle while the tropical morphism image covers only part of one edge.The image consists of vectors (a,a,b,c) with a ≤ b ≤ c, covering only half of the edge indexed by ⟨p1 −p2⟩.Source: §3 · p. 6

Naive Bayes model

• For the two-feature naive Bayes model, the parameterization is surjectively positive and its ideal is generated by the 3×3-subdeterminants.The model consists of k × l matrices of rank at most 2, and its Newton polytope is a zonotope associated with Kk,l.Source: §3 · pp. 6–7
• For the 3×3 determinant, the positive tropical variety is the nine-quadrangle subcomplex of the tropical complex and is a torus.The full complex has six triangles and nine quadrangles and is the 2-skeleton of a product of two triangles.Source: Figure 2 · p. 7, §3 · p. 8
• In the 3×3 case, the Newton polytope has 230 vertices, but 68 corresponding cones are rank-deficient and 162 map onto the torus’s nine quadrangles.The general fiber involves 18 cones, distributed as eight with 5 facets, eight with 6, and two with 9.Source: §3 · p. 8

• Explanations for a fixed observation correspond to vertices of NP(f_σ), while inference functions correspond to vertices of the Newton polytope of the full map f.Source: §4 · p. 8
• The full tropical variety is infeasible to compute when observations grow, but coordinate Newton polytopes provide efficiently computable information about its piecewise-linear coordinate functions.Source: §4 · p. 8
• Theorem 7 bounds the vertices of NP(f_σ) polynomially when the parameter count is fixed, with edge count E typically growing linearly in n.Source: §4 · p. 9
• For homogeneous HMMs, each fixed observation has at most Ck,l · n^k(k+l) explanations, including the binary bound C · n^10/3.Source: §4 · p. 9
• The number of inference functions is at most lnCdEd−1, so it grows singly exponentially in model complexity rather than matching the doubly exponential space of all Boolean functions.Source: §4 · p. 9
• Polytope propagation computes Newton polytopes recursively through the sum-product decomposition, and its efficiency follows when sum-product is fast and the polytopes have few vertices.Source: §4 · p. 9

• The general Markov model on a binary tree is represented by a multilinear polynomial map whose coordinates sum over hidden node colorations consistent with the observed leaves.Source: §5 · p. 10
• The proposed phylogenetic invariants are 3×3 determinants of flattenings associated with tree-edge splits, stated as Conjecture 13 for binary variables.Source: §5 · p. 11
• Conjecture 14 characterizes the tropical and positive tropical varieties through flattenings with tropical and Barvinok rank at most 2, respectively.Source: §5 · p. 11
• The sum-product algorithm evaluates the tree model in linear time despite exponentially many terms, and tropical arithmetic replaces ordinary operations for ancestral reconstruction.Source: §5 · p. 11
• With unrestricted edge-specific parameters, Newton-polytope vertex counts grow exponentially, motivating homogeneous models with identical transition matrices across edges.Source: §5 · p. 12
• For homogeneous tree models, each coordinate Newton polytope has at most a constant times nl^2−1 vertices, enabling efficient parametric ancestral reconstruction.Source: §5 · p. 12

• Graphical-model probabilities are coordinates on an algebraic variety, while MAP probabilities after logarithmic transformation are coordinates on its positive tropical part.Source: §6 · p. 12
• The sum-product algorithm evaluates coordinates on both the ordinary variety and the tropical variety by using the corresponding arithmetic operations.Source: §6 · p. 12
• Explanations are Newton-polytope vertices, and normal fans of coordinate polytopes solve the parametric inference problem when vertex counts remain polynomial.Source: §6 · p. 12
• Inference functions encode parameter-dependent MAP choices over all observations and correspond to vertices of the larger Newton polytope of f.Source: §6 · p. 12
• Polytope propagation has applications to biological sequence analysis and includes existing parametric alignment methods as special cases for pair hidden Markov models.Source: §6 · p. 12
• Newton polytopes can also support Bayesian computations by defining maximal cones over which parameter priors are integrated.Source: §6 · p. 13