线性检测高级计算机算法与设计

文章目录

linearity test前的基础知识
线性检测
定理

证明

全息规约看线性检测将期望写成张量网络
线性子空间指示函数的傅里叶形式
Ryser公式
全息归约的解释permanent

linearity test前的基础知识

f : { 0 , 1 } n → { 0 , 1 } ? { 1 , ? 1 } f:\{0,1\}^n\rightarrow \{0,1\}\leftrightarrow\{1,-1\} f:{0,1}n→{0,1}?{1,?1}
χ s ( x 1 , . . . , x n ) = ∑ i ∈ s x i ( m o d 2 ) = ( ? 1 ) ∑ i ∈ s x i ∏ i ∈ s ( ? 1 ) x i ∏ x j ? s ( 1 ) x j \chi_s(x_1,...,x_n)=\sum_{i\in s}x_i(mod 2)=(-1)^{\sum_{i\in s}x_i}\\ \prod_{i \in s}(-1)^{x_i}\prod_{x_j\notin s}(1)^{x_j} χs?(x1?,...,xn?)=i∈s∑?xi?(mod2)=(?1)∑i∈s?xi?i∈s∏?(?1)xi?xj?∈/?s∏?(1)xj?
- 上面的都是乘积，只有一个输入，所以对应一个张量网络，这就证明了所有这些χ s \chi_s χs?构成的矩阵是 H ? n H^{\otimes n} H?n
  
  文章图片
所有这些χ s \chi_s χs?构成的矩阵是 H ? n H^{\otimes n} H?n
- 是 2 n × 2 n 2^n \times 2^n 2n×2n的，可以看成每一列都是一个 χ s \chi_s χs?,列标和子集 s s s一一对应。
- H = ( χ { ? } , χ 1 ) H=\left(\chi_{\{\emptyset}\},\chi_{1}\right) H=(χ{??},χ1?), H ? n H^{\otimes n} H?n要回球哦！
傅里叶： f = ∑ s f ^ ( s ) χ s f=\sum_{s}\hat f(s)\chi_s f=s∑?f^?(s)χs?
- 等价于将 f f f的 2 n 2^n 2n个值列出来的矩阵形式
  
  文章图片
一个例子
- f ^ = ( 1 0 0 0 0 0 0 1 ) 2 n = [ 1 0 0 1 ] n + 1 \hat f=\left(\begin{array}{c} 1\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ 1\\ \end{array}\right)_{2^n}=\left[\begin{array}{c} 1\\ 0\\ 0\\ 1\\ \end{array}\right]_{n+1} f^?=?????????????10000001??????????????2n?=?????1001??????n+1?
  
  文章图片
- 不用矩阵乘法就是把 χ ? + χ { 1 , 2 , 3 } = ( 1 1 1 1 1 1 1 1 ) + ( 1 ? 1 ? 1 1 ? 1 1 1 ? 1 ) = 2 ( 1 0 0 1 0 1 1 0 ) = 2 [ 1 0 1 0 ] \chi_{\emptyset}+\chi_{\{1,2,3\}}=\\ \left(\begin{array}{c} 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ \end{array}\right)+\left(\begin{array}{c} 1\\ -1\\ -1\\ 1\\ -1\\ 1\\ 1\\ -1\\ \end{array}\right)=2\left(\begin{array}{c} 1\\ 0\\ 0\\ 1\\ 0\\ 1\\ 1\\ 0\\ \end{array}\right)=2\left[\begin{array}{c} 1\\ 0\\ 1\\ 0\\ \end{array}\right] χ??+χ{1,2,3}?=?????????????11111111??????????????+?????????????1?1?11?111?1??????????????=2?????????????10010110??????????????=2?????1010??????
- H ? 3 f ^ = H ? 3 [ 1 0 ] ? 3 + H ? 3 [ 0 1 ] ? 3 = [ 1 1 ] ? 3 + [ 1 ? 1 ] ? 3 = ( 1 1 1 1 1 1 1 1 ) + ( 1 ? 1 ? 1 1 ? 1 1 1 ? 1 ) = 2 ( 1 0 0 1 0 1 1 0 ) = 2 [ 1 0 1 0 ] H^{\otimes3}\hat f=H^{\otimes3}\left[\begin{array}{c} 1\\ 0\\ \end{array}\right]^{\otimes 3}+H^{\otimes3}\left[\begin{array}{c} 0\\ 1\\ \end{array}\right]^{\otimes 3}=\\ \left[\begin{array}{c} 1\\ 1\\ \end{array}\right]^{\otimes 3}+\left[\begin{array}{c} 1\\ -1\\ \end{array}\right]^{\otimes 3}=\\ \left(\begin{array}{c} 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ \end{array}\right)+\left(\begin{array}{c} 1\\ -1\\ -1\\ 1\\ -1\\ 1\\ 1\\ -1\\ \end{array}\right)=2\left(\begin{array}{c} 1\\ 0\\ 0\\ 1\\ 0\\ 1\\ 1\\ 0\\ \end{array}\right)=2\left[\begin{array}{c} 1\\ 0\\ 1\\ 0\\ \end{array}\right] H?3f^?=H?3[10?]?3+H?3[01?]?3=[11?]?3+[1?1?]?3=?????????????11111111??????????????+?????????????1?1?11?111?1??????????????=2?????????????10010110??????????????=2?????1010??????
- 总结：2 ⊕ 3 = H ? 3 " = 3 " \oplus_3=H^{\otimes 3} "=_3" ⊕3?=H?3"=3?"，
- H ? 3 ⊕ 3 = 4 " = 3 " H^{\otimes 3}\oplus_3=4 "=_3" H?3⊕3?=4"=3?"
一点记号
- 下面的内积除以 2 n 2^n 2n，课件上没有除哦！
  
  文章图片
- < f , g > 的内积 = 1 2 n ∑ x f ( x ) g ( x ) = E x f ( x ) g ( x ) 若 f , g ∈ { ± 1 } ，则上面 = P r ( f ( x ) = g ( x ) ) ? P r ( f ( x ) =? g ( x ) ) 1 ? 2 P r ( f ( x ) =? g ( x ) ) = 1 ? 2 d i s t ( f , g ) 的内积=\frac{1}{2^n}\sum_xf(x)g(x)=E_xf(x)g(x) \\ 若f,g\in \{ \pm1\}，\\ 则上面=Pr(f(x)=g(x))-Pr(f(x)\not=g(x))\\ 1-2Pr(f(x)\not=g(x))=\\ 1-2dist(f,g) 的内积=2n1?∑x?f(x)g(x)=Ex?f(x)g(x)若f,g∈{±1}，则上面=Pr(f(x)=g(x))?Pr(f(x)?=g(x))1?2Pr(f(x)?=g(x))=1?2dist(f,g)
- 卷积: ( f ? g ) ( x ) = E y f ( y ) g ( x ? y ) (f*g)(x)=E_yf(y)g(x-y) (f?g)(x)=Ey?f(y)g(x?y)
- 卷积的傅里叶系数等于各自傅里叶系数乘积： ( f ? g ) ^ ( s ) = f ^ ( s ) g ^ ( s ) \\\widehat {(f*g)}(s)=\hat f(s) \hat g(s) (f?g) ?(s)=f^?(s)g^?(s)

线性检测

算法：询问 f f f:
- 随机选取 x , y ∈ { 0 , 1 } n x,y\in\{0,1\}^n x,y∈{0,1}n
- queryf ( x ) , f ( y ) , f ( x + y ) f(x),f(y),f(x+y) f(x),f(y),f(x+y)
- 如映射到了 { 0 , 1 } \{0,1\} {0,1}，要看 , f ( x + y ) = f ( x ) + f ( y ) 吗 ,f(x+y) =f(x)+f(y)吗 ,f(x+y)=f(x)+f(y)吗
- 如映射到了 { 1 , ? 1 } \{1,-1\} {1,?1}，accept iff ( x ) f ( y ) = f ( x + y ) f(x)f(y)=f(x+y) f(x)f(y)=f(x+y)?
  - 等价于 accept iff ( x ) f ( y ) f ( x + y ) = 1 f(x)f(y)f(x+y)=1 f(x)f(y)f(x+y)=1?
如果f是线性的，算法以概率1接受
若 f f f不线性，下面定理说了接受概率和f与线性函数距离之间的关系。

定理 【线性检测】如果算法以 1 ? ? 1-\epsilon 1??接受，
那么 f 就是 ? ? c l o s e f就是\epsilon-close f就是??close to be linear
（即 ? 线性函数 g ， d i s t ( f , g ) < ? \exist 线性函数g，dist(f,g)<\epsilon ?线性函数g，dist(f,g) 证明

1 ? ? = P r ( a c c e p t ) = E x , y [ 1 2 + 1 2 f ( x ) f ( y ) f ( x + y ) ] 1-\epsilon=Pr(accept)=E_{x,y}[\frac 12+\frac 12f(x)f(y)f(x+y)] 1??=Pr(accept)=Ex,y?[21?+21?f(x)f(y)f(x+y)]
没问题
1 2 + 1 2 E x [ f ( x ) E y [ f ( y ) f ( x + y ) ] ] \frac 12+\frac 12E_{x}\left[f(x)E_y[f(y)f(x+y)]\right] 21?+21?Ex?[f(x)Ey?[f(y)f(x+y)]]
没问题
1 2 + 1 2 E x [ f ( x ) f ? f ( x ) ] \frac 12+\frac 12E_{x}\left[f(x)\quad{f*f}(x)\right] 21?+21?Ex?[f(x)f?f(x)]
- 上一部其实是内积的定义哦！，内积可以换成傅里叶的内积
- 这里的 H H H显然正规化了。
1 2 + 1 2 E x [ f ^ ( x ) f ? f ^ ( x ) ] \frac 12+\frac 12E_{x}\left[\widehat f(x)\quad \widehat{f*f}(x)\right] 21?+21?Ex?[f ?(x)f?f ?(x)]
s s s实际上是每个子集哈哈哈哈哈，你懂啊。
1 2 + 1 2 E s [ f ^ ( s ) f ? f ^ ( s ) ] \frac 12+\frac 12E_{s}\left[\widehat f(s)\quad \widehat{f*f}(s)\right] 21?+21?Es?[f ?(s)f?f ?(s)]
1 2 + 1 2 E s [ f ^ ( s ) 3 ] \frac 12+\frac 12E_{s}[\widehat f(s)^3] 21?+21?Es?[f ?(s)3]
所以有： 1 ? 2 ? = ∑ s ( f ^ ( s ) ) 3 ≤ 1-2\epsilon=\sum_s(\hat f(s))^3\le 1?2?=∑s?(f^?(s))3≤
max ? s f ^ ( s ) ∑ s ( f ^ ( s ) ) 2 = \max_s\hat f(s) \sum_s(\hat f(s))^2= maxs?f^?(s)∑s?(f^?(s))2=
为什么 E s ∑ s ( f ^ ( s ) ) 2 = 1 呢？ E_s\sum_s(\hat f(s))^2=1呢？ Es?∑s?(f^?(s))2=1呢？，
- 因为你先这样认为把。
max ? s { f ^ ( s ) } \max_s\{\hat f(s)\} maxs?{f^?(s)}
假设 f ^ ( s 0 ) \hat f(s_0) f^?(s0?)系数最大
所以 1 ? 2 ? ≤ f ^ ( s 0 ) = < f , χ s 0 > = 1-2\epsilon \le \hat f(s_0)== 1?2?≤f^?(s0?)==
1 ? 2 d i s t ( f , χ s 0 ) 1-2dist(f,\chi_{s_0}) 1?2dist(f,χs0??)
证毕！我们要找的 g g g就是 χ s 0 \chi_{s_0} χs0??

全息规约看线性检测将期望写成张量网络

E z = x y f ( x ) f ( y ) f ( z ) E_{z=xy}f(x)f(y)f(z) Ez=xy?f(x)f(y)f(z)
- = E x , y f ( x ) f ( y ) f ( z ) [ z = x + y ] =E_{x,y}f(x)f(y)f(z)[z=x+y] =Ex,y?f(x)f(y)f(z)[z=x+y]
- 实际是 = E x , y f ( x ) f ( y ) f ( z ) ( ∏ i = 1 n [ z i = x i + y i ] ) = =E_{x,y}f(x)f(y)f(z)(\prod_{i=1}^{n}[z_i=x_i+y_i])= =Ex,y?f(x)f(y)f(z)(∏i=1n?[zi?=xi?+yi?])=
- = E x , y f ( x ) f ( y ) f ( z ) ( ∏ i = 1 n ⊕ 3 ( x i , y i , z i ) ) = =E_{x,y}f(x)f(y)f(z)(\prod_{i=1}^{n}\oplus_3(x_i,y_i,z_i))= =Ex,y?f(x)f(y)f(z)(∏i=1n?⊕3?(xi?,yi?,zi?))=
  
  文章图片
  
  文章图片
  
  文章图片
  
  文章图片
线性检测的全息归约看法

文章图片

线性子空间指示函数的傅里叶形式

文章图片

下面这个是上面线性方程的张量网络，不过为啥要红色的线呢？？

文章图片

上面的图示个函数，下面的图是上面图的傅里叶形式，就是上图的每一个输入，都有下图与之对应

文章图片
下面的图
- 注意 z z z和 w w w的引入
- 他对应一个函数 { y 1 = z y 2 = z + w y 3 = z + w \left\{ \begin{aligned} y_1=z\\ y_2=z+w\\ y_3=z+w\\ \end{aligned} \right. ??????y1?=zy2?=z+wy3?=z+w?，
  - 相当于= z [ 1 , 1 , 1 ] T + w [ 0 , 1 , 1 ] T z[1,1,1]^T+w[0,1,1]^T z[1,1,1]T+w[0,1,1]T
  - 原来方程只接受和 [ 1 , 1 , 1 ] T 和 [ 0 , 1 , 1 ] T [1,1,1]^T和[0,1,1]^T [1,1,1]T和[0,1,1]T都垂直的量
  - 而现在方程只产生 [ 1 , 1 , 1 ] T 和 [ 0 , 1 , 1 ] T [1,1,1]^T和[0,1,1]^T [1,1,1]T和[0,1,1]T的组合

文章图片

Ryser公式全息归约的解释permanent

A A A两表示： n n n个点有向图， 2 n 2n 2n个点偶图
V = { 1 , 2 , . . . , n } V=\{1,2,...,n\} V={1,2,...,n},U={1’,2’,…,n’} , , ,无向偶图 H ( V , U , E , W ) H(V,U,E,W) H(V,U,E,W)
- 边 j k ′ 的权重 W ( j , k ) = A j , k ′ jk'的权重W(j,k)=A_{j,k'} jk′的权重W(j,k)=Aj,k′?
Permanent(A)是H的所有完美匹配权重之和
U , V 都用函数 [ 0 , 1 , 0 , . . . , 0 ] U,V都用函数[0,1,0,...,0] U,V都用函数[0,1,0,...,0]
- 这个张量网络的值就是Permanent(A)
- 把 V 中点换成 [ 0 , 1 , 1 , . . . , 1 ] V中点换成[0,1,1,...,1] V中点换成[0,1,1,...,1]，值不变
  - 这是因为如果V中的点娶了多于1个老婆，必然存在V中的点没法娶到老婆，所以整个网络的点的乘积为0.
[ 0 , 1 , . . . , 1 ] = ( 1 , 1 ) ? n ? ( 1 , 0 ) ? n [0,1,...,1]=(1,1)^{\otimes n}-(1,0)^{\otimes n} [0,1,...,1]=(1,1)?n?(1,0)?n