01/11/2013 - 17:26
Short Title: 
Statistics Seminar: Hao Chen (Stanford U)
Short Desc: 
Graph-based change-point detection


Monday January 14th, 2013 at 1:30pm, MSB 1147 (Colloquium Room)

Speaker: Hao Chen, Stanford University

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 observations, 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.

Keywords: change-point model, graph-based test, high dimensional data, non-parametric testing