概念学习和一般到特殊序

定义

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

任务描述

• 实例集合（X）
• 实例集合上的目标函数（C）
• 候选假设的集合（H）
• 训练样例集合（D）

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

术语定义

1. 概念定义在一个实例集合之上，该集合表示为X。
2. 待学习的概念或函数称为目标概念。
3. 在学习目标概念时， 必须提供一套训练样例， 每个样例为X中的一个实例x以及它的目标概念值c(x)，对c(x)=1的实例被称之为正例或目标概念成员，相反对于c(x)=0的实例称为反例或非目标概念成员。通常用序偶<x, c(x)>来描述训练样例，表示包含了实例x和目标概念值c(x)。
4. 一旦给定目标概念c的训练样例集， 学习器面临的问题就是假设或者估计c。H表示所有可能假设的集合，H确定目标概念考虑的范围。通常H依设计者所选择的假设表示而定。H中假设h表示X上定义的布尔函数,即h:X->{0， 1}。机器学习的目标就是寻找一个假设h，使对于X中的所有x, h(x)=c(x)。

归纳学习假设

机器学习任的任务是在整个实例集合X上确定与目标概念c相同的假设h，然而我们对于c仅有的信息只是它在训练样例上的值，因此，归纳学习算法最多只能保证输出的假设能与训练样例相拟合。如果没有更多的信息，我们只能假定，对未见实例最好的假设就是与训练数据最佳你和的假设，这是归纳学习的一个基本假定。

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

作为搜索的概念学习

概念学习可以看做是一个搜索的过程，范围是假设的表示所隐含定义的整个空间

如果把学习看作是一个搜索为题，那么自然，对于学习算法的研究需要考查假设空间搜索的不同策略，特别引起我们兴趣的算法应该能有效地搜索非常大或无限的假设空间，以找到最佳拟合训练数据的假设。

假设的一般到特殊序

对X中任意实例x和H中任意假设h， 我们说x满足h当且仅当h(x)=1

任何被h₁划分为正例的实例都会被h₂划分为正例，我们就说h₂比h₁更一般

** more-general-than-or-equal-to的定义如下：**
令h_j和h_k为在X上定义的布尔函数。定义more-general-than-or-equal-to关系(≥_g )。h_j ≥ _gh_k当且仅当：
（∀x ∈ X）[(h_k(x)=1)->(h_j(x)=1)]

备注：严格一般为上面定义去除等于

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

1. 将h初始化为H中最特数的假设
2. 对每个正例x

• 对h的每个属性约束a_i, 如果x满足a_i，那么不做任何事，否则，将h中a_i替换为x满足的近邻的更一般约束

3. 输出假设h

Find-S算法存在的一些未解决的问题

• 学习过程是否手链到了正确的目标概念？虽然Find-S找到了与训练数据一致的假设，但没办法确定它否找到了唯一合适的假设，或是否还有其他可能的假设。我们希望算法知道它是否收敛到了目标概念，如果不能，至少要描述出这种不确定性。
• 为什么要用最特殊的假设。如果有多个与训练样例一致的假设，Find-S只能找出最特殊的。为什么我们偏好最特殊的假设，而不选最一般的假设，或者一般程度位于两者之间的某个假设。
• 训练样例是否相互一致？在多数实际的学习问题中，训练数据中常会出现某些错误或者噪声，这样的不一致的训练集会严重破坏Find-S算法，因为它忽略了所有的反例。我们期望的算法至少能检测出训练数据的不一致性，并且最好能容纳这样的错误。
• 如果有多个极大特数假设怎么办？在一些假设空间可能有多个极大特数假设。这种情况下，Find-S必须被扩展以允许其在选择怎样泛华假设的路径上回溯，以容纳目标假设位于偏序结构的另一分支上的可能性。更进一步，我们可以定义一个不存在极大特殊假设的假设空间，然而这是一个更理论性的问题而非实践问题。

变形空间和候选消除算法

候选消除算法中，输出的是与训练样例一致的所有假设的集合。且候选消除算法在描述这一集合时不需要明确列举其所有成员，这主要归功于more-general-than偏序结构，在这里需要维护一个一致假设集合的简洁表示，然后在遇到新的训练样例时逐步精化这一表示。

定义:一个假设h与训练样例集合D一致（consistent），当且仅当对D中的每个样例<x,c(x)>, h(x)=c(x)

** Consistent(h,D) Ξ (∀ <x, c(x)> ∈ D ) h(x) = c(x)**
一致与满足的区别：一个样例x在h(x)=1时称为满足假设h，不论x是目标概念的正例还是反例。然而，这一样例是否与h一致与目标概念有关，即是否h(x) = c(x)

定义：关于假设空间H与训练样例集D的变型空间(version space)，标记为VS_H,D,是H中与训练样例D一致的所有假设构成的子集。

列表后消除算法

1. 变型空间VersionSpace<-包含H中所有的假设列表

2. 对每个训练样例<x, c(x)>，从变型空间中移除所有h(x) ≠ c(x)的假设h
3. 输出VersionSpace中的假设列表

候选消除算法

候选消除算法与上面的列表后消除算法遵循同样的原则。然而，它