机器学习 1~4

1 引言

$W_i \rightarrow Samples + History \rightarrow V_{train} \rightarrow W_i’$

2 概念学习和一般到特殊序

2.4 Find-S

2.5 Candidate-Elimination

2.7 归纳偏置

2.7.3 无偏学习的无用性

学习器如果不对目标概念的形式做预先的假定,它从根本上无法对未见实例进行分类.

3 决策树学习

3.4 ID3

3.5 决策树学习中的假设空间搜索

3.6 决策树学习的归纳偏置

3.6.1 限定偏置和优选偏置

优选偏置: ID3的假设空间是完整的,偏置来自于搜索策略

限定偏置: 候选消除算法的假设空间是局限的,算法会遍历整个假设空间选取最佳

3.6.2 为什么短的假设优先

奥坎姆剃刀: 优先选择拟合数据的最简单的假设

一个困难: 为什么选取短描述的小假设集合,而非其他小假设集合

第二个困难: 不同的假设,大小是内部使用的特定表示决定的

3.7 决策树学习的常见问题

问题:

  • 决定决策树增长的深度
  • 处理连续值属性

3.7.1 避免过拟合数据

两类途径:

  • 及早停止树增长
  • 后修剪法 第二种方法更成功

使用什么准则来确定最终树的规模:

  • cross validation
  • 使用统计测试来估计扩展一个特定节点是否有可能改善性能
  • 使用一个明确的标准来衡量, 最小描述长度

第一种方法是最普遍的,他有两个主要变种:

错误率降低修剪: 删除此节点为根的子树, 验证集合的性能不比原来差->删除该节点.

规则后修剪:

  1. 推导决策树,允许过度拟合.
  2. 将根到叶子的路径转化成规则合集
  3. 通过删除任何能够导致估计精度提高的前条件来剪枝
  4. 按照估计精度,对剪枝过的规则合集排序

3.7.2 合并连续值属性

阈值

3.7.3 属性选择的其他度量标准

信息增益度量的内在偏置: 它偏袒具有多值的属性.

增益比率: 加入一个被称作分裂信息的惩罚项

基于距离的度量: 这个度量标准定义了数据划分间的一种距离尺度. 每个属性的评估根据他产生的划分与理想划分间的距离, 然后选择划分最接近完美划分的属性. ???

3.7.4 处理缺少属性值的训练样例

  • 赋予该属性最常见的值
  • 赋予其一个概率分布

3.7.5 处理不同代价的属性

目标: 优先选择低代价属性的决策树

方法: 信息增益除以属性的代价, 低代价的属性就会被优先选择

4 人工神经网络

4.4 传感器

4.4.2 感知器训练法则

  • 选取初值 $w_0, b_0$
  • 在训练集选取 $(x_i, y_i)$
  • 如果 $y_i (w \dot x_i + b) \le 0$

4.4.3 梯度下降和delta法则

如何样例不是线性可分时,它将不能收敛.

delta法则: 收敛到目标概念的最佳近似

4.5 多层网络和反向传播算法

4.5.1 可微阈值单元

sigmoid function

4.5.2 反向传播算法

4.6 反向传播算法的说明

4.6.1 收敛性和局部极小值

  • 冲量项
  • 随机梯度下降
  • 不同的随机初始化值

4.6.2 前馈网络的表征能力

  • 布尔函数: 任何布尔函数都可以被具有两层单元的网络准确表示
  • 连续函数: 每个有节的连续函数可由有一个两层的网络以任意小的误差逼近
  • 任意函数: 任意函数可以被一个有三层单元的网络以人已经堵逼近

4.6.3 假设空间搜索和归纳偏置

在数据点之间平滑的插值

4.6.4 隐藏层表示

隐藏层自动发现特征

4.6.5 泛化,过度拟合和停止判据

k-fold 交叉验证

4.7 举例: 人脸识别

4.8 人工神经网络的高级课题

4.8.1 其他可选的误差函数

  • 为权值增加一个惩罚项
  • 对误差增加一项目标函数的斜率或导数 ???
  • 使网络对目标值的交叉熵最小化
  • 权值共享

4.8.2 其他可选的误差最小化过程

我们不妨把权值更新方法看作是要决定这样两个问题:

  • 选择一个改变当前权值向量的方向
  • 选择要移动的距离

反向传播算法:

  • 方向是通过梯度的负值来选择的
  • 距离是通过学习率来决定的

线搜索(line search) ???

4.8.3 递归网络

4.8.4 动态修改网络结构 ???