Exact and approximate inference for annotating graphs with structural SVMs

Research output: Contributions to collected editions/worksArticle in conference proceedingsResearchpeer-review

Authors

Training processes of structured prediction models such as structural SVMs involve frequent computations of the maximum-a-posteriori (MAP) prediction given a parameterized model. For specific output structures such as sequences or trees, MAP estimates can be computed efficiently by dynamic programming algorithms such as the Viterbi algorithm and the CKY parser. However, when the output structures can be arbitrary graphs, exact calculation of the MAP estimate is an NP-complete problem. In this paper, we compare exact inference and approximate inference for labeling graphs. We study the exact junction tree and the approximate loopy belief propagation and sampling algorithms in terms of performance and ressource requirements.

Original languageEnglish
Title of host publicationMachine Learning and Knowledge Discovery in Databases : ECML PKDD 2008
EditorsWalter Daelemans, Bart Goethals, Katharina Morik
Number of pages13
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Publication date2008
Pages611-623
ISBN (print)978-3-540-87478-2
ISBN (electronic)978-3-540-87479-9
DOIs
Publication statusPublished - 2008
Externally publishedYes
EventEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases - 2008 - Antwerpen, Belgium
Duration: 15.09.200819.09.2008
http://www.ecmlpkdd2008.org/