感知机

感知机模型

  • 输入空间/特征空间：$\boldsymbol{x} \subseteq \boldsymbol{R}^n$
  • 输出空间：$y = {+1, -1}$
  • 感知机：
    $$f(x)=sign(w \cdot x + b)$$
    • $w$和$b$为感知机模型参数，$w$ 叫作权值，$b$ 叫作偏置
    • $sign$表示符号函数，即：
      $$sign(x)=\begin{cases}+1, \text{ } x \ge 0 \\ -1, \text{ } x < 0\end{cases}$$
  • 假设空间：定义在特征空间上的所有线性分类模型
    • ${f | f(x) = w \cdot x + b }$

感知机的学习策略

  • 从输入空间中任意一点到超平面的距离推导：
    • $\cfrac{1}{|w|_2}|w \cdot x + b|$
  • 对误分类的点来说：
    • $-y_i(w \cdot x_i + b) > 0$
  • 也即误分类的点到超平面的距离为：
    • $-\cfrac{1}{|w|_2}y_i(w \cdot x + b)$
  • 总距离为：
    • $-\cfrac{1}{|w|_2} \sum\limits_{x_i \in M} y_i(w \cdot x + b)$
  • 无需考虑$\cfrac{1}{|w|_2}$，即得到感知机学习的损失函数：
    • $L(w,b)=-\sum\limits_{x_i \in M} y_i(w \cdot x + b)$

感知机的学习算法

  • 原始形式：
    • $\min\limits_{w,b}L(w,b)=-\sum\limits_{x_i \in M} y_i(w \cdot x + b)$
    • 采样随机梯度下降SGD
      • $\triangledown_wL(w,b)=-\sum\limits_{x_i \in M}y_ix_i$
      • $\triangledown_bL(w,b)=-\sum\limits_{x_i \in M}y_ix_i$
      • 设置学习率为$\eta$，则：
        • $w \leftarrow w + \eta y_ix_i$
        • $b \leftarrow b + \eta y_i$
  • 收敛性证明：
    • …反正收敛
  • 当训练数据集线性可分时，感知机学习算法存在无穷多个解，其解由于不同的初值或不同的迭代顺序而可能有所不同