Exact and approximate inference for annotating graphs with structural SVMs

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

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.
OriginalspracheEnglisch
TitelMachine Learning and Knowledge Discovery in Databases : ECML PKDD 2008
HerausgeberWalter Daelemans, Bart Goethals, Katharina Morik
Anzahl der Seiten13
ErscheinungsortBerlin, Heidelberg
VerlagSpringer Verlag
Erscheinungsdatum2008
Seiten611-623
ISBN (Print)978-3-540-87478-2
ISBN (elektronisch)978-3-540-87479-9
DOIs
PublikationsstatusErschienen - 2008
Extern publiziertJa
VeranstaltungEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases - 2008 - Antwerpen, Belgien
Dauer: 15.09.200819.09.2008
http://www.ecmlpkdd2008.org/

DOI

Zuletzt angesehen

Publikationen

  1. From Knowledge to Application
  2. Critical look at dynamic sketches when learning mathematics
  3. Service Level Driven Stock Allocation
  4. From Open Access to Open Science
  5. Plant density modifies root system architecture in spring barley (Hordeum vulgare L.) through a change in nodal root number
  6. Almost-invariant and finite-time coherent sets
  7. Reduction of springback by use of deep drawing tools with locally and temporally varying stiffness
  8. Microstructure refinement by a novel friction-based processing on Mg-Zn-Ca alloy
  9. Does an individualized learning design improve university student online learning? A randomized field experiment
  10. Learning to collaborate from diverse interactions in project-based sustainability courses
  11. Microstructure characterisation and creep properties of AE42 based hybrid composites prepared by squeeze casting process
  12. Interdiffusion and atomic mobility in hcp Mg–Al–Sn alloys
  13. Part IV: Theoretical and methodological advancements in disturbance rejection and robust control
  14. Microstructure, mechanical and functional properties of refill friction stir spot welds on multilayered aluminum foils for battery application
  15. John Howard Yoder
  16. Implementation of Sustainability Management and Company Size
  17. Mecanum wheel slip detection model implemented on velocity-controlled drives
  18. Model-based wind turbine control design with power tracking capability
  19. Representative time use data and calibration of the American time use studies 1965 - 1999
  20. Prolog und relationale Datenbanken als Grundlagen zur Implementierung einer NF2-Datenbank
  21. Gemeinsam lernen mit Selbstlernprogrammen
  22. Impact assessment of emissions stabilization scenarios with and without induced technological change
  23. Ice clamping system in manufacturing systems as a cyber-physical system towards Industry 4.0
  24. Special Issue: Proactive behaviour across group boundaries:
  25. The interaction of ecological norm orientation and external factors in the domain of travel mode choice behavior
  26. Developing Digitalization Strategies for SMEs
  27. Why the Future Is (Still) Democratic
  28. Energy transitions in small-scale regions – What we can learn from a regional innovation systems perspective.
  29. An InfoSpace Paradigm for Local and ad hoc Peer-to-Peer Communication
  30. We'll get them to do anything! Funny Inventions and Marketing
  31. Reliability, factor structure, and measurement invariance of the dominic interactive across European countries
  32. Advanced oxidation processes in the treatment of trifluraline effluent
  33. Fast response of groundwater to heavy rainfall
  34. The effect of organic acids and alcohols on precipitation of phosphate using calcined seashell powder
  35. Putting sustainable chemistry and resource use into context
  36. Out of the box
  37. The technological condition
  38. The Bali Convention: flexibility of targets and instruments inevitable
  39. Elution of monomers from three different bonding systems and their antibacterial effect
  40. Strategies, uncertainty and performance of small business startups
  41. y-Randomization and its variants in QSPR/QSAR