nips nips2009 nips2009-225 nips2009-225-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Mladen Kolar, Le Song, Eric P. Xing
Abstract: To estimate the changing structure of a varying-coefficient varying-structure (VCVS) model remains an important and open problem in dynamic system modelling, which includes learning trajectories of stock prices, or uncovering the topology of an evolving gene network. In this paper, we investigate sparsistent learning of a sub-family of this model — piecewise constant VCVS models. We analyze two main issues in this problem: inferring time points where structural changes occur and estimating model structure (i.e., model selection) on each of the constant segments. We propose a two-stage adaptive procedure, which first identifies jump points of structural changes and then identifies relevant covariates to a response on each of the segments. We provide an asymptotic analysis of the procedure, showing that with the increasing sample size, number of structural changes, and number of variables, the true model can be consistently selected. We demonstrate the performance of the method on synthetic data and apply it to the brain computer interface dataset. We also consider how this applies to structure estimation of time-varying probabilistic graphical models. 1
[1] Amr Ahmed and Eric P. Xing. Tesla: Recovering time-varying networks of dependencies in social and biological studies. Proceeding of the National Academy of Science, 2009.
[2] Francis R. Bach. Bolasso: model consistent lasso estimation through the bootstrap. In William W. Cohen, Andrew McCallum, and Sam T. Roweis, editors, ICML, volume 307 of ACM International Conference Proceeding Series, pages 33–40. ACM, 2008.
[3] J Bai and P Perron. Computation and analysis of multiple structural change models. Journal of Applied Econometrics, (18):1–22, 2003.
[4] Jushan Bai and Pierre Perron. Estimating and testing linear models with multiple structural changes. Econometrica, 66(1):47–78, January 1998.
[5] O. Banerjee, L. El Ghaoui, and A. d’Aspremont. Model selection through sparse maximum likelihood estimation. J. Mach. Learn. Res., 9:485–516, 2008.
[6] P. Bickel, Y. Ritov, and A. Tsybakov. Simultaneous analysis of lasso and dantzig selector. Ann. of Stat.
[7] Florentina Bunea. Honest variable selection in linear and logistic regression models via ℓ1 and ℓ1 + ℓ2 penalization. Electronic Journal of Statistics, 2:1153, 2008.
[8] Scott S. Chen, David L. Donoho, and Michael A. Saunders. Atomic decomposition by basis pursuit. SIAM Journal on Scientific Computing, 20(1):33–61, 1999.
[9] William S. Cleveland, Eric Grosse, and William M. Shyu. Local regression models. In John M. Chambers and Trevor J. Hastie, editors, Statistical Models in S, pages 309–376, 1991.
[10] David L. Donoho, Michael Elad, and Vladimir N. Temlyakov. Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Trans. Inform. Theory, 52:6–18, 2006.
[11] G. Dornhege, B. Blankertz, G. Curio, and K. M¨ ller. Boosting bit rates in non-invasive EEG single-trial u classifications by feature combination and multi-class paradigms. IEEE Trans. Biomed. Eng., 51:993– 1002, 2004.
[12] Jianqing Fan and Qiwei Yao. Nonlinear Time Series: Nonparametric and Parametric Methods. (Springer Series in Statistics). Springer, August 2005.
[13] Jianqing Fan and Wenyang Zhang. Statistical estimation in varying-coefficient models. The Annals of Statistics, 27:1491–1518, 2000. ´
[14] Za¨d Harchaoui, Francis Bach, and Eric Moulines. Kernel change-point analysis. In D. Koller, D. Schuı urmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems 21. 2009.
[15] Za¨d Harchaoui and C´ line Levy-Leduc. Catching change-points with lasso. In J.C. Platt, D. Koller, ı e Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems 20, pages 617– 624. MIT Press, Cambridge, MA, 2008.
[16] Trevor Hastie and Robert Tibshirani. Varying-coefficient models. Journal of the Royal Statistical Society. Series B (Methodological), 55(4):757–796, 1993.
[17] Mladen Kolar, Le Song, and Eric Xing. Estimating time-varying networks. In arXiv:0812.5087, 2008.
[18] Marc Lavielle and Eric Moulines. Least-squares estimation of an unknown number of shifts in a time series. Journal of Time Series Analysis, 21(1):33–59, 2000.
[19] E. Lebarbier. Detecting multiple change-points in the mean of gaussian process by model selection. Signal Process., 85(4):717–736, 2005.
[20] E. Mammen and S. van de Geer. Locally adaptive regression splines. Ann. of Stat., 25(1):387–413, 1997.
[21] N. Meinshausen and P. B¨ hlmann. High-dimensional graphs and variable selection with the lasso. Annals u of Statistics, 34:1436, 2006.
[22] Nicolai Meinshausen and Peter B¨ hlmann. Stability selection. Preprint, 2008. u
[23] Alessandro Rinaldo. Properties and refinements of the fused lasso. Preprint, 2008.
[24] Le Song, Mladen Kolar, and Eric P. Xing. Keller: Estimating time-evolving interactions between genes. In Proceedings of the 16th International Conference on Intelligent Systems for Molecular Biology, 2009.
[25] Robert Tibshirani, Michael Saunders, Saharon Rosset, Ji Zhu, and Keith Knight. Sparsity and smoothness via the fused lasso. Journal Of The Royal Statistical Society Series B, 67(1):91–108, 2005.
[26] S. A. van de Geer and P. Buhlmann. On the conditions used to prove oracle results for the lasso, 2009.
[27] M. J. Wainwright. Sharp thresholds for high-dimensional and noisy recovery of sparsity. Preprint, 2006.
[28] H. Wang and Y. Xia. Shrinkage estimation of the varying coefficient model. Manuscript, 2008.
[29] H Zha, C Ding, M Gu, X He, and H Simon. Spectral relaxation for k-means clustering. pages 1057–1064. MIT Press, 2001.
[30] P. Zhao and B. Yu. On model selection consistency of lasso. J. Mach. Learn. Res., 7:2541–2563, 2006. 9