Graphoids: a qualitative framework for probabilistic inference
Dan Geiger · 1990
This dissertation investigates properties of conditional independence in relation to the elicitation, organization and inference of probabilistic expert systems. Qualitative notions of interaction, connectedness, mediation and causation are given formal probabilistic underpinning: graph-based representations and algorithms are developed for processing these notions. A partial axiomatic characterization is established of the predicate $I(X,Z,Y)$ to read: X is conditionally independent of Y, given Z. This characterization facilitates both a graphical representation of dependence information and a solution to the implication problem, of deciding whether an arbitrary independence statement $I(X,Z,Y)$ logically follows from a given set $\Sigma$ of such statements. The solution of the implication problem is the key for identifying what information is unnecessary for performing a given computation. An algorithm is developed that identifies this information is probabilistic networks. The algorithm's correctness and optimality stems from the soundness and completeness of probabilistic networks with respect to probability theory. An enhanced version of the algorithm extends its applicability to networks that encode functional dependencies. Probabilistic dependence is also used to formalize the notion of interactions among variables; a class of distributions is identified for which this formal definition exhibits qualitative properties normally attributed to the word interact. Finally, the problem is addressed of deciding whether a given distribution can be represented as a graph of certain structure. Conditions are identified for the existence of a unique solution, an efficient algorithm is developed to find this solution, and a relationship to the problem of discovering causality from statistical data is discussed.