# Bayesian change point detection

Really naive question. I have a time series. I know how to perform segmentation (like binary segmentation algorithm). The goal is to find intervals generated from different probabilistic models.

But I have all information about possible models (distribution shape, variance, mean). So for each time point I have likelihood of each model and its prior. => I can calculate posterior for each time point, any model and any interval.

Problem: if I just segment the time series using maximum posterior probability, I will have too many change points. HMM can be a solution, but it also takes only one point into account and does not "look" at the whole interval. Also it is difficult to apply HMM for non-normal data.

It can be solved with sliding window, but it is not clear how to choose size of sliding window.

Is there an algorithm for this type of Bayesian change point detection (when you know possible models)? Like HMM, but takes the interval into account and can work with any parametric distribution? Heuristic algorithm is good too.

How can I apply maximum likelihood clustering for this problem?

UPD: Simulation of the problem:

variances <- runif(1000,0.01,0.5)

coverages <- c()

for (i in seq(1:100)) {
coverages <- c(coverages, rnorm(1, mean=0, sd=variances[i]))
}

for (i in seq(101:200)) {
coverages <- c(coverages, rnorm(1, mean=-log(2), sd=variances[i] / 0.75))
}

for (i in seq(201:300)) {
coverages <- c(coverages, rnorm(1, mean=log(3/2), sd=variances[i] * 0.75))
}

for (i in seq(301:1000)) {
coverages <- c(coverages, rnorm(1, mean=0, sd=variances[i]))
}

plot(coverages)


In real life, I know possible variances and means for each time point. I need to infer prevalence of one of the models inside the segment.

The two good papers on this subject are below:

These do not apply a clustering algorithm but take the interval (since the last change point) into account as you have asked for. And they work with parametric distributions. The paper by Adams and Mackay (the first one) also has the algorithm implemented in MatLab and Python.

• Thank you very much! It seems exactly like what I wanted. They look really nice! I will read them carefully, probably, my search is finished =) – German Demidov Feb 23 '16 at 13:56
• =( unfortunately, the thing that I did not notice in the first paper: We further assume that for each partition ρ, the data within it are i.i.d. from some probability distribution. For my situation I know distribution parameters, so I can answer the question: "what are parameters for time point $t$ and model $H_i$", but the data within is not i.i.d. so distributions for time points $t$ and $t+1$ can be different even for the same model $H_i$. – German Demidov Feb 23 '16 at 16:18

This is more of a comment than an answer but it's too long to be a comment:

The "bible" for sequential analysis is probably 2014's book Sequential Analysis: Hypothesis Testing and Changepoint Detection by Alexander Tartakovsky. It is seemingly exhaustive in its coverage of the topic.

http://www.amazon.com/Sequential-Analysis-Hypothesis-Changepoint-Probability-ebook/dp/B00MMOIWTS/ref=sr_1_1?ie=UTF8&qid=1445511005&sr=8-1&keywords=sequential+analysis+tartakovsky

That said, in June 2014 Columbia sponsored The Fifth International Workshop in Sequential Methodologies which brought together the latest and greatest practitioners in the field. Tartakovsky was on the organizing committee.