作者 | 蔣寶尚
編輯 | 叢 末
越來越多的數據流，讓視覺相似度檢索在應用場景中越來越難，例如微信每天都會產生十幾億甚至上百億的流數據網絡圖片，給相似圖片搜索帶來了挑戰。而視覺哈希編碼技術逐漸成為實現相似性檢索的有效途徑。
近日，廈門大學紀榮嶸關於在線哈希學習新方法的論文被發表在 IJCV 上，在論文中紀教授引入哈達瑪矩陣指導哈希函數的學習，即吸取了傳統在線哈希方法的優點，也最大程度上降低了精度損失。另外，對比當前最先進的七種技術，引入哈達瑪矩陣的在線哈希學習都有一定程度的性能提高。
論文地址：
https://arxiv.org/pdf/1905.04454.pdf
最近鄰搜索在搜索領域一夫當關，作為一種找尋最優點的思路，在很多領域中都有很廣泛應用，如：計算機視覺、信息檢索、數據挖掘、機器學習，大規模學習等。
但最近鄰搜索有兩個關鍵問題：1、特徵維度較高；2、數據量較大。例如，簡單的窮盡搜索，需要將原始數據從存儲中加載到內存，這將面臨非常高的時間複雜度，成為現實應用中所必須解決需要解決的一個瓶頸問題。
為解決這個問題，近年來，在實際應用中出現了一些時間複雜度為次線性的、快速有效的最近鄰搜索方法，例如KD樹、Ball樹、Metric樹。但基於樹的方法需要的存儲空間往往很大，在某些時候存儲這些索引樹的空間甚至超過存儲數據本身所需的存儲空間。
不同於基於樹的索引將數據空間進行遞歸的劃分，哈希類算法重複的對整個數據空間進行二類劃分，同時對於每一個劃分進行一次二值編碼。
即哈希算法將輸入數據映射到一個離散的漢明空間，每一個數據點用一串二值碼表示。漢明距離可以通過異或操作進行快速計算，因此使用哈希碼對資料庫進行窮盡檢索，時間複雜度也能滿足應用要求。
所以，哈希算法成為解決最近鄰搜索的希望之一。而最近鄰搜索思路在視覺相似度領域的應用也推動著哈希算法解決視覺相似性難題。
更進一步，網絡數據流源源不斷地產生使得資料庫急劇增長，在線哈希學習成為減少視覺哈希編碼複雜度不可或缺的技術途徑。
吸取了傳統在線哈希方法的優點，廈門大學的紀榮嶸，林明寶兩位老師，引入哈達瑪矩陣在線學習哈希函數，通過用Sylvester方法構造的正交二進位矩陣，其在一定程度上克服了強約束、需要大量的訓練批次的困境。
此項工作日前已經發表在International Journal of Computer Vision（ 國際計算機視覺雜誌）期刊上。作為人工智慧領域最重要的頂級學術期刊之一，IJCV 每年出版的文章數量極小，但卻擁有較高的影響因子（5年影響因子為12.389）。
方法介紹
根據紀教授在論文中介紹，這項方法被稱為：哈達瑪矩陣指導下的線哈希學習。旨在解決解決大規模流數據問題。方法的創新點在於引入哈達瑪矩陣，矩陣中的每一列都作為目標代碼來指導哈希函數的學習。
註：哈達瑪矩陣，英文為Hadamard Matrix，定義是由+1和-1元素構成的且滿足Hn*Hn』=nI（這裡Hn』為Hn的轉置，I為單位方陣）n階方陣。
不同於傳統的方法，該方案進行哈希編碼的時候僅僅只需要利用當前階段的流數據，因此學習效率在每一階段都是恆等的。為此，作者把具有正交性質的哈達瑪矩陣作為同一類流數據的目標編碼，目標編碼進一步作為感知機的虛擬類別來學習分類器。
另外，需要的訓練設備要求較低，對於內存的需求僅需要滿足一對數據的大小盡可，基於數據對的訓練方式又極大壓縮了訓練時間的消耗。
為了釋放強約束的需要，作者將哈達瑪矩陣的每一列作為每個類標籤的目標碼，它本質上滿足哈希碼的幾個期望性質。由於目標編碼是已知的，不需要去設計很複雜的約束性條件。相比於目前已有的最佳方法，所題方案以更少的訓練時間，在不同的數據集（CIFAR-10， Places205， MNIST、NUS-WIDE四個經典數據集）下獲得10%～30%的精度增長，該技術可應用於大規模城市視覺目標布控、特定網絡產品查找等。
方法細節
在線哈希框架：數據到來→在漢明空間中學習目標碼→學習獨立的二進位分類器進行預測
哈希學習的目的是學習一系列哈希編碼，使得期望的鄰域結構被保留。通過用一組哈希函數對數據集進行投影來達到此目標。
註：B是學習目標，即哈希編碼，H(x)是哈希函數，X是數據集，sign 是符號函數，W是投影矩陣。
定義完學習目標之後，作者使用核技巧來利用線性模型的優勢，同時使它們能夠捕獲非線性數據模型。具體而言，通過基於錨點的核函數將原始空間中的數據映射到特徵空間，然後數據Xi有了一種新的表示，如下：
註：下標m，代表有m個錨點。
為了獲得這些錨，作者假設了在初始階段有m個數據點可用。因為在收集到m個數據點之前，學習過程不會開始。所以這m個數據點被認為是內核技巧中使用的m個錨。另外，在核函數方面，作者使用了高斯徑向基函數核。例如：
註：η2 被定義為在學習過程中需要調整的寬度。
整個算法的流程如上圖所示。其中，W-ensemble為：
註：π^t是可調參數，作者設置 π^t=1/T
實驗
在實驗部分，作者使用了幾種最先進的方法進行了大規模的圖像檢索實驗，用到了四個廣泛使用的數據集，即CIFAR-10、 Places205、MNIST、NUS-WIDE。
CIFAR-10：該數據集共有60000張彩色圖像，這些圖像是32*32，分為10個類，每類6000張圖。作者將整個數據集分為59K圖像檢索集，以及1000圖像的測試集。此外，作者從從檢索集中隨機抽取20000張圖像組成訓練集來學習哈希函數。
Places205：作為Places 數據集的一個子數據集，裡面包含250萬張圖像，205個場景類別。作者首先從AlexNet的FC7層提取每個圖像的特徵，然後通過執行PCA將其表示為128維特徵。為了拆分整個數據集，作者從每個類別中隨機選擇20個實例，其餘的被視為檢索集。最後，使用檢索集中的100K圖像的隨機子集來更新哈希函數。
MNIST：數據集包含從0到9的70000手寫數字圖像。每個圖像均由784像素的歸一化原始像素表示。作者將數據集分為一個測試集，一個檢索集。
NUS-WIDE：從Flickr收集，包含296648張圖，共有81個標籤，作者根據前10個頻繁標籤從整個數據集中保留了186577張標記圖像，其中2000幅圖像作為查詢集，其餘的作為檢索集。並從檢索集中隨機抽取40000張圖像作為訓練集。
評價指標有兩個，分別為：mAP（ mean Average Precision）、Precision@H2（Precision within a Hamming ball of radius 2）。比較的基準方法有七個，分別為：OKH、SketchHash、AdaptHash、OSH、MIHash、BSODH、HCOH。
在CIFAR-10中mAP、 Precision指標的性能表現如上。
在CIFAR-10數據集的mAP指標上，除了在48-bit的實驗中，HCOH略勝HMOH一籌。其他實驗都是HMOH更加優秀。而在Precision@H2指標下，HMOH超越了所有的SOTA方法。
在Places205中mAP、 Precision指標的性能表現如上。
在Places205數據集中，mAP指標下，HMOH勝過了所有的SOTA方法。在Precision@H2指標下，HMOH輸給了MIHash。
在MNIST中mAP、 Precision指標的性能表現如上。
在MNIST數據集中，mAP指標下，HMOH勝過了所有的SOTA方法，在Precision@H2指標下，HMOH輸給了MIHash。
在NUS-WIDE 中mAP、 Precision@H2指標的性能表現如上。
在NUS-WIDE數據集中，兩個指標的表現中，HMOH勝過了所有的SOTA方法。