Hao Chen, Stanford

Starts:
4:00 pm on Thursday, February 7, 2013
Ends:
5:00 pm on Thursday, February 7, 2013
Location:
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 di ers 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.