Hao Chen, Stanford

4:00 pm on Thursday, February 7, 2013
5:00 pm on Thursday, February 7, 2013
MCS 148
Title: Graph-Based Change-Point Detection. Abstract: After observing snapshots of a network, can we tell if there has been a change in dynamics? After reading chapters of a historical text, can we tell if there has been a change in authorship? Given a sequence of independent observa- tions, we are concerned with testing the null hypothesis of homogeneity versus change-point alternatives, where a segment of the sequence diers in distribution from the rest. This problem has been well studied for observations in low dimension. Currently, many problems can be formulated in the change-point framework but with observations that are high-dimensional or non-Euclidean, where existing methods are limited. We develop a general nonparametric framework for change-point detection that relies on a distance metric on the sample space of observations. This new approach, which relies on graph-based tests, can be applied to high dimensional data, as well as data from non-Euclidean sample spaces. An analytic approximation for the false positive error probability is derived and shown to be reasonably accurate by simulation. We illustrate the method through the analysis of a phone-call network from the MIT Reality Mining project and of the authorship debate of a classic western novel.