檢索中的各類Hash及其應用

索引或搜索問題早在上世紀就以出現，如基於文本的搜索等。隨著互聯網等相關技術的飛速發展，搜索問題顯得越來越重要。多媒體信息檢索主要經過了三個階段，即基於關鍵詞、基於重複內容和基於語義。2012年5月谷歌推出知識圖譜技術即為基於語義的檢索，此後主流的搜索引擎，如Google，Biying，Baidu等以知識庫的搜索均是基於知識圖譜的搜索。知識圖譜簡單來說就是三元組，即知識圖譜的構建過程就是抽取非結構化數據（如圖片等）或半結構化數據（如網頁等）中客觀世界的概念、實體、事件及其之間的關係並將其結構化的過程（即構建三元組）。此外，互聯網中大量存在多維、高階、海量的文本、圖像和視頻等數據，這些信息間存在著錯綜複雜的交叉關聯，具有跨媒體特性。而對於跨模態的檢索其存在的最大問題即為「語義鴻溝」。

圖1. 「語義鴻溝」圖例說明

如上圖所示，若對圖像進行簡單的匹配搜索，即從視覺底層去進行相似性判斷而不進行語義層面上的推理分析，則將會出現很多荒誕的結果。

網路多媒體檢索的基本流程如下圖所示：

圖2. 網路多媒體檢索的基本流程

如上圖所示，網路多媒體檢索的基本流程主要包括三個階段：Step1.數據蒐集（網路爬蟲）；Step2.數據索引，該過程即為數據的清洗、結構化操作，如以圖搜圖中視覺詞袋的構建及Hash映射等；Step3.數據排序，如相似度和距離的定義及計算等。

1. 多媒體內容的索引

內容的搜索問題其本質上即為Top N排序問題。對於排序的準則主要包括動態相關性和靜態相關性這兩個方面。其中動態相關性是指與查詢詞的相關性，如TF-IDF。而靜態相關性即表示查詢對象的質量（權威性），如PageRank。

1.1 TF-IDF

TF-IDF_{i,j}=tf_{i,j}cdot idf_{i} tf_{i,j}=frac{n_{i,j}}{sum_kn_{k,j}} idf_i=lgfrac{|D|}{|{j:t_i o d_j}|} ag{1}

上式中， tf_{i,j} 為詞頻（term frequency），其中 n_{i,j} 為關鍵詞$i$在文檔$j$中的出現次數； sum_kn_{k,j} 為文檔 k 中出現的詞數之和。 idf_i 即反映該文檔 j 的重要程度，該值越大則說明文檔 j 越重要。 idf_i 為逆向文件頻率（inverse document frequency），其中 |D| 為資料庫中文件總數目， |{j:t_i o d_j}| 為包含關鍵詞 i 的文檔數目，為避免關鍵詞在所有文件中均未出現的情況（未登錄詞），在實際使用中我們一般取 1+|{j:t_i o d_j}| 。 |{j:t_i o d_j}| 越小，即說明該關鍵詞越能代表或反映所搜索的文檔內容，即其所包含的信息量越大（類比信息熵）。 idf_i 反映關鍵詞的重要程度，其值越大即 |{j:t_i o d_j}| 則說明關鍵詞越重要。

此外，考慮關鍵詞在文檔中出現的位置，以及文檔的大小，我們會對 TF-IDF 進行修正。（一般認為關鍵詞出現在文檔標題、關鍵詞、摘要、段首以及文檔越靠前的位置其重要度越高。文件大小<40K較為合適，若文檔過長我們需對 TF-IDF 進行一定的懲罰）

1.2 PageRank

作為Google戰勝Yahoo的祕密之一，大名鼎鼎的PageRank演算法在此就不做過多介紹，其核心思想即認為某一鏈接的質量由其本身即指向它的連接共同決定。如下式所示：

r(p)=alphasum_{q:(q,p) o epsilon}frac{r(q)}{w(q)}+(1-alpha)frac1N ag{2}

上式中， r(p) 為網頁 p 的PageRank值；

q 為網頁 p 的後向鏈接，即 q o p ； w(q) 為網頁 q 的前向鏈接數目；

r(q) 為網頁 q 的PageRank；

N 為整個網路中網頁的總數。

圖3. PageRank

從式(2)中我們可以看出PageRank是一種與與查詢無關的靜態演算法，即其最終排序結果可提前計算給出，能夠較好的滿足實時性的需求。而該演算法的缺點則是，其最終結果與主題無關，且舊網頁的排名往往要比新網頁高。

此外需要指出的是在PageRank提出之前，康奈爾大學的J.M.Kleinberg教授提出的HITS演算法也是基於相似的思想，即認為：一個好的「Authority」頁面會被很多好的「Hub」頁面指向，且一個好的「Hub」頁面會指向很多好的「Authority」頁面。該演算法在自然語言、社交網路等領域取得很好效果。然而該演算法也存在計算複雜、主題漂移、易作弊的缺陷。

2. 近鄰搜索中的Hash表示

在實際的圖像檢索應用中，如「以圖搜圖」問題，為滿足實時性的需求，我們一般是採用近似搜索的策略。此時，需要在檢索精度和檢索速度的trade-off中做到平衡，另外對於大多數應用，近似近鄰就能很好的滿足要求。

圖像檢索的主要過程如下：

圖4. 圖像檢索

如上圖所示，圖像檢索一般包括局部特徵的提取，如SIFT[Lowe』99]，HOG[Dalal』05]，LBP[Ojala』94]等；傳統手工設計的特徵描述子提取的特徵太多，因此需經過局部特徵編碼，如硬投票[Joachims』98]，軟投票[Gemert』08]，稀疏編碼[Yang』09]，局部敏感哈希[Indyk98]，譜哈希[Weiss08]等；圖像全局特徵表示，如空間金字塔模[Lazebnik』06]，空間劃分學習[Jia』11]等；相似性、距離計算等。其中Hash函數簡單來說就是將原始數據編碼（映射）為0-1碼，而通過Hash編碼，其不僅能實現時間上的高效（基於XOR操作的快速計算）還能實現存儲上的高效（基於位存儲的緊緻表達）。好的Hash函數一般要求原始相近的數據其哈希編碼也要儘可能的相近，而當原始數據發生變化時其Hash編碼的差異也要儘可能的大，同時還能抵禦各種攻擊以保護原始數據。Hash函數廣泛應用於密碼學、通信等領域，從最初的Hash提出直至今日，Hash函數已不下百種，然而在眾多的Hash中不得不提的是最初的LSH和譜哈希，它們的出現極大的推動了Hash研究的進行。

圖5. Hash表示

2.1 局部敏感哈希（Locality Sensitive Hashing，LSH）

局部敏感哈希是非常簡單的一種哈希函數，其通過無監督學習生成。由於結構、運算簡單而在許多鄰域得到廣泛應用。尤其是當編碼位數較長時其效率有明顯的提高，因此在很多任務中LSH是我們必須嘗試的編碼之一。LSH通過將原始數據進行隨機投影后經過符號函數得到Hash編碼，其表達式如下：

B=sgn(XW) ag{3}

上式中 X 為原始數據， W 為變換矩陣， B 為Hash編碼。可以看出LSH真的是非常簡潔，這也充分驗證了「Simple is beauty.」這句名言。而對於LSH為什麼會如此有效，不少學者進行了大量研究。2017年12月Science上發表文章"A Neural algorithm for a fundamental computing problem"，該研究發現果蠅的嗅覺環路對相近的嗅覺產生相近的神經活動模式，可將一種味覺習得的行為應用於接觸相似味覺時。因此研究者受此啟發，將其中的三種全新計算策略應用於計算領域，提出新的局部敏感哈希演算法，該方法可有效改善近似檢索的計算表現。

圖6. LSH VS the fly olfactory circuit

雖然該方法在編碼長度較短式其性能要由於LSH，然而隨著編碼長度的增加LSH性能快速上升，該方法在較長編碼時優勢並不明顯。

2.2 語義哈希（Semantic Hashing）

Semantic hashing由Hinton大爺於2007年提出（2006年Hinton在Science上首次提出了Deep Learning，然而當時在學術界並沒有引起太多的關注，於是其便將RBMs在各個鄰域進行應用，Hash編碼便是其中之一），其主要是利用深度受限制玻爾茲曼機RBMs，學習Hash編碼，網路結構如下圖所示：

圖7. Semantic Hash

從上圖可以看出通過最大釋然優化能量函數，得到Hash編碼，另外為使編碼更加魯棒，在編碼後進一步引入隨機雜訊，經一步的優化網路。

2.3 譜哈希（Spectral Hashing, SH）

譜哈希是哈希函數族中的又一經典代表，其天才的將哈希編碼過程轉化為圖像分割問題，進而通過放鬆約束條件將分割問題轉化成拉普拉斯特徵圖的降維問題，從而求解原問題得到圖像數據的哈希編碼。

圖8. Spectral Hash

上圖中， y_i,y_j 即為哈希編碼，最小化目標函數 sum_{ij}W_{ij}||y_i-y_j||^2 即最小化著名的Laplacian Eigenmaps（拉普拉斯特徵映射）公式。而約束條件 y_iin {-1,1}^k 即保證Hash編碼的離散型和有效性；約束條件 sum_iy_i=0 即保證各個哈希編碼內的平衡；約束條件 sum_i y_iy_i^T 即保證各個哈希編碼間互不相關。通過優化目標函數即可得到緊湊的哈希碼，從形式上看，哈希和流形學習之間的區別很小，主要區別在三個限制條件上。但其中最主要的，離散條件（二值化）的限制使得哈希學習的研究和傳統的流形學習方法或其他降維方法產生很大區別，主要體現在優化上面。對於哈希編碼B，由於其是離散的，所以不能用傳統的梯度下降方法去解，這一問題是典型的混合整數問題，即NP hard（non-deterministic polynomial，NP，非確定性多項式）問題。因此我們往往需要放寬約束去掉離散的限制，將原問題轉化為拉氏特徵圖降維問題，引入PCA求解。如下所示：

  • Step1. 利用主成分分析（PCA）獲取圖像各個主成分方向；
  • Step2. 在各個主成分上利用 lambda_k=1-e^{-frac{epsilon^2}{2}|frac{kpi}{b-a}|^2} 計算特徵值，並以從小到大的順序選取前 r 個最小的值，計算其對應的特徵函數值 Phi_k(x)=sin(frac{pi}{2}+frac{kpi}{b-a}x) 。
  • 將特徵函數值在零點進行二元量化（sign函數）得到哈希編碼。

對於Hash的求解問題一般分為兩步。第一步去掉離散約束，這就變成了連續優化的問題，即可以通過傳統的梯度下降方法去求解，然而它的缺點是很難得到比較好的局部最優解。第一步通過去掉離散限制得到連續結果，第二步再通過設定閾值進行二值化操作，如符號函數。由此就得到了哈希碼。當然，也可以利用類似2011年提出的ITQ去減少量化損失。然而這種方法的缺點是對於長哈希碼（超過100比特），量化偏差將會很大，使得學出來的哈希碼不是十分很有效。

2.4 迭代量化（Iterative Quantization, ITQ）

ITQ主要思想是基於PCA採用正交旋轉矩陣對初始投影矩陣進行優化以減少誤差。ITQ的目標函數如下：

min quad ||B-XWR||_F^2=||B-VR||_F^2 s.t.quad R^TR=I,Bin {-1,1}^{n imes c} ag{4}

上式中， B 為學習所得Hash編碼；

X 為原始數據；

W 為PCA所得特徵值對應的特徵向量；

R 為旋轉矩陣（正交陣）。

圖9. ITQ

我們一般要求相似的數據擁有相同的編碼。從上圖中可以看出，簡單的PCA對於不同維度的數據其方差並不平衡，因此該方法並不能很好的滿足上述要求，通過隨機將PCA進行旋轉，都比原始PCA能取得更好的效果。這也是ITQ的Motivation，同時這也是ITQ對比SH的主要區別，即ITQ通過旋轉主成分方向使得旋轉後各方向的方差盡量保持平衡，而SH則為方差大的主成分方向分配更多的比特。

此外，由式（4）可以看出，目標函數中 B,R 均未知，因此我們需通過類似坐標下降的方法進行求解，即固定 B 優化 R ，固定 R 求解 B （類似EM演算法)，其過程如下：

固定 R 優化 B （對 B 求偏導等於0）:

T=VR,J(B)=sum_{i=1}^nsum_{j=1}^cB_{i,j}T_{i,h},B_{i,j}=egin{cases} 1,quad if;T_{i,j}geq0 -1,quad otherwise end{cases} ag{5}

固定 B 優化 R （對 R 求偏導等於0，orthogonal Procrustes problem）:

B^TV=SOmegahat{S}^T,R=hat{S}S^T ag{6}

  • Step1. 首先根據PCA對數據進行降維並對降維後的結果進行二值量化處理得到所有數據的初始哈希編碼，這樣原始數據即被嵌入到了漢明空間中，各數據位於超立方體的頂點上；
  • Step2. 對主成分方向進行一次隨機旋轉，可以較好的平衡不同主成分方向的方差，接著對編碼矩陣和旋轉矩陣進行交替優化，以最小化量化誤差為目標，旋轉若干次後將得到局部最優解。

圖10. ITQ實驗結果

由圖10可以明顯看出，隨著編碼長度的增加，ITQ的性能急劇下降，對於較長的編碼其難以保持明顯的優勢。

這裡通過Euclidean ground truth和Class label ground truth指標比較各種哈希的性能，如下：

圖11. Evalution of Hash

通過上圖我們可以看到各個Hash函數的性能和特點，同時為不同編碼任務Hash函數的選擇提供一定的參考依據。

2.5 在線哈希學習（Online Hashing）

在現實的絕大多數場景中，檢索系統中數據是流式的、不斷更新的，而對於超大規模數據，很難將其載入內存進行哈希函數學習，而且在線學習往往伴隨著超高的時間和計算代價。因此我們有必要研究出一種可行的方法，以較好的實現增量學習。對此SIGKDD 2013BP就給出了在線Hash學習的可行方法，即矩陣素描（Matrix Sketching）。

矩陣素描的基本思想是通過尋找和維護一個較小的矩陣 Bin R^{l imes m} ，代替線上較大的矩陣 Ain R^{n imes m}(l<< m) ，同時使兩者間的差值 ||A-B|| 最小，即儘可能的保留原始矩陣的大多數特性。此思想即類似SVD，即求解 A 的best top-k近似 A_k 。然而於SVD所不同的是，我們既希望找到最佳近似 B ，同時在時間複雜度上又要優於SVD， O(nm,min(n,m)) 。對此我們使用FD Streaming algorithm（Frequent Directions）。即應用FP從 l 到 A 以獲得$l$維的素描矩陣 B ，同時滿足：

0leq ||AA^T-BB^T||_2leq frac{2}{l}||A||^2_Fquad or quad 0leq ||A^Tx||^2-||BB^Tx||^2leq frac{2}{l}||A||^2_F\ forall x, ||x||=1 ag{7}

圖12. FB algorithm

3. 基於哈希的特徵匹配

通過Hash特徵匹配，我們主要能解決圖像搜索、三維重建、圖像分類、目標識別等問題。現有的特徵匹配主要有三大類方法，即Point matching, Line matching, Region matching（本質上均為Point matching）。下圖為三維重建的主要過程：

圖13. 3D Rebuild

可以看到Matching花費了大量時間，其時間複雜度為 O(N(N-1)M^2) ， N 為圖像總數， M^2 為圖像大小。為減少時間，除硬體加速外有必要研究有效的Hash演算法。

4. 乘積量化（product quantization, PQ）

PQ主要用於解決的重排序時的向量間距離的快速計算的問題。它的基本思想是將樣本特徵量化為 M 個碼字之和的形式，即分割向量，對分割後的向量空間建立獨立碼本；通過將高維向量分割成多個低維向量，達到節省存儲空間的目的；通過subvector-to-centroid的查表方式，達到降低計算複雜度的目的。

其具體操作為對所有相似的向量用一個質心（聚類中心）來表示，那麼我們可以提前將各質心間的距離計算出來，而在實時查詢時，只需得到查詢向量和被查詢向量各自的質心索引，即可以得到二者間的距離，這樣就避免了在線的實時計算，滿足了實時性的要求。而對於高維浮點向量，其能夠大大減少重排序時間。而為獲得有效的結果，我們一般要求各個質心能過儘可能的代表各自樣本點，即期望質心數目儘可能多（當每個樣本均為一質心時將不存在誤差，但不合理），而數目較多的質心將帶來計算和存儲的巨大成本。對此，作者提出乘積量化，即將輸入向量分割為長度較短的子向量，而對每個子向量進行獨立的量化（聚類），並建立量化後的質心索引，即碼字，各子向量碼字的集合構成該輸入向量的碼本。同時將輸入向量的質心用各碼字的乘積表示，如下：

q(x)=sum_{m=1}^Mq_m(x),q_m(x)in C_m ag{8}

其優化目標為最小化量化誤差：

min_{C-1,...C_M}sum_M||x-q(x)||_2^2 ag{9}

即：

min_{C_m}sum_x||u_m(x)-q_m(x)||_2^2 ag{10}

圖14. 乘積量化

由於其時間複雜度為 O(TkND) ，因此難以應用於大規模數據集。

5. 基於量化的CNN加速與壓縮

由上知長向量可由其對應質心表示，而長向量質心的計算可拆分為多個短向量質心的乘積。因此我們通過對短向量進行聚類求得碼字，即可通過查錶快速獲取長向量的碼本。基於此，長向量間的乘積可以表示為短向量乘積的和，而短向量可通過建表查取，這樣即大大縮短了時間。基於此，即可對CNN進行量化加速與壓縮。

如圖15所示，總所周知，CNN網路的參數主要集中於全連接層，而運算時間主要集中於卷積層，因此為加速、壓縮網路，我們需對其分別進行處理。

圖15. 卷積層與全連接層參數數目與運算

（1）Fully-connected layer

T(c_t)=<W_{c_t},S>=sum_{m=1}^M<W_{c_t}^{(m)},S^{(m)}>approx sum_{m=1}^M<D^{(m)}B_{c_t}^{(m)},S^{(m)}> \where,W_{c_t}^{(m)}in R^{Cs imes l},D^{(m)in R{C_s imes K}},B{c_t}^{(m)}in {0,1}^{K imes l} ag{11}

使用PQ方法量化。將權重矩陣 W 均勻地分成 M 個子空間，對每個子空間使用K-means演算法得到碼字，其中 D 為碼本，包含 K 個子碼字。 B 中的每一列是指示矢量，指定哪個子碼字用於量化相應的子向量。全連接層結構如下：

圖16. 全連接層結構圖

通過量化操作，可將 S^{(m)}cdot D^{(m)} 的結果記錄，此後每次計算只需要 M 次加法運算，演算法複雜度由原來的 O(C_sC_t) 減少為 O(C_sK+C_tM) 。而且，只需要存儲sub-codebook D 和量化指示器 B ，可節約很大的存儲開銷。

（1）Conv layer

與全連接層中的1-D矢量不同，每個卷積核均為3維向量。故在量化前，我們需要確定如何將其分割為子向量，即將子空間分割應用於哪個維度。在測試階段，每個卷積核在空間域中使用滑動窗口遍歷輸入特徵圖。由於這些滑動窗口部分重疊，故沿特徵映射通道的維度拆分每個卷積核，以便計算的內積可以在多個空間位置重複使用。優化同樣通過每個子空間中的K-means聚類實現。

T_{pt}(c_t)=sum_{(p_k,p_s)}<W_{c_t,p_k},S_{p_s}>=sum_{p_k,p_s}sum_{m=1}^M<W_{c_t,p_k}^{(m)},S^{(m)}_{p_s}>approx sum_{p_k,p_s}sum_{m=1}^M<D^{(m)}B_{c_t,p_k}^{(m)},S^{(m)}_{p_s}> \where,W_{c_t,p_k}^{(m)}in R^{Cs imes C_t},D^{(m)in R{C_s imes K}},B{c_t,p_k}^{(m)}in {0,1}^{K imes C_t} ag{12}

圖17. 卷積層結構圖

網路的目標函數即為：

  • 最小化網路參數的量化誤差

min_{D,B}||W- ilde W||_F^2 s.t. ilde W=g(D,B) ag{13}

  • 最小化網路輸出的近似誤差

min_{D,B}||f(X;W)-f(X; ilde W)||_F^2 s.t. ilde W=g(D,B) ag{14}

最後需要指出的是，由於權值的近似表示因此存在累積誤差問題，即網路中淺層的參數被量化後，會改變深層的輸入，我們需要對其進行修正，在此不對其進行展開。

綜上可以看出，排序與索引是檢索和推薦的本質問題，其正在走向成熟但仍方興未艾。另外隨著深度學習的崛起，其在檢索問題上得到了越來越多的應用。

References

[1] S. Brin, L. Page: The Anatomy of a Large-scale Hypertextual Web Search Engine Computer Networks and ISDN Systems. WWW 1998

[2] J.M.Kleinberg. Authoritative sources in a hyperlinked environment. Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

[3] P.Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. STOC』98

[[4] Dasgupta S , Stevens C F , Navlakha S . A neural algorithm for a fundamental computing problem[J]. Science, 2017, 358(6364):793-796.](biorxiv.org/content/bio)

[5] R.Salakhutdinov and G.Hinton. Semantic hashing. SIGIR 2007 workshop

[6] Y. Weiss, A.B. Torralba, and R. Fergus. Spectral hashing. NIPS 2008

[7] Yunchao Gong, et.al.Iterative Quantization: A Procrustean Approach to Learning Binary Codes for Large-scale Large Retreival. CVPR 2011, IEEE TPAMI 2013.

[8] Edo Liberty, 「Simple and Deterministic Matrix Sketching」. SIGKDD 2013

[9] Jiaxiang Wu, et al., 「Quantized Convolutional Neural Networks for Mobile Devices」. CVPR 2016


推薦閱讀：
相關文章