Imperial College London > Talks@ee.imperial > COMMSP Seminar > Non-parametric change-point detection using string matching algorithms

Non-parametric change-point detection using string matching algorithms

Add to your list(s) Download to your calendar using vCal

  • UserDino Sejdinovic, University of Bristol
  • ClockThursday 14 July 2011, 14:00-15:00
  • HouseRoom 503.

If you have a question about this talk, please contact Lauren E Noto.

The problem of detecting change-points is an important and well-studied one, with applications in a range of fields, including bioinformatics, finance and sensor networks. Given the output of a data source taking values in a finite alphabet, we wish to detect change-points, i.e., times when the statistical properties of the source change. While many approaches to the change-point detection exist within a parametric framework, postulating a variety of statistical models with unknown parameters between the change-points, the non-parametric methods, required when the laws of underlying processes are not available, are less widely studied. Motivated by ideas of match lengths in information theory, we pursue a fully non-parametric approach, describe a directed graph associated to the data stream, and introduce an estimator which we call CRECHE (CRossings Enumeration CHange Estimator) which estimates the change-point from quantities related to conductance on this directed graph. We present simulation evidence that this estimator performs well, both for synthetic i.i.d. and Markovian sources, as well as for text and audio files. Further, we establish consistency of the CRECHE estimator for directed graphs generated by a related toy model, by establishing a fluid limit and using martingale arguments. The talk is based on joint work with O. Johnson, A. Ganesh (School of Mathematics, University of Bristol), R. Piechocki (Centre for Communications Research, University of Bristol) and J. Cruise (Department of Actuarial Mathematics and Statistics, Heriot-Watt University).

Bio: Dino Sejdinovic received a Dipl.Math.-Inf. degree in mathematics and theoretical computer science from the University of Sarajevo, Bosnia-Herzegovina, in 2006, and a Ph.D. degree in electrical and electronic engineering from the Centre for Communications Research, University of Bristol, in 2009. Since 2009, he has been with the Statistics group, University of Bristol, as a Brunel Postdoctoral Fellow. His research interests lie at the interface between statistical methodology and coding and information theory, with emphasis on approximate inference in graphical models and sparse estimaton.

This talk is part of the COMMSP Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


Changes to Talks@imperial | Privacy and Publicity