> For the complete documentation index, see [llms.txt](https://windmising.gitbook.io/lihang-tongjixuexifangfa/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://windmising.gitbook.io/lihang-tongjixuexifangfa/perceptron/4.md).

# 梯度下降法的收敛证明

**证明：经过有限次迭代，可以得到一个将线性可分的训练数据集完全正确划分的分离超平面及感知机模型**

*当训练数据集线性不可分时，算法不收敛*

## 假设前提：

1. 所有训练数据点都线性可分的  
2. 初值$$(w\_0, b\_0) = \vec{0}$$

## 证明前的一些定义

（1）令

$$
\begin{aligned}
\hat w = (w^T, b)^T && \text{向量一般默认为列向量} \\
\hat x = (x, 1)
\end{aligned}
$$

则

$$
\hat w \cdot \hat x = w \cdot x + b
$$

（2）\
所有训练数据点都线性可分\
$$\Rightarrow \exists$$一个超平面，使得所有训练数据集都被正确划分\
令这个超平面为

$$
\begin{aligned}
\hat w\_{opt} \cdot \hat x = 0  \text{且} ||\hat w\_{opt}|| = 1 && {15}
\end{aligned}
$$

（3）令

$$
\begin{aligned}
\gamma = min\_i{y\_i(\hat w\_{opt} \cdot \hat x\_i)}  && {1}
\end{aligned}
$$

（4）令$$\hat w\_k$$为更新了k次之后的$$\hat w$$\
（5）令

$$
\begin{aligned}
R = max\_{1 \le i \le n}||\hat x\_i|| && {10}
\end{aligned}
$$

## 证明过程

超平面$$\hat w\_{opt} \cdot \hat x = 0$$将所有数据都完全正确的分开\
$$\Rightarrow \forall (\hat x\_i, y\_i)$$，有$$y\_i$$与$$\hat w\_{opt} \cdot \hat x\_i$$符号相同，且两者都不为0\
$$\Rightarrow \forall (\hat x\_i, y\_i)$$，有$$y\_i(\hat w\_{opt} \cdot \hat x\_i)>0$$\
以上结论结合公式（1）得：

$$
\begin{aligned}
y\_i(\hat w\_{opt} \cdot \hat x\_i) \ge \gamma \gt 0  && {2}
\end{aligned}
$$

假设算法已经更新了k次，则至少有一个样本点在超平面$$\hat w\_{k-1} \cdot \hat x = 0$$上分类错误\
假设$$(x\_i, y\_i)$$就是这个分类错误的点，则

$$
\begin{aligned}
y\_i(\hat w\_{k-1} \cdot \hat x\_i) < 0 && {9}
\end{aligned}
$$

且：

$$
\begin{cases}
w\_k = w\_{k-1} + \eta y\_ix\_i \\
b\_k = b\_{k-1} + \eta y\_i && (3)
\end{cases}
$$

计算$$\hat w\_{k}$$与$$\hat w\_{k-1}$$的关系：

$$
\begin{aligned}
\hat w\_k = (w\_k, b\_k) = (w\_{k-1} + \eta y\_ix\_i, b\_{k-1} + \eta y\_i) \\
\= (w\_{k-1}, b\_{k-1}) + (\eta y\_ix\_i, \eta y\_i) = \hat w\_{k-1} + \eta y\_i (x\_i, 1)
\= \hat w\_{k-1} + \eta y\_i \hat x\_i
\end{aligned}
$$

得到：

$$
\begin{aligned}
\hat w\_k =  \hat w\_{k-1} + \eta y\_i \hat x\_i && {4}
\end{aligned}
$$

*Note: 由公式（3）推公式（4）本来很简单，之前一直推不出来是因为我把公式（4）*$$\eta y\_i \hat x\_i$$*当成了一个数，用numpy里面向量和数值相加的公式来算公式（4）。实际上*$$\eta y\_i \hat x\_i$$*也是一个n+1的向量，应该使用向量的加法来计算公式（4）。*

证明$$\hat w\_k \cdot \hat w\_{opt} \ge 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}  && {5}
\= \hat w\_{k-1} \cdot \hat w\_{opt} + \eta y\_i \hat x\_i \cdot \hat w\_{opt} && {}
\ge \hat w\_{k-1} \cdot \hat w\_{opt} + \eta \gamma && {6}
\ge \hat w\_{k-2} \cdot \hat w\_{opt} + 2\eta \gamma
\cdots && {}
\ge \hat w\_0 \cdot \hat w\_{opt} + k\eta \gamma
\ge k\eta \gamma && {7}
\end{aligned}
$$

公式说明：\
1\. 步骤（5）：由公式（4）得到\
2\. 步骤（6）：由公式（2）得到\
3\. 步骤（7）：假设初值$$(w\_0, b\_0) = \vec{0}$$？ 最终得到：

$$
\begin{aligned}
\hat w\_k \cdot \hat w\_{opt} \ge k \eta \gamma && {8}
\end{aligned}
$$

证明$$||\hat w\_k||^2 \le k \eta^2R^2$$：

$$
\begin{aligned}
||\hat w\_k||^2 = ||\hat w\_{k-1}||^2 + 2\hat w\_{k-1}\eta y\_i\hat x\_i + (\eta y\_i \hat x\_i)^2 && {11}
\lt ||\hat w\_{k-1}||^2 + 0 + \eta^2\hat x\_i^2 &&{12}
\le ||\hat w\_{k-1}||^2 + \eta^2R^2 &&{13}
\le ||\hat w\_{k-2}||^2 + 2\eta^2R^2
\cdots
\le ||\hat w\_{0}||^2 + k\eta^2R^2 &&{13}
\le k\eta^2R^2
\end{aligned}
$$

公式说明：\
1\. 步骤（11）：结合公式（4）得到\
2\. 步骤（12）：结合公式（9）得到第二项小于，第三项中$$y\_i^2=1$$\
3\. 步骤（13）：结合公式（10）得到\
最终得到：

$$
\begin{aligned}
||\hat w\_k||^2 \le k \eta^2R^2 && {14}
\end{aligned}
$$

$$
\begin{aligned}
\text{公式8}\Rightarrow  k\eta\gamma \le \hat w\_k \cdot \hat w\_{opt}
\Rightarrow  k^2\eta^2\gamma^2 \le ||\hat w\_k||^2||\hat w\_{opt}||^2
\Rightarrow  k^2\eta^2\gamma^2 \le ||\hat w\_k||^2 \le \eta^2R^2 && {16}
\Rightarrow  k \le (\frac {R}{\gamma})^2
\end{aligned}
$$

公式说明：\
1\. 步骤（16）：结合公式（15）

最终结论：

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

命题得证