Discriminative unsupervised learning of structured predictors

ABSTRACT

We present a new unsupervised algorithm for training structured predictors that is discriminative, convex, and avoids the use of EM. The idea is to formulate an unsupervised version of structured learning methods, such as maximum margin Markov networks, that can be trained via semidefinite programming. The result is a discriminative training criterion for structured predictors (like hidden Markov models) that remains unsupervised and does not create local minima. To reduce training cost, we reformulate the training procedure to mitigate the dependence on semidefinite programming, and finally propose a heuristic procedure that avoids semidefinite programming entirely. Experimental results show that the convex discriminative procedure can produce better conditional models than conventional Baum-Welch (EM) training.

REFERENCES

• 1: Altun, Y., McAllester, D., & Belkin, M. (2005). Maximum margin semi-supervised learning for structured variables. Proceedings NIPS 18.
• 2: Altun, Y., Tsochantaridis, I., & Hofmann, T. (2003). Hidden Markov support vector machines. Proc. ICML.
• 3: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 4: Koby Crammer , Yoram Singer, On the algorithmic implementation of multiclass kernel-based vector machines, The Journal of Machine Learning Research, 2, 3/1/2002
• 5: De Bie, T., & Cristianini, N. (2003). Convex methods for transduction. Proceedings NIP 16.
• 6: Durbin, B., Eddy, S., Krogh, A., & Mitchison, G. (1998). Biological sequence analysis. Cambridge U. Press.
• 7: Helmberg, C. (2000). Semidefinite programming for combinatorial optimization (Technical Report).
• 8: Frederick Jelinek, Statistical methods for speech recognition, MIT Press, Cambridge, MA, 1998
• 9: Daniel Jurafsky , James H. Martin, Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition, Prentice Hall PTR, Upper Saddle River, NJ, 2000
• 10: John D. Lafferty , Andrew McCallum , Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.282-289, June 28-July 01, 2001
• 11: Laurent, M., & Poljak, S. (1995). On a positive semidefinite relaxation of the cut polytope. Linear Algebra and its Applications, 223/224.
• 12: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 13: Nesterov, Y., & Nimirovskii, A. (1994). Interior-point polynomial algorithms in convex programming. SIAM.
• 14: Rabiner, L. (1989). A tutorial on hidden Markov models and selected applications in speech recognition. Proc. of IEEE, 77, 257--286.
• 15: Taskar, B., Guestrin, C., & Koller, D. (2003). Max-margin Markov networks. Proceedings NIPS 16.
• 16: 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]
• 17: Xu, L., Neufeld, J., Larson, B., & Schuurmans, D. (2004). Maximum margin clustering. NIPS 17.
• 18: Xu, L., & Schuurmans, D. (2005). Unsupervised and semi-supervised multi-class support vector machines. Proceedings AAAI.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing; Markov processes

General Terms:
Theory