哈工大人工智能原理习题homework-3

1、人工智能原理 练习题-3教科书当中的某些章节。对于加星号的习题，应该编写程序来完成。5 章 不确定性推理根据基本原理证明：P (a | ba )=1。使用概率公理证明：对于任何离散随机变量的概率分布，总和等于1。这个问题涉及原子事件的性质：证明所有原子事件的析取在逻辑上等价于true（）证明任何命题合法等价于蕴涵其真值的原子事件的析取。考虑从一副标准的52 张纸牌（不含大小王译者注）中分发每手5 张牌的扑克牌域。假设发牌人是公平的。在联合概率分布中共有多少个原子事件（即，共有多少种5 张手牌的组合）？每个原子事件的概率是多少？拿到大同花顺（即同花的 A、K、Q、J、10译者注）的概率是多少？四

2、同张（4张相同的牌，分别为4 种花色译者注）的概率是多少？在一年一度的体检之后，医生告诉你一个好消息和一个坏消息。坏消息是你在一种严重疾病的测试中结果呈阳性，而这个测试的精度为 99%（即当你确实患这种病时，测试结果为阳性的概率为 0.99，而当你未患这种疾病时测试结果为阴性。好消息是，这是一种罕见10000 1 例。为什么“这种病很罕见”对于你而言是一个好消息？你确实患有这种病的概率是多少？在保持某些一般背景证据固定的上下文中，而不是完全没有任何消息的情况下，考虑一些特定命题的结果经常是相当有益的e：证明乘法规则的条件化版本：P（X，Y|e）=P(X|Y,e)P(Y|e)证明公式（13.10

3、）中的贝叶斯法则的条件化版本。证明语句P(A,B|C)=P(A|C)P(B|C) 与语句 P(A|B,C)=P(A|C)，以及P(B|A,C)=P(B|C) 都是等价的。n 个无偏差硬币的袋子，并且告诉你其中n-1 个硬币是正常的，一面1 枚硬币是伪造的，它的两面都是正面。假设你把手伸进口袋均匀随机地取出一枚硬币，把它抛出去，并发现硬币落地后正面朝上。那么你拿到伪币的（条件）概率是多少？假设你不停地抛这枚硬币，拿到它之后一共抛了k 次而且看到 k 次正面向上。那么现在你拿到伪币的概率是多少？k k 次抛FAK（伪造NORMA（正常这个过程发生错误的（无条件）概率是多少？这道习题研究条件独立性关

4、系对概率计算中所需信息量的影响方式。假设我们希望计算P(h|e1,e2)，而我们没有任何条件独立性的信息。下面哪组数据足以完成计算？(i) P(E1,E2)，P(H)，P(E1|H)，P(E2|H)(ii) P(E1,E2)，P(H)，P(E1,E2|H)(iii) P(H)，P(E1|H)，P(E2|H)1212假设我们已知对于H，E ，E 的所有取值都有 P(E |H ,E )= P(E |H)。上面的这3 1212假设X，Y，Z 3 个布尔随机变量。将其联合概率分布P（X,Y,Z）8 个条目依次编号为a h。把语句“X 与Y 关于给定的Z 条件独立”表达为与a h 相关的一组公式。其中有

5、多少个不冗余的公式？1（改编自Pearl（198）假设你是雅典一次夜间出租车肇事逃逸的交通事故的目击者。雅典所有的出租车都是蓝色或者绿色的。而你发誓所看见得肇事出租车是蓝色的。大量的实验表明，在昏暗的灯光条件下，对于蓝色和绿色的区分的可靠度为 75%。有可能据（和命题“肇事车看起来是蓝色的）1（改编自Pear（198）3个囚犯，和，被关在各自的狱室里。大家都和中的一个人，让他知道明天早上他就会被赦免把赦免消息告诉了。那么，根据以上已知的信息，被处死的几率有多大？（用数学方法解答这个问题，而）贝叶斯网络部分考虑下图所示的汽车故障诊断网络：a: IcyWeathrestarterMotor 对网络

6、进行扩展b: 为所有的节点指定合理的条件概率表c: 8 个布尔节点的联合概率分布中包含多少个独立的数值?d: 在你的网络的条件概率表里一共包含多少个独立的数值?e: starts 的条件概率表可以描述为一个噪声与（noisy-and ）分布。请使用一种通用的方式对其进行定义，并分析它与噪声或(noisy-or)分布的关系。BatteryBatteryRadioIgnitionGasstartsMoves上图中每个变量都是布尔型并且其取值为true 时表示汽车的相应部件正常或者状态正常.Battery电池Radio 车内收音机Ignition 电子打火Gas 油箱状态Starts发动机能够发动M

7、oves汽车能够正常运行 A(报警器响)F (报警器 出A故障)FG(测温仪出故障)G(测温仪读数)T（核反应堆的核心温度）为这个问题域构造一个贝叶斯网络，假设当核心温度太高时测量以更容易出故障。你得到的贝叶斯网络是多数结构吗G T 都只有两种读数，正常/偏高; 当温度仪正常工作时他给出正常的读数的概率为x,出现故障时给出正确的读数的概率为y,给出与G 相关联的条件概率表假设报警器能正常工作-除非它坏了,这种情况下他不会发出报警声.给出与 A 相关联的条件概率表.假设报警器和测温仪都能正常工作,并且报警器发出了报警声.根据网络中的各种条件概率,计算核反应堆核心温度过高的概率表达式的值.两个来自

8、世界上不同地方的宇航员同时用他们自己的望远镜观测了太空中某个小区域内N,记者两个宇航员的观测结果分别为M M .通常,1 颗12的误差,发生错误的概率e 很小. 而每台望远镜可能发生(发生的概率f 更小)对焦不准确(分别F F1),3 颗甚至更多的恒星(或者说,N 3 时,连一颗和星都观测不到).考虑下图中所示的三种贝叶斯网络结构.这三种网络哪个是对上述信息的正确的 (但不一定是高效的) 表示;那一种网络结构是最好的?请给出解释c. 0,1,2,3,4时,写出一个关于P(M| N)的条件概率表.概率分布11表中的每一个条目都应该表达为e 的参数和/f 的一个函数假设 MM 3 .如果我们假设N

9、 取值上没有先验概率的约束,可能的恒星数目是12多少?在这些观测的结果下,最可能的恒星数是多少?解释如何计算这个数目,或者,如果不能计算,解释还需要附加什么信息及它将如何影响结果.F1F2M1F1F2M1M2NF1NF2M1M2M1M2NF1F2考虑上图M1M2NF1F2 0,1,2,3,4,3 描述的符号条件概率表.使用枚举算法,计12算概率分布P(N | M 2,M2)12这道习题是关于例题中的变量消元算法的:对如下查询应用了变量消元算法P(Burglary | JohnCalls true,MaryCalls true)执行必要的计算,并检验计算结果的正确性.统计计算中算术运算次数,将其

10、与枚举法完成的运算次数进行比较.假设贝叶斯网络具有链式结构,即由一个布尔随机变量序列X , X,., X构成;12n其中Parents(X ) X对于i 2,3,.,n.请问通过枚举法计算P(X| X)true 的复ii11n杂度是什么?用变量消元算法呢?证明对于任何排序与网络结构一致的变量,运行多树结构网络上的变量消元算法的复杂度与树的规模呈线性的关系。研究通用贝叶斯网络中精确推理的复杂度a, 3-sat 问题都可以归约到为了表示这个特定问题而构造的贝叶斯网络的精确推理问题,并且因此贝叶斯网络的精确推理是 NP 难题.提示:考虑一个网络,每个命题符号用一个变量来表示,每个句子用一个变量来表示

11、,以及每个子句合取式用一个变量来表示.b, 3-sat 问题中的可满足复制的个数进行统计是#P 完全的(个数 完全的)证明贝叶斯网络的精确推理至少和这个问题一样难.73 支足球队A,B,和C 两两之间各赛一场.每场在两队之间进行,结果对每支球队而言可能是胜,负,平.每支球队都有确定但未知的实力-表示为一个0 到3 之间的整数而每场的比赛结果以某种概率取决于两个球队之间的差距.A, 构造一个关系概率模型来描述这个阈,并为所有必要的概率分布给出数值.B, 构造等价的贝叶斯网络.C, 假设在前两场比赛中A B,C 战平.选择使用一种精确推理算法,3 场比赛结果的后验概率分布.D, 假设联赛中总共有

12、n 支球队,并且我们已经知道了除最后一场比赛外的所有比赛结果.现在要预测最后一场比赛的结果,其计算复杂度随n 如何变化?E, 研究将马尔可夫联蒙特卡洛方法应用于这个问题.在实际运算中算法的收敛速度如何?算法的规模扩展性能如何?6 章 机器学习方法针对下述问题画出其决策树：当十字路口的信号灯变为绿色时，判断是否向前走。我们从不沿着决策树中的同一条路经对某属性进行两次测试。为什么？假设我们从决策树中生成一个训练集，并对该训练集应用决策树学习方法。当训练集规模增加到无限的时候，学习算法最终是否能够返回正确的决策树？为什么？25 个实例的数据集。你计划采用逐一删除交叉验证。作为基准，你使用简单的多数分

13、类器进行实验（ 多数分类器是给定一个训练集，不考虑输入，总是输出在训练集中占多数的类别）你期望多数分类器的逐一删除交叉验证的评分达到50%，但是令你惊讶的是，其评分为0。你能解释这是为什么吗？假定某个学习算法试图在实例的分类实际上是随机的情况下，找到一个一致假设。现在有n 2 n个可能实例的集合中抽取出来的。计算在数据中0.5 之前，所需在的实例数目。考虑一个使用在M 个假设具有误差 M 和 表示的集体算法的误差公式，并对M =5，10，以及20 而 =0.1，0.20.4 的情况分别对公式求值。如果去掉独立假定，集体误差是否可能差于 ？本习题关注于决策表的表达能力（第18.5 节。证明决策表

14、能够表达任何布尔函数，如果测试的规模没有限制的话。证明如果每个测试可以包含至多 k 个文字，那么决策表能够表示任何可以用深度为k 的决策树表示的函数。考虑一个任意的贝叶斯网络、该网络的完全数据集，以及数据集与网络相关的似然率。 计算参数值的最大似然。考察下面的样本集，每个样本有6 个输入和一个目标输出。I111111110000000I200011001101011I311101001100011I401001001011101I500110110110010I600010101101110T11111101000000在这些数据上运行感知器学习规则，说明最终的权值。运行决策树学习规则，说明得

15、到的决策树。评论你的结果。考虑这样一个问题：要将 N 个数据点通过一个线性分类器分成正例和反例。显然，对d=1 N=2 个点，这总是可以做到的，无论点是如何进行标记的以（除非这些点落在相同的位置。说明对于在一个维度d=2 的平面上的N=3 个点，这总是可以做到的，除非它们是共线的。说明对于在一个维度d=2 的平面上的N=4 个点，这不是总能做到的。说明对于在一个维度d=3 的空间上的N=4 个点，这总是可以做到的，出非它们是共面的。说明对于在一个维度d=3 的空间上的N=5 个点，这不是总能做到的。有能力的学生可以试着证明：在一般位置上的（而不是）个点在维 空间上是线性可分的。由此可得，维线性

16、半空间的VC 维（参见第十八章）是N。20.1 中使用的数据可以视为由h54 个假设的每一个，分别100 的数据集，并为P(hi|d ,L ,d1P(Dm1 lime |d1,L ,dm画出相应的图。评价一下你的结果。重复上一个习题，这次画出P(Dm1 lime | hMAPP(Dm1 lime |hML的值。设Ann 对樱桃和酸橙糖果的效用值分别是cA 和lA ，而Bob 的则是cB 和lB （但是只要Ann 打开了一颗糖果的包装，Bob ）可以想到，如果Bob 比Ann 更喜欢酸橙糖，那么对于 Ann 来说聪明的做法是只要她足够确信一包糖果是酸橙味的，就把它卖给Bob。另一方面，如果Ann

17、 在这个过程中打开太多的糖果，这包糖的价值就损失了。讨论如何确定卖这包糖果的最优点的问题。给定第 20.1 节中的先验分布，确定最优过程的期望效用。两个统计学家去看病，得到了相同的诊断：40%的几率是一种致命疾病 A，60%的几率是可能致命疾病B。幸运的是，抗A 和抗B 的药都不贵，100%有效，并且没有副作用。统（狂热的贝叶斯论者）会怎么做？总是用最大似然假设的第二个统计学家呢？B B B，有同样的可能性并且都可以同样地用抗B 3 个假设，两个统计学家会怎么做呢？解释如何把 boosting 考虑有m 个数据点(x , y y （20.5）x 集jjjj合生成的。找出当数据达到最大条件对数似

18、然时 ， ，和 的值。127 章 自然语言理解简介DCG 符号，为一种语言编写语法，这种语言正如同E1，除了它要加强语句的主语和动词之间的一致性，从而不会生成类似“ I semells the wumpus”的语句之外。增强E1的语法，使其能够处理冠词-名词一致性问题。也就是说，确保“agents”是一个NP，而“agent”和“an agents”都不是。Java （或者任何其它你所熟悉的计算机语言和英语的主要区别，评论每种 情况下的“理解”问题。首先可以考虑如下方面：语法、句法、语义、语用、合成性、上下文 依赖性、词汇歧义、句法歧义、指代发现（包括代词、背景知识以及“理解”意味着什么。下列

19、哪个是引入准逻辑形式的原因？为了使书写简单合成语法的规则更容易。为了扩展语义表示语言的表达能力。为了能够用简洁的形式表示量词作用范围的歧义（除了其它歧义以外。为了使语义排歧更容易。用本章中的语法给出下列语句的语义解释：It is a wumpus.The wumpus is dead.The wumpus is in 2,2.简单地用x xWumpuses 作为“It is a wumpus”的语义解释是好主意吗？考虑可替It was a wumpu本习题是有关非常简单语言的语法的。写出语言anbn 的上下文有关语法。写出回文语言（即所有字符串的后半部分是前半部分的逆串）的上下文有关语法。写出复制语言（即所有字符串的后半部分与前半部分相同）的上下文有关语法。PronounsomeonePreptoVwalkedDettheAdvPronounsomeonePreptoVwalkedDettheAdvslowlyNounsupermarket个语法中的哪个与该词典结合能够产生上述语句？画出相应的句法分析树。（：B：（：SNP VPSNP VPSNP VPNP PronounNP PronounNP PronounNP Article NounNP NounNP Article NPVPVP PPNP Article NPVPVP A