2012/07/11 by Rina Dechter, Dechter, Rina, Robert Mateescu +1
Computer Science · #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Constraint Satisfaction and Optimization #Data Management and Algorithms #FOS: Computer and information sciences #cs.AI
paper · pdf · doi:10.48550/arxiv.1207.4119
Appears in Proceedings of the Twentieth Conference on Uncertainty in Artificial Intelligence (UAI2004)
arxiv created 2012/07/11 · openalex publication_date 2012/07/11 · arxiv updated 2012/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The paper introduces mixed networks, a new framework for expressing and reasoning with probabilistic and deterministic information. The framework combines belief networks with constraint networks, defining the semantics and graphical representation. We also introduce the AND/OR search space for graphical models, and develop a new linear space search algorithm. This provides the basis for understanding the benefits of processing the constraint information separately, resulting in the pruning of the search space. When the constraint part is tractable or has a small number of solutions, using the mixed representation can be exponentially more effective than using pure belief networks which odel constraints as conditional probability tables.