Imperial College London > Talks@ee.imperial > COMMSP Seminar > Non-parametric change-point detection using string matching algorithms
Log inImperial users Other users No account?Information onFinding a talk Adding a talk Syndicating talks Who we are Everything else |
Non-parametric change-point detection using string matching algorithmsAdd to your list(s) Download to your calendar using vCal
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. This talk is included in these lists:Note that ex-directory lists are not shown. |
Other listsCAS Talks Type the title of a new list here Featured listsOther talksControlled quantum dynamics The Effects of Network Structure on the Stability of Genetic Control: From Models to Data Docitive Networks Semi- and non-invasive brain-machine interfaces in humans - Part 1 |