概念学习和一般到特殊序

从特殊的训练样例中归纳一般函数是机器学习的中心问题。

概念学习： 给定某一类别的若干正例和反例，从中获得该类别的一般定义。概念学习也可以看作是一个搜索问题的过程，它在预定义的假设空间中搜索假设，使其与训练样例有最佳的拟合度。

多数情形下，为了高效的搜索，可以利用假设空间中一种自然形成的结构 —— 一般到特殊偏序结构。

简介

许多机器学习问题涉及到从特殊训练样例中得到一般概念。每个概念可被看作一个对象或事件集合，它是从更大的集合中选取的子集，或者是在这个较大集合中定义的布尔函数。

接下来需要考虑的问题是，给定一样例集合以及每个样例是否属于某一个概念的标注，怎么自动推断出该概念的一般定义。这一问题被称为 概念学习，或称从样例中逼近布尔值函数。

概念学习

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

概念学习任务

一般来说，任何概念学习任务能被描述为：实例的集合、实例集合上的目标函数、候选假设的集合以及训练样例的集合。

术语定义

概念定义在一个实例（instance）集合之上，这个集合表示为 $X$ 。

待学习的概念或函数称为目标概念（target concept），记作 $c$ 。一般来说，$c$ 可以是定义在实例集 $X$ 上的任意布尔函数，即 $c: X \rightarrow {0, 1}$ 。

学习目标概念时，必须提供一套训练样例（training examples），每个样例为 $X$ 中的一个实例 $x$ 以及它的目标概念 $c(x)$ 。对于 $c(x) = 1$ 的实例被称为正例（positive example），或称为目标概念的成员。对于 $c(x)=0$ 的实例为反例（negative example），或称为非目标概念成员。经常可以用序偶 $<x, c(x)>$ 来描述训练样例，表示其包含了实例 $x$ 和目标概念 $c(x)$ 。符号 $D$ 用来表示训练样例的集合。

一旦给定目标概念 $c$ 的训练样例集，学习器面临的问题就是假设和设计 $c$ 。使用符号 $H$ 来表示所有可能假设（all possible hypotheses）的集合，这个集合才是为确定目标概念所考虑的范围。通常 $H$ 依设计者所选择的假设表示而定。 $H$ 中每个的假设 $h$ 表示 $X$ 上定义的布尔函数，即 $h: X \rightarrow{0,1}$ 。机器学习的目标就是寻找一个假设 $h$ ，使对于 $X$ 中的所有 $x$ ，$h(x)=c(x)$ 。

归纳学习假设

机器学习的任务是在整个实例集合 $X$ 上确定与目标概念 $c$ 相同的假设 $h$ 。

归纳学习算法最多只能保证输出的假设能与训练样例相拟合。如果没有更多信息，我们只能假设，对于未见实例最好的假设就是与训练数据最佳拟合的假设。这是归纳学习的一个基本假设。

归纳学习机假设: 任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数。

作为搜索的概念学习

概念学习可以看作是一个搜索的过程，范围是假设的表示所隐含定义的整个空间。搜索的目标是为了寻找能最好地拟合训练样例的假设。

必须注意到，当假设的表示形式选定后，那么也就隐含地为学习算法确定了所有假设的空间。这些假设是学习程序所能表示的，也是能够学习的。

区分，实例空间和假设空间。假设集合中又区分语法不同的假设和语义不同的假设，参考书P17。

假设的一般到特殊序

许多概念学习算法中，搜索假设空间的方法依赖于一种针对任意概念学习都很有效的结构：假设的一般到特殊序关系。利用假设空间的这种自然结构，可以在无限的假设空间中进行彻底搜索，而不需要明确地列举所有的假设。

概念

更一般，P18。直观上的“比…更一般”的精确定义：首先，对 $X$ 中的任意实例 $x$ 和 $H$ 中的任意假设 $h$ ，我们说当且仅当 $h(x) = 1$ 时 $x$ 满足 $h$ 。

令 $h_j$ 和 $h_k$ 为在 $X$ 上定义的布尔函数。称 $h_j\ more\_general\_than\_or\_equal\_to\ h_k$ 记作 $h_j\geq_gh_k$，当且仅当

$(\forall\ x\in X)[(h_k(x)=1)\rightarrow(h_j(x)=1)]$

考虑一假设严格地比另一假设更一般的情形，我们说 $h_j$ 严格地 $more\_general\_than h_k$ （写作 $h_j >_gh_k$），当且仅当$(h_j\geq_gh_k)\bigwedge(h_k\ngeq_gh_j)$ 。还可以定义逆向的关系“比…更特殊”为 $h_j\ more\_specific\_than\ h_k$ 当$h_k\ more\_general\_than\ h_j$。

需要注意得失， $\geq_g$ 和 $>_g$ 关系的定义独立于目标概念。它们只依赖于满足这两个假设的实例，而与根据目标概念进行的实例分类无关。用形式化的语言来说，$\geq_g$ 关系定义了假设空间 $H$ 上的一个偏序（即这个关系是自反、反对称和传递的）。

$\geq_g$ 关系很重要，因为它在假设空间 $H$ 上对任意概念学习问题提供了一种有效的结构。概念学习算法将利用这一偏序结构有效地搜索假设空间。

FIND-S: 寻找极大特殊假设

如何使用 $more\_general\_than$ 偏序来搜索与训练样例相一致的假设呢？一种办法是从 $H$ 中最特殊假设开始，然后在该假设覆盖正例失败时将其一般化（当一假设能正确地划分一个正例时，称该假设覆盖该正例）。使用偏序实现的Find-S算法的精确描述如下：

• 将 $h$ 初始化为 $H$ 中最特殊假设

• 对每个正例 $x$

  • 对 $h$ 的每个属性约束 $a_i$

    • 如果 $x$ 满足 $a_i$ ，那么不做任何处理

    • 否则将 $h$ 中 $a_i$ 替换为 $x$ 满足的下一个更一般约束

• 输出假设 $h$

Find-S算法简单地忽略每一个反例。一般情况下，只要我们假定假设空间 $H$ 确实包含真正的目标概念 $c$ ，而且训练样例不包含错误，那么当前的假设 $h$ 不需要因反例的出现而更改。原因在于当前假设 $h$ 是 $H$ 中与所观察到的正例相一致的最特殊的假设，由于假定目标概念 $c$ 在 $H$ 中，而且它一定是与所有正例一致的，那么 $c$ 一定比 $h$ 更一般，而且目标概念 $c$ 不会覆盖一个反例，因此 $h$ 也不会。因此，对反例，$h$ 不需要作出任何更改。

Find-S 算法演示了一种利用 $more\_general\_than$ 偏序来搜索假设空间的方法。这一搜索沿着偏序链，从较特殊的假设逐渐转移到较一般的假设。

在每一步，假设只在需要覆盖新的正例时被一般化。因此，每一步得到的假设都是在那一点上与训练样例一致的最特殊的假设。

Find-S算法的重要特点是：对以属性约束的合取式描述的假设空间，Find-S保证输出为 $H$ 中与正例一致的最特殊的假设。只要正确的目标概念包含在 $H$ 中，并且训练数据都是正确的，最终的假设也与所有反例一致。

变型空间和候选消除算法

概念学习的另一种途径即候选消除（CANDIDATE-ELIMINATION）算法。它们解决FIND-S中的若干不足之处。FIND-S输出的假设只是 $H$ 中能够拟合训练样例的多个假设中的一个。而在候选消除算法中，输出的是与训练样例一致的所有假设的集合。令人惊讶的是，候选消除算法在描述这一集合时不需要明确列举其所有成员。这一归功于 $moew\_general\_than$ 偏序结构。在这里需要维护一个一致假设集合的简洁表示，然后在遇到新的训练样例时逐步精化这一表示。

然而，候选消除算法和FIND-S算法的实际应用都受到限制，因为它们在训练数据含有噪声时性能较差。

表示

候选消除算法寻找与训练样例一致的所有假设。首先，当一个假设能正确分类一组样例时，我们称这个假设是与这些样例一致（consistent）的。

定义：一个假设 $h$ 与训练样例集合 $D$ 一致，当且仅当对 $D$ 中每一个样例 $<x,c(x)>$ 都有 $h(x)=c(x)$ 。

$Consistent(h, D)\equiv(\forall<x,c(x)>\in D)\ h(x)=c(x)$

满足和一致：

• 满足: 一个样例 $x$ 在 $h(x)=1$ 时称为满足假设 $h$，不论 $x$ 是目标概念的正例还是反例

• 一致: 一个样例是否与 $h$ 一致则与目标概念有关，即是否 $h(x)=c(x)$

候选消除算法能够表示与训练样例一致的所有假设。在假设空间中的这一子集被称为关于假设空间 $H$ 和训练样例 $D$ 的变型空间，因为它包含了目标概念的所有合理的变型。

关于假设空间 $H$ 和训练样例集 $D$ 的变型空间，标记为 $VS_{H,D}$ ，是 $H$ 中与训练样例 $D$ 一致的所有假设构成的子集。

$VS_{H,D}\equiv \{h\in H|Consistent(h, D)\}$

列表后消除算法

表示变型空间的一种方法是列出其所有成员，这称为列表后消除(LIST-THEN-ELIMINATE)算法。

列表后消除算法

• 变型空间 $VersionSpace \leftarrow$ 包含 $H$ 中所有假设的列表

• 对每个训练样例 $<x, c(x)>$

  从变型空间中移除 $h(x)\neq c(x)$ 的假设 $h$

• 输出 $VersionSpace$ 中的假设列表

原则上，只要假设空间是有限的，就可使用列表后消除算法。

变型空间的更简洁表示

再次，变型空间被表示为它的极大一般的和极大特殊的成员。这些成员形成了一般和特殊边界的集合，这些边界在整个偏序结构中划分出变型空间。

候选消除算法通过使用极大一般成员 $G$ 和极大特殊成员 $S$ 来表示变型空间，通过使用特殊偏序结构来生成 $S$ 和 $G$ 集合之间的所有假设，列举出变型空间中所有成员。

关于假设空间 $H$ 和训练数据 $D$ 的一般边界(general boundary) $G$ ，是在 $H$ 中与 $D$ 相一致的极大一般成员的集合。

$G\equiv \{g\in H | Consistent(g, D) \bigwedge (\neg \exists g^{'} \in H)[(g^{'} >_g g) \bigwedge Consistent(g^{'}, D)] \}$

关于假设空间 $H$ 和训练数据 $D$ 的特殊边界 (specific boundary) $S$ ，是在 $H$ 中与 $D$ 相一致的极大特殊(maximally specific) 成员的集合。

$S\equiv \{ s\in H | Consistent(s, D) \bigwedge (\neg \exists s^{'} \in H)[(s >_g s^{'}) \bigwedge Consistent(s^{'}, D)] \}$

变型空间的确切组成：$G$ 中包含的假设，$S$ 中包含的假设以及 $G$ 和 $S$ 之间偏序结构所规定的假设。

定理：变型空间表示定理 令 $X$ 为一任意的实例集合， $H$ 为$X$ 上定义的布尔假设的集合。令 $c: X\rightarrow \{ 0, 1 \}$ 为$X$上定义的任一目标概念，并令$D$为任一训练样例的集合$\{<x,c(x)>\}$。对所有的 $X$，$H$，$c$，$D$ 以及良好定义的$S$和$G$：

$VS_{H,D} = \{h \in H | (\exists s \in S)(\exists g \in G) (g \geqslant_g h \geqslant_g s) \}$

候选消除学习算法

候选消除算法计算出的变型空间，包含$H$中与训练样例的观察序列一致的所有假设。开始，变型空间被初始化为$H$中所有假设的集合。即将G边界集合初始化为$H$中最一般的假设：

$G_0 \leftarrow \{<?,?,?,?,?,?>\}$

并将 $S$ 边界集合初始化为最特殊(最不一般的假设)：

$S_0 \leftarrow \{ \varnothing , \varnothing ,\varnothing ,\varnothing ,\varnothing ,\varnothing \}$

这两个边界包含了整个假设空间。因为 $H$ 中所有假设都比 $S_0$ 更一般，且比 $G_0$ 更特殊。算法在处理每个训练样例时，$S$ 和 $G$ 边界集合分别被一般化和特殊化，从变型空间中逐步消去与样例不一致的假设。在所有训练样例处理完后，得到的变型空间就包含了所有与样例一致的假设，而且只包含这样的假设。算法描述如下：

将 $G$ 集合初始化为 $H$ 中极大一般假设

将 $S$ 集合初始化为 $H$ 中极大特殊假设

对每个训练样例 $d$ ，进行一下操作:

• 如果 $d$ 是一正例

  • 从 $G$ 中移去所有与 $d$ 不一致的假设

  • 对 $S$ 中每个与 $d$ 不一致的假设 $s$

    • 从 $S$ 中移去 $s$

    • 把 $s$ 的所有的极小一般化式 $h$ 加入到 $S$ 中，其中 $h$ 满足

      • $h$ 与 $d$ 一致，而且 $G$ 的某个成员比 $h$ 更一般

    • 从 $S$ 中移去所有这样的假设：它比 $S$ 中另一假设更一般

• 如果 $d$ 是一个反例

  • 从 $S$ 中移去所有与 $d$ 不一致的假设

  • 对 $G$ 中每个与 $d$ 不一致的假设 $g$

    • 从 $G$ 中移除 $g$

    • 把 $g$ 的所有的极小特殊化式 $h$ 加入到 $G$ 中，其中 $h$ 满足

      • $h$ 与 $d$ 一致，而且 $S$ 的某个成员比 $h$ 更特殊

    • 从 $G$ 中移去所有这样的假设：它比 $G$ 中另一假设更特殊

正例使得变型空间的 $S$ 边界逐渐一般化，而反例扮演的角色恰好相反，使得 $G$ 边界逐渐特殊化。

关于变型空间和候选消除的说明

由候选消除算法得到的变型空间能够收敛到描述目标概念的假设的条件是：

• 在训练样例中没有错误

• $H$ 中确实包含描述目标概念的正确假设

如果训练数据中包含错误，那么算法肯定会从变型空间中删除正确的目标概念。空的变型空间表示 $H$ 中没有假设能够与样例一直。即便训练样例正确，也可能出现这种情况，这时说明，目标概念不能由假设表示方式所描述。

下一步需要什么样的训练样例

概念学习的最优查询策略，是产生实例以满足当前变型空间中大约半数的假设。这样，变型空间的大小可以在遇到每个新样例时减半，正确的目标概念就可在只用 $log_2 | VS$ 次试验后得到。

归纳偏置

一个有偏的假设空间

之前的假设空间表示方式，过于一般化。我们使学习器偏向于只考虑合取的假设，这里需要表示能力更强的假设空间。

无偏的学习器

为了保证目标概念在假设空间中，需要提供一个假设空间，它能表达所有的可教授概念。换言之，它能够表达实例集 $X$ 的所有可能子集。一般我们把集合 $X$ 的所有子集的集合称为 $X$ 的幂集。

无偏学习的无用性

归纳推理的一个基本属性：学习器如果不对目标概念的形式做预先的假定，它从根本上无法对未见实例进行分类。

候选消除算法能够从训练样例中泛华，其唯一的原因就是它是有偏的，它隐含假定了目标概念可以由属性值得合取来表示。

由于归纳学习需要某种形式的预先假定，或称为归纳偏执(inductive bias)，我们可以用归纳偏执来描述不同学习方法的特征。

现在来精确定地定义归纳偏执。这里要获取的关键思想在于，学习器在从训练样例中泛化并推断新实例的分类过程中所采用的策略。考虑一般情况下任意的学习算法 $L$ 以及为任意目标概念 $c$ 提供的任意训练样例 $D_c = \{<x, c(x)>\}$ 。训练过程结束后，$L$ 需要对新的实例 $x_i$ 进行分类。令 $L(x_i, D_c)$ 表示在对训练数据$D_c$ 学习后 $L$ 赋予 $x_i$ 的分类（正例或反例），我们可以如下描述 $L$ 所进行的这一归纳推理过程：

$(D_c \bigwedge x_i) \succ L(x_i, D_c)$

这里的记号 $y \succ z$ 表示 $z$ 从 $y$ 归纳推理得到。

由于 $L$ 是一归纳学习算法，则一般情况下 $L(x_i, D_c)$ 这一推论出的结果正确性无法证明；也就是说，分类 $L(x_i, D_c)$ 并非从训练数据集 $D_c$ 和新实例 $x_i$ 中演绎派生。问题是，需要在 $D_c \bigwedge x_i$ 上附加怎样的前提，以使 $L(x_i, D_c)$ 能演绎派生。我们定义 $L$ 的归纳偏置为这些附加前提的集合。更精确地说，我们定义 $L$ 的归纳偏置为前提集合 $B$ ，使所有的新实例 $x_i$ 满足：

$(B \bigwedge D_c \bigwedge x_i) \vdash L(x_i, D_c)$

这里的记号 $y \vdash z$ 表示 $z$ 从 $y$ 演绎派生（follow deductively，或 $z$ 可以由 $y$ 证明得出）。这样，我们定义学习器的归纳偏置为附加的前提集合 $B$ ，通过 $B$ 使归纳推理充分地由演绎推理来论证。

定义：考虑对于实例集合 $X$ 的概念学习算法 $L$ 。令 $c$ 为 $X$ 上定义的任一概念，并令 $D_c=\{ <x,c(x)> \}$ 为 $c$ 的任意训练样例集合。令 $L(x_i, D_c)$ 表示经过数据 $D_c$ 的训练后 $L$ 赋予实例 $x_i$ 的分类。$L$ 的归纳偏置是最小断言集合 $B$ ，它使任意目标概念 $c$ 和相应的训练样例 $D_c$ 满足：

$(\forall x_i \in X) [(B \bigwedge D_c \bigwedge x_i) \vdash L(x_i, D_c)]$

候选消除算法的归纳偏置：目标概念 $c$ 包含在给定的假设空间 $H$ 中。

一种算法如果有偏性越强，那它的归纳能力越强，可以分类更多的未见实例。