Efficient Inference in Large Discrete Domains
This addresses the challenge of scalability in probabilistic inference for domains with vast discrete spaces, which is incremental as it builds on variable elimination with new representations.
The paper tackles the problem of performing inference in Bayesian Networks with discrete random variables that have very large or unbounded domains, such as names or postal codes, by developing an inference algorithm based on variable elimination that uses compact representations of conditional probabilities. The result is an efficient method that handles both large-domain and normal discrete variables without requiring big probability tables.
In this paper we examine the problem of inference in Bayesian Networks with discrete random variables that have very large or even unbounded domains. For example, in a domain where we are trying to identify a person, we may have variables that have as domains, the set of all names, the set of all postal codes, or the set of all credit card numbers. We cannot just have big tables of the conditional probabilities, but need compact representations. We provide an inference algorithm, based on variable elimination, for belief networks containing both large domain and normal discrete random variables. We use intensional (i.e., in terms of procedures) and extensional (in terms of listing the elements) representations of conditional probabilities and of the intermediate factors.