Everything you need to know about change-point detection

Speaker 1 [00:05]

All right, thank you, Zoran, for the introduction. So I'm Charles, very glad to be here today to speak in front of such a large crowd. So yeah, today we'll be talking about change point detection. But first, a few words about myself. So I'm a researcher in academia. I work in Paris, so ENS Paris-Aclay. So I think maybe this presentation will be a bit different from what I've seen until now. So, I hope it will still be interesting. So, first of all, what are we studying? So, we are studying time series. So, I can give you a very broad definition. It's just an ordered sequence of observation, usually vectors okay it encompasses a lot of different data type and use cases so the most notorious one will be sound and video but it can be any data that you collect from sensors while you are monitoring something or someone and so why do I start with this a bit trivial definition is because I want to stress that here we are dealing with data where time is important. I mean, the order in which you observe the data is very important and something that you need to encode in whatever you do after. You can imagine that if you shuffle randomly all the frames of a video, well, it will not be exactly the same video in the end so there is information in time and that's something that we will try to keep whenever we want to deal with time series there are many things we can do with time series i've listed a very short possible task even detection classification feature extraction etc etc and today we'll be speaking about one particular task which is change point detection okay so change point detection it's a very very common step when you when you are dealing with very long time series which can change over time. It's part of usually part of a larger processing pipeline and informally it consists in finding when the generative model of a time series changes abruptly. So basically it's a function, it's an algorithm that takes as input a time series of multivariate vectors and outputs a list of instance indexes which corresponds to instance where the time series changes. So it's not clear what I mean by changes. and something that the user must input to design a change point detection algorithm. Yes, so I will give a few motivating examples. So those are examples that I've been working on myself, and then I will list very quickly several others. First is human activity recognition. So it's not generally formulated as a change point detection task. I mean, it can, but I haven't found that to be the case. But in nature, this is a change point detection task. So imagine that you are collecting data from a smartphone or a smartwatch, like the acceleration, and you want to detect when the user changes activities. And by activity, I mean from walking to climbing stairs or just standing in a room like here today. And if you have those instance, and also if you can classify each segment to the proper category of activity, you can design indexes of activity. You can have a very high-level view of what a person is doing during a day. And create activity indexes, let's say. So finding those instances amounts to do change point detection. And we'll come back on this example later. Second example that I wanted to talk about is data coming from motion capture sensors. So imagine that you have several sensors on your body. So let's use this. so those are sensors so this is the head both arms and I think it's on the back and the hips and they record their position in space so X, Y, Z and the patient that we monitor the medical doctor that we collaborate with they monitor the several patients some are healthy some have shoulder injury they want to understand if there is a difference in the certain movements when they raise their arms and stuff like that so they ask to do a certain protocol and then they recover time series like this okay so there are 34, I think. Yes, 34 markers. So in the end, it's a 102-dimensional time series. So as you can see, this time series is not very intuitive. It's not easy to understand at first sight. I mean, this is the same here for the 3D acceleration. It's really difficult to understand what is happening. I mean, you can guess that here the subject is not moving, but here it's not clear what this person is doing. So what I want to stress here is that usually time series, except if you are doing video or sound, they are not really intuitive. This is not something that you can look at and understand everything. So, change point detection is one way to compress, to represent in a better way your data so that it's more interpretable. And at the end of the presentation, we will see how we can do that. Okay, I have some other applications. So, this one on the left, I also work on this one. And those are applications that I just found on the internet that were using the package rupture. So, you see that it can be in a very different context. So, just to show you that this is a very broad subject that has many applications when it's used as part of a larger pipeline. so yeah after those uh motivating example i can go into further detail into what is a changepoint detection algorithm okay uh from just a historical note uh the first article on this subject is from the 1930s so it was an article about monitoring the the quality of a manufacturing process so it's almost a century of research on that subject it has there were a lot of different developments in different communities so that's a bit of a pain to gather everything and put it under the same umbrella into the same framework so I will describe the framework maybe some A few methods don't fit into the framework, but there are not much, I think. There are not many. So basically, what is the high-level view of a change protection algorithm is you want to choose between several segmentation, several ways to split your signal, and you will choose the one that minimizes a certain criterion, which I call V V of calligraphic T which is T calligraphic T will always denote a set of indexes and this criterion is usually a sum of segment costs so to be clearer imagine that you observe the blue signal and you want to test this specific segmentation with three change points so that's four segments Well, you compute the cost on each segment, so the cost will be like a measure of homogeneity. It will be low if the segment is homogeneous. That means that it's almost constant. And then you sum the cost of each segment, and that gives you your total criterion to discriminate between segmentation. And what I want to highlight is that most of the algorithms from the literature, they can be cast as this kind of optimization problem, like minimize this criterion. With one KVAT, that's usually to avoid trivial results, like when you have as many segments data points, you have to add some kind of what we call a penalization on the complexity. So, in the end, usually you minimize the data fidelity term, so this criterion, plus complexity penalization. But let's not go too much into details, but remember that we have to minimize that. And that defines change point detection algorithm. And what in the end, once we have said just what I said, we can see that there are only three things that we can change that we have to calibrate to have a detection algorithm. So, the first thing is what we call the cost function here. So, this homogeneity index. The second thing will be how to minimize, how to do the minimization. And this is what I will call the search method. And the last one is the constraints. So here it will be a penalization on the complexity. So I will go quickly into those three elements to explain what can be done, to give you just a sense of how you can choose each element. And then we'll do a bit of application and maybe a bit of not code, but I will show you code at least. Okay, so first element, the cost function. The cost function defines what you want to detect as a change. So it's certainly maybe the first thing you want to calibrate. it's where you put what you know about your data. If I know that my data is actually piecewise constant, so let's observe the orange signal but I know that the generative model is piecewise constant plus Gaussian noise then I can set my cost function to be just this that is on one segment I compute the average so the average is here and I add all the residuals like when I approximate my signal by this average so if I do, if I just define this cost function I will be able to detect when there is a change in in the mean, in the level of my signal this extends to multi-dimension, you can add some prior also on the if you want I won't speak much about it but it works, it can be extended in several directions, this is the most common change point detection method and actually it was the first that was introduced historically another one that you can think of and those are certainly the two most well known this is the change in scale so let's say you observe your signal and it changes abruptly of scale over the over the time series and if you just set your cost function to be this so it's whatever the formula it's not really important, it's just the log of the variance of the standard deviation, then you can detect easily that there is a change of scale at each moment of the signal. So just know that there are many, many different cost functions possible. A lot are already implemented, so it's a matter of choosing the one that is of interest to you or creating one that works for you. So this first part so defining this cost function is not an easy task usually you need to translate your knowledge about your data your expertise into mathematical terms and well that's not usually very very easy okay so that will be the first element the second element is the search method So, if you remember, this is the method that allows you to compute the, to find the actual segmentation that minimizes your criterion. So, as you can see here, it's a discrete optimization problem. Because you have to find, you have to check, you minimize over the number of changes, their position, which are indexes so it's a discrete optimization and maybe if you're not familiar with it it's a bit difficult to to do you cannot do just a gradient descent or something like this like in deep learning it's it won't work here you can say that there are only a finite number of ways to split your signal so you can just enumerate them and find the minimum but that won't work if you have even if you have very low very small signals because there are two to the power n minus one possible segmentation so you have to be a bit smart about it usually the exact way to solve it is through dynamic programming it's a well known recursive optimization algorithm and here usually if you don't have much programming resources, you can approximate the solution and it gives you a faster algorithm. So basically, this is quite easy to choose. If you have all the time in the world and all the memory in the world, you can tackle this exactly. And if you don't, then you choose the closest approximation that won't lose that much precision. So this element actually is quite easy to calibrate, contrary to the first one. And maybe the last one, I will be very brief because it's certainly the hardest, is trying to control the sensibility threshold. So you can think of it as filtering true changes from noise. so you have to estimate some kind of noise level and usually you don't observe it so it's very difficult and especially if you don't know the number of changes in your signal there is a lot of work on that part so if you ever do some checkpoint detection reserve some time for choosing that ok ok so what I've presented here is a broad overview so I didn't give much detail, but it's a broad overview of the literature. That means that if you choose a certain combination of cost function, search method, and constraints on the segmentation, it will define a proper change point detection algorithm. Certainly, it will correspond to one or two articles in the literature. So, we coded a library to do exactly that, so that But it follows exactly this framework. And when you choose, so it's a modular architecture. So you have to choose three parameters, three elements, let's say. And then you are good to go. You have an algorithm that works on some data. Maybe not your data, but on some data it will work. So the library is called ruptures. There's a link to the documentation. We try to code as, I mean, we are not professional developers at my lab, so we do our best, but feel free to give us tips. And if you want to, so there are some examples in the, like narrative examples in the documentation, but if you want also, I tried to do, well, on Google Scholar, it's quite easy to see who cited this library. So you can check if there is an article that corresponds to your use case. Maybe that can give you an idea on how to use ruptures. Okay. A few lines of code to show you how well we try to fit this framework that I just described to you. So imagine that you have a signal. Okay, import it. You define the cost. so there are several costs that are available here is the cost that can detect change in means you choose a search method, here is binary segmentation or whatever with some parameters you pass the cost you fit actually it's unsupervised no computation happens here but you can predict by choosing certain constraints so it can be the number of changes if you know it a priori or some other penalty function some other parameter so you can have a prediction the breakpoints and you can measure the actual distance there are several metrics from your prediction to the true change points so that can help you to do some cross-validation or any other things of that nature So, basically, everything in a rupture will look a bit like this, and then these few lines of code, you can have a working algorithm. Okay, coming back to the two examples that I've shown at the beginning, so this is the activity segmentation problem. We observe 3D acceleration from a smartphone, I think, and we want to detect when there is an activity change. So I've shown you how all this code is enough to do the segmentation that is shown here. So the prediction is the dashed vertical lines, and the true ones are the solid black lines. So you can see that we are very close to the ground truth. And basically, all pipeline will look like this. You have a preprocessing step. So here, we use the time frequency representation, plus some Gaussian mixture, but whatever. It's not really important. And then we define our cost function. Here we use some code from the, it's well explained in the library, but we use a base cost class. And then we only need to define, so here nothing happens really, we only need, those two lines are just the only lines important. So between the segment start and end, we select our segments and we compute here the entropy of the average segment. That would be our cost. And if I plug this cost into an algorithm with a proper penalty, so I choose it carefully, by hand I mean, so that it outputs the correct number. But if everything is correct, is well calibrated, you have directly a change point detection algorithm for this kind of signals. So it's pretty low tech, I would say, a few lines of code, it's not supervised, and it gives quite good results very quickly. So I found it quite nice. And maybe last example that I wanted to show you. So it's a more complex pipeline, like change protection is only the first step. So if you remember, maybe I will do this. It's bad practice to go back, but I will do it anyway. If you remember this signal, so this is the signal of a person doing a movement with motion capture data. And what we do with this pipeline is to do change point detection, so finding the start and end of each movement. And then we classified each segment and assigned a symbol to it. So segments that look alike, they will have the same symbol, okay? So basically the signal that I've shown you can be summarized easily like this. And so it's part of the yellow symbol, then green, then yellow, then green, et cetera. And if we look at the average position during the yellow observation, So it's here. So I only plotted three sensors. So it's both hands and the head, I think. So if you look at the yellow, this is a front view, so 3D view, front view, like this, and top view from above. And then you see that the yellow corresponds to someone who is sitting with both hands down. and the green one corresponds to the person who is sitting, so the head here, and both ends up like this. So you can understand easily what this person did during this trial. It's like staying seated and then raising their arms. And you can do it for several other signals, and those correspond to different movements, and you can check what each symbol represents. You have an online demo doing exactly that here and you can put your own data if you want to try it. Okay, so maybe to conclude, for us the future work of this library will be about adding more and more calibration schemes because that is what is most asked by users. And so, yeah, maybe the first, this point is maybe the most important. So I will stop here and thank you for your attention.

Speaker 2 [26:02]

Thank you, Charles, for this very inspiring, interesting talk. So we have some slide of questions. How could this be adapted to online, real-time change point detection?

Speaker 1 [26:14]

Okay. So, nice question indeed. I've talked about what we call offline. That is you observe the old signal and you output the correct change points. Well, here you have to change the argument. So, the search method. And if you that's where you put your online constraints. And you just, so it will be an approximation of this real, the best change points, but it will be online so it can be adapted to other settings. But yeah, it's the search method that you want to change.

Speaker 2 [26:57]

Okay, thanks. How do you see MLP deep learning approaches instead of manual math formula crafting? And have you used approaches with Fourier transformation?

Speaker 1 [27:12]

So yeah, this is exactly something that we try to do. So NLP maybe not, I will just speak about deep learning approaches. So there are two approaches, either you have some labels. So if you have some labels, you can try to, so everything happens in the cost function. So if you can parameterize your cost function by a very large vector, so let's say you have a neural network, the weights are your parameters, and you try to find the parameters of your cost function that can imitate what you saw in the labels. So you need to define a loss, so classification loss won't work here. You have to define a specific loss, and that's what we did recently, so it can be adapted. You just need to take care of the discrete nature of the optimization, which is a bit of a pain with deep learning methods.

Speaker 2 [28:13]

Okay, and last question from Slido. How can the penalty be defined to constrain the complexity? Can you give example for simple implementations?

Speaker 1 [28:23]

Yeah, so, again, if you have labels, you can parametrize it, just like the cost function, and learn it with labels. If it's unsupervised, usually people learn something like this, which is just a parameter times the number of changes, and it's constrained to just learning one parameter, and then either you have a good idea of what you want to find, and you can do some cross-validation. Otherwise, you try one, then 10, then 100.

Speaker 2 [28:59]

Always right trial and error. Yeah Okay, let's thank Charles once again and you can catch him for for the remain or