到性质的距离

从点到集合的距离 ​

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

$${\mathrm{dist}}_d(x,\mathcal{P})=\underset{y\in \mathcal{P}}{inf}d(x,y).$$

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

性质测试公理库性质测试模型Property testing model · Property testing通过少量 oracle 查询区分完全满足性质的对象与到该性质至少相距 ε 的对象，并允许 gap 内行为任意。取 $\mathrm{dist}(x,\mathcal{P})\ge \epsilon$ 为 far 侧，并把 $x\in \mathcal{P}$ 作为 yes 侧。距离是对象与性质的几何量，测试复杂度则是通过指定 oracle 区分两侧所需的访问量；一个距离容易定义，不表示它容易精确计算。

归一化 Hamming 距离 ​

对 $x,y\in {\mathrm{\Sigma }}^n$，Hamming 距离公理库Hamming 距离Hamming distance两个等长字在对应位置不同的坐标数。 $d_H(x,y)$ 计算不同坐标数。性质测试通常使用

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

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

$$\mathrm{dist}(x,\mathcal{P})=\frac{1}{n}\underset{y\in \mathcal{P}}{min}|\{i:x_i\ne y_i\}|.$$

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

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

令

$${\mathcal{P}}_n=\{0^n,1^n\}.$$

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

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

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

编码还可能复制信息。若每个逻辑 bit 在文件中重复十次，按物理位计算的 Hamming 距离会把一次逻辑修改放大十倍，却不应因此宣称性质更远。性质测试必须针对规范表示定义基本编辑；任意冗余编码需要单独说明其距离保持关系。

close、far 与无约束带 ​

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

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

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

退化与计算边界 ​

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

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

距离若只是伪度量，两个不同表示可能距离为 $0$。此时性质应在零距离等价类上闭合，或先选规范表示；否则一个不属于 $\mathcal{P}$ 的对象可能与性质距离为 $0$，基础测试 promise 的语义会变得含混。

参考资料

• 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.