Question regarding which search method is used for a kernelcpd example

[YanniPapandreou]

Hi,

I had another quick question regarding which search method is used for an example of the following form (this is similar to the example used in the music segmentation example in the docs:

import ruptures as rpt
gap = 90
algo = rpt.KernelCPD(kernel="rbf",min_size=gap).fit(signal_returns)

# choose the number of changes
n_bkps_max = 50 # K_max

# Start by computing the segmentation with most changes.
# After start, all segmentations with 1, 2,..., K_max-1 changes are also available
_ = algo.predict(n_bkps_max)

From the docs it seems like dynamic programming is used when you pass in the max number of changes. I was wondering which algorithm from the associated paper "Selective review of offline change point detection methods" this corresponds to? Sorry if this question is trivial, but I couldn't seem to find this info in the docs or source code.

Thanks,
Yanni

[deepcharles]

If you use rpt.KernelCPD(kernel="rbf"), then the algorithm behind it is from the following article:

Celisse, A., Marot, G., Pierre-Jean, M., & Rigaill, G. (2018). New efficient algorithms for multiple change-point detection with reproducing kernels. Computational Statistics and Data Analysis, 128, 200–220.

If you use rpt.Dynp(model="rbf"), then the algorithm behind it is Algorithm 1 (Opt) from "Selective review of offline change point detection methods".

Both have a time complexity of the order of T^2 (where T is the length of the signal). However, the first one has a memory complexity of the order of T and T^2 for the second.

[YanniPapandreou]

Thanks for getting back to me so quickly! I will take a look at the paper you mentioned, thanks :)

[YanniPapandreou]

Hi @deepcharles,

Sorry to bother but I had another quick question. In the advanced example about music segmentation you use an elbow plot to figure out the number of changepoints. From what I understood the y-axis in this plot indicates the sum of costs without the penalty term. However, in the paper:

Celisse, A., Marot, G., Pierre-Jean, M., & Rigaill, G. (2018). New efficient algorithms for multiple change-point detection with reproducing kernels. Computational Statistics and Data Analysis, 128, 200–220.

the problem which is being solved would have taken those sum of costs, added the corresponding penalty and then minimised that.

Is there any reason why you use an elbow plot instead, or is the y-axis actually the penalised cost?

Thanks,
Yanni

[deepcharles]

Hello,

Sorry for the late reply.

In the article you mention, they use a penalized approach so the correct number of changes is computed automatically. However, they need to find the correct amount of penalization. In the music segmentation example, the elbow plot is an heuristics to find the correct number of changes. In both cases, there is a parameter to tune (the penalty or the number of changes).
The choice between the two methods really depends on your use-case.