1. //
  2. Start
  3. //
  4. Publications
  5. Exact and approximate inference for anno...
  6. Output formats
  7. //

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 Verlag, 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

Klein, T, Brefeld, U & Scheffer, T 2008, Exact and approximate inference for annotating graphs with structural SVMs. in W Daelemans, B Goethals & K Morik (eds), 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), no. PART 1, vol. 5211 LNAI, Springer Verlag, Berlin, Heidelberg, pp. 611-623, European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases - 2008, Antwerpen, Belgium, 15.09.08. https://doi.org/10.1007/978-3-540-87479-9_58

APA

Klein, T., Brefeld, U., & Scheffer, T. (2008). Exact and approximate inference for annotating graphs with structural SVMs. In W. Daelemans, B. Goethals, & K. Morik (Eds.), Machine Learning and Knowledge Discovery in Databases: ECML PKDD 2008 (pp. 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). Springer Verlag. https://doi.org/10.1007/978-3-540-87479-9_58

Vancouver

Klein T, Brefeld U, Scheffer T. Exact and approximate inference for annotating graphs with structural SVMs. In Daelemans W, Goethals B, Morik K, editors, Machine Learning and Knowledge Discovery in Databases: ECML PKDD 2008. Berlin, Heidelberg: Springer Verlag. 2008. p. 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

Bibtex

@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/",

}

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

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 -

Other publications by the same author(s)

Interactive sequential generative models for team sports

Fassmeyer, D., Cordes, M. & Brefeld, U., 02.2025, In: Machine Learning. 114, 2, 15 p., 38.

Research output: Journal contributions › Journal articles › Research › peer-review

Joint Item Response Models for Manual and Automatic Scores on Open-Ended Test Items

Bengs, D., Brefeld, U., Kroehne, U. & Zehner, F., 2025, (Accepted/In press) In: Psychometrika.

Research output: Journal contributions › Journal articles › Research › peer-review

Machine Learning and Data Mining for Sports Analytics: 11th International Workshop, MLSA 2024, Vilnius, Lithuania, September 9, 2024, Revised Selected Papers

Brefeld, U. (Editor), Davis, J. (Editor), Van Haaren, J. (Editor) & Zimmermann, A. (Editor), 2025, Cham: Springer Verlag. 119 p. (Communications in Computer and Information Science; vol. 2460)

Research output: Books and anthologies › Conference proceedings › Research

Masked autoencoder for multiagent trajectories

Rudolph, Y. & Brefeld, U., 02.2025, In: Machine Learning. 114, 2, 18 p., 44.

Research output: Journal contributions › Journal articles › Research › peer-review

The promise and challenges of computer mouse trajectories in DMHIs – A feasibility study on pre-treatment dropout predictions

Zantvoort, K., Matthiesen, J., Bjurner, P., Bendix, M., Brefeld, U., Funk, B. & Kaldo, V., 06.2025, In: Internet Interventions. 40, 7 p., 100828.

Research output: Journal contributions › Journal articles › Research › peer-review

DOI

Recently viewed

Activities

  1. Where Did It Come From? Deep Learning for Event Extraction in Art Provenance
  2. Contractual Solutions for Addressing Harmful Interference
  3. The Linguistic Complexity of Test Items: Differential Effects for Students With Low and High Language Proficiency
  4. The Irish English discourse marker sure at the semantics/pragmatics interface
  5. Workshop mit David Bates: "Compossible Worlds"
  6. Rapid Prototyping of a Mechatronic Engine Valve Controller for IC Engines
  7. "Crowds and Party" Reading Workshop with Jody Dean - 2019
  8. Modeling Grounding Processes in Chat-Based CSCL
  9. Measuring is Knowing
  10. Unintended Consequences of Field Experiments in Poverty Settings
  11. Mathematikdidaktisches Kolloquium
  12. OR Spectrum (Zeitschrift)
  13. Zootechnologies. Swarming as a Cultural Technique
  14. What could university look like in the 21st Century. The Global Classroom Curriculum
  15. Group Decision and Negotiation (Fachzeitschrift)
  16. Summer School in the context of Biodiversity-Ecosystem Functioning 2012

Publications

  1. Applying the Three Horizons approach in local and regional scenarios to support policy coherence in SDG implementation
  2. Comparison of different FEM codes approach for extrusion process analysis
  3. Self-regulation in error management training: emotion control and metacognition as mediators of performance effects
  4. Holistic and scalable ranking of RDF data
  5. How Much Home Office is Ideal? A Multi-Perspective Algorithm
  6. Model and Validation of the Electromagnetic Interference Produced by Power Transmission Lines in Robotic Systems
  7. Development of a Parameterized Model for Additively Manufactured Dies to Control the Strains in Extrudates
  8. Advances in Computer Science and Engineering
  9. Highly Efficient IPT Transmitter Circuit Based on a Novel Enhanced Class B Amplifier for Consumer Applications
  10. Biomedical Entity Linking with Triple-aware Pre-Training
  11. Anwendungsprogrammierung mit Embedded-SQL
  12. Methods in Writing Process Research
  13. Non-destructive transmissive inductive thickness sensor for IoT applications
  14. Composing with the terra fluida of interaction: new paths for CCO research as relational practice
  15. Doing statistics, enacting the nation
  16. Investigating Factors on R estorative Sleep Quality and its Relationship with Personal Work Performance - An Analysis of Diary Data
  17. Experimental Investigation of Efficiency and Deposit Process Temperature During Multi-Layer Friction Surfacing
  18. Secondary task as a measure of cognitive load
  19. The State of Multimedia Mass-Balance Modeling in Environmental science and decision-making
  20. Predicting recurrent chat contact in a psychological intervention for the youth using natural language processing
  21. Media Review: Extrapolations - A View from OS4F
  22. Combining Model Predictive and Adaptive Control for an Atomic Force Microscope Piezo-Scanner-Cantilever System
  23. Material system analysis
  24. The use of pseudo-causal narratives in EU policies
  25. Motivation for the Continuation of Work
  26. An optimal minimum phase approximating PD regulator for robust control of a throttle plate
  27. Agile Portfolio Management Patterns
  28. Investigating quality raters' performance using interface evaluation methods