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. Finding Creativity in Predictability: Seizing Kairos in Chronos Through Temporal Work in Complex Innovation Processes
  2. Commitment to grand challenges in fluid forms of organizing
  3. The Replication Database: Documenting the Replicability of Psychological Science
  4. Study of fuzzy controllers performance
  5. Modernizing persistence–bioaccumulation–toxicity (PBT) assessment with high throughput animal-free methods
  6. Special Issue The Discourse of Redundancy Introduction
  7. Exploiting ConvNet diversity for flooding identification
  8. Modelling, explaining, enacting and getting feedback: How can the acquisition of core practices in teacher education be optimally fostered?
  9. Development of Early Spatial Perspective-Taking - Toward a Three-Level Model
  10. Introduction
  11. Visual Detection of Traffic Incident through Automatic Monitoring of Vehicle Activities
  12. Who can nudge for sustainable development? How nudge source renders dynamic norms (in-)effective in eliciting sustainable behavior
  13. Biodegradability and genotoxicity of surface functionalized colloidal silica (SiO2) particles in the aquatic environment
  14. Towards a caring transdisciplinary research practice
  15. A slow-fast trait continuum at the whole community level in relation to land-use intensification
  16. Measurement in Machine Vision Editorial Paper
  17. Hedge Detection Using the RelHunter Approach
  18. Chronic effects of a static stretching intervention program on range of motion and tissue hardness in older adults
  19. How to support students-learning in mathematical bridging-courses using ITS? Remedial Scenarios in the EU-Project Math-Bridge
  20. Study of non-linear systems
  21. Using latent class analysis to produce a typology of environmental concern in the UK
  22. Ablation Study of a Multimodal Gat Network on Perfect Synthetic and Real-world Data to Investigate the Influence of Language Models in Invoice Recognition
  23. Implementation of Chemometric Tools to Improve Data Mining and Prioritization in LC-HRMS for Nontarget Screening of Organic Micropollutants in Complex Water Matrixes
  24. The language of situated joint activity: Social virtual reality and language learning in virtual exchange
  25. Anonymized firm data under test: evidence from a replication study
  26. How development leads to democracy
  27. Predicting recurrent chat contact in a psychological intervention for the youth using natural language processing
  28. Dimensions, dialectic, discourse
  29. Model-Based Optimization of Spiral Coils for Improving Wireless Power Transfer
  30. Synthesis and future research directions linking tree diversity to growth, survival, and damage in a global network of tree diversity experiments