性质检验（Property Testing）然而，在计算机算法理论中非常重要的领域，性质检验本身就是一个非常普遍的概念。确切地说，性质检验包括图形性质（二分性、连通性、团体性质、切割性质）、离散函数性质（单调性、线性、多项性）等，涉及的领域非常多，几乎不可能涵盖一切。Property Testing核心是通过随机检查给出检验这些性质的高速算法。原因是在大数据时代，即使采用多项时间（甚至线性时间）算法在大规模图纸上进行图纸性质检验，也可能是杯水车薪。因此，有必要挖掘次线性算法（sublinear）解决这些问题的时间算法(如对数复杂度算法)。

一个想法是使用随机算法。随机算法通常可以有更高的概率(如 2 / 3 2/3 2/3）正确判断输入问题（如图所示），虽然概率不是很高，但我们可以多次测试，如果算法总是输出图具有二分性，那么结论的可信度很高（当然，只要一个输入没有二分性，一般可以证明图没有二分性，最多naive一种检验方法是取图的一部分，看看是否有二分性。如果只是没有二分性，当然整个图没有二分性。当然，事实上，随机算法会比这更好naive方法复杂，结论依赖于严格的数学证明)。

目前作者还没有看到更好的关于Property Testing本文主要参考教材Introduction to Property Testing与另外一篇Dana Ron英文44页slide（这个slide写得很好，整合了几十篇文章paper综述，这个slide我从前辈那里得到的，不知道在哪里可以下载，但文章的内容主要是参考文献的结论。如果你想了解更多，你可以直接查看文章末尾的参考文献）为课堂报告提供文案从入门到深入分析Property Testing的知识。

本文第一章来源于第一本教材，其他部分都是这样的slide本文末尾的翻译和笔记、参考文献可能不那么有趣，但也许不有趣的事情更有意义。

• 本节介绍性质检验，可参考Introduction to Property Testing第一章的内容，不再赘述。

• 一些常用的标记如下：

  • [ N ] = { 1 , 2 , . . . , N } [N]=\{1,2,...,N\} [N]={ 1,2,...,N}；
  • O ~ ( ⋅ ) = O ( log ⁡ ⋅ ) \tilde O(\cdot)=O(\log\cdot) O~(⋅)=O(log⋅)；

Introduction to Property Testing第一章的内容翻译如下：

1. 什么是属性检验（property testing，下简称为PT）：

   • 关于大数据的全局属性的分析: 如确定数据整体是否具有某种全局属性(global property)，或对数据结构中的全局参数进行估计；

   • 大数据通常可以由图（graph）的形式建模，因为数据对象之间往往都会具有一定联系，挖掘由大数据建模得到的图中的自然属性（natural properties）是PT的研究内容之一；

     • 注意图中的节点也可以是抽象的函数（function）：如对象通过函数建模，则函数之间的距离可以由函数不同的域的分数来度量， 如果函数与具有该属性的任何函数的距离超过给定的近似参数（proximity parameter），则认为该函数不具有该属性；对这些函数性质的测试也属于PT的研究范畴，如函数是否为低阶的多项式（low degree polynomial），是否单调（monotone）等；

       原文：

       … and distance between functions is measured as the fraction of the domain on which the functions differ.

     • 一些其他的PT研究范畴包括判断图是否二分（bipartite），是否不存在三角形（triangle-free），针对虚拟图片（visual images）或几何对象（geometric objects）的聚类性质（well-clustered）或凸性进行测试；

   • PT旨在挖掘超快算法，而避免获得对象的完整显式描述。

     原文：

     We refer to the fact that property testing seeks super-fast algorithms that refrain from obtaining the full explicit description of the object.

2. 一些下文即将用到的符号表示说明：

   • ∀ n ∈ N \forall n\in \mathbb{N} ∀n∈N，定义 [ n ] = d e f { 1 , 2 , . . . , n } [n]\overset{\rm def}{=}\{1,2,...,n\} [n]=def{ 1,2,...,n}；
   • 若 x x x为零一字符串，即 x ∈ { 0 , 1 } ∗ x\in\{0,1\}^* x∈{ 0,1}∗，则 ∣ x ∣ |x| ∣x∣表示 x x x的长度， x i x_i xi​表示 x x x的第 i i i位的字节；
   • 设 w t ( x ) = ∣ { i ∈ [ ∣ x ∣ ] : x i = 1 } ∣ = ∑ i = 1 ∣ x ∣ x i {\rm wt}(x)=|\{i\in[|x|]:x_i=1\}|=\sum_{i=1}^{|x|}x_i wt(x)=∣{ i∈[∣x∣]:xi​=1}∣=∑i=1∣x∣​xi​表示字符串 x x x的汉明权重（Hamming weight）；

1. 什么是近似搜索问题（approximate search problems）？

   • 搜索问题（search problems）：即给定 x x x搜索 y y y，使得 ( x , y ) ∈ R (x,y)\in R (x,y)∈R，如 R ⊆ { 0 , 1 } ∗ × { 0 , 1 } ∗ R\subseteq\{0,1\}^*×\{0,1\}^* R⊆{ 0,1}∗×{ 0,1}∗，定义 R ( x ) = d e f { y : ( x , y ) ∈ R } R(x)\overset{\rm def}{=}\{y:(x,y)\in R\} R(x)=def{ y:(x,y)∈R}表示搜索空间；
   • 优化问题（optimization problems）：找出最优解 y ∗ ∈ R ( x ) y^*\in R(x) y∗∈R(x)，使得关于 y y y的目标函数最大化（或最小化），如 ν ( y ∗ ) = max ⁡ y ∈ R ( x ) { ν ( y ) } \nu(y^*)=\max_{y\in R(x)}\{\nu(y)\} ν(y∗)=maxy∈R(x)​{ ν(y)}；
   • 近似搜索问题：指找到一个近似最优解 y ^ \hat y y^​，使得 ν ( y ^ ) \nu(\hat y) ν(y^​)与 ν ( y ∗ ) \nu(y^*) ν(y∗)的差距很小，如达到最优解目标函数值的 1 2 \frac{1}{2} 21​， 3 4 \frac{3}{4} 43​等；

2. 什么是近似决策问题？

   • 很多时候判断某个输入 x x x是否属于集合 S S S是很困难的，原因是集合 S S S的边界往往很模糊，当 x x x落在集合 S S S的 边界上时就会很难做出判断，所以会考虑将问题放宽到判断 x ∈ S x\in S x∈S或== x x x距离 S S S非常远==。

   • 关于非常远的定义：可以采用汉明距离（Hamming distance），并引入一个近似参数（proximity parameter） ϵ \epsilon ϵ；令： δ ( x , z ) = { ∣ { i ∈ [ ∣ x ∣ ] : x i ≠ z i } ∣ ∣ x ∣ i f   ∣ x ∣ = ∣ z ∣ ∞ o t h e r w i s e \delta(x,z)=\left\{\begin{aligned}\frac{|\{i\in[|x|]:x_i\neq z_i\}|}{|x|}\quad{\rm if}\space|x|=|z|\\\infty\quad{\rm otherwise}\end{aligned}\right. δ(x,z)=⎩⎪⎨⎪⎧​∣x∣∣{ i∈[∣x∣]:xi​​=zi​}∣​if ∣x∣=∣z∣∞otherwise​ 则 x x x与集合 S S S之间的距离可以定义为（即从 S S S中找到一个距离 x x x最近的点）： δ S ( x ) = d e f min ⁡ z ∈ S { δ ( x , z ) } \delta_S(x)\overset{\rm def}{=}\min_{z\in S}\{\delta(x,z)\} δS​(x)=defz∈Smin​{ δ(x,z)} 于是我们只需要观察是否 δ S ( x ) > ϵ \delta_S(x)>\epsilon δS​(x)>ϵ，当 x x x满足 0 < δ S ( x ) ≤ ϵ 0<\delta_S(x)\le\epsilon 0<δS​(x)≤ϵ就直接被忽略掉了；

3. 为什么我们要将标准的决策问题转换为近似决策问题？

   • 因为标准的决策问题是NP-Hard，需要转为多项式时间；

   • 当然也用于处理线性时间的问题，目的是得到次线性的复杂度时间，因为很多时候算法的输入会极为庞大；

   • 命题1.1：P. 35

     令 M A J = { x : ∑ i = 1 ∣ x ∣ x i > ∣ x ∣ 2 } {\rm MAJ}=\{x:\sum_{i=1}^{|x|}x_i>\frac{|x|}{2}\} MAJ={ x:∑i=1∣x∣​xi​>2∣x∣​}，存在时间复杂度为 O ( 1 ϵ 2 ) O(\frac{1}{\epsilon^2}) O(ϵ21​)的随机算法能够确定 x x x是否在 M A J \rm MAJ MAJ中或距离 M A J \rm MAJ MAJ有 ϵ \epsilon ϵ远；

     注意：在随机算法的情境下，所谓算法能够确定，指算法有至少 2 3 \frac{2}{3}