《统计学习方法》学习笔记之第二章:感知机

第一节模型介绍和学习策略

模型介绍

学习策略

第二节梯度下降法

概念

算法

梯度下降法：例子

原理

第三节学习算法之原始形式

学习问题

原始形式

例题分析

第三节学习算法之对偶形式

对偶形式

例题分析

第四节原始形式算法的收敛性

第一节模型介绍和学习策略

模型介绍

输入空间： $\chi \subseteq R^n$ ; 输入： $x=(x^{(1)},x^{(2)},...,x^{(n)})^T\epsilon \chi$
输出空间： $Y = \{+1,-1\}$ ; 输出： $y\epsilon Y$
感知机：

$f(x)=sign(w\cdot x+b)=\begin{Bmatrix} +1,\qquad w\cdot x+b\geq 0\\ -1,\qquad w\cdot x+b < 0\end{}$

其中， $w=(w^{(1)},w^{(2)},...,w^{(n)})^T\epsilon R^n$ 称为权值(Weight), $b\epsilon R$ 称为偏置(Bias), $w\cdot x$ 表示内积

$w\cdot x = w^{(1)}x^{(1)}+w^{(2)}x^{(2)}+...+w^{(n)}x^{(n)}$

假设空间： $F=\{f|f(x)=w\cdot x+b\}$

线性方程：

$w\cdot x+b = 0$

特征空间 $R^n$ 中的一个超平面S(超平面比特征空间向量少一维)

法向量：w; 截距：b

学习策略

前提条件：数据集需要线性可分

给定数据集

$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$

若存在某个超平面S

$w\cdot x + b=0$

能够将数据集的正负实例点完全正确的划分到超平面两侧，即

$\left\{ \begin{aligned} y_i &=&+1,\qquad w\cdot x+b>0\\ y_i &= & -1, \qquad w\cdot x_i+b<0 \end{aligned} \right.$

那么，称T为线性可分数据集；否则，称T为线性不可分。

$\forall x_0\epsilon R^n$ 到S的距离：

$\frac{1}{||w||}|w\cdot x_0+b|$

- 若 $x_0$ 是正确分类点，则

$\frac{1}{||w||}|w\cdot x_0+b|=\left\{ \begin{aligned} \frac{w\cdot x_0+b}{||w||}, \qquad y_0=+1\\ -\frac{w\cdot x_0+b}{||w||},\qquad y_0=-1 \end{aligned} \right.$

- 若 $x_0$ 是错误分类点，则

$\frac{1}{||w||}|w\cdot x_0+b|=\left\{ \begin{aligned} -\frac{w\cdot x_0+b}{||w||}, \qquad y_0=+1\\ \frac{w\cdot x_0+b}{||w||},\qquad y_0=-1 \end{aligned} \right.$

误分类点 $x_i$ 到S的距离：

$-\frac{1}{||w||}y_i(w\cdot x_i+b)$

所有误分类点到S的距离：

$-\frac{1}{||w||}\sum\limits_{x_i\epsilon M}y_i(w\cdot x_i+b)$

其中，M代表所有误分类点的集合

损失函数( $\frac{1}{||w||}$ 不影响最后的结果)：

$L(w,b)=-\sum\limits_{x_i\epsilon M}y_i(w\cdot x_i+b)$

第二节梯度下降法

概念

梯度，指某一函数在该点出最大的方向导数，沿着该方向可取得最大的变化率

$\bigtriangledown =\frac{\partial f(\theta)}{\partial \theta}$

若 $f(\theta)$ 是凸函数，可通过梯度下降法进行优化：

$\theta^{(k+1)}=\theta^{(k)}-\eta \bigtriangledown f(\theta^{(k)})$

算法

输入：目标函数 $f(\theta)$ ,步长为 $\eta$ ,计算精度 $\varepsilon$ ;

输出： $f(\theta)$ 得极小值点 $\theta^*$

(1)选取初始值 $\theta^{(0)}\epsilon R^n$ ,置k=0

(2)计算 $f(\theta^{(k)})$

(3)计算梯度 $\bigtriangledown f({\theta^{(k)}}))$

(4)置 $\theta^{(k+1)}=\theta^{(k)}-\eta \bigtriangledown f(\theta^{(k)})$ ，计算 $f(\theta^{(k+1)})$ ;当 $||f(\theta^{k+1})-f(\theta^{(k)})||<\varepsilon$ 或者 $||\theta^{(k+1)}-\theta^{k}||<\varepsilon$ 时，停止迭代，令 $\theta^*=\theta^{(k+1)}$

(5)否则，置k=k+1，转(3)

梯度：

单变量

$f(x)=x^2$ , $\bigtriangledown_x = \frac{\partial(x)}{\partial x}=2x$

$g(\theta)=(2-\theta)^3$ , $\bigtriangledown_{\theta}=\frac{\partial g(\theta)}{\partial\theta}=-3(2-\theta)^2$

多变量： $F(\theta)=5\theta_{1}^2+2\theta_2+\theta_3^4, \theta=(\theta_1,\theta_2,\theta_3)'$

$\bigtriangledown_{\theta_1} = \frac{\partial F(\theta)}{\partial\theta_1}=10\theta_1$

$\bigtriangledown_{\theta_2}=\frac{\partial F(\theta)}{\partial\theta_2}=2$ $\Rightarrow \bigtriangledown_\theta=(10\theta_1,2,4\theta_3^3)$

$\bigtriangledown_{\theta_3}=\frac{\partial F(\theta))}{\partial\theta_3}=4\theta_{3}^3$

通俗的理解，当为多变量时，梯度可以是一个一阶导数矩阵

梯度下降法：例子

梯度下降法：

$\theta^{(k+1)} = \theta^{(k)}-\eta\bigtriangledown f(\theta^{(k)})$

例子：

$f(\theta)=\theta^2$ , $\bigtriangledown_{\theta}=\frac{\partial f(\theta)}{\partial \theta}=2\theta$

初始值和步长分别设置为：

$\theta^{(0)}=1$ , $\eta=0.4$ , $\varepsilon=0.01$

迭代计算过程：

$\theta^{(0)}=1$

$\theta^{(1)}=\theta^{(0)}-\eta\bigtriangledown f(\theta^{(0)})=1-0.4\times2=0.2$

$\theta^{(2)}=\theta^{(1)}-\eta\bigtriangledown f(\theta^{(1)})=0.2-0.4\times0.4=0.04$

$\theta^{(3)}=\theta^{(2)}-\eta\bigtriangledown f(\theta^{(2)})=0.04-0.4\times 0.08=0.008$

$\theta^{(4)}=\theta^{(3)}-\eta\bigtriangledown f(\theta^{(3)})=0.008-0.4\times 0.016=0.0016$

原理

泰勒展开：

$f(\theta)\approx f(\theta^{(k)})+(\theta-\theta^{(k)})\bigtriangledown f(\theta^{(k)})$

$f(\theta)\approx f(\theta^{(k)})-(\theta^{(k)}-\theta)\bigtriangledown f(\theta^{(k)})$

$f(\theta)\approx f(\theta^{(k)})+(\theta-\theta^{(k)})\bigtriangledown f(\theta^{(k)})$

$\theta-\theta^{(k)}$ 的单位向量用v表示， ${\eta}'$ 为标量

$\theta - \theta^{(k)}={\eta}'v$

重新表达，

$f(\theta)\approx f(\theta^{(k)})+{\eta}'v\cdot\bigtriangledown f(\theta^{(k)})$

更新θ使函数值变小，因此

$f(\theta)-f(\theta^{(k)})\approx {\eta}'v \cdot \bigtriangledown f(\theta^{(k)})<0\Rightarrow v\cdot\bigtriangledown f(\theta^{(k)})<0$

v和 $\bigtriangledown f(\theta^{(k)})$ 互为反向才能满足这一条件,即

$v = -\frac{\bigtriangledown f(\theta^{(k)})}{||\bigtriangledown f(\theta^{(k)})||}$

更新θ

$\theta^{(k+1)} = \theta^{(k)}-{\eta}'\frac{\bigtriangledown f(\theta^{(k)})}{||\bigtriangledown f(\theta^{(k)})}||$

化简

$\theta^{(k+1)}=\theta^{(k)}-\eta\bigtriangledown f(\theta^{(k)})$

第三节学习算法之原始形式

学习问题

训练数据集：

$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$

其中， $x_i\epsilon \chi \subseteq R^n$ , $y_i\epsilon Y=\{+1,-1\}$

损失函数：

$L(w,b)=-\sum_{x_i\epsilon M}y_i(w\cdot x_i+b)$

其中，M代表误分类点的集合

模型参数估计：

$\arg \min\limits_{w,b}L(w,b)$

原始形式

损失函数：

$L(w,b)=-\sum\limits_{x_i\epsilon M}y_i(w\cdot x_i+b)$

梯度：

$\bigtriangledown_w L(w,b)=-\sum\limits_{x_i\epsilon M}y_ix_i$ ; $\bigtriangledown_b L(w,b)=-\sum\limits_{x_i\epsilon M}y_i$

参数更新：

批量梯度下降法(Batch Gradient Descent):每次迭代时使用所有误分类点来进行参数更新

$w \leftarrow w+\eta\sum\limits_{x_i\epsilon M}y_ix_i$ ; $b \leftarrow b+\eta\sum\limits_{x_i\epsilon M}y_i$

其中， $\eta(0\leq{\eta}\leq{1})$ 代表步长

随机梯度下降法(Stochastic Gradient Descent):每次随机选取一个误分类点

${\color{Blue}w\leftarrow w+\eta y_ix_i }$ ; ${\color{Blue} b\leftarrow b + \eta y_i}$

算法

输入：训练集：

$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$

其中， $x_i\epsilon \chi \subseteq R^n$ , $y\epsilon Y= \{+1,-1\}$ ;步长 $\eta(0<\eta\leq1)$

输出：w,b;感知机模型 $f(x)=sign(w\cdot x+b)$

(1)选取初始值 $w_0,b_0$ ;

(2)在训练集中随机选取数据 $(x_i,y_i)$ ;

(3)若 $y_i(w\cdot x+b)\leq 0$ ,

$w\leftarrow w+\eta y_ix_i$ ; $b\leftarrow b+\eta y_i$

(4)转(2),直到训练集中没有误分类点

例题分析

输入：训练集：

$T=\{(x_1,+1),(x_2,+1),(x_3,-1)\}$

其中， $x_1=(3,3)^T,x_2=(4,3)^T,x_3=(1,1)^T$ ,假设η=1

输出：w,b;感知机模型 $f(x)=sign(w\cdot x+b)$

此时学习问题转化为：

$\arg\min\limits_{w,b}L(w,b)=\arg\min\limits_{w,b}[-\sum\limits_{x_i\epsilon M}y_i(w\cdot x_i+b)]$

(1)选取初始值 $w_0=(0,0)^T,b_0=0$ ;

(2)对于点 $x_1$ ,有

$y_1(w_0\cdot x_1+b_0)=+1\times((0,0)^T\cdot (3,3)^T+0)=0$

- 更新参数，

$w_1=w_0+\eta y_1x_1=(3,3)^T$ , $b_1=b_0+\eta y_1=1$

- 模型，

$w_1\cdot x+b=3x^{(1)}+3x^{(2)}+1$

(3)对于点 $x_1$ ,有

$y_1(w_1\cdot x_1+b_1)=+1\times (3x_1^{(1)}+3x_1^{(2)}+1)=19>0$ (被正确分类)

对于点 $x_2$ ,有

$y_2(w_1\cdot x_2+b_1) = +1\times (3x_2^{(1)}+3x_2^{(2)}+1)=22>0$ (被正确分类)

对于点 $x_3$ ,有

$y_3(w_1\cdot x_3+b_1)=-1 \times(3x_3^{(1)}+3x_3^{(2)}+1)=-7<0$ (被错误分类)

- 更新参数，

$w_2=w_1+\eta y_3x_3=(2,2)^T$ , $b_2=b_1+\eta y_3=0$

-模型，

$w_2\cdot x+b_2=2x^{(1)}+2x^{(2)}$

(4)重复以上步骤，直到没有误分类点

得到参数

$w_7=(1,1)^T,$ $b_7=-3$

模型，

$w_7\cdot x+b_7=x^{(1)}+x^{(2)}-3$

结果：

分离超平面

$x^{(1)}+x^{(2)}-3=0$

感知机模型，

$f(x)=sign(x^{(1)}+x^{(2)}-3)$

注：

若误分类点依次取 $x_1,x_3,x_3,x_1,x_3,x_3,$ 可以得到分离超平面

$x^{(1)}+x^{(2)}-3=0$

若误分类点依次取 $x_1,x_3,x_3,x_3,x_2,x_3,x_3,x_3,x_1,x_3,x_3,$ 可以得到分离超平面

$2x^{(1)}+x^{(2)}-5=0$

第三节学习算法之对偶形式

对偶形式

在原始形式中，若 $(x_i,y_i)$ 为误分类点，可得如下更新参数的方式：

$w \leftarrow w+\eta y_ix_i$ ; $b \leftarrow b+\eta y_i$

假设初始值 $w_0=\boldsymbol{0}$ , $b_0=0$ ,对误分类点 $(x_i,y_i)$ 通过上述公式更新参数，修改 $n_i$ 次之后， $w,b$ 的增量分别为 $\alpha_i y_ix_i$ 和 $\alpha_iy_i$ ,其中 $\alpha_i=n_i\eta$ 。
最后学习到的参数为，

$w = \sum\limits_{i=1}^N\alpha_iy_ix_i$ ; $b=\sum\limits_{i=1}^N\alpha_iy_i$

对原始算法求解的迭代过程再做分析

更新次数： ${\color{Blue}n_1=2,n_2=0,n_3=5,}$ 最后学习到的参数为，

${\color{Blue}w=\alpha_1y_1x_1+\alpha_3y_3x_3=(1,1)^T;}$ ${\color{Blue}b = \alpha_1y_1+\alpha_3y_3=-3}$

其中 $n_i$ 表示第i个实例点在参数更新中贡献的次数。

实例点 $x_1$ 为正例，因此 $y_1$ 为+1，所以 $\alpha_1y_1x_1$ 为 $(6,6)^T$ ;实例点 $x_3$ 为负例，因此 $y_3$ 为-1，所以 $\alpha_3y_3x_3$ 为 $(-5,-5)^T$ ，最终 $w$ 为 $(1,1)^T$ 。同理可得b。

算法

输入：训练集：

$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$

其中， $x_i\epsilon\chi\subseteq R^n$ , $y\epsilon Y=\{+1,-1\}$ ;步长 $\eta(0<\eta<1)$

输出： $\alpha,b;$ 感知机模型 $f(x)=sign(\sum\limits_{j=1}^N\alpha_jy_jx_j\cdot x+b)$ ,其中 $\alpha=(\alpha_1,\alpha_2,...,\alpha_N)^T$

(1)选取初始值 $\alpha^{<0>}=(0,0,...,0)^T,b^{<0>}=0;$

(2)在训练集中随机选取数据 $(x_i,y_i)$ ;

(3)若 $y_i(\sum\limits_{j=1}^N\alpha_jy_jx_j\cdot x_i+b)\leq0$ ,

${\color{Blue}\alpha_i\leftarrow\alpha_i+\eta;}$ ${\color{Blue}b\leftarrow b+ \eta y_i}$

(4)转(2),直到训练集中没有误分类点。

对(3)步进行具体分析：

迭代条件：

$\begin{aligned}y_i(\sum\limits_{j=1}^N\alpha_jy_jx_j\cdot x_i+b)&=y_i[(\alpha_1y_1x_1+\alpha_2y_2x_2+\hdots+\alpha_Ny_Nx_N)\cdot x_i+b]\\ &=y_i(\alpha_1y_1x_1\cdot x_i+\alpha_2y_2x_2\cdot x_i+\hdots+\alpha_Ny_Nx_N\cdot x_i+b)\\ &\leq 0 \end{aligned}$

$Gram$ 矩阵：

$G=[x_i\cdot x_j]_{N\times N}=\begin{bmatrix}x_1\cdot x_1\quad x_1\cdot x_2 \quad \hdots \quad x_1\cdot x_N \\ x_2\cdot x_1\quad x_2\cdot x_2 \quad\hdots\quad x_2\cdot x_N\\ \vdots\qquad\quad\vdots\qquad\qquad\qquad\vdots\\ x_N\cdot x_1\quad x_N\cdot x_2 \quad\hdots\quad x_N\cdot x_N \end{bmatrix}$

例题分析

输入：训练集：

$T=\{(x_1,+1),(x_2,+1),(x_3,-1)\}$

其中， $x_1=(3,3)^T,x_2=(4,3)^T,x_3=(1,1)^T$ ,假设η=1

输出： $\alpha$ ,b;感知机模型 ${\color{Blue}f(x)=sign(\sum\limits_{i=j}^N\alpha_jy_jx_j+b)}$

(1)选取初始值 $\alpha^{<0>}=(0,0,0)^T,b^{<0>}=0;$

(2)计算Gram矩阵

$G=[x_i\cdot x_j]_{N\times N}=\begin{bmatrix}x_1\cdot x_1\quad x_1\cdot x_2 \quad \hdots \quad x_1\cdot x_3 \\ x_2\cdot x_1\quad x_2\cdot x_2 \quad\hdots\quad x_2\cdot x_3\\ \vdots\qquad\quad\vdots\qquad\qquad\qquad\vdots\\ x_3\cdot x_1\quad x_3\cdot x_2 \quad\hdots\quad x_3\cdot x_3\end{bmatrix}=\begin{bmatrix} 18\quad21\quad6 \\ 21\quad25\quad7\\ 6\quad7\quad2\end{matrix}$

(3)误分类条件 $y_i(\sum\limits_{j=1}^N\alpha_jy_jx_j\cdot x_i+b)\leq0,$ 参数更新

${\color{Blue}\alpha_i\leftarrow\alpha_i+1};$ ${\color{Blue}b\leftarrow b+\eta y_i}$

(4)对于点 $x_1$ ,有

$y_1(\sum\limits_{j=1}^N\alpha_jy_jx_j\cdot x_1+b)\leq0$ （被错误分类）

- 参数更新，

$\alpha_1^{<1>}=\alpha_1^{<0>}+\eta=1,$ $b^{<1>}=b^{<0>}+\eta y_1=1$

(5)对于点 $x_1,$ 有

$y_1(\sum\limits_{j=1}^N\alpha_j^{<1>}y_jx_j\cdot x_1+b^{<1>})=y_1(\alpha_1^{<1>}y_1x_1\cdot x_1+b^{<1>})=19\geq0$ （被正确分类）

对于点 $x_2$ ,有

$y_2(\sum\limits_{j=1}^N\alpha_j^{<1>}y_jx_j\cdot x_2+b^{<1>})=y_2(\alpha_1^{<1>}y_1x_1\cdot x_2+b^{<1>})=22\geq0$ （被正确分类）

对于点 $x_3$ ,有

$y_3(\sum\limits_{j=1}^N\alpha_j^{<1>}y_jx_j\cdot x_3+b^{<1>})=y_3(\alpha_1^{<1>}y_1x_1\cdot x_3+b^{<1>})=-7\leq0$ （被错误分类）

- 更新参数，

$\alpha_3^{<2>}=\alpha_3^{<1>}+\eta=1,$ $b^{<2>}=b^{<1>}+\eta y_3=0$

（6）重复以上步骤，直到没有误分类点

(7)得到参数

${\color{Blue}w^{<7>}=2x_1+0x_2-5x_3=(1,1)^T},$ ${\color{Blue}b^{<7>}=-3}$

结果：

- 分离超平面

$x^{(1)}+x^{(2)}-3=0$

- 感知机模型

$f(x)=sign(x^{<1>}+x^{<2>}-3)$

第四节原始形式算法的收敛性

定理

记 $\hat w=(w^{T},b)^T,\hat x=(x^T,1)^T,$ 则分离超平面可以写为

$\hat w\cdot \hat x=0$

Novikoff

若训练集

$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N))\}$

线性可分，其中， $x_i\epsilon \chi \subseteq R^n$ , $y\epsilon Y=\{+1, -1\},$ 则

(1)存在满足条件 $||\hat w_{opt}||=1$ 的超平面 $\hat w_{opt}\cdot \hat x=0$ 可将T完全正确分开；且 $\exists \gamma>0,$ 对所有 $i=1,2,...,N,$

$y_i(\hat w_{opt}\cdot \hat x_i) \geq \gamma$

(2)令 $R=max_{1\leq i \leq N}||\hat x_i||$ ,则感知机算法在T上的误分类次数k满足不等式

$k\leq (\frac{R}{\gamma})^2$

证明

(1) $\because T$ 线性可分

$\therefore \exists$ 超平面 $\hat w_{opt}\cdot\hat x=w_{opt}\cdot x+b_{opt}=0$ 将T完全正确分开。(不妨令 $||\hat w_{opt}||=1$ )

那么，对有限的 $i=1,2,...,N$ 均有

$y_i(\hat w_{opt}\cdot \hat x_i)=y_i(w_{opt}\cdot x_i+b_{opt})>0$

记 $\gamma=min_i \{y_i(w_{opt}\cdot x_i+b_{opt})\},$ 则有

$y_i(\hat w_{opt}\cdot \hat x_i)=y_i(w_{opt\cdot x_i+b_{opt}})\geq \gamma$

(2)假设 $\hat w_0=\mathbf{0},$ 为n_1维；若实例被误分类，则权重更新。令 $\hat w_{k-1}$ 为第k个误分类实例之前的扩充权重向量，即

$\hat w_{k-1}=(w_{k-1}^T, b_{k-1})$

若

$y_i(\hat w_{k-1}\cdot \hat x_i)=y_i(w_{k-1}\cdot x_i + b_{k-1})\leq0$

则， $(x_i,y_i)$ 为第k个误分类实例，更新参数，

$\left \{ \begin{aligned} w_k\leftarrow w_{k-1}+\eta y_ix_i \\ b_k\leftarrow b_{k-1}+\eta y_i \quad\end{aligned}\right.\qquad\Rightarrow \hat w_k = \hat w_{k-1}+\eta y_i\hat x_i$

需要推导的两个不等式：

$\left\{\begin{aligned}\hat w_k \cdot \hat w_{opt}\geq k\eta\gamma \\ ||\hat w_k||^2\leq k{\eta}^2 R^2 \end{aligned}\right.$

(1) $\hat w_k\cdot\hat w_{opt}\geq k\eta\gamma:$

$\begin{aligned}\hat w_k \cdot \hat w_{opt} & =(\hat w_{k-1}+\eta y_i\hat x_i)\cdot \hat w_{opt}\\ & =\hat w_{k-1}\cdot\hat w_{opt}+\eta{\color{Blue} y_i\hat w_{opt}\cdot\hat x_i} \\ &\geq \hat w_{k-1}\cdot \hat w_{opt}+\eta\gamma \\ &\geq\hat w_{k-2}\cdot \hat w_{opt}+2\eta\gamma \\ &\quad\vdots \\ &\geq\hat w_1\cdot\hat w_{opt}+(k-1)\eta\gamma \\ &\geq \hat w_0\cdot\hat w_{opt}+k\eta\gamma\\ &=k\eta\gamma \end{aligned}$

(2) $||\hat w_k||^2\leq k\eta^2R^2:$

$\begin{aligned} ||\hat w_k||^2 & =||\hat w_{k-1}+\eta y_i\hat x_i||^2\\ & = ||\hat w_{k-1}||^2+2\eta{\color{Blue} y_i\hat w_{k-1}\cdot \hat x_i}+\eta^2||\hat x_i||^2 \\ &\leq||\hat w_{k-1}||^2 + \eta^2{\color{Blue}||\hat x_i||^2}\\ &\leq||\hat w_{k-1||^2}+\eta^2R^2\\ &\leq||\hat w_{k-1}||^2+2\eta^2R^2\\ &\quad\vdots\\ &\leq||\hat w_1||^2+(k-1)\eta^2R^2\\ &\leq||\hat w_0||^2+k\eta^2R^2\\ &=k\eta^2R^2 \end{aligned}$

结合所得两个不等式，

$\left\{\begin{aligned}\hat w_k \cdot \hat w_{opt}\geq k\eta\gamma \\ ||\hat w_k||^2\leq k{\eta}^2 R^2 \end{aligned}\right.\qquad \Rightarrow k\eta\gamma\leq\hat w_k\cdot\hat w_{opt}\leq ||\hat w_k||||\hat w_{opt}||\leq\sqrt{k}\eta R$

$\therefore k\eta\gamma\leq\sqrt{k}\eta R\Rightarrow k^2\gamma^2\leq kR^2$

于是，有

$k\leq(\frac{R}{\gamma})^2$

收敛性：对于线性可分的T,经过有限次搜索，可得将T完全正确分开的分离超平面。
依赖性：不同的初值选择，或者迭代过程中不同的误分类点选择顺序可能会得到不同的分离超平面。
对于线性不可分的T,算法不收敛，迭代结果会发生震荡。
未得到唯一分离超平面，需增加约束条件。

参考资料：

《统计学习方法》第二版

参考视频：

【合集】十分钟机器学习系列视频《统计学习方法》_哔哩哔哩_bilibili