广义感知器的收敛性¶
(定理 3.2). 广义感知器在 \(\frac{R^2}{\gamma^2}\)步内必收敛.
邱锡鹏教授 《神经网络与深度学习》 (NNDL)
证明:
\(\omega_0,~k,~t\) 均为0, 若 $ \hat{y}^{(n)} \neq y^{(n)} $ , 那么 $ \omega_{k+1} = \omega_{k} + \left[ \phi(x^{(n)} , y^{(n)} ) - \phi ( x^{(n)} , y) \right] . $
- 上界:
\[
\begin{aligned}
\| \omega_k \|^2 =& \| \omega_{k-1} + \phi ( x^{(n)}, y^{(n)} ) - \phi (x^{(n)} , y) \|^2 \\
=& \| \omega_{k-1} \|^2 + \| \phi ( x^{(n)}, y^{(n)} ) - \phi (x^{(n)} , y) \|^2 \\ &+ 2 \omega^\top_{k-1} \left[ \phi ( x^{(n)}, y^{(n)} ) - \phi (x^{(n)} , y) \right] \\
\leq & \| \omega_{k-1} \|^2 + R^2 \leq \| \omega_{k-2} \|^2 + 2 R^2 \\ \leq & \dots \leq \| \omega_0 \|^2 + K R^2 = 0+ K R^2 = K R^2
\end{aligned}
\]
- 下界: 我们使用一个 \(\omega^*\) 作为单位方向向量, \(\| \omega^* \| = 1\) , 所以
\[
\begin{aligned}
\| \omega_k \|^2 =& \| \omega^* \|^2 \cdot \| \omega_k \|^2 \geq \| \omega^{*\top} \omega_{k} \|^2 \\
=& \left\| \omega^{*\top} \cdot \sum^{K}_{k=1} \left[ \phi(x^{(n)}, y^{(n)}) - \phi(x^{(n)},y) \right] \right\|^2 \\
=& \left\| \sum^{K}_{k=1} \omega^{*\top} \left[ \phi(x^{(n)}, y^{(n)}) - \phi(x^{(n)},y) \right] \right\|^2 .
\end{aligned}
\]
由于 $$ \omega^{*\top} \left[ \phi(x^{(n)}, y^{(n)}) - \phi(x^{(n)},y) \right] \geq \gamma , $$ 所以 $$ | \omega_k |^2 \geq ( k \gamma )^2 . $$
综上, $$ K R^2 \geq | \omega_k |^2 \geq (k \gamma)^2 \implies K^2 \gamma^2 \leq | \omega_k |^2 \leq K R^2 , $$ 即 $$ K^2 \gamma^2 \leq K R^2 \implies \boxed{ K \leq \frac{R^2}{\gamma^2} } , $$ 即 Perceptron 在 \(\frac{R^2}{\gamma^2}\)步内必收敛.