  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 case-factor 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.
