基于偽逆的局部保留迭代哈希

杜仲舒 王永利 趙 亮

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

隨著互聯網時代的高速發展，產生的數據和其維度不斷增加，快速準確地檢索大量的高維數據越來越成為一個嚴峻的挑戰。在解決這些問題的過程中，哈希學習受到了越來越多的人的關注。哈希學習將原始數據映射到一個二進制向量中，可以加快信息的查詢檢索速度，已經廣泛應用于圖像識別，數據挖掘，模式識別等領域。

局部敏感哈希算法（Locality Sensitive Hashing，LSH）是一種常見的近似最近鄰哈希算法［1］，尤其是在高維且數據量很大的情況下，很多傳統哈希算法都會陷入“維數災難”，而局部敏感哈希算法卻能很好地克服這個問題，因此在音頻識別，視頻識別，網頁去重，DNA序列相似比較等方向應用廣泛。原始的lsh算法只是在漢明距離下進行處理。國內Li等提出了P-穩定分布（p-stable）的局部敏感哈希，將原始的漢明距離擴充到了歐式空間。

Yair等提出了譜哈希（Spectral hashing），把對數據特征向量的編碼過程作為對圖的分割問題來解決［4］。圖的分割問題是一個NP難題，但是可以求出其松弛解，即的利用相似圖的拉普拉斯矩陣求得陣特征值和特征向量，將原始特征降維。

Jae-Pil等提出了球哈希（Spherical Hashing）［6］，使用超球平面代替超平面劃分原始數據，原始特征空間Rd被球心為c和半徑為R的超球面劃分為球內和球外兩個部分。由于超球面具有更強的區分性，超平面可以看做超球面半徑無限大的特殊情況，球哈希提升了對高維數據檢索的正確率。

本文提出了基于偽逆的局部保留迭代哈希（Pseudo-inverse locality preserving iterative hashing，PLIH）算法，構建鄰接圖并最小化近鄰在低維空間的距離使得投影后的矩陣可以保持高維的近鄰關系，解決了局部敏感哈希等無法有效保留高維近鄰關系的問題。同時，采用偽逆替代逆矩陣解決了矩陣奇異的情況下求解投影矩陣失效的問題。最后通過迭代量化盡可能降低了投影矩陣在量化過程中的損失，通過與其他哈希算法在公開數據集上的比較，發現正確率和召回率都有5%～10%的提升，證明了該算法的可行性。

2 基于偽逆的局部保留迭代哈希算法

2.1 算法介紹

本文中哈希算法分為兩個步驟，首先將高維數據進行投影，然后對投影后的數據進行量化。基于偽逆的局部保留迭代哈希（pseudo-inverse locality preserving iterative hashing），核心思想是利用數據點之間的近鄰關系將高維數據中的非線性數據映射到低維空間，使其近鄰關系保持較小誤差。

2.1.1 基于偽逆的局部保投影

根據原始數據的近鄰關系構建鄰接矩陣，當出現以下情況可判定向量xi與xj鄰接：

1）球形相近。當兩個向量之間的距離小于ε。

2）K近鄰相近。即一個向量在另一個向量的前K近鄰中。

3）指定相近。在有監督情況下，兩個向量已知是屬于同一個類別。

構造權值矩陣W，使用熱核計算方式：

為了保持近鄰關系，最小化投影后的誤差，有如下目標函數：

其中 yi和 yj是投影后得到的向量，Wij為鄰接矩陣的權值。

為了求解上述目標函數，假定a是投影向量，y表示原始向量X經過a投影后的向量，我們有：

不失一般性，構建約束yTDy=1，目標函數

即 XDXT不滿秩，故 XDXT不存在逆矩陣，出現奇異的情況。因此這里使用偽逆來解決不存在逆的情況，即投影矩陣為(XDXT)+XWXT。偽逆求解過程如式（8～10）。進行svd分解后獲取奇異值中非零元素求倒數，重新組織后得到偽逆。

因此，基于偽逆的局部保投影可以保證投影過程的魯棒性，解決采樣率不足情況下不存在逆矩陣的情況，同時有效保持原始數據中的近鄰關系。

2.1.2 迭代量化

對于給定一個投影得到的固定維度的向量Y，需要將其量化到一個二進制向量B。由于傳統方法更多地關注于投影方法的優化，而忽略了量化的過程。傳統的方法使用零作為量化的閾值，很容易就能將其二進制量化為sgn(Y)，但是這樣量化會影響哈希的準確度，因為量化過程中，很多信息通過量化損失掉了，所以很有必要提出一種更有效的量化方案。

PLIH中的迭代量化過程可看做使用超立方體來近似樣本點的過程，對Y施加一個正交變換可以保持原有的距離關系。為了減少量化損失，我們將量化的目標函數表示為

這里的B∈{-1。1}n*c，c是二進制串的長度，R為旋轉矩陣。二維空間中直接以均值0為閾值的量化方法，隨機旋轉的投影和PLIH中使用的迭代量化的量化結果如下：

圖1 閾值為零量化，隨機旋轉的投影量化PLIH中使用的迭代量化

1）固定R更新B。

由于正交投影矩陣R是固定的，因此最小化方程等價于：

不難驗證，問題的最優解可以取正交變換后的正負符號函數即可，即B=sgn(YRλ)。

2）固定B更新R。

對于固定的B，目標函數對應于傳統的普羅克汝斯忒斯正交問題，即尋找一個最佳的旋轉方向來對齊所有的點。問題轉化為

由矩陣分析理論得到，原問題等價于最大化矩陣秩的問題，即max tr(BμRY)，s.t.RTR=I。由于Bμ是固定量，使用奇異值分解，令BTY=UΩVT，可得R=VUT是一個最優解。迭代交替更新B和R，便可以找到全局最優的量化方案滿足目標函數，最小化量化過程中的信息損失。

2.2 PLIH算法流程

3 實驗及結果分析

實驗平臺為Matlab2016a，算法在cpu為3.2GHz、內存為16G的計算機上運行。實驗采用了經典的gist_CIFAR和cnn_Caltech數據集，對比了經典的哈希算法和目前效果相對較好的近似最近鄰 算 法 ，例 如 ITQ，LSH，PCAH，SH，PCA-RR，DSH，SpH［10～15］等算法。

ITQ是基于PCA降維的迭代量化算法，LSH使用的是從高維正態分布中產生隨機矩陣的方法，SPH降維采用的是將高維向量投影到超球面的算法。從實驗結果可以看到，PLIH相對其他算法正確率與召回率都有較大的提升，尤其在比特位數較少時優勢更為明顯，證明了PLIH可以有效地保留近鄰間的相似關系。

圖2 gist_CIFAR數據集上多種哈希算法的正確率與召回率

圖3 cnn_Caltech數據集上多種哈希算法的正確率與召回率

4 結語

在本文中，提出了一種新的近似最近鄰檢索算法，可以有效保持數據的近鄰關系，同時解決了哈希過程中的矩陣奇異和量化損失較大的問題。實驗證明，基于偽逆的局部保留迭代量化算法的具有良好的效果。本文中的哈希方法是線性正交的，部分高維數據中的數據并不一定可以在線性空間中得到有效表示，因此接下來的工作可以關注非線性的數據特征處理，以便獲得更高的正確率和召回率。