document: Grafting-light : fast , incremental feature selection and structure learning of Markov random fields 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 l1-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 l1-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 .
doc_bio_tags: O O O O O B I O B I O B I I B I O O O O O O O O O O O O O O O O B I O B I I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O B I O O O O O O O O O O O O O O O O O B I O O O O O O O O B I O O O