5. 小结
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解唯一