感知机模型

感知机模型

• 定义：假设输入空间（特征空间）是$\chi \subseteq R^n $,输出空间是$Y=\{+1,-1\}$。输入$x\in\chi$表示实例的特征向量，对应于输入空间的点；输出$y\in Y$表示实例的类别。由输入空间到输出空间的如下函数：$$f(x)=sign(w\cdot{x}+b)$$称为感知机。

• 感知机的损失函数定义如下：$$L(w,b)=-\displaystyle \sum_{x_i\in M}y_i(w\cdot x_i+b)$$

• $\frac {\partial L}{\partial w}=-\displaystyle \sum_{x_i\in M}y_ix_i$

  $\frac{\partial L}{\partial b}=-\displaystyle \sum_{x_i\in M}y_i$

• 感知机学习算法的原始形式

  • 输入：训练数据集$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N\}$，其中$i=1,2,3,..,N$；学习率$\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_i+b)\leq0$，$$w\leftarrow w+\eta y_ix_i$$ $$b\leftarrow b+\eta y_i$$
    4. 转至2，直至训练集中没有误分类点
• 感知机学习算法的对偶形式
• 基本思想：将w和b表示为实例$x_i$和标记$y_i$的线性组合的形式，通过求解其系数而求得w和b。$$w\leftarrow w+\eta y_ix_i$$ $$b\leftarrow b+\eta y_i$$.假设$w_0,b_0$均为0.对误分类的点按照上式迭代，则$w,b$关于$(x_i,y_i)$的增量分别是$\alpha_iy_ix_i$和$\alpha_iy_i$，这里$\alpha_i=n_i\eta$，故$w,b$可表示如下：$$w=\displaystyle \sum^N_{i=1}\alpha_iy_ix_i,$$$$b=\displaystyle \sum^N_{i=1}\alpha_iy_i.$$

• 算法：

  • 输入：训练数据集$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N\}$，其中$i=1,2,3,..,N$；学习率$\eta(0<\eta\leq1)$

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

    1. $\alpha \leftarrow 0$， $b\leftarrow 0$
    2. 在训练集中选取数据$(x_i,y_i)$
    3. 如果$y_i(\displaystyle \sum^n_{j=1}\alpha_jy_jx_j\cdot x_i+b)\leq0$,$$\alpha_i\leftarrow\alpha_i+\eta.$$$$b=b+\eta y_i.$$
    4. 转至2直到没有误分类数据
  • 对偶形式中训练实例仅以内积形式出现，可以提前计算Gram矩阵$$G=[x_i\cdot x_j]_{N\times N}$$