使用 Spark，LSH和TensorFlow 檢測圖片相似性

雷鋒網按：本文為 AI 研習社編譯的技術博客，原標題 Detecting image similarity using Spark, LSH and TensorFlow，作者為 Andrey Gusev（Pinterest 工程師，內容質量分析師）。

翻譯 | 沈波  張天航    校對 |  餘杭    整理 |  凡江

作為一個視覺數據處理平台，擁有從海量圖片中學習並理解其內容的能力是非常重要的。為了檢測幾近重複的相似圖片，我們使用了一套基於 Spark 和 TensorFlow 的數據流處理系統——NearDup。這套系統的核心由一個使用 Spark 實現的批量化 LSH（locality-sensitive hashing，局部敏感哈希）搜索器和一個基於 TensorFlow 的分類器構成。這個數據流處理系統每天能夠比較上億個分析對象，並漸進式地完成各個圖像類別的信息更新。在本文中，我們將講解如何使用這項技術更好地理解海量圖片內容，從而使得我們產品前端界面的推薦內容和搜索結果具有更高的信息準確性、更大的數據密度。

簡介

我們將我們圖片庫中的所有圖片劃分為不同的圖片類，每一類都由幾近相同（以人類觀察員的判斷為標準）的圖片組成。這種分類標準有一定的主觀性，為了給你一個感性認識，下圖展示了一些按照 NearDup 閾值進行圖片分類的例子。注意，這些相似圖片不一定來自同一圖像源（參見右下圖），也不一定有相同的背景（參見左下圖）。同時，圖像中可能包含一定的幾何扭曲（參見左上圖），或者旋轉、剪切和翻轉變化（見中心圖和右上圖）。

為圖片庫中的所有圖片進行分類與劃分的過程在數學上無法進行嚴格定義與求解，這是因為在 NearDup 系統中，圖片之間的關係不具有傳遞性和相等性。為了說明這一點，我們可以想像將一張「貓」的圖片通過 1000 步慢慢地形變為一張「狗」的圖片的過程。容易推斷，每一步微小形變前後的兩張圖片的相似度都將落入 NearDup 的閾值，從而將它們判斷為「相似」圖片。然而，究竟該將這一串前後相似的圖片序列劃分為哪幾類？貓類，狗類，還是貓-狗類？為了解決這一問題，我們將問題模型轉化為圖：圖的節點代表圖片，邊代表相應圖片間的相似度。隨後我們結合傳遞閉包法（ transitive closure ）和貪婪 k-cut 演算法來最小化圖的 k-cut 劃分，從而近似求解整個圖片庫的最優劃分。

使用批量化 LSH 進行數據預處理

嵌入和 LSH 對象

為了理解圖片內容，我們將圖片轉換到一個嵌入向量空間（embedded vector space）中。這些圖嵌入向量是圖片的一種高維向量表示，能夠抓取圖片的視覺和語義相似性。它們一般通過神經網路架構如 VGG16 或 Inception 等處理生成。為了在 NearDup 系統中處理圖片關係並對圖片庫進行分類，我們每天要比較幾千萬張新圖片，並將它們分類到上億個圖片類別中。如果沒有優化措施，如此大規模的近鄰搜索（nearest neighbor search）問題的時間複雜度為平方（quadratic）複雜度，相應的計算時間將正比於甚至超過 10 個 quadrillion 秒（1 後面 16 個 0！）。為此，我們通過將圖嵌入向量進一步縮減為 LSH 對象的方法，顯著縮小了問題規模，降低了處理難度。

LSH 是一種先進的數據降維技術，降維前後數據點之間的距離關係保持不變。原向量空間首先通過隨機投影法（random projection）和位抽樣 LSH（bit sampling LSH）法進行一定的降維。隨後，我們繼續將所得到的向量位分組為多個 LSH 對象，分組過程有效地權衡了檢測準確率和計算時間這一矛盾體。分組越精細，進行最近鄰搜索的計算複雜度將越高，但檢測準確率也將越高。這裡，我們使用 LSH 對象之間的 Jaccard 重合度來近似表示原向量空間中相應向量間的餘弦相似度。

批量 LSH 搜索

當所有圖片都用一組 LSH 對象表示之後，我們繼續為它們建立反向索引，並實現對所有圖片的批量查詢與搜索。從頂層看，我們通過函數式轉換法（functional transformation）、壓縮式反向索引與連接法（compressed inverted indexes and joins）等方法的結合，來實現對所有圖片的一次性批量查詢與比較。這個數據流處理過程是用 Spark 實現的，並需要藉助一系列的優化措施來進一步保證這些海量數據能夠轉化到盡量簡單有效地的LSH 對象空間中進行處理。我們所使用到的主要優化措施包括：

字典編碼（ Dictionary encoding ） 使得所有數據都用具有最短寬度的數值進行表示

可變位元組編碼（ Variable byte encoding ） 被用於所有的反向索引

索引切分（ Index partitioning ） 提高了反向索引的平衡性

基於代價的優化器（ Cost-based optimizer ） 能夠檢測嵌入向量空間的密度，並計算最優的運行時參數

原始數據堆排（ Primitive data packing ） 進一步提高了內存使用率

Jaccard 重合度計數（ Jaccard overlap counting ） 基於低層次、高性能的數據收集實現

去堆化（ Off heaping ） 減少了垃圾回收（GC）過載

使用遷移學習的候選選擇

批量化LSH是產生高查全率（召回率）同時又能最小化計算成本的一個很效果的方法。但是，它通常不會對候選項產生最優的查准率（準確率）和排序。我們通過使用一個有監督的分類器去挑選那些NearDups 認為足夠相似的候選項。這個分類器是一個遷移學習在視覺嵌入上的例子。它使用了Tensorflow 前饋網路和一個 Adam 優化器 。我們已經在超過包含10億不同對圖像的樣本集中訓練了分類器。訓練集由決策樹分類器在SURF 視覺特徵上的輸出得到，並進行了幾何驗證，然後用於NearDup 系統的先前迭代。為了提高學習和每一對圖像的收斂性，將 hamming 碼位元組進行異或運算後輸入到輸入層。該分類器被調整到很高的準確率並且在人類標記的樣本上達到了 99% 以上準確率。

SparkContext 也可以對訓練過的網路進行推斷。使用 mapPartitions 和分組範式，我們可以使用預定義好尺寸的大批數據去有效地向量化和減少開銷。在一個擁有1000萬個參數的網路中，我們在一個r3.8xlarge 的機器集群上實現了平均2ms進行一個預測的速率。

結論

NearDup 檢測需要進行計算代價很高的兩兩比較。通過在Spark 中使用批處理LSH實現，我們通過跳過不太相似的圖像對大大降低了計算的複雜度。Spark-based 的實現結合了高效的工作負載分配和低層次的優化，以最小化內存和CPU佔用。隨後的調優步驟使用了一個有監督的前饋網路來選擇和排序高於NearDup 相似性閾值的圖相對。Spark 和Tensorflow 的推斷結合使用了分散式計算和每個內核矢量化的最佳特性，實現了高吞吐量和低延遲的預測。然後，將這兩個步驟的結果用於集群圖像，每天幫助提供數百億的搜索結果和在Pinterest 上的推薦。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！