Maximally Consistent Sampling and the Jaccard Index of Probability Distributions
Ryan Moulton, Yunjiang Jiang
cs.DS, cs.IR
2018-09-12
Google 与京东提出 P-MinHash，碰撞概率是尺度不变的 J_P。它是采样型 LSH 的帕累托最优，和 Jensen-Shannon 的关系比加权 Jaccard 更紧，取回 JSD<0.25 的网页时 64 个哈希相当于加权 MinHash 的 128 个。
MinHash 是大规模去重和近邻检索的基本零件:随机排列下，两个集合抽到同一个最小元素的概率等于 Jaccard。落到带权重的对象上，Chum 等人给出两条路。一条给元素固定全局权重，适合 idf;另一条处理正向量，碰撞概率是加权 Jaccard JW = Σ min(xi，yi) / Σ max(xi，yi)。后续工作把第二条做到任意正权重，速度和 Ioffe、Shrivastava 看齐，目标仍是 JW。
JW 当概率分布的相似度不好用。它不尺度不变:把集合变成均匀分布再比，集合大小不同时 JW 会低于原来的 Jaccard。它对支撑集变化不敏感，JW((a，b，c，0)，(a，b，0，c)) 等于 JW((a+c，b)，(a，b+c))，信息论里支撑不一致通常是最差分。从无权重 MinHash 切到 JW，碰撞概率还会整体下降，原来调好的哈希条数和拼接长度容易失效。
检索系统真正想要的，是一个把输入当分布来看的 Jaccard 替代:尺度不变、在均匀分布上不低于集合 Jaccard、对支撑变化敏感、还能当碰撞概率实现。
P-MinHash 从 Chum 的第一条出发，扩到任意正向量。每个非零坐标 i 抽一个指数变量 ei = −log Ui / xi，输出 argmini ei。这是指数竞速:被抽中的概率正比于 xi。同一组哈希种子用在 x 和 y 上，碰撞概率就是新的相似度
JP(x，y) = Σ{i: xi，yi>0} 1 / Σj max(xj/xi， yj/yi)。
它尺度不变，H(αx)=H(x)。几何上，这相当于在概率单纯形里按 x 切开，再在每块里钉同一个随机点当代表;两块同面相交的体积之和正比于 JP。
稀疏数据按非零个数线性扫描，和 Ioffe 2010 同阶。稠密或连续数据把同一套指数流接到 A Sampling 的 Global-Bound 算法上，共享有序哈希前缀，运行时间和 Shrivastava 2016 的稠密加权 MinHash 同阶，并覆盖连续分布。
论文证明 JP 是采样型 LSH 的帕累托最优:任何采样方法若在某一对上超过 JP，必须在另一对更近的分布上损失碰撞。JW 被 JP 支配。若 JW=(1−p)/(1+p)，则该值 ≤ JP ≤ 1−p，两端都有分布取到。1−JP 是概率单纯形上的度量。
实验用 66 亿高 PageRank 网页的归一化 unigram 词向量。用 2 个 W-MinHash 之和做重要性抽样，打了 1 亿对，再按抽样概率的倒数加权，模拟全部非零对。
JP 和 Jensen-Shannon 散度的关系明显更紧。大约 10^{−7} 的对落在他们给 JP 画的近似下界下面，最远低 0.0077;JW 有 7×10^{−3} 的对落到同一条曲线下，最远低 0.16。相对集合 Jaccard，JP 的对数比大致居中，JW 稳定偏低，和均匀分布上的理论行为一致。
键值检索里，AND(把多个哈希加起来当键)几乎免费，OR(输出多组独立键)线性涨存储和 CPU。碰撞概率更高的算法，高召回更便宜。取回 JSD<0.25 的对，P-MinHash 用 64 个哈希达到 W-MinHash 用 128 个的精度-召回。更反常的是，在低成本区取回 JW>0.5 的对，P-MinHash 也略好:JP 在 JW 已经高的对上更高，两个哈希相乘时接近「1 个哈希的召回、2 个哈希的精度」。成本继续加大后，JW 才凭分数差异本身反超。
如果对象是语言模型的主题分布、图像的直方图、网页的词分布，继续用 JW 当 MinHash 碰撞概率，是在用一个不尺度不变、对支撑不敏感的集合权重去近似信息论距离。P-MinHash 把碰撞概率直接换成更像 JSD 的量，稀疏稠密两套实现都不比当时的 SOTA 慢，而且 64 对 128 这条曲线对倒排和键值店是真金。从无权重 MinHash 迁过来，JP 还更接近原来的 Jaccard，哈希条数不用立刻重调。
2018 年的 ICDMW 论文，算法本身不新到需要等一篇跟进才能用。该用的场景是「输入应当作分布」，不是「输入是带计数的多重集」。后一种 JW 仍是对的目标。
JP 的式子 nested max，朴素计算 O(n^2)，论文给出按 xi/yi 排序后 O(n log n)，实现时不能按公式直译。帕累托最优不是「每一对都最高」:可以构造树形递归采样，让某个坐标的碰撞达到 min(xi，yi)，代价是别的对下降。网页实验的重要性抽样本身用了 W-MinHash，对极端不相似的对覆盖取决于这个提案分布。JP 与 JSD 的下界是数值欧拉-拉格朗日近似，不是定理;样本里仍有 10^{−7} 的对破界。连续分布的 JP 用越来越细的有限剖分取 inf，奇异测度和互不正交的支撑要小心定义。没有公开代码附录。对现代向量检索，这篇解决的是高维稀疏计数/分布的 LSH，不是稠密 embedding 的 ANN。