大數(shù)據(jù)哈希學(xué)習(xí): 現(xiàn)狀與趨勢_數(shù)據(jù)分析師

隨著信息技術(shù)的迅速發(fā)展, 各行各業(yè)積累的數(shù)據(jù)都呈現(xiàn)出爆炸式增長趨勢, 我們已經(jīng)進入大數(shù)據(jù)時代. 大數(shù)據(jù)在很多領(lǐng)域都具有廣闊的應(yīng)用前景, 已經(jīng)成為國家重要的戰(zhàn)略資源, 對大數(shù)據(jù)的存儲、管理和分析也已經(jīng)成為學(xué)術(shù)界和工業(yè)界高度關(guān)注的熱點. 收集、存儲、傳輸、處理大數(shù)據(jù)的目的是為了利用大數(shù)據(jù), 而要有效地利用大數(shù)據(jù), 機器學(xué)習(xí)技術(shù)必不可少. 因此, 大數(shù)據(jù)機器學(xué)習(xí)(簡稱大數(shù)據(jù)學(xué)習(xí))是大數(shù)據(jù)研究的關(guān)鍵內(nèi)容之一. 哈希學(xué)習(xí)通過將數(shù)據(jù)表示成二進制碼的形式, 不僅能顯著減少數(shù)據(jù)的存儲和通信開銷, 還能降低數(shù)據(jù)維度, 從而顯著提高大數(shù)據(jù)學(xué)習(xí)系統(tǒng)的效率. 因此, 哈希學(xué)習(xí)近年來成為大數(shù)據(jù)學(xué)習(xí)中的一個研究熱點. 本文對這方面的工作進行介紹.

隨著近年來互聯(lián)網(wǎng)、云計算、物聯(lián)網(wǎng)、社交媒體以及其他信息技術(shù)的迅速發(fā)展, 各行各業(yè)積累的數(shù)據(jù)都呈現(xiàn)出爆炸式增長趨勢. 例如, 歐洲粒子物理研究所(CERN)的大型強子對撞機每秒產(chǎn)生的數(shù)據(jù)高達40 TB(1 TB=1024 GB), Facebook每天處理的數(shù)據(jù)超過500 TB, 阿里巴巴擁有的數(shù)據(jù)量超過100 PB (1 PB=1024 TB), 新浪微博用戶數(shù)超過5億, 每天產(chǎn)生的微博數(shù)超過1億條. 中國移動研究院的一份簡報中稱, 2011年人類創(chuàng)造的數(shù)據(jù)達到180億吉字節(jié)(GB), 而且每年還在以高于60%的速度增長, 預(yù)計到2020年, 全球每年產(chǎn)生的數(shù)據(jù)將達到350萬億吉字節(jié)(GB). 大數(shù)據(jù)在科學(xué)、金融、氣象、醫(yī)療、環(huán)保、教育、軍事、交通等領(lǐng)域都具有非常廣闊的應(yīng)用前景[1,2]. 例如, 在科學(xué)領(lǐng)域, 包括天文、生物、物理、化學(xué)、信息等在內(nèi)的各個領(lǐng)域的科學(xué)發(fā)現(xiàn)已經(jīng)從實驗型科學(xué)發(fā)現(xiàn)、理論型科學(xué)發(fā)現(xiàn)、計算型科學(xué)發(fā)現(xiàn)發(fā)展到第四范式, 即基于大數(shù)據(jù)的數(shù)據(jù)密集型科學(xué)發(fā)現(xiàn)[3,4]. 因此可以說, 大數(shù)據(jù)已經(jīng)成為國家重要的戰(zhàn)略資源, 對大數(shù)據(jù)的存儲、管理和分析也已經(jīng)成為學(xué)術(shù)界和工業(yè)界高度關(guān)注的熱點[1,2].

收集、存儲、傳輸、管理大數(shù)據(jù)的目的是為了利用大數(shù)據(jù), 而要有效地利用大數(shù)據(jù), 機器學(xué)習(xí)技術(shù)[5]必不可少. 事實上, 機器學(xué)習(xí)界一直在嘗試對越來越大的數(shù)據(jù)進行學(xué)習(xí)[6], 但今日的大數(shù)據(jù)已不僅僅是數(shù)據(jù)量大, 同時還伴隨著數(shù)據(jù)的多源、動態(tài)、價值稀疏等特性, 因此為機器學(xué)習(xí)界提出了一些新的挑戰(zhàn). 近年來, 大數(shù)據(jù)機器學(xué)習(xí)(或簡稱為大數(shù)據(jù)學(xué)習(xí))受到了廣泛關(guān)注[7], 成為機器學(xué)習(xí)領(lǐng)域的研究熱點之一, 新成果不斷涌現(xiàn). 例如Kleiner等人[8]基于集成學(xué)習(xí)中Bagging的思想提出了新型數(shù)據(jù)采樣方法BLB, 用來解決Bootstrap在遇到大數(shù)據(jù)時的計算瓶頸問題; Shalev-Shwartz和Zhang[9]基于隨機(在線)學(xué)習(xí)的思想提出了梯度上升(下降)的改進方法, 用來實現(xiàn)大規(guī)模模型的快速學(xué)習(xí); Gonzalez等人[10]提出了基于多機集群的分布式機器學(xué)習(xí)框架GraphLab, 用以實現(xiàn)基于圖的大規(guī)模機器學(xué)習(xí); Gao等人[11]提出了“單遍學(xué)習(xí)”(one-pass learning)的思想, 力圖在學(xué)習(xí)中只掃描一遍數(shù)據(jù)、且使用常數(shù)級存儲來保存中間計算結(jié)果, 在AUC優(yōu)化這樣的復(fù)雜學(xué)習(xí)任務(wù)上已取得很好的效果. 此外還有很多新進展, 本文不再贅述.

哈希學(xué)習(xí)(learning to hash)[12~22]通過機器學(xué)習(xí)機制將數(shù)據(jù)映射成二進制串的形式, 能顯著減少數(shù)據(jù)的存儲和通信開銷, 從而有效提高學(xué)習(xí)系統(tǒng)的效率. 哈希學(xué)習(xí)的目的是學(xué)到數(shù)據(jù)的二進制哈希碼表示, 使得哈希碼盡可能地保持原空間中的近鄰關(guān)系, 即保相似性. 具體來說, 每個數(shù)據(jù)點會被一個緊湊的二進制串編碼, 在原空間中相似的2個點應(yīng)當(dāng)被映射到哈希碼空間中相似的2個點. 圖1是哈希學(xué)習(xí)的示意圖, 以圖像數(shù)據(jù)為例, 原始圖像表示是某種經(jīng)過特征抽取后的高維實數(shù)向量, 通過從數(shù)據(jù)中學(xué)習(xí)到的哈希函數(shù)h變換后, 每幅圖像被映射到一個8位(bit)的二進制哈希碼, 原空間中相似的兩幅圖像將被映射到相似(即海明距離較小)的2個哈希碼, 而原空間中不相似的兩幅圖像將被映射到不相似(即海明距離較大)的2個哈希碼. 使用哈希碼表示數(shù)據(jù)后, 所需要的存儲空間會被大幅減小. 舉例來說, 如果原空間中每個數(shù)據(jù)樣本都被1個1024 B的向量表示, 1個包含1億個樣本的數(shù)據(jù)集要占用100 GB的存儲空間. 相反, 如果把每個數(shù)據(jù)樣本哈希到1個128位的哈希碼, 一億個樣本的存儲空間只需要1.6 GB. 單臺機器(包括配置很高的單臺服務(wù)器)處理原始表示時, 需要不斷地進行外內(nèi)存交換, 開銷非常大. 但如果用哈希碼表示, 所有計算都可以在內(nèi)存中完成, 單臺普通的個人電腦(PC)也能很快地完成計算. 由于很多學(xué)習(xí)算法, 比如k近鄰(kNN)、支持向量機(SVM)等的本質(zhì)是利用數(shù)據(jù)的相似性, 哈希學(xué)習(xí)的保相似性將在顯著提高學(xué)習(xí)速度的同時, 盡可能地保證精度. 另一方面, 因為通過哈希學(xué)習(xí)得到的哈希碼位數(shù)(維度)一般會比原空間的維度要低, 哈希學(xué)習(xí)也能降低數(shù)據(jù)維度, 從而減輕維度災(zāi)難問題. 因此, 哈希學(xué)習(xí)在大數(shù)據(jù)學(xué)習(xí)中占有重要地位.

需特別指出的是, 數(shù)據(jù)庫研究領(lǐng)域早已使用二進制哈希碼來表示數(shù)據(jù)[23~25], 但他們使用的哈希函數(shù)是人工設(shè)計或者隨機生成的; 與之不同, 哈希學(xué)習(xí)是希望從數(shù)據(jù)中自動地學(xué)習(xí)出哈希函數(shù). 從哈希技術(shù)的角度來看, 前者被稱為數(shù)據(jù)獨立方法, 后者被稱為數(shù)據(jù)依賴方法. 有研究表明[17,18], 與數(shù)據(jù)獨立方法相比, 數(shù)據(jù)依賴方法(即哈希學(xué)習(xí)方法)只需用較短的哈希編碼位數(shù)就能取得理想的精度, 從而進一步提高檢索和學(xué)習(xí)效率, 降低存儲和通信開銷.

1 研究進展

哈希學(xué)習(xí)由Salakhutdinov和Hinton[12,13]于2007年推介到機器學(xué)習(xí)領(lǐng)域, 于近幾年迅速發(fā)展成為機器學(xué)習(xí)領(lǐng)域和大數(shù)據(jù)學(xué)習(xí)領(lǐng)域的一個研究熱點[14~22,26~37], 并廣泛應(yīng)用于信息檢索[38,39]、數(shù)據(jù)挖掘[40,41]、模式識別[42,43]、多媒體信息處理[44,45]、計算機視覺[46,47]、推薦系統(tǒng)[48]、以及社交網(wǎng)絡(luò)分析[49,50]等領(lǐng)域. 值得一提的是, 國內(nèi)學(xué)者在這方面也進行了有意義的探索[32~37,43,45~47,50,51].

由于從原空間中的特征表示直接學(xué)習(xí)得到二進制的哈希編碼是一個NP難問題[14]. 現(xiàn)在很多的哈希學(xué)習(xí)方法[14,17~20]都采用兩步學(xué)習(xí)策略:

第一步, 先對原空間的樣本采用度量學(xué)習(xí)(metric learning)[52]進行降維, 得到1個低維空間的實數(shù)向量表示;

第二步, 對得到的實數(shù)向量進行量化(即離散化)得到二進制哈希碼.

現(xiàn)有的方法對第二步的處理大多很簡單, 即通過某個閾值函數(shù)將實數(shù)轉(zhuǎn)換成二進制位. 通常使用的量化方法為1個閾值為0的符號函數(shù), 即如果向量中某個元素大于0, 則該元素被量化為1, 否則如果小于或等于0, 則該元素被量化為0. 例如, 假設(shè)樣本在原空間中的特征表示為1個5維實數(shù)向量(1.1, 2.3,1.5, 4, 3.2), 經(jīng)過某種度量學(xué)習(xí)(通常把降維看成度量學(xué)習(xí)的一種)處理后得到1個三維的實數(shù)向量(1.8, 2.3, 0.6), 然后經(jīng)過符號函數(shù)量化后, 得到的二進制哈希碼為(1, 0, 1). 一般來說, 度量學(xué)習(xí)階段首先得構(gòu)建學(xué)習(xí)模型, 然后對模型的參數(shù)進行優(yōu)化和學(xué)習(xí). 下面我們將從學(xué)習(xí)模型、參數(shù)優(yōu)化和量化策略3方面來介紹哈希學(xué)習(xí)的最新進展.

根據(jù)學(xué)習(xí)模型(一般指度量學(xué)習(xí)階段的模型)是否利用樣本的監(jiān)督信息(例如類別標記等), 現(xiàn)有的哈希學(xué)習(xí)模型可以分為非監(jiān)督模型[18~20]、半監(jiān)督模型[17,36,47]和監(jiān)督模型[26,31,42]. 非監(jiān)督模型又可以進一步細分為基于圖的模型[19]和不基于圖的模型[18,20],

監(jiān)督模型又可以進一步細分為監(jiān)督信息為類別標記的模型[26,42]和監(jiān)督信息為三元組或者排序信息的模型[31]. 實際上, 這每一個細分的類對應(yīng)于機器學(xué)習(xí)中一個比較大的子方向, 例如基于圖的模型. 由此可以看出, 現(xiàn)有的哈希學(xué)習(xí)模型雖然總數(shù)比較多, 但是在各個子方向上還僅僅只是進行了初步的嘗試.

此外, 度量學(xué)習(xí)是機器學(xué)習(xí)領(lǐng)域的研究熱點之一, 而度量學(xué)習(xí)方面的工作剛好可以用來實現(xiàn)哈希學(xué)習(xí)的第一步, 因此目前很多哈希學(xué)習(xí)模型(包括非監(jiān)督、半監(jiān)督和監(jiān)督)只是直接利用或者簡單改進已有度量學(xué)習(xí)模型, 然后采用上述的符號函數(shù)進行量化, 得到哈希編碼. 經(jīng)過一些摸索[20,22,29], 我們發(fā)現(xiàn)度量學(xué)習(xí)得到的結(jié)果通常是在模型目標函數(shù)的限制下使得信息損失最小, 因此得到的總是最優(yōu)的結(jié)果; 而在將度量學(xué)習(xí)應(yīng)用到哈希學(xué)習(xí)中時, 除了第一步的度量學(xué)習(xí)可能造成信息損失外, 第二步量化過程的信息損失對性能的影響也非常大, 有時候甚至超過第一步造成的信息損失, 因此, 第一步度量學(xué)習(xí)得到的最優(yōu)結(jié)果并不能保證最終量化后的二進制編碼為最優(yōu). 目前, 很多哈希學(xué)習(xí)方法沒有將量化過程中的信息損失考慮到模型構(gòu)建中去.

現(xiàn)有的參數(shù)優(yōu)化方法大概可以分為兩類.

第一類是采用與傳統(tǒng)度量學(xué)習(xí)的優(yōu)化方法類似的策略, 對所有位對應(yīng)的(實數(shù))參數(shù)一次性全部優(yōu)化[14,19]. 這種策略帶來的一個不利后果是沒辦法彌補量化過程帶來的信息損失, 有可能導(dǎo)致的結(jié)果是隨著哈希碼長度的增大, 精確度反而下降.

第二類是避免一次性全部優(yōu)化所有位對應(yīng)的(實數(shù))參數(shù), 而采用按位(bitwise)優(yōu)化策略[17,22,36], 讓優(yōu)化過程能夠自動地彌補量化過程中損失的信息. 實驗結(jié)果表明, 即使學(xué)習(xí)模型的目標函數(shù)相同, 采用按位優(yōu)化策略能取得比一次性全部優(yōu)化所有參數(shù)的策略更好的性能. 但按位優(yōu)化策略對模型目標函數(shù)有一定的要求和限制, 比如目標函數(shù)可以寫成殘差的形式[22]. 目前, 大部分哈希學(xué)習(xí)方法還是采取一次性全部優(yōu)化所有參數(shù)的策略.

哈希學(xué)習(xí)跟傳統(tǒng)度量學(xué)習(xí)的一個很本質(zhì)的區(qū)別是需要量化成二進制碼. 現(xiàn)有的哈希學(xué)習(xí)方法大多采用很簡單的量化策略, 即通過某個閾值函數(shù)將實數(shù)轉(zhuǎn)換成二進制位. 最近出現(xiàn)一些專門研究量化策略的工作[29,39,53], 并且發(fā)現(xiàn)量化策略也會影響哈希學(xué)習(xí)方法的性能, 至少跟第一步的度量學(xué)習(xí)階段同等重要. 我們在文獻[29,39]中, 采用對度量學(xué)習(xí)階段得到的每一個實數(shù)維進行多位編碼的量化策略, 取得了比傳統(tǒng)的單位編碼策略更好的效果. 一般來說, 度量學(xué)習(xí)的結(jié)果中, 各維的方差(或信息量)通常各不相等[18,20]. 而現(xiàn)有的很多方法采用“度量學(xué)習(xí)+相同位數(shù)編碼”的策略[14,19], 導(dǎo)致的結(jié)果是隨著哈希碼長度的增大, 精確度反而下降. 一種更合理的量化策略是, 采用更多的位數(shù)編碼信息量更大的維. 目前, 有部分工作在這方面進行了嘗試, 取得了不錯的結(jié)果[53].

綜上所述, 目前哈希學(xué)習(xí)的研究現(xiàn)狀是: 已被廣泛關(guān)注并在某些應(yīng)用領(lǐng)域取得了初步成效, 但研究才剛剛開始, 有的學(xué)習(xí)場景和應(yīng)用領(lǐng)域甚至還沒有研究者進行哈希學(xué)習(xí)的嘗試; 問題本質(zhì)和模型構(gòu)建有待于進一步深入思考; 模型參數(shù)的優(yōu)化方法有待于進一步探索; 量化階段的重要性已經(jīng)引起注意, 但量化策略期待進一步突破.

2 發(fā)展趨勢

目前大部分哈希學(xué)習(xí)研究的思路為: 針對某個機器學(xué)習(xí)場景(比如排序?qū)W習(xí)場景[31])或者應(yīng)用場景, 只要以前沒有人嘗試過用哈希學(xué)習(xí)的思想來加速學(xué)習(xí)過程, 就可以考慮把哈希學(xué)習(xí)用進去, 然后在一個傳統(tǒng)模型(這個傳統(tǒng)模型不用哈希)解決不了的數(shù)據(jù)或者應(yīng)用規(guī)模上進行實驗驗證. 從解決實際問題的角度來講, 這些工作雖然初步, 但還是很有研究價值的, 畢竟為大數(shù)據(jù)中傳統(tǒng)模型不能解決的問題提供了一種可行的解決思路. 但從哈希學(xué)習(xí)本身的研究來講, 目前大部分工作還沒有從哈希學(xué)習(xí)問題的本質(zhì)上進行考慮. 我們認為以后的工作可以從理論分析、模型構(gòu)建、參數(shù)優(yōu)化、量化策略等幾個方面進行進一步探索.

目前哈希學(xué)習(xí)理論分析方面的工作還很少. 用哈希碼表示數(shù)據(jù)后, 數(shù)據(jù)相當(dāng)于進行了有損壓縮. 在后續(xù)的處理中, 比如檢索或者挖掘過程中, 基于哈希碼表示的數(shù)據(jù)得到的模型能在多大程度上逼近從原始數(shù)據(jù)得到的模型, 即精確度如何, 目前還沒有相關(guān)的理論分析. 另外, 針對一個具體問題或應(yīng)用, 到底需要多少位編碼才能保證結(jié)果達到一定的精確度, 目前都是根據(jù)在驗證集上的實驗結(jié)果來進行選擇, 是否存在一些理論上的指導(dǎo)也非常值得研究.

針對哈希學(xué)習(xí)的量化過程會存在信息損失這一本質(zhì)特征, 更好的策略是在度量學(xué)習(xí)的模型構(gòu)建過程中將量化過程中可能的信息損失考慮進去. 但如果把量化過程中可能的信息損失考慮到模型的構(gòu)建過程中, 量化結(jié)果的離散性將使得模型構(gòu)建變得異常復(fù)雜. 因此, 如何構(gòu)建考慮到量化過程信息損失的有效哈希學(xué)習(xí)模型是哈希學(xué)習(xí)研究需要解決的又一重要問題.

在參數(shù)優(yōu)化過程中, 雖然按位優(yōu)化策略能自動地彌補量化過程中損失的信息, 但目前大部分模型的目標函數(shù)并不適合于這種優(yōu)化方式. 為其他模型設(shè)計能彌補量化過程信息損失的優(yōu)化策略, 還需要進行進一步的研究. 另外, 目前的監(jiān)督模型中[26,42], 對監(jiān)督信息的利用大多通過構(gòu)建樣本對之間的關(guān)系來實現(xiàn). 例如, 如果樣本i和j屬于同一類, 則Y(i, j)=1, 否則Y(i, j)=0. 然后再基于Y矩陣來建模. 這種監(jiān)督信息利用方式的一個后果是: 存儲和計算開銷都至少是訓(xùn)練樣本數(shù)的平方級. 哈希學(xué)習(xí)研究近幾年之所以這么熱, 正是因為它能夠被用來處理大數(shù)據(jù). 當(dāng)存在海量的訓(xùn)練數(shù)據(jù), 尤其是海量有監(jiān)督信息的數(shù)據(jù)時, 模型的參數(shù)訓(xùn)練和優(yōu)化過程非常慢或者甚至不可行. 如何保證參數(shù)優(yōu)化算法能快速地完成, 也是有待解決的關(guān)鍵問題之一.

雖然最近出現(xiàn)的量化策略[29,39,53]已經(jīng)取得了比傳統(tǒng)量化策略更好的性能, 但還沒有很好地跟保相似性或者監(jiān)督信息結(jié)合起來. 因此, 研究更優(yōu)的量化策略, 以更好地保持原始空間的相似性或者跟監(jiān)督信息盡可能保持一致, 也是值得進一步探索的方向.

3 總結(jié)與展望

本文對大數(shù)據(jù)哈希學(xué)習(xí)的研究進展和發(fā)展趨勢進行了介紹. 可以看出，哈希學(xué)習(xí)雖然已被廣泛關(guān)注并在某些應(yīng)用領(lǐng)域取得了初步成效, 但研究才剛剛開始，大部分學(xué)習(xí)場景和應(yīng)用領(lǐng)域到目前為止還只出現(xiàn)很少的哈希學(xué)習(xí)方法, 有的場景和應(yīng)用甚至還沒有研究者進行哈希學(xué)習(xí)的嘗試. 例如, 推薦系統(tǒng)是個很大的應(yīng)用方向, 但到目前為止這方面采用哈希學(xué)習(xí)的工作還不多[48]. 因此，怎樣將哈希學(xué)習(xí)的思想和方法拓展到新的學(xué)習(xí)場景和應(yīng)用領(lǐng)域, 用來解決傳統(tǒng)方法在遇到大數(shù)據(jù)時不能解決的問題, 將是非常有意義的工作. 特別值得一提的是, 大數(shù)據(jù)學(xué)習(xí)中的另一重要研究方向是基于多機集群的分布式機器學(xué)習(xí)[10], 而很多分布式機器學(xué)習(xí)的瓶頸在于節(jié)點間的通信開銷. 因此, 將哈希學(xué)習(xí)引入到分布式機器學(xué)習(xí)算法, 并驗證哈希學(xué)習(xí)在減小通信開銷方面的有效性, 也是非常有意義的研究方向.