到性质的距离 | Codeboy's Blog

形式陈述

从点到集合的距离

设对象空间 $\Omega$ 是度量空间，距离为 $d$ ，性质是非空子集 $\mathcal P\subseteq\Omega$ 。对象 $x$ 到性质的距离定义为

\operatorname{dist}_d(x,\mathcal P) =\inf_{y\in\mathcal P}d(x,y).

这里取距离值集合的下确界；它非空且有下界零，所以实数下确界存在。在有限对象空间中，下确界由某个 $y^*\in\mathcal P$ 取得，可以写成最小值；在无限空间里最近点未必存在，保留 $\inf$ 更准确。若 $x\in\mathcal P$ ，距离为 $0$ 。反过来只有在 $\mathcal P$ 对所用度量闭时，距离为 $0$ 才保证 $x\in\mathcal P$ ；有限离散模型通常自动满足这一点。

性质测试取 $\operatorname{dist}(x,\mathcal P)\ge\varepsilon$ 为 far 侧，并把 $x\in\mathcal P$ 作为 yes 侧。距离是对象与性质的几何量，测试复杂度则是通过指定 oracle 区分两侧所需的访问量；一个距离容易定义，不表示它容易精确计算。

归一化 Hamming 距离

对 $n\ge1$ 、 $x,y\in\Sigma^n$ ，Hamming 距离 $d_H(x,y)$ 计算不同坐标数。性质测试通常使用

d_n(x,y)=\frac{d_H(x,y)}n,

使距离落在 $[0,1]$ ，并让固定 $\varepsilon$ 表示必须改动常数比例坐标。于是

\operatorname{dist}(x,\mathcal P) =\frac1n\min_{y\in\mathcal P} \bigl|\{i:x_i\ne y_i\}\bigr|.

raw 距离与 normalized 距离不能共用同一个 $\varepsilon$ 。若 raw $d_H(x,\mathcal P)=5$ ，它在 $n=20$ 时是四分之一输入，在 $n=10^6$ 时只是极小比例；省略分母会让“亚线性测试”随编码长度失去稳定含义。

直觉

到性质的距离衡量最少需要修改多少规范基本单元才能进入某个合法对象，而普通测试器区分性质成员与距离至少 $\varepsilon$ 的对象，不必真的找到最近修复。性质闭时，成员侧恰好就是零距离集合。分母和表示决定一个编辑占整体的比例，因此同一抽象对象在稠密图、邻接表或冗余编码下可能对应不同测试问题。

例子与边界

常量字符串性质的最近编辑

令

\mathcal P_n=\{0^n,1^n\}.

若 $x$ 的 Hamming 重量为 $w=|\{i:x_i=1\}|$ ，把 $x$ 改成 $0^n$ 需要翻转 $w$ 位，改成 $1^n$ 需要翻转 $n-w$ 位，因此

\operatorname{dist}(x,\mathcal P_n) =\frac{\min\{w,n-w\}}n.

对 $x=00101$ ，重量为 $2$ 。翻转第 $3$ 、 $5$ 位可得到 00000，翻转另外三个 $0$ 才能得到 11111，故最近合法对象是 00000，归一化距离为 $2/5$ 。这里的距离不仅给出数值，还保留“至少要改哪一类基本单元”的概念图像。

若 $n$ 为偶数且 $w=n/2$ ，两个常量串同为最近对象。距离仍唯一，最近修复却不唯一；测试器只需区分 close/far，并不承诺选择某个修复方向。把一个最邻近对象写成“唯一真值”会在这种 tie 上失败。

表示决定基本编辑

字符串的 Hamming 模型只允许替换等长位置；若允许插入和删除，应使用编辑距离，并明确以原长度、目标长度还是二者最大值归一化。不同约定会改变短串附近的比例，不能只换距离名称而沿用原 $\varepsilon$ 。

图的情况更敏感。在稠密邻接矩阵模型中，基本编辑是一条潜在边，分母通常为 $\Theta(n^2)$ ；改变一条边只占约 $1/n^2$ 。在最大度 $d$ 的邻接表模型中，oracle 暴露的是 $O(dn)$ 个邻接槽，距离按需要修改的槽数相对 $dn$ 归一化。同一个抽象图命题在两种表示下会产生不同的 far 集合和查询界。

编码还可能复制信息。若每个逻辑 bit 在文件中等次数重复十次，且只比较合法编码，raw Hamming 距离与总长度都乘十，归一化距离反而保持不变。若不同坐标重复次数不同，就会改变各坐标的权重；若允许输入含不一致副本，还要说明性质如何约束这些副本。冗余编码的影响应按实际分子、分母和合法域计算。

推论与应用

close、far 与无约束带

说 $x$ 是 $\varepsilon$ -close，通常表示 $\operatorname{dist}(x,\mathcal P)\le\varepsilon$ ；说它是 $\varepsilon$ -far，则常取 $\operatorname{dist}(x,\mathcal P)\ge\varepsilon$ 。边界是否使用严格不等号是约定问题，但同一结论中要保持一致。

基础测试模型的 yes 侧是性质成员；对闭性质，它恰等于零距离集合，no 侧是距离至少 $\varepsilon$ 的对象。距离位于 $(0,\varepsilon)$ 的对象不受输出约束。若任务要区分距离至多 $\varepsilon_1$ 与至少 $\varepsilon_2$ ，其中 $0<\varepsilon_1<\varepsilon_2$ ，那是具有两条正阈值的另一种 promise，不能默认为基础定义已经保证。

距离到性质也不等于违反局部约束的比例。一个对象可能只显露少量局部冲突，却需要大量协调修改才能进入 $\mathcal P$ ；也可能有许多彼此重叠的违规，只需一次编辑共同修复。把局部拒绝概率与全局距离联系起来需要结构定理，而不是从 $\inf$ 定义直接得到。

退化与计算边界

若 $\mathcal P=\Omega$ ，每个对象距离都为 $0$ ，测试器可以不查询便接受。若性质为空，通常把到空集距离定义为 $+\infty$ ，但此时没有 completeness 输入，测试问题退化；多数框架直接要求性质非空。

找到最近 $y^*$ 可能是困难的优化问题，甚至在表示隐式时无法有效求值。性质测试的价值之一正是在不计算精确距离、也不构造 $y^*$ 的情况下区分性质成员与距离至少 $\varepsilon$ 的对象。因此不能把“定义中取最小值”误读为测试器可以免费调用最近点 oracle。

距离若只是伪度量，两个不同表示可能距离为 $0$ 。此时性质应在零距离等价类上闭合，或先选规范表示；否则一个不属于 $\mathcal P$ 的对象可能与性质距离为 $0$ ；它不在普通测试的 yes 侧，也不在任何正阈值的 far 侧。成员判定与零距离判定此时是不同任务。

参考资料

Oded Goldreich, Introduction to Property Testing, Cambridge University Press, 2017, Chapters 1 and 8.
Dana Ron, “Property Testing: A Learning Theory Perspective,” Foundations and Trends in Machine Learning 1(3), 2008, pp. 307–402.
Ronitt Rubinfeld and Madhu Sudan, “Robust Characterizations of Polynomials with Applications to Program Testing,” SIAM Journal on Computing 25(2), 1996, pp. 252–271.

形式陈述 ​

从点到集合的距离 ​

归一化 Hamming 距离 ​

常量字符串性质的最近编辑 ​

表示决定基本编辑 ​

close、far 与无约束带 ​

退化与计算边界 ​