感知机模型

感知机模型

• 定义：假设输入空间（特征空间）是\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}