1. 问题描述
感知机算法的提出最初被用来解决二分类问题，即给定 \(N\) 个样本，其中每个样本都是 \(p\) 维的向量。每一个样本属于 \(C_1\) 或 \(C_2\)。我们的任务是找到一个超平面来将所有样本进行准确分类并且具有较强的泛化能力。 ### 2. 问题数学描述 这里我们将这类问题抽象为数学描述。我们假设 \(x_1,x_2,\ldots,x_N\) 是 \(p\) 维向量。然后我们将 \(\vec{x}_1,\vec{x}_2,...,\vec{x}_N\) 定义为： 如果 \(x_i\in C_1\),则 \(\overrightarrow{x_i}=\begin{bmatrix}x_i\\1\end{bmatrix}\); 如果 \(x_i\in C_2\),则 \(\overrightarrow{x_i}=\begin{bmatrix}-x_i\\ -1\end{bmatrix}\) 此时所有向量变成了 \(p+1\) 维。这个问题也转变成了寻找一个 \(p+1\) 维向量 \(\omega\), 使得对于任何 \(i=1,2,\cdots,N\) 都有： \[\omega^T\overrightarrow{x_i}> 0\]
3. 算法流程
\[\begin{aligned} & \textbf{Input: }\overrightarrow{x_1},\overrightarrow{x_2},\ldots,\overrightarrow{x_N}\\ & \textbf{Output: }\omega \\ & _\textbf{1} \quad \omega= \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{bmatrix};\\ &_\textbf{2} \quad FLAG=1;\\ &_\textbf{3} \quad \textbf{while }FLAG \textbf{ do}\\ &_\textbf{4} \quad \qquad FLAG=0;\\ &_\textbf{5} \quad \qquad \textbf{for }i=1:N\;\textbf{do}\\ &_\textbf{6} \quad\qquad\qquad \textbf{if }\omega^T\overrightarrow{x_i}\le 0 \textbf{ then}\\ &_\textbf{7} \quad \qquad\qquad\qquad \omega=\omega+\overrightarrow{x_i};\\ &_\textbf{8} \quad \qquad\qquad\qquad FLAG=1;\\ &_\textbf{9} \quad \qquad\qquad \textbf{end}\\ &_\textbf{10} \quad \qquad \textbf{end}\\ &_\textbf{11} \quad \textbf{end}\\ &_\textbf{12} \quad \textbf{return }w;\\ \end{aligned} \]
4. 算法收敛性证明
定理1 对于所有的 \(N\) 个向量 \(\overrightarrow{x_1},\overrightarrow{x_2},\ldots,\overrightarrow{x_N}\)，如果存在一个向量 \(\omega_{opt}\) 使得 \(\omega_{opt}^T\overrightarrow{x_i}>0\) 对于所有的 \(i={1,2,\ldots,N}\) 都成立，则 3 中描述的算法一定能够找到一个 \(\omega\)，使得 \(\omega_{opt}^T\overrightarrow{x_i}>0\) 对于所有 \(i={1,2,\ldots,N}\) 都成立。且算法的收敛性不取决于 \(\omega\) 的初值选择。 证明 我们可以假设 \(\lVert \omega_{opt} \Vert=1\)。因为对于找到的超平面 \(\omega_{opt}\)，我们总可以乘以一个系数，使得\(\omega_{opt}\) 模长为1. 我们记\(\omega(k)\) 为\(\omega\) 的第 \(k\) 次迭代值。然后我们有： 1. 如果对于所有的 \(i={1,2,\ldots,N} \omega(k)^T\overrightarrow{x_i}>0\) 都成立，则算法直接成立 2. 否则，假设第 \(k\) 次时，有\(\omega(k)^T\overrightarrow{x_i}<0\)
然后我们根据算法更新参数 \[\omega(k+1)=\omega(k)+\overrightarrow{x_i}\] 然后我们有： \[\omega(k+1)-a\omega_{opt}=\omega(k)-a\omega_{opt}+\overrightarrow{x_i}\] 两边同时取模，则有： \[ \begin{aligned} &{\|\omega(k+1)-a\omega_{opt}\|}^2 \\ = &{\|\omega(k)-a\omega_{opt}+\overrightarrow{x_i}\|}^2 \\ = &{\|\omega(k)-a\omega_{opt}\|}^2+{\|\overrightarrow{x_i}\|}^2+2\omega(k)^T\overrightarrow{x_i}-2a\omega_{opt}^T\overrightarrow{x_i} \end{aligned} \] 这里 a 是一个正数，我们之后再具体讨论它的数值。因为 \(\omega(k)^T\overrightarrow{x_i}<0\)，因此我们有： \[ \begin{aligned} &{\|\omega(k+1)-a\omega_{opt}\|}^2 \\ \le &{\|\omega(k)-a\omega_{opt}\|}^2+{\|\overrightarrow{x_i}\|}^2-2a\omega_{opt}^T\overrightarrow{x_i} \end{aligned} \] 我们定义 \(\beta=\max_{i=1}^{N}\lVert\overrightarrow{x_i}\lVert\)，\(\gamma=\min_{i=1}^{N}(\omega_{opt}^T\overrightarrow{x_i})\) 易得 \(\beta,\gamma>0\)。此时当 \(a=\frac{\beta^2+1}{2\gamma}\) 并带入，很容易得到： \[ {\|\omega(k+1)-a\omega_{opt}\|}^2 \le {\|\omega(k)-a\omega_{opt}\|}^2 -1 \] 我们定义 \(D=\lVert\omega(0)-\omega_{opt}\lVert\)。基于上式我们可以得到，每迭代一次 \(\omega\) 与\(\omega_{opt}\)的距离减少1，因此至多迭代 \(D^2\) 次，\(\omega\) 就会收敛到\(\omega_{opt}\)。