2014 秋季学期硕士生《人工智能原理》试题题签 2014 年 12 月 31 日 注意：所有答案都写在答题纸上，请在答题纸上标清题号再写答案。 1．（7 分）分别用框架结构和语义网络表示下面的命题句子。 哈尔滨工业大学是一所著名的高等学府，设有本科生院、研究生院、成教学 院和国际教育学院，所有学院的本科生都必修计算机导论，战老师是教学名名师， 他主讲计算机导论这门课。 2．（7 分）如图 1 所示为一棵博弈树，假设 A 在极大值层，请描述 α-β 剪枝 的全过程并标注 A~K 结点的变化情况（注：被剪枝掉的节点不需标注）。 图 1 一棵博弈树 3．（8 分）对于图 2 所示的八数码问题，定义启发函数为 f(x)=d(x)+w(x)，其 中 d(x)表示搜索树的深度；h(x)是启发函数，表示估计放错位置的数字的个数， 请画出这棵搜索树并给出全部扩展节点的 f 值。 2 8 3 1 6 4 7 5 1 2 3 8 4 7 6 5 初始状态 目标状态 图 2 八数码问题 第 1 页 共 3 页 

4．（8 分）有三名警察押解三名犯人过河，只有一条船，每次最多载两人。 如果在任何一边岸上犯人数大于警察数且警察数不为零，则犯人就会对警察不 利。如果每个警察和每个犯人都能划船，（假设不存在犯人划船逃跑的情形）请 设计一种过河方法，且： （1）确定一种搜索方法； （2）按你设计的搜索方法写出过河规则； （3）画出搜索图。 5．（共 15 分）假设有如下一个多连通贝叶斯网络，其中 F 是证据节点，给定的 状态为 F=T，C 是查询节点。其条件概率表如节点旁所示，c|a 表示在 A=T 条件 下 C=T，f|d,e 表示在 D=F 和 E=T 条件下 F=T。 b|a 0.7 b|a 0.2 B a 0.5 A c|a 0.3 C c|a 0.8 d|b,c 0.7 D d|b,c 0.2 d|b,c 0.4 E e|c 0.9 e|c 0.2 f|d,e 0.3 d|b,c 0.7 F f|d,e 0.8 f|d,e 0.7 f|d,e 0.2 （1）（6 分）考虑似然加权采样算法，如果给定事件 A=T，试就算法中调用的 Weighted-Sample 函数写出各节点的状态，节点状态向量按照 A 到 F 的次序，同 时给出 w 的值。该函数返回后，W 向量结果是什么？随后再给定 A=F，也依次 写出状态向量的值、w 值及 W 向量结果。 （2）（3 分）查询节点 C 的马尔科夫覆盖包括哪些节点？按字母序写出。 （3）（6 分）考虑吉布斯采样算法，如果分别给定贝叶斯网的 2 个节点向量状态 (按照 A→F 次序)如下：(注意 F 为证据变量)和， 试在 for 循环中各进行一次采样，分别给出新的非证据变量状态值和 N 向量的值。 6．（5 分）设在一个贝叶斯网络中，糖果包装节点为支配节点，包装颜色为红色 (r)和绿色(g)2 种，为红色的概率是；被其支配的节点为口味节点，分为樱桃口 味(c)和柠檬口味(l)2 种。现在增加一个被支配的节点为空心节点，分为有空心(h) 第 2 页 共 3 页 

和无空心(n)2 种，且数据总量 N 不变。增加节点之前和之后网络的形式分别如 图(a)和(b)所示。试列出前后 2 个 log 似然计算公式，公式中要恰当地使用前述符 号，并通过公式说明：数据似然性 L 在节点增加之后不会降低。注意：L 指的是 似然概率取负 log。 图(a) 图(b) B B F F H 7．（6 分，每题 3 分）回答下述 2 个问题： （1）试举例说明，EM 算法尽管在初始时为所求解的概率设置了统一值，也会 随着对数据的不断计算而朝着真实值改变。 （2）简要说明潜在因子模型对于降维问题的解决思路。 8．（4 分）假设采用多个相互独立的分类器进行二值分类学习，每个分类器的误 差概率为i，其中 i 是分类器编号，最终分类判定采取简单多数策略。试说明： 一般而言多分类器策略所得结果要好于单分类器。 第 3 页 共 3 页