|
|
 |
 |
|
 |
|
| home | publications | book | courses | about | Revised on Mar. 28, 2001 |
|
|
|
|
|
|
|
| home | publications | book | courses | about | Revised on Mar. 28, 2001 |
| About Dr. Dechter | |
| short biography |
research interests |
research overview |
graduate students
|
|
| Research Interests | |
|
|
|
The overall aim of my research is to devise methods of automated
reasoning via the understanding and exploitation of tractable classes
of reasoning tasks. I believe that approximation methods based on
tractable models cover a significant portion of intelligent activities
and, hence, should serve as the cornerstone in automated reasoning
systems. This principle has motivated my previous research on greedy
problems, mechanical generation of heuristics, topological decompositions,
and local computations in constraint networks.
Constraint networks have proven to be a useful language for modeling and solving computationally intensive tasks in Artificial Intelligence. The language of constraints expresses information in terms of the desired relationships among entities without specifying how such relationships are to be achieved. Constraint networks are used to model mundane cognitive tasks (e.g., vision, language comprehension, default reasoning, abduction) as well as applications such as scheduling, design, and diagnosis which require high levels of human expertise. In general, the tasks posed in this language are computationally intractable (NP-hard). A survey of constraint networks appears in "Constraint Networks," in the Encyclopedia of Artificial Intelligence, 1992. In recent years, I have developed and analyzed a large number of techniques for finding partial and complete solutions to a variety of constraint classes, often accompanied by theoretical guarantees of worst-case performance. These techniques, including directional consistency, adaptive consistency, tree clustering, cycle cutset schemes, backjumping, and search-based learning, have become popular in many constraint-processing applications. My current research interests focus on developing scalable techniques in constraint processing and on applying those techniques to broader areas in automated reasoning. The following is an outline of my research projects. Empirical Evaluation Of Constraint Processing Algorithms:
An ongoing research goal is to close the gap between theory
and practice in constraint processing. To that end, we perform
a large-scale experimentation on both real-life and simulated systems.
We plan to build an environment in which large scale constraint-based
problems could be modeled, processed, evaluated, and analyzed.
The project
promises to yield a deeper understanding of those features in the domain
that admit efficient processing. I hope that this understanding will
lead to scalable algorithms, and to new software tools and languages for
generic constraint-processing applications. My experimental work
focuses both on comparing backtracking style algorithms as well as local
search greedy algorithms.
Dechter, R., "Enhancement Schemes for Constraint Processing: Backjumping, Learning and Cutset Decomposition,"
Artificial Intelligence, Vol. 41(3), pp. 273-312, January, 1990.
Dechter, R., and Meiri, I., "Experimental Evaluation of Preprocessing Algorithms for Constraint Satisfaction Problems,"
Artificial Intelligence Journal, Vol 68,2, pp. 211-241, 1994.
Frost, D., and Dechter R.,
"Dead-end Driven Learning,"
In National Conference of Artificial Intelligence, AAAI-94, Seattle, WA, August,
1994, pp. 294-300.
Frost, D., and Dechter R.,
"In search of the best constraint satisfaction search,"
In National Conference of Artificial Intelligence, AAAI-94, Seattle, WA, August, 1994, pp. 301-306.
Frost, D., and Dechter R.,
"Look-ahead value ordering for constraint satisfaction problems,"
In International Joint Conference on Artificial Intelligence, IJCAI-95, Montreal, Canada, August, 1995, pp.572-578.
Kask, K. and Dechter, R.,
"GSAT and Local Consistency,"
In International Joint Conference on Artificial Intelligence, IJCAI-95, Montreal, Canada, August, 1995, 616-622.
Temporal Reasoning
We (with I. Meiri and J. Pearl) have developed a
general network-based framework for temporal reasoning capable of
handling both qualitative and quantitative temporal information.
Using this framework, we characterized new tractable problems involving
qualitative networks augmented by quantitative domains.
We developed a
language that expresses information about fluents events
and constraints whose computational tool is based on temporal constraint
networks.
Dechter, R., Meiri, I., and Pearl, J., "Temporal Constraint Networks,"
Artificial Intelligence, Vol. 49, pp. 61-95, 1991.
Meiri I., "Combining Quantitative and Qualitative Constraints in
Temporal Reasoning," In AAAI-91, Anaheim, CA, July, 1991.
Schwalb, E., and Dechter, R.,
"Coping with Disjunctions in Temporal
Constraint Satisfaction Problems," In The National Conference on
Artificial Intelligence, AAAI-93, Washington, DC, pp. 127-132,
July, 1993.
Schwalb, E., Kask, K., and Dechter, R.,
"Temporal Reasoning with Constraints on Fluents and Event,"
In National Conference of Artificial Intelligence,
AAAI-94, Seattle, WA, August, 1994.
Schwalb, E., and Dechter, R.,
"Processing Temporal Constraint Networks",
ICS Technical report, January 1995.
Qualitative Reasoning And Diagnosis
A physical system can be formulated by a set of constraints and
subsequently be processed by constraint processing algorithms. Such
algorithms were developed for finding a best diagnosis, finding all
minimal cardinality, or all minimal diagnoses. These algorithms
exploit the structure of the system and they are particularly useful
for systems that have sparse graphs. I intend to empirically compare
the performance of such structure-based diagnosis algorithms with more
traditional approaches.
Dechter, R., and Dechter, A.,
"Structure-Driven Algorithms for Truth Maintenance."
To appear in Artificial Intelligence.
Preliminary version was
"Belief Maintenance in Dynamic Constraint
Networks", in Proceedings of the Seventh National Conference on Artificial
Intelligence (AAAI-88), pp. 37-42, St. Paul, MN, August, 1988.
El Fattah, Y., and Dechter, R.,
"Diagnosing Tree-Decomposable Circuits,
in International Joint Conference on Artificial Intelligence,
IJCAI-95, Montreal, Canada, August, 1995.
Ben-Eliyahu, R., and Dechter, R.,
"On Computing Minimal Models",
In the Journal of Annals of Math and AI, Special issue.
Constraint-Based Nonmonotonic Reasoning
I (with R. Ben-Eliyahu) have formed a connection between
constraint-based algorithms and nonmonotonic reasoning,
uncovering new tractable classes of logic programs and default knowledge
bases. I plan to extend these results to nonpropositional languages and
to demonstrate the potential of such techniques in practical logic
programming applications.
Ben-Eliyahu, R., and Dechter, R.,
"Propositional Semantics for Disjunctive Logic Programs",
In the Journal of Annals of Math and AI, 12 (1994) 53-87.
Ben-Eliyahu, R. and Dechter, R.,
"Default Reasoning Using Classical Logic"
Under review.
Preliminary version appeared as "Default Logic, Propositional Logic
and Constraints," in Proceedings of the Ninth National Conference on
Artificial Intelligence (AAAI-91), pp. 379-385, Anaheim, CA, July, 1991.
Ben-Eliyahu, R. and Dechter, R.,
"Inferences in Inheritance Networks,
Using Propositional Logic and Constraint Networks Techniques", In the
Canadian Artificial Intelligence Conference (AI-92), pp. 1833-189,
Vancouver, British Columbia, May, 1992.
Distributed And Connectionist-Like Constraint Processing
I studying the computational features and convergence of constraint
networks under local distributed computation. Initial investigations
have generated new insights and general principles governing network
representations. Through these investigations, I hope to devise
distributed and parallel architectures for processing constraint-based
information. Potentially, this could lead to a substantial speed up
in processing time while also simplifying programming.
Collin, Z., Dechter, R., and Katz, S.,
"Self-Stabilizing Distributed Constraint Satisfaction"
Under review.
Preliminary version appeared as "On the Feasibility of Distributed
Constraint Satisfaction", in Proceedings of the Twelfth International
Joint Conference of Artificial Intelligence (IJCAI-91), pp. 318-324,
Sidney, Australia, August, 1991.
Pinkas, G., and Dechter, R.,
"On Improving Connectionist Energy Minimization"
Under review.
Preliminary version appeared as "An Improved Connectionist Activation
Function for Energy Minimization", in The National Conference on
Artificial Intelligence, pp. 434-439, San Jose, CA, July, 1992.
Tractable Islands And The Role Of Topology In Reasoning
Throughout my research I have investigated the role of the knowledge
structure in enabling fast reasoning which had led to the identification
of several structure-based tractable islands. I will continue
to investigate this issue by exploring the role of the dependency graph
of various propositional theories.
Empirical tests confirm theoretical predictions
by parameters like "induced width" and "diversity," showing that on problems
with special structures, like chains, directional resolution
greatly out-performs the popular Davis-Putnam procedure.
Recently I have discovered new tractable classes that are based on the
syntactic nature of the constraints. These are the row-convex constraint
and tight domains and constraints.
Another travtable class called causal networks is characterized
by a comnination of the constraint graph and the nature of the
constraints themselves.
Dechter, R. and Pearl, J., "Network-Based Heuristics for
Constraint-Satisfaction Problems", Artificial Intelligence, Vol. 34(1),
pp. 1-38, December, 1987.
Dechter, R. and Pearl, J., "Tree-Clustering Schemes for
Constraint-Processing", Artificial Intelligence, Vol. 38(3),
pp. 353-366, April, 1989.
Dechter, R., Dechter, A., and Pearl, J., "Optimization in
Constraint-networks", In Proceedings of the Conference on Influence
Diagrams for Decision Analysis, Inference, UC Berkeley, CA, May, 1987.
Dechter, R. and Rish I.,
"Directional Resolution: the Davis-Putnam Procedure, Revisited",
In KR-94, Bonn, Germany, May, 1994.
Dechter, R., and Pearl, J., "Directed Constraint Networks: A Relational
Framework for Causal Modeling", in Proceedings of the Twelfth International
Joint Conference of Artificial Intelligence (IJCAI-91), pp. 1164-1170,
Sydney, Australia, August, 1991.
Dechter, R., "From Local to Global Consistency", Artificial
Intelligence, Vol. 55, pp. 87-107, 1992.
van Beek, P. and Dechter, R.,
"Constraint Restrictiveness Versus Local And Global Consistency"
Under review. A preliminary version ``Constraint tightness and global
consistency appears in KR-94, Bonn, Germany, May, 1994.
van Beek, P. and Dechter, R.,
"On the Minimality and Decomposability of
Row-Convex Constraint Networks",
Accepted for publication in the Journal of the ACM, January, 1994.
Structure Identifiability And Knowledge Compilation
In the past I have presented algorithms for uncovering
tree-structured knowledge-bases from raw data [ST-1,ST-2]. I
(with J. Pearl) have
presented a new framework for studying the identifiability of such
tractable structures and the identifiability of classes of constraint
networks: Horn theories were also characterized [ST-3,ST-4,ST-6].
ST-1. Dechter, R., "Decomposing A Relation Into A Tree Of Binary Relations" ,
Journal of Computer and System Sciences, Special Issue on the Theory
of Relational Databases, Vol. 41, pp. 2-24, 1990.
ST-2. Meiri, I., Dechter, R., and Pearl, J.,
"Tree Decomposition with Applications to Constraint Processing"
Under review.
Preliminary version appeared as "Tree Decomposition With
Applications To Constraint Processing" In Proceedings of the
Eighth National Conference on Artificial Intelligence (AAAI-90),
pp. 10-16, Boston, MA, July, 1990.
ST-3. Dechter, R. and Pearl, J., "Structure Identification in Relational
Data", Artificial Intelligence, Vol 58, pp. 237-270, 1992.
ST-4. Dechter, R., "On the Expressiveness of Networks with Hidden Variables"
In Proceedings of the Eighth National Conference on Artificial
Intelligence (AAAI-90), pp. 556-562, Boston, MA, July, 1990.
ST-5. Dechter, R. and Schwalb, E.,
"Compiling Relational Data into
Disjunctive Structure: Empirical Evaluation" In AI/GI/VI-94,
Banff, Alberta, Canada, May 1994.
ST-6. Dechter, R. and Itai, A.,
"Finding All Solutions If You Can Find One"
Presented in the Workshop on Tractable Reasoning, AAAI-92, pp. 35-39,
San Jose, CA, July, 1992.
Inference In Belief Networks
We are currently extending constraint processing algorithms
to probabilistic inference. In particular a new algorithmic
framework called ``Bucket Elimination'' was introduced
as a unifying and simplifying framework for expressing
many known probabilistic algorithms. It is also shown to accomodate
the combination of conditioning and clustering in order
to alleviate the memory required by clustering methods.
A
Common Lisp implementation
of the ElimBel algorithm is available, as well as examples
of the algorithm at work on a
tiny network, a
small network and
another small network.
Dechter, R.,
"Topological Parameters For Time-Space Tradeoff",
UAI-96, Portland Oregon, August 1996 (An earlier version was
presented at Math-AI, January, 1996, Florida.)
El Fattah, Y. and R. Dechter.,
"An Evaluation Of Structural Parameters For Probabilistic Reasoning;
Results On Benchmark Circuits"
In Proceedings of Uncertainty in AI (UAI-96).
J. Pearl and R. Dechter,
"Identifying Independencies In Causal Graphs With Feedback"
In Proceedings of Uncertainty in AI (UAI-96), Portland Oregon, August
1996.
R. Dechter.,
"Bucket Elimination : A Unifying Framework For Probabilistic
Inference"
In Proceedings of Uncertainty in AI (UAI-96), Portland Oregon, August 1996.
|
|
|
||
University of California, Irvine, CA 92697-3425 |
Dr. Rina Dechter dechter at ics.uci.edu |
|