Aligning Time Series on Incomparable Spaces

Key Takeaways

[Music] this is data skeptic time series the podcast about how to predict the future based on historical sequential data episode number our series of episodes on time series have primarily covered univariate time series that is sequential data that is observed in a uni variant or a single variable value that's not entirely true we touched on some use cases for multivariate time series but when you need to move out into an actual application then you can often encounter real-world problems that weren't there in textbook data a good example of this is unaligned data in this episode i interview alex turenin one of the co-authors of the paper aligning time series on incomparable spaces we discuss their methods which are inspired by optimal transport for time series alignment [Music] my name is alex trenin i'm an incoming postdoctoral researcher at the university of cambridge well before we get into a discussion of the paper tell me a little bit about what you have planned for the postdoc mostly my plans actually are going to be to work on similar topics to what i've been doing in my thesis in my phd i've done quite a bit of work on decision making systems and gaussian process methods the paper that we're talking about actually is sort of like a side project at least from my point of view and so that work i've had a lot of success with it but it feels more at a halfway point rather than a completion point what i'm really planning to do is kind of develop a lot more of that and build on the ideas so i'm i'm really excited well i was supposed to start tomorrow but i think probably that's going to get postponed a little bit i'll probably start in about a week or so i'm very excited well the paper i invited you on to talk about is titled aligning time series on incomparable spaces you'd mention this as being a side project how did you connect with your co-authors the first author on the paper is sam cohen and he is a lab mate of mine we have different affiliations on the paper because my advisor who is mark dyson roth switched universities kind of midway through my phd sam is really interested in optimal transport and in particular in applications of ideas of optimal transport for tackling various problems and building tools for machine learning and so i got involved in the project because he had this idea for extending something called the grom of westerstein distance which maybe we'll get to in a bit to a time series setting and needed basically just uh somebody who had like a little bit more experience with the mathematics and the analysis as well as with the process of actually putting together a scientific paper because this was one of the first kind of works that he did during his phd when we got things to work we decided to write together i also want to credit the other authors on the paper this is a joint work with julia who's not in our lab but in kind of one of the labs sort of around hours at ucl as well as brandon who said facebook research he does a lot of work on how to differentiate through interesting things so that's kind of the team and how it got together for listeners not familiar with optimal transport can you give a high level overview so optimal transport is a very intuitive thing that ends up actually being mathematically very rich and you can build a lot of things out of imagine you have two piles of dirt with the same amount of dirt lying in each pile i'm talking about literally you have like a pile of sand that's sitting on like a bit of concrete or something like this and you've got two of these things and somebody just tells you that they have the same amount of sand in them so the question is how do you move the sand from one pile to make it like the other pile in a way that minimizes transportation cost and i've kind of stated it with sand lying on a thing of concrete because it's a very easy image to picture in your head but you can also think kind of a bit more abstractly where on one side you have like consumers and producers or you have a more like economics type sort of way of thinking about it so what optimal transport is is the study of this class of problems and how to formalize them mathematically and what kind of concepts you can actually build out of the formalism once you have it one of the key concepts that you can build using optimal transport is a notion of a distance so for example if you have two different piles of sand with two different shapes let's say one of them is sort of like a long and narrow shape and the other is more like just a big blob because the sand is arranged differently you could actually say how far away is one pile of sand from the other pile of sand and this is done very easily you just transport the sand from one pile to the other one in the optimal manner which minimizes the transportation cost and you ask what is the total cost that you pay by doing that and so it's really easy to draw it's very intuitive and that's the idea of optimal transport the thing i just mentioned to you is something called the wasserstein distance is sort of constructed in this way i like the sand analogy when i think of grains of sand i'm thinking of something fungible you know i'm not concerned with this grain versus that green and in that sense if i have two piles it seems like there's a operation here of how many grains of sand or the minimum number to take shape a and converted into shape b is that a fair stretch of the analogy yeah so basically the pile of sand you're right that the sand has kind of a discrete shape in it and you're also completely right that we don't distinguish between different individual particles in the sand it's not like we have a sand and different particles of sand have different colors and we want to do some kind of thing with the colors there's nothing like that all of the particles are identical in the example i've given you you can think of it as like a discrete number of particles but the abstract theory allows you to have essentially a continuum of particles and sort of the discrete nature that is important in the example actually doesn't really play much of a role in the abstract mathematical setup it's one of the things that makes it quite a powerful tool with something being generalizable in that way it obviously has a lot of mathematical applications i'm curious are you aware of any industrial or maybe econometric applications as well i want to say absolutely these ideas now i'm not an expert but i know that in operations research people will use this stuff and in like various flavors of economics how to like arrange stuff people would use these ideas but it also ends up in machine learning being like a really useful tool for just as like a technical tool for building components of generative models and so this is kind of almost straight to the examples that we have in the paper which is generative modeling as i mentioned optimal transport can be used to define notions of distance and those notions of distance in turn can be used for building losses so if you're training a model and you want to have an interesting kind of loss that's tailored to the domain and incorporates whatever some kind of structure from it for instance a geometric structure then optimal transport can actually be a tool for building such a loss but this is within machine learning i guess you're asking me more broadly but more broadly they are definitely used as well i like the application of machine learning if i'm going to train a model i need a loss function that's going to be efficient are there any computational considerations when adopting this approach yes sometimes and that's why we write papers about this subject in part because the optimal transport distances are kind of very rich sort of things so you need to generally there is an algorithm that is used to actually compute the distance typically there's many variations of this but the sort of magic two words to know about which is a synchorn algorithm which is sort of an idea for essentially giving an algorithm that is uh quite efficient for computing these things if you need to run an actual algorithm to compute your loss you might ask well how am i gonna what am i gonna do am i just gonna how do i differentiate through that for purposes of like training or minimization and that's actually something else that there's a whole like list of papers written about and it's closely related to for instance differentiating through convex optimization problems and so i just want to plug brandon amos has done a whole bunch of work as part of his thesis and other things exactly on this topic which is if you have some kind of optimization problem or some kind of algorithm that's used for computing a loss and you need to differentiate through that efficiently can you do better than just literally unrolling your computation and just backprop straight through the whole thing and oftentimes you can do a bit better than that and so this is kind of something that people study but i do want to mention that these things do end up oftentimes practical it takes some actual like effort to compute the loss i mean you don't just summon square stuff for instance the fact that you have to do more computation there doesn't really kill the ideas well there's another prerequisite we should probably go over before getting into the core contributions of the paper and that's dynamic time warping could you give another definition dynamic time warping works as follows we have two time series call them x and y the key thing here is that the time series are defined as a sequence of discrete points so we're not talking about an actual continuous curve the inputs going into this thing is a finite sequence of points potentially of different length so we might have one time series that is sort of sampled with like more points than the other time series we want to align these time series as much as possible with each other this is something that's actually very similar to the optimal transport problem because remember that in the optimal transport problem we have two piles of sand and we're essentially aligning different grains of sand with each other in the way that minimizes the cost dynamic time warping is something that's a lot like this except in the same in the case of the sand we sort of assume that there's no sort of structure with the individual grains of the sand there's no color as i mentioned i think earlier there's no ordering and here we're going to change the problem in order to actually have an ordering and we're going to enforce the ordering in the time series case there is an actual order to the points and so it's a very similar problem where we try to align the points to each other but we enforce the fact that the ordering of the points remains the same in both cases and so the first point in time series one has to be aligned to the first point in time series two and the last point in time series one also has to be aligned in time series two and so the question is how do we arrange this sort of middle points as accurately as we can because the problem is discrete you can represent each alignment as a matrix what you do is you build a matrix where the amount of rows is the amount of points in in the first time series and the amount of columns is the amount of points in the second time series and you just put a one if the two are aligned and you put a zero if they're not aligned and so you have a little diagonal of ones that starts from one quarter and gradually moves up to the other corner and we call something like that in alignment matrix and so for each alignment matrix there's a certain cost dynamic time warping you get a distance by basically picking the alignment matrix that minimizes that cost and then looking at the number that you get so that's dynamic time warping so quick follow-up just to make sure i understand i'm thinking of maybe two of those old-timey movie cameras that have the hand crank so of course there's a lot of variance in the rate at which observations are being taken and if maybe we have two of those cameras from different angles and also different rates lining that up is that something this technique can help us with what's the data is it the images in each camera yeah i guess it would really be the time series of the images taken yeah but i mean what's an individual point in this time series is it an image or is it some kind of number that represents where an object is like from the point of view of the camera so you've already ran some kind of other thing to get that like good point so yeah let's say it's the position of an object that you can see from both cameras so you're looking for an x y and a z so if you imagine you have two cameras that observe an object and there's some kind of method that sort of runs over the image and gives you back a position of the thing relative to the camera then in a sense the thing that we're trying to work with is exactly that you have two times series of an object moving but it's from different cameras and so the actual numbers representing the position are going to be different because the camera angles are different aligning those things with each other is exactly what like dtw and gram of dcw is trying to do with the extra point that it can also do that even if one of the cameras is recording faster than the other so let's say one records at 24 frames per second and the other one is like a fancy camera cords at 48 frames per second it could also align those for the same length of time [Music] the following message comes from data iq 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 dot com [Music] is a managed service provider and managed security provider with a 20-year history of industry-leading customer service vpls's network and security operations centers can be an additional resource for your it team or function as an outsourced it department they offer help desk managed security managed backup and other managed it services they handle the it needs of both large and growing companies and can help your team with it needs of all sizes they operate 24 7 365 who else does that maybe they're a good fit for after hours support for your team when it comes to things like cloud migration or backup and disaster recovery you're going to need outside expert help vpls is a great fit for companies with existing it staff and teams but may have some gaps in their i.t framework which could include cyber security network optimization and more they're great for companies without existing it support who are looking for experts to manage their entire it infrastructure and they're great for companies looking for it expertise for a specific project or issue visit vpls.com go it to see all their offers including a low monthly co-location rate for new customers that's vpls.com go it let's get into some of the core contributions of the paper perhaps starting with the distance function you proposing i mentioned how dynamic time working works earlier and so one of the key aspects about it mathematically is that it's defined as the minimization problem over a series of alignment matrices of a cost in optimal transport that's exactly the same only you minimize in the case of a discrete probability distribution so you're lining a pile of sand with sort of a finite set of let's say categories like let's say bins uh rather than with you know something sort of continuous and so there it's the same problem only instead of alignment matrices you work with coupling matrices and a coupling matrix is essentially exactly sort of the same thing as the alignment matrix only without the time ordering it's also something that's got entries between zero and one and rows correspond to one of the probability measures i'm using the word probability measure as a replacement for pile of sand and the columns is sort of the other probability measure one of the really cool things about the sort of optimal transport problem is that you can generalize it to other settings that are not quite the same as the classical setting and one of those is what's called the grom of wasserstein setting so grom of osterstein essentially generalizes the wasserstein which does not require the two probability measures to live on the same space so instead of having two piles of sand that both live on the same block of concrete you might have a pile of sand that lives on the concrete on one side and then you might have something else like an image you know taken by a camera on the other side or excuse me you're not going to have a single image you're going to have a big collection of images and so the question is how in the world are you going to try to compare two things like that they're sort of completely different that have nothing to do with one another and the answer is you don't compare the spaces you compare the relationships between the points inside the spaces so in the case of the pile of sand instead of thinking about all of the pieces of sand as having like just some location if i have a finite number of points i can build a matrix which looks at the distance between any two points in the pile of sand and i can just build a big matrix that tracks all of those distances similarly if i have like a collection of images that describes some kind of phenomena that i think is related to the sand and i have a collection of images then i can build a big distance matrix between those images just the same way that i build a distance matrix between the pieces of sand and so now i have two distance matrices and i can just ask how far away are they and the formalization of that idea is the gram of osterstein distance what it captures is essentially the kind of intra-relational geometries as we call them between the two sets of samples and the two spaces what is a gram of dynamic time warping it's exactly this idea but where we built the time structure in in the same way that we did it for alignment matrices so i can give an example straight from our paper figure 3 has something called the quick draw data set now the quick draw data set is you know somebody took their kids and they had them draw some sort of different shapes so they had somebody draw some shapes of hands somebody else draw some shapes of fishes i think clouds and blueberries are the other two categories different points in this data set have a different number of discrete observations because some of them they're drawn faster than in other ones and something you might be interested in doing with that data set is finding okay can i just pick one example that summarizes the data set can i find some kind of mean in this sort of crazy space of handwriting sequence time series and the answer is you can and so one of the things that methods like dynamic time warping and actually optimal transport methods also allow you to do is they allow you to have notions of berry centers now a berry center is like a mean but a mean is something that you have of real numbers whereas a very center can be something you can have of a something much more complex images being kind of another example although it actually images not being a good example because points on a sphere being like a much better example because if you just take a bunch of points on the sphere and you try to just take an average you're probably going to end up with a point that's not even on the sphere whereas if you take a berry center you will get a point that is on the sphere and you know is sort of a center of the points that you've chosen because optimal transport gives you ways of defining these notions our paper essentially gives you a way to extend those ideas to the time series setting and so if you look in figure 3 you can see with dtw you have basically an average shape of a hand or a fish and it actually doesn't look very good how come it doesn't look very good well it's because in the data set you also have symmetries some of the hands and some of the fishes they're going to be rotated compared to each other and translated and kind of moved around the space and so one of the things that gromo of dtw allows you to do is get a notion of an average for this data set that is based off of comparing the distance matrices that i described earlier for each observation and then you just pick the point that has sort of an average looking distance matrix and so if you want to then draw such a thing you sort of pick a point and then you draw the other ones to match that and so that's roughly how that works is picking that point trivial or are there some steps involved i believe we did in the paper was we draw the sequence by applying a multi-dimensional scaling algorithm specifically we use the one in scikit-learn on the distance matrix associated with the berry center and then display the result so i think the answer is in that example that we don't generate the time series we just pick the time series whose distance matrix is the closest to the one that's the very center i don't see anything else that's sensible that we could have done in that example at least one of the really cool things about having a notion like gdtw which again gives you a way to compare points in potentially different spaces by containing the time series in different spaces by comparing their interrelational geometries is that once you have such a notion and you know how to differentiate through it you can use it to build a generative model so in a wasserstein gan you have basically a loss that's used to train the generator and the discriminator that loss comes from an underlying notion of a distance that needs to be selected and so all we do is end up using gdtw as this notion of distance together with an entropy regularization term which is needed sort of for the method to work algorithmically it sort of just smooths everything out a little bit what you get ultimately is an objective that looks like the minimum so the minima with respect to the parameters of the neural networks of the expectation with respect to the generator of uh gdtw that is a loss that you can define and once the loss is defined as long as you have a way of computing it which we can do with a sort of synchorn type algorithm and you have a way of differentiating through it which we also do because the inner gdtw term we actually use the softened version that has good properties with respect to differentiation then that's something that's defined and so you can just try to solve that problem using your favorite optimization algorithm and you'll get a set of neural network weights and those weights in turn will generate time series so you get a generative model but a typical application area for methods like this is actually imitation learning so in imitation learning there is some kind of expert data that we have some kind of system and the goal of the system is to imitate the expert it's kind of a very intuitive name in the time series settings the expert might have like a trajectory of some kind of problem that you know you might otherwise be using reinforcement learning for we're not using reinforcement learning i'm just using that as a kind of word to be evocative of the sort of setting we're thinking about so actually an example of this is in figure 5 in our paper so in figure 5 there is a car that sort of drives in a spiral shape the expert is somebody with a video game controller probably who's driving that car and what we observe is actually the images that are in the top row so we observe an image of a car kind of driving around sort of in a spiral shape and the goal is to learn not in image space but in xy space a policy of an agent that generates the same trajectory and so we use gdtw to solve that problem now one of the really cool things about like that setup is that if we just give you the x y coordinates of the car then you can solve that problem by just dynamic time warping so you just find the policy that leads to trajectories that minimize dtw the really cool thing is that you can take this sort of procedure where you just take a policy with an agent you sort of run the policy and you try to minimize the dtw between the trajectory that the agent produces and just the example trajectory that you saw it's kind of a very basic imitation learning type setup you can more or less solve this problem with dtw but what dtw can't do is you have an an expert that gives you images and you have a policy that doesn't produce images it produces trajectories in r2 and so gdtw essentially gives you a way of doing that which is you take your agent you run the policy with the agent you get a set of numbers in r2 and from those numbers you build the distance matrix then you get a sequence of images which are just pixel data from that pixel data you build your distance matrices that's the expert's distance matrices and you just sort of minimize gdtw which is built out of those things and you get a policy for the agent and we actually didn't compare the method against any baseline because we were at the time of writing not aware of any baseline for actually doing this particular task where there's both kind of an imitation learning setup and a time series setup but it's also an area where optimal transport is often considered in sort of many variations do you have any thoughts on where this line of research should go next i know you may be off on other topics but i'm curious if you have a vision for what comes next so optimal transport for machine learning broadly is a very active area there's a lot of work being done on both exploring the different variations of the setup and one of the contributions we had was exploring what happens if you add a time series structure to kind of the setup but there's also a lot of work being done on kind of the algorithmic side as well as the application side i think people in the community are becoming aware of these tools largely through just sort of a lot of papers being written about them and can use them for various problems in areas like robotics i think there's a little bit of sort of image processing although nowadays image processing mostly done using other stuff really the goal of broadly the community is just development of these things as a toolbox that you can use for whatever your purpose is and the toolbox is in pretty good shape i mean it's certainly not an area that's finished there's still a lot more to do can you comment on how computationally demanding these approaches are so anytime you have a loss that is built by like some kind of algorithm you generally if you can compute the gradient of that loss without running a second algorithm that's useful because it means that all you need to do is just solve the original minimization you don't need to back propagate all the way through it and that sort of can save you compute time it can save you memory and it's cleaner so in tensorflow and frameworks like this there is a functionality for defining custom gradients that is exactly based for this where you know you can take a certain shortcut for computing the gradient then otherwise you'd have to like do some kind of massive computation so the advantage of this a really simple formula for the gradient of gdtw is that it saves you potentially your compute costs you know you just solve the minimization without any kind of back prop and then you take the solution you plug it in and so the rest of your you know back propagation for your neural network sort of whatever it is you're doing becomes isolated from the computation of the loss itself it's both cleaner and it's more efficient and in particular it saves you memory because if you have to store the intermediate result of like a thousand iterations of an algorithm in order to differentiate through it you might run out of memory doing that but a sort of shortcut formula like this prevents you from running out of memory because you never have to store all the intermediate steps to begin with you just need the final solution this is actually typical behavior not only in gttw but also in a whole host of other examples and so if you see papers about differentiable layers or differentiating through context optimization they're often studying this idea in sort of different settings than ours but it works in our setting as well and that's one of our results that's a good trick there's a number of innovations in the paper and i hope listeners will check it out and learn more about the work there alex before i let you go i'd love to switch gears for a second i know one of your primary areas of interest is gaussian process models what should listeners know about them so that's a very different topic than the one we were talking about and it's kind of the bulk of my work so i'm quite happy to plug it broadly the main thing i would say about gaussian processes is just for people to be aware of them gaussian processes are a way of handling uncertainty that is sort of very principled and works really well for both problems and spatial statistics and as well as decision making problems and settings like bayesian optimization where sort of principle handling of uncertainty is really important to balance explore exploit trade-offs and other things like this and so i don't have any kind of particular message about them other than it's a really cool set of techniques it's a lot of what i've been working on recently i'd love to talk to you more about them because it's a subject area sort of i've spent a lot of my time on and where can people follow you online at my website it's avt dot i am people can also follow me on twitter and by the way the website has blog posts for both this paper and others so if you want to read a kind of bite-sized description of what's going on in the paper and just see some you know pretty pictures then the website will have those it's also got a nice video of basically some of the alignments so you can see how the time series alignment under dtw and gdtw changes as you kind of move two sets of time series around in space and i'm also active on twitter so my twitter handle is avt underscore i am so just like my website with an underscore instead of a dot and i'm actually writing my phd thesis which i mentioned gaussian processes briefly which is sort of the main topic of the thesis i'm actually writing my thesis in an open source format that anybody can read and look at while i write it and i'm actually due to submit very very soon so the thesis is close to complete and yeah just uh you know go on github check that out i'll have a pre-compiled version of it available soon because overleaf is becoming very slow compiling the thesis and that makes it a bit difficult for people to get to uh as it's gotten quite quite long but it's yeah it's there feel free to check it out feel free to follow me feel free to send me an email i'll have that in the show notes as well so people can find it there too thank you so much for taking the time to come on and share your work thanks for having me that concludes another installment of data skeptic time series our guest today alex trenin thanks to our sponsors data iq and vpls myself claudia armbruster as associate producer vanessa bly guest coordinator and our host kyle police [Music] you