大数据机器学习算法与计算机视觉应用04：多项式

The Algorithm Magic of Polynomial

• Polynomials
• The Root of Polynomial
• A Delete Channel
• Polynomials for Finding Maximum Matchings

Polynomials 多项式

一个 $d$ 次多项式可以用一个 $d+1$ 元组 $c_i$ 表达。在这种情况下，两个多项式相加的时间复杂度是 $O(d)$ ，而两个多项式相乘的实践复杂度是 $O(d\log d)$ 。

快速地估计一个多项式的值的方法：对应给定值b，循环执行将当前式子乘b,加下一项。这个方法叫做霍纳规则。流程如下：
$$c_d{c}_d\times b+c_{d-1}(c_d\times b+c_{d-1})\times b+c_{d-2}$$
该算法的时间复杂度是 $O(d)$。

多项式的根

对于一个多项式 $P(x)$，令 $P(x)=0$ 的值 $x^{\prime }$ 被称作多项式的根。

根据代数基本定理，一个d次多项式一定有d个根。

Unique Reconstruction Theorem 唯一重构定理

唯一重构定理告诉我们，给定d个点 $(x_1,y_1),(x_2,y_2)\ddots ,(x_d,y_d)$, 总有一个多项式 $P(x)$ 使得这些点都在多项式上。

事实上，唯一重构定理告诉我们如何构造这样一个多项式满足条件。
首先我们构造这样一组多项式 $R_i(x)$ 满足：
$$R_i(x_i)=1R_i(x_j)=0,j\ne i$$
结果如下：
$$\frac{{\Pi }_{j\ne i}(x-x_j)}{{\Pi }_{j\ne i}(x_i-x_j)}$$
那么
$$P(x)=y_0{R}_0(x)+y_1{R}_1(x)+\cdots +y_d{R}_d(x)$$

举个例子：有三个点 $(5,1),(6,2),(7,9)$，现在找出经过这三个点的多项式。
$$R_1(x)=\frac{(x-6)(x-7)}{(5-6)(5-7)}=\frac{1}{2}(x^2-13x+42)R_2(x)=\frac{(x-5)(x-7)}{(6-5)(6-7)}=-\frac{1}{2}(x^2-12x+35)R_3(x)=\frac{(x-5)(x-6)}{(7-6)(7-5)}=\frac{1}{2}(x^2-11x+30)P(x)=R_1(x)+2R_2(X)+9R_3(x)=4x^2-50x+$$

A Deletion Channel 丢失频道

下面是另一个问题，假设在上面构造多项式的情景中，Alice要向Bob传d+1个数，但是在传输的过程中总会有k个数丢失，那么怎么才能保证Bob一定收的到这d+1个数呢？

一种很笨的方法是，将每个数据发送k+1次就可以了。但是这需要发送 $d\times (k+1)$ 个数据，有没有更好的方法呢？

一种好方法是构造一个多项式 $P(x)=\Sigma c_i{x}_i$，然后发送 $P(0),P(1),\ddots ,P(d+k)$，这样Bob至少可以收到d+1个多项式的值，根据唯一重构定理，Bob可以计算出这个多项式从而得出所有的c。
这种做法的时间复杂度是 $O(d+k+1)$，比上面的做法少传输很多数据。（注意，不用担心乱序的问题，因为是一个一个传的,而如果出错会传乱码而不是什么也不做）。

General Error Correction 误码纠错

假设现在不是传输丢失，而是传输一个错误的数字，那么在同样的背景下，需要进行怎样的传输呢？

很明显，答案是需要传输 $d+2k+1$个数字，其中$d+k+1$是正确的多项式的值。因为$k+1>k$，所以我们从理论上确认了Bob可以通过这种方式找到正确的多项式。

那么实际上应该怎么找到那个正确的多项式呢？

假设Bob收到的数据是 $r_0,r_1,\ddots ,r_{d+2k}$，Z是其中错误信息的集合，那么我们声明一个错误项多项式
$$E(x)={\Pi }_{i\in Z}(x-i)$$
那么对于Bob收到的所有项都满足以下等式，因为要么$E(x)=0$，要么 $P(x)=r_x$
$$P(x)\cdot E(x)=r_x\cdot E(x)$$

Berlekamp-Welch Algorithm BW算法

BW算法是一种用于误码纠错的算法，其运行规律基于上文所述，我们假设
$$E(x)=x^k+e_{k-1}{x}^{k-1}+\cdots +e_0(ifdegree(E(x))isk)P(x)\cdot E(x)=f_{d+k}{x}^{d+k}+f_{d+k-1}{x}^{d+k-1}+\cdots +f_0$$
这种情况下，我们分别将 $x=0,1,\cdots ,d+2k$带入方程
$$P(x)\cdot E(x)=r_x\cdot E(x)$$
左边是一堆参数f相加，右边是一堆e相加，f和e未知数的总和是d+2k+1个，而带入d+2k+1个x的值对应d+2k+1个方程，而且方程必定有解，因此就可以解出所有的e和f。

已知 $P(x)\cdot E(x)$ 和 $E(x)$ ，相除就可以求出 $P(x)$。

Polynomials for Finding Maximum Matching 多项式在最大匹配中的应用

Schwarz-Zippel Lemma Schwarz-Zippel 引理

这个引理的内容是：假设$P$是一个非零$m$元$d$次多项式，假设$S$是有限域$F$的一个子集。如果从$S$中随机抽取$m$个数$x_1,x_2,\cdots ,x_m$，那么
$$Pr[P(x_1,\cdots ,x_m)=0]\le \frac{d}{|S|}$$
健全性检查：当$m=1$时，因为d次多项式最多有$d$个根，因此概率很明显就是$\frac{d}{|S|}$。

这个引理可以用来解决下文提到的图的匹配问题。

Tutte Matrix

每个顶点数$v$的简单无向图都对应一个Tutte Matrix $M(G)$，简单来说如图所示：

Tutte Determinant Theorem Tutte行列式定理

一个图有完美匹配当且仅当$M(G)$的行列式不是零多项式。
（注：匹配指的找到图中一组边集，其中任意两条边都没有公共点。如果这组边集包括了图中所有的顶点，那么就说该匹配是完美匹配。）

那么剩下的就是选取$F$的大小了，$F$的基数越大，这张图有完美匹配的概率就越高。

Finding a Perfect Matching

上面我们知道了有完美匹配的概率，但是我们如何找到一个完美匹配呢？下面是一个方法:

对于每个边，将图中的该边删去，判断剩下的图中是否还存在完美匹配。如果没有完美匹配，那么将该边加回来；否则丢弃该边。
最后一定剩下$\frac{V}{2}$条边，这些边就是一个完美匹配。