nips nips2009 nips2009-224 nips2009-224-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jean Honorio, Dimitris Samaras, Nikos Paragios, Rita Goldstein, Luis E. Ortiz
Abstract: Locality information is crucial in datasets where each variable corresponds to a measurement in a manifold (silhouettes, motion trajectories, 2D and 3D images). Although these datasets are typically under-sampled and high-dimensional, they often need to be represented with low-complexity statistical models, which are comprised of only the important probabilistic dependencies in the datasets. Most methods attempt to reduce model complexity by enforcing structure sparseness. However, sparseness cannot describe inherent regularities in the structure. Hence, in this paper we first propose a new class of Gaussian graphical models which, together with sparseness, imposes local constancy through 1 -norm penalization. Second, we propose an efficient algorithm which decomposes the strictly convex maximum likelihood estimation into a sequence of problems with closed form solutions. Through synthetic experiments, we evaluate the closeness of the recovered models to the ground truth. We also test the generalization performance of our method in a wide range of complex real-world datasets and demonstrate that it captures useful structures such as the rotation and shrinking of a beating heart, motion correlations between body parts during walking and functional interactions of brain regions. Our method outperforms the state-of-the-art structure learning techniques for Gaussian graphical models both for small and large datasets. 1
[1] D. Crandall, P. Felzenszwalb, and D. Huttenlocher. Spatial priors for part-based recognition using statistical models. IEEE Conf. Computer Vision and Pattern Recognition, 2005.
[2] P. Felzenszwalb and D. Huttenlocher. Pictorial structures for object recognition. International Journal of Computer Vision, 2005.
[3] L. Gu, E. Xing, and T. Kanade. Learning GMRF structures for spatial priors. IEEE Conf. Computer Vision and Pattern Recognition, 2007.
[4] N. Meinshausen and P. B¨ hlmann. High dimensional graphs and variable selection with the lasso. The u Annals of Statistics, 2006.
[5] O. Banerjee, L. El Ghaoui, A. d’Aspremont, and G. Natsoulis. Convex optimization techniques for fitting sparse Gaussian graphical models. International Conference on Machine Learning, 2006.
[6] J. Friedman, T. Hastie, and R. Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 2007.
[7] M. Yuan and Y. Lin. Model selection and estimation in the Gaussian graphical model. Biometrika, 2007.
[8] E. Levina, A. Rothman, and J. Zhu. Sparse estimation of large covariance matrices via a nested lasso penalty. The Annals of Applied Statistics, 2008.
[9] J. Duchi, S. Gould, and D. Koller. Projected subgradient methods for learning sparse Gaussians. Uncertainty in Artificial Intelligence, 2008.
[10] V. Mansinghka, C. Kemp, J. Tenenbaum, and T. Griffiths. Structured priors for structure learning. Uncertainty in Artificial Intelligence, 2006.
[11] S. Lauritzen. Graphical Models. Oxford Press, 1996.
[12] A. Dempster. Covariance selection. Biometrics, 1972.
[13] R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society, 1996.
[14] O. Banerjee, L. El Ghaoui, and A. d’Aspremont. Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data. Journal of Machine Learning Research, 2008.
[15] S. Lee, V. Ganapathi, and D. Koller. Efficient structure learning of Markov networks using regularization. Advances in Neural Information Processing Systems, 2006. 1-
[16] M. Schmidt, A. Niculescu-Mizil, and K. Murphy. Learning graphical model structure using regularization paths. AAAI Conf. Artificial Intelligence, 2007. 1-
[17] M. Schmidt, K. Murphy, G. Fung, and R. Rosales. Structure learning in random fields for heart motion abnormality detection. IEEE Conf. Computer Vision and Pattern Recognition, 2008.
[18] M. Wainwright, P. Ravikumar, and J. Lafferty. High dimensional graphical model selection using regularized logistic regression. Advances in Neural Information Processing Systems, 2006. 1-
[19] R. Tibshirani, M. Saunders, S. Rosset, J. Zhu, and K. Knight. Sparsity and smoothness via the fused lasso. Journal of the Royal Statistical Society, 2005.
[20] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2006.
[21] J. Friedman, T. Hastie, H. H¨ fling, and R. Tibshirani. Pathwise coordinate optimization. The Annals of o Applied Statistics, 2007.
[22] J. Deux, A. Rahmouni, and J. Garot. Cardiac magnetic resonance and 64-slice cardiac CT of lipomatous metaplasia of chronic myocardial infarction. European Heart Journal, 2008.
[23] R. Goldstein, D. Tomasi, N. Alia-Klein, L. Zhang, F. Telang, and N. Volkow. The effect of practice on a sustained attention task in cocaine abusers. NeuroImage, 2007.
[24] P. Domingos and M. Pazzani. On the optimality of the simple Bayesian classifier under zero-one loss. Machine Learning, 1997.
[25] N. Friedman, D. Geiger, and M. Goldszmidt. Bayesian network classifiers. Machine Learning, 1997. 9