用決策樹處理高維數(shù)據(jù)的一種快速監(jiān)督性哈希

【摘要】監(jiān)督性哈希旨在將原始特征映射成為能夠保護漢明空間中基于標簽的相似性的緊湊二進制編碼耸别。非線性哈希函數(shù)由于其強大的泛化能力而優(yōu)于線性哈希函數(shù)。研究表明，核函數(shù)通常用來實現(xiàn)哈希中的非線性，并且以較緩慢的評估和訓練時間作為代價可以實現(xiàn)良好的檢索性能。本文分析了一種使用決策樹來實現(xiàn)哈希的非線性方法，其評估和訓練的速度快吐根。首先提出對于哈希二進制編碼推論問題的子模塊公式化，和一種對于解決大規(guī)模推論的基于塊搜索方法的高效圖分割法辐马。然后通過訓練優(yōu)化的決策樹來學習哈希函數(shù)使得適用于二進制編碼拷橘，并通過實驗對以上算法進行了分析和結果的探討。

【關鍵字】決策樹監(jiān)督性哈希 高維數(shù)據(jù)

1引言

哈希方法構造一系列的哈希函數(shù)，將原始的特征映射成為緊湊的二進制代碼冗疮。哈希能夠通過使用查找表或者基于排名的漢明空間實現(xiàn)快速的搜索萄唇。并且，緊湊的二進制代碼對于大規(guī)模的數(shù)據(jù)存儲非常有效赌厅。類似的應用有圖像檢索，大型對象檢測等等轿塔。哈希方法旨在保留漢明空間中的一些概念的相似度或者稱之為距離特愿。這些方法可以被粗略地分為監(jiān)督性方法和非監(jiān)督性的方法。非監(jiān)督性的方法努力保留原始特征空間的相似度勾缭。例如揍障，局部敏感哈希（Locality-Sensitive Hashing, LSH）隨機生成線性哈希函數(shù)來近似余弦相似度[1];譜哈希（SpectralHashing）學習保留高斯關聯(lián)性的特征函數(shù)[2]；迭代量化（Iterative Quantization, ITQ）近似漢明空間中的歐氏距離[3]俩由；在流形結構上的散列將內(nèi)在流形結構考慮進去毒嫡。

監(jiān)督性的哈希被設計來保留一些基于標簽的相似性。比如幻梯，這個可能發(fā)生在來自同一類型的圖片被定義為彼此語義相似的情形兜畸。近年來，監(jiān)督性哈希受到了越來越多的關注碘梢，比如有內(nèi)核的監(jiān)督哈希（KSH）[4]咬摇，兩步哈希（TSH）[5]，二進制重建嵌入（BRE）[6]等煞躬。盡管監(jiān)督性哈希對于現(xiàn)實應用更加靈活和吸引人肛鹏，但是其學習速率比起非監(jiān)督性哈希慢了許多。盡管現(xiàn)實情況是恩沛，哈希只有在被應用到大量的高維特征時才有著實用利益在扰，大部分的監(jiān)督性哈希方法僅僅被展示在相對小數(shù)目的低維特征上。比如雷客，基于特征的碼本在圖像分類上獲得了巨大的成功芒珠，其特征維數(shù)通常達到了數(shù)以萬計[7]。為了利用這個特征學習的最新進展搅裙，對于監(jiān)督性哈希能夠在復雜的高維特征上有效處理大規(guī)模數(shù)據(jù)是非常需要的妓局。為了填補這個差距，因此希望有一個監(jiān)督性的哈希方法呈宇，能夠利用大的訓練集并有效利用高維特征好爬。

非線性哈希函數(shù)，例如在KSH和TSH中使用到的核哈希函數(shù)甥啄，展示了比線性哈希函數(shù)很大的性能改進存炮。然而循集，核函數(shù)對于在高維特征上的訓練和測試的代價非常高姻报。因此，一個有著非線性哈希函數(shù)的可擴展監(jiān)督性哈希方法也是非常需要的。

2問題提出與分析

令χ?= {x1,x2,...xn}?

表示一系列的訓練點文留。基于標簽的相似性信息保存在一個關聯(lián)矩陣Y中舞终，也就是監(jiān)督性學習中的參考標準废膘。Y中的元素表示兩個數(shù)據(jù)點和的相似度，且?=般又。特別地彼绷，如果兩個點相似則=1，如果兩個點不相似則= -1茴迁，如果兩者之間的關系沒有被定義寄悯，則= 0。目標是學習一組哈希函數(shù)來保留漢明空間中基于標簽的相似性堕义。m個哈希函數(shù)表示成：. 哈希函數(shù)的輸出是m位的二進制代碼:猜旬。漢明關聯(lián)性與漢明距離密切相關，是通過兩個二進制編碼的內(nèi)積來計算的倦卖，計算公式為洒擦。與KSH相似，基于漢明關聯(lián)性來公式化哈希學習怕膛，使得相似數(shù)據(jù)對的關聯(lián)性值為正秘遏，不相似數(shù)據(jù)對的關聯(lián)性值為負。優(yōu)化過程可以寫為：

????????????

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????? （1）

???????? 其中嘉竟，

用來避免未定義的數(shù)據(jù)對關系影響哈希的任務邦危。因為如果關系沒有定義的話，=0舍扰，否則倦蚪，=1。因為使用決策樹來作為哈希函數(shù)边苹，因此定義每一個哈希函數(shù)為決策樹的一個線性組合陵且，即

????????????????

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????（2）

其中，Q是決策樹的數(shù)量个束。

表示有二進制輸出的一個樹函數(shù)慕购。權重和樹是用來學習一個哈希函數(shù)的參數(shù)。與核方法相比茬底，決策樹有著高維數(shù)據(jù)上更快的測試速度和非線性的適應能力沪悲。

直接學習決策樹優(yōu)化（1）顯得比較困難，因此添加了輔助變量

作為在處的第k個哈希函數(shù)的輸出阱表，即有殿如。顯然贡珊，是第i個數(shù)據(jù)點在第k位的二進制編碼。有了這個輔助變量涉馁，（1）式就可以分解為兩個子問題：

???????????????????

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??（3a）

???????????????????????

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??????（3b）

其中Z是所有訓練數(shù)據(jù)點的m位二進制的矩陣门岔。式（3a）是一個二進制代碼推理問題，式（3b）是一個簡單的二分類問題烤送。這樣寒随，原本復雜的監(jiān)督性哈希的決策樹學習就轉化為兩個相對簡單的任務——解（3a）（步驟1）和（3b）（步驟2）。

步驟1：二進制代碼推理

對于式（3a）帮坚，順序優(yōu)化妻往，一次優(yōu)化一位，調節(jié)之前的位叶沛。當優(yōu)化第k位時蒲讯，（3a）的代價可以表示為：

? ? ??? ? ? ?

??（4）

因此忘朝，對于第k位的優(yōu)化可以等價公式化為一個二進制二次規(guī)劃問題：

???????????????

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（5a）

其中灰署，???????

? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （5b）

這里

的表示前面位的二進制代碼。使用一個階段性的方案來解決每一位局嘁。特別地溉箕，當?shù)降趉位時，位的長度設為k而不是m悦昵。這樣肴茄，當前位的優(yōu)化就取決于前面位產(chǎn)生的損失，通常這樣的優(yōu)化可以取得更好的推理結果但指。

由于該方法是需要處理高維的數(shù)據(jù)寡痰，因此采用一種對于二進制編碼推論問題的子模塊公式化，和一種有效地解決大規(guī)模的推理的基于塊搜索的圖分割方法棋凳。首先將數(shù)據(jù)點分成很多塊拦坠，然后一次優(yōu)化一個塊的對應變量，同時調節(jié)剩下的變量剩岳。令??表示數(shù)據(jù)點的一個塊贞滨。那么（5a）的代價可以表示為：

? ? ? ? ? ??

? ? ? ? ? ? ? ? ?（6）

當優(yōu)化一個塊的時候，那些不存在目標塊中的變量被設為常量拍棕。因此晓铆，對于一個塊的優(yōu)化也可以寫成：

??????? ?

? ? ? ? ? ? ? ? ? ??（7）

其中，表示不包含在目標塊中的第k位的二進制編碼绰播。加上（5b）中對的定義骄噪，對于一個塊的優(yōu)化可以寫成：

????????????

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（8a）

其中，

? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （8b）

? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ?（8c）

這里蠢箩，

和都是常量腰池。構建一個塊的關鍵是保證這樣一個塊的（8a）是子模塊化的尾组，因此這里可以應用有效的圖分割法。實現(xiàn)算法（算法1）如下：

輸入：關聯(lián)矩陣：Y示弓；位長度：k讳侨；最大推理迭代；塊集：

奏属；二進制碼:

輸出：一位的二進制碼：

重復：

隨機轉置所有的塊

對于每一個塊

：

???使用圖分割對每一個

進行（8a）的推論

???直到達到最大的迭代次數(shù)

特別地跨跨，在這個哈希問題中，通過利用相似度信息囱皿，可以很容易地構建滿足子模塊化要求的塊勇婴，并引出如下命題。

命題1

如果嘱腥，（8a）中的優(yōu)化是一個子模塊化的問題耕渴。換句話說，對于塊中的任意數(shù)據(jù)點齿兔，如果它不是與塊中其他任意的數(shù)據(jù)點都不相似橱脸，那么（8a）就是子模塊化的。

證明：如果

分苇，成立添诉。那么，医寿。令栏赴，那么有?；?靖秩。因此须眷，? ，沟突，因此證明了（8a）的子模塊性花颗。

只要滿足命題1的條件，一個塊可以使用許多種方式構建事扭。一個簡單的構造塊的貪心算法（算法2）實現(xiàn)如下：?

輸入：訓練數(shù)據(jù)點：

?捎稚，關聯(lián)矩陣Y

輸出：塊：

重復：

t= t + 1；

求橄；：從V中隨機選擇今野；

初始化U為V和

的相似案例的并集；

對于U中的任何一個

：

???如果

與中的任何點都不相似罐农，那么

???????將

加到中条霜；將從V中移除

???直到V =?

需要注意的是，塊可以覆蓋涵亏，它們的并集需要覆蓋所有n個變量宰睡。蒲凶，

步驟2：學習作為哈希函數(shù)的決策樹

對于（3b）中的二分類問題，通常0-1損失被一些凸代理損失替代拆内。這里旋圆，使用對于提升方法常用的指數(shù)型損耗。學習第k個哈希函數(shù)的分類問題可以寫為：

??????????????

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??（9）

這一步應用Adaboost來解決以上問題麸恍。在每一個提升的迭代中灵巧，一棵決策樹和它的權重系數(shù)被學習。一棵二叉決策樹的每一個節(jié)點是一個決策樹樁抹沪。訓練一個樹樁是為了找到一個特征維和最小化權重分類誤差的閾值刻肄。從這點上看，該方法是在同時進行特征選擇和哈希函數(shù)的學習融欧∶羝可以簡單利用已有可用的有效決策樹學習技術來提高訓練速度。最終使用一種高效的樹樁實現(xiàn)算法[8]噪馏，比傳統(tǒng)的方法大約快了10倍麦到；特征量化能夠在實踐中無性能損失地大大提高訓練速度，并且能大大減少內(nèi)存消耗逝薪。線性量化特征值為256個容器隅要；應用權重修剪技術蝴罪，在每一個提升迭代中董济，最小的10%權重被修剪掉（被設置為0）；應用了LazyBoost技術：只有隨機選取的特征維的一部分在樹節(jié)點分裂中被評估使用要门。

因此虏肾，快速哈希方法的過程就可以表述為如下算法（算法3），實現(xiàn)過程如下：

輸入：訓練數(shù)據(jù)點：

欢搜；關聯(lián)矩陣Y封豪；位長度：m；塊：.

輸出：哈希函數(shù)：

.

對于k = 1,…,m,

???第一步：調用算法1得到第k位的二進制碼炒瘟；

???第二步：訓練（9）中的樹得到哈希函數(shù)

吹埠；

???通過

的輸出更新第k位的二進制碼；

對于每一位疮装，二進制碼通過應用學習的哈希函數(shù)被更新缘琅。學習過的哈希函數(shù)能夠對下一個的二進制碼推論做出反饋，能夠得到更好的性能廓推。

3實驗分析

實驗所用編程語言為MATLAB刷袍，使用MATLAB的軟件版本為MATLAB R2014b，數(shù)據(jù)集是采用MNIST進行訓練和優(yōu)化樊展。MNIST是一個手寫數(shù)字識別的數(shù)據(jù)集呻纹，包含60000個訓練樣本堆生，10000個測試樣本，是一個更大的數(shù)據(jù)集合NIST的一個子集雷酪。

在訓練之前淑仆，需要生成數(shù)據(jù)的關聯(lián)標簽矩陣，即之前提到的Y哥力。接著糯景，為下面步驟的基于塊的圖分割生成推斷塊。至此省骂，預處理結束蟀淮。

接下來訓練前參數(shù)的配置。實驗所選用的二進制推斷方法是基于塊的Grapg-Cut方法钞澳，迭代次數(shù)為2怠惶。損失函數(shù)使用的是Hinge函數(shù)。針對步驟2中的分類器的設定轧粟，實驗中使用的是boost_tree, boosting的迭代次數(shù)為200次策治，決策樹的深度需要不斷測試和修建，本實驗室中決策樹的深度設置為4兰吟，通常決策樹的深度越深通惫，得到的精度越好，但是訓練速度會越慢混蔼。大的數(shù)據(jù)集需要要求更深的深度履腋。對于權重的調整，一般取值為0.9~0.99之間惭嚣，值越大遵湖，得到的精度越高，但是會減慢訓練速度晚吞。該實驗取值為0.99延旧。lazyboost設置中，樹節(jié)點分割的維度為200槽地。

實驗最后的檢索精度有三種方式衡量：得到的檢索樣本前K個的正確率（也就是實驗結果的縱坐標——精確度）迁沫，平均準確率（MAP）和精確度-召回曲線下的面積。實驗采用第一種尺度來衡量精確度捌蚊，其中K取值100集畅。橫坐標是采用哈希決策樹函數(shù)映射的二進制碼位數(shù)，分別取2,4,6,8位逢勾，也可以取其他的值牡整。

實驗運行結果如下圖1所示：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

圖1- 快速哈希的檢索實驗結果

???從實驗的圖形走勢可以看出，隨著位的數(shù)量增大溺拱，檢索的精確度也隨之提高逃贝，在bit位的數(shù)量達到8的時候谣辞，精確度已經(jīng)達到94.1%。事實上沐扳，通過反復實驗泥从，最后也發(fā)現(xiàn)，實驗的精確度在bit位數(shù)為8時穩(wěn)定在0.937以上沪摄。

參考文獻

[1]A. Gionis, P. Indyk,and R. Motwani. Similarity search in high dimensions via?hashing. In Proc. Int. Conf. Very Large Data Bases (VLDB), 1999.1, 7

[2]Y. Weiss, R. Fergus,and A. Torralba.Multidimensional spectral hashing. In?Proc. Eur. Conf. Comp. Vis. (ECCV), 2012. 1, 7

[3]Y. Gong, S. Lazebnik,A. Gordo, and F. Perronnin. Iterative quantization: a?procrustean approach to learning binary codes for large-scaleimage retrieval.?IEEE T. Pattern Analysis Mach. Intelli. (TPAMI), 2012. 1, 7

[4]W. Liu, J.Wang, R. Ji,Y. Jiang, and S. Chang. Supervised hashing with kernels.?In Proc. IEEE Conf. Comp. Vis. Pattern Recogn. (CVPR), 2012. 1,2, 4, 6

[5]G. Lin, C. Shen, D.Suter, and A. van den Hengel. A general two-step approach?to learning-based hashing. In Proc. Int. Conf. Comp. Vis.(ICCV), 2013. 1, 2,?4, 5