2.4. 感知机如何处理非线性可分集

预期收益

  • ★ PLA 实际使用时可能存在问题
  • ☆ pocket algorithm基本思想

时间成本

  • 阅读 01 分钟
  • 思考 05 分钟

2.4.1. PLA 实际使用时可能存在问题

PLA 收敛的前提假设是, 训练数据集线性可分, 实际使用中, 无法确定训练数据集是线性可分

  • 即使原始问题是线性可分, 但是采集的样本可能引入噪声, 这样在一定程度上训练数据集就有可能不适用PLA
  • 即使能够确认训练数据集是线性可分的, 由上一节给出了迭代次数的上限估计, 但是这种估计却引入了未知变量(目标函数的权重向量), 具体需要迭代多久不确定
  • 更多情况下, 无法确认数据集是线性可分的, 这时无论用PLA执行多久都无法达到终止条件

2.4.2. 度量超平面是否符合要求的标准

  • 感知机的目标就是找到超平面, 将训练数据集可以完美划分开来
  • 如果是不可分情况下, 我们也希望划分错误点的个数越少越好
\[\mathop{\arg\min}_{w}{\sum_{i=1}^N{\|y_n \neq sign(w \cdot x_n)\|}}\]

不幸的是, 上述问题为NP-hard, 这一类问题尚无法求其最优解

通常采用近似算法求其解, 其基本思想, 在当前状态下, 获取最优迭代策略

2.4.3. pocket algorithm

核心思想, 每迭代一步, 都能使得分错点的个数在减少

我们在PLA过程中, 每次找到误分点, 然后进行迭代. PLA可能有以下问题

  • 每次迭代只能保证, 当前误分类的点在迭代后更有可能分类正确

  • 无法保证, 迭代更新后, 错误分类点的个数减少

    每次迭代后, 用于误分类的点可能正确分类了, 但是其他正确的点也有可能分错了, 并且分错的个数可能大于1个

pocket algorithm 在PLA的基础做了调整

  • 权重迭代更新公式和PLA一致, 但增加每次进行迭代时有效性判断

    • 判断新的权重是否能够有效减少分类错误点的个数, 如果不能减少分类点的个数, 则放弃此次迭代
    • 重新选取误分类点, 计算新的权重, 依次类推
  • 增加选取错误分类点的随机性, 保证所有分类点都有相同的机会得到修正

  • 终止条件, 达到一定迭代次数终止