Computing concise representations of semi-graphoid independency models

Abstract

The conditional independencies from a joint probability distribution constitute a model which is closed under the semi-graphoid properties of independency. These models typically are exponentially large in size and cannot be feasibly enumerated. For describing a semi-graphoid model therefore, a more concise representation is used, which is composed of a representative subset of the independencies involved, called a basis, and letting all other independencies be implicitly defined by the semi-graphoid properties; for computing such a basis, an appropriate algorithm is available. Based upon new properties of semi-graphoid models in general, we introduce an improved algorithm that constructs a smaller basis for a given independency model than currently existing algorithms.