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

Recently viewed

Publications

  1. 'SPREAD THE APP, NOT THE VIRUS’ – AN EXTENSIVE SEM-APPROACH TO UNDERSTAND PANDEMIC TRACING APP USAGE IN GERMANY
  2. Convolutional Neural Networks
  3. Age effects on controlling tools with sensorimotor transformations
  4. Stability analysis of a linear model predictive control and its application in a water recovery process
  5. Structural Synthesis of Parallel Robots with Unguided Linear Actuators
  6. TARGET SETTING FOR OPERATIONAL PERFORMANCE IMPROVEMENTS - STUDY CASE -
  7. Machine vision system errors for unmanned aerial vehicle navigation
  8. A PD regulator to minimize noise effect using a minimal variance method for soft landing control of an electromagnetic valve actuator
  9. Order parameters and energies of analytic and singular vortex lines in rotating3He-A
  10. Analytic reproducibility in articles receiving open data badges at the journal Psychological Science
  11. Exploring large vegetation databases to detect temporal trends in species occurrences
  12. Are criminals better lie detectors? Investigating offenders' abilities in the context of deception detection
  13. Effects of maize roots on aggregate stability and enzyme activities in soil
  14. Geometric series with randomly increasing exponents
  15. WHICH ESTIMATION SITUATIONS ARE RELEVANT FOR A VALID ASSESSMENT OF MEASUREMENT ESTIMATION SKILLS
  16. Performance of an IMU-Based Sensor Concept for Solving the Direct Kinematics Problem of the Stewart-Gough Platform
  17. Space Systems Cross-Compatibility
  18. Cross-hedging minimum return guarantees
  19. Fermentative utilization of coffee mucilage using Bacillus coagulans and investigation of down-stream processing of fermentation broth for optically pure L(+)-lactic acid production
  20. rSOESGOPE Method Applied to Four-Tank System Modeling
  21. The role of plant biodiversity in modifying the structure and functioning of higher tropic Levels in species-rich forests
  22. DigiSchreib
  23. Comparison of Software Tools for Liquid Chromatography-High-Resolution Mass Spectrometry Data Processing in Nontarget Screening of Environmental Samples
  24. Guest Editors' Introduction
  25. Polynomial Augmented Extended Kalman Filter to Estimate the State of Charge of Lithium-Ion Batteries
  26. A Model Based Feedforward Regulator Improving PI Control of an Ice-Clamping Device Activated by Thermoelectric Cooler