2009 PrimalSparseMaxMarginMarkovNetw

• (Zhu et al., 2009) ⇒ Jun Zhu, Eric P. Xing, and Bo Zhang. (2009). “Primal Sparse Max-margin Markov Networks.” In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2009). doi:10.1145/1557019.1557132

Subject Headings: Max-Margin Markov Network.

Notes

• Categories and Subject Descriptors: I.5.1 Pattern Recognition: Models - Statistical.
• General Terms: Algorithms, Experimentation

Cited By

• http://scholar.google.com/scholar?q=%22Primal+sparse+Max-margin+Markov+networks%22+2009
• http://portal.acm.org/citation.cfm?doid=1557019.1557132&preflayout=flat#citedby

Quotes

Author Keywords

L1-Norm Max-Margin Markov Networks, Primal Sparsity, Dual Sparsity

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 prediction accuracy and time efficiency.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2009 PrimalSparseMaxMarginMarkovNetw	Eric P. Xing Jun Zhu Bo Zhang			Primal Sparse Max-margin Markov Networks		KDD-2009 Proceedings		10.1145/1557019.1557132		2009