MiniRocket

Key Takeaways

[Music] this is data skeptic time series the podcast about how to predict the future based on historical sequential data episode number i say table you think chair i say time series problem you think forecasting but there's also the problem of time series classification in which the task is to apply labels to the time series this is often done in a streaming setting in which you need computationally efficient techniques something expensive is difficult or infeasible to use in your production system today on the show i speak with angus dempster about the algorithm mini rocket mini rocket is something like a 75x improvement over rocket it uses convolutional neural networks to transform the data such that linear classifiers can be used to make the actual labeling task we do a high level dissection of mini rocket and discuss some of the empirical results of this algorithm and practice [Music] my name is angus and i'm a phd student at monash university in australia working on scalable methods for time series classification well let's dive right in tell me a little bit more about the scalability aspect what's unscalable about some of the more popular or maybe well-known procedures for doing time series there are many methods which exist to do time series classification but one of the sort of issues that has existed in the field for quite a while is this issue of scalability in particular many of the most accurate methods for time series classification have been burdened by high computational complexity and a lack of scalability i know a lot of people have broad interest in looking at mini univariate time series so scalability can be challenging in two ways maybe i have thousands of signals i want to look at and so there's although i guess they could run in parallel there's still a scalability issue and then there's the individual time series where maybe it's you know of only i don't know a thousand points sounds pretty small in the big data world but just as you were mentioning the computational cost to it can be difficult what are the real frontiers where are you pushing on scalability the most it's both so we're looking at scalability in terms of the the number of examples that you're trying to process and also in terms of the length of the time series you might have exactly how you deal with this issue depends a little bit on context so you'll see maybe the domain where you have the sort of the longest time series or typically is in audio classification which is kind of a specialized subset of time series classification and audio you know has a very high sampling frequency so i think often in audio for example you have sort of specialized techniques which you use to deal with that for example often in audio a typical thing that you do is to do a kind of pre-processing where you might turn your audio signal into a spectrogram and pass that to a some kind of classification model and that's sort of doing a kind of implicit down sampling of the input to deal with that and what is the nature of the expense why are some of these expensive where are you spending the time generally speaking it really depends very much on the method so there's quite a variety of methods which are at the forefront of time series classification and yeah it really depends on the particular method and where that time is spent i guess our focus has been trying to mainly deal with it on the training side and so then yeah different methods they may be spending a lot of time trying to tune hyper parameters or there may be something kind of inherent in the method which has a high computational complexity and then the sort of single most accurate method is an ensemble of other models and of course that sort of brings in the the complexities of all its constituent models so that's another reason why there's high complexity in some cases well prior to the publishing of mini rocket what can you tell me about the state of the art in time series approaches what were some of the main contenders a person might think to use when going at a big problem there's been a little bit of movement in the field i'd say over the last year or so in around 2017 there was a big review paper that went through for intensive purposes all of the methods which existed up to that point and it identified a number of models which really stood out so one we would call it a dictionary method or a bag of words method which is based on looking at the frequency of discriminative patterns in time series another one is called a shapelet method or the shapelet transform where you're looking for kind of discriminative sub series in time series and another was a large ensemble method which incorporated both the dictionary method the shape method and a number of other methods since then there has been quite a bit of progress there are methods which are based on distance measures so that's where you perform classification by measuring the distance between time series with various distance measures and those methods been pushed quite a long way there are also a recent method what you would call an interval based method so that is where you're looking at sort of sub-regions of time series and extracting features from those sub-regions well can we focus on rockets since that's sort of pivotal to the contribution in this paper what is rocket right so rocket is a method where we try to take a slightly bit of a different approach and what we do is we take our input time series and transform them using a large number of random convolutional kernels and then use the transformed features to train a simple linear classifier so that's kind of the crux of rocket and how it works it turns out that this process although it seems very simple produces high classification accuracy and is quite fast and scalable yeah the appeal to me of that design is okay maybe i spend a lot of time training that convolutional neural network but once i've got it i've got it and it's probably as big as i let it be right and once the i have a linear feature that's as efficient as you can get in your production system so there's some obvious advantages for someone who wants to put rocket in production is there a price for that efficiency and that good implementation do i lose accuracy or something like that the method has i'd say reasonably high accuracy compared to other state-of-the-art methods i don't think you lose out on accuracy per se i guess there's two points to make the first is that no model is going to be you know the be all and end-all so you know non-model is going to be the most accurate on on every data set and the second thing is as it is a method which incorporates a lot of stochasticity it is going to have some variability in the accuracy so on each run it's going to give a slightly different result so i think that's probably the main thing to bear in mind from that point of view can you contrast then uh what is mini rocket in comparison to rocket with mini rocker what we're really trying to explore is i guess two things firstly what is really the importance of this randomness this stochasticity in rocket to what extent can we take that away so it's the first thing and then secondly how can we build on that in order to really i guess fulfill the promise of rocket in terms of scalability how fast can we make it so with mini rocket we're going from a random to a largely non-random method and ultimately we're going to end up with a much much faster method for time series classification that's interesting because broadly speaking and maybe this is a weird bias i bring to the table but i feel like in a lot of computer science work injecting randomness has these advantages you know it comes up in like probabilistically checkable proofs and stuff like that de-randomizing doesn't always seem to have the same benefits what's the key insight here where that gives you an advantage the takeaway in one sense with mini rocket is that the randomness that we have in the rocket method while it is highly effective is not strictly necessary but the other sort of bigger picture takeaway is that or this method in the way it works so the randomness with rocket is really all in the kernels basically every aspect of the kernel is random and with mini rocket that's not the case but i think the the bigger picture item here is that the set of kernels that you use for a method like this is you know the question of the set of kernels that you use is something of a red herring and in fact there's a lot of flexibility there so you can use random kernels you can use this small fixed set of kernels that we have in mini rocket and in fact there's a number of different sets of kernels which work similarly and similarly well so i think that's kind of the bigger picture takeaway that a particular set of kernels are using is not really of primary importance there's lots of different sets of kernels which are going to perform similarly well and of those then selected for mini rocket how are those constrained what are the kernels you're using it there so we use a small fixed set of kernels and we can see from experimentation that actually a number of sort of different sets of kernels are going to perform the job well are going to produce high accuracy so what we ended up choosing was just a relatively small set of kernels they've all got length of nines they have nine weights and they're restricted to having two different values of the weights but they're not binary in the sense of having the values zero one or negative one and positive one in fact our kernels are constrained to having the values negative one and two but actually in fact the particular values the magnitude of the weights in this model doesn't really matter subject to a couple of constraints but yeah that's the kernels we're using makes sense you'd mention arriving at those in part through experimentation what were the underlying data sets you experimented on the field of time series classification is really been built on work to produce a big repository of data sets that everybody can use to you know develop their methods and ultimately to do benchmarking and demonstrate the efficacy of their methods that's work that has come out of mainly two groups so that's work by professor eamon keo at the university of california riverside and also work by professor tony bagnol and his group at the university of east anglia so they've built up this archive called commonly known as the ucr archive which is kind of the benchmark collection of data sets for time series classification and it contains a whole mixture of different types of time series data sets so you have data sets which are sort of motion sensor data sets to do with activity recognition you have data sets which are sort of spectra you have data sets which to do with sort of medical data a big variety of data sets and this sort of comes to a sort of interesting observation you take a step back and sort of look at this field in in context so i think an interesting observation here is that something like a field like image classification for whatever reason is typically benchmarked on a relatively small number of relatively large data sets whereas time series classification for a variety of reasons has really developed in a way that benchmarking tends to be done on a relatively large number of relatively small data sets that is changing uh slowly i think it's still good to have a mix of large and small data sets because it provides a kind of a different challenge but yeah historically this archive has contained a large number of relatively small data sets but now larger data sets are starting to be added to it [Music] thanks to this week's sponsor quantum metric to all the digital leaders out there how would it feel not only to know what your customer is experiencing but how many others are experiencing this too i think it's about time we put our customers at the center of our decisions and get ahead with real-time insights way before a code freeze it might be beach weather outside but for retailers the holiday season has already begun 2021 holiday e-commerce sales are expected to exceed 2020 benchmarks are you prepared to capture every customer revenue opportunity with quantum metric you can be their unique approach to the digital customer experience helps today's top retailers and e-commerce brands quickly identify and prioritize the big and small revenue opportunities that keep customers engaged in coming back stay off the naughty list this upcoming holiday season by reducing customer friction increasing conversions and personalizing the shopping experience want a sneak peek visit us at quantummetric.com pod offer and see if you qualify to receive the 12 days of insights offer using the code skeptic all caps this offer gives you 12-day access to their platform coupled with a bespoke insights report that will help you identify where customers are struggling or engaging in your digital product some restrictions apply if you're doing anything related to ecommerce you've gotta have a look at quantum metric and see if it suits your needs head over to quantummetric.com pod offer and while you're there use the code skeptic all caps [Music] thanks to this week's sponsor seamless ml are you a data scientist kegeler physicist mathematician who wants to be a data scientist or quantitative researcher seamless ml is looking for exceptional people to join their team the team is already stacked with one of the best poker players in europe one of the best cosmologists of his generation and a top 20 sudoku player in the world seamless ml is applying machine learning to do algorithmic trading that's a challenging but incredibly rewarding project if you're deeply committed to excellence in machine learning this team could be the place for you to leverage your training and take the next step in your career to learn more head over to seamlessml.com jobs that's seamless s-e-a-m l-d-s-s m-l dot com slash jobs [Music] when i'm looking at table one of the paper that compares rocket mini rocket and some of its features one thing i can say is pretty much every row rocket is in a more constrained position right you go from 20 000 features in rocket to only 10 000 in mini rocket and rocket has randomness where mini rocket must be fixed so everything is kind of constraining one might expect it's going to perform worse under all these constraints what are the actual results the results show that mini rocket more or less basically on par with rocket in terms of accuracy and in fact the results for each of the data sets it's quite similar so it's basically performing very similarly overall and i think what that shows is that it's really coming down to the sort of overall procedure and what is happening there so the fact that the results are similar show that you can sort of make these changes changes are made really with a focus on scalability but that in a sense the core of the sort of information that you're getting out of this transformers is very similar and so that you can still maintain this high accuracy and get very very similar results so if i have similar accuracy that's very appealing to me what do i gain in terms of improved training time so this is going to depend a little bit on you know how big your data set is in terms of how many time series you have and then the length of the time series so overall basically the larger the data set is the bigger the advantage that mini rocket is going to have essentially what mean rocket represents is a large constant factor reduction in training and inference time over rocket but that reduction is very large so it's approaching two orders of magnitude on larger data sets so i think or a very large data set sort of up to approximately 75 times faster than rocket well if i can train faster and i get more or less the same accuracy is it correct to call this a free lunch yeah possibly you're getting essentially the same results so i think it really makes sense to treat mini rocket as kind of the best version of rocket so i'd say what mini rocket in a sense really does is is to fulfill the promise of rocket in terms of beating scalability so doing the work with mini rocket we realize there are a number of ways which the procedure can be really aggressively optimized so yeah you're getting a massive benefit in terms of speed and getting in essentially the same results in terms of accuracy could we dig into some of those key insights where do the speed ups really come from the speed ups in terms of knee rocket over rocket are due to really four key optimizations so the first is not strictly speaking explicit optimization so much as a way of avoiding doing a whole lot of work in the first place so this comes down to and this is based on a property of the pooling mechanism we use and pulling mechanism produces what we call ppv features for proportion of positive values and this optimization is based on an observation that these features have a kind of symmetry in that if you know the proportion of positive values then that's one minus the proportion of negative values and what that means is that if you produce a ppv feature for some kernel what's called w then that's really closely equivalent to a feature that you would get if you were going to do the same thing but for the negative that kernel negative w what that means overall is that we can basically get away with using half the kernels that we would otherwise have to use because every time we produce a feature for one kernel w it's sort of equivalent to a feature that we get for the negative that kernel so we don't actually have to do the procedure for the negative kernel negative w so we're kind of using half the kernels overall that we'd otherwise have to use that's the first optimization the second optimization again comes back to how we're performing pooling so what happens in earlier method rocket and what is typical in convolutional neural networks is that you know you have some convolution outputs on feature map you perform pooling and then if that's a global pooling you get a single feature when we perform pooling we are reusing or recycling the convolution output multiple times so we get our convolution output and then we're going to use that to produce multiple features so we get multiple features for the cost of one convolution operation basically the third optimization is performing convolution by addition so this is a fairly standard kind of optimization you see in some binarized and quantized convolutional neural networks and basically the convolutional operation involves doing you can think of it as a sliding dot product in terms of time series between your kernel which is like a vector of values and your time series so if you imagine your kernel at any particular position on your time series it's doing a dot product and then you do that at each position in the time series but that involves repeated multiplication and addition however if your kernel is limited to a relatively small number of weights here we're limited to just having two different values for our weights but it doesn't have to be just two you can kind of factor out the multiplication aspect you can do all of your multiplications kind of up front and then when you want to perform convolution all you're left to do is addition and if you think about the convolution operation or doing a transform like this in terms of a kind of set of nested for loops what that basically does is it's taking the multiplication from one of the inner loops right to the kind of outer loop that's the third optimization and the fourth optimization is basically like a little trick it's building on this idea of convolution by addition so in our method we take our input time series and we convolve it with our small fixed set of kernels but each kernel is going to be applied with multiple different dilation values so what we do here is we treat dilation as the outer loop and what we do is we kind of pre-compute a convolution output where we pretend for a given dilation we pretend that all values in the kernel are negative one so that's one of our two different values for our weights negative one and two so we pretend all of the values in our kernel are negative one we pre-compute this for each dilation then when we go to compute the final convolution output for a given kernel all we have to now do is compute a little correction which is based on where the values of two are in our kernel we compute this kind of intermediate representation once for each dilation and then for each kernel we only have to compute this little correction and the key point here is that this correction that would otherwise be required to compute the convolution output for the full kernel so what that means overall in essence is that you're getting the convolution output for you know approximately two-thirds of your kernels essentially for free so there's sort of four key optimizations which mini rocket uses and they're really built on the simplicity of this small set of kernels and that's what really makes it so much faster than rocket yeah all four of those key optimizations seem in some sense generalized i don't think they're necessarily specialized to rocket we see convolutional neural networks showing up in other techniques and things like that do you imagine that some of these techniques will be lifted and applied under other methodologies as well well in some sense some of them at least are really just highly simplified forms of optimizations which are already used in some other methods so yeah i think there's definitely broad applicability but with mini rocket i guess the key thing is that they're really natural optimizations which are very easy to apply when you have this small very simplified set of kernels so i think things are going to get more complicated if you're trying to turn them into kind of more generalized optimizations what do you see as next steps will there be a mini rocket the 1.5 or is it all about applying it to different domains no i think we're definitely interested in taking the methods further exactly what that's going to look like i'm not sure i mean again one sort of overall point with methods like this is that nothing is going to be you know the best method for every possible data set so there's always kind of things that you can work on to expand the sort of applicability of these methods we have a number of things which you know we know that kind of shortcomings of the method in some sense there's a lot of room still to improve i think we'd like to take these methods further exactly what they're going to look like i'm not sure yet and then we're also interested in you know really exploring other methods as well to see you know what we can bring to the field well maybe to wrap up could you talk about the long-term goals like what do you see as the horizons or the real cutting edge in time series exploration one of the interesting things about time series and this is not an original observation to me by any means is that in an important sense time series classification is a task in some ways very similar to image classification albeit in sort of one less dimension and so the observation has been made that methods which work well for image classification you know we should have really quite a strong expectation that perhaps with some modification they should work also for time series classification and i think bearing that in mind i think perhaps what we might see i'm not sure you know exactly when but as some of these new cutting edge methods that are coming actually originally from sort of nlp then to image classification i think ultimately we're going to see that come into time series classification as well so what i have in mind here are you know transformer models mixer models things like that i think there's a lot of potential for that to be explored in the field of time series classification so my expectation is that's going to be one of the main changes that we see over the next few years there are some interesting challenges with that because as similar as they are there are some important differences between for example image classification and time series classification i think there's some really sort of key issues to try and crack to apply these methods that are coming from other fields into time series classification i think the two things in particular that i have in mind are really working out what is an appropriate kind of embedding for time series to be used with transformer-like models and secondly if we were to look at a model like the mlp mixer model or the similar models that have come out recently how you're going to deal with the information being mixed across the time dimension so when you apply like a mixer model or a transform model to images what's typically done is that the image is cut up into patches and i think that particular procedure is probably going to be a bit of a problem when you try to apply it to time series so i think there's big challenges there but i think you know that's my expectation of where maybe the field might go at least in one direction yeah some very exciting research paths there for sure well angus where can people follow you online the best place would be to go to our github repository for the mini rocket method and you can also contact me by email awesome and tell me a little bit about the implementation there what language and what's it take to get started mini rocket is coded in python what we do though is we apply just in time compilation so we're using the number library for that but in terms of sort of reading the implementation it's essentially pure python and numpy but i think if people want to get started in time series classification more generally i think i would suggest checking out a couple of the prominent libraries in the area so one is the sk time library that's an offshoot of the scikit-learn library and that it's got a lot of capability way beyond time series classification but there's a lot of the kind of core time series classification methods are implemented there it's also a very active library so it's a great place to start and i'd also suggest people check out the tsai library so that's like an unofficial time series library for fast.ai you can find them both on github i think yeah they're both excellent projects well good suggestions angus thank you so much for taking the time to come on the show and share your expertise oh my pleasure thanks for having me that concludes another installment of data skeptic time series thanks to our sponsors today quantum metric and seamless ml our guest today angus dempster myself claudia armbruster as associate producer vanessa bly guest coordinator and our host kyle police [Music] you