Doctoral thesis

Algebras of gaussian linear information

    23.06.2009

XVI + 354 p

Thèse de doctorat: Université de Fribourg, 2009

English German Gaussian linear information arises in many real-world models of the natural and social sciences. The Gaussian distribution has turned out to appropriately represent uncertainty in many linear models. The main goal of this thesis is to describe and to compare different algebras of Gaussian linear information: Corresponding elements and operations in the various algebras are revealed and the respective computational advantages are highlighted. In order to make large models computationally tractable, they have to be decomposed into independent factors by exploiting sparsity. For such factorisations, valuation algebras provide a general, abstract framework for local computations. A valuation algebra is a two-sorted algebra with three operations: valuations (which may be seen as pieces of information) refer to a domain of interest; valuations can be marginalised (focussed) to a domain of interest, and they may be combined (aggregated). Generic message-passing schemes can be used to answer projection problems. Many problems in applications can be reduced to a projection problem: diagnostic estimation, prediction, filtering, smoothing. For instance, Gaussian densities form a valuation algebra: marginalisation is integration, and combination is multiplication (plus renormalisation). Gaussian densities may be represented by Gaussian potentials or moment matrices, using either the concentration or the variance-covariance matrix, respectively. Here, marginalisation and combination are matrix operations. A conditional Gaussian density is the family of Gaussian densities obtained on the head variables by fixing a value for the tail variables. A conditional Gaussian density corresponds to a Gaussian density on the head variables plus a linear regression on the tail variables. Conditional Gaussian densities can be analysed in three ways: geometric, algebraic and analytic. General Gaussian linear systems lead to Gaussian hints by assumption-based inference. Gaussian hints have focal sets which are parallel linear manifolds of the same dimension in the parameter space. Combination corresponds to intersection of focal sets and marginalisation to projection of focal sets. Gaussian potentials correspond to Gaussian hints whose focal sets are all singletons. Gaussian potentials can be extended to a valuation algebra of quotients which are represented by pairs of Gaussian potentials. Conditional Gaussian densities can be represented in the so-called separative extension of Gaussian potentials. Since a conditional Gaussian density is a quotient function of two Gaussian densities, the concentration matrix in the exponent of the denominator can be subtracted from the concentration matrix in the exponent of the numerator. This leads to a new representation of symmetric Gaussian potentials whose pseudo-concentration matrix is only symmetric but not necessarily positive definite. The main result of these considerations is that different conditional Gaussian densities turn out to be linked to the same Gaussian hints (up to equivalence) if and only if the conditional Gaussian densities are equal up to a constant factor. In other words, Gaussian likelihood functions bear the full information contained in Gaussian hints. This explains why assumption-based reasoning on (over-)determined Gaussian linear systems reproduces the estimation results based on the maximum-likelihood principle. Variables may be linear combinations of other variables. This imposes linear restrictions on the parameter space. In the spirit of assumption-based reasoning, algorithms for inference, the combination and marginalisation are derived for symmetric Gaussian potentials with deterministic equations. Finally, it is shown how Gaussian linear systems can be expressed in the language Abel. Queries on a complex Gaussian linear system can be answered in the Abel system. Several examples illustrate the new approach of symmetric Gaussian potentials. Gauss’sche lineare Information kommt in verschiedenen Modellen der reellen Welt vor, sowohl in den natur- wie auch in den sozialwissenschaftlichen Disziplinen. Mit der Gauss-Verteilung kann Unsicherheit oft adäquat dargestellt werden. Das Ziel dieser Dissertation ist es, verschiedene Algebren Gauss’scher Information zu beschreiben und zu vergleichen: Die einander entsprechenden Elemente und Operationen in den unterschiedlichen Algebren sollen herausgearbeitet und ihre jeweiligen rechentechnischen Vorteile hervorgehoben werden. Damit grosse Modelle computertechnisch behandelt werden können, müssen sie in unabhängige Faktoren zerlegt werden. Dies ist möglich, falls die Modelle dünn besetzt sind. Valuationsalgebren bieten ein allgemeines abstraktes Framework für lokales Rechnen mit solchen Faktorisierungen. Eine Valuationsalgebra ist eine zweisortige Struktur mit drei Operationen: Valuationen (die als Informationsstücke angesehen werden können) beziehen sich auf eine Domäne; Valuationen können auf eine Dom¨ane marginalisiert (fokussiert) und kombiniert (aggregiert) werden. Generische Algorithmen mit Nachrichtenaustausch k¨onnen angewendet werden, um ein Projektionsproblem zu lösen. Viele Anwendungsprobleme k¨onnen auf ein Projektionsproblem zurückgeführt werden: diagnostische, pr¨adiktive, Filter- und Smoothing- Probleme. Zum Beispiel bilden Gauss’sche Dichten eine Valuationsalgebra: Marginalisierung ist Integration und Kombination ist Multiplikation (plus Normalisierung). Gauss’sche Dichten können durch Gauss’sche Potentiale oder Moment- Matrizen dargestellt werden, wobei entweder die Konzentrationsmatrix oder die Varianz-Kovarianzmatrix verwendet wird. Hier sind Marginalisierung und Kombination Matrizenoperationen. Eine bedingte Gauss’sche Dichte ist die Familie von Gauss’sche Dichten über die Kopfvariabeln für einen jeweils festen Wert der Rumpfvariabeln. Eine bedingte Gauss’sche Dichte entspricht einer Gauss’schen Dichte über die Kopfvariabeln mit linearer Regression von den Rumpfvariabeln. Bedingte Gauss’sche Dichten können auf drei Arten betrachtet werden: auf geometrische, algebraische und analytische. Allgemeine Gauss’sche lineare Systeme führen zu Gauss’schen Hinweisen durch annahmen-basiertes Schliessen in Gauss’schen linearen Systemen. Die Fokalmengen Gauss’scher Hinweise sind parallele lineare Mannigfaltigkeiten derselben Dimension im Parameterraum. Gauss’sche Hinweise werden kombiniert, indem ihre Fokalmengen geschnitten werden, und marginalisiert, indem ihre Fokalmengen projiziert werden. Gauss’sche Potentiale entsprechen Gauss’schen Hinweisen mit einelementigen Fokalmengen. Gauss’sche Potentiale können zu einer Valuationsalgebra von Quotienten erweitert werden, die durch Paare von Gauss’schen Potentialen repräsentiert werden. In dieser sogenannten separativen Erweiterung können auch bedingte Gauss’sche Dichten dargestellt werden. Da eine bedingte Gauss’sche Dichte eine Quotientenfunktion zweier Gauss’scher Dichten ist, entspricht diese der Subtraktion zweier Konzentrationsmatrizen. Dies führt zu symmetrischen Gauss’schen Potentialen, deren Pseudo-Konzentrationsmatrix nur symmetrisch, aber nicht notwendigerweise positiv definit ist. Aus diesen Betrachtungen ergibt sich, dass bedingte Gauss’sche Dichten genau dann dem (bis auf ¨Aquivalenz) gleichen Gauss’schen Hinweis entsprechen, falls die bedingten Gauss’schen Dichten bis auf einen konstanten Faktor gleich sind. In anderen Worten tragen Gauss’sche Likelihood-Funktionen dieselbe Information wie Gauss’sche Hinweise. Dies erklärt, wieso annahmen-basiertes Schliessen aus (über-)bestimmten Gauss’schen linearen Systemen zu denselben Schätzern führt wie die Maximum- Likelihood-Methode. Variabeln können lineare Kombinationen anderer Variabeln sein. Dies erlegt lineare Einschränkungen auf den Parameterraum. Durch annahmen-basiertes Schliessen werden Algorithmen für Inferenz, Kombination und Marginalisierung für symmetrische Gauss’sche Potentiale mit linearen Gleichungen hergeleitet. Schliesslich wird gezeigt, wie Gauss’sche lineare Systeme in der Sprache Abel ausgedrückt werden können. Anfragen über komplexe Gauss’sche lineare Systeme können durch Abel beantwortet werden. Symmetrische Gauss’sche Potentiale werden anhand mehrerer Beispiele illustriert.
Faculty
Faculté des sciences et de médecine
Department
Département d'Informatique
Language
  • English
Classification
Computer science and technology
Notes
  • Ressource en ligne consultée le 13.01.2010
License
License undefined
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/301415
Statistics

Document views: 129 File downloads:
  • EichenbergerC.pdf: 96