概述
学习问题
训练数据集：$$T={(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)}$$其中，$x_i\in\mathcal X\subseteq\boldsymbol R^n,y_i\in\mathcal Y={+1,-1}$ 损失函数：$$L(w,b)=\sum_{x_i\in M}y_i(w\cdot x_i+b)$$其中，$M$表示所有误分类点的集合 模型参数估计：$$\underset{w,b}{\arg\min}L(w,b)$$
随机梯度下降法
损失函数：$$L(w,b)=\sum_{x_i\in M}y_i(w\cdot x_i+b)$$ 梯度：$$\nabla_wL(w,b)=-\sum_{x_i\in M}y_ix_i;\quad\nabla_bL(w,b)=-\sum_{x_i\in M}y_i$$ 参数更新：
- 批量梯度下降法（Batch Gradient Descent）；每次迭代时使用所有误分类点来进行参数更新$$w\leftarrow w+\eta\sum_{x_i\in M}y_ix_i;\quad b\leftarrow b+\eta\sum_{x_i\in M}y_i$$其中，$\eta(0<\eta\leq1)$表示步长
- 随机梯度下降法（Stochastic Gradient Descent）：每次随机选取一个误分类点$$w\leftarrow w+\eta y_ix_i;\quad b\leftarrow b+\eta y_i$$
算法
输入：训练集：$$T={(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)}$$其中，$x_i\in\mathcal X\subseteq\boldsymbol R^n,y_i\in\mathcal Y={+1,-1}$；步长$\eta(0<\eta\leq1)$ 输出：$w,b$；感知机模型$f(x)=sign(w\cdot x+b)$
对于感知机模型，参数$w$对应分离超平面的旋转程度，$b$对应位移量
-
选取初始值$w_0,b_0$（例如图中的蓝线）
-
于训练集中随机选取数据$(x_i,y_i)$
-
若$y_i(w\cdot x_i+b)\leq 0$，$$w\leftarrow w+\eta y_ix_i;\quad b\leftarrow b+\eta y_i$$
-
转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$，假设$\eta=1$
输出：$w,b$；感知机模型$f(x)=sign(w\cdot x+b)$
学习问题：$$\underset{w,b}{\arg\min}L(w,b)=\underset{w,b}{\arg\min}[-\sum_{x_i\in M}y_i(w\cdot x_i+b)]$$
-
选取初始值$w_0=(0,0)^T,b_0=0$
-
对于点$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_ix_i=(3,3)^T,\quad b_1=b_0+\eta y_1=1$$
- 模型，$$w_1\cdot x+b=3x^{(1)}+3x^{(2)}+1$$
-
对于点$x_1$，有$$y_1(w_1\cdot x_1+b_1=+1\times(3x^{(1)}_1+3x^{(2)}_1+1)=19>0$$ 对于点$x_2$，有$$y_2(w_1\cdot x_2+b_1=+1\times(3x^{(1)}_2+3x^{(2)}_2+1)=22>0$$ 对于点$x_3$，有$$y_3(w_1\cdot x_3+b_1=-1\times(3x^{(1)}_3+3x^{(2)}_3+1)=-7<0$$
- 更新参数$$w_2=w_1+\eta y_3x_3=(2,2)^T,\quad b_2=b_1+\eta y_3=0$$
- 模型，$$w_2\cdot x+b_2=2x^{(1)}+2x^{(2)}$$
-
重复以上步骤，直到没有误分类点
迭代次数|误分类点|$w$|$b$|$w\cdot x+b$ :-:|:-:|:-:|:-:|:-: $0$| |$(0,0)^T$|$0$|$0$|$0$ $1$|$x_1$|$(3,3)^T$|$1$|$3x^{(1)}+3x^{(2)}+1$ $2$|$x_3$|$(2,2)^T$|$0$|$2x^{(1)}+2x^{(2)}$ $3$|$x_3$|$(1,1)^T$|$-1$|$x^{(1)}+x^{(2)}-1$ $4$|$x_3$|$(0,0)^T$|$-2$|$-2$ $5$|$x_1$|$(3,3)^T$|$-1$|$3x^{(1)}+3x^{(2)}-1$ $6$|$x_3$|$(2,2)^T$|$-2$|$2x^{(1)}+2x^{(2)}-2$ $7$|$x_3$|$(1,1)^T$|$-3$|$x^{(1)}+x^{(2)}-2$ $8$| |$(1,1)^T$|$-3$|$x^{(1)}+x^{(2)}-3$ 得到参数$$w_7=(1,1)^T,\quad 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_3,x_1,x_3,x_3$，可以得到分离超平面$$x^{(1)}+x^{(2)}-3=0$$
- 若误分类点依次取$x_1,x_3,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$$
算法的收敛性：Novikoff定理
记$\hat w=(w^T,b)^T,\hat x=(x^T,1)^T$，则分离超平面可以写为$$\hat w\cdot \hat x=0$$ 若训练集$$T={(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)}$$线性可分，其中，$x_i\in\mathcal X\subseteq\boldsymbol R^n,y_i\in\mathcal Y={+1,-1}$，则
- 存在满足条件$||\hat w_{opt}||=1$（补充，一定存在$||\hat w_{opt}||=1$）的超平面$\hat w_{opt}\cdot\hat x=0$可将$T$完全正确分开，且$\exists \gamma>0$，对所有$i=1,2,\cdots,N$$$y_i(\hat w_{opt}\cdot \hat x_i)\geq\gamma$$
- 令$R=\underset{1\leq i\leq N}{\max}||\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}$将$T$完全正确的分开（不妨令$||\hat w_{opt}||=1$） 那么，对有限的$i=1,2,\cdots,N$均有$$y_i(\hat w_{opt}\cdot\hat x)=y_i(w_{opt}\cdot x+b_{opt})>0$$ 记$\gamma=\min_i{y_i(w_{opt}\cdot x+b_{opt})}$，则有$$y_i(\hat w_{opt}\cdot\hat x)=y_i(w_{opt}\cdot x+b_{opt})\geq\gamma$$
证明2. 假设$\hat w_0=\boldsymbol0$，若实例被误分类，则更新权重。令$\hat w_{k-1}$为第$k$个误分类实例之前的扩充权重向量，即$$\hat w_{k-1}=(w_{k-1}^T,b_{k-1})$$ 若$$y_i(\hat w_{opt}\cdot\hat x)=y_i(w_{opt}\cdot x+b_{opt})\leq0$$ 则，$(x_i,y_i)$为第$k$个误分类实例，更新参数，$$\begin{cases}w_k\leftarrow w_{k-1}+\eta y_ix_i\b_k\leftarrow b_{k-1}+\eta y_i\end{cases}\Rightarrow\hat w_k=\hat w_{k-1}+\eta y_i\hat x_i$$ 下面推导两个不等式$$\begin{cases}\hat w_k\cdot\hat w_{opt}\geq k\eta\gamma\||\hat w_k||^2\leq k\eta^2R^2\end{cases}$$ $\hat w_k\cdot\hat w_{opt}\geq k\eta\gamma$ $$ \begin{aligned} \hat{w}{k} \cdot \hat{w}{o p t} &=\left(\hat{w}{k-1}+\eta y{i} \hat{x}{i}\right) \cdot \hat{w}{o p t} \ &=\hat{w}{k-1} \cdot \hat{w}{o p t}+\eta y_{i} \hat{w}{o p t} \cdot \hat{x}{i} \ & \geq \hat{w}{k-1} \cdot \hat{w}{o p t}+\eta \gamma \ & \geq \hat{w}{k-2} \cdot \hat{w}{o p t}+2 \eta \gamma \ & \quad \vdots \ & \geq \hat{w}{1} \cdot \hat{w}{o p t}+(k-1) \eta \gamma \ & \geq \hat{w}{0} \cdot \hat{w}{o p t}+k \eta \gamma \ &=k \eta \gamma \end{aligned} $$ $||\hat w_k||^2\leq k\eta^2R^2$ $$ \begin{aligned} \left|\hat{w}{k}\right|^{2} &=\left|\hat{w}{k-1}+\eta y_{i} \hat{x}{i}\right|^{2} \ &=\left|\hat{w}{k-1}\right|^{2}+2 \eta y_{i} \hat{w}{k-1} \cdot \hat{x}{i}+\eta^{2}\left|\hat{x}{i}\right|^{2} \ & \leq\left|\hat{w}{k-1}\right|^{2}+\eta^{2}\left|\hat{x}{i}\right|^{2} \ & \leq\left|\hat{w}{k-1}\right|^{2}+\eta^{2} R^{2} \ & \leq\left|\hat{w}{k-2}\right|^{2}+2 \eta^{2} R^{2} \ & \quad \vdots \ & \leq\left|\hat{w}{1}\right|^{2}+(k-1) \eta^{2} R^{2} \ & \leq\left|\hat{w}{0}\right|^{2}+k \eta^{2} R^{2} \ &=k \eta^{2} R^{2} \end{aligned}$$ 结合两个不等式$$\left{ \begin{matrix} \hat{w}{k}. \hat{w_{opt}}\geq k \eta \gamma \ || \hat{w}{k}||^{2}\leq k \eta ^{2}R^{2}\ \end{matrix} \right. \Rightarrow k \eta \gamma \leq \hat{w}{k}. \hat{w}{opt}\leq || \hat{w_k}||\space|| \hat{w}{opt}|| \leq \sqrt{k}\eta R$$ $\therefore k\eta\gamma\leq\sqrt k\eta R\Rightarrow k^2\eta^2\leq kR^2$ 于是，有$$k\leq(\frac R\gamma)^2$$
说明
收敛性
- 对于线性可分的$T$，经过有限次搜索，可得将$T$完全正确分开的分离超平面
- 对于线性不可分的$T$，算法不收敛，迭代结果会发生震荡
依赖性
- 不同的初值选择，或者迭代过程中不同的误分类点选择顺序，可能会得到不同的分离超平面
- 为得到唯一分离超平面，需增加约束条件
算法实现
def original_form_of_perceptron(x, y, eta):
"""感知机学习算法的原始形式
:param x: 输入变量，二维数组，每个一维数组素表示一个特征向量，一位数组中的元素数量，表示维度的数量
:param y: 输出变量，一维数组，数量与x中一维数组的数量相同
:return: 感知机模型的w和b
"""
# 没啥必要的变量合理性检测，以后不会再写了
str = ''
if sum([len(x[i]) - len(x[0]) for i in range(len(x))]) !=0:
str += '输入x维度不唯一\n'
if len(x) != len(y):
str += '输入x，y数量不相同\n'
if eta > 1 or eta <= 0:
str += '输入eta不在范围内'
if str != '':
return str
n_samples = len(x) # 样本点数量
n_features = len(x[0]) # 特征向量维度数
# 用数组元素个数，模拟向量维度数
w0, b0 = [0] * n_features, 0 # 初值
while True:
for i in range(len(x)):
xi, yi = x[i], y[i]
if yi * (sum(w0[j] * xi[j] for j in range(n_features)) + b0) <= 0:
w1 = [w0[j] + eta * yi * xi[j] for j in range(n_features)]
b1 = b0 + eta * yi
w0, b0=w1, b1
break
else:
return w0, b0
测试
dataset = [[(3, 3), (4, 3), (1, 1)], [1, 1, -1]]
original_form_of_perceptron(dataset[0], dataset[1], eta=1)
([1, 1], -3)