Categories
程式開發

機器學習在滴滴網絡定位中的探索和實踐


機器學習在滴滴網絡定位中的探索和實踐 1

今天給大家分享的是機器學習在滴滴網絡定位中的實踐工作,會重點介紹三階段的演進:無監督模型、有監督回歸模型、端到端CNN模型。

1. 什麼是網絡定位

目前定位技術主要包括GPS、網絡定位、慣性航位推算、MM(地圖匹配)、視覺定位等。 GPS是最為人熟知的定位技術,是依靠設備與衛星交互來獲取經緯度的方式。 GPS精度高,但有冷啟動耗時長、耗電大、遮擋場景不可用等缺點。在滴滴場景下,乘客和司機在有遮擋的場景下,例如室內、高架下等,GPS通常處於不可用狀態。這時就需要有其他定位技術作為GPS的補充,使得乘客發單、司機導航等服務依然可用。其中最主要的補充便是網絡定位。

室內類場景雖然有遮擋,但設備通常可以掃描到Cell(基站)和Wifi列表,而且Cell和Wifi設備位置相對穩定,連接其上的設備可以藉其定位,這就產生了網絡定位。網絡定位包括wifi定位和基站定位,是指基於終端掃描到的wifi或基站列表進行的定位技術。 Wifi的接入設備通常稱為AP(Acess Point),方便起見,下文將AP和基站統稱為AP。

網絡定位通常採用的是指紋定位技術,是一個根據query匹配指紋庫信息,併計算得到坐標位置的過程。如下圖所示,網絡定位系統主要包括離線建庫和在線定位兩個階段。

機器學習在滴滴網絡定位中的探索和實踐 2

離線建庫主要是基於有GPS時的採集數據,建指紋庫的過程。指紋庫中記錄AP的各類信息在不同地理網格內的採集數據分佈,如下圖所示。

機器學習在滴滴網絡定位中的探索和實踐 3

在線階段,根據線上query匹配指紋庫信息,併計算得到坐標位置。

本文介紹的主要是在線定位部分,即query匹配指紋庫、計算坐標位置。

2. 網絡定位匹配算法迭代

在線定位算法共經歷了無監督概率模型、有監督回歸模型、端到端CNN模型三次大的迭代。前兩個階段的網絡定位主要包括網格召回、網格排序、網格平滑三步,如下圖圖一所示。端到端CNN模型去除了網格排序和網格平滑,基於一個召回中心點,直接回歸位置坐標,如下圖圖二所示。

機器學習在滴滴網絡定位中的探索和實踐 4

圖一

機器學習在滴滴網絡定位中的探索和實踐 5

圖二

2.1 無監督概率模型

網絡定位要完成在線AP與離線AP指紋庫的匹配,是聯合概率計算的過程。

以AP指紋庫的信號強度分佈為例,看下網格概率計算過程。

機器學習在滴滴網絡定位中的探索和實踐 6

縱軸為採集數據中的AP編號,橫軸為空間網格編碼,相交點表示每個AP在對應網格中的採集信號強度分佈。空值表示AP在對應的位置無採集數據。

以一個實時定位query信息:(AP1:RSSI=1,AP3:RSSI=0)為例,介紹網格召回、排序、平滑的過程。

召回階段,基於掃描到的AP1和AP3,可以召回Grid1、Grid2、Grid4;

排序階段,結合離線AP庫,基於獨立性假設和貝葉斯公式,計算各網格的權重:

機器學習在滴滴網絡定位中的探索和實踐 7

$ap_j$ 表示觀測到的APj的信息。以信號強度RSSI單一特徵為例,上例中,

機器學習在滴滴網絡定位中的探索和實踐 8

網格平滑階段,基於上述的統計概率,排序獲取TopK個網格,採用爬山法求解最優坐標:

機器學習在滴滴網絡定位中的探索和實踐 9

其中,$d_i$ 為預測位置到$Grid_i$ 的距離。

2.2 有監督回歸模型

無監督概率模型的方法,思路清晰易懂,易實現,是早期網絡定位的主要方式。但有以下問題:

  • 聯合概率的方式對採集信息不充分的位置不友好,例如上例$W_{Grid_2}=0$
  • 難以擬合多維特徵,尾部badcase較嚴重
  • 技術目標無法得到直接優化,天花板較低

出於對以上問題的思考,整體流程仍保持網格召回、排序、平滑三階段,我們將網格排序升級為有監督回歸模型,通過引入多元特徵和顯式的優化目標,實現對網格的更精準打分。

Label:待預測網格與真實位置的位置偏差,回歸任務。

特徵工程:構建近百維特徵,主要包含AP特徵,網格特徵,前文信息等。

模型選擇:一期上線GBDT模型;二期對比了GBDT、FM、DeepFM、FM+GBDT等,最終線上最優融合模型結構如下。

機器學習在滴滴網絡定位中的探索和實踐 10

原始特徵中的稠密特徵和低維稀疏特徵經過GBDT進行特徵組合、交叉;GBDT輸出的葉子節點編號與高維稀疏特徵經過DeepFM網絡,最終輸出網格與真值的位置偏差。

TopK網格平滑:預測偏差距離從小到大排序,截取TopK網格;爬山法,梯度下降求解最優坐標。

2.3 端到端CNN模型

有监督模型在特征利用、模型结构、优化目标等方面提供了更大的操作空间,可以极大地打开天花板。上线后定位精度等指标取得了显著的收益。

但該方法仍有以下問題:

  • 每個網格孤立刻畫,信息採集時的不均衡、有偏的問題無法有效解決
  • TopK平滑層與排序層割裂,無法聯合優化,且引入部分人工超參

對於以上問題,考慮以下解決方案:

  • CNN網絡:充分利用空間信息的局部相關性,增強特徵的提取能力
  • 端到端網絡:合併排序與平滑層,改為直接回歸位置坐標,目標更統一,減少人工超參

最終,整體網絡結構如下:

機器學習在滴滴網絡定位中的探索和實踐 11

下面以基站定位為例,介紹該結構的實現細節。

首先介紹下輸入特徵的構建:

  • Wide網絡特徵:表達Query信息的Wide特徵共十幾維
  • CNN特徵圖的構建:
    • 召回中心:採集熱度較高的TopN網格的經緯度中位數作為圖的中心點。
    • 特徵圖構建:選取C維圖特徵,每一維特徵為一個channel;基於召回中心,構建M*M分辨率的特徵圖。

機器學習在滴滴網絡定位中的探索和實踐 12

CNN特徵類別

機器學習在滴滴網絡定位中的探索和實踐 13

網格上各個channel的特徵計算

機器學習在滴滴網絡定位中的探索和實踐 14

輸入特徵圖的示例

網絡結構:在CNN網絡部分,採用多尺度卷積核提取特徵後,經過兩個卷積+池化層後,將特徵圖打平。 Wide部分稀疏特徵經過embedding後,與稠密特徵級聯。兩部分tensor級聯後經過全連接層,最終輸出與召回中心點的位置偏差。

Label與Loss:label為真實位置與召回中心位置的偏移dx和dy,召回中心點+預測偏移即得預測位置。 loss最初使用的是經緯度的L2 loss:

機器學習在滴滴網絡定位中的探索和實踐 15

考慮到經緯度在球面上表達距離的差異,我們改為了使用球面距離偏差作為label,也獲得了穩定的收益:

機器學習在滴滴網絡定位中的探索和實踐 16

dx和dy表示真實空間距離

CNN模型在线上AB实验取得了显著的收益,已全量上线。

CNN端到端模型升级了信息的表达方式,由单网格、结构化的信息表达改为了Image的表达方式,配合cnn网络结构,获取了效果的显著提升;并且将几十甚至几百个网格的预测问题改为了单次位置回归问题,虽然模型复杂度有所增加,但整体性能基本持平。

2.4 線上效果

網絡定位三階段的模型先後上線進行了AB對比實驗。以基站定位三個主要技術指標為例,對比結果如下表所示:

機器學習在滴滴網絡定位中的探索和實踐 17

3. 總結與展望

本文總結了定位策略團隊在網絡定位算法側的工作,介紹了無監督概率模型、有監督回歸模型、端到端CNN的演進及其中的思考。

無GPS時的定位仍面臨著很多困難,未來我們將在以下方面持續探索:

  • 模型效果優化:

    目前CNN模型在基礎信息利用、召回等方面仍有較大優化空間。

  • 性能問題:

    考慮線上性能,在基礎信息和網絡結構上做了很多刪減。期望通過更優的召回策略、蒸餾剪枝等平衡效果與性能。

  • 5G技術:

    5G的天然优势(高频率、高密度、低延时)也必定会带来定位精度的显著提升,相关调研工作正在进行。

  • 複雜場景定位:

    對於室內、地下停車場等典型複雜場景,網絡定位面臨著真值獲取難、移動ap等難點。細分場景也逐漸向模型化方向演進。

以上就是滴滴網絡定位近期工作的實踐介紹,歡迎隨時交流。

作者介紹

劉磊,滴滴專家算法工程師

2017年加入滴滴,目前從事地圖定位算法方向,多年LBS領域算法研究工作,在滴滴先後從事猜你想去、上下車點推薦、定位算法等方向的開發工作。

尹蔔一,滴滴高級算法工程師

2018年加入滴滴,主要從事網絡定位、慣導推算等方向的算法開發工作。

林宇,滴滴高級算法工程師

2018年加入滴滴,主要從事網絡定位、融合定位等方向的算法開發工作。

本文轉載自公眾號(ID:)。

原文鏈接

機器學習在滴滴網絡定位中的探索和實踐