Uber 是如何使用深度學習預計到達時間的？

語言: CN / TW / HK

時間 2022-05-06 17:08:54 InfoQ

在 Uber，令人驚歎的客戶體驗依賴於準確的預計到達時間（ETA）。我們利用 ETA 來計算票價，估計接載時間，為乘客和司機牽線搭橋，安排送貨，等等。傳統的路由引擎計算是通過將道路網路劃分為若干個小的路段（由圖中的加權邊表示）來計算 ETA。它們利用最短路徑演算法來尋找通過該圖的最佳路徑，然後將權重相加計算出來 ETA。但是大家都清楚，地圖並非地形：道路圖僅僅是一個模型，並不能很好地反映出地表的狀況。另外，我們也不知道具體的乘客和司機將會選擇哪條路線到達目的地。基於道路圖預測，對機器學習模型進行了訓練，並將歷史資料和實時訊號結合起來，對 ETA 進行了完善，使其能夠更好地預測真實世界的結果。

在過去的數年中，Uber 利用梯度提升決策樹對 ETA 的預測進行了改進。ETA 模型及其訓練資料隨著每個版本的釋出而穩步增長。為了跟上這個增長的步伐，Uber 的 Apache Spark™ 團隊對 XGBoost 進行了上游改進，使模型不斷深入發展，成為當時世界上最大、最深的 XGBoost 組合之一。最終，我們達到了一個點，即使用 XGBoost 增加資料集和模型的大小變得難以維持。為了繼續擴大模型的規模並提高準確性，我們決定深入研究深度學習，因為使用數據並行的 SGD 相對容易擴充套件到大資料集。為了證明轉向深度學習的合理性，我們需要克服三個主要挑戰：

延遲性：該模型必須在最多幾毫秒內返回 ETA。
準確性：平均絕對誤差（MAE）必須比現有的 XGBoost 模型有明顯改善。
通用性：該模型必須在全球範圍內提供 ETA 預測，包括 Uber 的所有業務線，如移動和交付。為了應對這些挑戰，Uber AI 與 Uber 的地圖團隊合作開展了一個名為 DeepETA 的專案，為全球 ETA 預測開發一種低延遲的深度神經網路架構。在這篇博文中，我們將帶領大家瞭解一些幫助 DeepETA 成為 Uber 新的生產 ETA 模型的經驗和設計選擇。

問題陳述

近年來，人們對世界的物理模型與深度學習相結合的系統產生了濃厚的興趣。我們在 Uber 也採取了類似的方法來預測 ETA。我們的物理模型是一個路由引擎，它使用地圖資料和實時交通測量來預測 ETA，作為兩點之間最佳路徑的分段遍歷時間的總和。然後，我們利用機器學習來預測路由引擎 ETA 和現實世界觀測結果之間的殘差。我們稱這種混合方法為 ETA 後處理，而 DeepETA 是後處理模型的一個例子。從實用的角度來看，通過更新後處理模型來吸納新的資料來源，並適應快速變化的業務需求，通常比重構路由引擎本身更容易。

圖 1：基於機器學習模型的 ETA 後處理混合方法

為了能夠預測 ETA 殘差，一個後處理的機器學習模型考慮到了空間和時間特徵，例如請求的出發地、目的地和時間，以及實時交通訊息和請求的性質，例如是上門送貨還是搭車接人，如圖 1 所示。這個後處理模型是 Uber 最高的 QPS（queries per second，每秒查詢次數）模型。這個模型需要快速，以免給 ETA 請求增加太多的延遲，而且它們需要提高 ETA 的準確性，這是由不同段資料的平均絕對誤差（mean absolute error，MAE）衡量的。

我們如何使它準確？

DeepETA 團隊對 7 種不同的神經網路架構進行了測試，並對其進行了優化： MLP 、 NODE 、 TabNet 、 Sparsely Gated Mixture-of-Experts 、 HyperNetworks 、 Transformer 和 Linear Transformer 。我們發現，具有自注意力的編碼器-解碼器架構能夠提供最好的準確性。圖 2 顯示了我們所設計的高階架構。此外，我們測試了不同的特徵編碼，結果表明，將所有的輸入離散化並嵌入到模型中，其效果明顯要好於替代方案。

圖 2：DeepETA 模型管道概述

具有自注意力的編碼器

由於 Transformer 在自然語言處理和計算機視覺中的應用，許多人對其體系結構很熟悉，但是 Transformer 在諸如 ETA 預測這樣的表格資料問題上的應用並不是很清楚。Transformer 的決定性創新是自注意力機制。自注意力是一個序列到序列的運算，它接收一個向量序列併產生一個重新加權的向量序列。詳情可參閱 Transformer 論文。

在語言模型中，每個向量代表一個單詞標記，而在 DeepETA 中，每個向量代表一個特徵，如行程的起點或者一天中的時間。自注意力通過明確計算成對點積的 K*K 注意力矩陣，再利用這些縮放點積的 softmax 對特徵進行重新加權，從而發現表格資料集中的 K 個特徵之間的成對互動關係。當自注意力層處理每個特徵時，它檢視輸入中的每一個其他特徵的線索，並將這個特徵的表示輸出為所有特徵的加權和。這個過程如圖 3 所示。通過這種方式，我們可以將對所有時間和空間特徵的理解烘托到當前正在處理的一個特徵中，並將注意力集中在重要的特徵上。與語言模型相比，由於特徵的順序並不重要，所以 DeepETA 不存在位置編碼。

圖 3：自注意力的注意力矩陣

以一次從出發地 A 到目的地 B 的行程為例，自注意力層根據一天中的時間、出發地和目的地、交通狀況等因素來衡量特徵的重要性。圖 4 顯示了自注意力的視覺化（由 Tensor2Tensor 生成），8 種顏色對應於 8 個注意力頭，所佔份額對應於隨機生成的注意力權重。

圖 4：輸入特徵的成對點積的說明：顏色對應於注意力頭，顏色份額對應於隨機生成的注意力權重。

特徵編碼

連續和分類的特徵

DeepETA 模型嵌入了所有的分類特徵，並在嵌入之前對所有的連續特徵進行了桶化。有點反直覺的是，連續特徵的桶化導致了比直接使用連續特徵更好的準確性。雖然桶化並不是嚴格必要的，因為神經網路可以學習任何非線性的不連續函式，但具有桶化特徵的網路可能有一個優勢，因為無需花費任何引數運算，就可以學會如何劃分輸入空間。就像梯度增強決策樹神經網路的論文一樣，我們發現使用分位桶比等寬桶具有更高的準確性。我們認為，分位桶之所以能夠表現很好，是因為它們將熵最大化：對於任何固定數量的桶，分位桶傳遞的關於原始特徵的資訊都比任何其他的桶要多（以位元為單位）。

地理空間嵌入

後處理模型以緯度和經度的形式接收行程的起點和終點。因為這些起點和終點對於預測 ETA 非常重要，DeepETA 對它們的編碼與其他連續特徵不同。位置資料在全球範圍內的分佈非常不均勻，並且包含多種空間解析度的資訊。因此，我們將地點分位為基於經緯度的多個解析度網格。隨著解析度的提高，不同網格單元的數量呈指數級增長，而每個網格單元的平均資料量則成比例減少。我們探索了三種不同的策略來將這些網格對映到嵌入中：

精確索引，它將每個網格單元對映到一個專門的嵌入。這佔用了最多的空間。
特徵雜湊，它使用雜湊函式將每個網格單元對映到一個緊湊的倉位範圍。緩衝區的數量比精確索引要小得多。
多重特徵雜湊，通過使用獨立的雜湊函式將每個網格單元對映到多個緊湊的 bin 範圍，從而擴充套件了特徵雜湊。見圖 5：

圖 5：利用獨立雜湊函式 H1 和 H2 進行多要素雜湊的多解析度位置格網的圖示

實驗結果顯示，儘管與精確索引相比，特徵雜湊節省了空間，但是由於網格的解析度不同，其準確度也會有一定的差別。這可能是因為雜湊碰撞導致一些資訊丟失。與精確索引相比，多特徵雜湊提供了最好的準確性和延遲，同時仍然節省了空間。這意味著網路能夠結合來自多個獨立雜湊桶的資訊，以消除單桶碰撞的負面影響。

我們是如何讓它變得快速的

DeepETA 對服務延遲的要求十分苛刻。儘管可以利用專用的硬體或者經過訓練的優化來加快推理速度，但在本節中，我們將會介紹如何幫助 DeepETA 最小化延遲的架構設計決策。

快速 Transformer

儘管基於 Transformer 的編碼器可以達到最好的準確性，但是對於線上實時服務的延遲要求來說，它的速度還是太慢了。原始的自注意力模型具有二次複雜度，因為它從 K 個輸入計算出 K 個注意矩陣。已經有多個研究工作將自注意力計算線性化，例如線性 Transformer 、 Linformer 、 Performer 。通過實驗，我們選擇了線性 Transformer，它使用核心技巧來避免計算注意力矩陣。

為了說明時間複雜度，我們用下面的例子來說明：假設我們有 K 個維度為 d 的輸入，原始 Transformer 的時間複雜度為 :

而線性 Transformer 的時間複雜度為

如果我們有 40 個特徵都有 8 個維度，即

而

很明顯，只要 :

線性 Transformer 就會更快。

我們是如何做到通用的

DeepETA 的設計目標之一是提供一個通用的 ETA 模型，為 Uber 在全球的所有業務線服務。由於不同業務線的需求和資料分佈情況不同，因此這將成為一項具有挑戰性的工作。整體模型結構如下圖 6 所示。

圖 6：DeepETA 模型結構圖解

偏置調整解碼器

一旦我們學會了有意義的特徵表徵，下一步就是對它們進行解碼並進行預測。在我們的案例中，解碼器是一種全連線神經網路，它具有分段偏置調整層。絕對誤差的分佈在送貨行程與乘車行程、長行程與短行程、上客行程與下客行程之間有很大的不同，在全球大區域之間也是如此。新增偏差調整層來調整每個不同細分市場的原始預測，可以考慮到它們的自然變化，反過來提高 MAE。這種方法比簡單地在模型中新增分段特徵表現得更好。我們之所以實施偏見調整層而非多工解碼器，是因為延時的限制。我們還運用了一些技巧，例如在輸出端使用 ReLU 來強制預測 ETA 為正，並通過鉗制來降低極端值的影響，從而進一步提高預測的準確性。

非對稱 Huber 損失

不同的業務用例需要不同型別的 ETA 點估計，並且在其資料中也會有不同比例的離群值。例如，我們想估計一個用於計算票價的平均 ETA，但需要控制離群值的影響。其他用例可能需要 ETA 分佈的特定分位數。為了適應這種多樣性，DeepETA 使用了一個引數化的損失函式，即非對稱的 Huber 損失，它對離群值具有健壯性，可以支援一系列常用的點估計。

非對稱 Huber 損失有兩個引數， delta 和 omega ，分別控制對離群值的穩健程度和不對稱程度。通過改變 delta （如圖 7 所示），平方誤差和絕對誤差可以平滑地插值，後者對離群值不太敏感。通過改變 omega ，你可以控制預測不足與預測過度的相對成本，這在晚一分鐘比早一分鐘更糟糕的情況下很有用。這些引數不僅可以模仿其他常用的迴歸損失函式，而且還可以對模型產生的點估計進行調整，以滿足不同的業務目標。

圖 7：非對稱 Huber 損失

我們如何訓練和服務模型

我們使用了 Uber 的機器學習平臺的 Canvas 框架，即 Michelangelo ，對模型進行了訓練和部署。我們的原型的具體架構基本在圖 8 中描述。在模型經過訓練並部署到 Michelangelo 之後，我們就需要將這些預測結果提供給使用者，以便進行實時 ETA 預測。高階架構如下圖 9 所示。Uber 消費者的請求通過各種服務被路由到 uRoute 服務。uRoute 服務作為所有路由查詢的前端。它向路由引擎提出請求，以產生路由線和 ETA。它使用這個 ETA 和其他模型特徵向 Michelangelo 線上預測服務提出請求，以獲得來自 DeepETA 模型的預測結果。定期的自動再訓練工作流程被設定為再訓練和驗證模型。

圖 8：模型再訓練和部署管道

圖 9：線上服務的高階系統圖

總結與展望

我們已經將這個 DeepETA 模型投入生產，用於全球汽車 ETA 預測。DeepETA 模型的推出使訓練和服務大規模的深度學習模型成為可能，而且效率很高，這些模型對 ETA 的預測比 XGBoost 方法更好。DeepETA 為生產中的指標提供了直接的改善，並建立了一個可以重複使用的模型基礎，用於多個消費者用例。

DeepETA 使 ETA 團隊能夠探索不同的模型架構，並輸出多種 ETA，為每個消費者量身定做。更多的工作進行中，通過研究建模過程的各個方面，包括資料集、特徵、轉換、模型架構、訓練演算法、損失函式和工具/基礎設施的改進，進一步擴大它所能提供的準確性。在未來，該團隊將探索增強功能，如連續的、增量的訓練，這樣 ETA 就可以利用更新鮮的資料進行訓練。

作者介紹：

Xinyu Hu，Uber AI 的高階研究員，專注於大規模機器學習在時空問題和因果推理方面的應用。擁有哥倫比亞大學生物統計學博士學位。

Olcay ciri，Uber AI 的研究員，主要研究機器學習系統和大規模的深度學習問題。曾在谷歌從事廣告定位工作。

Tanmay Binaykiya，地圖 ETA 預測團隊的高階軟體工程師，專注於機器學習和系統交叉的專案。

Ramit Hora，Uber AI & Maps 的技術專案管理主管，致力於推動 Uber 技術系統和產品體驗的創新。

原文連結：

http://eng.uber.com/deepeta-how-uber-predicts-arrival-times/

「其他文章」