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