TY - JOUR
T1 - Efficient exact inference with loss augmented objective in structured learning
AU - Bauer, Alexander
AU - Nakajima, Shinichi
AU - Müller, Klaus Robert
N1 - Funding Information:
Manuscript received April 4, 2016; revised August 3, 2016; accepted August 3, 2016. Date of publication August 19, 2016; date of current version October 16, 2017. This work was supported by the Federal Ministry of Education and Research under the Berlin Big Data Center Project under Grant FKZ 01IS14013A. The work of K.-R. Müller was supported in part by the BK21 Program of NRF Korea, BMBF, under Grant 01IS14013A and in part by DFG. (Corresponding author: Klaus-Robert Müller.) A. Bauer and S. Nakajima are with the Berlin Big Data Center, Machine Learning Group, Technische Universität Berlin, 10623 Berlin, Germany (e-mail: alexander.bauer@tu-berlin.de; nakajima@tu-berlin.de).
Publisher Copyright:
© 2016 IEEE.
PY - 2017/11
Y1 - 2017/11
N2 - Structural support vector machine (SVM) is an elegant approach for building complex and accurate models with structured outputs. However, its applicability relies on the availability of efficient inference algorithms - the state-of-the-art training algorithms repeatedly perform inference to compute a subgradient or to find the most violating configuration. In this paper, we propose an exact inference algorithm for maximizing nondecomposable objectives due to special type of a high-order potential having a decomposable internal structure. As an important application, our method covers the loss augmented inference, which enables the slack and margin scaling formulations of structural SVM with a variety of dissimilarity measures, e.g., Hamming loss, precision and recall, Fβ-loss, intersection over union, and many other functions that can be efficiently computed from the contingency table. We demonstrate the advantages of our approach in natural language parsing and sequence segmentation applications.
AB - Structural support vector machine (SVM) is an elegant approach for building complex and accurate models with structured outputs. However, its applicability relies on the availability of efficient inference algorithms - the state-of-the-art training algorithms repeatedly perform inference to compute a subgradient or to find the most violating configuration. In this paper, we propose an exact inference algorithm for maximizing nondecomposable objectives due to special type of a high-order potential having a decomposable internal structure. As an important application, our method covers the loss augmented inference, which enables the slack and margin scaling formulations of structural SVM with a variety of dissimilarity measures, e.g., Hamming loss, precision and recall, Fβ-loss, intersection over union, and many other functions that can be efficiently computed from the contingency table. We demonstrate the advantages of our approach in natural language parsing and sequence segmentation applications.
KW - Dynamic programming
KW - Graphical models
KW - High-order potentials
KW - Inference
KW - Margin scaling (MS)
KW - Slack scaling (SS)
KW - Structural support vector machines (SVMs)
KW - Structured output
UR - http://www.scopus.com/inward/record.url?scp=84983036054&partnerID=8YFLogxK
U2 - 10.1109/TNNLS.2016.2598721
DO - 10.1109/TNNLS.2016.2598721
M3 - Article
C2 - 28113643
AN - SCOPUS:84983036054
SN - 2162-237X
VL - 28
SP - 2566
EP - 2579
JO - IEEE Transactions on Neural Networks and Learning Systems
JF - IEEE Transactions on Neural Networks and Learning Systems
IS - 11
M1 - 7547945
ER -