Exact and approximate inference for annotating graphs with structural SVMs

Publikation: Beiträge in SammelwerkenAufsätze in KonferenzbändenForschungbegutachtet

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. 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 SammelwerkenAufsätze in KonferenzbändenForschungbegutachtet

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 (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

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 (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

Vancouver

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

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 -

DOI

Zuletzt angesehen

Aktivitäten

  1. Activating an Integrative Mindset Improves the Subjective Outcomes of Value-Driven Conflicts
  2. 13th IFAC and IEEE Conference on Programmable Devices and Embedded Systems - PDeS 2015
  3. Workshop of the Nordic Research Network in Memory Studies - 2013
  4. Plasma shock wave simulation for laser shock processing
  5. Workshop: The Black Technical Object
  6. Modelling biodegradability based on OECD 301D data for the design of mineralising ionic liquids
  7. Transdisciplinary Evaluation of Different Coastal Adaptation Strategies: Integrating Regional Perceptions of Scientists, Practitioners and the Public
  8. Interpretation and contestation of fracking in a changing context: The case of Germany and its proclaimed energy transition
  9. Reading strategy instruction and students' perceptions on fostering self-regulated reading
  10. 4th CRITICS Workshop and Winter School on “Critical Transitions in Complex Systems: Mathematical theory and applications”
  11. Interpreting integrative political strategies as boundary objects
  12. Interactions between social movements and international organisations
  13. Management and lnternational Networking Workshop 2014
  14. MIZ allgemein (Organisation)
  15. Empathic Healthcare Chatbots: Comparing the Effects of Emotional Expression and Caring Behavior
  16. IEEE International Conference on Advanced Intelligent Mechatronics 2017
  17. 15th Internation Conference on Renewable Resources and Biorefineries
  18. Workshop on plasma modelling and simulation - WOPMAS 2018
  19. Development and Validation of a U.S. and German Short Version of the Later Life Workplace Index (LLWI-S)

Publikationen

  1. Automatic feature selection for anomaly detection
  2. Performance incentives in activity-based management
  3. Comparison of Bio-Inspired Algorithms in a Case Study for Optimizing Capacitor Bank Allocation in Electrical Power Distribution
  4. Tuning kalman filter in linear systems
  5. How mobile app design impacts user responses to mixed self-tracking outcomes
  6. Implementation of formative assessment
  7. A Comparative Study for Fisheye Image Classification
  8. The role of task meaning on output in groups
  9. Optimal scheduling of AGVs in a reentrant blocking job-shop
  10. General Patterns and Conclusions
  11. Model-based nonlinear filter design for tower load reduction of wind power plants with active power control capability
  12. Self-perceived quality of life predicts mortality risk better than a multi-biomarker panel, but the combination of both does best
  13. Comparison of Supervised versus Self-Administered Stretching on Bench Press Maximal Strength and Force Development
  14. Putting adaptive planning into practice: A meta-analysis of current applications
  15. Almost-invariant and finite-time coherent sets
  16. A common European asylum system? How variation in Member States’ administrative capacity undermines EU asylum harmonisation
  17. Studying properties of water data using manifold-aware anomaly detectors
  18. Algorithmisches Management
  19. Quantification of amino acids in fermentation media by isocratic HPLC analysis of their
  20. A Stacked Planar Sensor Concept for Minimally Invasive Plasma Monitoring
  21. How to move the transition to sustainable food consumption towards a societal tipping point
  22. A review of mobile language learning applications
  23. Microsimulation - A survey of principles, developments and applications