nips nips2010 nips2010-108 nips2010-108-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Han Liu, Xi Chen, Larry Wasserman, John D. Lafferty
Abstract: Undirected graphical models encode in a graph G the dependency structure of a random vector Y . In many applications, it is of interest to model Y given another random vector X as input. We refer to the problem of estimating the graph G(x) of Y conditioned on X = x as “graph-valued regression”. In this paper, we propose a semiparametric method for estimating G(x) that builds a tree on the X space just as in CART (classification and regression trees), but at each leaf of the tree estimates a graph. We call the method “Graph-optimized CART”, or GoCART. We study the theoretical properties of Go-CART using dyadic partitioning trees, establishing oracle inequalities on risk minimization and tree partition consistency. We also demonstrate the application of Go-CART to a meteorological dataset, showing how graph-valued regression can provide a useful tool for analyzing complex data. 1
[1] O. Banerjee, L. E. Ghaoui, and A. d’Aspremont. Model selection through sparse maximum likelihood estimation. Journal of Machine Learning Research, 9:485–516, March 2008.
[2] G. Blanchard, C. Sch¨ fer, Y. Rozenholc, and K.-R. M¨ ller. Optimal dyadic decision trees. a u Mach. Learn., 66(2-3):209–241, 2007.
[3] L. Breiman, J. Friedman, C. J. Stone, and R. Olshen. Classification and regression trees. Wadsworth Publishing Co Inc, 1984.
[4] D. Edwards. Introduction to graphical modelling. Springer-Verlag Inc, 1995.
[5] J. H. Friedman, T. Hastie, and R. Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 9(3):432–441, 2007.
[6] IPCC. Climate Change 2007–The Physical Science Basis IPCC Fourth Assessment Report.
[7] S. L. Lauritzen. Graphical Models. Oxford University Press, 1996.
[8] A. C. Lozano, H. Li, A. Niculescu-Mizil, Y. Liu, C. Perlich, J. Hosking, and N. Abe. Spatialtemporal causal modeling for climate change attribution. In ACM SIGKDD, 2009.
[9] P. Ravikumar, M. Wainwright, G. Raskutti, and B. Yu. Model selection in Gaussian graphical models: High-dimensional consistency of 1 -regularized MLE. In Advances in Neural Information Processing Systems 22, Cambridge, MA, 2009. MIT Press.
[10] A. J. Rothman, P. J. Bickel, E. Levina, and J. Zhu. Sparse permutation invariant covariance estimation. Electronic Journal of Statistics, 2:494–515, 2008.
[11] C. Scott and R. Nowak. Minimax-optimal classification with dyadic decision trees. Information Theory, IEEE Transactions on, 52(4):1335–1353, 2006.
[12] J. Whittaker. Graphical Models in Applied Multivariate Statistics. Wiley, 1990.
[13] M. Yuan and Y. Lin. Model selection and estimation in the Gaussian graphical model. Biometrika, 94(1):19–35, 2007.
[14] S. Zhou, J. Lafferty, and L. Wasserman. Time varying undirected graphs. Machine Learning, 78(4), 2010. 9