Alain Celisse - Using kernels to detect abrupt changes in time series
Channel: Institut des Hautes Études Scientifiques (IHÉS)
Date: 2016-03-26

In this talk we discuss the change-point detection problem when dealing with complex data. Our  goal  is  to  present  a  new  procedure  involving  positive  semidefinite  kernels  and  allowing 
to  detect  abrupt  changes arising  in  the  full  distribution  of  the  observations    along  the  time (and  not  only  in  their  means).    This  two-stage  procedure  is  based  first  on  dynamic programming,  and  second  on  a  new  $l_0$-type  penalty  derived  from  a  non-asympsotic model  selection  result  applying  to  vectors  in  a  reproducing  kernel  Hilbert  space.  Since  our procedure relies on the dynamic programming algorithm, which induces a high computational complexity at the first step, we will also discuss an improved version of this first step allowing to achieve a complexity of $O(n^2)$ in time and $O(n)$ in space.  Finally, we will illustrate the  behavior  of  our  kernel  change-point  procedure  on  a  wide  range  of  simulated  data.  In particular  we  empirically  validate  our  penalty  since  the  resulting  penalized  criterion  recovers the true (number of) change-points with high probability. We also infer the influence of the kernel on the final results in practice.