Uber DeepETA

01 · CONTEXT AND CHALLENGES

Why Uber swapped trees for deep learning

At Uber, estimated time of arrival (ETA) feeds central decisions. The blog cites fare calculation, pickup time estimation, matching riders and drivers, and delivery planning.

A traditional routing engine splits the road network into segments represented by weighted edges, applies shortest-path algorithms, and sums the weights to arrive at the ETA. The authors remind us that the map is not the territory: the road graph is just a model.

For several years, Uber used gradient-boosted decision tree ensembles to refine these predictions. The model and the training set grew with each version, until, in the authors' words, scaling up data and model with XGBoost became unsustainable. The alternative explored was deep learning, for its relative ease of scaling to large datasets with data-parallel SGD.

To justify the switch, the team had to overcome three challenges. Latency: the model must return the ETA in a few milliseconds at most. Accuracy: the mean absolute error (MAE) must improve substantially over the incumbent XGBoost. Generality: global predictions for all lines of business, such as mobility and delivery.

02 · PHYSICS PLUS LEARNING

The model corrects the routing engine

The central idea is hybrid. The physical model is the routing engine, which uses map data and real-time traffic measurements to predict the ETA as the sum of segment traversal times along the best path. On top of it, machine learning predicts the residual between the engine's ETA and the real observed outcome. The blog calls this approach ETA post-processing, and DeepETA is an example.

In practice, it is easier to incorporate new data sources and keep up with fast-changing business requirements by updating the post-processing model than by refactoring the routing engine. The model receives spatial and temporal features, such as origin, destination, and request time, plus real-time traffic information and the nature of the request.

This model has Uber's highest QPS and must be fast so as not to add latency to the ETA request.

1. Consumer requests reach uRoute through several intermediate services.

2. uRoute queries the routing engine, which produces routes and the base ETA.

3. With that ETA and other features, uRoute calls Michelangelo's online prediction, where DeepETA runs.

Note that the routing engine stays in the path: the learning model predicts the residual on top of its ETA, and uRoute uses that ETA as input to the prediction call.

03 · HOW IT BECAME ACCURATE

Self-attention over features and embeddings

The team tested and tuned seven neural network architectures: MLP, NODE, TabNet, sparsely gated mixture-of-experts, HyperNetworks, Transformer, and Linear Transformer. The one that gave the best accuracy was an encoder-decoder with self-attention. The authors also report that discretizing and embedding all inputs gave a significant gain over the alternatives.

In a language model, each vector is a word. In DeepETA, each vector is a feature, such as the trip origin or the time of day. Self-attention computes the pairwise interactions among the K features through a K*K attention matrix of dot products. There is no positional encoding, because the order of the features does not matter.

All categorical features become embeddings, and continuous ones are discretized into buckets before becoming embeddings. Counterintuitively, discretizing gave more accuracy than using the continuous value directly, and quantile buckets outperformed equal-width buckets.

Origin and destination arrive as latitude and longitude and get special treatment: locations are quantized into grids at multiple resolutions. The authors explored three strategies for mapping grid cells to embeddings.

According to the authors, the accuracy loss of simple hashing probably comes from hash collisions that lose information. The multiple hashing result suggests the network can combine the information from several independent buckets to undo the effect of collisions in a single bucket.

04 · HOW IT BECAME FAST

Linear transformer and many embeddings

The transformer encoder gave the best accuracy, but was too slow to serve online in real time. Original self-attention has quadratic complexity. Research exists that linearizes this computation, and after experimenting the team chose the linear transformer, which uses the kernel trick to avoid computing the attention matrix.

In the blog's example, with K equal to 40 features of dimension d equal to 8, the result is the one in the table, and the linear transformer is faster whenever K is greater than d.

Another speed factor is sparsity. The model has hundreds of millions of parameters, but each prediction touches only a tiny fraction of them, about 0.25%. The model is relatively shallow, with few layers, and most of the parameters are in embedding tables. By discretizing the inputs, the system avoids evaluating the embedding parameters that are not used.

To map latitude and longitude to an embedding, DeepETA quantizes the coordinates and does a hash lookup in O(1) time. The authors compare this with trees, which would require O(log N), and with fully connected layers, which would require O(N²). It is the old space-time trade-off: by precomputing partial answers in large embedding tables learned during training, computation at serving time is reduced.

05 · HOW IT BECAME GENERAL

Per-segment bias adjustment and asymmetric Huber loss

After learning the representations, the decoder is a fully connected network with a per-segment bias adjustment layer. The distribution of absolute error varies widely between deliveries and rides, long and short trips, pickup and drop-off, and global mega-regions. Adjusting the raw prediction per segment absorbs this variation and improves MAE, and works better than just adding segment features.

The authors chose the bias layer over a multitask decoder because of latency constraints. They also use ReLU at the output to force the predicted ETA to be positive and clamping to reduce the effect of extreme values.

Different use cases call for different point estimates. For fare calculation, the team wants a mean ETA but needs to control the effect of outliers. Other cases call for a specific quantile of the distribution. That is why DeepETA uses a parameterized loss function, the asymmetric Huber, which is robust to outliers and able to produce several common point estimates.

Two parameters control the behavior. Delta interpolates smoothly between squared error and absolute error, the latter less sensitive to outliers. Omega controls the relative cost of underestimating versus overestimating, useful when arriving a minute late is worse than arriving a minute early.

06 · TRAINING, SERVING, AND EVOLUTION

From Michelangelo to uRoute

The team used the Canvas framework from Uber's ML platform, Michelangelo, to train and deploy the model. Once deployed, the predictions must be served in real time. For model updates, the blog describes periodic automatic retraining and validation flows.

1. The model is trained with Michelangelo's Canvas framework on the training set.

2. Once trained and deployed, the model starts serving predictions in real time.

3. Periodic automatic retraining and validation flows are configured on the model.

On the serving side, uRoute acts as the frontend for route queries, requests routes and ETAs from the routing engine, and, with that ETA and other features, calls Michelangelo's online prediction service to get the DeepETA prediction.

DeepETA was launched in production for global ETA prediction for four-wheel vehicles (4-wheel, in the blog). According to the authors, the launch makes it possible and efficient to train and serve large-scale deep learning models that predict ETAs better than XGBoost-based approaches, and establishes a reusable model foundation for several consumption use cases.

Among next steps, the team cites exploring continuous and incremental training, which would allow training the ETAs on more recent data.