Exact and approximate inference for annotating graphs with structural SVMs
Research output: Contributions to collected editions/works › Article in conference proceedings › Research › peer-review
Standard
Exact and approximate inference for annotating graphs with structural SVMs. / Klein, Thoralf; Brefeld, Ulf; Scheffer, Tobias.
Machine Learning and Knowledge Discovery in Databases: ECML PKDD 2008. ed. / Walter Daelemans; Bart Goethals; Katharina Morik. Berlin, Heidelberg : Springer, 2008. p. 611-623 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5211 LNAI, No. PART 1).Research output: Contributions to collected editions/works › Article in conference proceedings › Research › peer-review
Harvard
APA
Vancouver
Bibtex
}
RIS
TY - CHAP
T1 - Exact and approximate inference for annotating graphs with structural SVMs
AU - Klein, Thoralf
AU - Brefeld, Ulf
AU - Scheffer, Tobias
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
KW - Informatics
KW - Gibbs Sampling
KW - Graph Size
KW - Junction Tree
KW - Approximate Inference
KW - Exact Inference
KW - Business informatics
UR - http://www.scopus.com/inward/record.url?scp=56049121271&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-87479-9_58
DO - 10.1007/978-3-540-87479-9_58
M3 - Article in conference proceedings
AN - SCOPUS:56049121271
SN - 978-3-540-87478-2
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 611
EP - 623
BT - Machine Learning and Knowledge Discovery in Databases
A2 - Daelemans, Walter
A2 - Goethals, Bart
A2 - Morik, Katharina
PB - Springer
CY - Berlin, Heidelberg
T2 - European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases - 2008
Y2 - 15 September 2008 through 19 September 2008
ER -