Case-factor diagrams for structured probabilistic modeling.

*(English)*Zbl 1161.68784Summary: We introduce a probabilistic formalism handling both Markov random fields of bounded tree width and probabilistic context-free grammars. Our models are based on Case-Factor Diagrams (CFDs) which are similar to binary decision diagrams but are more concise for circuits of bounded tree width. A probabilistic model consists of a CFD defining a feasible set of Boolean assignments and a weight (or cost) for each individual Boolean variable. We give versions of the inside-outside algorithm and the Viterbi algorithm for these models.

##### MSC:

68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |

60C05 | Combinatorial probability |

68Q42 | Grammars and rewriting systems |

##### Keywords:

Boolean decision diagrams; Markov random fields; probabilistic context free grammars; hidden Markov models; conditional random fields; probabilistic relational models; structured labeling; graphical models; Bayesian networks; zero supression; recursive conditioning; and/or graphs
PDF
BibTeX
XML
Cite

\textit{D. McAllester} et al., J. Comput. Syst. Sci. 74, No. 1, 84--96 (2008; Zbl 1161.68784)

Full Text:
DOI

##### References:

[1] | Lafferty, J.; McCallum, A.; Pereira, F., Conditional random fields: probabilistic models for segmenting and labeling sequence data, (), 282-289 |

[2] | K. Kanazawa, D. Koller, S. Russell, Stochastic simulation algorithms for dynamic probabilistic networks, in: Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence, UAI, 1999, pp. 346-351 |

[3] | Poole, D., Probabilistic Horn abduction and Bayesian networks, Artificial intelligence, 64, 1, 81-129, (1993) · Zbl 0792.68176 |

[4] | N. Friedman, L. Getoor, D. Koller, A. Pfeffer, Learning probabilistic relational models, in: Proceedings of the 16th International Joint Conference on Artificial Intelligence, IJCAI, 1999, pp. 1300-1309 |

[5] | Bryant, R.E., Graph-based algorithms for Boolean function manipulation, IEEE trans. comput. C, 35, 8, 677-691, (1986) · Zbl 0593.94022 |

[6] | Minato, S., Zero-suppressed BDDs for set manipulation in combinatorial problems, (), 272-277 |

[7] | K.L. McMillan, Hierarchical representation of discrete functions, with application to model checking, in: Computer Aided Verification, CAV, 6th International Conference, 1994, pp. 41-54 |

[8] | Darwiche, A., Recursive conditioning, Artificial intelligence, 125, 1-2, 5-41, (2001) · Zbl 0969.68150 |

[9] | D. Allen, A. Darwiche, New advances in inference by recursive conditioning, in: Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence, UAI, 2003, pp. 2-10 |

[10] | Darwiche, A., A differential approach to inference in Bayesian networks, J. ACM, 280-305, (2003) · Zbl 1325.68226 |

[11] | C. Boutilier, N. Friedman, M. Goldszmidt, D. Koller, Context-specific independence in Bayesian networks, in: Proceedings of the 12th Conference on Uncertainty in Artificial Intelligence, UAI, 1996, pp. 115-123 |

[12] | R. Dechter, And/or search spaces for graphical models, ICS Technical Report, Artificial Intelligence (March 2004), in press · Zbl 1168.68549 |

[13] | Jaeger, M., Probabilistic decision graphs: combining verification and AI techniques for probabilistic inference, Internat. J. uncertain. fuzzyness knowledge-based systems, 12, 19-42, (2004) · Zbl 1087.68111 |

[14] | F. Bacchus, S. Dalmao, T. Pitassi, Algorithms and complexity results for #sat and Bayesian inference, in: Proceedings of the 44th Annual IEEE Symposium on the Foundations of Computer Science, FOCS, 2003, pp. 340-351 |

[15] | F. Bacchus, S. Dalmao, T. Pitassi, Value elimination: Bayesian inference via backtracking search, in: Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence, UAI, 2003, pp. 20-28 |

[16] | B. Taskar, C. Guestrin, D. Koller, Max-margin Markov networks, in: Proceedings of the 17th Annual Conference on Neural Information Processing Systems Conference, NIPS, 2003, a version will appear in J. Mach. Learn. Res |

[17] | Collins, M., Parameter estimation for statistical parsing models: theory and practice of distribution-free methods, (), revised version of the paper that appeared at IWPT 2001 |

[18] | Y. Altun, T. Hofmann, Large margin methods for label sequence learning, in: 8th European Conference on Speech Communication and Technology, EuroSpeech, 2003 |

[19] | Della Pietra, S.; Della Pietra, V.; Lafferty, J., Inducing features of random fields, IEEE trans. pattern anal. Mach. intell., 19, 4, 380-393, (1997) |

[20] | Bodlaender, H.L., A linear time algorithm for finding tree-decompositions of small treewidth, SIAM J. comput., 25, 1305-1317, (1996) · Zbl 0864.68074 |

[21] | Durbin, R.; Eddy, S.; Krogh, A.; Mitchison, G., Biological sequence analysis: probabilistic models of proteins and nucleic acids, (1998), Cambridge University Press · Zbl 0929.92010 |

[22] | Ristad, E.S.; Yianilos, P.N., Learning string edit distance, IEEE trans. pattern anal. Mach. intell., 20, 5, 522-532, (1998) |

[23] | J. Eisner, Parameter estimation for probabilistic finite-state transducers, in: Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, ACL, 2002, pp. 1-8 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.