About

Rina Dechter is a Distinguished Professor of Computer Science at UC Irvine's Donald Bren School of Information & Computer Sciences. Her research centers on the computational aspects of automated reasoning and knowledge representation, including search, constraint processing, and probabilistic reasoning. Her primary aim is to devise efficient methods through the understanding and exploitation of tractable reasoning tasks. She is an author of the book 'Constraint Processing' published by Morgan Kaufmann in 2003, and 'Reasoning with Probabilistic and Deterministic Graphical Models: Exact Algorithms' published by Morgan and Claypool in 2013. Dechter has authored over 150 research papers and has served on the editorial boards of several prominent journals, including Artificial Intelligence, the Constraint Journal, the Journal of Artificial Intelligence Research, and the Journal of Machine Learning (JMLR). She has received numerous awards, including the Presidential Young Investigator Award in 1991, the 2007 Association of Constraint Programming (ACP) research excellence award, and is a Fellow of the ACM since 2013. She has also been Co-Editor-in-Chief of Artificial Intelligence since 2011.

Research topics

• Computer Science
• Artificial Intelligence
• Theoretical computer science
• Mathematics
• Algorithm
• Data Mining
• Mathematical optimization
• Combinatorics

Selected publications

• A community‐driven vision for a new knowledge resource for AI

  AI Magazine · 2025-10-26

  articleOpen access

  Abstract The long‐standing goal of creating a comprehensive, multi‐purpose knowledge resource, reminiscent of the 1984 Cyc project, still persists in AI. Despite the success of knowledge resources like WordNet, ConceptNet, Wolfram|Alpha and other commercial knowledge graphs, verifiable, general‐purpose, widely available sources of knowledge remain a critical deficiency in AI infrastructure. Large language models struggle due to knowledge gaps; robotic planning lacks necessary world knowledge; and the detection of factually false information relies heavily on human expertise. What kind of knowledge resource is most needed in AI today? How can modern technology shape its development and evaluation? A recent AAAI workshop gathered over 50 researchers to explore these questions. This paper synthesizes our findings and outlines a community‐driven vision for a new knowledge infrastructure. In addition to leveraging contemporary advances in knowledge representation and reasoning, one promising idea is to build an open engineering framework to exploit knowledge modules effectively within the context of practical applications. Such a framework should include sets of conventions and social structures that are adopted by contributors.

  PublisherOA PDFDOI

• Estimating Causal Effects from Learned Causal Networks

  arXiv (Cornell University) · 2024-08-26

  preprintOpen accessSenior author

  The standard approach to answering an identifiable causal-effect query (e.g., $P(Y|do(X)$) when given a causal diagram and observational data is to first generate an estimand, or probabilistic expression over the observable variables, which is then evaluated using the observational data. In this paper, we propose an alternative paradigm for answering causal-effect queries over discrete observable variables. We propose to instead learn the causal Bayesian network and its confounding latent variables directly from the observational data. Then, efficient probabilistic graphical model (PGM) algorithms can be applied to the learned model to answer queries. Perhaps surprisingly, we show that this \emph{model completion} learning approach can be more effective than estimand approaches, particularly for larger models in which the estimand expressions become computationally difficult. We illustrate our method's potential using a benchmark collection of Bayesian networks and synthetically generated causal models.

  PublisherOA PDFDOI

• Estimating Causal Effects from Learned Causal Networks

  Frontiers in artificial intelligence and applications · 2024-10-16

  book-chapterOpen accessSenior author

  The standard approach to answering an identifiable causal-effect query (e.g., P(Y|do(X)) given a causal diagram and observational data is to first generate an estimand, or probabilistic expression over the observable variables, which is then evaluated using the observational data. In this paper, we propose an alternative paradigm for answering causal-effect queries over discrete observable variables. We propose to instead learn the causal Bayesian network and its confounding latent variables directly from the observational data. Then, efficient probabilistic graphical model (PGM) algorithms can be applied to the learned model to answer queries. Perhaps surprisingly, we show that this model completion learning approach can be more effective than estimand approaches, particularly for larger models in which the estimand expressions become computationally difficult. We illustrate our method’s potential using a benchmark collection of Bayesian networks and synthetically generated causal models.

  PublisherDOI

• Graph-based Complexity for Causal Effect by Empirical Plug-in

  arXiv (Cornell University) · 2024-11-15

  preprintOpen access1st authorCorresponding

  This paper focuses on the computational complexity of computing empirical plug-in estimates for causal effect queries. Given a causal graph and observational data, any identifiable causal query can be estimated from an expression over the observed variables, called the estimand. The estimand can then be evaluated by plugging in probabilities computed empirically from data. In contrast to conventional wisdom, which assumes that high dimensional probabilistic functions will lead to exponential evaluation time of the estimand. We show that computation can be done efficiently, potentially in time linear in the data size, depending on the estimand's hypergraph. In particular, we show that both the treewidth and hypertree width of the estimand's structure bound the evaluation complexity of the plug-in estimands, analogous to their role in the complexity of probabilistic inference in graphical models. Often, the hypertree width provides a more effective bound, since the empirical distributions are sparse.

  PublisherOA PDFDOI

• Boosting AND/OR-Based Computational Protein Design: Dynamic Heuristics and Generalizable UFO

  arXiv (Cornell University) · 2023-08-31

  preprintOpen accessSenior author

  Scientific computing has experienced a surge empowered by advancements in technologies such as neural networks. However, certain important tasks are less amenable to these technologies, benefiting from innovations to traditional inference schemes. One such task is protein re-design. Recently a new re-design algorithm, AOBB-K*, was introduced and was competitive with state-of-the-art BBK* on small protein re-design problems. However, AOBB-K* did not scale well. In this work we focus on scaling up AOBB-K* and introduce three new versions: AOBB-K*-b (boosted), AOBB-K*-DH (with dynamic heuristics), and AOBB-K*-UFO (with underflow optimization) that significantly enhance scalability.

  PublisherOA PDFDOI

• Submodel Decomposition Bounds for Influence Diagrams

  Proceedings of the AAAI Conference on Artificial Intelligence · 2021 · 4 citations

  Senior authorCorresponding
  • Computer Science
  • Data Mining
  • Computer Science

  Influence diagrams (IDs) are graphical models for representing and reasoning with sequential decision-making problems under uncertainty. Limited memory influence diagrams (LIMIDs) model a decision-maker (DM) who forgets the history in the course of making a sequence of decisions. The standard inference task in IDs and LIMIDs is to compute the maximum expected utility (MEU), which is one of the most challenging tasks in graphical models. We present a model decomposition framework in both IDs and LIMIDs, which we call submodel decomposition that generates a tree of single-stage decision problems through a tree clustering scheme. We also develop a valuation algebra over the submodels that leads to a hierarchical message passing algorithm that propagates conditional expected utility functions over a submodel-tree as external messages. We show that the overall complexity is bounded by the maximum tree-width over the submodels, common in graphical model algorithms. Finally, we present a new method for computing upper bounds over a submodel-tree by first exponentiating the utility functions yielding a standard probabilistic graphical model as an upper bound and then applying standard variational upper bounds for the marginal MAP inference, yielding tighter upper bounds compared with state-of-the-art bounding schemes for the MEU task.

  PublisherOA PDFDOI

• Empowering Mini-Bucket in Anytime Heuristic Search with Look-Ahead: Preliminary Evaluation

  Proceedings of the International Symposium on Combinatorial Search · 2021-09-01

  articleOpen accessSenior author

  The paper explores the potential of look-ahead methods within the context of AND/OR search in graphical models using the Mini-Bucket heuristic for combinatorial optimization tasks (e.g., weighted CSPS or MAP inference). We study how these methods can be used to compensate for the approximation error of the initially generated Mini-Bucket heuristics, within the context of anytime Branch-And-Bound search.

  PublisherOA PDFDOI

• Approximating Spatial Evolutionary Games using Bayesian Networks

  2021-05-03 · 1 citations

  articleSenior author

  Evolutionary Game Theory is an application of game theory to evolving populations of organisms. Of recent interest are EGT models situated on structured populations or spatial evolutionary games. Due to the complexity added by introducing a population structure, model analysis is usually performed through agent-based Monte-Carlo simulations. However, it can be difficult to obtain desired quantities of interest from these simulations due to stochastic effects. We define a framework for modeling spatial evolutionary games using Dynamic Bayesian Networks that capture the underlying stochastic process. The resulting Dynamic Bayesian Networks can be queried for quantities of interest by performing exact inference on the network. We then propose a method for producing approximations of the spatial evolutionary game through the truncation of the corresponding DBN, taking advantage of the high symmetry of the model. This method generalizes mean-field and pair approximations in the literature for spatial evolutionary games. Furthermore, we show empirical results demonstrating the capability of the method to obtain much better accuracy than pair approximation with respect to stochastic simulations.

  PublisherDOI

• A New Bounding Scheme for Influence Diagrams

  Proceedings of the AAAI Conference on Artificial Intelligence · 2021-05-18 · 2 citations

  articleOpen accessSenior author

  Influence diagrams provide a modeling and inference framework for sequential decision problems, representing the probabilistic knowledge by a Bayesian network and the preferences of an agent by utility functions over the random variables and decision variables. Computing the maximum expected utility (MEU) and the optimizing policy is exponential in the constrained induced width and therefore is notoriously difficult for larger models. In this paper, we develop a new bounding scheme for MEU that applies partitioning based approximations on top of the decomposition scheme called a multi-operator cluster DAG for influence diagrams that is more sensitive to the underlying structure of the model than the classical join-tree decomposition of influence diagrams. Our bounding scheme utilizes a cost-shifting mechanism to tighten the bound further. We demonstrate the effectiveness of the proposed scheme on various hard benchmarks.

  PublisherOA PDFDOI

• STLS: Cycle-Cutset-Driven Local Search For MPE

  Proceedings of the International Symposium on Combinatorial Search · 2021-09-01

  articleOpen accessSenior author

  In this paper we present Stochastic Tree-based Local Search or STLS, a local search algorithm combining the notion of cycle-cutsets with the well-known Belief Propagation to approximatethe optimum of sums of unary and binary potentials. This is done by the previously unexplored concept oftraversal from one cutset to another and updating the induced forest, thus creating a local search algorithm, whose updatephase spans over all the forest variables. We study empirically two pure variants of STLS against the state-of-the art GLS+ scheme and against a hybrid.

  PublisherOA PDFDOI

Recent grants

• RI: Small: Heuristic Search Algorithms for Probabilistic Graphical Models

  NSF · $500k · 2015–2019

• Strategies for High Performance Graph-Based Reasoning

  NSF · $450k · 2004–2008

• RI: High Performance Algorithms for Probabilistic and Deterministic Graphical Models

  NSF · $450k · 2007–2012

• RI: Small: Anytime Algorithms and Bounds for Probabilistic Graphical Models

  NSF · $450k · 2020–2024

• RI: Medium: Approximation Algorithms for Probabilistic Graphical Models with Constraints

  NSF · $1.1M · 2011–2016

Frequent coauthors

• Kalev Kask

  University of California, Irvine

  64 shared

• Robert Mateescu

  Western Digital (United States)

  57 shared

• Vibhav Gogate

  The University of Texas at Dallas

  52 shared

• Radu Marinescu

  49 shared

• Lars Otten

  University of California, Irvine

  40 shared

• Alexander Ihler

  University of California, Irvine

  33 shared

• Judea Pearl

  University of California, Los Angeles

  23 shared

• Bozhena Bidyuk

  19 shared

Education

• Ph.D., Computer Science

  Stanford University

  1980

• M.S., Computer Science

  Stanford University

  1976

• B.S., Mathematics

  University of California, Los Angeles

  1974

Awards & honors

• Presidential Young Investigator Award (1991)
• Fellow of the American Association of Artificial Intelligenc…
• Radcliffe Fellowship (2005-2006)
• 2007 Association of Constraint Programming (ACP) Research Ex…
• Fellow of the ACM (2013)