容忍性质测试

两阈值 promise ​

设性质为 $\mathcal{P}\subseteq \mathrm{\Omega }$，距离记作

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

给定 $0\le {\epsilon }_1<{\epsilon }_2\le 1$，一个 $({\epsilon }_1,{\epsilon }_2)$-tolerant tester 满足

$$\begin{array}{rl}d(x,\mathcal{P})\le {\epsilon }_1& ⟹\text{Pr}[T^x=\mathrm{accept}]\ge \frac{2}{3},\\ d(x,\mathcal{P})\ge {\epsilon }_2& ⟹\text{Pr}[T^x=\mathrm{reject}]\ge \frac{2}{3}.\end{array}$$

距离位于 $({\epsilon }_1,{\epsilon }_2)$ 的对象无约束。基础性质测试公理库性质测试模型Property testing model · Property testing通过少量 oracle 查询区分完全满足性质的对象与到该性质至少相距 ε 的对象，并允许 gap 内行为任意。是 ${\epsilon }_1=0$ 的特例；只把 no 阈值仍写作 $\epsilon$ 而不报告 close 阈值，会隐藏更强的完备性要求。

Gap 宽度是资源参数 ​

令

$$\mathrm{\Delta }={\epsilon }_2-{\epsilon }_1.$$

当 $\mathrm{\Delta }$ 缩小时，tester 必须分辨距离非常接近的对象，查询量通常随 $1/\mathrm{\Delta }$ 增长。Complexity 应写成 $q(n,{\epsilon }_1,{\epsilon }_2,\delta )$，而不是只依赖 far 阈值。

若能构造距离估计量 $\hat{d}$，满足

$$\text{Pr}[|\hat{d}-d(x,\mathcal{P})|\le \mathrm{\Delta }/3]\ge 1-\delta ,$$

便可在阈值中点附近切分得到 tolerant tester。反过来，对一系列阈值调用 tester 并做带置信度的二分，可形成粗距离估计；每次调用的错误需求并，不能把单次 $2/3$ 保证无限复用。

常量字符串的容忍测试 ​

令 $x\in \{0,1{\}}^n$，性质 $\mathcal{P}=\{0^n,1^n\}$。若 1 的比例为 $p$，则

$$d(x,\mathcal{P})=min\{p,1-p\}.$$

均匀独立查询 $m$ 个坐标，令样本均值为 $\hat{p}$，并估计

$$\hat{d}=min\{\hat{p},1-\hat{p}\}.$$

函数 $u\mapsto min\{u,1-u\}$ 是 1-Lipschitz，所以 $|\hat{d}-d|\le |\hat{p}-p|$。Hoeffding 界说明

$$m=O({\mathrm{\Delta }}^{-2}\log \frac{1}{\delta })$$

足以把估计误差控制在 $\mathrm{\Delta }/3$。取阈值 $({\epsilon }_1+{\epsilon }_2)/2$：close 对象高概率落在阈值下，far 对象高概率落在阈值上。

与非容忍常量测试相比，这里不能见到一对不同 bit 就立即拒绝；close 对象本来允许含少量少数 bit。Tester 必须估计少数比例，而不是只寻找一个局部 violation。

容忍性为何可能更难 ​

普通 tester 的 yes 输入完全满足性质，常能依靠 perfect completeness 和局部 witness；tolerant tester 必须接受整个 ${\epsilon }_1$ 邻域，其中已经存在许多 witness。拒绝规则要判断违规的 总量 是否越过远阈值。

对某些性质，普通测试只需常数或 poly$(1/\epsilon )$ 查询，tolerant testing 却接近学习或距离估计的复杂度。不能从基础 tester 通过“把拒绝次数阈值调高”无条件得到正确算法；需要违规计数与全局距离之间的稳定关系。

错误侧别与适应性 ​

Tolerant 与 one-sided/two-sided 是不同轴。当 ${\epsilon }_1>0$ 时，close 但不满足性质的对象也必须高概率接受；一个发现真实局部 violation 就必拒绝的 perfect-completeness 规则通常不再适用。

查询仍可自适应或非自适应。上面的样本均值 tester 非自适应；某些距离估计算法会根据粗估结果把后续查询集中到可疑区域。容忍性本身不规定访问顺序。

边界 ​

距离必须与对象表示一致。对图性质，dense 与 bounded-degree 距离给同一图不同 close/far 身份；阈值不能脱离 oracle 单独搬用。

如果 ${\epsilon }_1={\epsilon }_2$，promise 没有间隔，采样噪声下通常不能以有限次查询统一分辨边界两侧；定义要求严格 ${\epsilon }_1<{\epsilon }_2$。

最后，接受 close 对象不等于输出修复后的成员，也不保证找到最近对象。Tolerant testing 仍只输出一个 gap decision bit；local reconstruction 是额外任务。

参考资料

• Michal Parnas, Dana Ron, and Ronitt Rubinfeld, “Tolerant Property Testing and Distance Approximation,” Journal of Computer and System Sciences 72(6), 2006, pp. 1012–1042.
• Oded Goldreich, Introduction to Property Testing, Cambridge University Press, 2017, Chapter 12.
• Irit Newman and Christian Sohler, “Every Property of Hyperfinite Graphs Is Testable,” SIAM Journal on Computing 42(3), 2013, tolerant-testing context.