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

Researchers

  1. Lara Schimpf

Activities

  1. Disturbing Objects, Disquiet Objects
  2. Phase-mixture Modeling of Nanocrystalline Materials Including Gradient Effects of Higher Order
  3. Das Spiel der Differenzen
  4. Publishing without perishing: How to publish in English- speaking journals with high impact rates
  5. Green IT & IT-for-Green - 2010
  6. The Contract Governance Conference - 2010
  7. Regulation and Innovation
  8. Workshop zu Hochschulprofilierung und das deutsche Studentenwerk - 2015
  9. ‘Inanimate’ bodies and the soil in the art of Isabel Ruiz and Edgar Calel
  10. Skype, Tandem and other Technical Catastrophes
  11. The Value of Time and the Production of Heritage
  12. Fakultät Kulturwissenschaften (Organisation)
  13. Bridging Education and Science for Sustainable Development -2015
  14. When Middle Managers in the Public Sector create Value: Antecedents to Entrepreneurial Orientation
  15. ('World Café' format) of the Karamoja campaign
  16. Public Lecture Series "Global Politics" 2015
  17. Alcohol myopia as a mechanism for the effect of alcohol on goal commitment
  18. 26th CCSBE Conference 2010 (Veranstaltung)
  19. American Political Science Association - APSA 2010
  20. Making out the Case of Discourse Markers in ELT von Buysse, Lieven, ESSE-8 (European Society for the Study of English)
  21. Fakultät Bildung (Organisation)
  22. Female Identities in the Post-Utopian 2017
  23. The survey of surveys: a meta-analysis of arts participation surveys
  24. Feuilleton 2015
  25. Virtual Teacher Seminar: Teach about the U.S. 2021
  26. 3rd International Symposium for Engineering Education - 2010
  27. Treffen des Norddeutsche Netzwerk Nordamerikastudien 2015 (Veranstaltung)
  28. 6th IFAC Symposium on Advances in Automotive Control - 2010
  29. Neuchâtel Graduate Conference of Migration and Mobility Studies - 2019
  30. 75th Annual Meeting of the Academy of Management (Veranstaltung)