Exact and approximate inference for annotating graphs with structural SVMs

Thoralf Klein; Ulf Brefeld; Tobias Scheffer

doi:10.1007/978-3-540-87479-9_58

Exact and approximate inference for annotating graphs with structural SVMs

Thoralf Klein^*
, Ulf Brefeld
, Tobias Scheffer

^*Korrespondierende/r Autor/-in für diese Arbeit

Publikation: Beiträge in Sammelwerken › Aufsätze in Konferenzbänden › Forschung › Begutachtung

1 Zitat (Scopus)

Abstract

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.

Originalsprache	Englisch
Titel	Machine Learning and Knowledge Discovery in Databases : ECML PKDD 2008
Redakteure/-innen	Walter Daelemans, Bart Goethals, Katharina Morik
Seitenumfang	13
Erscheinungsort	Berlin, Heidelberg
Herausgeber (Verlag)	Springer Verlag
Erscheinungsdatum	2008
Seiten	611-623
ISBN (Print)	978-3-540-87478-2
ISBN (elektronisch)	978-3-540-87479-9
DOIs	https://doi.org/10.1007/978-3-540-87479-9_58
Publikationsstatus	Erschienen - 2008
Extern publiziert	Ja
Veranstaltung	European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases - 2008 - Antwerpen, Belgien Dauer: 15.09.2008 → 19.09.2008 http://www.ecmlpkdd2008.org/

Fachgebiete und Schlagwörter

Informatik
Wirtschaftsinformatik

Zugriff auf Dokument

10.1007/978-3-540-87479-9_58

Dieses zitieren

Klein, T., Brefeld, U., & Scheffer, T. (2008). Exact and approximate inference for annotating graphs with structural SVMs. in W. Daelemans, B. Goethals, & K. Morik (Hrsg.), Machine Learning and Knowledge Discovery in Databases: ECML PKDD 2008 (S. 611-623). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 5211 LNAI, Nr. PART 1). Springer Verlag. https://doi.org/10.1007/978-3-540-87479-9_58

Klein, Thoralf ; Brefeld, Ulf ; Scheffer, Tobias. / Exact and approximate inference for annotating graphs with structural SVMs. Machine Learning and Knowledge Discovery in Databases: ECML PKDD 2008. Hrsg. / Walter Daelemans ; Bart Goethals ; Katharina Morik. Berlin, Heidelberg : Springer Verlag, 2008. S. 611-623 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

@inbook{4610070ef2d44c358ad392559f8fe61e,

title = "Exact and approximate inference for annotating graphs with structural SVMs",

abstract = "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.",

keywords = "Informatics, Gibbs Sampling, Graph Size, Junction Tree, Approximate Inference, Exact Inference, Business informatics",

author = "Thoralf Klein and Ulf Brefeld and Tobias Scheffer",

year = "2008",

doi = "10.1007/978-3-540-87479-9\_58",

language = "English",

isbn = "978-3-540-87478-2",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

number = "PART 1",

pages = "611--623",

editor = "Walter Daelemans and Bart Goethals and Katharina Morik",

booktitle = "Machine Learning and Knowledge Discovery in Databases",

address = "Germany",

note = "European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases - 2008, ECML PKDD 2008 ; Conference date: 15-09-2008 Through 19-09-2008",

url = "http://www.ecmlpkdd2008.org/",

}

Klein, T, Brefeld, U & Scheffer, T 2008, Exact and approximate inference for annotating graphs with structural SVMs. in W Daelemans, B Goethals & K Morik (Hrsg.), Machine Learning and Knowledge Discovery in Databases: ECML PKDD 2008. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Nr. PART 1, Bd. 5211 LNAI, Springer Verlag, Berlin, Heidelberg, S. 611-623, European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases - 2008, Antwerpen, Belgien, 15.09.08. https://doi.org/10.1007/978-3-540-87479-9_58

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. Hrsg. / Walter Daelemans; Bart Goethals; Katharina Morik. Berlin, Heidelberg: Springer Verlag, 2008. S. 611-623 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 5211 LNAI, Nr. PART 1).

Publikation: Beiträge in Sammelwerken › Aufsätze in Konferenzbänden › Forschung › Begutachtung

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 - https://www.scopus.com/pages/publications/56049121271

UR - https://www.mendeley.com/catalogue/d2368264-b85e-3034-944e-a245641cbc08/

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 Verlag

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 -

Klein T, Brefeld U, Scheffer T. Exact and approximate inference for annotating graphs with structural SVMs. in Daelemans W, Goethals B, Morik K, Hrsg., Machine Learning and Knowledge Discovery in Databases: ECML PKDD 2008. Berlin, Heidelberg: Springer Verlag. 2008. S. 611-623. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-540-87479-9_58

Exact and approximate inference for annotating graphs with structural SVMs

Abstract

Fachgebiete und Schlagwörter

Zugriff auf Dokument

Fingerprint

Dieses zitieren