365 次浏览

感知机与线性可分

感知机

感知机是一个线性分类模型,由于与神经网络类似而得名。它解决的是二分类问题,当我们输入的样本\(\)\(X= (x_1, x_2, \ldots, x_n)^T\)\(\)(其中\(\)\(x_i\)\(\)为向量),对应标签为\(\)\(Y = (y_1, y_2, \ldots, y_n)^T\)\(\)(其中\(\)\(y_i \in \{-1, 1\}\)\(\)),目标是找到超平面\(\)\(w^T x +b = 0\)\(\)将数据划分开来。

\(\)\(f(x)=sign(w^T x + b)\)\(\)
\(\)\(sign(x)\)\(\)是一个符号函数

我们的数据通过上式,可以得出对应的属性\(\)\(\hat{y}\)\(\),划分完,出现误分类,即原本+1的被误分为-1,或者-1被误分为+1,换成数学公式为\(\)\(-y(w^T x +b > 0)\)\(\),误分类的点到超平面的距离:\(\)\(-\frac{y_i (w^T x_i +b)}{||w||}\)\(\),所以误分类的点带来的损失为\(\)\(-\frac{\sum y_i (w^T x_i +b)}{||w||}\)\(\)。我们需要最小化损失,可以采用梯度下降法。

损失函数:
\(\)\(L = -\sum y_i(w^T x_i + b)\)\(\)

梯度如下:
\(\)\(\Delta _w = -\sum y_i x_i\)\(\)
\(\)\(\Delta_b=-\sum y_i\)\(\)

更新(\(\)\(\eta\)\(\)为学习率):
\(\)\(w \leftarrow w+\eta y_i x_i\)\(\)
\(\)\(b \leftarrow b + \eta y_i\)\(\)

上述式子可以由如下图来解释,易知向量\(\)\(w\)\(\)为超平面的法向量。
1. 原类为-1,误分类为+1时,则需要将\(\)\(w\)\(\)与\(\)\(x\)\(\)夹角变小
2. 原类为+1,误分类为-1时,则需要将\(\)\(w\)\(\)与\(\)\(x\)\(\)夹角变大

线性可分

根据上面的过程,感知机进行分类时其实是很严格的,需要数据是线性可分的。

若数据是线性可分的,假设目标函数的理想权重为\(\)\(w_f\)\(\),我们的权重有\(\)\(w_t\)\(\),根据情况修正至\(\)\(w_{t+1}\)\(\),最终使得\(\)\(w_{t+1}\approx w_f\)\(\),所有数据我们都正确分类。并且\(\)\(w_{t+1}\)\(\)与\(\)\(w_f\)\(\)的内积越来越大

\(\)\(w_f ^T w_{t+1} = w_f ^T (w_t +y_i ^{(t)} x_i ^{(t)}) \geq w_f ^T w_t + \min y_i ^{(t)} w_f ^T x_i ^{(t)} > w_f ^T w_t\)\(\)

\(\)\(w_{t+1}\)\(\)与\(\)\(w_f\)\(\)的内积越来越大,但是我们还需要知道\(\)\(w\)\(\)的长度对此内积的影响。

\(\)\(||w_{t+1}||^2 = ||w_t + y_i ^{(t)} x_i ^{(t)}||^2 \leq ||w_t||^2 + \max ||x_i ^{(t)}||^2\)\(\)

由上式可知,\(\)\(||w_{t+1}||^2\)\(\)的增长被限制了,\(\)\(||w_{t+1}||^2\)\(\)的增加不会超过\(\)\(\max||x_i^{(t)}||^2\)\(\)

通过novikoff定理,感知机最终会在上界固定的\(\)\(k\)\(\)此收敛。

reference
1. https://blog.csdn.net/red_stone1/article/details/70866527
2. 周志华. 《机器学习》
3. 李航. 《统计学习方法》