Fixed-threshold SMO for Joint Constraint Learning Algorithm of Structural SVM

ABSTRACT

In this paper, we describe a fixed-threshold sequential minimal optimization (FSMO) for a joint constraint learning algorithm of structural classification SVM problems. Because FSMO uses the fact that the joint constraint formulation of structural SVM has b=0, FSMO breaks down the quadratic programming (QP) problems of structural SVM into a series of smallest QP problems, each involving only one variable. By using only one variable, FSMO is advantageous in that each QP sub-problem does not need subset selection.

REFERENCES

• 1: V. Vapnik, Statistical Learning theory, Wiley, New York, 1998.
• 2: J. Platt, "Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines," Microsoft Research Technical Report MSR-TR-98-14, 1998.
• 3: Ioannis Tsochantaridis , Thomas Hofmann , Thorsten Joachims , Yasemin Altun, Support vector machine learning for interdependent and structured output spaces, Proceedings of the twenty-first international conference on Machine learning, p.104, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015341]
• 4: Thorsten Joachims, A statistical learning learning model of text classification for support vector machines, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.128-136, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383974]
• 5: D. Sculley , Gabriel M. Wachman, Relaxed online SVMs for spam filtering, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277813]
• 6: Yisong Yue , Thomas Finley , Filip Radlinski , Thorsten Joachims, A support vector method for optimizing average precision, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277790]
• 7: B. Taskar, C. Guestrin, and D. Koller, "Max margin markov networks," NIPS 16, 2004.
• 8: Thorsten Joachims, Training linear SVMs in linear time, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150429]
• 9: C. Lee, J. Eun, M. Jeong, G. Lee, Y. Hwang, and M. Jang, "A Multi-Strategic Concept-Spotting Approach for Robust Understanding of Spoken Korean," ETRI J., vol. 29, no. 2, 2007, pp. 179--188.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Abstracting methods

General Terms:
Algorithms, Experimentation

Keywords:
fixed-threshold SMO, joint constraint learning algorithm, structural SVM