做大规模近邻检索的时候大家多少都会撞上同一堵墙数据量一旦过了百万级精确检索打不过延迟指标暴力扫描又扛不住。树形索引呢二维三维里表现还行维度一高就开始表演“维度灾难”退化成线性扫描。这时候哈希检索成了折中方案——把实数向量压缩成几十到几百比特的二进制码用汉明距离近似样本之间的相似度。但哈希方法也有讲究我用过一个叫Anchor Graph Hashing锚点图哈希简称AGH的算法它的双层压缩函数设计相当精巧也算是我做亿级图像去重实验时少数几次“跑得动、效果还不拉胯”的谱哈希变体。当年第一次跑谱哈希直接卡死在小规模数据上——算法要求把所有样本的邻接图构造出来再对图拉普拉斯做特征分解复杂度在O(n²)以上十万条样本就让人头皮发麻。AGH之所以能在大数据场景下站稳脚跟核心思路就是通过锚点anchor把原始邻接图压成低秩锚点图再用一个双层锚点图哈希压缩函数把数据非线性地映射到二进制码。这篇文章我就把它内部的两个压缩函数掰开揉碎讲清楚数学推导、代码实现和工程里的坑。这篇文章适合正在实现或调优AGH的人也适合那些不想只调包、想理解“锚点图怎么近似邻接图”“两层压缩函数各自在做什么”的工程同学。代码部分我用Python风格的伪代码写方便你落地到自己项目里改。1. 为什么AGH需要双层压缩函数线性哈希的容量瓶颈1.1 邻接图哈希在大数据上为什么消受不起传统谱哈希的核心逻辑是基于全部数据构造邻接图计算图拉普拉斯的前几个小特征值对应的特征向量然后把特征向量阈值化得到一位位哈希码。这思路在几百条数据上没问题一旦数据量到了几十万条邻接矩阵是n×n的稠密矩阵光存储就是几十个GB特征分解更是把计算资源吃干净。工程上遇到的第一道坎就是“图根本建不起来、特征根本算不动”。AGH的逻辑是把“全局图”替换成“锚点图”。什么叫锚点你可以把它理解为数据空间中的一组代表点最常用的获取方式就是K-means聚类中心。假设我们有n条样本聚出m个锚点m远小于n。然后我们不直接计算样本两两之间的距离而是计算每条样本和这m个锚点之间的相似度组成一个n×m的稀疏矩阵Z。这个Z矩阵的行数再大也无所谓因为列数m受控矩阵是低秩的存起来就是稀疏格式算起来也快得多。锚点图的本质就是“用m个中心去近似n个点之间完整的邻接关系”。在AGH的整个流程里锚点图矩阵Z是一切的地基。双层压缩函数接收的输入就是基于Z推导出的特征映射矩阵。也就是说理解压缩函数之前你得先搞清楚Z是怎么构造、怎么归一化、怎么参与特征分解的——这些步骤直接决定后续压缩函数的输出质量。1.2 单层线性哈希的表达能力天花板早期谱哈希的做法是直接用线性映射把数据投影到特征向量张成的空间然后符号化。这种方式本质上假设数据流形可以用一个线性子空间去近似。现实中的数据哪会这么听话图像特征、文本嵌入、用户行为向量这些高维数据落到低维流形上往往是弯曲的、多模态的一个线性投影很难把不同聚类结构分开。我举个直观的例子。假设两个簇在原始空间里像同心圆套在一起线性投影到一维时两个簇很可能重叠阈值化之后码位严重冲突。这时候如果你先把投影结果过一个ReLU把负半轴的信息折叠到零再学一个旋转矩阵去重新分配各个维度的权重就相当于给线性映射加分了非线性激活和特征重对齐的能力。AGH第二层压缩函数做的正是这件事。所以两层压缩函数的分工非常清晰第一层负责用谱方法拿到数据在流形上的低维坐标是线性拟合第二层对低维坐标做非线性拉伸再旋转到方差最大的方向上增强哈希码的区分度。用好这个分工你才能在手写实现时做出正确的设计选择。2. 压缩函数的前置工程锚点图矩阵与近似特征向量求解2.1 锚点选择与核相似度计算锚点选择最省事也最稳定的方案就是K-means。需要注意一个实操细节K-means的初始化次数不要省跑三次选目标函数最小的一次锚点分布才均匀。锚点数m怎么定经验值通常是样本量的1%到5%但别超过5000个。再大一方面K-means本身吃时间另一方面后面的r×m矩阵运算会变慢压缩收益就没有了。选好锚点之后构造相似度矩阵。假设样本为x_i锚点为a_k用高斯核计算相似度s_{ik} exp(-||x_i - a_k||^2 / (2 * sigma^2))这里的sigma是核带宽我后面会专门讲它怎么选。原始高斯核矩阵里每个样本对每个锚点都有一个权重如果全部保留Z矩阵虽然还没爆炸但计算和存储成本也不低。工程上通常做一步截断对每个样本只保留与它最近的k_sparse个锚点的相似度其余置零。推荐k_sparse取2~10常见取5。然后按行归一化每行的权重除以该行所有非零权重之和让每行之和等于1。这一步很重要等于把相似度变成了概率分布能抵御不同样本间尺度差异带来的影响。2.2 特征向量的Nyström近似从Z到压缩矩阵P有了归一化后的Z矩阵下一步是求锚点图的近似特征向量。推导过程不啰嗦但结果是关键我们想求低秩相似矩阵W ZΛ⁻¹Zᵀ的近似特征向量其中Λ是对角矩阵对角元是Z每一列的和即Λ diag(Zᵀ·1_n)。直接对W做特征分解依然是n×n的复杂度所以通过Nyström方法绕一圈构造小矩阵 Γ Zᵀ·Z·Λ⁻¹维度是m×m。对Γ做特征分解取前r个最大特征值对应的特征向量组合成Um×r矩阵对应特征值组成对角阵Σ。计算压缩矩阵 P Λ⁻¹·U·Σ^(-1/2)维度是m×r。为什么这么算核心在于Γ是m×m的我们只需要对m阶小矩阵做特征分解复杂度和全量数据n完全脱钩。这里有个反直觉的点Nyström近似取的是最大特征值对应的特征向量而不是最小特征值。因为W表示样本间的相似度累积大特征值方向对应的是数据聚集最强的方向取这些方向等于抓住了流形的主干结构。P矩阵就是第一层压缩函数的主角。后续无论是训练样本还是新来的查询样本只要先算出它和锚点的相似度向量f(x)再左乘Pᵀ就能得到低维特征F1(x)整条链路就通了。3. 第一层压缩函数线性投影、阈值化与哈希码生成3.1 F1(x) Pᵀ·f(x) 的流形坐标含义第一层压缩函数做的事很纯粹把样本x在高维空间里的锚点相似度向量f(x)映射到一个r维低维空间。f(x)是m维的每个分量表示x与某个锚点的归一化相似度经过Pᵀ线性变换后得到r维的坐标向量这些坐标可以理解为样本在锚点图拉普拉斯特征空间中的近似位置。同一流形上的近邻样本在这个坐标空间里会被拉近不同流形结构则被拉开。这里要强调Matrix P为什么是m×r而不是r×m。很多第一次实现的人容易把维度搞反。我们用Pᵀ·f(x)时P是m×rPᵀ是r×m乘以m×1的f(x)得到r×1的输出正好是低维坐标。如果写成P·f(x)维度就错了。我最早实现时在这里卡了一个晚上矩阵乘法跑起来全是维度不匹配的报错。具体到训练样本矩阵X它的整体第一层特征是Z·P形状是n×r。因为f(x_i)就是Z矩阵的第i行这一步可以在矩阵级别一次算完不用循环。3.2 平衡阈值与第一层哈希码生成拿到低维特征之后什么时候符号化直接取正负号当然可以但会导致码不平衡可能某个维度上绝大多数样本都是正号那么这一位几乎没有区分度。衡量的标准是比特平衡度和独立性哈希码里每一位最好一半是1、一半是-1各维之间尽量不相关。做法是在训练集上对低维特征F1的每一维取中位数作为阈值b1。样本的低维坐标大于阈值记1小于阈值记-1。这样从训练集整体看每位码的产生概率接近均匀分布汉明距离的空间利用率更高。中位数阈值还有一个额外的工程好处它天然屏蔽了特征尺度变化。就算某个维度整体偏大或偏小中位数也能自适应地把那一维分成两半。3.3 第一层压缩函数的代码实现我用Python写一个紧凑版本方便你把流程跑通。import numpy as np from sklearn.cluster import KMeans def compute_P_matrix(X, anchors, sigma, k_sparse5): # X: n x d # anchors: m x d n X.shape[0] m anchors.shape[0] # 1. 计算高斯核相似度并做近邻截断 # 这里用矩阵距离计算避免循环 D2 ((X[:, None, :] - anchors[None, :, :]) ** 2).sum(axis2) # n x m Z_full np.exp(-D2 / (2 * sigma * sigma)) Z np.zeros_like(Z_full) for i in range(n): # 仅保留最近的k_sparse个锚点 idx np.argpartition(Z_full[i], -k_sparse)[-k_sparse:] Z[i, idx] Z_full[i, idx] # 行归一化 s Z[i].sum() if s 0: Z[i] / s # 2. 构造对角阵Λ Lambda Z.sum(axis0) # m维 Lambda_inv 1.0 / Lambda # 3. 对Γ Zᵀ Z Λ⁻¹ 做特征分解 Gamma Z.T Z * Lambda_inv[None, :] # m x m # 注意这里是用右乘Λ⁻¹实现Gamma[j,k] Σ_i Z[i,j] Z[i,k] / Λ[k] # 严谨处理应为 Z.T Z 再右乘 diag(Lambda_inv)这里写成矩阵方式更清晰 # Gamma Z.T Z np.diag(Lambda_inv) eigval, eigvec np.linalg.eigh(Gamma) r 32 # 第一层特征维度按需修改 order np.argsort(eigval)[::-1][:r] U eigvec[:, order] # m x r Sigma eigval[order] # r Sigma_inv_sqrt 1.0 / np.sqrt(Sigma 1e-8) # 4. 压缩矩阵 P Λ⁻¹ U Σ^(-1/2) P U * (Lambda_inv[:, None] * Sigma_inv_sqrt[None, :]) # m x r return Z, P这段代码里有一个数值稳定小细节Sigma_inv_sqrt里加了一个1e-8的epsilon防止特征值接近零时除出来无穷大。别小看这个epsilon我在实际跑实验时遇到过特征值为负的杂散方向浮点误差导致如果不做保护后面的P矩阵会出现NaN整个压缩函数直接报废。第一层码生成def first_layer_hash(Z_train, P, X_query, anchors, sigma, k_sparse5): # 先用训练样本得到阈值b1 F1_train Z_train P # n x r b1 np.median(F1_train, axis0) # 查询样本与锚点的稀疏相似度向量 f(x) m anchors.shape[0] nq X_query.shape[0] D2 ((X_query[:, None, :] - anchors[None, :, :]) ** 2).sum(axis2) Zq_full np.exp(-D2 / (2 * sigma * sigma)) Zq np.zeros_like(Zq_full) for i in range(nq): idx np.argpartition(Zq_full[i], -k_sparse)[-k_sparse:] Zq[i, idx] Zq_full[i, idx] s Zq[i].sum() if s 0: Zq[i] / s F1_query Zq P h1 (F1_query b1).astype(np.int8) * 2 - 1 return h1, b1注意一个点查询阶段用的稀疏近邻锚点数量和训练阶段必须保持一致否则查询样本的相似度向量分布会明显偏掉后面的哈希码质量也会跟着崩。4. 第二层压缩函数ReLU非线性、旋转矩阵学习与哈希码生成4.1 从ReLU到特征空间折叠第一层压缩函数是个纯线性操作它给出的是样本在锚点图流形坐标里的“原始读数”。如果直接对这个坐标做阈值化得到的二进制码过于依赖线性可分性。于是第二层压缩函数引入了两个变化一个非线性激活ReLU一个旋转矩阵R。ReLU的作用是把所有负坐标压成0。你可能觉得这操作太粗暴实际效果却很好它把低维特征空间进行了折叠原本落在负半轴的坐标全部归零相当于对同方向的正特征做了聚类增强。从哈希学习角度看ReLU提供了一个非线性决策边界让后续的阈值化有机会捕捉到线性空间里分不开的簇结构。这里有个直观的类比第一层像是把人从三维世界“拍扁”到二维影子第二层ReLU更像是把影子里暗的那部分全部涂黑然后再旋转画布让明暗分布最有辨别力的方向对齐到新坐标轴。这样你再在二维平面上划线就能把之前叠在一起的两拨人分辨开。4.2 旋转矩阵R的学习最大化码方差第二层特征F2(x) ReLU(F1(x))得到之后直接阈值化也可以但效果并不好。原因在于ReLU把一半信息压到零导致特征向量内部各维度之间相关性很强码位之间冗余度高。为了降低冗余、增强区分度AGH需要在F2之上再学一个旋转矩阵R将特征重新对齐使得投影后的各维方差尽可能拉开。具体做法是PCA的思路在训练集上计算所有样本的F2矩阵去中心化然后做主方向提取。前r2个主方向就是旋转矩阵R的列。这样当样本的F2投影到R上时每个码位对应不同的主方向方差最大码之间的独立性也最好。实现细节上不加正则的PCA在特征维度r较大时容易出现过拟合。我一般在计算协方差时加一个小的L2正则项相当于对协方差矩阵对角元素加一个常数这样学到的旋转矩阵更稳尤其当训练样本没到几万条时这个正则能明显提升二层码的泛化表现。PCA之外也有把R当作随机旋转矩阵用的做法但随机旋转对码的区分度帮助有限。我更推荐基于方差的PCA学法。如果原始维度很高而样本量不足可以先降维再做PCA避免小样本协方差估计噪声过大。4.3 第二层哈希码与两层码拼接第二层哈希码的步骤是样本过F1再过ReLU得到F2然后投影到R上阈值化。阈值b2同样在训练集上取中位数。有两点操作提示第一层码长r1和第二层码长r2不需要相等通常总码长r r1 r2推荐设置r1大于等于r2因为第一层承载的结构信息更基础第二层负责微调。拼接顺序要固定。训练和查询时必须按相同的顺序拼接h1和h2否则会直接破坏哈希码的语义。第二层代码实现如下def second_layer(R, F1_query, b2): F2 np.maximum(0, F1_query) # ReLU proj F2 R # nq x r2 h2 (proj b2).astype(np.int8) * 2 - 1 return h2 def learn_rotation_matrix(F1_train, r2, reg1e-3): F2 np.maximum(0, F1_train) mean F2.mean(axis0, keepdimsTrue) F2_c F2 - mean C (F2_c.T F2_c) / F2_c.shape[0] reg * np.eye(F2_c.shape[1]) eigval, eigvec np.linalg.eigh(C) order np.argsort(eigval)[::-1][:r2] R eigvec[:, order] # r x r2 return R, mean注意learn_rotation_matrix返回的mean在查询阶段要用到F2_query - mean之后再过R。如果省略去中心化旋转方向会有偏差实测下来mAP会掉1到2个点。返工过一次之后我就把这步焊死在代码里了。 最终两层哈希码拼接 python def concat_hash(h1, h2): return np.concatenate([h1, h2], axis1)5. 双层压缩函数的完整训练与查询流程整合5.1 训练流程梳理把前面的模块拼起来一套完整的AGH训练流程包括K-means聚类得到锚点矩阵anchorsm×d。用训练数据X计算锚点图矩阵Z得到归一化稀疏矩阵。构造Λ、Γ做m阶特征分解取前r个方向得到压缩矩阵P。计算训练数据的第一层特征F1_train Z P取中位数阈值b1。对F1_train施加ReLU得到F2_train。对F2_train去中心化后做PCA得到旋转矩阵Rr×r2和中心向量mean。计算投影后的中位数阈值b2。输出压缩参数anchors、sigma、k_sparse、P、R、mean、b1、b2。这八个参数配合查询阶段的相似度计算逻辑就能对任意新的查询样本生成哈希码。我觉得一个常见的工程误区是把P和R合并成一个变换矩阵再整体量化。从数学上合并矩阵是可行的但一旦折叠你后续想单独调第二层的ReLU阈值或旋转维度就非常麻烦。建议训练完后保留原始结构不要提前融合。5.2 查询流程与汉明空间检索查询阶段不需要重新做K-means、特征分解或PCA只需要按训练阶段的参数套用相似度计算与映射流程计算查询样本x与anchors的高斯核相似度截断并归一化得到f(x)。F1(x) f(x) P。h1 sign(F1(x) - b1)。F2(x) ReLU(F1(x))去中心化后投影到Rproj (F2(x) - mean) R。h2 sign(proj - b2)。拼接h1和h2得到最终哈希码。检索时对数据库里所有样本的哈希码建倒排索引或者直接用汉明距离扫描——这阶段是纯位运算速度极快。工业落地时常用策略是“汉明距离粗排 原始特征精排”先用汉明距离从几千万个码里筛出几百个候选再对这数百个样本计算原始距离做精排序。这套组合拳在图像检索和推荐召回里都非常实用。5.3 参数配置建议与检索评估关于参数配置直接给一组我实际跑过的经验值参数推荐范围说明锚点数m总样本量的1%~5%不超过5000太小近似误差大太大K-means耗时高相似度稀疏近邻k_sparse2~10默认5截断范围影响降噪也影响Z的非零占比第一层码长r1总码长r的60%~80%第一层承载基础结构信息占比应更大第二层码长r2总码长r的20%~40%第二层负责非线性细化RBF带宽sigma用锚点间距离中位数初始化再调优太小Z会退化到每个样本只和一个锚点相关太大Z会趋向均匀评估时先算检索召回率RecallK或mAP再对比训练时间和查询延迟。我自己在开源数据集上做的对比是相同总码长比如64位下AGH的双层结构比单层谱哈希mAP高出5~10个百分点。6. 压缩函数实现中的坑位与工程化解法6.1 矩阵数值稳定性与奇异值保护AGH的核心运算绕不开特征分解。Z矩阵出现稀疏近邻且带宽sigma偏小的时候Γ的特征值会有一批接近零甚至小于零取倒数再开根号就会炸。加上1e-8的epsilon不是万能的更稳的做法是加一个和Γ对角线量级匹配的jitter比如Gamma 1e-6 * np.trace(Gamma) / m * np.eye(m)再做特征分解。这个小改动能让特征向量的方向更稳。我遇到过一次极度稀疏场景k_sparse2且大量样本只与同一个锚点相似导致Λ里某些对角元接近零Λ⁻¹直接变成了巨大的数。这种情况下P矩阵的某些维度会被异常放大哈希码就废了。规避方案对Λ做下限截断设置min_Lambda 1e-6小于这个值的按这个值算。6.2 RBF带宽sigma的选择策略sigma是所有参数里最需要花心思的。AGH里Z矩阵的元素是高斯核相似度sigma决定了“连接强度”的范围。如果sigma太小Z的每一行退化成独热向量锚点图实际上退化成最近邻哈希数据结构信息大量丢失如果sigma太大Z的每一行接近均匀分布锚点之间区分度全无第二层PCA学出来的R方向也会失去意义。我的经验是两步走先用所有锚点间的成对距离中位数作为sigma初值然后在一小块验证集上做Recall100评估小范围搜索sigma乘子在0.5到2.0之间的几个档位。绝大多数场景下sigma落在锚点距离中位数的0.8~1.5倍区间里。6.3 第二层旋转矩阵的过拟合第二层学到的R矩阵本质上是训练集F2特征的前r2个主方向如果训练样本不够多这些主方向会过度拟合训练集新样本投影后方差迅速衰减码质量下滑。解决办法有三条一是把特征维度r先限制在合理区间32或64不要一上来就是256二是给协方差矩阵加L2正则三是在足够大的样本上训练。如果样本量少于5万条我建议r2不要超过16每一次验证都会提醒你这一点。6.4 在线新增数据时的阈值更新问题工业场景里数据是源源不断进来的。直接把新样本加入数据库但不更新b1和b2时间一长中位数阈值就会漂移。解法是周期性用采样数据重新统计阈值每次采样几千条计算它们在当前P和R下的投影分布更新阈值。锚点、P和R可以低频重训阈值则可以高频更新。这样做能在保持整体压缩函数稳定的同时维持哈希码的平衡度。还有一点容易被忽略新样本进入后如果原来被ReLU压成零的方向慢慢积累了正特征说明老的非线性方向不足以表达新数据分布了这时候就该考虑重训R矩阵而不是继续加大阈值刷码平衡。我通常用“正特征比例”作为监控指标——F2矩阵里非零元素占比低于10%时就该触发第二层重训了。结尾的一些心得双层锚点图哈希的压缩函数实际落地比我预想的要敏感。第一层映射P几乎决定了下限第二层旋转R决定上限。P矩阵的数值稳定性、sigma的选择、稀疏近邻数的设定任何一个环节波动后面两层码都会受到影响。建议在新数据集上先跑通全流程打印出F1特征的均值方差和中位数阈值确认每个维度都在合理范围再去做检索评估。省掉这一步你很容易被奇怪的召回率波动浪费一整天。最后分享一个小技巧训练完成后把P、R、b1、b2阈值都存成npy或二进制文件同时保存一份sigma和k_sparse配置查询服务直接加载这组参数即可不需要保留训练数据和聚类状态很方便。
锚点图哈希AGH双层压缩函数解析：从谱哈希到亿级近邻检索
做大规模近邻检索的时候大家多少都会撞上同一堵墙数据量一旦过了百万级精确检索打不过延迟指标暴力扫描又扛不住。树形索引呢二维三维里表现还行维度一高就开始表演“维度灾难”退化成线性扫描。这时候哈希检索成了折中方案——把实数向量压缩成几十到几百比特的二进制码用汉明距离近似样本之间的相似度。但哈希方法也有讲究我用过一个叫Anchor Graph Hashing锚点图哈希简称AGH的算法它的双层压缩函数设计相当精巧也算是我做亿级图像去重实验时少数几次“跑得动、效果还不拉胯”的谱哈希变体。当年第一次跑谱哈希直接卡死在小规模数据上——算法要求把所有样本的邻接图构造出来再对图拉普拉斯做特征分解复杂度在O(n²)以上十万条样本就让人头皮发麻。AGH之所以能在大数据场景下站稳脚跟核心思路就是通过锚点anchor把原始邻接图压成低秩锚点图再用一个双层锚点图哈希压缩函数把数据非线性地映射到二进制码。这篇文章我就把它内部的两个压缩函数掰开揉碎讲清楚数学推导、代码实现和工程里的坑。这篇文章适合正在实现或调优AGH的人也适合那些不想只调包、想理解“锚点图怎么近似邻接图”“两层压缩函数各自在做什么”的工程同学。代码部分我用Python风格的伪代码写方便你落地到自己项目里改。1. 为什么AGH需要双层压缩函数线性哈希的容量瓶颈1.1 邻接图哈希在大数据上为什么消受不起传统谱哈希的核心逻辑是基于全部数据构造邻接图计算图拉普拉斯的前几个小特征值对应的特征向量然后把特征向量阈值化得到一位位哈希码。这思路在几百条数据上没问题一旦数据量到了几十万条邻接矩阵是n×n的稠密矩阵光存储就是几十个GB特征分解更是把计算资源吃干净。工程上遇到的第一道坎就是“图根本建不起来、特征根本算不动”。AGH的逻辑是把“全局图”替换成“锚点图”。什么叫锚点你可以把它理解为数据空间中的一组代表点最常用的获取方式就是K-means聚类中心。假设我们有n条样本聚出m个锚点m远小于n。然后我们不直接计算样本两两之间的距离而是计算每条样本和这m个锚点之间的相似度组成一个n×m的稀疏矩阵Z。这个Z矩阵的行数再大也无所谓因为列数m受控矩阵是低秩的存起来就是稀疏格式算起来也快得多。锚点图的本质就是“用m个中心去近似n个点之间完整的邻接关系”。在AGH的整个流程里锚点图矩阵Z是一切的地基。双层压缩函数接收的输入就是基于Z推导出的特征映射矩阵。也就是说理解压缩函数之前你得先搞清楚Z是怎么构造、怎么归一化、怎么参与特征分解的——这些步骤直接决定后续压缩函数的输出质量。1.2 单层线性哈希的表达能力天花板早期谱哈希的做法是直接用线性映射把数据投影到特征向量张成的空间然后符号化。这种方式本质上假设数据流形可以用一个线性子空间去近似。现实中的数据哪会这么听话图像特征、文本嵌入、用户行为向量这些高维数据落到低维流形上往往是弯曲的、多模态的一个线性投影很难把不同聚类结构分开。我举个直观的例子。假设两个簇在原始空间里像同心圆套在一起线性投影到一维时两个簇很可能重叠阈值化之后码位严重冲突。这时候如果你先把投影结果过一个ReLU把负半轴的信息折叠到零再学一个旋转矩阵去重新分配各个维度的权重就相当于给线性映射加分了非线性激活和特征重对齐的能力。AGH第二层压缩函数做的正是这件事。所以两层压缩函数的分工非常清晰第一层负责用谱方法拿到数据在流形上的低维坐标是线性拟合第二层对低维坐标做非线性拉伸再旋转到方差最大的方向上增强哈希码的区分度。用好这个分工你才能在手写实现时做出正确的设计选择。2. 压缩函数的前置工程锚点图矩阵与近似特征向量求解2.1 锚点选择与核相似度计算锚点选择最省事也最稳定的方案就是K-means。需要注意一个实操细节K-means的初始化次数不要省跑三次选目标函数最小的一次锚点分布才均匀。锚点数m怎么定经验值通常是样本量的1%到5%但别超过5000个。再大一方面K-means本身吃时间另一方面后面的r×m矩阵运算会变慢压缩收益就没有了。选好锚点之后构造相似度矩阵。假设样本为x_i锚点为a_k用高斯核计算相似度s_{ik} exp(-||x_i - a_k||^2 / (2 * sigma^2))这里的sigma是核带宽我后面会专门讲它怎么选。原始高斯核矩阵里每个样本对每个锚点都有一个权重如果全部保留Z矩阵虽然还没爆炸但计算和存储成本也不低。工程上通常做一步截断对每个样本只保留与它最近的k_sparse个锚点的相似度其余置零。推荐k_sparse取2~10常见取5。然后按行归一化每行的权重除以该行所有非零权重之和让每行之和等于1。这一步很重要等于把相似度变成了概率分布能抵御不同样本间尺度差异带来的影响。2.2 特征向量的Nyström近似从Z到压缩矩阵P有了归一化后的Z矩阵下一步是求锚点图的近似特征向量。推导过程不啰嗦但结果是关键我们想求低秩相似矩阵W ZΛ⁻¹Zᵀ的近似特征向量其中Λ是对角矩阵对角元是Z每一列的和即Λ diag(Zᵀ·1_n)。直接对W做特征分解依然是n×n的复杂度所以通过Nyström方法绕一圈构造小矩阵 Γ Zᵀ·Z·Λ⁻¹维度是m×m。对Γ做特征分解取前r个最大特征值对应的特征向量组合成Um×r矩阵对应特征值组成对角阵Σ。计算压缩矩阵 P Λ⁻¹·U·Σ^(-1/2)维度是m×r。为什么这么算核心在于Γ是m×m的我们只需要对m阶小矩阵做特征分解复杂度和全量数据n完全脱钩。这里有个反直觉的点Nyström近似取的是最大特征值对应的特征向量而不是最小特征值。因为W表示样本间的相似度累积大特征值方向对应的是数据聚集最强的方向取这些方向等于抓住了流形的主干结构。P矩阵就是第一层压缩函数的主角。后续无论是训练样本还是新来的查询样本只要先算出它和锚点的相似度向量f(x)再左乘Pᵀ就能得到低维特征F1(x)整条链路就通了。3. 第一层压缩函数线性投影、阈值化与哈希码生成3.1 F1(x) Pᵀ·f(x) 的流形坐标含义第一层压缩函数做的事很纯粹把样本x在高维空间里的锚点相似度向量f(x)映射到一个r维低维空间。f(x)是m维的每个分量表示x与某个锚点的归一化相似度经过Pᵀ线性变换后得到r维的坐标向量这些坐标可以理解为样本在锚点图拉普拉斯特征空间中的近似位置。同一流形上的近邻样本在这个坐标空间里会被拉近不同流形结构则被拉开。这里要强调Matrix P为什么是m×r而不是r×m。很多第一次实现的人容易把维度搞反。我们用Pᵀ·f(x)时P是m×rPᵀ是r×m乘以m×1的f(x)得到r×1的输出正好是低维坐标。如果写成P·f(x)维度就错了。我最早实现时在这里卡了一个晚上矩阵乘法跑起来全是维度不匹配的报错。具体到训练样本矩阵X它的整体第一层特征是Z·P形状是n×r。因为f(x_i)就是Z矩阵的第i行这一步可以在矩阵级别一次算完不用循环。3.2 平衡阈值与第一层哈希码生成拿到低维特征之后什么时候符号化直接取正负号当然可以但会导致码不平衡可能某个维度上绝大多数样本都是正号那么这一位几乎没有区分度。衡量的标准是比特平衡度和独立性哈希码里每一位最好一半是1、一半是-1各维之间尽量不相关。做法是在训练集上对低维特征F1的每一维取中位数作为阈值b1。样本的低维坐标大于阈值记1小于阈值记-1。这样从训练集整体看每位码的产生概率接近均匀分布汉明距离的空间利用率更高。中位数阈值还有一个额外的工程好处它天然屏蔽了特征尺度变化。就算某个维度整体偏大或偏小中位数也能自适应地把那一维分成两半。3.3 第一层压缩函数的代码实现我用Python写一个紧凑版本方便你把流程跑通。import numpy as np from sklearn.cluster import KMeans def compute_P_matrix(X, anchors, sigma, k_sparse5): # X: n x d # anchors: m x d n X.shape[0] m anchors.shape[0] # 1. 计算高斯核相似度并做近邻截断 # 这里用矩阵距离计算避免循环 D2 ((X[:, None, :] - anchors[None, :, :]) ** 2).sum(axis2) # n x m Z_full np.exp(-D2 / (2 * sigma * sigma)) Z np.zeros_like(Z_full) for i in range(n): # 仅保留最近的k_sparse个锚点 idx np.argpartition(Z_full[i], -k_sparse)[-k_sparse:] Z[i, idx] Z_full[i, idx] # 行归一化 s Z[i].sum() if s 0: Z[i] / s # 2. 构造对角阵Λ Lambda Z.sum(axis0) # m维 Lambda_inv 1.0 / Lambda # 3. 对Γ Zᵀ Z Λ⁻¹ 做特征分解 Gamma Z.T Z * Lambda_inv[None, :] # m x m # 注意这里是用右乘Λ⁻¹实现Gamma[j,k] Σ_i Z[i,j] Z[i,k] / Λ[k] # 严谨处理应为 Z.T Z 再右乘 diag(Lambda_inv)这里写成矩阵方式更清晰 # Gamma Z.T Z np.diag(Lambda_inv) eigval, eigvec np.linalg.eigh(Gamma) r 32 # 第一层特征维度按需修改 order np.argsort(eigval)[::-1][:r] U eigvec[:, order] # m x r Sigma eigval[order] # r Sigma_inv_sqrt 1.0 / np.sqrt(Sigma 1e-8) # 4. 压缩矩阵 P Λ⁻¹ U Σ^(-1/2) P U * (Lambda_inv[:, None] * Sigma_inv_sqrt[None, :]) # m x r return Z, P这段代码里有一个数值稳定小细节Sigma_inv_sqrt里加了一个1e-8的epsilon防止特征值接近零时除出来无穷大。别小看这个epsilon我在实际跑实验时遇到过特征值为负的杂散方向浮点误差导致如果不做保护后面的P矩阵会出现NaN整个压缩函数直接报废。第一层码生成def first_layer_hash(Z_train, P, X_query, anchors, sigma, k_sparse5): # 先用训练样本得到阈值b1 F1_train Z_train P # n x r b1 np.median(F1_train, axis0) # 查询样本与锚点的稀疏相似度向量 f(x) m anchors.shape[0] nq X_query.shape[0] D2 ((X_query[:, None, :] - anchors[None, :, :]) ** 2).sum(axis2) Zq_full np.exp(-D2 / (2 * sigma * sigma)) Zq np.zeros_like(Zq_full) for i in range(nq): idx np.argpartition(Zq_full[i], -k_sparse)[-k_sparse:] Zq[i, idx] Zq_full[i, idx] s Zq[i].sum() if s 0: Zq[i] / s F1_query Zq P h1 (F1_query b1).astype(np.int8) * 2 - 1 return h1, b1注意一个点查询阶段用的稀疏近邻锚点数量和训练阶段必须保持一致否则查询样本的相似度向量分布会明显偏掉后面的哈希码质量也会跟着崩。4. 第二层压缩函数ReLU非线性、旋转矩阵学习与哈希码生成4.1 从ReLU到特征空间折叠第一层压缩函数是个纯线性操作它给出的是样本在锚点图流形坐标里的“原始读数”。如果直接对这个坐标做阈值化得到的二进制码过于依赖线性可分性。于是第二层压缩函数引入了两个变化一个非线性激活ReLU一个旋转矩阵R。ReLU的作用是把所有负坐标压成0。你可能觉得这操作太粗暴实际效果却很好它把低维特征空间进行了折叠原本落在负半轴的坐标全部归零相当于对同方向的正特征做了聚类增强。从哈希学习角度看ReLU提供了一个非线性决策边界让后续的阈值化有机会捕捉到线性空间里分不开的簇结构。这里有个直观的类比第一层像是把人从三维世界“拍扁”到二维影子第二层ReLU更像是把影子里暗的那部分全部涂黑然后再旋转画布让明暗分布最有辨别力的方向对齐到新坐标轴。这样你再在二维平面上划线就能把之前叠在一起的两拨人分辨开。4.2 旋转矩阵R的学习最大化码方差第二层特征F2(x) ReLU(F1(x))得到之后直接阈值化也可以但效果并不好。原因在于ReLU把一半信息压到零导致特征向量内部各维度之间相关性很强码位之间冗余度高。为了降低冗余、增强区分度AGH需要在F2之上再学一个旋转矩阵R将特征重新对齐使得投影后的各维方差尽可能拉开。具体做法是PCA的思路在训练集上计算所有样本的F2矩阵去中心化然后做主方向提取。前r2个主方向就是旋转矩阵R的列。这样当样本的F2投影到R上时每个码位对应不同的主方向方差最大码之间的独立性也最好。实现细节上不加正则的PCA在特征维度r较大时容易出现过拟合。我一般在计算协方差时加一个小的L2正则项相当于对协方差矩阵对角元素加一个常数这样学到的旋转矩阵更稳尤其当训练样本没到几万条时这个正则能明显提升二层码的泛化表现。PCA之外也有把R当作随机旋转矩阵用的做法但随机旋转对码的区分度帮助有限。我更推荐基于方差的PCA学法。如果原始维度很高而样本量不足可以先降维再做PCA避免小样本协方差估计噪声过大。4.3 第二层哈希码与两层码拼接第二层哈希码的步骤是样本过F1再过ReLU得到F2然后投影到R上阈值化。阈值b2同样在训练集上取中位数。有两点操作提示第一层码长r1和第二层码长r2不需要相等通常总码长r r1 r2推荐设置r1大于等于r2因为第一层承载的结构信息更基础第二层负责微调。拼接顺序要固定。训练和查询时必须按相同的顺序拼接h1和h2否则会直接破坏哈希码的语义。第二层代码实现如下def second_layer(R, F1_query, b2): F2 np.maximum(0, F1_query) # ReLU proj F2 R # nq x r2 h2 (proj b2).astype(np.int8) * 2 - 1 return h2 def learn_rotation_matrix(F1_train, r2, reg1e-3): F2 np.maximum(0, F1_train) mean F2.mean(axis0, keepdimsTrue) F2_c F2 - mean C (F2_c.T F2_c) / F2_c.shape[0] reg * np.eye(F2_c.shape[1]) eigval, eigvec np.linalg.eigh(C) order np.argsort(eigval)[::-1][:r2] R eigvec[:, order] # r x r2 return R, mean注意learn_rotation_matrix返回的mean在查询阶段要用到F2_query - mean之后再过R。如果省略去中心化旋转方向会有偏差实测下来mAP会掉1到2个点。返工过一次之后我就把这步焊死在代码里了。 最终两层哈希码拼接 python def concat_hash(h1, h2): return np.concatenate([h1, h2], axis1)5. 双层压缩函数的完整训练与查询流程整合5.1 训练流程梳理把前面的模块拼起来一套完整的AGH训练流程包括K-means聚类得到锚点矩阵anchorsm×d。用训练数据X计算锚点图矩阵Z得到归一化稀疏矩阵。构造Λ、Γ做m阶特征分解取前r个方向得到压缩矩阵P。计算训练数据的第一层特征F1_train Z P取中位数阈值b1。对F1_train施加ReLU得到F2_train。对F2_train去中心化后做PCA得到旋转矩阵Rr×r2和中心向量mean。计算投影后的中位数阈值b2。输出压缩参数anchors、sigma、k_sparse、P、R、mean、b1、b2。这八个参数配合查询阶段的相似度计算逻辑就能对任意新的查询样本生成哈希码。我觉得一个常见的工程误区是把P和R合并成一个变换矩阵再整体量化。从数学上合并矩阵是可行的但一旦折叠你后续想单独调第二层的ReLU阈值或旋转维度就非常麻烦。建议训练完后保留原始结构不要提前融合。5.2 查询流程与汉明空间检索查询阶段不需要重新做K-means、特征分解或PCA只需要按训练阶段的参数套用相似度计算与映射流程计算查询样本x与anchors的高斯核相似度截断并归一化得到f(x)。F1(x) f(x) P。h1 sign(F1(x) - b1)。F2(x) ReLU(F1(x))去中心化后投影到Rproj (F2(x) - mean) R。h2 sign(proj - b2)。拼接h1和h2得到最终哈希码。检索时对数据库里所有样本的哈希码建倒排索引或者直接用汉明距离扫描——这阶段是纯位运算速度极快。工业落地时常用策略是“汉明距离粗排 原始特征精排”先用汉明距离从几千万个码里筛出几百个候选再对这数百个样本计算原始距离做精排序。这套组合拳在图像检索和推荐召回里都非常实用。5.3 参数配置建议与检索评估关于参数配置直接给一组我实际跑过的经验值参数推荐范围说明锚点数m总样本量的1%~5%不超过5000太小近似误差大太大K-means耗时高相似度稀疏近邻k_sparse2~10默认5截断范围影响降噪也影响Z的非零占比第一层码长r1总码长r的60%~80%第一层承载基础结构信息占比应更大第二层码长r2总码长r的20%~40%第二层负责非线性细化RBF带宽sigma用锚点间距离中位数初始化再调优太小Z会退化到每个样本只和一个锚点相关太大Z会趋向均匀评估时先算检索召回率RecallK或mAP再对比训练时间和查询延迟。我自己在开源数据集上做的对比是相同总码长比如64位下AGH的双层结构比单层谱哈希mAP高出5~10个百分点。6. 压缩函数实现中的坑位与工程化解法6.1 矩阵数值稳定性与奇异值保护AGH的核心运算绕不开特征分解。Z矩阵出现稀疏近邻且带宽sigma偏小的时候Γ的特征值会有一批接近零甚至小于零取倒数再开根号就会炸。加上1e-8的epsilon不是万能的更稳的做法是加一个和Γ对角线量级匹配的jitter比如Gamma 1e-6 * np.trace(Gamma) / m * np.eye(m)再做特征分解。这个小改动能让特征向量的方向更稳。我遇到过一次极度稀疏场景k_sparse2且大量样本只与同一个锚点相似导致Λ里某些对角元接近零Λ⁻¹直接变成了巨大的数。这种情况下P矩阵的某些维度会被异常放大哈希码就废了。规避方案对Λ做下限截断设置min_Lambda 1e-6小于这个值的按这个值算。6.2 RBF带宽sigma的选择策略sigma是所有参数里最需要花心思的。AGH里Z矩阵的元素是高斯核相似度sigma决定了“连接强度”的范围。如果sigma太小Z的每一行退化成独热向量锚点图实际上退化成最近邻哈希数据结构信息大量丢失如果sigma太大Z的每一行接近均匀分布锚点之间区分度全无第二层PCA学出来的R方向也会失去意义。我的经验是两步走先用所有锚点间的成对距离中位数作为sigma初值然后在一小块验证集上做Recall100评估小范围搜索sigma乘子在0.5到2.0之间的几个档位。绝大多数场景下sigma落在锚点距离中位数的0.8~1.5倍区间里。6.3 第二层旋转矩阵的过拟合第二层学到的R矩阵本质上是训练集F2特征的前r2个主方向如果训练样本不够多这些主方向会过度拟合训练集新样本投影后方差迅速衰减码质量下滑。解决办法有三条一是把特征维度r先限制在合理区间32或64不要一上来就是256二是给协方差矩阵加L2正则三是在足够大的样本上训练。如果样本量少于5万条我建议r2不要超过16每一次验证都会提醒你这一点。6.4 在线新增数据时的阈值更新问题工业场景里数据是源源不断进来的。直接把新样本加入数据库但不更新b1和b2时间一长中位数阈值就会漂移。解法是周期性用采样数据重新统计阈值每次采样几千条计算它们在当前P和R下的投影分布更新阈值。锚点、P和R可以低频重训阈值则可以高频更新。这样做能在保持整体压缩函数稳定的同时维持哈希码的平衡度。还有一点容易被忽略新样本进入后如果原来被ReLU压成零的方向慢慢积累了正特征说明老的非线性方向不足以表达新数据分布了这时候就该考虑重训R矩阵而不是继续加大阈值刷码平衡。我通常用“正特征比例”作为监控指标——F2矩阵里非零元素占比低于10%时就该触发第二层重训了。结尾的一些心得双层锚点图哈希的压缩函数实际落地比我预想的要敏感。第一层映射P几乎决定了下限第二层旋转R决定上限。P矩阵的数值稳定性、sigma的选择、稀疏近邻数的设定任何一个环节波动后面两层码都会受到影响。建议在新数据集上先跑通全流程打印出F1特征的均值方差和中位数阈值确认每个维度都在合理范围再去做检索评估。省掉这一步你很容易被奇怪的召回率波动浪费一整天。最后分享一个小技巧训练完成后把P、R、b1、b2阈值都存成npy或二进制文件同时保存一份sigma和k_sparse配置查询服务直接加载这组参数即可不需要保留训练数据和聚类状态很方便。