- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Generalized constraint-based inference
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Generalized constraint-based inference Chang, Le
Abstract
Constraint-Based Inference (CBI) is a unified framework that subsumes many practical problems in different research communities. These problems include probabilistic inference, decision-making under uncertainty, constraint satisfaction, propositional satisfiability, decoding problems, and possibility inference. Solving them efficiently is important for both research and practical applications. Along with the development of inference approaches for concrete CBI problems, researchers are increasingly aware that these problems share common features in representation and essentially identical inference approaches. As the first contribution of this thesis, we explicitly use the semiring concept to generalize various CBI problems into a single formal representation framework with a broader coverage of the problem space based on the synthesis of existing generalized frameworks. Second, the proposed semiring-based unified framework is also a single formal algorithmic framework that provides a broader coverage of both exact and approximate inference algorithms, including variable elimination, junction tree, and loopy message propagation methods. Third, we discuss inference algorithm design and complexity issues based on the abstract representations of CBI problems and inference algorithms. These discussions are examples of applying the abstract knowledge to the concrete application domains. Researchers from various fields can (1) study the most important common characteristics of various CBI problems without representation barriers; (2) analyze and compare different inference approaches; (3) borrow design ideas from other fields and improve the inference approaches' efficiency in their own domains; and (4) significantly reduce the amount of implementation work target ted previously at the individual problems. Finally, we present a software toolkit named the Generalized Constraint- Based Inference Toolkit in Java (GCBIJ) as the last contribution of this thesis. GCBIJ is the first concrete software toolkit that implements the abstract semiring approach to unify the CBI problem representations and the inference algorithms. Users can design their own task-specific semirings or simply use ones provided by the toolkit to solve their own concrete CBI problems through instantiating various already provided abstract inference algorithms. Users can also design their own inference algorithms on the abstract level and apply them to solve different problems. Furthermore, researchers can test, verify, compare, and analyze inference approaches based on this toolkit. The the experimental results based on GCBIJ show that the generalized CBI framework is a useful tool for both research and practical problem-solving.
Item Metadata
Title |
Generalized constraint-based inference
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
2005
|
Description |
Constraint-Based Inference (CBI) is a unified framework that subsumes many
practical problems in different research communities. These problems include
probabilistic inference, decision-making under uncertainty, constraint satisfaction,
propositional satisfiability, decoding problems, and possibility inference.
Solving them efficiently is important for both research and practical applications.
Along with the development of inference approaches for concrete CBI problems,
researchers are increasingly aware that these problems share common features
in representation and essentially identical inference approaches. As the
first contribution of this thesis, we explicitly use the semiring concept to generalize various CBI problems into a single formal representation framework with
a broader coverage of the problem space based on the synthesis of existing generalized frameworks. Second, the proposed semiring-based unified framework
is also a single formal algorithmic framework that provides a broader coverage
of both exact and approximate inference algorithms, including variable elimination,
junction tree, and loopy message propagation methods. Third, we
discuss inference algorithm design and complexity issues based on the abstract
representations of CBI problems and inference algorithms. These discussions
are examples of applying the abstract knowledge to the concrete application
domains. Researchers from various fields can (1) study the most important
common characteristics of various CBI problems without representation barriers;
(2) analyze and compare different inference approaches; (3) borrow design
ideas from other fields and improve the inference approaches' efficiency in their
own domains; and (4) significantly reduce the amount of implementation work
target ted previously at the individual problems.
Finally, we present a software toolkit named the Generalized Constraint-
Based Inference Toolkit in Java (GCBIJ) as the last contribution of this thesis.
GCBIJ is the first concrete software toolkit that implements the abstract
semiring approach to unify the CBI problem representations and the inference
algorithms. Users can design their own task-specific semirings or simply use
ones provided by the toolkit to solve their own concrete CBI problems through
instantiating various already provided abstract inference algorithms. Users can
also design their own inference algorithms on the abstract level and apply them
to solve different problems. Furthermore, researchers can test, verify, compare,
and analyze inference approaches based on this toolkit. The the experimental
results based on GCBIJ show that the generalized CBI framework is a useful
tool for both research and practical problem-solving.
|
Extent |
6004839 bytes
|
Genre | |
Type | |
File Format |
application/pdf
|
Language |
eng
|
Date Available |
2009-12-03
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
For non-commercial 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.0051112
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2005-05
|
Campus | |
Scholarly Level |
Graduate
|
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.