2010 GraftingLightFastIncrementalFea

• (Zhu et al., 2010) ⇒ Jun Zhu, Ni Lao, and Eric P. Xing. (2010). “Grafting-light: Fast, Incremental Feature Selection and Structure Learning of Markov Random Fields.” In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2010). doi:10.1145/1835804.1835845

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%22Grafting-light%3A+fast%2C+incremental+feature+selection+and+structure+learning+of+Markov+random+fields%22+2010
• http://portal.acm.org/citation.cfm?id=1835845&preflayout=flat#citedby

Quotes

Abstract

Feature selection is an important task in order to achieve better generalizability in high dimensional learning, and structure learning of Markov random fields (MRFs) can automatically discover the inherent structures underlying complex data. Both problems can be cast as solving an [math]\displaystyle{ \ell_1 }[/math]-norm regularized parameter estimation problem. The existing Grafting method can avoid doing inference on dense graphs in structure learning by incrementally selecting new features. However, Grafting performs a greedy step to optimize over free parameters once new features are included. This greedy strategy results in low efficiency when parameter learning is itself non-trivial, such as in MRFs, in which parameter learning depends on an expensive subroutine to calculate gradients. The complexity of calculating gradients in MRFs is typically exponential to the size of maximal cliques.

In this paper, we present a fast algorithm called Grafting-Light to solve the [math]\displaystyle{ \ell_1 }[/math]-norm regularized maximum likelihood estimation of MRFs for efficient feature selection and structure learning. Grafting-Light iteratively performs one-step of orthant-wise gradient descent over free parameters and selects new features. This lazy strategy is guaranteed to converge to the global optimum and can effectively select significant features. On both synthetic and real data sets, we show that Grafting-Light is much more efficient than Grafting for both feature selection and structure learning, and performs comparably with the optimal batch method that directly optimizes over all the features for feature selection but is much more efficient and accurate for structure learning of MRFs.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2010 GraftingLightFastIncrementalFea	Eric P. Xing Jun Zhu Ni Lao			Grafting-light: Fast, Incremental Feature Selection and Structure Learning of Markov Random Fields		KDD-2010 Proceedings		10.1145/1835804.1835845		2010