ETA Prediction with Graph Neural Networks in Google Maps | Paper Explained
👨‍👩‍👧‍👦 JOIN OUR DISCORD COMMUNITY:
Discord ► https://discord.gg/peBrCpheKE

📢 SUBSCRIBE TO MY MONTHLY AI NEWSLETTER:
Substack ► https://aiepiphany.substack.com/

❤️ Become The AI Epiphany Patreon ❤️ ► https://www.patreon.com/theaiepiphany

In this video I cover the "ETA Prediction with Graph Neural Networks in Google Maps" paper. An awesome new real-world application of GNNs!

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
✅ Paper: https://arxiv.org/abs/2108.11482
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

⌚️ Timetable: 
00:00 Intro - GNNs in production
02:40 How graphs are formed
05:30 Graph features
07:10 GNN explained (DeepMind GN)
12:40 Different horizons
14:30 Loss functions
18:45 Reducing the variance
21:50 ETA baselines explained
25:30 How does the inference work
28:20 Offline results
30:45 Ablations and experiments
37:30 Outro, engineering

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
💰 BECOME A PATREON OF THE AI EPIPHANY ❤️ 

If these videos, GitHub projects, and blogs help you,
consider helping me out by supporting me on Patreon! 

The AI Epiphany ► https://www.patreon.com/theaiepiphany
One-time donation: 
https://www.paypal.com/paypalme/theaiepiphany 

Much love! ❤️

Huge thank you to these AI Epiphany patreons:
Eli Mahler
Petar Veličković
Bartłomiej Danek
Zvonimir Sabljic

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

💡 The AI Epiphany is a channel dedicated to simplifying the field of AI using creative visualizations and in general, a stronger focus on geometrical and visual intuition, rather than the algebraic and numerical "intuition". 

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
👋 CONNECT WITH ME ON SOCIAL 
LinkedIn ► https://www.linkedin.com/in/aleksagordic/ 
Twitter ► https://twitter.com/gordic_aleksa 

Instagram ► https://www.instagram.com/aiepiphany/ 
Facebook ► https://www.facebook.com/aiepiphany/ 

👨‍👩‍👧‍👦 JOIN OUR DISCORD COMMUNITY:
Discord ► https://discord.gg/peBrCpheKE

📢 SUBSCRIBE TO MY MONTHLY AI NEWSLETTER:
Substack ► https://aiepiphany.substack.com/

💻 FOLLOW ME ON GITHUB FOR ML PROJECTS: 
GitHub ► https://github.com/gordicaleksa 

📚 FOLLOW ME ON MEDIUM:
Medium ► https://gordicaleksa.medium.com/ 
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

#googlemaps #gnns #graphml
 What's cracking guys in this video I'm covering this super exciting paper called ETA prediction with graph neural networks in Google Maps. So it's yet another application of graph neural networks in a like a real world setting. So previously on this channel I've covered PINSAGE. So that's another application of GraphML to the recommender system application. And here we are using it to predict this. So ETA stands for Estimated Time of Arrival. I mean you probably already knew that if you have ever used Google Maps. And basically as you can see it's running at production settings at Google Maps and they achieved some awesome results. So basically our GNN proved powerful when deployed significantly reducing negative ETA outcomes in several regions compared to the previous production baseline up to 40 plus percent in cities like Sydney. And I'm going to zoom in a little bit here into this map here. And you can see the results are pretty awesome like in Sydney they achieve like 43 percent. And as you can see it's very dependent on the geography. So in some cities like this Tai Chung city it's up to 51 percent in Europe it seems to be a little bit lower compared to these like increases here. And I guess it has a lot to do with the topology of the place with the data available because obviously this is going to be trained in a supervised setting. Even though the experimented with some unsupervised methods I'm going to see those details a bit later. But yeah it'd be funny to kind of analyze and understand why the why these variations in the in the improvements. But that's like something that's outside of the scope of this paper obviously. OK so let me just motivate the whole paper and kind of explain the problem if it's not already clear enough. So basically we have you have a point A so that's your starting point and you have like a point B so that's your end point. And basically what like Google Maps does is one of like one of the modules of that application is going to source like feasible routes from A to B. So something like this A to B and then like a third path maybe like this. And then this system is going to like estimate ETA for all of these routes. So ETA or estimated time of arrival. And that basically means how like long does the system expect your travel to last from A to B. And basically once you have that information Google Maps can kind of sort like sort basically all of these routes according to ETA and suggest you the shortest routes like timewise. Shortest maybe they're longer like physically but like there you'll get quicker there pretty much. OK so that's hopefully the problem is now clear enough. Now let's see how this is like posed as a graph ML problem. So I think it's pretty clear but let me let me kind of explain that. And the part that's super interesting is how they constructed graphs. So it's not that intuitive and this is not something I'd expect. But yeah so I guess if you had like like a street here and you had some intersection here and then you had another street here and you had another street here I guess the way you model this thing. So if you had let's say we have another intersection here. So how you would model it is basically how I just like draw it down. So you have this these will be nodes. So the intersections would be nodes and then you'd probably have like the whole street would be an edge between two nodes. And I guess once you think about it a bit more deeply it makes sense that I mean if this is like two kilometers you don't want to have that as a single edge. Whereas like some other streets may be like 20 meters or something. So it makes sense to kind of segment the roads themselves into nodes. So that's exactly and precisely what I did here. So as you can see here they segment the roads into these segments and so this is called a segment. Let me just get the like terminology out there. So this is a segment and this whole thing here is called a super segment and you can then like going from here to here you can see that these things so the segments will be nodes and the edges will exist between the like obviously segments that are connected. So something like this. So this would be like like a graph. And finally you can see that on the third like chart here. And so that's the final super segment and that's the unit that the graph like the graph neural network will be consuming. So obviously if you're not familiar with graph ML I have a whole playlist you can check it out. I'll link it somewhere here. But basically what is needed here is you. I mean with every machine learning algorithm but like here as well. So you want to associate certain features with all of these nodes and that's precisely what I've done. And so once you have a graph once you have the features then you just need a graph and then and you can basically predict that like time it takes to traverse a certain segment. So what the graph neural network is going to do is given as an input this this super segment is going to predict among other things is going to predict how long does it expect once you enter. So once you enter here how long does it take to exit here. So that will be like a node level prediction. But the system is also going to predict how long does it take if you enter here. How long does it take you to exit here. So all of those predictions are going to be made by the G and M. So let's slowly start digging into details so you can understand the like the like specifics of this whole pipeline. First things first we've got like features. I mentioned those and here are some of the features they were using. So the actual no by the way this is these are labels. So the actual traversal times along segments and super segments in seconds are used as node level and graph level labels for prediction. So hopefully now it's clear. So you have some graph and the labels are basically the amount of seconds that it takes to traverse the segment or traverse the super segment. And all of that data is obviously collected by Google Maps throughout the last many years. And so they got the data available. So that's something that's given. And now the features. So on the segment node level we provide the average real time and historical segment traversal travel speeds and times. So both the speeds and times are like ingrained in the feature vectors as well as segment length and segment priority. Like is it a road classific is it a highway is it an intersection I guess like all of that is provided as features. And so I won't be digging into details here obviously like on a high level you can understand that here we've got some domain specific knowledge like that's basically injected into these feature vectors. And the other important thing is that we additionally provide learnable segment and super segment level embedding vectors. So that means that these vectors here are going to be a concatenation between all of the features we just saw like the length of the road etc. Etc. And the second part is going to be learnable. So we will have a learnable portion of those vectors. OK. So that's that's how I understand all of this. OK. What next once we have labels we have data we know how graphs are formed. We need a gene and obviously. And the model they are using here is graph network. So that's a paper that came out of deep mind as well. It's a super generic framework. You can see the equations here. So these are the basically update equations for the edges for the nodes and for this like basically graph level embedding. And these are some like basically aggregation functions again for edges and for for nodes. And let me try and break them down so that you have a feeling what's going on in here. So let me draw a simple graph here. So I have a note here. Let me draw a couple more nodes or something like this. And we've got some edges. So there's going to be an edge here and then here and then here maybe and then here. So this is the update rule for for the edge. And basically this fight what I've used in practice is a simple MLP. So it's a multilayer perceptron. Nothing fancy there. So what happens is you take the edge feature. So this is this is an edge and you've got some features there. And so basically you take those features you put them in here and you probably concatenate those features with the next thing. So you concatenate those features with the source node with this one and with the target node. So basically the two nodes that the edge is connecting with. So those are this is a source and this is the target nodes features. And you just add this global. This is a global feature vector that's basically associated with the graph itself. So there is some like a separate feature vector out here that's being updated together with this graph like features. And so once you concatenate all of the data all of that data and you kind of pass it through the MLP. That's the update and you get a novel edge representation which is like denoted here as E prime. And very similarly you do it for nodes. So you have a so you basically have a node here. Let's focus on this one. So what do you do as you can see here you concatenate its features again with this global thing. Global feature vector and you additionally add this aggregated like vector that's formed precisely in this manner. So this way. OK what you do is and these are simple summations. So just when you see this thing in all one you can think of it as a summation. So what you do here is you basically take all of the incoming and outgoing edges. And you just kind of sum up their features of those edges and that's this vector. And then you concatenate it here and you use an MLP to produce a novel representation for this node. OK. Hopefully that's clear enough. So in this particular case that's going to be this edge. It's going to be this edge and it's going to be this edge. And finally you're updating this global feature vector. Again you use its own features. You use like basically the aggregated versions of edges and nodes. Now you basically take all of the edges and all of the node features and you just basically sum them up. I guess you may need to do some kind of like me like averaging there. But basically you kind of combine them and you concatenate them. Pass them through the MLP and you get a novel representation here. And that's it. You just rinse and repeat. Usually GNNs are very shallow so you won't be doing this like in CNN like 150 times like in Resonance. You'll be doing this a couple of times two three times and we'll see that in this paper in particular. They are only doing it two times. OK. So that's a high level overview of this GN block. And now let's see what else. So as a quick recap of GN architecture it's fairly simple. Again you have a graph here. I'm going to denote it as this blob and then you have an encoder block here. So something like this. So this is encoder. Then what to do is they once you encode these raw features into a latent space you have this processor like part of the pipeline which is basically your GNN. And you apply like this logic you just saw here a couple of times and then you take those latent representations which are now refined. You pass them through the decoder and the decoder will finally output all of the predictions you're interested in. So that's it on the high level how this GN like pipeline looks like. They mentioned it also here so we compose three GN blocks into an encode process decode architecture and learn a separate model for each horizon H. These blocks are defined as blah blah blah. I'm going to return to this thing in a second because it's very important this horizon detail. But I'm going to first kind of like explain this thing in a bit more detail. So the encoder is first applied to the super segment S with the previously described raw features. So those were the as we saw the speeds the time the additional like learnable embeddings. Those are the raw features. It produces latent representations of nodes edges and the super segment itself. So that's the you components. So that's the this is the super segment segment representation. These latents are then passed to the processor which is applied two times with shared parameters. So there is additional sharing of the parameters here to update these representations. Finally these representations are transformed into appropriate predictions by applying the decoder. So again this is going to output the basically both node wise as well as graph level predictions of how long does it take to traverse a segment or a super segment. Those are going to be outputs. We'll see soon see a bit more details there. But yeah now getting back to the horizon detail it's very important because what they do is they basically for each region of the world because you obviously can't train a single system that will work everywhere. What they do is like focus on some specific region like take Serbia. That's my home country. I'm going to take Serbia as an example and I'm going to draw something that looks like Serbia but not exactly. And so this is Serbia and basically you train a single GNN for this region. So for Serbia or even some like like a small smaller like part of Serbia and you additionally train a GNN model for different horizons. So that means what they were using was zero minutes 10 minutes 20 minutes 30 minutes and finally 60 minutes. So an hour. So they're going to have one two three four five GNN for a specific region. So why is that. Well the reason is this is like zero GNN. Let me call it that way is basically going to is basically going to predict the time it takes to traverse this particular segment right now. Whereas when you input like a graph a super segment into this one is going to predict what the traversal time of that super segment is going to be or segment in 10 minutes. And by analogy this one will like tell you like how long does it take to traverse a segment or a super segment in 20 minutes 30 minutes and one hour. And they just figure out experimentally that that's that leads to much better performances. And that's what I stick with. So yeah this was Serby. OK something like that. Nice. Let's see what else. So once we have we know how the graph is structured. We know how the graph neural network is structured. Now let's see how the actual loss functions look like and a loss function at least the one they're using in production. They also experiment and we'll see those details in a minute with some other losses here which are unsupervised. So basically unsupervised and soup. And so this is using production. Basically there are three components. One component is this SS which is basically super segment. One component is this which is segment level prediction. And one component is this segment but cumulative prediction. We'll see what that means in a second. So here is how the super segment loss is formed. You iterate over different super segments. You have this normalization part which I'm going to explain in a second and you have your Huber loss over here. So Huber loss for those of you who are not familiar with that is very simple and it's supposed to kind of prevent certain outliers from like destabilizing the training. So it looks like basically like a parabola in a certain range which is denoted by delta and minus delta here. And then you basically have just a linear extrapolation here. So here you have a linear function. So it's not a parabola here. It's not going to be like this. It's going to be a simple linear function there. And so the gradients remain constant. They are not increasing. And so this kind of stabilizes the training when you're updating the gradients. If you watch my DQN video or checked out my project on GitHub about DQN, that's I think the only place I've seen Huber loss being used so far. But I guess it's a neat technique to have in your toolkit whenever you want to kind of stabilize the update procedure. So this 400 basically means this delta is 400. And so the main part here is this means this is a prediction like a super segment level prediction at time t with horizon with the model that has a horizon H. So if we had the model, if we're training the model with the horizon zero, you can just ignore this. So we are predicting we have the ground truth here. So this is the GT label. So this part is the GT. So this is from the data set that the Google Maps team collected. And this will be your actual prediction on a super segment level. And so basically you just do this Huber loss over it. And that's that's it. So for the normalizing normalization component, I owe you an explanation there. So this flow basically tells you the following thing. So this flow of I is how long does it take to traverse this super segment I when there is almost no traffic on the road? And the kind of reasoning behind it is so imagine if you have a super long like a super segment. And that means that these errors are probably going to be larger because there is so much more like uncertainty when you have a larger like a route. Right. And so what you do is kind of normalize with this like zero time or basically the time it takes to traverse it when there are no cars in there, no traffic. And so that's kind of the intuition. So the bigger the road, you want to kind of normalize it by its this flow time. Similarly for segments. So you additionally just have here, as you can see, you have this iteration over the segments of the super segment. So M this index I means the amount of segments in that super segment. And you do the same procedure basically. And finally, you have these cumulative segments. So what they do is let me let me kind of jump back here. So it will tell you if you're here right now, it's going to tell you how long did it take to get up to there. So it won't tell you the traversal time from here to here. It's going to tell you the cumulative time from here all the way here to here. And then for for this one, obviously, you're just going to include this one as well and et cetera. So that's the whole point there. OK, I think we're pretty much done with the methods. There is two more details. Fairly important for the production setting. Genehands and all that's all nice. But like at the end, you got to make the thing work. And what I noticed is that as they were dumping models across every single epoch, the predictions that came from those models were like varying a lot. So there was like a large amount of variance there. And so they they used basically two methods to dampen out those oscillations to kind of reduce the variance. One is using this meta gradient method. And the second one is using this exponential moving average method. And this you've seen this if you watch my previous videos, like self supervised learning field uses EMA a lot to form the teacher networks, et cetera. But basically, let me let me first quickly explain meta gradient. I won't be digging into details here. But like the whole idea is instead of picking a learning rate and some schedule, you basically treat learning rate as a hyperparameter itself and you jointly optimize the learning rate alongside the model parameters. So this is what these fancy formulas are telling us. We're basically also updating this this this is learning rate parameter using the loss function. So this is just a generic set of meta gradient. That's why they're using this new this Greek symbol. But in this particular application of this paper, new is basically learning rate. And so you are tuning those as well during the training. And the second thing is they're using EMA, as I said. So basically, what do you do? You take when you're updated, when you update the GNN, you don't just use those weights as as the new weights. What you do is instead you take this previous weights, which is the EMA accumulative estimation of weights. You kind of weighted with this parameter and they've used zero point nine nine here. That's again a hyperparameter. They just figured out that that number works well. And these are the novel weights. And as you can see, so this is kind of pulling these novel weights towards this stable estimate of the weights that was created through snapshots, multiple snapshots in the history, I guess. That's pretty much it. That's the whole method. And now I'm going to slowly start explaining the experimental setup. I'm going to show you the results. And yeah, for showing you the baselines they're going to compare with, let me just quickly just mention this part. So they mentioned that we know that November twenty twenty data may be susceptible to covid-19 traffic patterns. And hence we attempted to select regions that minimize this deviation for evaluation in order to capture performance under regular traffic conditions. So the thing is, obviously, because because of the covid, the traffic patterns have changed. And so they are kind of trying to find the regions where even post covid, hopefully they'll have relevant results. And so my question is, how do they actually find the regions that minimize this deviation? There are no mention they haven't mentioned this in the paper, but I'd love to know the answer. So if somebody somehow knows that, feel free to comment down in the comment section. OK, having said that, let me show you the baselines they are they're using. So first baseline is super simple. It's basically real time travel times. So what you do is the following. So you have a segment. So you have one segment and I'm just going to draw it here as a square, but it basically represents this thing here. So one of these segments. And so what happens is the following thing. So they have over the last like two minutes or five minutes, they have the data of what were the traversal times of the cars and vehicles in general passing through that segment. I mean, they say here nicely summation of segment level travel times computed using segment speeds averaged over a two minute period. So you have a two minute window prior to the time of prediction. So basically take the data, the recent data, the last two minutes, and you use that as a as a weight as a predictor. So what happens basically is you find that average for this segment, then you find the average for the next segment. You find the average for the next segment. And if this was the whole super like a super segment, the predictor would just sum up these average numbers. Let's call this T1, T2, T3. You just basically take and sum them up to get the final value. So T will just be basically a sum of all of these TIs where individual TIs for this particular segment, you use the last two minute data and compute it. So it's a nonparametric model. You don't have a neural network. You don't have any fancy model models. You just have nonparametric method there. Fairly simple with historical travel times baseline. What you do here instead of using the last two minutes, like basically you can use both the future and past information, but in the like last days. So, for example, if this if we're trying to predict like what is going to what is the travel time of a super segment at 4 p.m. What they're going to do is take a look at the 4 p.m. So let me just kind of draw this as a timeline. So 4 p.m. is here. So they're going to take the data over the last, I don't know, like 15 minutes, maybe here and 15 minutes here. And they're going to take a look at like what those times were like last week and the week before and etc. And they are going to combine and average out that data over the last some weeks. So they say here average across last 17 weeks. So that's how you form the predictions here. So that's so you have you use the historical data to form these TIs and then you again just sum them up to get the final T. Finally, deep sets is like the last method. This is a model based approach. So this is not so this is parametric method. And the thing is, it's ignoring the graph structure. So if you have a super segment, what this method is going to do is the following. Let me kind of go up there. It's going to be easier to explain. So this method is going to pass this through an MLP, pass this through an MLP, pass all of the segments through an MLP. Then it's going to like kind of aggregate all of those, maybe using summation. And then it's going to pass that final representation. So we have a final representation here, which is formed, as I said, by aggregating all of these feature vectors of all of these segments. And then you just pass it to another MLP here to get the final representation. And then you can do the predictions. So as you can see here, you're treating this as a bag of words in a way. You're just taking all of those features, feature vectors of the segments. You're kind of ditching the graph data, the graph information of how they're connected. And you just kind of aggregate them and then inform the prediction. So that's the deep set. Having explained deep set, I realized I have not explained how the actual inference looks like once we have this this GNN model trained. So let me explain that in a second. Basically, this is how the serving looks like. Once this app, once this model is running in production in your Google Map application, this is how you're actually getting the results. So imagine you have a route from A to B. So you have route from A to B and A and B are connected with three super segments. So we have like something like this. A is connected by a segment one, two, and three to the segment, to the actual destination B. OK, so what do you do here? And this is going to make the reason behind using the horizon models like more clear, hopefully. So what happens is you take. So we are at time t and you basically take take this segment one and use the model that has the horizon equal to zero. And you do prediction and that is going to give you t one. So that's basically the estimated, the predicted time. What the model is expecting, how long do you need to to kind of traverse this segment one? So once you have t one, let's imagine t one is 12 minutes. So this is 12 minutes, 12 minutes. OK, so once you have 12 minutes, then what you do is out of the pool of the horizon models. So that means, as I said, we have the 10 minute model, the 20 minute model, the 30 minute model. So we are because we are 12 minutes, we're going to take the models that have horizon 10. So I'm going to denote them as horizon 10 and you're going to take the model that has horizon 20. So that's horizon 20 like this. And now you're going to take those models and pass the segment two through them. So H10 is going to tell you how long does it take to traverse segment two in 10 minutes from now. But since we have 12, we are actually expecting 12 minutes. That means we're going to do basic interpolation here. So this one is going to tell us the result. Let me call it t two at 20. And this will be t two. So that's the second time it takes to traverse the second segment according to this model 10. And you're going to combine this two informations, simple interpolation to form the actual time it takes to traverse the data. So it's going to be somewhere between these two numbers. Right. And so once you have the t two, you can use the t two and t one. You can add them up and then do the same procedure for segment super segment three and rinse and repeat until you get to the end point B. So, yeah, hopefully that's now it's clear how you're using this model in inference. Now, let me get back to the where we stopped. So I explained the deep sets. That's the third baseline. Now, let's see the actual results here. By the way, they're using this RMS metric to to kind of compare the baselines. And you can see here it's very simple. You basically take the super segment level predictions. You do the summation over the super segments and you do a square and you average here. Yeah, basically root mean squared error. It's pretty pretty self-explanatory. And so here are the results. You can see the real time baseline, the historical, the deep sets baseline and the GM baseline. And you can see that it's they also show it's a significant statistically significant result. And it's lower compared to all of the other baselines, which is cool. So the thing that initially kind of bugged me here is that if you take a look at the numbers, the differences are fairly trivial, like small compared to the other baselines. So deep set seems to be performing really well. So why the whole hustle? Like why why are we using the graph data? And I'm going to get to that in a second. But like, let's see here, if we compare these numbers, like take this number, you can see it's way worse compared to these two models. So these two are out of the question. That's obviously like clear. But like between deep sets and GM, what should we use? And I mean, it's a bit better, but is it like worth it? And the thing is one important note here dimension is so one note is that these improvements are computed over individual super segments, and they will accumulate over entire routes. Hence, our improvements may quickly become more important on a whole route level. So a super segment may be and I think they have a data somewhere here. Let me find it. Where it is. Okay, here it is data set statistics. So you can see that the super segment length is so average segment length is around like 100 meters and super segments are around so average number of segments per super segment is around 20. So that means probably average super segment has around two kilometers. So once you accumulate that over like 10 kilometers, when you have multiple super segments, then obviously the errors accumulate and GM start bringing more and more advantage compared to these other baselines. And I mean, obviously, Google would not put this into production if it wasn't meaningful enough. So yeah, but just don't get confused by the small differences. Now, hopefully, it's clear enough. And let's see the ablations. So one thing I have not mentioned is they've experimented with various things. I did mention the unsupervised loss. So they tried using stuff like deep graph info max. They've also experimented with these combinations of aggregators and like not using just the some aggregator but using some other types of aggregations. And all of the ideas come from this principal neighborhood aggregation paper. You can check it out. Yeah, just keep in mind that they've experimented with lots of things and they eventually decided not to use many of those ideas in the production because the trade off was not acceptable. So even though they brought some performance benefits, the cost of kind of serving those more like complex models is way higher. So, okay, let's kind of skim over these ablations. I mentioned those embedding vectors. So aside from the domain knowledge that was ingrained by those speeds and times in the feature vectors, we had the learnable portion. And you can see that actually using like both embeddings, both the segment level embeddings as well as the super segment embeddings brings better results. Don't get confused by this column like these acronyms. This stands for New York City, I guess, LA, Tokyo and Singapore. They had to kind of obviously pick a subset of the cities. They can't evaluate this on the whole on a global scale. And you can see results are always better when you're using the embeddings. That's that's kind of clear. Second thing here is they showed how the meta gradient and EMA are reducing the variants in the during the training. So we can see on the x axis here, basically training iterations on the y axis, we see the RMS metric. And we can see that when we're just using Adam with no EMA and no meta gradients, you can see that just the red curve is kind of getting crazy here. And once you start adding EMA and meta gradients, they show that the blue curves are using both of these is the best thing to do. And they show that not only for they'll just show for it for Tokyo and they show it also for for LA here. And I just made a note here. So basically, it'd be interesting to see how learning rate evolves over the duration of the training. So that means I'd love to see the like how the meta gradient is tuning the learning rate. Can we see some interesting patterns there? Like those types of visualizations in the appendix would be super appreciated. And secondly, be interesting to understand which other schedules did they try with Adam before deciding to go with meta gradients. Let's wrap up the ablation studies. They experimented with these extended super segments and extended super segments plus extra features, whereby they were using additional segments, he can see extended super segments, but they were still predicting only the like traversal times for the segments in our original super segment. And they basically showed that all of that kind of helps, but like it's very, very expensive, both memory wise and I guess inference wise. And so they decided not to use this in the production setting. Here you can see the unsupervised loss I mentioned. So this is the deep graph informax paper. This is the I guess, or encoder. So graph or encoder, I guess, paper. And so you can see that those two are, again, improving results across various cities and various horizons. So both for New York City, LA, et cetera, for different horizons. But the trick here is, and this is an excerpt from this paper. So the optimal variant and hyperparameters were different for each region and prediction horizon. Thus, it is likely expensive to tune such losses for all existing regions and each horizon. So as I said, you're going to be using various different GNNs depending on region. So if you have additionally have to tune these kind of hyperparameters, it's going to be hard and expensive. And so they decided not to use them in the actual production setting. Finally, let's see this, these results. So using various different aggregation functions like the sum is the actual, the one that's using production, but they also try the square root, the mean, the max and all of them combined. And as you can see, usually this all of them combined, like gives you additional performance. But again, you have to once you're in a production setting, this is engineering, you have to trade off the costs. And so they stick with the sum function. They also did this online evaluation of GN compared to the baselines and they showed it's again better, same as in the offline setting we just saw. So a couple of things that bug me there is, so they mentioned that computed over all tracks within a week, specifically January 15th through January 22nd. What is not clear to me is what it means over all tracks. So do they actually average the results across every single region they are covering or what? So this part kind of bugs me. So yeah, not sure about it. And again, I said the results are nice, but like basically we don't have a gut feeling for what these small improvements mean. And so A, it'd be nice to have like something like, hey, when you're using this model, it's going to save you up that many seconds or minutes compared to this baseline. So that would be much more intuitive. We'd have a much better intuitive understanding of what's going on here. Secondly, and I noted it here, basically some type of geographical heat maps where we see, depending on the region, like what the performance differences are, that'd be super nice visualization, I guess. Finally, they did the last evaluation on this particular route in LA, I think, and they show certain results and I have a same remark here. It's not intuitive what these curves mean. Like, I mean, you can see that the GN, so this graph neural network model is way better. It's better compared to real time baseline, but I don't have a gut feeling for what this means. And so yeah, that kind of sucks. And also they don't have any units here. And so I guess it's seconds, but it's kind of not clear enough. And so they here also show for the, when we have results for the horizon, like one hour from now, you can see that this GN that was trained with that horizon is way better compared to the GN that was trained with the horizon equals to zero. So that's kind of argument behind why do we need all of these multiple horizon GNM models and we're combining them to actually serve the results, the end results. I'm going to end it up here and I'm going to just briefly mention that this is a thing that's running in production, which means that research was only a small portion of this whole project and there were many engineering challenges they had to solve. So one of them was, so they had to obviously cache results. So as they say here, the path in an ETA request usually includes multiple super segments and making predictions for these super segments on the fly is not practical nor scalable. So they had to kind of cache the results and then periodically refresh all of the cache. So that's one of the engineering details. The second thing they mentioned here, for less frequently visited road segments, we use simpler per segment models. So they drop to simpler baselines in certain regions. So it's a complex system. There are many components. So the meta-gradient, the EMA, the graph neural networks, all of this engineering tricks to make this work and I think it's a very impactful project. I mean, I use Google Maps all the time. So I really love this paper. I think it's a clearly written paper aside from a couple of these remarks and maybe the lack of appendix section. Hopefully like this video. If you did share it out with a friend, subscribe to this channel, hit the bell icon. Also join the Discord community. There is a lot of engagement happening there. Cool people interested in ML helping each other out. So yeah, do check it out and until next time, bye-bye.
[{"start": 0.0, "end": 7.2, "text": " What's cracking guys in this video I'm covering this super exciting paper called ETA prediction with graph neural networks in Google Maps."}, {"start": 7.6000000000000005, "end": 13.6, "text": " So it's yet another application of graph neural networks in a like a real world setting."}, {"start": 14.200000000000001, "end": 16.8, "text": " So previously on this channel I've covered PINSAGE."}, {"start": 16.96, "end": 21.76, "text": " So that's another application of GraphML to the recommender system application."}, {"start": 21.96, "end": 24.2, "text": " And here we are using it to predict this."}, {"start": 24.240000000000002, "end": 26.76, "text": " So ETA stands for Estimated Time of Arrival."}, {"start": 26.76, "end": 29.96, "text": " I mean you probably already knew that if you have ever used Google Maps."}, {"start": 30.32, "end": 37.32, "text": " And basically as you can see it's running at production settings at Google Maps and they achieved some awesome results."}, {"start": 37.32, "end": 50.92, "text": " So basically our GNN proved powerful when deployed significantly reducing negative ETA outcomes in several regions compared to the previous production baseline up to 40 plus percent in cities like Sydney."}, {"start": 51.160000000000004, "end": 54.56, "text": " And I'm going to zoom in a little bit here into this map here."}, {"start": 54.56, "end": 60.440000000000005, "text": " And you can see the results are pretty awesome like in Sydney they achieve like 43 percent."}, {"start": 60.64, "end": 63.040000000000006, "text": " And as you can see it's very dependent on the geography."}, {"start": 63.040000000000006, "end": 72.24000000000001, "text": " So in some cities like this Tai Chung city it's up to 51 percent in Europe it seems to be a little bit lower compared to these like increases here."}, {"start": 72.56, "end": 80.24000000000001, "text": " And I guess it has a lot to do with the topology of the place with the data available because obviously this is going to be trained in a supervised setting."}, {"start": 80.24, "end": 85.64, "text": " Even though the experimented with some unsupervised methods I'm going to see those details a bit later."}, {"start": 85.91999999999999, "end": 94.03999999999999, "text": " But yeah it'd be funny to kind of analyze and understand why the why these variations in the in the improvements."}, {"start": 94.03999999999999, "end": 98.24, "text": " But that's like something that's outside of the scope of this paper obviously."}, {"start": 98.56, "end": 104.39999999999999, "text": " OK so let me just motivate the whole paper and kind of explain the problem if it's not already clear enough."}, {"start": 104.4, "end": 113.52000000000001, "text": " So basically we have you have a point A so that's your starting point and you have like a point B so that's your end point."}, {"start": 113.52000000000001, "end": 123.12, "text": " And basically what like Google Maps does is one of like one of the modules of that application is going to source like feasible routes from A to B."}, {"start": 123.12, "end": 128.52, "text": " So something like this A to B and then like a third path maybe like this."}, {"start": 128.52, "end": 134.60000000000002, "text": " And then this system is going to like estimate ETA for all of these routes."}, {"start": 134.60000000000002, "end": 136.76000000000002, "text": " So ETA or estimated time of arrival."}, {"start": 137.08, "end": 143.16000000000003, "text": " And that basically means how like long does the system expect your travel to last from A to B."}, {"start": 143.48000000000002, "end": 154.08, "text": " And basically once you have that information Google Maps can kind of sort like sort basically all of these routes according to ETA and suggest you the shortest routes like timewise."}, {"start": 154.08, "end": 161.12, "text": " Shortest maybe they're longer like physically but like there you'll get quicker there pretty much."}, {"start": 161.4, "end": 164.24, "text": " OK so that's hopefully the problem is now clear enough."}, {"start": 164.48000000000002, "end": 170.44, "text": " Now let's see how this is like posed as a graph ML problem."}, {"start": 170.92000000000002, "end": 174.12, "text": " So I think it's pretty clear but let me let me kind of explain that."}, {"start": 174.72000000000003, "end": 178.12, "text": " And the part that's super interesting is how they constructed graphs."}, {"start": 178.12, "end": 181.60000000000002, "text": " So it's not that intuitive and this is not something I'd expect."}, {"start": 181.6, "end": 194.16, "text": " But yeah so I guess if you had like like a street here and you had some intersection here and then you had another street here and you had another street here I guess the way you model this thing."}, {"start": 194.16, "end": 196.64, "text": " So if you had let's say we have another intersection here."}, {"start": 197.0, "end": 200.88, "text": " So how you would model it is basically how I just like draw it down."}, {"start": 201.04, "end": 202.76, "text": " So you have this these will be nodes."}, {"start": 202.76, "end": 208.84, "text": " So the intersections would be nodes and then you'd probably have like the whole street would be an edge between two nodes."}, {"start": 208.84, "end": 217.2, "text": " And I guess once you think about it a bit more deeply it makes sense that I mean if this is like two kilometers you don't want to have that as a single edge."}, {"start": 217.48000000000002, "end": 221.32, "text": " Whereas like some other streets may be like 20 meters or something."}, {"start": 221.32, "end": 224.96, "text": " So it makes sense to kind of segment the roads themselves into nodes."}, {"start": 225.2, "end": 227.36, "text": " So that's exactly and precisely what I did here."}, {"start": 227.4, "end": 232.72, "text": " So as you can see here they segment the roads into these segments and so this is called a segment."}, {"start": 233.28, "end": 236.32, "text": " Let me just get the like terminology out there."}, {"start": 236.32, "end": 252.07999999999998, "text": " So this is a segment and this whole thing here is called a super segment and you can then like going from here to here you can see that these things so the segments will be nodes and the edges will exist between the like obviously segments that are connected."}, {"start": 252.07999999999998, "end": 253.04, "text": " So something like this."}, {"start": 253.12, "end": 255.56, "text": " So this would be like like a graph."}, {"start": 255.72, "end": 259.03999999999996, "text": " And finally you can see that on the third like chart here."}, {"start": 259.36, "end": 265.92, "text": " And so that's the final super segment and that's the unit that the graph like the graph neural network will be consuming."}, {"start": 265.92, "end": 271.36, "text": " So obviously if you're not familiar with graph ML I have a whole playlist you can check it out."}, {"start": 271.52000000000004, "end": 272.8, "text": " I'll link it somewhere here."}, {"start": 273.12, "end": 276.0, "text": " But basically what is needed here is you."}, {"start": 276.24, "end": 279.48, "text": " I mean with every machine learning algorithm but like here as well."}, {"start": 279.48, "end": 284.96000000000004, "text": " So you want to associate certain features with all of these nodes and that's precisely what I've done."}, {"start": 285.12, "end": 294.6, "text": " And so once you have a graph once you have the features then you just need a graph and then and you can basically predict that like time it takes to traverse a certain segment."}, {"start": 294.6, "end": 305.24, "text": " So what the graph neural network is going to do is given as an input this this super segment is going to predict among other things is going to predict how long does it expect once you enter."}, {"start": 305.24, "end": 309.0, "text": " So once you enter here how long does it take to exit here."}, {"start": 309.24, "end": 311.48, "text": " So that will be like a node level prediction."}, {"start": 311.64000000000004, "end": 315.24, "text": " But the system is also going to predict how long does it take if you enter here."}, {"start": 315.48, "end": 317.64000000000004, "text": " How long does it take you to exit here."}, {"start": 317.88, "end": 320.6, "text": " So all of those predictions are going to be made by the G and M."}, {"start": 320.6, "end": 327.96000000000004, "text": " So let's slowly start digging into details so you can understand the like the like specifics of this whole pipeline."}, {"start": 328.20000000000005, "end": 331.0, "text": " First things first we've got like features."}, {"start": 331.0, "end": 334.36, "text": " I mentioned those and here are some of the features they were using."}, {"start": 334.36, "end": 337.56, "text": " So the actual no by the way this is these are labels."}, {"start": 337.56, "end": 344.6, "text": " So the actual traversal times along segments and super segments in seconds are used as node level and graph level labels for prediction."}, {"start": 344.6, "end": 345.56, "text": " So hopefully now it's clear."}, {"start": 345.56, "end": 354.68, "text": " So you have some graph and the labels are basically the amount of seconds that it takes to traverse the segment or traverse the super segment."}, {"start": 354.68, "end": 360.04, "text": " And all of that data is obviously collected by Google Maps throughout the last many years."}, {"start": 360.04, "end": 362.04, "text": " And so they got the data available."}, {"start": 362.04, "end": 364.04, "text": " So that's something that's given."}, {"start": 364.04, "end": 366.04, "text": " And now the features."}, {"start": 366.04, "end": 373.32, "text": " So on the segment node level we provide the average real time and historical segment traversal travel speeds and times."}, {"start": 373.32, "end": 381.64, "text": " So both the speeds and times are like ingrained in the feature vectors as well as segment length and segment priority."}, {"start": 381.64, "end": 387.71999999999997, "text": " Like is it a road classific is it a highway is it an intersection I guess like all of that is provided as features."}, {"start": 387.71999999999997, "end": 401.0, "text": " And so I won't be digging into details here obviously like on a high level you can understand that here we've got some domain specific knowledge like that's basically injected into these feature vectors."}, {"start": 401.0, "end": 406.92, "text": " And the other important thing is that we additionally provide learnable segment and super segment level embedding vectors."}, {"start": 406.92, "end": 415.24, "text": " So that means that these vectors here are going to be a concatenation between all of the features we just saw like the length of the road etc."}, {"start": 415.24, "end": 415.96, "text": " Etc."}, {"start": 415.96, "end": 418.04, "text": " And the second part is going to be learnable."}, {"start": 418.04, "end": 421.48, "text": " So we will have a learnable portion of those vectors."}, {"start": 421.48, "end": 422.52, "text": " OK."}, {"start": 422.52, "end": 424.68, "text": " So that's that's how I understand all of this."}, {"start": 424.68, "end": 424.92, "text": " OK."}, {"start": 424.92, "end": 429.4, "text": " What next once we have labels we have data we know how graphs are formed."}, {"start": 429.4, "end": 430.6, "text": " We need a gene and obviously."}, {"start": 430.6, "end": 434.68, "text": " And the model they are using here is graph network."}, {"start": 434.68, "end": 437.40000000000003, "text": " So that's a paper that came out of deep mind as well."}, {"start": 437.40000000000003, "end": 439.8, "text": " It's a super generic framework."}, {"start": 439.8, "end": 440.92, "text": " You can see the equations here."}, {"start": 440.92, "end": 451.24, "text": " So these are the basically update equations for the edges for the nodes and for this like basically graph level embedding."}, {"start": 451.24, "end": 458.04, "text": " And these are some like basically aggregation functions again for edges and for for nodes."}, {"start": 458.04, "end": 463.08000000000004, "text": " And let me try and break them down so that you have a feeling what's going on in here."}, {"start": 463.08000000000004, "end": 465.48, "text": " So let me draw a simple graph here."}, {"start": 465.48, "end": 467.88, "text": " So I have a note here."}, {"start": 467.88, "end": 471.24, "text": " Let me draw a couple more nodes or something like this."}, {"start": 471.24, "end": 472.76000000000005, "text": " And we've got some edges."}, {"start": 472.76000000000005, "end": 477.72, "text": " So there's going to be an edge here and then here and then here maybe and then here."}, {"start": 477.72, "end": 481.64000000000004, "text": " So this is the update rule for for the edge."}, {"start": 481.64000000000004, "end": 485.48, "text": " And basically this fight what I've used in practice is a simple MLP."}, {"start": 485.48, "end": 487.0, "text": " So it's a multilayer perceptron."}, {"start": 487.0, "end": 488.28, "text": " Nothing fancy there."}, {"start": 488.28, "end": 491.08, "text": " So what happens is you take the edge feature."}, {"start": 491.08, "end": 494.6, "text": " So this is this is an edge and you've got some features there."}, {"start": 495.4, "end": 502.52, "text": " And so basically you take those features you put them in here and you probably concatenate those features with the next thing."}, {"start": 502.52, "end": 508.04, "text": " So you concatenate those features with the source node with this one and with the target node."}, {"start": 508.04, "end": 510.68, "text": " So basically the two nodes that the edge is connecting with."}, {"start": 510.68, "end": 514.68, "text": " So those are this is a source and this is the target nodes features."}, {"start": 514.68, "end": 517.2399999999999, "text": " And you just add this global."}, {"start": 517.2399999999999, "end": 521.16, "text": " This is a global feature vector that's basically associated with the graph itself."}, {"start": 521.16, "end": 529.0799999999999, "text": " So there is some like a separate feature vector out here that's being updated together with this graph like features."}, {"start": 529.0799999999999, "end": 533.4, "text": " And so once you concatenate all of the data all of that data and you kind of pass it through the MLP."}, {"start": 533.4, "end": 540.1999999999999, "text": " That's the update and you get a novel edge representation which is like denoted here as E prime."}, {"start": 540.1999999999999, "end": 543.4799999999999, "text": " And very similarly you do it for nodes."}, {"start": 543.48, "end": 545.64, "text": " So you have a so you basically have a node here."}, {"start": 545.64, "end": 546.6800000000001, "text": " Let's focus on this one."}, {"start": 547.4, "end": 553.0, "text": " So what do you do as you can see here you concatenate its features again with this global thing."}, {"start": 553.88, "end": 561.24, "text": " Global feature vector and you additionally add this aggregated like vector that's formed precisely in this manner."}, {"start": 561.24, "end": 562.28, "text": " So this way."}, {"start": 562.28, "end": 566.9200000000001, "text": " OK what you do is and these are simple summations."}, {"start": 566.9200000000001, "end": 571.4, "text": " So just when you see this thing in all one you can think of it as a summation."}, {"start": 571.4, "end": 575.72, "text": " So what you do here is you basically take all of the incoming and outgoing edges."}, {"start": 576.52, "end": 581.16, "text": " And you just kind of sum up their features of those edges and that's this vector."}, {"start": 581.16, "end": 587.16, "text": " And then you concatenate it here and you use an MLP to produce a novel representation for this node."}, {"start": 587.16, "end": 587.64, "text": " OK."}, {"start": 587.64, "end": 588.92, "text": " Hopefully that's clear enough."}, {"start": 588.92, "end": 591.24, "text": " So in this particular case that's going to be this edge."}, {"start": 591.24, "end": 593.9599999999999, "text": " It's going to be this edge and it's going to be this edge."}, {"start": 593.9599999999999, "end": 596.84, "text": " And finally you're updating this global feature vector."}, {"start": 596.84, "end": 599.24, "text": " Again you use its own features."}, {"start": 599.24, "end": 604.52, "text": " You use like basically the aggregated versions of edges and nodes."}, {"start": 604.52, "end": 609.32, "text": " Now you basically take all of the edges and all of the node features and you just basically sum them up."}, {"start": 609.32, "end": 613.5600000000001, "text": " I guess you may need to do some kind of like me like averaging there."}, {"start": 613.5600000000001, "end": 616.84, "text": " But basically you kind of combine them and you concatenate them."}, {"start": 616.84, "end": 620.84, "text": " Pass them through the MLP and you get a novel representation here."}, {"start": 620.84, "end": 621.4, "text": " And that's it."}, {"start": 621.4, "end": 622.76, "text": " You just rinse and repeat."}, {"start": 622.76, "end": 628.12, "text": " Usually GNNs are very shallow so you won't be doing this like in CNN like 150 times like in Resonance."}, {"start": 628.12, "end": 632.36, "text": " You'll be doing this a couple of times two three times and we'll see that in this paper in particular."}, {"start": 632.36, "end": 633.72, "text": " They are only doing it two times."}, {"start": 634.6, "end": 635.16, "text": " OK."}, {"start": 635.16, "end": 638.12, "text": " So that's a high level overview of this GN block."}, {"start": 638.12, "end": 639.48, "text": " And now let's see what else."}, {"start": 640.84, "end": 646.92, "text": " So as a quick recap of GN architecture it's fairly simple."}, {"start": 646.92, "end": 648.68, "text": " Again you have a graph here."}, {"start": 648.68, "end": 653.16, "text": " I'm going to denote it as this blob and then you have an encoder block here."}, {"start": 653.16, "end": 654.12, "text": " So something like this."}, {"start": 654.12, "end": 655.24, "text": " So this is encoder."}, {"start": 655.24, "end": 667.0, "text": " Then what to do is they once you encode these raw features into a latent space you have this processor like part of the pipeline which is basically your GNN."}, {"start": 667.0, "end": 674.92, "text": " And you apply like this logic you just saw here a couple of times and then you take those latent representations which are now refined."}, {"start": 674.92, "end": 680.76, "text": " You pass them through the decoder and the decoder will finally output all of the predictions you're interested in."}, {"start": 680.76, "end": 685.72, "text": " So that's it on the high level how this GN like pipeline looks like."}, {"start": 685.72, "end": 694.12, "text": " They mentioned it also here so we compose three GN blocks into an encode process decode architecture and learn a separate model for each horizon H."}, {"start": 695.08, "end": 697.48, "text": " These blocks are defined as blah blah blah."}, {"start": 697.48, "end": 702.12, "text": " I'm going to return to this thing in a second because it's very important this horizon detail."}, {"start": 702.12, "end": 706.4399999999999, "text": " But I'm going to first kind of like explain this thing in a bit more detail."}, {"start": 706.44, "end": 711.32, "text": " So the encoder is first applied to the super segment S with the previously described raw features."}, {"start": 711.32, "end": 717.48, "text": " So those were the as we saw the speeds the time the additional like learnable embeddings."}, {"start": 717.48, "end": 718.84, "text": " Those are the raw features."}, {"start": 718.84, "end": 723.08, "text": " It produces latent representations of nodes edges and the super segment itself."}, {"start": 723.08, "end": 724.5200000000001, "text": " So that's the you components."}, {"start": 724.5200000000001, "end": 727.1600000000001, "text": " So that's the this is the super segment segment representation."}, {"start": 728.7600000000001, "end": 734.0400000000001, "text": " These latents are then passed to the processor which is applied two times with shared parameters."}, {"start": 734.04, "end": 739.48, "text": " So there is additional sharing of the parameters here to update these representations."}, {"start": 739.48, "end": 743.9599999999999, "text": " Finally these representations are transformed into appropriate predictions by applying the decoder."}, {"start": 743.9599999999999, "end": 754.68, "text": " So again this is going to output the basically both node wise as well as graph level predictions of how long does it take to traverse a segment or a super segment."}, {"start": 754.68, "end": 755.7199999999999, "text": " Those are going to be outputs."}, {"start": 755.7199999999999, "end": 757.88, "text": " We'll see soon see a bit more details there."}, {"start": 757.88, "end": 770.84, "text": " But yeah now getting back to the horizon detail it's very important because what they do is they basically for each region of the world because you obviously can't train a single system that will work everywhere."}, {"start": 770.84, "end": 775.0, "text": " What they do is like focus on some specific region like take Serbia."}, {"start": 775.0, "end": 776.28, "text": " That's my home country."}, {"start": 776.28, "end": 780.92, "text": " I'm going to take Serbia as an example and I'm going to draw something that looks like Serbia but not exactly."}, {"start": 780.92, "end": 787.56, "text": " And so this is Serbia and basically you train a single GNN for this region."}, {"start": 787.56, "end": 797.88, "text": " So for Serbia or even some like like a small smaller like part of Serbia and you additionally train a GNN model for different horizons."}, {"start": 797.88, "end": 808.4399999999999, "text": " So that means what they were using was zero minutes 10 minutes 20 minutes 30 minutes and finally 60 minutes."}, {"start": 808.4399999999999, "end": 809.7199999999999, "text": " So an hour."}, {"start": 809.7199999999999, "end": 815.0799999999999, "text": " So they're going to have one two three four five GNN for a specific region."}, {"start": 815.0799999999999, "end": 816.3599999999999, "text": " So why is that."}, {"start": 816.36, "end": 820.28, "text": " Well the reason is this is like zero GNN."}, {"start": 820.28, "end": 829.96, "text": " Let me call it that way is basically going to is basically going to predict the time it takes to traverse this particular segment right now."}, {"start": 829.96, "end": 841.5600000000001, "text": " Whereas when you input like a graph a super segment into this one is going to predict what the traversal time of that super segment is going to be or segment in 10 minutes."}, {"start": 841.56, "end": 851.4, "text": " And by analogy this one will like tell you like how long does it take to traverse a segment or a super segment in 20 minutes 30 minutes and one hour."}, {"start": 851.4, "end": 856.1999999999999, "text": " And they just figure out experimentally that that's that leads to much better performances."}, {"start": 856.1999999999999, "end": 857.64, "text": " And that's what I stick with."}, {"start": 857.64, "end": 863.7199999999999, "text": " So yeah this was Serby."}, {"start": 863.7199999999999, "end": 864.8399999999999, "text": " OK something like that."}, {"start": 864.8399999999999, "end": 866.52, "text": " Nice."}, {"start": 866.52, "end": 867.88, "text": " Let's see what else."}, {"start": 867.88, "end": 871.3199999999999, "text": " So once we have we know how the graph is structured."}, {"start": 871.32, "end": 874.2, "text": " We know how the graph neural network is structured."}, {"start": 874.2, "end": 881.08, "text": " Now let's see how the actual loss functions look like and a loss function at least the one they're using in production."}, {"start": 881.08, "end": 886.2800000000001, "text": " They also experiment and we'll see those details in a minute with some other losses here which are unsupervised."}, {"start": 886.2800000000001, "end": 889.48, "text": " So basically unsupervised and soup."}, {"start": 889.48, "end": 892.5200000000001, "text": " And so this is using production."}, {"start": 892.5200000000001, "end": 894.2800000000001, "text": " Basically there are three components."}, {"start": 894.2800000000001, "end": 898.12, "text": " One component is this SS which is basically super segment."}, {"start": 898.12, "end": 900.9200000000001, "text": " One component is this which is segment level prediction."}, {"start": 900.92, "end": 904.8399999999999, "text": " And one component is this segment but cumulative prediction."}, {"start": 904.8399999999999, "end": 906.28, "text": " We'll see what that means in a second."}, {"start": 906.28, "end": 908.52, "text": " So here is how the super segment loss is formed."}, {"start": 908.52, "end": 911.56, "text": " You iterate over different super segments."}, {"start": 911.56, "end": 917.64, "text": " You have this normalization part which I'm going to explain in a second and you have your Huber loss over here."}, {"start": 917.64, "end": 927.8, "text": " So Huber loss for those of you who are not familiar with that is very simple and it's supposed to kind of prevent certain outliers from like destabilizing the training."}, {"start": 927.8, "end": 940.04, "text": " So it looks like basically like a parabola in a certain range which is denoted by delta and minus delta here."}, {"start": 940.04, "end": 944.04, "text": " And then you basically have just a linear extrapolation here."}, {"start": 944.04, "end": 945.4799999999999, "text": " So here you have a linear function."}, {"start": 945.4799999999999, "end": 947.0799999999999, "text": " So it's not a parabola here."}, {"start": 947.0799999999999, "end": 949.0, "text": " It's not going to be like this."}, {"start": 949.0, "end": 951.88, "text": " It's going to be a simple linear function there."}, {"start": 951.88, "end": 954.1999999999999, "text": " And so the gradients remain constant."}, {"start": 954.1999999999999, "end": 955.56, "text": " They are not increasing."}, {"start": 955.56, "end": 959.88, "text": " And so this kind of stabilizes the training when you're updating the gradients."}, {"start": 959.88, "end": 970.76, "text": " If you watch my DQN video or checked out my project on GitHub about DQN, that's I think the only place I've seen Huber loss being used so far."}, {"start": 970.76, "end": 977.9599999999999, "text": " But I guess it's a neat technique to have in your toolkit whenever you want to kind of stabilize the update procedure."}, {"start": 977.9599999999999, "end": 982.92, "text": " So this 400 basically means this delta is 400."}, {"start": 982.92, "end": 996.36, "text": " And so the main part here is this means this is a prediction like a super segment level prediction at time t with horizon with the model that has a horizon H."}, {"start": 996.36, "end": 1001.7199999999999, "text": " So if we had the model, if we're training the model with the horizon zero, you can just ignore this."}, {"start": 1001.7199999999999, "end": 1004.28, "text": " So we are predicting we have the ground truth here."}, {"start": 1004.28, "end": 1005.4799999999999, "text": " So this is the GT label."}, {"start": 1005.4799999999999, "end": 1006.8399999999999, "text": " So this part is the GT."}, {"start": 1006.8399999999999, "end": 1010.28, "text": " So this is from the data set that the Google Maps team collected."}, {"start": 1010.28, "end": 1014.04, "text": " And this will be your actual prediction on a super segment level."}, {"start": 1014.04, "end": 1017.88, "text": " And so basically you just do this Huber loss over it."}, {"start": 1017.88, "end": 1019.24, "text": " And that's that's it."}, {"start": 1019.24, "end": 1024.44, "text": " So for the normalizing normalization component, I owe you an explanation there."}, {"start": 1024.44, "end": 1028.52, "text": " So this flow basically tells you the following thing."}, {"start": 1028.52, "end": 1037.8799999999999, "text": " So this flow of I is how long does it take to traverse this super segment I when there is almost no traffic on the road?"}, {"start": 1037.88, "end": 1045.8000000000002, "text": " And the kind of reasoning behind it is so imagine if you have a super long like a super segment."}, {"start": 1045.8000000000002, "end": 1055.72, "text": " And that means that these errors are probably going to be larger because there is so much more like uncertainty when you have a larger like a route."}, {"start": 1055.72, "end": 1067.0, "text": " Right. And so what you do is kind of normalize with this like zero time or basically the time it takes to traverse it when there are no cars in there, no traffic."}, {"start": 1067.0, "end": 1068.68, "text": " And so that's kind of the intuition."}, {"start": 1068.68, "end": 1073.88, "text": " So the bigger the road, you want to kind of normalize it by its this flow time."}, {"start": 1073.88, "end": 1075.16, "text": " Similarly for segments."}, {"start": 1075.16, "end": 1082.04, "text": " So you additionally just have here, as you can see, you have this iteration over the segments of the super segment."}, {"start": 1082.04, "end": 1087.4, "text": " So M this index I means the amount of segments in that super segment."}, {"start": 1087.4, "end": 1089.96, "text": " And you do the same procedure basically."}, {"start": 1089.96, "end": 1092.6, "text": " And finally, you have these cumulative segments."}, {"start": 1092.6, "end": 1096.52, "text": " So what they do is let me let me kind of jump back here."}, {"start": 1096.52, "end": 1104.2, "text": " So it will tell you if you're here right now, it's going to tell you how long did it take to get up to there."}, {"start": 1104.2, "end": 1107.08, "text": " So it won't tell you the traversal time from here to here."}, {"start": 1107.08, "end": 1111.72, "text": " It's going to tell you the cumulative time from here all the way here to here."}, {"start": 1111.72, "end": 1116.84, "text": " And then for for this one, obviously, you're just going to include this one as well and et cetera."}, {"start": 1116.84, "end": 1118.44, "text": " So that's the whole point there."}, {"start": 1118.44, "end": 1122.12, "text": " OK, I think we're pretty much done with the methods."}, {"start": 1122.12, "end": 1123.8, "text": " There is two more details."}, {"start": 1123.8, "end": 1126.12, "text": " Fairly important for the production setting."}, {"start": 1126.12, "end": 1127.7199999999998, "text": " Genehands and all that's all nice."}, {"start": 1127.7199999999998, "end": 1130.52, "text": " But like at the end, you got to make the thing work."}, {"start": 1130.52, "end": 1135.56, "text": " And what I noticed is that as they were dumping models across every single epoch,"}, {"start": 1135.56, "end": 1139.3999999999999, "text": " the predictions that came from those models were like varying a lot."}, {"start": 1139.3999999999999, "end": 1142.28, "text": " So there was like a large amount of variance there."}, {"start": 1142.28, "end": 1148.76, "text": " And so they they used basically two methods to dampen out those oscillations to kind of reduce the variance."}, {"start": 1148.76, "end": 1151.2399999999998, "text": " One is using this meta gradient method."}, {"start": 1151.2399999999998, "end": 1155.08, "text": " And the second one is using this exponential moving average method."}, {"start": 1155.08, "end": 1164.36, "text": " And this you've seen this if you watch my previous videos, like self supervised learning field uses EMA a lot to form the teacher networks, et cetera."}, {"start": 1164.36, "end": 1167.08, "text": " But basically, let me let me first quickly explain meta gradient."}, {"start": 1167.08, "end": 1169.08, "text": " I won't be digging into details here."}, {"start": 1169.08, "end": 1182.84, "text": " But like the whole idea is instead of picking a learning rate and some schedule, you basically treat learning rate as a hyperparameter itself and you jointly optimize the learning rate alongside the model parameters."}, {"start": 1182.84, "end": 1185.56, "text": " So this is what these fancy formulas are telling us."}, {"start": 1185.56, "end": 1192.9199999999998, "text": " We're basically also updating this this this is learning rate parameter using the loss function."}, {"start": 1192.9199999999998, "end": 1195.24, "text": " So this is just a generic set of meta gradient."}, {"start": 1195.24, "end": 1199.0, "text": " That's why they're using this new this Greek symbol."}, {"start": 1199.0, "end": 1204.1999999999998, "text": " But in this particular application of this paper, new is basically learning rate."}, {"start": 1204.1999999999998, "end": 1207.9599999999998, "text": " And so you are tuning those as well during the training."}, {"start": 1207.9599999999998, "end": 1211.6399999999999, "text": " And the second thing is they're using EMA, as I said."}, {"start": 1211.64, "end": 1213.16, "text": " So basically, what do you do?"}, {"start": 1213.16, "end": 1219.4, "text": " You take when you're updated, when you update the GNN, you don't just use those weights as as the new weights."}, {"start": 1219.4, "end": 1226.5200000000002, "text": " What you do is instead you take this previous weights, which is the EMA accumulative estimation of weights."}, {"start": 1226.5200000000002, "end": 1230.68, "text": " You kind of weighted with this parameter and they've used zero point nine nine here."}, {"start": 1230.68, "end": 1232.1200000000001, "text": " That's again a hyperparameter."}, {"start": 1232.1200000000001, "end": 1234.68, "text": " They just figured out that that number works well."}, {"start": 1234.68, "end": 1237.0, "text": " And these are the novel weights."}, {"start": 1237.0, "end": 1249.48, "text": " And as you can see, so this is kind of pulling these novel weights towards this stable estimate of the weights that was created through snapshots, multiple snapshots in the history, I guess."}, {"start": 1249.48, "end": 1250.44, "text": " That's pretty much it."}, {"start": 1250.44, "end": 1252.28, "text": " That's the whole method."}, {"start": 1252.28, "end": 1256.92, "text": " And now I'm going to slowly start explaining the experimental setup."}, {"start": 1256.92, "end": 1258.36, "text": " I'm going to show you the results."}, {"start": 1258.36, "end": 1264.84, "text": " And yeah, for showing you the baselines they're going to compare with, let me just quickly just mention this part."}, {"start": 1264.84, "end": 1270.9199999999998, "text": " So they mentioned that we know that November twenty twenty data may be susceptible to covid-19 traffic patterns."}, {"start": 1270.9199999999998, "end": 1279.6399999999999, "text": " And hence we attempted to select regions that minimize this deviation for evaluation in order to capture performance under regular traffic conditions."}, {"start": 1279.6399999999999, "end": 1284.28, "text": " So the thing is, obviously, because because of the covid, the traffic patterns have changed."}, {"start": 1284.28, "end": 1292.6, "text": " And so they are kind of trying to find the regions where even post covid, hopefully they'll have relevant results."}, {"start": 1292.6, "end": 1298.12, "text": " And so my question is, how do they actually find the regions that minimize this deviation?"}, {"start": 1298.12, "end": 1303.08, "text": " There are no mention they haven't mentioned this in the paper, but I'd love to know the answer."}, {"start": 1303.08, "end": 1308.52, "text": " So if somebody somehow knows that, feel free to comment down in the comment section."}, {"start": 1308.52, "end": 1312.6, "text": " OK, having said that, let me show you the baselines they are they're using."}, {"start": 1312.6, "end": 1314.9199999999998, "text": " So first baseline is super simple."}, {"start": 1314.9199999999998, "end": 1317.9599999999998, "text": " It's basically real time travel times."}, {"start": 1317.9599999999998, "end": 1319.32, "text": " So what you do is the following."}, {"start": 1319.32, "end": 1320.6, "text": " So you have a segment."}, {"start": 1320.6, "end": 1327.6399999999999, "text": " So you have one segment and I'm just going to draw it here as a square, but it basically represents this thing here."}, {"start": 1327.6399999999999, "end": 1329.6399999999999, "text": " So one of these segments."}, {"start": 1329.6399999999999, "end": 1332.4399999999998, "text": " And so what happens is the following thing."}, {"start": 1332.4399999999998, "end": 1344.1999999999998, "text": " So they have over the last like two minutes or five minutes, they have the data of what were the traversal times of the cars and vehicles in general passing through that segment."}, {"start": 1344.1999999999998, "end": 1350.52, "text": " I mean, they say here nicely summation of segment level travel times computed using segment speeds averaged over a two minute period."}, {"start": 1350.52, "end": 1353.56, "text": " So you have a two minute window prior to the time of prediction."}, {"start": 1353.56, "end": 1359.8799999999999, "text": " So basically take the data, the recent data, the last two minutes, and you use that as a as a weight as a predictor."}, {"start": 1359.8799999999999, "end": 1366.36, "text": " So what happens basically is you find that average for this segment, then you find the average for the next segment."}, {"start": 1366.36, "end": 1368.36, "text": " You find the average for the next segment."}, {"start": 1368.36, "end": 1375.16, "text": " And if this was the whole super like a super segment, the predictor would just sum up these average numbers."}, {"start": 1375.16, "end": 1384.2, "text": " Let's call this T1, T2, T3. You just basically take and sum them up to get the final value."}, {"start": 1384.2, "end": 1396.1200000000001, "text": " So T will just be basically a sum of all of these TIs where individual TIs for this particular segment, you use the last two minute data and compute it."}, {"start": 1396.1200000000001, "end": 1397.64, "text": " So it's a nonparametric model."}, {"start": 1397.64, "end": 1398.68, "text": " You don't have a neural network."}, {"start": 1398.68, "end": 1400.0400000000002, "text": " You don't have any fancy model models."}, {"start": 1400.0400000000002, "end": 1403.0, "text": " You just have nonparametric method there."}, {"start": 1403.0, "end": 1405.88, "text": " Fairly simple with historical travel times baseline."}, {"start": 1405.88, "end": 1415.08, "text": " What you do here instead of using the last two minutes, like basically you can use both the future and past information, but in the like last days."}, {"start": 1415.08, "end": 1423.4, "text": " So, for example, if this if we're trying to predict like what is going to what is the travel time of a super segment at 4 p.m."}, {"start": 1423.4, "end": 1427.16, "text": " What they're going to do is take a look at the 4 p.m."}, {"start": 1427.16, "end": 1429.48, "text": " So let me just kind of draw this as a timeline."}, {"start": 1429.48, "end": 1431.08, "text": " So 4 p.m. is here."}, {"start": 1431.08, "end": 1438.4399999999998, "text": " So they're going to take the data over the last, I don't know, like 15 minutes, maybe here and 15 minutes here."}, {"start": 1438.4399999999998, "end": 1447.6399999999999, "text": " And they're going to take a look at like what those times were like last week and the week before and etc."}, {"start": 1447.6399999999999, "end": 1451.56, "text": " And they are going to combine and average out that data over the last some weeks."}, {"start": 1451.56, "end": 1454.9199999999998, "text": " So they say here average across last 17 weeks."}, {"start": 1454.9199999999998, "end": 1458.12, "text": " So that's how you form the predictions here."}, {"start": 1458.12, "end": 1465.1599999999999, "text": " So that's so you have you use the historical data to form these TIs and then you again just sum them up to get the final T."}, {"start": 1465.1599999999999, "end": 1469.0, "text": " Finally, deep sets is like the last method."}, {"start": 1469.0, "end": 1470.84, "text": " This is a model based approach."}, {"start": 1470.84, "end": 1473.08, "text": " So this is not so this is parametric method."}, {"start": 1473.08, "end": 1476.28, "text": " And the thing is, it's ignoring the graph structure."}, {"start": 1476.28, "end": 1481.08, "text": " So if you have a super segment, what this method is going to do is the following."}, {"start": 1481.08, "end": 1482.52, "text": " Let me kind of go up there."}, {"start": 1482.52, "end": 1484.28, "text": " It's going to be easier to explain."}, {"start": 1484.28, "end": 1491.6399999999999, "text": " So this method is going to pass this through an MLP, pass this through an MLP, pass all of the segments through an MLP."}, {"start": 1491.6399999999999, "end": 1495.3999999999999, "text": " Then it's going to like kind of aggregate all of those, maybe using summation."}, {"start": 1495.3999999999999, "end": 1498.44, "text": " And then it's going to pass that final representation."}, {"start": 1498.44, "end": 1506.84, "text": " So we have a final representation here, which is formed, as I said, by aggregating all of these feature vectors of all of these segments."}, {"start": 1506.84, "end": 1511.6399999999999, "text": " And then you just pass it to another MLP here to get the final representation."}, {"start": 1511.6399999999999, "end": 1513.08, "text": " And then you can do the predictions."}, {"start": 1513.08, "end": 1516.28, "text": " So as you can see here, you're treating this as a bag of words in a way."}, {"start": 1516.28, "end": 1520.04, "text": " You're just taking all of those features, feature vectors of the segments."}, {"start": 1520.04, "end": 1524.84, "text": " You're kind of ditching the graph data, the graph information of how they're connected."}, {"start": 1524.84, "end": 1527.56, "text": " And you just kind of aggregate them and then inform the prediction."}, {"start": 1527.56, "end": 1528.9199999999998, "text": " So that's the deep set."}, {"start": 1528.9199999999998, "end": 1538.12, "text": " Having explained deep set, I realized I have not explained how the actual inference looks like once we have this this GNN model trained."}, {"start": 1538.12, "end": 1541.0, "text": " So let me explain that in a second."}, {"start": 1541.0, "end": 1543.56, "text": " Basically, this is how the serving looks like."}, {"start": 1543.56, "end": 1550.36, "text": " Once this app, once this model is running in production in your Google Map application, this is how you're actually getting the results."}, {"start": 1550.36, "end": 1553.4, "text": " So imagine you have a route from A to B."}, {"start": 1553.4, "end": 1558.84, "text": " So you have route from A to B and A and B are connected with three super segments."}, {"start": 1558.84, "end": 1560.68, "text": " So we have like something like this."}, {"start": 1560.68, "end": 1570.04, "text": " A is connected by a segment one, two, and three to the segment, to the actual destination B."}, {"start": 1570.04, "end": 1572.68, "text": " OK, so what do you do here?"}, {"start": 1572.68, "end": 1580.36, "text": " And this is going to make the reason behind using the horizon models like more clear, hopefully."}, {"start": 1580.36, "end": 1582.2, "text": " So what happens is you take."}, {"start": 1582.2, "end": 1591.1599999999999, "text": " So we are at time t and you basically take take this segment one and use the model that has the horizon equal to zero."}, {"start": 1591.1599999999999, "end": 1594.52, "text": " And you do prediction and that is going to give you t one."}, {"start": 1594.52, "end": 1597.48, "text": " So that's basically the estimated, the predicted time."}, {"start": 1597.48, "end": 1602.52, "text": " What the model is expecting, how long do you need to to kind of traverse this segment one?"}, {"start": 1602.52, "end": 1605.88, "text": " So once you have t one, let's imagine t one is 12 minutes."}, {"start": 1605.88, "end": 1609.48, "text": " So this is 12 minutes, 12 minutes."}, {"start": 1609.48, "end": 1615.56, "text": " OK, so once you have 12 minutes, then what you do is out of the pool of the horizon models."}, {"start": 1615.56, "end": 1619.72, "text": " So that means, as I said, we have the 10 minute model, the 20 minute model, the 30 minute model."}, {"start": 1619.72, "end": 1624.76, "text": " So we are because we are 12 minutes, we're going to take the models that have horizon 10."}, {"start": 1624.76, "end": 1630.2, "text": " So I'm going to denote them as horizon 10 and you're going to take the model that has horizon 20."}, {"start": 1630.2, "end": 1633.24, "text": " So that's horizon 20 like this."}, {"start": 1633.24, "end": 1637.8799999999999, "text": " And now you're going to take those models and pass the segment two through them."}, {"start": 1637.8799999999999, "end": 1643.56, "text": " So H10 is going to tell you how long does it take to traverse segment two in 10 minutes from now."}, {"start": 1643.56, "end": 1647.0, "text": " But since we have 12, we are actually expecting 12 minutes."}, {"start": 1647.0, "end": 1649.56, "text": " That means we're going to do basic interpolation here."}, {"start": 1649.56, "end": 1656.6, "text": " So this one is going to tell us the result. Let me call it t two at 20."}, {"start": 1656.6, "end": 1659.1599999999999, "text": " And this will be t two."}, {"start": 1659.1599999999999, "end": 1665.6399999999999, "text": " So that's the second time it takes to traverse the second segment according to this model 10."}, {"start": 1665.6399999999999, "end": 1674.52, "text": " And you're going to combine this two informations, simple interpolation to form the actual time it takes to traverse the data."}, {"start": 1674.52, "end": 1677.1599999999999, "text": " So it's going to be somewhere between these two numbers."}, {"start": 1677.1599999999999, "end": 1677.48, "text": " Right."}, {"start": 1677.48, "end": 1682.28, "text": " And so once you have the t two, you can use the t two and t one."}, {"start": 1682.28, "end": 1690.6, "text": " You can add them up and then do the same procedure for segment super segment three and rinse and repeat until you get to the end point B."}, {"start": 1690.6, "end": 1694.84, "text": " So, yeah, hopefully that's now it's clear how you're using this model in inference."}, {"start": 1694.84, "end": 1697.72, "text": " Now, let me get back to the where we stopped."}, {"start": 1697.72, "end": 1700.68, "text": " So I explained the deep sets. That's the third baseline."}, {"start": 1700.68, "end": 1704.04, "text": " Now, let's see the actual results here."}, {"start": 1704.04, "end": 1712.12, "text": " By the way, they're using this RMS metric to to kind of compare the baselines."}, {"start": 1712.12, "end": 1713.8799999999999, "text": " And you can see here it's very simple."}, {"start": 1713.8799999999999, "end": 1716.68, "text": " You basically take the super segment level predictions."}, {"start": 1716.68, "end": 1722.04, "text": " You do the summation over the super segments and you do a square and you average here."}, {"start": 1722.04, "end": 1724.2, "text": " Yeah, basically root mean squared error."}, {"start": 1724.2, "end": 1726.84, "text": " It's pretty pretty self-explanatory."}, {"start": 1726.84, "end": 1728.76, "text": " And so here are the results."}, {"start": 1728.76, "end": 1733.56, "text": " You can see the real time baseline, the historical, the deep sets baseline and the GM baseline."}, {"start": 1733.56, "end": 1739.24, "text": " And you can see that it's they also show it's a significant statistically significant result."}, {"start": 1739.24, "end": 1744.6, "text": " And it's lower compared to all of the other baselines, which is cool."}, {"start": 1744.6, "end": 1750.12, "text": " So the thing that initially kind of bugged me here is that if you take a look at the numbers,"}, {"start": 1750.12, "end": 1755.6399999999999, "text": " the differences are fairly trivial, like small compared to the other baselines."}, {"start": 1755.6399999999999, "end": 1758.28, "text": " So deep set seems to be performing really well."}, {"start": 1758.28, "end": 1761.8799999999999, "text": " So why the whole hustle? Like why why are we using the graph data?"}, {"start": 1761.88, "end": 1763.64, "text": " And I'm going to get to that in a second."}, {"start": 1763.64, "end": 1768.92, "text": " But like, let's see here, if we compare these numbers, like take this number,"}, {"start": 1768.92, "end": 1773.0, "text": " you can see it's way worse compared to these two models."}, {"start": 1773.0, "end": 1774.68, "text": " So these two are out of the question."}, {"start": 1774.68, "end": 1776.7600000000002, "text": " That's obviously like clear."}, {"start": 1776.7600000000002, "end": 1780.44, "text": " But like between deep sets and GM, what should we use?"}, {"start": 1780.44, "end": 1783.5600000000002, "text": " And I mean, it's a bit better, but is it like worth it?"}, {"start": 1783.5600000000002, "end": 1788.8400000000001, "text": " And the thing is one important note here dimension is so one note is that these"}, {"start": 1788.84, "end": 1791.9599999999998, "text": " improvements are computed over individual super segments,"}, {"start": 1791.9599999999998, "end": 1794.52, "text": " and they will accumulate over entire routes."}, {"start": 1794.52, "end": 1798.76, "text": " Hence, our improvements may quickly become more important on a whole route level."}, {"start": 1798.76, "end": 1801.8799999999999, "text": " So a super segment may be and I think they have a data somewhere here."}, {"start": 1801.8799999999999, "end": 1802.52, "text": " Let me find it."}, {"start": 1805.08, "end": 1805.8, "text": " Where it is."}, {"start": 1805.8, "end": 1808.04, "text": " Okay, here it is data set statistics."}, {"start": 1808.04, "end": 1813.32, "text": " So you can see that the super segment length is so average segment length is around like"}, {"start": 1813.32, "end": 1819.32, "text": " 100 meters and super segments are around so average number of segments per super segment"}, {"start": 1819.32, "end": 1820.12, "text": " is around 20."}, {"start": 1820.12, "end": 1823.96, "text": " So that means probably average super segment has around two kilometers."}, {"start": 1823.96, "end": 1827.96, "text": " So once you accumulate that over like 10 kilometers, when you have multiple super"}, {"start": 1827.96, "end": 1834.52, "text": " segments, then obviously the errors accumulate and GM start bringing more and more advantage"}, {"start": 1834.52, "end": 1836.9199999999998, "text": " compared to these other baselines."}, {"start": 1836.9199999999998, "end": 1841.08, "text": " And I mean, obviously, Google would not put this into production if it wasn't meaningful"}, {"start": 1841.08, "end": 1841.32, "text": " enough."}, {"start": 1841.32, "end": 1843.8799999999999, "text": " So yeah, but just don't get confused by the small differences."}, {"start": 1843.8799999999999, "end": 1845.08, "text": " Now, hopefully, it's clear enough."}, {"start": 1845.08, "end": 1846.6799999999998, "text": " And let's see the ablations."}, {"start": 1846.6799999999998, "end": 1851.56, "text": " So one thing I have not mentioned is they've experimented with various things."}, {"start": 1851.56, "end": 1853.8, "text": " I did mention the unsupervised loss."}, {"start": 1853.8, "end": 1858.6799999999998, "text": " So they tried using stuff like deep graph info max."}, {"start": 1858.6799999999998, "end": 1863.48, "text": " They've also experimented with these combinations of aggregators and like not using just the"}, {"start": 1864.2, "end": 1867.8799999999999, "text": " some aggregator but using some other types of aggregations."}, {"start": 1867.88, "end": 1871.8000000000002, "text": " And all of the ideas come from this principal neighborhood aggregation paper."}, {"start": 1872.44, "end": 1873.24, "text": " You can check it out."}, {"start": 1873.24, "end": 1879.16, "text": " Yeah, just keep in mind that they've experimented with lots of things and they eventually"}, {"start": 1879.16, "end": 1883.96, "text": " decided not to use many of those ideas in the production because the trade off was not"}, {"start": 1883.96, "end": 1884.5200000000002, "text": " acceptable."}, {"start": 1884.5200000000002, "end": 1889.72, "text": " So even though they brought some performance benefits, the cost of kind of serving those"}, {"start": 1889.72, "end": 1892.8400000000001, "text": " more like complex models is way higher."}, {"start": 1892.84, "end": 1898.84, "text": " So, okay, let's kind of skim over these ablations."}, {"start": 1898.84, "end": 1900.9199999999998, "text": " I mentioned those embedding vectors."}, {"start": 1900.9199999999998, "end": 1907.24, "text": " So aside from the domain knowledge that was ingrained by those speeds and times in the"}, {"start": 1907.24, "end": 1910.12, "text": " feature vectors, we had the learnable portion."}, {"start": 1910.12, "end": 1916.12, "text": " And you can see that actually using like both embeddings, both the segment level embeddings"}, {"start": 1916.12, "end": 1919.08, "text": " as well as the super segment embeddings brings better results."}, {"start": 1919.08, "end": 1923.0, "text": " Don't get confused by this column like these acronyms."}, {"start": 1923.0, "end": 1927.08, "text": " This stands for New York City, I guess, LA, Tokyo and Singapore."}, {"start": 1927.08, "end": 1930.36, "text": " They had to kind of obviously pick a subset of the cities."}, {"start": 1930.36, "end": 1932.76, "text": " They can't evaluate this on the whole on a global scale."}, {"start": 1933.48, "end": 1936.36, "text": " And you can see results are always better when you're using the embeddings."}, {"start": 1936.36, "end": 1937.3999999999999, "text": " That's that's kind of clear."}, {"start": 1938.12, "end": 1945.3999999999999, "text": " Second thing here is they showed how the meta gradient and EMA are reducing the variants"}, {"start": 1945.3999999999999, "end": 1946.6799999999998, "text": " in the during the training."}, {"start": 1946.68, "end": 1952.44, "text": " So we can see on the x axis here, basically training iterations on the y axis, we see"}, {"start": 1952.44, "end": 1954.6000000000001, "text": " the RMS metric."}, {"start": 1954.6000000000001, "end": 1960.3600000000001, "text": " And we can see that when we're just using Adam with no EMA and no meta gradients, you"}, {"start": 1960.3600000000001, "end": 1964.2, "text": " can see that just the red curve is kind of getting crazy here."}, {"start": 1964.2, "end": 1969.8, "text": " And once you start adding EMA and meta gradients, they show that the blue curves are using both"}, {"start": 1969.8, "end": 1972.6000000000001, "text": " of these is the best thing to do."}, {"start": 1972.6, "end": 1976.84, "text": " And they show that not only for they'll just show for it for Tokyo and they show it also"}, {"start": 1976.84, "end": 1978.12, "text": " for for LA here."}, {"start": 1978.12, "end": 1979.56, "text": " And I just made a note here."}, {"start": 1979.56, "end": 1984.04, "text": " So basically, it'd be interesting to see how learning rate evolves over the duration of"}, {"start": 1984.04, "end": 1984.6, "text": " the training."}, {"start": 1985.24, "end": 1990.1999999999998, "text": " So that means I'd love to see the like how the meta gradient is tuning the learning rate."}, {"start": 1990.1999999999998, "end": 1992.28, "text": " Can we see some interesting patterns there?"}, {"start": 1992.28, "end": 1996.6, "text": " Like those types of visualizations in the appendix would be super appreciated."}, {"start": 1996.6, "end": 2001.3999999999999, "text": " And secondly, be interesting to understand which other schedules did they try with Adam"}, {"start": 2001.4, "end": 2003.96, "text": " before deciding to go with meta gradients."}, {"start": 2003.96, "end": 2006.2800000000002, "text": " Let's wrap up the ablation studies."}, {"start": 2006.2800000000002, "end": 2013.16, "text": " They experimented with these extended super segments and extended super segments plus"}, {"start": 2013.16, "end": 2021.24, "text": " extra features, whereby they were using additional segments, he can see extended super segments,"}, {"start": 2021.24, "end": 2025.72, "text": " but they were still predicting only the like traversal times for the segments in our original"}, {"start": 2025.72, "end": 2026.76, "text": " super segment."}, {"start": 2026.76, "end": 2032.84, "text": " And they basically showed that all of that kind of helps, but like it's very, very expensive,"}, {"start": 2032.84, "end": 2035.24, "text": " both memory wise and I guess inference wise."}, {"start": 2035.24, "end": 2037.64, "text": " And so they decided not to use this in the production setting."}, {"start": 2038.84, "end": 2041.64, "text": " Here you can see the unsupervised loss I mentioned."}, {"start": 2041.64, "end": 2043.72, "text": " So this is the deep graph informax paper."}, {"start": 2044.52, "end": 2048.12, "text": " This is the I guess, or encoder."}, {"start": 2048.12, "end": 2050.6, "text": " So graph or encoder, I guess, paper."}, {"start": 2050.6, "end": 2056.04, "text": " And so you can see that those two are, again, improving results across various cities and"}, {"start": 2056.04, "end": 2057.0, "text": " various horizons."}, {"start": 2057.72, "end": 2061.64, "text": " So both for New York City, LA, et cetera, for different horizons."}, {"start": 2061.64, "end": 2066.7599999999998, "text": " But the trick here is, and this is an excerpt from this paper."}, {"start": 2066.7599999999998, "end": 2072.2, "text": " So the optimal variant and hyperparameters were different for each region and prediction"}, {"start": 2072.2, "end": 2072.92, "text": " horizon."}, {"start": 2072.92, "end": 2078.2799999999997, "text": " Thus, it is likely expensive to tune such losses for all existing regions and each horizon."}, {"start": 2078.2799999999997, "end": 2082.44, "text": " So as I said, you're going to be using various different GNNs depending on region."}, {"start": 2082.44, "end": 2087.96, "text": " So if you have additionally have to tune these kind of hyperparameters, it's going to be"}, {"start": 2087.96, "end": 2089.8, "text": " hard and expensive."}, {"start": 2089.8, "end": 2092.68, "text": " And so they decided not to use them in the actual production setting."}, {"start": 2093.8, "end": 2097.0, "text": " Finally, let's see this, these results."}, {"start": 2097.0, "end": 2105.16, "text": " So using various different aggregation functions like the sum is the actual, the one that's"}, {"start": 2105.16, "end": 2111.56, "text": " using production, but they also try the square root, the mean, the max and all of them combined."}, {"start": 2111.56, "end": 2116.2799999999997, "text": " And as you can see, usually this all of them combined, like gives you additional performance."}, {"start": 2116.2799999999997, "end": 2120.2799999999997, "text": " But again, you have to once you're in a production setting, this is engineering, you have to"}, {"start": 2120.2799999999997, "end": 2121.16, "text": " trade off the costs."}, {"start": 2121.16, "end": 2123.16, "text": " And so they stick with the sum function."}, {"start": 2123.16, "end": 2127.4, "text": " They also did this online evaluation of GN compared to the baselines and they showed"}, {"start": 2127.4, "end": 2130.44, "text": " it's again better, same as in the offline setting we just saw."}, {"start": 2131.0, "end": 2136.12, "text": " So a couple of things that bug me there is, so they mentioned that computed over all tracks"}, {"start": 2136.12, "end": 2140.36, "text": " within a week, specifically January 15th through January 22nd."}, {"start": 2140.36, "end": 2143.6400000000003, "text": " What is not clear to me is what it means over all tracks."}, {"start": 2143.6400000000003, "end": 2150.52, "text": " So do they actually average the results across every single region they are covering or what?"}, {"start": 2150.52, "end": 2152.84, "text": " So this part kind of bugs me."}, {"start": 2152.84, "end": 2154.1200000000003, "text": " So yeah, not sure about it."}, {"start": 2155.2400000000002, "end": 2161.1600000000003, "text": " And again, I said the results are nice, but like basically we don't have a gut feeling"}, {"start": 2161.1600000000003, "end": 2163.6400000000003, "text": " for what these small improvements mean."}, {"start": 2163.6400000000003, "end": 2169.48, "text": " And so A, it'd be nice to have like something like, hey, when you're using this model, it's"}, {"start": 2169.48, "end": 2173.2400000000002, "text": " going to save you up that many seconds or minutes compared to this baseline."}, {"start": 2173.2400000000002, "end": 2174.6, "text": " So that would be much more intuitive."}, {"start": 2175.08, "end": 2178.04, "text": " We'd have a much better intuitive understanding of what's going on here."}, {"start": 2178.04, "end": 2184.44, "text": " Secondly, and I noted it here, basically some type of geographical heat maps where we see,"}, {"start": 2184.44, "end": 2189.64, "text": " depending on the region, like what the performance differences are, that'd be super nice"}, {"start": 2189.64, "end": 2191.0, "text": " visualization, I guess."}, {"start": 2191.0, "end": 2197.64, "text": " Finally, they did the last evaluation on this particular route in LA, I think, and they"}, {"start": 2197.64, "end": 2200.6, "text": " show certain results and I have a same remark here."}, {"start": 2200.6, "end": 2204.2, "text": " It's not intuitive what these curves mean."}, {"start": 2204.2, "end": 2209.7999999999997, "text": " Like, I mean, you can see that the GN, so this graph neural network model is way better."}, {"start": 2211.16, "end": 2215.3199999999997, "text": " It's better compared to real time baseline, but I don't have a gut feeling for what this"}, {"start": 2215.3199999999997, "end": 2215.8799999999997, "text": " means."}, {"start": 2215.8799999999997, "end": 2217.4, "text": " And so yeah, that kind of sucks."}, {"start": 2217.4, "end": 2220.68, "text": " And also they don't have any units here."}, {"start": 2221.48, "end": 2225.16, "text": " And so I guess it's seconds, but it's kind of not clear enough."}, {"start": 2225.16, "end": 2231.8799999999997, "text": " And so they here also show for the, when we have results for the horizon, like one hour"}, {"start": 2231.8799999999997, "end": 2236.7599999999998, "text": " from now, you can see that this GN that was trained with that horizon is way better compared"}, {"start": 2236.7599999999998, "end": 2239.64, "text": " to the GN that was trained with the horizon equals to zero."}, {"start": 2239.64, "end": 2246.12, "text": " So that's kind of argument behind why do we need all of these multiple horizon GNM models"}, {"start": 2246.12, "end": 2250.44, "text": " and we're combining them to actually serve the results, the end results."}, {"start": 2250.44, "end": 2255.16, "text": " I'm going to end it up here and I'm going to just briefly mention that this is a thing"}, {"start": 2255.16, "end": 2259.0, "text": " that's running in production, which means that research was only a small portion of"}, {"start": 2259.0, "end": 2262.52, "text": " this whole project and there were many engineering challenges they had to solve."}, {"start": 2262.52, "end": 2265.96, "text": " So one of them was, so they had to obviously cache results."}, {"start": 2265.96, "end": 2271.32, "text": " So as they say here, the path in an ETA request usually includes multiple super segments and"}, {"start": 2271.32, "end": 2276.36, "text": " making predictions for these super segments on the fly is not practical nor scalable."}, {"start": 2276.36, "end": 2282.6800000000003, "text": " So they had to kind of cache the results and then periodically refresh all of the cache."}, {"start": 2283.7200000000003, "end": 2285.4, "text": " So that's one of the engineering details."}, {"start": 2285.4, "end": 2289.48, "text": " The second thing they mentioned here, for less frequently visited road segments,"}, {"start": 2289.48, "end": 2291.6400000000003, "text": " we use simpler per segment models."}, {"start": 2291.6400000000003, "end": 2294.6800000000003, "text": " So they drop to simpler baselines in certain regions."}, {"start": 2294.6800000000003, "end": 2295.96, "text": " So it's a complex system."}, {"start": 2295.96, "end": 2297.08, "text": " There are many components."}, {"start": 2297.08, "end": 2301.8, "text": " So the meta-gradient, the EMA, the graph neural networks, all of this engineering"}, {"start": 2301.8, "end": 2306.6000000000004, "text": " tricks to make this work and I think it's a very impactful project."}, {"start": 2306.6000000000004, "end": 2308.28, "text": " I mean, I use Google Maps all the time."}, {"start": 2308.28, "end": 2309.88, "text": " So I really love this paper."}, {"start": 2309.88, "end": 2315.8, "text": " I think it's a clearly written paper aside from a couple of these remarks and maybe the"}, {"start": 2315.8, "end": 2317.6400000000003, "text": " lack of appendix section."}, {"start": 2317.6400000000003, "end": 2318.76, "text": " Hopefully like this video."}, {"start": 2318.76, "end": 2323.0, "text": " If you did share it out with a friend, subscribe to this channel, hit the bell icon."}, {"start": 2323.0, "end": 2324.76, "text": " Also join the Discord community."}, {"start": 2324.76, "end": 2326.6000000000004, "text": " There is a lot of engagement happening there."}, {"start": 2327.2400000000002, "end": 2330.6800000000003, "text": " Cool people interested in ML helping each other out."}, {"start": 2330.68, "end": 2345.24, "text": " So yeah, do check it out and until next time, bye-bye."}]