On Primal and Dual Sparsity of Markov Networks

Abstract

Sparsity is a desirable property in high dimensional learning. The l₁-norm regularization can lead to primal sparsity, while max-margin methods achieve dual sparsity. Combining these two methods, an l₁-norm max-margin Markov network (l₁-M³N) can achieve both types of sparsity. This paper analyzes its connections to the Laplace max-margin Markov network (LapM³N), which inherits the dual sparsity of max-margin models but is pseudo-primal sparse, and to a novel adaptive M³N (AdapM³N). We show that the l₁-M³N is an extreme case of the LapM³N, and the l₁-M³N is equivalent to an AdapM³N. Based on this equivalence we develop a robust EM-style algorithm for learning an l₁-M³N. We demonstrate the advantages of the simultaneously (pseudo-) primal and dual sparse models over the ones which enjoy either primal or dual sparsity on both synthetic and real data sets.