人工智能导论第三次作业

人工智能导论第三次作业 2003011628李波睿自36班

1 人工智能导论第三次作业

5.1给出三种机器学习方法适合的计算机应用，三种不适合的计算机应用，（请不要使用课上

或者阅读材料中给出的例子），挑选一些本书未提到的应用并对每个应用来评价。

解：三种机器学习方法适合的计算机应用：

① 保险业中的汽车修理费用程序

这是个机械式学习器的例子，程序输入的是被损坏的汽车的描述，包括制造厂家、汽车

种类、损坏纪录等的一个表，程序的输出是查找纪录得出的保险公司应付的修理费用。如果

之前没有类似的纪录，就使用保险公司的赔偿规则估算出一个修理费用，然后保存结果。

② 机器人AI的学习提高

机器学习可以应用到机器人领域，通过强化学习，可以实现寻路导航控制、多足机器人

的协调动作以及机器人足球中的分布式智能控制等等。在平时的PC游戏中也有类似的体会，

和同一难度的电脑对手交手几次之后就会发现它变得更智能了。

③ 计算机反病毒、木马

与垃圾邮件类似，病毒、木马这类特殊的软件程序的构成以及行为特征都是有关联和内

在规律的，通过大量实例的学习，可以提高反病毒软件的智能性和预防能力。

三种机器学习方法不适合的计算机应用：

① 人类语言的内涵应用

这里指的不是OCR、语音识别等，而是类似诗歌创作这样的内涵应用，例如：写命题

作文、作曲写词、读书评论等等。特别是对于汉语这样包罗万象的语言，我认为不适合。

② 模拟人类的心理和情绪

例如希望计算机通过机器学习方法的训练，在得到某件事情的描述之后，做出相应的悲

伤、喜悦、兴奋等反应；或者是希望计算机可以做心理咨询师。因为人类的心理和情绪就是

很个性化的东西，人与人差异很大，而且一件事对人的影响随周围环境、当事人心情处境的

不同而剧烈变化，因而不适合。

③ EDA制作电路板时的自动布线

电路板在布线时需要考虑的因素众多，而且会因为实际需要进行必要的加强和简化，不

同的应用场合差异较大。计算机做到连通还有可能，但是要得到好的布线结果就不适合了。

5.2挑选一些本书未提到的学习任务。写一段话非正式地加以描述。再尽可能精确地描述出

它的任务、性能衡量标准和训练经验。最后，给出要学习的目标函数和它的表示。讨论这个

任务设计中考虑的主要折中。

解：1、RSS阅读器给特定用户提供最感兴趣的新闻

网络上每天都会有海量的新闻信息，如果靠人自己去找有用的信息，会花费很多时间。

RSS技术使得网站可以把信息“推”到用户面前，但同样存在着信息冗余的问题。这样就希

望RSS阅读器可以通过学习，把用户最感兴趣的新闻提供给用户，这样可以节省大量的时

间和网络流量。

任务T：每天早晨在用户开机联网后，提供他/她最感兴趣的RSS新闻。

性能标准P：在每天提供的RSS新闻中用户感兴趣的数量百分比。

训练经验E：以往每天的RSS新闻信息，用户标注了感兴趣或者不感兴趣。

目标函数：:VRSSNews→ℜ

目标函数的表示：0()

ii

iVbwwx∧=+∑，其中ix为用户感兴趣的各个关键词在该新闻人工智能导论第三次作业 2003011628李波睿自36班

2 中的出现次数。若ix出现在感兴趣的新闻中，则iw为正值；若ix出现在不感兴趣的新闻中

则iw为负值。

即目标函数用ix的线性组合来表示，函数值大于0表示用户感兴趣，小于0表示用户

不感兴趣。iw为权，由学习算法来确定；关键词的个数和具体是哪些词也需要学习算法来

确定。

任务设计中考虑的主要折中有：

① 考虑到每个人的兴趣差别很大，所以任务只要求针对特定用户，这样便于设计。

② 用户感兴趣的新闻的特征表示可以有许多的方式，例如Markov链、关键词等等。

这里选择的是关键词的形式，形式简单但也使得错误率上升。

③ 目标函数的表示形式可以有多种选择，例如Bayes方法、多项式、查表等等，这里

简化讨论，选择的是n个参数的线性函数，虽然简单但是表现力一般。学习算法也可以有线

性规划、梯度下降等等选择，这里选择的是梯度下降的方法。

④ 在实际应用中，用户对各条新闻的感兴趣的程度是比较模糊的，由感兴趣的程度之

分。这里只是简单的分为感兴趣和不感兴趣两类，并不能完整地表达用户的意见。

2、垃圾邮件过滤

常用的邮件客户端和WebMail基本上都具备了反垃圾邮件的功能，但依然防不胜防，

很令人头疼。希望邮件过滤程序可以通过学习提高垃圾邮件的识别成功率，同时减少把正常

邮件错判成垃圾邮件的情况。

任务T：对收到的邮件做垃圾邮件过滤。

性能标准P：正确识别垃圾邮件的百分比和错判正常邮件的百分比的加权平均。

训练经验E：经过用户确认之后的垃圾邮件箱与收件箱里的邮件。

目标函数：:VMails→ℜ

目标函数的表示：0()

ii

iVbwwx∧=+∑，其中ix为垃圾邮件中经常出现的各个关键词

在该邮件中的出现次数；

即目标函数用ix的线性组合来表示，函数值大于0时该邮件为垃圾邮件，小于0时为

正常邮件。iw为权，由学习算法来确定；关键词的个数和具体是哪些词也需要学习算法来

确定。

任务设计中考虑的主要折中有：

① 垃圾邮件的特征表示可以有许多的方式，例如题目与内容的关联程度、收发件人信

息等等。这里选择的是关键词的形式，简单但容易出错。比如垃圾邮件中“开发票”的内容

很多，但是如果一封正常邮件也使关于公司开发票的，就很有可能被错判。

② 目标函数的表示形式可以有多种选择，例如Bayes方法、多项式、查表等等，这里

简化讨论，选择的是n个参数的线性函数，虽然简单但是表现力一般。

③ 学习算法也可以有线性规划、梯度下降等等选择，这里选择的是梯度下降的方法。

④ 在实际应用中，各封邮件的重要性是有很大区别的，但在设计时实际上是把所有的

邮件都看作同等的重要，没有考虑邮件的重要性权值分配。 人工智能导论第三次作业 2003011628李波睿自36班

3 6.1 解释为什么EnjoySport 学习任务的假设空间的大小为973。如果增加一属性

WaterCurrent，可取值Light、Moderate 和Strong，那么可能的实例数和可能的假设数将会

增加多少？推广到一般情况，增加一新属性A，有k 种取值，实例数和假设数将会增加多

少？

解：讲义中的属性Sky 有3 种可能的值，而AirTemp、Humidity、Wind、Water 和Forecast

都只有两种可能值，再加上每种属性都都可以取“?”和“∅”，那么在假设空间H中，有

5×4×4×4×4×4 = 5120 种不同的假设。但是可以注意到包含有∅符号的假设代表的是空实例

集合，即它们将每个实例都分类为反例，()(()0)xXhx∀∈=。因此，不同的假设其实只有

1 + 4×3×3×3×3×3=973个。所以EnjoySport 学习任务的假设空间的大小为973。

如果增加一属性WaterCurrent，可取值Light、Moderate 和Strong，那么可能的实例数

变为3×2×2×2×2×2×3=288种，增加了192种；可能的假设数变为1+4×3×3×3×3×3×4=3889

个，增加了2916个。

推广到一般情况，增加一新属性A，有k 种取值，实例数变为3×2×2×2×2×2×k=96k种，

增加了96*(k-1)种；假设数变为1+4×3×3×3×3×3×(k+1)=(972k+973)个，增加了972k个。

6.4 假定一实例空间包含x、y平面中的整数点，假设集合H为矩形集，也就是说，假设

的形式为axb≤≤，cyd≤≤ 其中a、b、c、d为任意整数。

(a) 考虑对应于下图所示正例(+)和反例(－)集合的变型空间，它的S 边界是什么？写出

其中的假设并在图中画出。

(b) 变型空间的G 边界是什么，写出其中的假设并在图中画出。

解：S边界是{46,35}xy<≤≤≤≤>；

G边界是{38,27}xy<≤≤≤≤>。

如下图所示：

(c) 假定学习器可提出一个新实例(,)xy，并要求施教者进行分类。试给出一个查询，

无论施教者怎样分类都能保证减小变型空间。再给出一个不能保证的查询。 人工智能导论第三次作业 2003011628李波睿自36班

4 解：能保证减小变型空间的一个查询：(7,4)，即边界S与G之间的点。

不能保证减小变型空间的一个查询：(10,1)，即边界S之内，G以外的点。

(d) 作为施教者，如果想让学习器学习一特定的目标概念(如3≤ x ≤5，2≤ y ≤9)，

为使候选消除算法完全学习到目标概念，需要提供的的训练样本数目最小是多少?

解：需要提供的的训练样本数目最小是6，其中2个正例，4个反例。

6.5 请看以下的正例和反例序例，它们描述的概念是“两个住在同一房间中的人”。每个训

练样本描述了一个有序对，每个人的属性有性别、头发颜色（black、brown 或blonde）、身

高（tall、medium 或short)以及国籍（US、French、German、Irish、Indian、Chinese 或Portuguese）。

+ <， >

+ <， >

- <， >

+ <， >

考虑在这些实例上定义的假设空间为：所有假设以一对4 元组表示，其中每个值约束

与EnjoySFort 中的假设表示相似，可以为：特定值、“？”或者“∅”。例如，下面的假设：

< >它表示了所有这样的有序对：第一个人为高个男性（国

籍和发色任意），第二个人为法国女性（发色和身高任意）。

(a) 根据上述提供的训练样本和假设表示，手动执行候选消除算法。特别是要写出处理了每

一个训练样本后变型空间的特殊和一般边界。

解：第1个和第2个训练样本： S0: {<,>}

S1: {<，>}

S2: {<，>}

G0, G1, G2: {<,>}

训练样本：

1、<，>+

2、<，>+

第3个训练样本：

S3: {<，>}

G2: {<,>}

训练样本：

3、<，>-G3: {<,> ; <,>}

第4个训练样本：