CaseFactor Diagrams for Structured Probabilistic Modeling
David McAllester, Michael Collins, Fernando Pereira
Abstract:
We introduce a probabilistic formalism subsuming Markov random fields of bounded tree width and probabilistic context free grammars. Our models are based on a representation of Boolean formulas that we call casefactor diagrams (CFDs). CFDs are similar to binary decision diagrams (BDDs) but are concise for circuits of bounded tree width (unlike BDDs) and can concisely represent the set of parse trees over a given string undera given context free grammar (also unlike BDDs). A probabilistic model consists of aCFD defining a feasible set of Boolean assignments and a weight (or cost) for each individual Boolean variable. We give an insideoutside algorithm for simultaneously computing the marginal of each Boolean variable, and a Viterbi algorithm for finding the mininum cost variable assignment. Both algorithms run in time proportional to the size of the CFD.
Keywords: null
Pages: 382391
PS Link:
PDF Link: /papers/04/p382mcallester.pdf
BibTex:
@INPROCEEDINGS{McAllester04,
AUTHOR = "David McAllester
and Michael Collins and Fernando Pereira",
TITLE = "CaseFactor Diagrams for Structured Probabilistic Modeling",
BOOKTITLE = "Proceedings of the Twentieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI04)",
PUBLISHER = "AUAI Press",
ADDRESS = "Arlington, Virginia",
YEAR = "2004",
PAGES = "382391"
}

