給數(shù)據(jù)生成一段短指紋讓相似的樣本指紋也相似這就是壓縮哈希Compressed Hashing在做的事。最近在手頭一個大規(guī)模相似檢索的小項目里樣本量一上來暴力算距離立刻撐不住存儲也跟著告急我花了兩天把這個算法完整重新梳理了一遍順便把實際踩過的坑記錄下來。這篇文章非常適合正在做最近鄰檢索、想用哈希碼壓縮高維向量、或者在調(diào)研二值表示學(xué)習(xí)方案的開發(fā)者閱讀。我會從“為什么需要壓縮哈?！敝v起拆解它的建模思路、學(xué)習(xí)算法推導(dǎo)再給出一份可以直接照著復(fù)現(xiàn)的完整流程最后附上我在實操中遇到的問題排查表。內(nèi)容不依賴某個特定框架核心邏輯用偽代碼和矩陣運算就能講清楚盡量做到看過就能上手。1. 為什么需要壓縮哈希當(dāng)存儲和檢索都卡在瓶頸上1.1 從暴力檢索到二進制指紋先算一筆賬。假設(shè)你有100萬個樣本每個樣本是一個384維的浮點向量按float32存儲體積大約是100萬×384×4字節(jié)約1.5GB。如果要做近鄰檢索一次查詢需要對全部100萬樣本逐個計算點積或歐氏距離幾十毫秒已經(jīng)算快這還只是單條query。放到線上系統(tǒng)里QPS稍微上來一點CPU就燒沒了。如果把每個384維向量壓縮成32位哈希碼情況完全不一樣。100萬個32位二進制碼只需要100萬×4字節(jié)也就是4MB左右。存儲縮小了將近400倍而且檢索時計算的是漢明距離——兩個二進制串做異或再數(shù)1的個數(shù)這類操作在CPU里有專門的指令支持百萬級別的異或計數(shù)可以在毫秒甚至微秒級完成。這里的關(guān)鍵不只在于“壓縮”更在于“壓縮后還能不能找到相似樣本”。如果只是隨便做隨機投影再取符號得到的二進制碼雖然短但可能把原本類似的樣本映射到完全不同的碼字上檢索就沒意義了。壓縮哈希這個名字里藏著它的核心訴求它是一套“學(xué)習(xí)算法”要從數(shù)據(jù)本身出發(fā)學(xué)出一組投影方向使得映射后的短哈希碼能夠保留原始空間里的相似性。這是它和很多固定隨機哈希方法的本質(zhì)區(qū)別。1.2 與局部敏感哈希的區(qū)別隨機 vs 學(xué)習(xí)很多人一開始會把壓縮哈希和經(jīng)典的局部敏感哈希LSH混在一起我也經(jīng)歷過這個階段。LSH的思路是數(shù)據(jù)無關(guān)的設(shè)計一族哈希函數(shù)使得兩個相似樣本被映射到同一個桶的概率大于不相似樣本然后用足夠多的隨機投影來近似這個概率。理論上很漂亮實際用起來卻往往需要很長的碼長才能達到可以接受的召回率因為隨機投影沒有利用數(shù)據(jù)分布的信息很多投影方向是浪費的。壓縮哈希走的是另一條路數(shù)據(jù)相關(guān)、任務(wù)相關(guān)。它把哈希碼的生成看成一個優(yōu)化問題有一個期望的相似度矩陣S我們想要找到一組哈希碼Y使得Y的內(nèi)部結(jié)構(gòu)盡可能貼近S。這樣一來哈希函數(shù)不再是拍腦袋隨機的而是從數(shù)據(jù)的局部結(jié)構(gòu)里“學(xué)”出來的。這種思路的優(yōu)勢很明顯同樣位數(shù)下學(xué)出來的哈希碼通常比隨機LSH有更高的檢索精度或者換個角度看達到同樣的召回率學(xué)習(xí)式哈?？梢杂酶痰拇a存儲和計算優(yōu)勢又進一步擴大。當(dāng)然學(xué)習(xí)式哈希也有代價需要先做一次離線訓(xùn)練可能有超參數(shù)要調(diào)對數(shù)據(jù)分布也有一定的假設(shè)。但如果你是多輪查詢、重復(fù)使用的場景把訓(xùn)練成本攤到線上請求里幾乎可以忽略不計。2. 核心思路讓短哈希碼繼承數(shù)據(jù)相似性2.1 建模相似矩陣與哈希內(nèi)積的對齊搞清楚壓縮哈希在優(yōu)化什么是理解整套算法最重要的一步。設(shè)想我們有n個樣本它們組成數(shù)據(jù)矩陣X維度是n行d列。我們想學(xué)習(xí)一個投影矩陣W維度是d行b列這里的b就是哈希碼的位數(shù)。對任意樣本x它的哈希碼就是sign(xW)結(jié)果是一個長度為b的向量每個分量是1或-1。把所有樣本的哈希碼堆疊起來得到矩陣Y維度是n行b列。Y的第i行是第i個樣本的二進制碼。對于一個二進制碼矩陣Y乘以Y轉(zhuǎn)置再除以b得到的就是樣本之間哈希內(nèi)積的相似度。為什么要關(guān)心這個內(nèi)積因為漢明距離和二進制內(nèi)積之間有非常直接的換算關(guān)系。兩段長度為b的二進制碼如果它們的漢明距離是d那么它們對應(yīng)向量的內(nèi)積就是b減去2d。也就是說哈希內(nèi)積越大漢明距離越小樣本在哈?？臻g里越接近。于是問題變得清晰我們希望學(xué)習(xí)出來的哈希碼讓“哈希內(nèi)積相似度”盡量接近“原始空間相似度”。前者由Y和內(nèi)積決定后者用一個預(yù)先構(gòu)造好的相似矩陣S來表達。S告訴我們哪些樣本應(yīng)該相近哪些樣本應(yīng)該疏遠(yuǎn)。整個優(yōu)化目標(biāo)可以寫成最小化S與Y的某種尺度歸一化內(nèi)積之間的誤差通常用Frobenius范數(shù)來表示。這個說法的直觀解釋是我們在找一個低維二值表示讓它作為原始高維相似結(jié)構(gòu)的一個“壓縮投影”。2.2 二值化的松弛與譜解法直接優(yōu)化帶符號函數(shù)的離散問題非常棘手因為sign這個操作讓目標(biāo)函數(shù)變得非凸且不可導(dǎo)。這是哈希學(xué)習(xí)里最經(jīng)典的困難點。壓縮哈希的解法思路是先退一步暫時丟掉sign假設(shè)Y可以直接取連續(xù)值Y XW在連續(xù)空間里先找到最優(yōu)投影方向最后再做量化。丟掉sign之后優(yōu)化問題變成了一個典型的低秩矩陣近似問題。直觀來說我們是在用一個n行b列的連續(xù)矩陣去逼近n行n列的相似矩陣S。在連續(xù)空間里這個問題有非常漂亮的解析解先構(gòu)造一個d維方陣M X轉(zhuǎn)置乘以S乘以X然后對M做特征分解取出最大的b個特征值對應(yīng)的特征向量構(gòu)成投影矩陣W。這個結(jié)論的本質(zhì)是把原問題轉(zhuǎn)化成了在投影方向空間里的一個瑞利商優(yōu)化最優(yōu)方向落在矩陣M的top特征子空間里。整個過程可以理解成兩個動作先用相似矩陣S把數(shù)據(jù)集的局部幾何信息“吸收”進來再通過特征分解找到最能代表這些信息的b個正交方向。每個方向上原始數(shù)據(jù)投影得越遠(yuǎn)說明這個方向?qū)^(qū)分樣本的貢獻越大。最后一步我們把連續(xù)投影結(jié)果用sign二值化取正為1、取負(fù)為-1就得到了最終的哈希碼。量化這一步當(dāng)然會帶來信息損失但在b比較小時損失是可以接受的畢竟我們的目標(biāo)本來就是用一個短碼去近似原始結(jié)構(gòu)而不是無損編碼。2.3 為什么要強調(diào)“學(xué)習(xí)”而不是“隨機”這里值得多說一句。單看最終操作壓縮哈希看起來也就是“隨機投影-取符號”的變體但只要對比一下就能看出差異。隨機投影不關(guān)心數(shù)據(jù)長什么樣無論數(shù)據(jù)集中在哪個方向投影方向都是撒網(wǎng)式的必然有很多方向落在數(shù)據(jù)方差極小的地方攜帶的信息量很少。而壓縮哈希的投影矩陣W來自對M的特征分解M里已經(jīng)融合了數(shù)據(jù)分布和相似關(guān)系取出的top特征向量天然對準(zhǔn)了數(shù)據(jù)變化最劇烈的方向。這就像給一群人拍證件照。隨機投影相當(dāng)于從隨機角度亂拍總有些角度把所有人都拍成一團模糊壓縮哈希相當(dāng)于先觀察人群的站位挑最能區(qū)分大家的幾個角度去拍。后者在碼長有限時的信息密度自然更高。3. 實操復(fù)現(xiàn)從零到哈希碼的完整流程3.1 數(shù)據(jù)預(yù)處理與相似矩陣構(gòu)造先說明一下我下面給出的流程是基于常見實踐的補充具體數(shù)據(jù)集和場景里你可以在細(xì)節(jié)上做替換但主干路線是通用的。第一步是準(zhǔn)備數(shù)據(jù)矩陣X把每個樣本歸一化成單位長度。歸一化這一步非常重要后面構(gòu)造相似矩陣時如果不歸一化范數(shù)大的樣本會天然和誰都“相似”距離度量完全失真。接著計算n個樣本兩兩之間的相似度。比較常用的做法是余弦相似度加top-k鄰居截斷先算全量的相似度矩陣對每一行只保留相似度最大的k個鄰居其余置零然后做對稱化。為什么要截斷因為全量相似矩陣是n乘n的當(dāng)n到幾萬甚至幾十萬時內(nèi)存和計算量都會爆炸而且全量保留會讓每個樣本和所有樣本都產(chǎn)生相似關(guān)系稀釋了局部結(jié)構(gòu)。只保留top-k鄰居相當(dāng)于構(gòu)造了一張稀疏的相似圖只讓真正相近的樣本互相“傳遞”相似性計算量和存儲都大幅下降。如果特征不是高維稀疏類型也可以換成RBF核來構(gòu)造相似度帶寬參數(shù)可以取所有樣本對距離的中位數(shù)這個經(jīng)驗值在多數(shù)情況下表現(xiàn)穩(wěn)定。構(gòu)造完S之后記得做S (S S轉(zhuǎn)置)除以2的對稱化再給對角線加一個很小的正則項防止后面特征分解時出現(xiàn)奇異問題。S的構(gòu)造是整個壓縮哈希里最影響最終效果的一步它決定了“相似”到底是按什么標(biāo)準(zhǔn)定義的后面所有的學(xué)習(xí)都是在試圖逼近這個定義。3.2 投影矩陣求解特征分解與迭代精煉拿到S之后下一步就是求解投影矩陣W。按照前面推導(dǎo)的邏輯核心計算是構(gòu)造矩陣M X^T S X對它做特征分解取出最大的b個特征向量。這里有一個隱藏的計算細(xì)節(jié)值得提醒X^T S X的維度是d乘dd是原始特征維度通常比n小得多所以這個特征分解非常輕量。如果特征是幾千維依然可以秒級完成真正貴的是構(gòu)造全量相似矩陣那一步所以要盡量用稀疏化的方式去算S。下面我用一段示意代碼給出主流程的骨架方便理解整體計算順序import numpy as np # X: (n, d) 已經(jīng)做歸一化/中心化n是樣本數(shù)d是原始特征維度 # b: 哈希碼位數(shù) # k_neighbor: top-k鄰居數(shù) n, d X.shape b 16 k_neighbor 10 # 1. 構(gòu)造稀疏相似矩陣S sim X X.T # n x n 余弦相似度 S np.zeros_like(sim) for i in range(n): idx np.argsort(sim[i])[-k_neighbor:] S[i, idx] sim[i, idx] S (S S.T) / 2.0 S S 1e-6 * np.eye(n) # 2. 特征分解求解連續(xù)投影方向 M X.T S X # d x d eigvals, eigvecs np.linalg.eigh(M) idx np.argsort(eigvals)[::-1][:b] W eigvecs[:, idx] # 3. 生成連續(xù)投影再二值化成哈希碼 Y_continuous X W # n x b B np.sign(Y_continuous).astype(np.int8) # 4. 查詢給定新樣本xq xq xq / np.linalg.norm(xq) yq_continuous xq W bq np.sign(yq_continuous).astype(np.int8) # 漢明距離 bit_diff的數(shù)量 hamming_dist (B ! bq).sum(axis1)如果你希望進一步提升精度可以在特征分解之后加一個交替優(yōu)化的步驟固定當(dāng)前的W計算連續(xù)投影的符號作為Y然后反向更新W去擬合這個Y如此循環(huán)幾次。這個精煉步驟借鑒了迭代量化方法的思想本質(zhì)上是在二值化和投影之間交替修正彌補直接量化帶來的損失。我自己實驗下來的體感是b比較小比如8位、16位時精煉能帶來明顯的檢索精度提升b比較大時直接特征分解的結(jié)果已經(jīng)足夠好收益就沒那么大了。3.3 量化成二進制碼與檢索驗證拿到哈希碼B之后實際使用中要注意存儲格式。n行b列的int8矩陣如果在內(nèi)存里展開每個碼還是占用1字節(jié)沒有達到真正的存儲壓縮效果。更好的做法是把每b位打包成uint64或者uint32存儲。例如b32時每行哈希碼可以用一個uint32整數(shù)表示內(nèi)存占用立刻縮小到原來的八分之一。漢明距離的計算也隨之變成一個異或加popcount操作這在很多CPU上都是單指令速度非?？?。驗證哈希碼質(zhì)量時我建議先不要直接上線上指標(biāo)而是做一個小規(guī)模的離線對比隨機挑一些查詢樣本在原始空間里用歐氏距離或余弦距離找它們的真實k近鄰再在哈?？臻g里用漢明距離找哈希近鄰然后計算兩個近鄰集合的重疊率也就是precisionk。如果重疊率低先回到S的構(gòu)造那一步找問題不要急著調(diào)b。我見過不少初學(xué)者一上來就調(diào)b折騰半天效果還是差原因其實是相似矩陣構(gòu)造得太粗糙比如沒有歸一化、top-k太大或太小、或者S沒有對稱化。另外新樣本的哈希碼生成一定要和訓(xùn)練時的預(yù)處理完全一致。訓(xùn)練時如果對每個向量做了L2歸一化查詢時也必須先歸一化再投影訓(xùn)練時如果做過某種特征中心化查詢時也得用完全相同的均值去中心化。這一步看起來小實際出錯率卻很高一旦預(yù)處理不對齊訓(xùn)練時精心學(xué)的投影矩陣就全部白費了。4. 常見問題與排查技巧實錄4.1 一張問題排查對照表實操過程中我整理了下面這些最常遇到的問題和對應(yīng)的排查方向基本能覆蓋大多數(shù)失敗場景。現(xiàn)象可能原因排查與對策不同隨機種子下檢索精度差異大構(gòu)造S時依賴隨機采樣或者W初始化的隨機性影響過大固定隨機種子用PCA投影作為W的初始化多次運行取平均結(jié)果哈希碼檢索精度很低相似矩陣S構(gòu)造不合理未歸一化、top-k太大或太小、S非對稱檢查預(yù)處理流程可視化S的行分布調(diào)整top-k和帶寬參數(shù)查詢時新樣本哈希碼和訓(xùn)練碼分布不一致預(yù)處理不對齊比如訓(xùn)練時歸一化而查詢時沒有統(tǒng)一封裝預(yù)處理函數(shù)保證訓(xùn)練和查詢走同一套流程特征維度d很大時訓(xùn)練很慢M X^T S X 雖然維度d×d但X^T S這一步計算量可能不小利用稀疏S減少乘法量必要時先用PCA把d降到幾百維再做哈希b增大時檢索效果反而下降特征分解取top特征向量時后面特征向量含噪聲較多適當(dāng)增大S的正則項對特征值做歸一化篩選改用精煉迭代漢明距離計算仍然很慢每行碼用int8展開比較沒有打包將b位碼打包成uint64用異或popcount計算距離這張表里的很多坑我都實際踩過。比如第一次做實驗時我沒有做L2歸一化直接用了原始特征算余弦相似度結(jié)果S矩陣根本不能反映真實近鄰關(guān)系top-k鄰居里混入了大量范數(shù)大的噪聲樣本學(xué)出來的哈希碼自然不能用。后來把所有向量歸一化之后效果立刻提升了一個檔次。4.2 幾個我實際踩過的坑先說相似矩陣的對角線問題。S的構(gòu)建過程中假設(shè)i是某個樣本的top-k鄰居S[i][i]一般會被置成相似度值。但我們后面用哈希內(nèi)積去逼近S時Y的每一行是一個長度為b的±1向量它的自內(nèi)積是b而S對角線上的值通常是1或者相似度值。這個尺度不對齊會導(dǎo)致優(yōu)化時過度關(guān)注對角線而把非對角線的結(jié)構(gòu)給犧牲掉。我習(xí)慣在構(gòu)造S時把對角線手動置零或者給S整體乘一個縮放因子去匹配b的尺度具體效果需要根據(jù)數(shù)據(jù)集測試。還有一個容易被忽略的問題是sign函數(shù)的輸入尺度。如果投影后得到的連續(xù)值整體偏小也就是集中在零附近那么sign對噪聲非常敏感一點點擾動就會翻轉(zhuǎn)哈希位導(dǎo)致相似樣本的碼相差很遠(yuǎn)。解決辦法是在投影后、量化前做一個適當(dāng)?shù)臄?shù)據(jù)標(biāo)準(zhǔn)化把連續(xù)投影值的方差拉大。有些實現(xiàn)里會直接對投影矩陣W做正交歸一化這樣每個哈希位攜帶的信息更均衡。我自己比較喜歡在算完W后對Y_continuous的每一列做減均值除標(biāo)準(zhǔn)差的操作這樣能明顯增強哈希碼的穩(wěn)定性。最后說一說數(shù)據(jù)規(guī)模變大時的擴展方案。原始的壓縮哈希流程里S是全量矩陣或稀疏矩陣當(dāng)n到百萬級別時連稀疏矩陣都可能撐爆內(nèi)存。這時可以改用mini-batch的訓(xùn)練思路每次隨機采樣一批樣本在批內(nèi)構(gòu)造局部相似矩陣并更新投影矩陣多輪迭代后得到一個總體可用的W。這個做法不完全等同于全量最優(yōu)解但工程上可行而且配合學(xué)習(xí)率的衰減收斂效果不差。我在一個百萬級別的圖像特征場景里試過這種方案檢索精度相比全量版本只損失了1%左右訓(xùn)練時間卻從幾小時降到了十幾分鐘這個取舍是非常值得的。還有一個細(xì)節(jié)是哈希碼位數(shù)的選擇。b太小表示能力不夠區(qū)分度差b太大壓縮紅利變小而且特征分解取太多特征向量時后面的方向往往開始擬合噪聲。我習(xí)慣做一個簡單的掃描實驗把b從8、16、32、64、128依次試一遍畫一條precisionk隨b變化的曲線。曲線會有一個明顯的“收益飽和”點這個點附近就是當(dāng)前數(shù)據(jù)分布下比較合適的碼長。不要只看精度要同時看存儲壓縮和計算速度因為哈希檢索的優(yōu)勢本來就來自短碼過度追求精度而用很長的碼會丟掉壓縮哈希的使用價值。整個流程再過一遍構(gòu)造相似矩陣、特征分解求投影、量化成碼、離線驗證、打包上線。壓縮哈希最大的妙處在于把“相似性保持”和“壓縮”統(tǒng)一成了一個優(yōu)化問題而不是像傳統(tǒng)做法那樣先降維再檢索每步各干各的。這種端到端的視角在工程實現(xiàn)里非常有價值也解釋了為什么這個方向雖然年頭不短到現(xiàn)在做大規(guī)模向量檢索時依然會被人重新?lián)炱饋碛?。如果你正在折騰二值表示或者近鄰檢索照著這套流程在自己的數(shù)據(jù)上跑一版很快就能感受到短碼檢索的甜頭。