The Gaussian conditional independence inference problem

Abstract

Die vorliegende Dissertation beschäftigt sich mit Strukturen Gaußscher bedingter Unabhängigkeit und ihrem Inferenzproblem. Bedingte Unabhängigkeit (engl. conditional independence, CI) ist ein Begriff aus der Wahrscheinlichkeits- und Informationstheorie und “Gaußsch” bezieht sich auf die bekannte multivariate Normalverteilung. Die CI-Relation einer multivariaten Zufallsvariable , deren Komponenten durch eine endliche Menge N indiziert sind, enthält Informationen darüber, welche Komponenten I die Verteilung anderer Komponenten J beeinflussen, wenn der Wert wieder anderer Komponenten K bekannt ist. Diese Relation wird als [ I ?? J j K] oder kurz (I; JjK) geschrieben. Bedingte Unabhängigkeit ist also eine dreiwertige Relation auf Teilvektoren von , die komplexe Abhängigkeiten zwischen den Variablen in kodiert. CI-Relationen werden formal in einem Zweig der künstlichen Intelligenz über logische Inferenzregeln studiert. Solche Inferenzregeln nehmen die folgende Form an: “wenn bestimmte bedingte Unabhängigkeiten gelten, welche (Disjunktionen von) anderen Unabhängigkeiten müssen ebenfalls gelten?” Kenntnis dieser Regeln erlaubt die automatische Deduktion von Informationen über die Abhängigkeitsstruktur von beobachteten Zufallsvariablen. Die Regeln, welche für CI-Relationen gelten, hängen von der Art der Wahrscheinlichkeitsverteilung ab. Binäre Verteilungen erfüllen beispielsweise andere Inferenzregeln als die kontinuierlichen Gaußschen Verteilungen. Eine multivariat Gauß-verteilte Zufallsvariable ist vollständig durch ihre Parameter, den Mittelwert 2 RN und die Kovarianzmatrix Σ 2 PDN, bestimmt. Unter dieser speziellen Annahme ist die bedingte Unabhängigkeitsaussage [ I ?? J j K] äquivalent zu einer Rangbedingung an die Teilmatrix von Σ mit Zeilen I [ K und Spalten J [ K, nämlich dass diese Matrix Rang jKj hat. Dieses Kriterium erlaubt die Behandlung von Gaußscher CI mit Mitteln der kommutativen Algebra, da die Rangbedingung als das Verschwinden einer Reihe von Polynomen in den Einträgen von Σ formuliert werden kann. Das Inferenzproblem wird dann zu einer Frage über die Geometrie spezieller reeller Varietäten innerhalb des Kegels des positiv-definiten Matrizen. Diese Dissertation behandelt das Gaußsche CI-Inferenzproblem aus kombinatorischer, logischer und geometrischer Sicht. Der Inhalt eines jeden Kapitels wird im Folgenden kurz zusammengefasst. Kapitel 1 gibt eine Einführung in die Theorie der Strukturen der bedingten Unabhängigkeit im Allgemeinen und von Gaußverteilungen im Besonderen. Elementare Reduktionen der allgemeinen Situation werden hergeleitet und es wird eine Übersicht über frühere Resultate über Gaußsche bedingte Unabhängigkeit gegeben. Kapitel 2 enthält eine Exposition der Werkzeug aus der Logik, Algebra, Geometrie und Informationstheorie, die wiederholt in der gesamten Arbeit oder in einigen Teilen davon benutzt werden. Kapitel 3 führt eine Verallgemeinerung von Gaußschen CI-Relationen auf allgemein Körper ein und gibt elementare Resultate über ihre Struktur, insbesondere werden die Gaussoid- Axiome hergeleitet. Das Inferenzproblem wird in eine geometrische Sprache übersetzt und die Existenz von finalen Polynomen als Korrektheitsbeweise für CI-Inferenzregeln wird bewiesen. Kapitel 4 setzt den Fokus auf algebraische Konstruktionen Gaußscher CI-Relationen über unendlichen Körpern. Das wichtigste Werkzeug ist ein sogenanntes Transferprinzip, das es erlaubt Konstruktionen von Gaußverteilungen über rationalen Funktionenkörpern auf den Grundkörper zurückzuziehen. Diese Technik wird verwendet um neue Ergebnisse über die Struktur von Gaußschen CI-Relationen zu beweisen. Es folgt, dass die wahren Inferenzregeln für Gaußverteilungen keine endliche, vollständige Axiomatisierung haben, jedoch folgen alle wahren Inferenzregeln mit höchsten zwei Voraussetzungen aus den Gaussoid- Axiomen. Endliche Axiomatisierungen über den zwei kleinsten endlichen Körpern werden hergeleitet, was zeigt dass die Annahme der Unendlichkeit des Körpers signifikant ist. Es wird ein Analogon von Rotas Vermutung aus der Matroidtheorie aufgestellt. Kapitel 5 widmet sich der Komplexität des Inferenzproblems im für die Statistik gewöhnlichen Rahmen der reellen Zahlen. Aufbauend auf einer Kodierung der von-Staudt-Konstruktionen in der projektiven Geometrie werden drei Universalitätssätze bewiesen, die zeigen dass diese Aufgabe schwer ist, im algorithmischen Sinne (sie ist vollständig für die existentielle Theorie der reellen Zahlen), algebraisch (alle reellen algebraischen Zahlen werden benötigt um Gegenbeispiele für falsche Inferenzen hinzuschreiben), sowie, für eine orientierte Version des Inferenzproblems, topologisch (die Mengen der Gegenbeispiele zu falschen Inferenzregeln können alle Homotopie-Typen von primären semialgebraischen Mengen annehmen). Das algebraische Universalitätsresultat beantwortet eine Frage von Petr Šimeček aus dem Jahr 2006 über rationale Punkte auf Gaußschen CI-Modellen. Kapitel 6 gibt eine Einführung in eine allgemeine Maschinerie, die aus polynomiellen Relationen auf Unterdeterminanten einer symmetrischen Matrix valide Inferenzregeln erzeugt. Diese Technik wird auf zwei Klassen von polynomiellen Relationen angewendet, was in den Gaussoid- (und den orienteriten Gaussoid-) sowie, respektive, den Semimatroid-Axiomen resultiert. Letztlich wird gezeigt, dass Gaußverteilungen die aus der Informationstheorie stammende Eigenschaft der Selbstadhäsivität haben, welche auf eine Klasse von Inferenzaxiomen angewendet werden kann um potentiell stärkere Axiome zu erzeugen. Trotz der algorithmischen Komplexität des Inferenzproblems im Allgemeinen, sind diese Axiome mithilfe des booleschen Erfüllbarkeitsproblems und linearer Programmierung schnell auffindbar. Über rechnergestützte Resultate basierend auf einer Softwareimplementierung dieser Methoden wird berichtet. Kapitel 7 fasst die Hauptresultate der Arbeit knapp zusammen und weist auf offene Fragen und künftige Forschungsrichtungen hin.

The present thesis deals with Gaussian conditional independence structures and their inference problem. Conditional independence (CI) is a notion from statistics and information theory and “Gaussian” refers to the familiar multivariate normal distribution. The conditional independence relation of a multivariate random variable whose components are indexed by a finite set N gives information about which components I influence the distribution of other components J given that yet other components K have been observed. This relation is denoted by [ I ?? J j K] or just (I; JjK) for short. Thus, CI is a ternary relation on subvectors of which encodes complicated dependencies among the variables of . Conditional independence relations are formally studied in branches of artificial intelligence by means of logical inference rules. Such inference rules take the form of “given that some conditional independences hold, which other (disjunctions of) conditional independences must also hold?” Knowing these rules allows the reasoning about dependencies among observed random variables to be automated. The rules which are valid for CI relations depends on the kind of probability distribution under consideration. Binary distributions, for example, satisfy different inference rules than the continuous Gaussian distributions. A multivariate Gaussian random variables is completely given by its two parameters, the mean 2 RN and its covariance matrix Σ 2 PDN. In this special setting, the conditional independence statement [ I ?? J j K] is equivalent to a rank condition on the submatrix of Σ whose rows are I[K and whose columns are J[K, namely it must have rank jKj. This criterion makes Gaussian conditional independence amenable to methods of commutative algebra because the rank condition can be formulated as the vanishing of a number of polynomials in the entries of Σ. The inference problem then becomes a question of the geometry of certain real varieties inside of the cone of positive-definite matrices. This thesis studies the Gaussian conditional independence inference problem from a combinatorial, logical and geometric point of view. The content of each chapter is briefly summarized as follows. Chapter 1 gives an introduction to the theory of conditional independence structures in general and of Gaussians in particular. Elementary simplifications of the general setting are derived and previous results on Gaussian CI are surveyed. Chapter 2 is an exposition of tools from logic, algebra, geometry and information theory which are used throughout or in various parts of the thesis. Chapter 3 introduces a generalization of Gaussian CI relations to to arbitrary fields and provides elementary results on their structure, including a derivation of the gaussoid axioms. The inference problem is cast into geometric language and the existence of final polynomials proofs for the validity of CI inference rules is proved. Chapter 4 shifts the focus to algebraic constructions for Gaussian CI relations which are valid over infinite fields. The main tool is a so-called transfer principle which allows constructions of Gaussian distributions in rational function field extensions to be carried back into the base field. This technique is used to prove new results on the structure of Gaussian CI relations which are specific to infinite fields. It follows that the valid inference rules for Gaussian have no finite complete axiomatization, but all inference rules with at most two antecedents follow from the gaussoid axioms. Finite axiomatizations are given for the two smallest finite fields, showing that the assumption of infinite cardinality matters. An analogue of Rota’s conjecture in matroid theory is posed. Chapter 5 studies the complexity of the inference problem in the usual statistical setting over the real numbers. Based on an encoding of the von Staudt constructions from projective geometry, three universality theorems are proved which show that this problem is hard algorithmically (it is complete for the existential theory of the reals), algebraically (all real algebraic numbers are necessary to prove the invalidity of proposed inference rules for Gaussians), and an oriented variant of the inference problem is hard topologically (the set of counterexamples to an invalid inference rule assumes the homotopy type of any primary semialgebraic set). The algebraic hardness result answers a question posed in 2006 by Petr Šimeček about rational points on Gaussian conditional independence models. Chapter 6 introduces a framework for turning polynomial relations on the subdeterminants of a symmetric matrix into inference rules. This is applied to two classes of polynomial relations which result in the gaussoid (and oriented gaussoid) and semimatroid axioms, respectively. Finally, Gaussians are shown to possess an information-theoretic property called selfadhesivity which can be applied to any set of axioms and potentially derives a stronger set. In spite of the hardness of the general inference problem, these axioms can be found much more quickly using solvers for the boolean satisfiability problem and linear programming. Computational results based on a computer implementation of these methods are shown. Chapter 7 gives a brief summary of the main results and points out some open questions and future directions.