大數據哈希學習: 現狀與趨勢_數據分析師

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

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

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

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

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

1 研究進展

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

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

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

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

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

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

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

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

現有的參數優化方法大概可以分為兩類.

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

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

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

綜上所述, 目前哈希學習的研究現狀是: 已被廣泛關注并在某些應用領域取得了初步成效, 但研究才剛剛開始, 有的學習場景和應用領域甚至還沒有研究者進行哈希學習的嘗試; 問題本質和模型構建有待于進一步深入思考; 模型參數的優化方法有待于進一步探索; 量化階段的重要性已經引起注意, 但量化策略期待進一步突破.

2 發展趨勢

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

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

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

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

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

3 總結與展望

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