5. 小结

5.1. 概要

预期收益

  • ★ 感知机是什么、PLA算法

时间成本

  • 阅读 03 分钟
  • 思考 10 分钟

5.2. 感知机是什么

  • 生活中加权平均抽象, 再和给定阈值进行比较, 主要是用来确定加权系数和阈值
  • 将特征空间中的点,正确分类的超平面
  • 感知机的假设空间\(\mathcal{H} = \{h(x) | h(x) = w \cdot x\}\)

5.3. PLA

  • 核心思想, 知错能改, 善莫大焉. 误分类点, 驱动算法
  • 迭代过程的几何意义 - 正样本误分类, 正样本和当前权重向量的夹角过大, 新的权重向量需要偏向误分类点, \(w_{t+1} = w_{t} + x_{n(t)}\) - 负样本误分类, 正样本和当前权重向量的夹角过小, 新的权重向量需要偏离误分类点, \(w_{t+1} = w_{t} - x_{n(t)}\)

5.4. PLA 收敛性前提条件

  • 数据集线性可分, 存在超平面可以将正负样本完美分开
  • 数据集线性可分条件下, PLA收敛
  • 迭代次数\(T \leq \frac{R^2}{{\rho}^2}\)
    • 样本范围(\(R\))越大, 迭代次数可能越大
    • 正负例越接近(\(\rho\)), 迭代过程有可能会出现震荡, 迭代次数可能越大

5.5. 非线性可分集合 pocket algorithm

  • PLA 存在问题
    • 无法预知, 训练集是否线性可分
    • 无法判断运行未结束的原因: 不可分造成的, 永远不可能结束; 还是迭代次数不够造成的
  • 误分类点数作为度量标准, 转化为最优化问题
    • \(\displaystyle\mathop{\arg\min}_{w}\sum_{n=1}^N{\|y_n \neq sign(w \cdot x_n)\|}\)
    • NP-hard问题
  • 贪心方法
    • 每次迭代, 保证误分类点减少
    • 随机选取误分类点
    • 达到一定迭代次数终止

5.6. 未涵盖内容

  • 迭代公式理论依据
    • 感知机的损失函数\(\displaystyle\min_{w}{loss(w)}=\min_{w}\sum_{x_i \in M}{-y_i w \cdot x_i}\)
    • 随机梯度下降法\(w_{t+1} = w_{t} + y_i x_i\)
  • 解不唯一性
    • 不同初始值
    • 误分类点的选取顺序
  • 感知机无法求解异或问题
  • 对偶问题求解
    • 解的最终结构\(w_{f} = \sum_{i=1}^N{\alpha_i y_i x_i}\)
    • 当学习率为1时, \(\alpha_i\)为第\(i\)个样本点误分类点的次数
  • 感知机和SVM的关系
    • SVM对假设空间进行了约束, 最小间隔最大化, 使得SVM解唯一