Change Point Detection Algorithms

Key Takeaways

[Music] this is data skeptic time series the podcast about how to predict the future based on historical sequential data episode number a time series is intended to be a sequence of data of observations or measurements or events that you've measured from one source for example i have a digital thermometer on our property it measures the outside temperature every i think 15 minutes and i'm essentially measuring the same thing all the time the ambient temperature at that point in space now the weather here in southern california is pretty consistent but elsewhere in the world or if you imagine i move that sensor suddenly indoors the underlying data has changed there's likely to be a particular change point in the data set and finding those change points saying exactly where something went from an old regime to a new one that's an interesting problem and the topic of today's show i speak with garrett vandenberg about change point detection in general what algorithms are out there how they intuitively work and then interestingly how they benchmark against one another [Music] my name is garrett i am a machine learning scientist and i'm based in london at the moment and i recently finished a postdoc at the alan turing institute here in london so in my postdoc i focus on a couple different topics the main one was automating data science so what we were looking at was trying to automate the boring parts of data science so data cleaning and dealing with messy data but i also worked on time series analysis and recently i looked and looked into memorization in deep generative models well the paper i invited you on today to discuss is titled an evaluation of change point detection algorithms maybe to kick things off for a listener who's not familiar what are change point detection algorithms in time series what can happen is that the data generating process changes so essentially the behavior of the time series changes and that can happen very abruptly and when it happens abruptly that's when we talk about a change point so in change point detection we're trying to either identify these points in a time series or we're trying to train an algorithm that is robust against these kind of changes well i think that's a really good and precise definition and an intuitively appealing one until i put on my math hat and i ask the question what is the definition of abrupt so that's a very good question so if we want to be mathematical about it we would say we have a set of observations a sequence of the time series that form one behavior and then from one point to the next a new behavior starts so we could say from a to b it's one behavior and from b to c it's another behavior but in practice it can be a couple time steps that you have that change and then it becomes a little bit of a definition question if i synthesize some data i can inject my own change points so i know the value i'm looking for if i just want to play around with an algorithm and see its behavior but if i get my hands on some real world data sets that's where it gets interesting i want to apply these change point detection algorithms to my real world data but what's my notion of ground truth in that situation that's a great question and that's typically quite difficult if we're simulating the data then of course it's easy we can just say we generate 100 observations from a normal distribution with this mean and variance and then we generate another 100 from a different mean and variance and then we know where that change point happens and what the behavior is in these different segments but in practice that's much harder when i'm thinking of some simulated data i might create you know maybe i have some sine wave with some gaussian noise and then i have a plateau a change point in the data and i know there's a plateau and the magnitude of it because i put it there it's you know sort of abrupt and i'm sure that does happen in the real world but i'm also thinking of just the messier noisier data on most real world data sets do you find that in general when you go looking for change points the data you're checking against is admitting them you know is the real world so revealing in its change points or is it a bit noisier and harder to detect so they're not always that revealing but sometimes they can be so i'll give you two examples that we use in the paper one is on the introduction of seat belts so that's a fairly well-known data set where we can see when seat belts were introduced in the uk that the number of road accidents decreases from one date to the other essentially accidents or injuries it's the number of drivers killed or seriously injured in the uk around the period of introduction of seat belts when the seat belts were compulsory in new cars and when they were made mandatory for everyone those were two different times and those clearly show up in the data and then we can say we have two change points because we have behavior before there were any laws we have behavior when it only held for new cars and then we have the behavior after it's been introduced for everyone i think change point detection is a sort of intuitive problem is there one master method or are there a variety of algorithms and approaches there is a vast literature of algorithms going back to the 50s where people were looking in to change points there's an enormous amount of different algorithms and different problems that fall into this category yeah we investigated a selection of these when you think about all the methods you surveyed are there any clusters or groups where you can organize them in your mind so there are two mainstreams of algorithms one of them is an algorithm that's essentially based on partitioning so you construct a cost function and you are trying to minimize a cost function given a particular number of change points or you're also trying to figure out how many change points fit well to the data that's one stream and there are a couple of variations of algorithms within that idea and then the other is the bayesian approach where we try to learn a probability distribution over the locations of change points if i collect a bunch of historical data i can kind of look back in time and try and assess are there change points in my data set are there also ways i can do this in a more real-time fashion oh certainly yes so that's a great question so if you have a time series and you have collected say a thousand data points and you then want to find out were there any change points in this time series that's when we're talking about offline change point detection if you have an application where the data points keep on coming in then you have an online setting and then you want to online change point detection and there are different algorithms for these different settings if i was planning to roll out some change point detection process into a production system i personally would like to have something like a lever or a knob i can pull you know what sort of parameters are available and a lot of these typical algorithms that a user can optimize towards so it's about hyper parameters right so we can usually vary some cost if we have an algorithm that tries to identify change points we can say introducing a change point will cost you x amount we are that's sort of a regularization on the number of change points and we can then vary that cost so if we have a low cost algorithm would find maybe multiple change points whereas if we set a very high it might only find one or even zero so those are the kind of things you can vary it seems to me we're never going to get one true change point detection algorithm to rule them all maybe it's the same thing as the no free lunch theorem so if there are a variety of techniques i'd really like to be able to compare and contrast them on the data set i want to apply them to and see which works best in my case the paper proposes a framework for doing this can you describe what that is so it's not that easy to figure out which algorithm is the best of course you're going to find that in some application areas some algorithms are going to be better than others we got a data set that we wanted to analyze using change point detection and we found it very hard to figure out okay what is the state of the art in the literature and and how do we determine what is the best algorithm and of course in machine learning this is a very well established framework of how we're going to figure this out because there's benchmark data sets all over the place in machine learning for for image detection and image recognition language etc but we found that for change point detection this was not really the case there were a number of data sets that were frequently used a number of time series i should say and there were a couple of data sets for different domains such as in genetics but for general time series there weren't that many well-established time series that people were evaluating on so that's what we set out to create can you talk a little bit about the variety and contents we set out to construct a data set of time series for change point detection that came from different domains essentially we have different kinds of data set i'll give you a few examples so we have data sets such as gdp of different countries we have data sets of macroeconomic phenomenon such as population sizes investment in business things like that but then we also have financial ones from stock market i could go on there are a couple different areas as well one of the ones i mentioned before was seat belts and then there's one where a person is running or walking so that's also a switch between different states so there's a various domains of time series that we include in our data set when i think of that example with the human activity i feel confident you can get some notion of ground truth even if you have to ask the person to use a clicker or something but when i think about a maybe more chaotic time series and one that doesn't necessarily have a ground truth let's say the google stock price you know if there's some big announcement that goes well or goes poorly we could expect a change point maybe in their stock price but really that price is a composite of so many dynamic factors it's it's maybe we wouldn't find a change point is it effective to apply some of these techniques to these more complex noisy data sources it's very hard to assign ground truth to the locations of change points in different time series and so what we did is that we invited data scientists who had experience with time series or change point detections itself to annotate where they believed that the change points in the time series were and for every time series in our data set we had five people annotate where they believed the locations of the change points were or they could say there are no change points in this data set in this time series then what we did was evaluate the algorithms against these multiple ground truths provided by the human annotators i think i could have been one of the people who helped you rate these if you needed extra hands it seems like not that i have any special experience but when i look at certain time series is i feel i have an intuitive understanding of where there are some change points but those also might be my bias in some weird way were you able to measure anything about the you know inter raider operator reliability how consistent were people's responses so that's a good question so we investigate that in our paper so one way we look at this is for by looking at the metrics that we establish and then we apply these metrics one annotator against the others and if they agree you would expect that on average they get a high score against their colleagues so to say and we do indeed find that there is quite a lot of interoperator agreement for one of the metrics that we use which is the f1 score with some adjustments we allow sort of a tolerance so we say you can be within five observations of where the change point is marked and then we'll consider that a correct assignment and that also allows algorithms and humans to be a bit more flexible in the exact location do you find anything insightful in the cases where the annotators didn't agree i'm thinking of something like the mnist data set the handwritten digit recognition and a lot of times when you take a look at the actual digits that are misclassified it's sort of like sloppy handwriting where all that seven kind of is almost a one and you sympathize with the mistake yeah the same goes so we have a couple of data sets most of the data sets i have to say most of the time series the people agree but there are a couple where some annotators find there are a lot of change points and some find only a few those who mark only a few change points typically do agree with the ones that mark many change points but the ones that mark many change points just had additional ones what we attribute that to is that essentially there is a bit of debate maybe about what exactly is a change point but that would be difficult for a human and for an algorithm the metrics that we apply in our paper they look at these multiple ground troops so they they look at these different annotators and try to find essentially a bit of a middle ground maybe [Music] these days small business owners are busier than ever yeah i totally agree and spending time searching for the right candidates can feel like you're just taking time away from growing your business that's why linkedin jobs made it easier to find the people you want to talk to faster and for free i can attest to this first hand i've made direct hires a data skeptic from linkedin jobs and when i want to see new candidates i go directly to the source where i know everyone's already at you can create a free job post in minutes on linkedin jobs to reach your network and beyond to the world's largest professional network of 770 million people they'll help you focus on candidates with just the right skills and experience and they give you the option of screening questions to help you get your role in front of only the most qualified candidates their solution helps you filter and prioritize who you want to interview and find your best hire it's why small businesses rate linkedin jobs number one in delivering quality hires versus the leading competitors linkedin jobs helps you find the candidates you want to talk to faster did you know every week nearly 40 million job seekers visit linkedin post your job for free at linkedin.com slash data skeptic that's linkedin.com slash data skeptic to post your job for free terms and conditions apply [Music] the following message comes from data iku the platform for everyday ai let's face it the potential for positive change with ai is huge but seeing that value is hard ai driven growth is about organizational transformation not just technology and today's businesses struggle with the complexities of bringing ai innovation to fruition that is where data iq comes in infusing a culture of working with data and ai every day and at every level of the company whether solving for the mundane like automating forecasting or what is the optimal number of widgets to buy or understanding moonshots that push the limits of today's technology to grow your organization and innovate that's everyday ai join more than 45 000 people worldwide across banking insurance pharmaceuticals manufacturing retail and more who are driving results with data iq visit dataiku.com to learn more that's d-a-t-a-i-k-u.com [Music] well we've talked about the steps to assemble this diverse expert annotated data set can you go into some details about the algorithms you want to unleash on this data i guess put these algorithms head to head yeah sure so we look at a number of different algorithms some are very well established some are from the 70s such as binary segmentation which essentially just hierarchically splits up a time series until it's done and then a number of of the methods are bayesian so we included those because as i mentioned before it's a bit of a different stream and then there are different kinds of methods so most of them are fairly recent because we wanted to look at what are people actually using nowadays those are the algorithms we include and then for sort of a baseline we also include a method that always says there are no change points and that allows us to also investigate like things like false positives uh yeah good point nice baseline to have seems like a good collection of approaches let's talk about the results how do the algorithms stand up so maybe it's good to to describe first the kind of experiment we do so we essentially look at two different studies so we look at what we call the default experiment where we take the method as it has been implemented using default hyper parameter settings the other experiment that we look at is what we call the best or oracle experiment where we vary the hyper parameters and take the best performing setting for that algorithm and that data set and then we look at the averages of these scores the reason we do that is because in practice you wouldn't necessarily know how to vary your hyper parameters so if i give you a time series i tell you find the change points and you have an algorithm where you can tune this hyperparameter how are you going to know which one is correct because you're trying to find these change points we are very interested in the default experiment and then we do the oracle experiment also sort of a as a test but i think the default experiment is sort of my favorite it's the one that i'm really interested in what do you learn in the default experiment in the default experiment we find that binary segmentation does quite well and that's followed quite closely by a number of methods such as the one that at most finds one change point and then there is one that's called pelt and the bayesian method in our work we find that kind of an old method binary segmentation from the 70s does quite well just straight out of the box well it seems almost surprising that in a few decades the tried and true methods haven't really been dethroned per se if you do vary the hyperparameters then you can get higher scores but of course these are averages as i mentioned before on different kind of domains you might find that the particular algorithm does very well so i would definitely recommend in practice that you try a number of algorithms but maybe i think the simplicity of this algorithm might be its advantage maybe that's why it's doing so well so this is something that of course like we're going to continue doing research on change point detection as scientific community and one of the things that i would be curious to figure out is why does this work so well well in order for me to be confident that the findings you have and have highlighted about these algorithms and how they stack up it really kind of depends on the robustness of the training data sets you know if these were just a few cherry picked examples maybe it's not representative of all the data sets people might encounter can you speak a little bit to the diversity of what was included in the training yeah of course so so like i mentioned before we have a variety of different domains from which we get these time series so some are financial some are macroeconomic others are kind of tourism numbers and i think that speaks to the strength of this data set it's that it's diverse it allows you to explore domains that maybe are more similar to what you're working on so if you're working on a financial time series of stock market data you might be more interested in the methods that do well on those time series in our data set given that do you have any advice you would give out about which methods are more or less appropriate in certain industries i don't want to say in this domain do that method right because i would say explore a number of different methods and try different parameters but maybe one of the things that you can try is if you have say a number of time series from a particular domain make a training set and a test set right try first on a number of them a number of algorithms on these time series see what works and then apply it to the rest be scientific about applying these methods well the code's up on github so if i were someone with my own change point detection technique i guess i could clone your repo integrate my method into your framework and then see how it stacks up could you speak a little bit to what the technical challenges might be in setting something like that up sure yeah we've we've tried to make it easy so all the code as you mentioned is online so we have the code online that we use for the experiments we have the code online that we used to have people annotate the time series so if you have a setting where you actually want some of your colleagues or some of your users to annotate time series for you you can use that as well and then we have to set up the code of the experiments we've tried to set it up such that it's easy to use it on your own data sets or your own methods so there's a single api for how these methods are applied so how it's supposed to return a result from a change point detection algorithm and then the data sets come in a particular format as well and there's a schema even so it should be hopefully easy to use for different methods and different data sets but if you have a problem of course you can raise an issue on github and i'm happy to take a look are there any ceilings limits or bottlenecks people might encounter as they try and push more data through so that depends more on the individual algorithms most of these are fairly fast like it wasn't actually an issue to run these experiments other than that we were trying in a large number of hyper parameters i would say probably focus on the simpler algorithms because they're likely going to be faster we mentioned binary segmentation comes out pretty well in our study so that could be a good place to start because it's also very fast and then a number of these methods explicitly have been focused on being either linear or almost linear in runtime so that could be something to look into then as well and then maybe compare them to how well they do in our study i could see adding more data sets or adding more algorithms maybe both as future steps where do you envision the project going one of the reasons why we did this was that we wanted to find out like which are the best performing algorithms out there it was also in a way from noticing that people were often experimenting on simulated data or a handful of real-world data sets so we hope that with this data set people can evaluate their algorithms on multiple real-world data sets use the annotations that we have created to evaluate them and then develop new algorithms like this is supposed to be a proving ground for future algorithms what we've seen so this paper has been cited a couple of times already and what we see is that people actually use say a handful of time series from our data set to evaluate their algorithms and that's great that's that's sort of what we wanted it's because they're working on a particular application or they just want to look at some of these time series yeah hopefully it'll push the science forward right that's the goal ultimately absolutely well for analysis purposes it's great to run these sorts of techniques offline do you know of anyone deploying these in actual industrial settings where they're monitoring for change points and taking some action so i bet they are out there so online change point detection would be great to use if you're monitoring some sort of system maybe customer numbers come in you want to know when they change abruptly or in some maybe even a security setting i don't know it's also a bit related to what's called data drift or concept drift where the data distribution changes a bit more slowly in real world settings well if a listener wanted to get their hands dirty writing some code not necessarily implementing these methods but leveraging them do you have any package recommendations that'll help so i know at the alan turing institute where this work was done they have developed a package for time series analysis that's called sk time so psychic time it's based on the scikit-learn philosophy so there could be an interest to implement change point detection methods and i know there is another one i think it's called ruptures which also does change point detection but they i believe focus on offline change point detection but yeah if you're in the market for a package for change point detection but definitely check those packages out yeah good advice naturally you have support for univariate time series what about multivariate yeah this is a good point so in practice of course we can have multivariate time series what we see in the literature is that a number of these methods have been designed with univariate so one dimensional time series in mind for some of these methods there's not necessarily a technical reason that they can't be applied to multivariate time series so you could for instance extend a loss function to be multi-dimensional but the support in software is not always there so in our experiments we separated out between univariate and multivariate time series so we have a number of multivariate time series in the data set and then we only look at the methods that work on those but that's a small subset of both the time series and the methods so if you'll imagine with me someone in an industry position they've been asked to do some change point detection on their company's data i see two paths they could take here one is they could read the literature get very familiar with these different algorithms and contemplate how the techniques and nuances of those methods would apply or not apply maybe in their individual use case and then perhaps at the other extreme there's someone who could forego all that learning just grab one of those packages or your library shove their data into it and just see what they get out do you have any thoughts on those two approaches so my first thought is define what would be success right how are you going to measure that you've done a good job at change mode detection that could mean you record data for a week or so and you first run your algorithms on only that week before you apply it to something else and you annotate the change points that you believe are there by hand and then you just see do the algorithms find these and tune your parameters and your algorithms based on where you believe these change points are and then hopefully in the future it will find similar change points right if you've tuned the algorithms and parameters for those settings that would be my first thought like okay this is in a way change point detection is unsupervised learning so you have to define your own metric of how you're going to be satisfied with your solution would you encourage people to do some sort of smoke testing you know if i'm the manager and i've tasked the team to implement some sort of change point detection i could put in the extra effort and find a way to inject a change point just to test the methods is it worth doing definitely definitely in favor of that it would allow you to test your systems right and in fact one of the things that we did in this paper is that we had what we called quality control time series that we inserted in between the real-time series and had data scientists that helped us annotate they annotated these quality control time series as well and that allowed us to investigate whether they were accurate or how accurate they were and what kind of time series they found difficult so this is definitely an approach that i would recommend in practice to test your setup yeah well i already asked you about how your raiders compared against each other in terms of their agreement but i know you were also able to analyze them in terms of their overall accuracy how did the raiders perform so we had five different time series that we inserted in there that were simulated time series so we knew where the change points were and then we looked at can the annotators find these simulated change points most of the times they were correct the one that they found difficult was one with periodicity so if you have periodic time features in your time series that turned out to be a bit difficult to annotate and the reason for that is because in this particular time series it was very hard to identify that there were indeed change points so some of the annotators got them correctly but not all of them so yeah this is maybe something to be aware of that their seasonality can be a bit more tricky to identify the change points from time to time so i get the impression from the paper binary segmentation is a good option i ought to consider should i take that now as a golden rule or what's the interpretation to have here it's sort of how strong are these results so how much do we have to rely on the best method being the best method going forward and on that point i would like to say you know we don't show that binary segmentation is the best method in terms of statistical significance right there are a couple of methods that do about as well so definitely try those out as well and that's just something we do find statistical significant differences between methods and for that i would definitely check the paper if that's something you're interested in but don't just blindly assume that whatever number one we found has to be the best going forward like there's always nuance in science and for that i definitely recommend checking out the paper as well and are you still working on this or have you moved on to other things so i have moved on to some other things this is still something that i'm very interested in change point detection so i do see myself working on this again in the future but my recent work has been more into deep learning so i looked at deep generative models in particular probabilistic degenerative models and to what extent they memorize their training data so that's if that's something that's interested to your listeners they can check out the latest paper it's on my website and on archive and all the usual places i'm going to check that out myself maybe we can get back together in the future and discuss scans together that'd be cool yeah well garrett thank you so much for coming on data skeptic happy too thanks for the invite yeah that's fun that concludes another installment of data skeptic time series our guest today was garrett vandenberg thanks to our sponsors linkedin and data aiku myself claudia armbruster as associate producer vanessa bly guest coordinator and our host kyle pulich [Music]