Primal sparse Max-margin Markov networks

ABSTRACT

Max-margin Markov networks (M³N) have shown great promise in structured prediction and relational learning. Due to the KKT conditions, the M³N enjoys dual sparsity. However, the existing M³N formulation does not enjoy primal sparsity, which is a desirable property for selecting significant features and reducing the risk of over-fitting. In this paper, we present an l₁-norm regularized max-margin Markov network (l₁-M³N), which enjoys dual and primal sparsity simultaneously. To learn an l₁-M³N, we present three methods including projected sub-gradient, cutting-plane, and a novel EM-style algorithm, which is based on an equivalence between l₁-M³N and an adaptive M³N. We perform extensive empirical studies on both synthetic and real data sets. Our experimental results show that: (1) l₁-M³N can effectively select significant features; (2) l₁-M³N can perform as well as the pseudo-primal sparse Laplace M³N in prediction accuracy, while consistently outperforms other competing methods that enjoy either primal or dual sparsity; and (3) the EM-algorithm is more robust than the other two in pre-diction accuracy and time efficiency.

REFERENCES

• 1: Y. Altun, I. Tsochantaridis, and T. Hofmann. Hidden {Markov} support vector machines. In ICML, 2003.
• 2: Galen Andrew , Jianfeng Gao, Scalable training of L¹-regularized log-linear models, Proceedings of the 24th international conference on Machine learning, p.33-40, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273501]
• 3: P. Bartlett, M. Collins, B. Taskar, and D. McAllester. Exponentiated gradient algorithms for larg-margin structured classification. In NIPS, 2004.
• 4: K. Bennett and O. Mangasarian. Robust linear programming discrimination of two linearly inseparable sets. Optim. Methods Softw, (1):23--34, 1992.
• 5: D.P. Bertsekas. Nonlinear Programming. Athena Scientific, 1999.
• 6: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 7: S. Boyd, L. Xiao, and A. Mutapcic. Subgradient methods. In Lecture Notes of EE392o}, Stanford University, Autumn Quarter, 2003--2004.
• 8: John Duchi , Shai Shalev-Shwartz , Yoram Singer , Tushar Chandra, Efficient projections onto the l₁-ball for learning in high dimensions, Proceedings of the 25th international conference on Machine learning, p.272-279, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390191]
• 9: Amir Globerson , Terry Y. Koo , Xavier Carreras , Michael Collins, Exponentiated gradient algorithms for log-linear structured prediction, Proceedings of the 24th international conference on Machine learning, p.305-312, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273535]
• 10: Y. Grandvalet. Least absolute shrinkage is equivalent to quadratic penalization. In ICANN, 1998.
• 11: Y. Grandvalet and S. Canu. Adaptive scaling for feature selection in svms. In NIPS, 2002.
• 12: T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning: Data Mining, Inference and Prediction. Springer Verlag, NY, 2001.
• 13: Thorsten Joachims , Thomas Finley , Chun-Nam John Yu, Cutting-plane training of structural SVMs, Machine Learning, v.77 n.1, p.27-59, October 2009 [doi>10.1007/s10994-009-5108-8]
• 14: Ata Kabán, On Bayesian classification with Laplace priors, Pattern Recognition Letters, v.28 n.10, p.1271-1282, July, 2007 [doi>10.1016/j.patrec.2007.02.010]
• 15: J.E. Kelley. The cutting-plane method for solving convex programs. J. Sco. Indust. Appl. Math., (4):703--712.
• 16: 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
• 17: S.-I. Lee, V. Ganapathi, and D. Koller. Efficient structure learning of {Markov} networks using l_1-regularization. In NIPS, 2006.
• 18: Radford M. Neal, Bayesian Learning for Neural Networks, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 19: N.D. Ratliff, J.A. Bagnell, and M.A. Zinkevich. (Online) Subgradient} methods for structured prediction. In AISTATS, 2007.
• 20: B. Taskar, C. Guestrin, and D. Koller. Max-margin {Markov} networks. In NIPS, 2003.
• 21: Choon Hui Teo , Alex Smola , S. V.N. Vishwanathan , Quoc Viet Le, A scalable modular convex solver for regularized risk minimization, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281270]
• 22: Michael E. Tipping, Sparse bayesian learning and the relevance vector machine, The Journal of Machine Learning Research, 1, p.211-244, 9/1/2001 [doi>10.1162/15324430152748236]
• 23: 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]
• 24: M.J. Wainwright, P. Ravikumar, and J. Lafferty. High-dimensional graphical model selection using l_1 regularized logistic regression. In NIPS, 2006.
• 25: Jun Zhu , Zaiqing Nie , Bo Zhang , Ji-Rong Wen, Dynamic Hierarchical Markov Random Fields for Integrated Web Data Extraction, The Journal of Machine Learning Research, 9, p.1583-1614, 6/1/2008
• 26: J. Zhu, S. Rosset, T. Hastie, and R. Tibshirani. 1-norm support vector machines. In NIPS, 2004.
• 27: Jun Zhu , Eric P. Xing , Bo Zhang, Laplace maximum margin Markov networks, Proceedings of the 25th international conference on Machine learning, p.1256-1263, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390314]
• 28: Jun Zhu , Eric P. Xing, On primal and dual sparsity of Markov networks, Proceedings of the 26th Annual International Conference on Machine Learning, p.1265-1272, June 14-18, 2009, Montreal, Quebec, Canada [doi>10.1145/1553374.1553536]
• 29: H. Zou. An improved 1-norm svm for simultaneous classification and variable selection. AISTATS, 2007.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
l_1-norm max-margin markov networks, dual sparsity, primal sparsity