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. Development of a quality assurance framework for the open source development model
  2. Different approaches to learning from errors: Comparing the effectiveness of high reliability and error management approaches
  3. A Control Scheme for PMSMs using Model Predictive Control and a Feedforward Action in the Presence of Saturated Inputs
  4. Changing the Administration from within:
  5. Dynamically changing sequencing rules with reinforcement learning in a job shop system with stochastic influences
  6. Joint entity and relation linking using EARL
  7. Using cross-recurrence quantification analysis to compute similarity measures for time series of unequal length with applications to sleep stage analysis
  8. Accounting and Modeling as Design Metaphors for CEMIS
  9. Using complexity metrics with R-R intervals and BPM heart rate measures
  10. Recurrence quantificationanalysis as a general-purpose tool for bridging the gap between qualitative and quantitative analysis
  11. ActiveMath - a Learning Platform With Semantic Web Features
  12. The Scalable Question Answering Over Linked Data (SQA) Challenge 2018
  13. An expert-based reference list of variables for characterizing and monitoring social-ecological systems
  14. Analyzing User Journey Data In Digital Health: Predicting Dropout From A Digital CBT-I Intervention
  15. Using transition management concepts for the evaluation of intersecting policy domains ('grand challenges')
  16. Global temporal typing patterns in foreign language writing
  17. Complex problem solving and intelligence
  18. Finding Creativity in Predictability: Seizing Kairos in Chronos Through Temporal Work in Complex Innovation Processes
  19. XOperator - An extensible semantic agent for instant messaging networks
  20. Proxies
  21. Conceptualizing Role Development in Agile Transformations
  22. Integration of Environmental Management Information Systems and ERP systems using Integration Platforms
  23. Enhancing the Building Information Modeling Lifecycle of Complex Structures with IoT
  24. Intersection tests for the cointegrating rank in dependent panel data
  25. On robustness properties in permanent magnet machine control by using decoupling controller
  26. Visualization of the Plasma Frequency by means of a Particle Simulation using a Normalized Periodic Model
  27. The role of learners’ memory in app-based language instruction: the case of Duolingo.
  28. Global Finite-Time Stabilization of Planar Linear Systems With Actuator Saturation