 Library Home /
 Search Collections /
 Open Collections /
 Browse Collections /
 UBC Theses and Dissertations /
 Probabilistic inference with large discrete domains
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Probabilistic inference with large discrete domains Sharma, Rita
Abstract
The straightforward representation of many real world problems is in terms of discrete random variables with large or infinite domains. For example, in a domain where we are trying to identify a person, we may have variables that have as domains, a set of all names, a set of all postal codes, and a set of all credit card numbers. The task usually reduces to performing probabilistic inference, i.e., compute the probability of some values of some random variables given the values of some other variables. Bayesian networks are a compact way to represent joint probability distributions. This thesis is concerned with probabilistic inference in Bayesian networks that have discrete random variables with large or infinite domains. Carrying out inference in Bayesian networks that have variables with large domains is a difficult problem. For efficient inference, we consider cases where there is some structure that can be exploited to make inference efficient. In this thesis we consider two kinds of structures that can be exploited for efficient inference. These structures allow us to partition the large number of values in equivalence classes. Rather than reasoning about every value of a variable individually, we can reason about a set of values in a single step. We first consider the case where there are intensional definitions of the conditional probability distributions. To represent these conditional probabilities, we introduce a CPD language that allows us to define the conditional probabilities procedurally, in terms of predicates and functions. We present an inference algorithm, Large Domain VE, for the CPD language that uses this representation to partitions the domains of the variables dynamically. The partitions depend on what is observed and what is queried. We apply Large Domain VE to the person identification problem that has variables with large domains. The second case we consider where there is a priori internal structure on the values of the variables. In particular, we consider the case where the values of the variables are represented as tree hierarchies. We call such variables hierarchically structured variables. We present a language for representing the conditional probabilities of Bayesian networks with hierarchically structured variables. To perform inference in Bayesian networks with hierarchically structured variables we construct an abstract Bayesian network dynamically, given some evidence and a query, by collapsing the hierarchies to include only those values necessary to answer the query. We can answer the query from the abstract Bayesian network using any standard inference algorithm. Finally, we show how both intensional definitions of the conditional probability distributions and hierarchically structured values can be put together to produce a general framework that can be applied to a more general class of problems.
Item Metadata
Title  Probabilistic inference with large discrete domains 
Creator  Sharma, Rita 
Publisher  University of British Columbia 
Date Issued  2006 
Description 
The straightforward representation of many real world problems is in terms of discrete random variables with large or infinite domains. For example, in a domain where we are trying to identify a person, we may have variables that have as domains, a set of all names, a set of all postal codes, and a set of all credit card numbers. The task usually reduces to performing probabilistic inference, i.e., compute the probability of some values of some random variables given the values of some other variables. Bayesian networks are a compact way to represent joint probability distributions. This thesis is concerned with probabilistic inference in Bayesian networks that have discrete random variables with large or infinite domains. Carrying out inference in Bayesian networks that have variables with large domains is a difficult problem. For efficient inference, we consider cases where there is some structure that can be exploited to make inference efficient. In this thesis we consider two kinds of structures that can be exploited for efficient inference. These structures allow us to partition the large number of values in equivalence classes. Rather than reasoning about every value of a variable individually, we can reason about a set of values in a single step. We first consider the case where there are intensional definitions of the conditional probability distributions. To represent these conditional probabilities, we introduce a CPD language that allows us to define the conditional probabilities procedurally, in terms of predicates and functions. We present an inference algorithm, Large Domain VE, for the CPD language that uses this representation to partitions the domains of the variables dynamically. The partitions depend on what is observed and what is queried. We apply Large Domain VE to the person identification problem that has variables with large domains. The second case we consider where there is a priori internal structure on the values of the variables. In particular, we consider the case where the values of the variables are represented as tree hierarchies. We call such variables hierarchically structured variables. We present a language for representing the conditional probabilities of Bayesian networks with hierarchically structured variables. To perform inference in Bayesian networks with hierarchically structured variables we construct an abstract Bayesian network dynamically, given some evidence and a query, by collapsing the hierarchies to include only those values necessary to answer the query. We can answer the query from the abstract Bayesian network using any standard inference algorithm. Finally, we show how both intensional definitions of the conditional probability distributions and hierarchically structured values can be put together to produce a general framework that can be applied to a more general class of problems.

Genre  Thesis/Dissertation 
Type  Text 
Language  eng 
Date Available  20100118 
Provider  Vancouver : University of British Columbia Library 
Rights  For noncommercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. 
DOI  10.14288/1.0051316 
URI  
Degree  Doctor of Philosophy  PhD 
Program  Computer Science 
Affiliation  Science, Faculty of; Computer Science, Department of 
Degree Grantor  University of British Columbia 
Campus  UBCV 
Scholarly Level  Graduate 
Aggregated Source Repository  DSpace 
Item Media
Item Citations and Data
License
For noncommercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.