概念学习和一般到特殊序

50 阅读 0 评论 33 点赞

我是靠谱客的博主难过帆布鞋，最近开发中收集的这篇文章主要介绍概念学习和一般到特殊序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

机器学习的中心问题：从特殊归纳出一般。

概念学习：给定某一类别的若干正例和反例，从中获得该类别的一般定义。也可以看做是一个搜索问题，它在预定义的假设空间中搜索假设，使其与训练样例有最佳的拟合度。或者说是从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。

由？表示任意本属性可接受的值；
明确指定的属性值（如warm）；
由∅表示不接受任何值；

------------------------------------------------------------概念学习任务例子--------------------------------------------------------

已知：

实例集X：可能的日子，每个日子包含的属性有Sky，AirTemp，Humidity，Wind，Water，Forecast。

假设集H：每个假设描述6个属性的值约束的合取，约束可以为？，∅或者特定值。

目标概念c：EnjoySport：X->{0，1}

训练样例集D：目标函数的正例和反例，对于c(x)=0的实例称为反例，对于c(x)=1的实例称为正例，经常使用序偶<x,c(x)>表示训练样例，其中包含了实例x和目标概念值c(x)，如下表所示

--------------------------------------------------------------------------------------------------------------------------------------

Example Sky AirTemp Humidity Wind Water Forecast EnjoySport

1 Sunny Warm Normal Strong Warm Same Yes

2 Rainy Cold High Strong Cold Change No

--------------------------------------------------------------------------------------------------------------------------------------

求解：

H中的一假设h，使对于X中的任意x，h(x)=c(x)

--------------------------------------------------------------------------------------------------------------------------------------------

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

more_general_than_or_equal_to：令hj和hk为在X上定义的布尔函数，称hj more_general_than_or_equal_to hk (记作hj >=g hk)，当且仅当(∀x∈X)[(hk(x)=1)->(hj(x)=1)]。

Find-S：需找极大特殊假设。从H中的最特殊假设（即范围最小的）开始，然后再该假设覆盖正例失败的时候将其一般化（即将范围扩大，当一假设能正确划分一个正例的时候，称该假设“覆盖”该正例），具体算法如下

1.将h初始化为H中最特殊的假设

2.对每个实例x

对h的每个属性约束ai

如果x满足ai

那么不做任何处理

否则将h中ai替换成满足x的另一个更一般的约束

3.输出假设h

Find-S演示了一种利用more_general_than偏序来搜索假设空间的方法。这一搜索沿着偏序链，从较特殊的假设逐渐转移到较为一般的假设。其重要特点是：对以属性约束的合取式描述的假设空间，Find-S保证输出H中语正例一致的最特殊的假设。只要真确的目标概念包含在H中并且训练数据都是正确的，最终的假设也与左右的反例一致。

候选消除算法：Find-S输出的假设只是H中能够拟合训练样例的多个假设中的一个。而在候选消除算法中，输出的是与训练样例一致的所有的假设的集合。