第三章 学习的计算理论示例学习的优化问题最优覆盖问题（.ppt

* 第三章 学习的计算理论 示例学习的优化问题 最优覆盖问题(MCV)—生成具有最少数目公式的覆盖； 最简公式问题(MCOMP)—生成具有最少数目选择子及属性值的公式，或极大复合； 最优示例学习问题(OPL)—生成只由最简公式组成的最优覆盖。 二. 最优覆盖问题是NP难题 定理3.1：已知两个问题P1和P2,如果P1是NP难题。并且P1可在多项式时间内归纳到P2,则P2也是NP难题，并称P1可（多项式）归纳到P2,如果P2反过来也能归纳到P1,则称P1和P2是等价的。 定理3.2：最优集合覆盖问题(SETCV)是从一个有穷集合的有穷覆盖中，找到一个具有最小基数的子覆盖。即设T是一个m个点的集合，F是T的子集族。 F={S1, …,Sp}, 其中Si T。SETCV是找到F的具有最少数目的子族F’, 使得F’是T的一个覆盖：F’ F, 并且 |F|=最小；其中符号| |表示基数。 定理3.3 最优覆盖问题(MCV)是NP难题。 设 T={1, …,7} , F={S1, …,S6} S1={1,4,5,7}, S2={3,4}, S3={2,5,7},S4={1,2,6}, S5={1,3,7}, S6={3,5,6} 7 7 ⑦ 7 6 ⑥ 6 5 5 ⑤ 5 ④ ④ 4 3 3 ③ 3 ② 2 2 1 ① ① 1 S6 S5 S4 S3 S2 S1 Point# 0 1 0 1 0 1 7 1 0 1 0 0 0 6 1 0 0 1 0 1 5 0 0 0 0 1 1 4 1 1 0 0 1 0 3 0 0 1 1 0 0 2 0 1 1 0 0 1 1 F6 F5 F4 F3 F2 F1 Point# ● 0 ● 0 ● 0 7 0 ● 0 ● ● ● 6 0 ● ● 0 ● 0 5 ● ● ● ● 0 0 4 0 0 ● ● 0 ● 3 ● ● 0 0 ● ● 2 ● 0 0 ● ● 0 1 X6 X5 X4 X3 X2 X1 EM# 0 0 0 0 0 0 NE * 1 * 1 * 1 7 1 * 1 * * * 6 1 * * 1 * 1 5 * * * * 1 1 4 1 1 * * 1 * 3 * * 1 1 * * 2 * 1 1 * * 1 1 X6 X5 X4 X3 X2 X1 EM# 0 0 0 0 0 0 NE 定理3.4 最简公式问题是NP难题。 定理3.5 最优示例学习问题是NP难题。 SETCV MCV, Li 归纳 P0 Li MCOMP P0+ 三. 最小属性子集问题 定理3.6 最小属性子集问题(MAS)是NP难题。 归纳到 Pi 7 7 ⑦ 7 6 ⑥ 6 5 5 ⑤ 5 ④ ④ 4 3 3 ③ 3 ② 2 2 1 ① ① 1 S6 S5 S4 S3 S2 S1 Point# 0 ① 0 ① 0 ① e7 ① 0 ① 0 0 0 e6 ① 0 0 ① 0 ① e5 0 0 0 0 ① ① e4 ① ① 0 0 ① 0 e3 0 0 ① ① 0 0 e2 0 0 ① 0 0 ① e1 S6 S5 S4 X3 X2 X1 Point# [算法GMAS] A← ,i←1; 建立正例集 PE在反例集NE背景下的联合扩张矩阵EM(PE|NE); 这里联合扩张矩阵是将所有正例的扩张矩阵罗在一起。 (3) 在EM(PE|NE)找到一列，记为第j列，它含有最少数目的死元素“*”,A←A {xj}. (4) 如果EM(PE|NE) 删去所有在第j列含有非死元素的行； (5) 如果EM(PE|NE)= ,则终止，并返回A;否则i←I+1.并转向(3); 参考文献： 归纳学习—算法，理论，应用。 洪加荣著 P.46-52, P.57-58. 1. 将h初始化为H中最特殊假设 2. 对每个正例x 对h的每个属性约束a 如果x满足a 那么不做任何处理 否则将h中a替换为x满足的另一个更一般约束 3. 输出假设h h←? , ? , ? , ? , ? , ? h←Sunny,Warm,Normal,Strong,Warm,Same h←Sunny,Warm,?,Strong,Warm,Same h←Sunny,Warm,?,Strong,?,? 表 FIND-S算法 候选消除算法