证明感知机收敛定理：对于二分类问题，若数据集线性可分，则感知机学习算法一定能找到能将数据集分开的权重

感知机学习算法：if \( y_i \neq \textrm{sign}(w_n^T \cdot x_i) \), update \( w_n \) with \( w_{n+1} \leftarrow w_n + y_i x_i \)

数据集线性可分 \( \Leftrightarrow \exists w_f \)将数据集分开 \( \Leftrightarrow y_i(w_f^T \cdot x_i) > 0 \)

令 \( \rho = \textrm{min} y_i \frac{w_f^T}{| w_f |} x_i, R^2 = \textrm{max} {| x_n |}^2\)

设\( w_0 = 0 \)，经T次迭代之后，权重变为\( w_T = \sum_{i=1}^{T}y_i x_i \)

\( \frac{w_f^T w_T}{| w_f |} = \frac{w_f^T \sum_{i=1}^{T}y_i x_i}{| w_f |} = \frac{\sum_{i=1}^{T}w_f^T y_i x_i}{| w_f |} \geq T \rho \)

\( {|w_T|}^2 = {| w_{T-1} + y_T \cdot x_T |}^2 = {| w_{T-1} |}^2 + {| x_T |}^2 + 2 y_T w_{T-1}^T x_T \leq {| w_{T-1} |}^2 + {| x_T |}^2 \leq … \leq \sum_{i=1}^{T}{| x_i |}^2 \leq TR^2\)

故 \( 1 \geq \frac{w_f^T w_T}{| w_f | | w_T |} \geq \frac{T \rho}{\sqrt{T} |R|} \)

故T的上界为\( \frac{ {|R|}^2 }{ {\rho}^2 } \)