感知机
模型介绍
感知机简单来说就是找到一个平面,将数据分成两类.因为这是一个分类的模型,所以这一定是一个监督模型.这个模型的输入是实例的特征向量,输出的是+1和-1作为内边的判断.
模型函数
$$f(x) = sign(\omega{x}+b)$$
任何一点到此超平面的距离$\propto\omega{x_i}+b$
对于误分类的数据 $-y_i(\omega{x_i}+b) \geq 0(y_i对于距离的绝对大小没有影响)$
所以对于所有误分类点到超平面的总距离$\propto{\underset{x_i\in{M}}\Sigma{-y_i(\omega{x_i}+b)}}$
所以损失函数定义为
$$L(\omega,b) = {\underset{x_i\in{M}}\Sigma{-y_i(\omega{x_i}+b)}}$$
感知机学习算法
感知机模型是误差驱动的模型,当损失函数极小化的时候,则可认为拟合完成.采取梯度下降算法进行损失函数极小化(梯度下降算法容易陷入极小化陷阱,所以不一定能求得最小值).
梯度向量是$(-{\Sigma}y_ix_i,-{\Sigma}y_i) = (\nabla_{\omega}L(\omega,b),\nabla_{b}L(\omega,b))$,步长是$\eta$
原始形式
- 选取初始的$\omega_0,b_0$
- 在训练集中选取数据$(x_i,y_i)$
- 如果$-y_i(\omega{x_i}+b) \geq 0$
$$\begin{aligned}
\omega \leftarrow \omega + \eta{y_ix_i}\\
b \leftarrow b + \eta{y_i}
\end{aligned}$$ - 循环第二步,直到没有误分类点
对偶形式
$$\begin{aligned}
\omega \leftarrow \omega + \eta{y_ix_i}\\
b \leftarrow b + \eta{y_i}
\end{aligned}$$
不难看出最后的
$$\begin{aligned}
\qquad\omega &= \Sigma\alpha_iy_ix_i+\omega_0\\
b &= \Sigma\alpha_iy_i+b_0\\
\alpha_i &= n_i\eta(n是该点由于误分进行更新的次数)
\end{aligned}$$
令$\omega_0 = 0,b_0 = 0$
算法:
- $\alpha \rightarrow 0,b \rightarrow 00$
- 读取数据($x_i,y_i$)
- 如果$y_i(\Sigma{\alpha_j}y_jx_jx_i + b) \leq 0$
$$\begin{aligned}
\alpha_i = \alpha_i + \eta \\
b = b + {\eta}y_i
\end{aligned}$$ - 重复第二步直至没有误分类数据
