We propose compiling Bayesian networks (BNs) into arithmetic circuits (ACs) using symbolic probabilistic inference (SPI). Traditionally, ACs have been compiled from BNs using variable elimination (VE). A key advantage of SPI is its ability to combine product terms that VE would not. When the BN exhibits specific topological structures, SPI produces significantly smaller ACs than VE, addressing the core concern of circuit size in knowledge compilation. We also introduce the notion of indicator-determined buckets (IDBs) in ACs. These are sets of AC nodes that take on two exclusive values: zero or a fixed probability value. We present a method for identifying and leveraging them to construct more compact circuits. Experimental results on benchmark BNs demonstrate that combining SPI with IDB optimization yields a noticeable reduction in circuit size and in the time required for exact inference compared to inference using an AC compiled with VE.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Arithmetic Circuit Compilation Using Symbolic Probabilistic Inference and Indicator-Determined Buckets

  • Cory J. Butz,
  • Camilla E. Lewis,
  • Alejandro Santoscoy-Rivero,
  • Anders L. Madsen

摘要

We propose compiling Bayesian networks (BNs) into arithmetic circuits (ACs) using symbolic probabilistic inference (SPI). Traditionally, ACs have been compiled from BNs using variable elimination (VE). A key advantage of SPI is its ability to combine product terms that VE would not. When the BN exhibits specific topological structures, SPI produces significantly smaller ACs than VE, addressing the core concern of circuit size in knowledge compilation. We also introduce the notion of indicator-determined buckets (IDBs) in ACs. These are sets of AC nodes that take on two exclusive values: zero or a fixed probability value. We present a method for identifying and leveraging them to construct more compact circuits. Experimental results on benchmark BNs demonstrate that combining SPI with IDB optimization yields a noticeable reduction in circuit size and in the time required for exact inference compared to inference using an AC compiled with VE.