快速近似近鄰檢索的哈希方法研究.pdf

1、隨著互聯(lián)網(wǎng)的普及，過去的幾年里，網(wǎng)絡(luò)上的數(shù)據(jù)快速增長。對(duì)機(jī)器學(xué)習(xí)來說，大量的數(shù)據(jù)意味著可以訓(xùn)練更加復(fù)雜的模型，模型的泛化能力也得到提高，但同時(shí)，模型在訓(xùn)練和使用階段的計(jì)算和時(shí)間代價(jià)使某些機(jī)器學(xué)習(xí)算法面臨較大的可用性問題。特別的，KNN檢索作為機(jī)器學(xué)習(xí)領(lǐng)域經(jīng)常用到的一種基本算法，大規(guī)模數(shù)據(jù)集上簡單的線性搜索會(huì)消耗大量時(shí)間。哈希算法作為最有效的近似近鄰檢索方法之一，能有效權(quán)衡檢索速度和檢索準(zhǔn)確度，在過去幾年時(shí)間里得到了國內(nèi)外學(xué)者越來越多的關(guān)

2、注。
　　另一方面，網(wǎng)絡(luò)上的很多對(duì)象同時(shí)包含多個(gè)模態(tài)進(jìn)行展示，例如微博通常同時(shí)包括文本和圖片，或者文本和視頻。隨著多模態(tài)數(shù)據(jù)的增多，在學(xué)術(shù)和工業(yè)上，跨模態(tài)檢索逐漸成為一個(gè)新的需求。由于不同模態(tài)的數(shù)據(jù)往往有不同維度的特征，目前常用的方法是把不同模態(tài)的數(shù)據(jù)投影到同一個(gè)隱空間以消除不同模態(tài)之間的異構(gòu)性，從而數(shù)據(jù)可以直接在隱空間中尋找近鄰。在此基礎(chǔ)上，跨模態(tài)哈?？梢约涌鞕z索速度。
　　本文的主要工作是無監(jiān)督哈希算法和跨模態(tài)哈希算法的

3、研究。由于二進(jìn)制編碼計(jì)算的高效性，使用哈希算法進(jìn)行檢索往往比線性搜索K近鄰快數(shù)十甚至上百倍。本文主要進(jìn)行了兩方面的研究:1）一種歐幾里得空間線性無監(jiān)督哈希（USEH算法）。部分無監(jiān)督哈希算法使用徑向基核函數(shù)來度量歐幾里得空間中數(shù)據(jù)樣本之間的相似度，構(gòu)造相似度矩陣。USEH算法也采用了相似的思路，以確保投影到海明空間后樣本間的相似度保一致。但由于構(gòu)造這樣一個(gè)相似度矩陣占用的空間過大，USEH利用LSH向量來近似徑向基函數(shù)的。具體的，USE

4、H算法利用LSH從無監(jiān)督數(shù)據(jù)集中生成偽標(biāo)簽信息，用標(biāo)簽矩陣和它轉(zhuǎn)置的乘積來近似相似度矩陣，從而減少訓(xùn)練過程中占用的內(nèi)存空間和訓(xùn)練時(shí)間。另外，由于哈希編碼正交約束會(huì)導(dǎo)致較多的信息丟失，USEH算法使用順序?qū)W習(xí)的策略逐個(gè)學(xué)習(xí)哈希函數(shù)，忽略正交約束以獲取訓(xùn)練集數(shù)據(jù)更多的方差信息。隨著哈希編碼長度增加，相比于正交約束算法，USEH順序?qū)W習(xí)方法的優(yōu)勢越來越明顯。2）一種基于字典學(xué)習(xí)的跨模態(tài)檢索哈希（DLCMH算法）。DLCMH算法把不同模態(tài)的數(shù)據(jù)

5、投影到同一個(gè)海明空間，并假設(shè)同一個(gè)對(duì)象的不同模態(tài)數(shù)據(jù)有相同的哈希編碼。通常情況下，同一個(gè)模態(tài)內(nèi)樣本特征之間的歐氏距離和語義相似度之間存在不一致的情況，而線性哈希投影矩陣很難糾正兩者之間的偏差。為了使投影后數(shù)據(jù)間的距離和語義相似度更好的匹配，DLCMH算法引入了字典學(xué)習(xí)，通過字典表示來自動(dòng)學(xué)習(xí)語義信息，然后用線性投影矩陣把數(shù)據(jù)的字典表示投影到海明空間。在目標(biāo)函數(shù)優(yōu)化階段，DLCMH對(duì)哈希編碼矩陣進(jìn)行松弛使目標(biāo)函數(shù)容易求導(dǎo)，并把較難求解的優(yōu)