Conditional independence relations have no finite complete
characterization. In Information Theory, Statistical Decision Functions
and Random Processes. Transactions of the 11th Prague Conference vol. B
(S. Kubik, J.A. Visek eds.), Kluwer, Dordrecht - Boston - London
(also Academia, Prague) 1992, pp. 377-396.
- The hypothesis of existence of a finite characterization of
conditional independence relations (= structures) is refused. This result
is shown to be equivalent to the non-existence of a simple deductive
system describing relationships among conditional independence statements
(it is a certain type of syntactic description). However, under the
assumption that the conditional independence relations are grasped
the existence of a countable characterization of conditional independence
relations is proved.
Finally, the problem of characterization of conditional independence
relations is shown to be diverse from an analogical problem of
axiomatization of embedded multivalued dependencies arising in the theory
of relational databases.
- AMS classification 68T30, 03B30, 60A05, 68P15
- stochastic conditional independence
- syntactic description of conditional independence
- embedded multivalued dependency
postscript version (349 kB) is available.
The paper is motivated by the problem raised in the following work:
- J. Pearl: Probabilistic Reasoning in Intelligent Systems:
Networks of Plausible Inference. Morgan Kaufman, San Mateo CA
The paper builds on the following works: