An EM Algorithm on BDDs with Order Encoding for Logic-based Probabilistic Models

Masakazu Ishihata (Tokyo Institute of Technology), Yoshitaka Kameya (Tokyo Institute of Technology), Taisuke Sato (Tokyo Institute of Technology), and Shin-ichi Minato (Hokkaido University); JMLR W&P 13:161-176, 2010.

Abstract

Logic-based probabilistic models (LBPMs) enable us to handle various problems in the real world thanks to the expressive power of logic. However, most of LBPMs have restrictions to realize efficient probability computation and learning. We propose an EM algorithm working on BDDs with order encoding for LBPMs. A notable advantage of our algorithm over existing approaches is that it copes with multi-valued random variables without restrictions. The complexity of our algorithm is proportional to the size of the BDD. In the case of hidden Markov models (HMMs), the complexity is the same as that specialized for HMMs. As an example to eliminate restrictions of existing approaches, we utilize our algorithm to give diagnoses for failure in a logic circuit involving stochastic error gates.



Home Page

Papers

Submissions

News

Scope

Editorial Board

Announcements

Proceedings

Open Source Software

Search

Login



RSS Feed