{'fraction_non_alphanumeric': 0.03152341739577972, 'fraction_numerical': 0.0053182364041859664, 'mean_word_length': 4.667719980554205, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Algebra in probabilistic reasoning

This short expository paper outlines applications of computer algebra to the implication problem of conditional independence for Gaussian random variables. We touch on certificates for validity and invalidity of inference rules from the perspective of reproducibility of research data, computational complexity of the inference problem and draw a parallel to automated theorem proving in synthetic geometry.

Probabilistic reasoning is an approach, based on probability theory, to tasks of decision making under uncertainty. Random variables are used to model our uncertainty about the factors that define what a good decision is. Decision making (certain or uncertain) is a vast field with different paradigms. For example, one may seek to make the globally least bad decision given what is known certainly about the state of the random variables.
In probably approximately correct learning, on the other hand, one tries to keep the errors small, most of the time.
Another part of probabilistic reasoning is concerned with conditional independence. This is a ternary relation among jointly distributed random variables which gives information of the following sort: "Given that factor C is observed, factor A does not influence factor B". This relation is denoted by [A ⊥ ⊥ B | C]. We can also choose to condition on multiple observed variables or none at all and recover the familiar notion of stochastic independence [A ⊥ ⊥ B]. Conditional independence (in the following abbreviated to CI) is an extension of stochastic independence which can accomodate a priori knowledge that we may have about the outcome of a subsystem C of random variables, such as when C is controlled in a random experiment. CI reveals essential combinatorial information that can guide decision making when only incomplete data about the state of a system is available.
As a first exercise in conditional independence, note what this relation specializes to when A = B. Suppose the outcome C is known and [A ⊥ ⊥ A | C] holds. Then the outcome of A has no bearing on itself after we observe C. This is absurd, unless C reveals everything there is to know about A, i.e., A takes only a single value that depends on the value C takes. This is known as a functional dependence (FD) and it implies the existence of a function f such that A = f (C) as random variables.
CI and FD provide basic qualitative information about dependencies among the observations made in, say, a random experiment in the sciences. But they play a role in other disciplines that deal with the representation or processing of information. For example, a database in relational algebra may be seen as a (large) sample from an unknown discrete probability distribution. The designer of a database will usually anticipate CI and FD relations in the data (e.g., your zip code functionally determines your city). The purpose of various normal forms for relational databases is to eliminate undesirable dependencies because they increase the risk of inconsistencies in the data after updates. Instead, the database must be factored into multiple "tables" according to the normal form. In spirit, what these normal forms demand is similar to the factorization of a rank-1 matrix into an outer product If M is the probability matrix of the joint distribution of discrete random variables A and B, then a and b are uniquely determined up to a scalar as the row and column sums of M and they correspond to the marginal distributions of A and B. (With more than two random variables, we factor a rank-1 tensor.) This representation of M as ab T makes maintaining the independence of A and B in the joint distribution automatic under updates to the marginal distributions a and b, and it saves space!

Synthetic statistics
The reasoning task attached to CI is that of conditional independence inference: given a boolean formula ϕ whose variables are CI statements and a family of probability distributions, decide if ϕ is true for every distribution in the family. By writing boolean formulas in conjunctive normal form, one can restrict this investigation to disjunctive clauses written in implication form, such as: This formula is one half of the semigraphoid property and it holds for all random vectors [16, Appendix A.7]. Its meaning should be intuitively clear: suppose that knowing B makes A and C independent, but also that B has no influence on A; then A and C must be independent even without knowledge of B. One should be cautious, however, of leaping to "intuitively clear" conclusions in CI inference because the laws of probability theory sometimes seem to defy intuition. The implications are all wrong. The reader is invited to construct random experiments which falsify them. The semigraphoid property allows us to deduce with absolute confidence from some CI assumptions other CI consequences, no matter what the underlying probability distribution is. A valid implication is also called a CI axiom or inference rule. More restrictions on the distributions under consideration make more valid inference rules available for reasoning. In this article, we will consider multivariate normal distributions. This class has many favorable properties: (1) relatively few parameters are needed to specify a distribution, (2) they include classes of popular graphical models and (3) conditional independence has an algebraic reformulation. Whenever possible we wish to use algebra in reasoning and benefit from the exactness of symbolic methods.
In this article, I want to explain a different point of view on probabilistic reasoning, in particular CI inference. It is motivated by similarities to synthetic geometry [6] which describes geometric objects in relations of "special position" to each other. Figure 1 illustrates Pappus's theorem in the projective plane over a field. This is an inference rule in synthetic geometry stating that: if all points on the solid lines are collinear, then the points on the dashed line must also be collinear. Instead of geometric objects, in probabilistic reasoning we describe random variables and their "special position" in relation to each other. Special position in this case is conditional independence and we wish to obtain rules of reasoning such as Pappus's theorem in this setting -which we may call synthetic statistics.

The geometry of CI inference Algebraic statistics of Gaussian random vectors
We suppose a finite ground set N of size n indexing the entries of a random vector X = (X i : i ∈ N ). Instead of referring to random variables, subsequently we refer to their indices. It is customary not to distinguish between an element i ∈ N and a singleton subset { i } ⊆ N : both are usually denoted by i. Moreover, the symbol for set union I ∪ K for subsets of N is usually omitted. Hence, an expression such as iK means the subset { i } ∪ K ⊆ N . Denote by Sym N (K) the affine space of N × N symmetric matrices over a field K ⊆ R and by PD N (K) the semialgebraic subset of positive definite matrices. Recall that this is a full-dimensional, open convex cone and that its boundary is the hypersurface of singular positive semidefinite matrices.
A regular multivariate normal ("Gaussian") distribution is determined by its mean µ ∈ R N and its covariance matrix Σ ∈ PD N (R). Regularity refers to the covariance matrix Σ which in general only needs to be positive semidefinite. While an algebraic theory of conditional independence can be developed even in the degenerate case, this is more involved and we stick to the regular Gaussians here.
The density of a Gaussian random vector X with respect to the standard Lebesgue measure on R N is a proper transcendental function depending on µ and Σ: A surprising but basic fact of algebraic statistics is that the conditional independence relation among the components of X depends only on certain polynomial expressions in the covariance matrix.
An almost-principal minor is a subdeterminant of the form Σ[ij|K] := det Σ iK,jK for ijK ⊆ N and i, j ∈ K distinct, where iK indexes rows and jK columns.
Sign convention It is advantageous for the general CI theory to view the set N and hence the rows and columns of our matrices as unordered. To still get a welldefined sign for its determinant, it only matters which row and column labels r, c ∈ N are paired together in the k th position from the top-left corner of the matrix. For principal minors Σ[K] and almost-principal minors Σ[ij|K] we establish the following convention: in the principal submatrix with respect to K ⊆ N , pair each k ∈ K with itself, and in the almost-principal submatrix additionally pair row i with column j.
If Σ is the positive definite covariance matrix of the Gaussian random vector X, then the conditional independence The crucial ingredient to prove this is in [18, Proposition 4.1.9]. In particular, the CI relation does not depend on the mean µ and we may identify Gaussian distributions with their positive definite covariance matrices.
Definition 3 A Gaussian CI model is a subset of PD N (R) which is given by vanishing and non-vanishing constraints on almost-principal minors (referred to as the independence and the dependence assumptions of the model, respectively).

Remark 4
It should be noted that in geometry it is (linear) dependence of vectors which corresponds to a Zariski-closed condition, whereas in statistics it is the (conditional) independence which is closed.
Gaussian conditional independence models are subsets of the PD cone which are cut out by very special classes of polynomial constraints. They are all determinantal and, up to the symmetric group on N acting on the coordinates of Sym N (R), there is precisely one principal and one almost-principal minor of each degree.

Conditional independence inference
Consider the general implication formula ϕ: involving CI statements over a fixed ground set N . This formula is a valid inference rule for Gaussians if and only if every Σ ∈ PD N (R) which satisfies Σ[i p j p |K p ] = 0 for all p ∈ [s] also satisfies Σ[x q y q |Z q ] = 0 for at least one q ∈ [t]. We associate to ϕ a CI model M(ϕ) which is defined by the independence assump- . This is the set of counterexamples to ϕ; the implication is valid if and only if M(ϕ) = ∅. Conversely, every CI model is the set of counterexamples to a suitable CI implication formula.
Hence, the CI inference problem is equivalent to the problem of checking if a system of independence and dependence assumptions is consistent, which in turn reduces to checking the feasibility of a semialgebraic set which is defined by integer polynomials -the CI assumptions as well as positive definiteness.

Example 5
The weak transitivity property of Gaussians over N = ijk states that To prove this rule algebraically, we first determine the ideal generated by the assumptions: These vanishing conditions give rise to a hyperplane and a quadratic hypersurface in the space of 3 × 3 correlation matrices, pictured in Figure 2. The equation σ ik σ jk = 0 holds on the intersection, which is the union of two line segments: one for each of the possible conclusions [i ⊥ ⊥ k] ∨ [j ⊥ ⊥ k] of weak transitivity reasoning. The line segments intersect in the identity matrix which satisfies both conclusions. It was observed by Matúš [10] that fundamental inference rules for Gaussians, including a generalization of Example 5 to arbitrary conditioning sets, follow from a single determinantal identity: Matúš's identity Let R be a commutative ring with unity and Σ ∈ Sym N (R). The following identity holds for all ijkL ⊆ N : Remark 6 Matúš's formulation of this result in [10] adds a sign to one of the terms of the identity, depending on the relative ordering of i, j and k. This sign is fixed to +1 by our Sign convention.
Remark 7 Moreover, Matúš proves this identity over the complex numbers, but the extension to any commutative ring is standard. It suffices even to prove the identity only for real positive-definite matrices. Since then the identity is known to hold on a full-dimensional (and therefore dense) subset of the irreducible affine space Sym N (C), it holds for all symmetric matrices over C. But then evaluating the linear combination of determinants in (1) must result in the zero polynomial in Z[Σ] and thus in every commutative ring with unity.
The general weak transitivity property is a simple consequence of this relation and the algebraic definition of conditional independence in Lemma 2. This motivates the investigation of general determinantal identities which can be formulated in terms of principal and almost-principal minors only. More precisely, we consider the polynomial ring R N whose variables are formal brackets . The generators of the quadratic part of J N have been found in [5].
In some way, the Matús identity, which belongs to this generating set, acts like the three-term Grassmann-Plücker relations in geometry. While the latter lead to the definition of matroid as a combinatorial model for geometric special position, the Matúš identity leads to the gaussoid axioms, the most basic inference rules for Gaussian CI relations. The gaussoid axioms satisfy two important completeness results which justify viewing the Matúš identity as fundamental (even though it alone does not generate the quadratic part of J N ).

Proposition 9 ([3])
The gaussoid axioms generate (by logical implication) all true inferences, having at most two assumptions, among any number of Gaussian random variables.
The ideal J N encodes the particular combinatorial flavor of principal and almost-principal minors of symmetric matrices that distinguishes the algebraic geometry of Gaussian conditional independence from that of point configurations and special position which is instead derived from the maximal minors of rectangular matrices. The following conjecture about J N is still open. Its analogue in synthetic geometry is an established theorem stating that the Grassmann-Plücker relations generate the vanishing ideal of the Grassmannian.

Conjecture 10 ([5])
The ideal J N is generated by its quadratic part.

Algebraic certificates and reproducibility
There is no finite axiomatization of all inference rules which are valid for n Gaussian random variables as n grows. The notion of axiomatization can be made precise by introducing minors. In analogy to graph and matroid theory, minors are the "natural subconfigurations" of a collection of random variables. In graph theory, one obtains minors by deleting and contracting edges. In probability theory, we take marginal and conditional distributions. Non-axiomatizability results have been achieved independently byŠimeček [15] and Sullivant [18].
Nevertheless, one may be interested in finding all valid inference rules for small numbers of random variables, so that larger systems can be partially reasoned about, one couple of variables at a time. The case of three Gaussians is covered by the gaussoid axioms. The fourvariate case was solved by Lněnička and Matúš in [9] and the five-variate case is still wide open.
This classification task was posed as Challenge 1 in [5]. Determining the realizability status of the 254 826 candidate gaussoids computed there is equivalent to finding all valid inference rules on five Gaussian random variables. A proper solution to such a large-scale classification task is a FAIR database (cf. [8]) which includes not only the classification itself but also machine-checkable proofs of its correctness. The existence of these proofs is guaranteed by theorems in real algebra. I want to close this exposition by discussing what they are and the obstacles currently faced when computing them in practice.

Algebraic numbers and final polynomials
Let us return to Pappus's theorem for a moment. Call the three points on the upper, the lower and the middle line in Figure 1 a, b, c, then d, e, f and then g, h, i, respectively, from left to right. For brevity denote below the determinant of the 3 × 3 matrix those columns are the homogeneous coordinates of the points labeled p, q, r by the bracket [pqr]. One strikingly mechanic way of proving Pappus's theorem is presented in the following snippet of Macaulay2 code: --Bracket is an abbreviation for --the 3x3 determinant of (p q r). br = (p,q,r) -> det matrix( apply({p,q,r}, x -> apply({1,2,3}, i -> value(toString(x)|"_"|i) ))); --The ideal of collinearity assumptions --for Pappus's theorem.
where the polynomials g i are the elements of the list G in the above code listing. The first polynomial in G is the desired conclusion that g, h and i are collinear.
All other polynomials in G are non-zero because they correspond to non-degeneracy conditions for the point and line configuration in Figure 1. This implies Pappus's theorem because it shows that [ghi] vanishes, under the non-degeneracy conditions, whenever the assumptions of Pappus's theorem are satisfied. The crucial list G for this proof is extracted from the fourth proof of Pappus's theorem in [13,Section 1.3].
The polynomial 20 i=1 g i and the linear combinators h 1 , . . . , h 8 represent a self-contained proof of Pappus's theorem. This proof is big and relatively hard to find but verifying it is a matter of multiplying out both sides of (2) and comparing coefficients. This can be done in any computer algebra system off-the-shelf. This high standard of verifiability is, fortunately, a theorem which extends far beyond Pappus: x n ] has no solution if and only if 0 ∈ I + P + U 2 , where I is the ideal generated by the f i , P is the cone generated by the g j and U is the multiplicative monoid generated by the h k in Z[x 1 , . . . , x n ].
This version of the Positivstellensatz is proved in [2,Proposition 4.4.1]. The condition 0 ∈ I + P + U 2 implies the existence of an integer polynomial f ∈ I ∩ (P + U 2 ). This final polynomial (cf. [6,Section 4.2]) must be simultaneously zero and positive on every point satisfying the polynomial system. It therefore serves as an obvious proof of the emptiness of the semialgebraic set. The coefficients witnessing that f ∈ I and f ∈ P + U 2 constitute the algebraic certificate.
In the context of probabilistic reasoning, we can now certify when the model of counterexamples M(ϕ) of an inference formula ϕ is empty. Hence, we obtain proofs for the validity of true inference rules. On the other hand, if an inference formula is wrong, there must be a counterexample. A famous theorem in model theory implies that this counterexample can be chosen algebraic; see [2,Proposition 5.2.3].
Tarski's transfer principle The semialgebraic set defined by { f i = 0, g j ≥ 0, h k = 0 } is non-empty over some real-closed field if and only if it is non-empty over every real-closed field, in particular the real closure of Q.
The counterexample is a symmetric matrix Σ ∈ Sym N (K) whose entries come from some finite real extension K of Q. By the Primitive element theorem K = Q(α) and all entries of Σ may be represented exactly on a computer as polynomials modulo the minimal polynomial of α. This allows again verification of a claim about the invalidity of an inference formula by off-the-shelf computer algebra systems. In summary: Alternatives in Gaussian CI inference If ϕ is a true inference rule for Gaussians, there exists a final polynomial proof for it with integer coefficients. Otherwise there exists a counterexample to ϕ with real algebraic coordinates.
The Matúš identity is a final polynomial for weak transitivity (and all other gaussoid axioms). For four and more Gaussian random variables, there exist inference rules which are valid but do not follow from the gaussoid axioms. To be precise, for n = 4 there are five of them up to symmetry, for example [9, Lemma 10, eq. (20)] This inference rule is valid for 4 × 4 positive definite matrices. From its proof one can extract the following fact: the bracket polynomial is in the ideal generated by the assumptions of (3). But this polynomial splits into the desired conclusion [ij|∅] and another factor which is a sum of non-negative polynomials at least one of which is positive as a product of principal minors. Hence, [ij|∅] must vanish whenever the assumptions are satisfied by a positive definite matrix.
Notably, counterexamples to (3) exist when positive definiteness is relaxed to allow (indefinite) matrices all of whose principal minors do not vanish. This condition of principal regularity is a natural substitute for positive definiteness over algebraically closed fields. An example is this matrix: This shows that positive definiteness is a crucial feature of our reasoning task. In particular, we may not find all valid inference rules by working in an algebraically closed field and basing all computations on ideals only.

Computation and hardness
The problem of deciding whether a proposed inference formula ϕ is valid for all Gaussian distributions over ground set N reduces the problem of checking if the model of counterexamples M(ϕ) is empty. This is a problem in the existential theory of the reals (ETR) and the associated complexity class of all problems which reduce in polynomial time to ETR is known as ∃R; cf. [14]. This is a fundamental complexity class in computational geometry, polynomial optimization and statistics. We have thus an upper bound on the complexity of the Gaussian CI inference problem.
Unfortunately this upper bound is attained in the complexity-theoretic sense due to a universality result for Gaussian CI models. Similar universality theorems have been known for the realizability of rank-3 matroids [6], 4-polytopes [12] or Nash equilibria of 3-person games [7]. See [4,Chapter 5] for a more thorough discussion.

Theorem 11 ([4])
The Gaussian CI inference problem is co-∃R-complete. This theorem is proved by encoding synthetic geometry in the real projective plane in conditional independence and dependence constraints. Even though CI models are at first glance very special semialgebraic sets, they possess no structure which makes them in general easier to work with than arbitrary semialgebraic sets.
There exist implementations of quantifier elimination over the real numbers via cylindrical algebraic decomposition in computer algebra systems such as Wolfram Mathematica. These methods, when they terminate, decide the emptiness of a semialgebraic set and in the inhabited case they return a real algebraic number certifying this. Software for finding final polynomials does not seem to be readily available but there are recent advances in computing real radical ideals [1].
An even more fundamental obstacle in the tabulation of all valid inference rules among five Gaussian random variables is finding reasonable candidate implications. The following problem should enable an experimental and data-driven approach: Problem 12 Develop (numerical) software for sampling positive definite points uniformly from varieties inside Sym N (R).
Sampling allows to check if a proposed inference formula has any obvious counterexamples. It can also aid in testing candidates for final polynomials, such as the left-hand side in (2) or the expression (4), by evaluating these candidates on sufficiently many samples and checking whether they vanish. Since CI equations are continuous, small numerical errors can be tolerated.