編者按：Sentiance首席數據科學家Vincent Spruyt介紹了如何基于CNN和三重損失函數，學習位置嵌入。

在Sentiance，我們開發了一個平臺，從智能手機感知數據（加速度傳感器、陀螺儀、位置信息等）中提取行為學的洞見。我們的AI平臺學習用戶模式，能夠據此預測和解釋事件何時、為何發生，讓我們的客戶能夠更好地輔助其用戶，在合適的時間，以合適的方式接觸用戶。

這一平臺的一個重要組件是地點映射算法。地點映射的目標是根據位置測量得出當前訪問的地點，位置測量來自智能手機的位置子系統，經常不夠精確。

左：估計用戶實際訪問的相鄰地點；右：快速丟棄可能性不大的地點，例如海灘上的救生站

盡管地點映射本身就是一個困難的問題，足以專門寫一篇博客，人類的直覺能在很大程度上幫助解決這一問題。考慮上圖中訪問圣莫尼卡海灘的例子。稍微一瞥周邊地點，就能得出結論，用戶真去訪問一個救生站的幾率大概非常小。

事實上，僅僅只是查看某一區域的地圖，人類常常能夠快速丟棄可能性不大的地點，并形成關于實際發生的情況的先驗信念。地點在工業區，公園，海灘旁，市中心，公路旁？

為了在我們的地點映射算法中加入類似的直覺，我們開發了一個基于深度學習的方案，經訓練后可以編碼地理空間關系和語義相似性，描述位置的周邊。

編碼器輸出的嵌入捕捉了輸入位置的高層語義

編碼器轉換位置為分布表示，類似用于自然語言的Word2Vec。這些嵌入位于一個度量空間之中，因而遵循代數規則。以詞嵌入為例，我們可以推斷單詞相似性，甚至直接在嵌入空間中進行算術運算，例如“國王 - 男人 + 女人 = 王后”。

接下來我們將討論，如何設計一個方案，將位置坐標映射至讓我們可以進行類似操作的度量空間。

圖塊生成

柵格化GIS數據

給定位置的坐標和半徑，我們可以查詢GIS數據庫獲取大量地理信息。我們的GIS數據庫是OpenStreetMap的本地拷貝，存儲在PostGis數據庫中。PostGis是PostgreSQL的一個方便的擴展，增加了空間操作、類型、索引支持。

例如，使用一組查詢語句，我們很容易就可以檢查位置附近是否有河流，到最近的火車站有多遠，位置是否靠近馬路。此外，道路本身可以作為多段線獲取，而火車站建筑的輪廓也許能以多邊形對象的形式提供。

然而，神經網絡難以高效地處理這些未結構化的大量數據。考慮到我們的目標是訓練神經網絡理解形狀和空間關系，例如距離、包含、封閉、除外，我們決定柵格化位置周邊，得到固定尺寸的圖像，再傳入編碼器。

幸運的是，這些有很高效的現成工具。我們使用了Mapnik的Python接口，搭配定制的OpenStreetmap-Carto風格頁，得到了一個高速的柵格化工具，如下圖所示。

我們的柵格化服務可以通過參數方便地進行數據增強，也就是在生成圖塊前旋轉、平移地圖，如下圖所示。

這些圖塊均表示同一位置，但朝向、偏移量不同

從圖像到張量

盡管這些柵格化圖塊讓編碼器可以很容易地學習捕捉空間結構和關系，卻有大量信息在柵格化的過程中丟失了。實際上，柵格化合并了所有多邊形和多段線，例如道路、建筑、停車場輪廓、河流，等等。由于GIS數據庫包含這些結構的單獨信息，讓神經網絡編碼器學習如何分割這些結構毫無道理。

因此，我們并沒有將數據柵格化為三通道RGB圖像（如上面的示意圖所示）。相反，我們修改了柵格化工具，生成一個12通道的張量，每個通道包含不同類型的柵格化信息。

為了便于可視化，本文剩下的部分常常使用RGB柵格化圖塊，實際上它代表12通道張量。

表示學習

空間相似性

我們的目標是學習一個度量空間，其中語義相似的圖塊對應相近的嵌入向量。那么，問題在于如何定義“語義相似”？

一個樸素的方法是將每個圖塊表示為直方圖，然后應用k-均值聚類，接著使用詞袋模型建模空間。然而，我們不清楚各個通道應該分配多少權重。例如，如果道路相似，但建筑不相似，那么這兩個圖塊仍然算語義相似嗎？

此外，即使兩個圖塊有相似的直方圖，也不能給我們提供位置周邊的空間結構信息。如果圖塊的一半被大海覆蓋，那么這個圖塊和另一個包含大量小池塘、噴水池的圖塊在語義上相似嗎？下圖中的兩個圖塊會產生幾乎一模一樣的直方圖：

然而，這兩個圖塊在語義上并不相同。第一個圖塊覆蓋的是相互連接的道路，第二個圖塊覆蓋的是一些小路，這些小路可能通向人們的住所。事實上，在我們的嵌入空間中，這兩個圖塊對應的嵌入之間的歐幾里得距離可不小（||p1-p2||2=2.3），盡管兩者的直方圖的卡方距離接近零。

除了使用直方圖，每個通道也可以總結為一組特征，例如方向梯度的直方圖，或者更傳統的SIFT或SURF。然而，我們并不打算手工指定哪些特征定義了語義相似性，相反，我們決定借助深度學習的力量，學習自動檢測有意義的特征。

為了達成這一點，我們將12通道張量傳入作為編碼器的卷積神經網絡。該網絡以自監督的方式基于三重損失函數訓練，這意味著無需手工標記的訓練數據。

自監督學習：三重網絡

Ailon等提出的三重損失這一概念，借鑒自孿生網絡架構，可以基于無監督特征學習進行深度度量學習。

三重網絡是一個基于三元組(x, x+, x-)訓練的神經網絡架構：

錨實例x

和x語義相似的正例x+

和x語義相異的反例x-

接著訓練神經網絡學習滿足下式的嵌入函數f(.)：

從而直接優化度量空間，如下圖所示：

Google的FaceNet讓基于三重網絡的度量學習變得更流行了，FaceNet使用三重損失學習類似面孔接近、不同面孔疏遠的面部圖像嵌入空間。

對面部識別而言，正例圖像是和錨圖像屬于同一人的圖像，而反例圖像是從mini batch中隨機選擇的人的圖像。然而，我們的例子沒有這么容易選取正例、反例的分類。

為了定義位置的語義相似性，我們可以利用Tobler的地理第一定律：“所有位置之間都有關系，但近處的關系比遠處的關系密切。”

令I(.)為位置坐標到柵格化圖塊的映射，給定變換T(.)，該變換在生成位置X的柵格化圖塊前先旋轉、平移地圖，然后給定一個隨機位置Y，滿足X ≠ Y，那么我們便得到了三元組：

x = I(X)

x+= I(T(X))

x-= I(Y)

因此，我們假定地理上相鄰、部分重疊的兩個圖塊，相比完全不同的兩個圖塊，在語義上更相近。

為了避免網絡僅僅學習瑣碎變換，我們在訓練過程中隨機開啟或關閉正例圖像12個通道中的部分通道，迫使網絡在信息的隨機子集不同（例如，沒有建筑物，沒有道路，等等）的情況下，學習正例圖塊的相似性。

SoftPN三重損失函數

下為我們使用的三重網絡的一般結構。

上圖中的損失函數的具體定義如下：

所以優化網絡等價于最小化向量(d+, d-)和向量(0, 1)的MSE。

下面我們解釋下為什么損失函數這么定義。我們想要Δ(a,p)盡可能地接近零，Δ(a,n)盡可能大。為了優化這一比率，我們應用softmax，使兩者位于[0, 1]之間：

三重損失函數的這一定義經常稱為softmax比率，最早由Ailon等提出。

這一定義的主要問題在于，網絡會很快學到一個d-接近一的嵌入空間，因為大多數隨機負例圖像和瞄圖像大不一樣。因此，大多數(a,n)對優化過程中的梯度沒有貢獻，導致網絡很快停止學習。

我們可以使用不同的方法解決這一問題，其中之一是難分樣本挖掘，精心選擇(a,n)以確保網絡可以維持學習。然而，在我們的例子中，在不引入偏差的情況下，并不總是清楚如何有效地選取難分樣本。而Balntas等提出的SoftPN三重損失函數，是一個更簡單的方案。

SoftPN損失將上述softmax計算中的Δ(a,n)替換為min(Δ(a,n), Δ(p,n))。這就使網絡在優化過程中，試圖學習一個錨嵌入和正例嵌入都盡可能遠離反例嵌入的度量空間。相反，原本的softmax比率損失只考慮錨嵌入和反例嵌入的距離。

神經網絡架構

編碼器部分我們用了相當傳統的卷積神經網絡架構，包含5個卷積層，過濾器大小為3x3，接著是兩個一維卷積層，一個密集層。一維卷積通過跨通道參數池化起到降維作用。

嵌入層由另一個密集層加上一個線性激活函數構成，線性激活函數使得輸出范圍不限于前一層非線性激活的正值區域。完整的網絡架構如下圖所示：

我們激進地使用dropout和BN，同時使用了Leaky ReLU激活函數，因為我們在剛開始的測試中碰到了死亡ReLU問題。

此外，我們直接對輸入應用了空間池化，完全丟棄一個隨機選擇的通道，迫使網絡通過關注不同的通道學習區分圖像。

整個網絡基于Keras實現，僅包含305040參數，使用Adam優化在p3.2x large AWS主機上訓練了兩周。

訓練數據

我們獲取了用戶在我們平臺上訪問的約一百萬位置，并增加了用戶沿途拍攝的接近五十萬位置。

我們將這一百五十萬位置中的每個位置柵格化為128×128×12的圖塊，表示該位置方圓一百米內的區域。這些張量用作錨圖像。

我們同時為每個位置柵格化20張隨機平移、旋轉的圖塊，用作正例圖像。橫縱兩方向的偏移均勻取樣自0到80米的區間。最終，每個位置得到了20對(錨，正例)，共計三百萬張圖像。

網絡訓練生成mini batch時同時生成三元組。每個mini batch包含20個位置。每個位置隨機選擇5對(錨, 正例)，而反例圖像則隨機取樣自mini batch，這樣每個mini batch大小總共為100。

在生成mini batch的同時生成三元組，實際上我們得到了一個幾乎無限大的包含獨特的三元組的數據集，鼓勵網絡在許多epoch后持續學習。

可視化過濾器和激活函數

由于嵌入空間是以自監督的方式學習的，沒有使用標注數據，所以難以監測網絡是否真的在訓練中學到了東西。

可視化網絡學習到的過濾器是一個不全面但仍然很有用的檢查方法。事實上，我們想要可視化可以最大化網絡不同層的激活的輸入圖像。

為了做到這一點，我們可以從一個隨機生成的圖像開始，將每個像素看成需要優化的一個參數。接著我們使用最大化選定層輸出的梯度上升更新圖像的參數。

計算輸入圖像在卷積層輸出激活的均值上的梯度，基于若干次迭代進行的梯度上升，能夠生成高亮網絡層最關注的結構的圖像。

因為我們的輸入是一個12通道張量，而不是RGB圖像，所以我們直接從12個通道中選擇了像素值均值最大的3個通道，將其轉為RGB圖像。我們在每個通道上應用了直方圖均衡化，以進一步增強視覺細節。

下圖顯示了位于底部的一個網絡層的每個32過濾器。顯然，這一層看起來更關注底層細節（道路、小塊結構等）。

對比位于上部的一個網絡層的64過濾器，很明顯，這些過濾器更容易被更平滑、更復雜的結構激活。這一對比也許意味著整個網絡能夠學習輸入的層級特征分解。

高層傾向于通過組合低層學習到的低層特征學習更復雜的結構

盡管我們不應該過高估計這些可視化的有用程度，但它們確實看起來很有意思，特別是在多次研究迭代之間。例如，早期版本的可視化快速地指引了正確方向，發現了我們網絡中的一堆死亡ReLU。我們后來通過替換激活函數為Leaky ReLU解決了這一問題。

探索度量空間

可視化嵌入

可視化網絡學習到的過濾器主要用于調試，但在判斷學習到的嵌入空間的質量方面沒有多大幫助。

為了大致了解嵌入空間看起來什么樣，我們使用PCA將維度降至三維后，可視化了嵌入空間。為便于解釋，每個位置嵌入可視化為相應的柵格化圖塊。

顯然，即便只留下三個主成分，這三個分量仍然捕捉了大量有意思的信息。公園等綠化區域、道路區域、（右下角的）城市中心區域區別非常明顯。

下圖是一個嵌入空間的三維t-SNE動畫，更清楚地顯示了這些局部結構的差異。

這些嵌入不僅可以用于地點映射，還可以用在我們的交通路線分類器中。下圖顯示了取自我們的交通路線分類訓練集的位置嵌入的散點圖。這里，我們使用線性判別分析（LDA）將16維嵌入空間映射至二維。

上圖顯示，不同的交通方式一般發生在不同的區域。例如，我們的嵌入捕捉了關于鐵軌和電車站的信息。

為了顯示不同的地理區域是如何編碼的，我們使用PCA將16維嵌入降至三維，縮放后直接作為RGB顏色值使用，以便在地圖上繪制測試數據集。下圖可視化了倫敦區域，清楚地體現了市中心、公路、水域、旅游區域、住宅區的編碼各不相同。

通過可視化伯明翰區域，可以揭示，與充斥大量建筑的倫敦相比，伯明翰有一個更大的郊區。

空間內的隨機行走

我們可以通過隨機行走進一步檢驗嵌入空間的平滑性。隨機行走從一個隨機的種子點開始，每次跳躍隨機選擇當前嵌入的k近鄰中的一個，然后可視化相應的圖塊。

下圖顯示了6次隨機行走的結果。注意，大多數情況下，嵌入空間的最近鄰在地理上相距數百千米、數千千米，但在語義上高度相似。

位置計算

盡管上面的可視化表明學習到的嵌入空間是平滑的，也捕捉到了語義相似性，但并不能證明我們確實學到了一個歐幾里得度量空間——我們可以在嵌入之間插值，在嵌入上進行基本的算術運算，并得到有意義的結果。

下圖演示了在兩個嵌入（最左、最右）之間插值的結果。插值的每一步所得，映射至測試數據中的最近嵌入，然后可視化相應的圖塊。

最后，下圖顯示了加上嵌入或減去嵌入，并將結果映射至測試數據中的最近鄰，會發生什么。

這些結果表明，我們的嵌入空間確實表示了一個距離具有意義、基本算術規則成立的度量空間。

由于度量空間是基于自監督方式訓練得到的，我們可以使用大量未標簽數據迫使網絡學習捕捉有意義的關系。因此，在后續分類器中使用這些嵌入作為特征向量，是一種遷移學習的形式，讓我們可以基于非常有限的標注數據訓練強大的分類器。

結語

本文顯示了如何使用三重網絡學習捕捉不同地理位置坐標間的語義相似性的度量空間。

我們訓練卷積神經網絡學習提取定義語義相似性的特征，然后通過度量學習得到一個嵌入空間。

所得嵌入空間可以直接用在地點映射或交通路線分類這樣的任務上，通過遷移學習幫助我們大大改善分類器的精確度和概括能力。

此外，這些嵌入給分類器帶來了某種直覺，使得錯誤的分類仍然可以作出直觀的解釋。例如，我們的地點映射器很快學習到將日間活動和夜間活動綁定到不同的特定區域，例如工業區、市中心、公園、火車站等。