Semi-supervised learning for structured output variables

ABSTRACT

The problem of learning a mapping between input and structured, interdependent output variables covers sequential, spatial, and relational learning as well as predicting recursive structures. Joint feature representations of the input and output variables have paved the way to leveraging discriminative learners such as SVMs to this class of problems. We address the problem of semi-supervised learning in joint input output spaces. The co-training approach is based on the principle of maximizing the consensus among multiple independent hypotheses; we develop this principle into a semi-supervised support vector learning algorithm for joint input output spaces and arbitrary loss functions. Experiments investigate the benefit of semi-supervised structured models in terms of accuracy and F1 score.

REFERENCES

• 1: Altun, Y., McAllester, D., & Belkin, M. (2006). Maximum margin semi-supervised learning for structured variables. Adv. in Neural Information Proc. Systems.
• 2: Altun, Y., Tsochantaridis, I., & Hofmann, T. (2003). Hidden Markov support vector machines. Proceedings of the International Conference on Machine Learning.
• 3: Avrim Blum , Tom Mitchell, Combining labeled and unlabeled data with co-training, Proceedings of the eleventh annual conference on Computational learning theory, p.92-100, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279962]
• 4: Brefeld, U., Büscher, C., & Scheffer, T. (2005). Multi-view discriminative sequential learning. Proceedings of the European Conference on Machine Learning.
• 5: Koby Crammer , Yoram Singer, On the algorithmic implementation of multiclass kernel-based vector machines, The Journal of Machine Learning Research, 2, 3/1/2002
• 6: Dasgupta, S., Littman, M., & McAllester, D. (2001). PAC generalization bounds for co-training. Advances in Neural Information Processing Systems.
• 7: Hardoon, D., Farquhar, J. D. R., Meng, H., Shawe-Taylor, J., & Szedmak, S. (2006). Two view learning: SVM-2K, theory and practice. Advances in Neural Information Processing Systems.
• 8: Thorsten Joachims, Transductive Inference for Text Classification using Support Vector Machines, Proceedings of the Sixteenth International Conference on Machine Learning, p.200-209, June 27-30, 1999
• 9: Thorsten Joachims, A support vector method for multivariate performance measures, Proceedings of the 22nd international conference on Machine learning, p.377-384, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102399]
• 10: Mark Johnson, PCFG models of linguistic tree representations, Computational Linguistics, v.24 n.4, p.613-632, December 1998
• 11: John Lafferty , Xiaojin Zhu , Yan Liu, Kernel conditional random fields: representation and clique selection, Proceedings of the twenty-first international conference on Machine learning, p.64, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015337]
• 12: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 13: Kamal Nigam , Rayid Ghani, Analyzing the effectiveness and applicability of co-training, Proceedings of the ninth international conference on Information and knowledge management, p.86-93, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354805]
• 14: Taskar, B., Guestrin, C., & Koller, D. (2004). Max-margin Markov networks. Advances in Neural Information Processing Systems.
• 15: Ioannis Tsochantaridis , Thorsten Joachims , Thomas Hofmann , Yasemin Altun, Large Margin Methods for Structured and Interdependent Output Variables, The Journal of Machine Learning Research, 6, p.1453-1484, 9/1/2005

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Neural nets

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

General Terms:
Theory