Skip to content

Concept Learning

概念学习的定义

给定的某一类别的若干正例和反例，从中获得该类别的一般定义。

概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。

概念学习任务

形式化表达

每个属性可有三种取值

  • "?" 表示任意本属性可接受的值。

  • 明确的属性

  • "\(\varnothing\)" 表示不接受任何值。

如最一般的假设：

\[ <?, ?, ?, ?, ?, ?> \]

最特殊的假设：

\[ <\varnothing, \varnothing, \varnothing, \varnothing, \varnothing, \varnothing> \]

术语定义

术语定义

  • 概念定义在 实例集 \(X\) 上.

  • 待学习的概念或目标函数被称为 目标概念(target concept, \(c\)). 可以是定义在实例集\(X\)上的任意布尔函数，即

\[ c: X \mapsto \{0,1\} \]
  • 训练样例(training examples): 每个样例为 \(X\) 中的一个元素 \(x\) 以及对应的目标概念 \(c(x)\)，记为 \(<x, c(x)>\). 若 \(c(x)=1\) 该样例被称为正例，是目标概念的成员。

给定训练样例集，我们可以学习或估计\(c\)。

术语定义

  • 所有可能假设集(all possible hypotheses) \(H\).

  • \(h\) 是 \(H\) 中的一个元素，表示 \(X\) 上定义的布尔函数 \(h:X\mapsto \{0,1\}\).

学习的目标就是，寻找一个 \(h\)，使得 \(\forall x\in X\), 有 \(h(x)=c(x)\).

  • 归纳学习假设: 对于未见实例最好的假设就是与训练数据最佳拟合的假设。任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见的实例中很好地逼近目标函数。

用搜索进行概念学习 | Find-S算法

从 \(H\) 中最特殊假设开始，然后在假设覆盖正例时将其一般化。

FIND-S算法

  1. 将 \(h\) 初始化为 \(H\) 中最特殊假设 (\(<\varnothing >\) 组成)

  2. 对每个正例 \(x\) in \(X\)

    对 \(h\) 的每一个属性约束 \(a_i\)

    Text Only
    if $x$ 满足

    $a_i$ continue;

else

    将 $h$ 中 $a_i$ 替换为 $x$ 满足的另一个更一般约束

  3. 输出 \(h\).

其实是利用 more_general_than 的偏序来搜索。每一步得到的假设都是那一点上与训练样例一致的最特殊假设。

  • 存在问题

收敛性： 无法确定是否拟合到目标概念 \(c\). 得到的只是能够拟合训练样例的多个假设的一个。

没有考虑满足条件的最一般假设和介于两者之间的其他假设。

算法不够robust，当样例中出现错误时，会严重破坏。

变形空间和候选消除算法(Candidate-Elimination)

该算法得到的是和训练样例一致的所有假设的集合。

优点: 依赖于 more_general_than 偏序结构，能够在描述时不用列举所有成员。

  • 变形空间: 与训练样例一致的所有假设的集合，即变形空间中任意一个假设都能覆盖所有的正例并排斥所有的反例。一般使用一个 极大一般假设(G) 和 极大特殊假设(S)，来形成一般和特殊边界，在整个偏序结构中划分出变形空间。

候选消除算法

  1. 初始化 G 为 "?", S 为 "\(\varnothing\)".

  2. 遍历训练样例 x in X:

    若为正例，则一般化 S;

    否则为负例，特殊化 G

注意点

  • 可以筛选样例中的错误： 给定足够样例，会收敛到空的变形空间。

  • 候选消除算法能够收敛到正确假设的前提: 样例没有错误， H 中确实包含描述目标概念的正确假设(目标概念不再假设空间内，即不能够由几个属性的合取，而只能是析取)。

归纳偏置

如果目标概念不在假设空间，那该如何解决? 如两个正例包含属性sky=sunny 和 sky=cloudy, 这时候训练得到的极大特殊假设是 sky=?，这样就会将 反例sky=rainy 判成正例。这个问题出现的原因在于我们的假设空间不够大，上述的极大特殊假设还是太一般了。

显然，需要一个假设空间，能够表达所有的 可教授概念, 即能够表达实例 \(X\) 所有可能的子集，把这些子集组成的集合称为 \(X\) 的幂集(power set)。

这就用到了下面的 归纳偏置。

当学习器去预其未遇到过的输入，会做出假设，学习算法的归纳偏置是这些假设的集合。

归纳偏置

  • FIND-S 算法的归纳偏置

目标概念在假设空间中；对于任何实例，若不符合最特殊假设，除非其为正例；

  • 候选消除算法的归纳偏置

目标概念包含在给定的假设空间内。

对于新实例做分类，或无法分类。

一个算法有偏性越强，则归纳能力越强，可以分类更多的未见实例。无偏的学习器无法对未见样例进行归纳。如果假设空间被拓展，实例集的幂集都有一个假设，则候选消除算法的归纳偏置消失。