《机器学习》第三章 学习的计算理论

第三章学习的计算理论 示例学习的优化问题 1)最优覆盖问题(MCV)生成具有最少数目公式的覆盖; (2)最简公式问题( MCOMP)生成具有最少数目选择子及属 性值的公式,或极大复合; (3)最优示例学习问题(OPL)生成只由最简公式组成的最 优覆盖。 二.最优覆盖问题是NP难题 定理3.1:已知两个问题P1和P2,如果P1是NP难题。并且P1可 在多项式时间内归纳到P2,则P2也是NP难题,并称P1可 (多项式)归纳到P2,如果P2反过来也能归纳到P1,则称 P1和P2是等价的。 定理32:最优集合覆盖问题( SETCV是从一个有穷集合的有 穷覆盖中,找到一个具有最小基数的子覆盖。即设T是 个m个点的集合,F是T的子集族。F={S1,…,Sp},其 中SiCT。 SETCV是找到F的具有最少数目的子族F

第三章 学习的计算理论 一. 示例学习的优化问题 (1) 最优覆盖问题(MCV)—生成具有最少数目公式的覆盖； (2) 最简公式问题(MCOMP)—生成具有最少数目选择子及属 性值的公式，或极大复合； (3) 最优示例学习问题(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的一个覆盖:FF ∪S=US=T并且 S∈FS∈F F最小;其中符号表示基数 定理33最优覆盖问题(MCV)是NP难题。 设T={1,…,7},F={S1,…,S6} Sl={1,4,5,7},S2={3,4},S3={25,7},S4={1,2,6},S5={1,3,7} S6-{35,6} Point# s1 s2 s3 $4 S5 S6 Point# F1 F2 F3 F4 F5 F6 2② 4567 23456 000 000 7 7

使得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} S S T S F' S F = =     Point# S1 S2 S3 S4 S5 S6 1 ① ① 1 2 2 ② 3 ③ 3 3 4 ④ ④ 5 ⑤ 5 5 6 ⑥ 6 7 ⑦ 7 7 Point# F1 F2 F3 F4 F5 F6 1 1 0 0 1 1 0 2 0 0 1 1 0 0 3 0 1 0 0 1 1 4 1 1 0 0 0 0 5 1 0 1 0 0 1 6 0 0 0 1 0 1 7 1 0 1 0 1 0 

Net 0 0000 NE000000 EM# X1 X2 X3 X4 X5 X6 EM# X1 X2 X3 X4 X5 X6 2345 **1* 00 0(00 234567 1*** *1***1 0 0● 定理34最简公式问题是NP难题 定理3.5最优示例学习问题是NP难题。 归纳 SETCV MCV V Li

NE 0 0 0 0 0 0 EM# X1 X2 X3 X4 X5 X6 1 0 ● ● 0 0 ● 2 ● ● 0 0 ● ● 3 ● 0 ● ● 0 0 4 0 0 ● ● ● ● 5 0 ● 0 ● ● 0 6 ● ● ● 0 ● 0 7 0 ● 0 ● 0 ● NE 0 0 0 0 0 0 EM# X1 X2 X3 X4 X5 X6 1 1 * * 1 1 * 2 * * 1 1 * * 3 * 1 * * 1 1 4 1 1 * * * * 5 1 * 1 * * 1 6 * * * 1 * 1 7 1 * 1 * 1 * 定理3.4 最简公式问题是NP难题。 定理3.5 最优示例学习问题是NP难题。 SETCV MCV, Li 归纳 P0 = 

归纳到 MCOMP PO+ ∑P 三.最小属性子集问题 定理36最小属性子集问题(MAS)是NP难题

Li MCOMP P0+ 三. 最小属性子集问题 定理3.6 最小属性子集问题(MAS)是NP难题。 归纳到 Pi = e i 1 Pi

Point# S1 S2 S3 S4 S5 S6 Point# X1 X2 X3 $4 S5 S6 00①00 2② 234 200①①00 30①00①① e4①①0000 567 es①0①00① 000①0① ⑦ 7 7 e7①0①0①0 算法GMAS (1)A← (2)建立正例集PE在反例集NE背景下的联合扩张矩阵 EM(PENE);这里联合扩张矩阵是将所有正例的扩张矩阵 罗在一起

Point# S1 S2 S3 S4 S5 S6 1 ① ① 1 2 2 ② 3 ③ 3 3 4 ④ ④ 5 ⑤ 5 5 6 ⑥ 6 7 ⑦ 7 7 Point# X1 X2 X3 S4 S5 S6 e1 ① 0 0 ① 0 0 e2 0 0 ① ① 0 0 e3 0 ① 0 0 ① ① e4 ① ① 0 0 0 0 e5 ① 0 ① 0 0 ① e6 0 0 0 ① 0 ① e7 ① 0 ① 0 ① 0 [算法GMAS] (1) A← ,i←1; (2) 建立正例集 PE在反例集NE背景下的联合扩张矩阵 EM(PE|NE); 这里联合扩张矩阵是将所有正例的扩张矩阵 罗在一起。 

(3)在EM(PENE找到一列,记为第j列,它含有最少数目 的死元素“*”,A←人{x (4)如果EM(PENE)删去所有在第j列含有非死元素的行; (5)如果EM(PENE)=⑨,则终止,并返回A否则1+1 并转向(3) 参考文献: 归纳学习一算法,理论,应用。洪加荣著P46-52,P.57-58

(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.  

Training Examples for Enjoy Sport Sky Temp Humid Wind Water Forecst EnjoySpt Sunny Warm Normal Strong Warm Same Yes Sunny Warm High Strong Warm Same Ye Rainy Cold High Strong Warm Change No Sunny Warm High Strong Cool Change Yes

Prototypical Concept Learning Task ● Giver: Instances X: Possible days, each described by the attributes Sky, Air Temp, Humidity, Wind. water, forecast Target function c: Enjoy Sport: X>10,1] Hypotheses H: Conjunctions of literals. E (?,Cold,High,"?,"?,? Training examples D: Positive and negative examples of the target function 〈x1,c(x1)),…(xm,c(xm) Determine: A hypothesis h in H such that h(a)=c(a) for all a in D

表 FIND-S算法 1.将h初始化为H中最特殊假设 2.对每个正例x 对h的每个属性约束a 如果x满足a 那么不做任何处理 否则将h中a替换为x满足的另一个更一般约束 3.输出假设h h← he he he<Sunny, Warm,?, Strong, ?,?

1. 将h初始化为H中最特殊假设 2. 对每个正例x 对h的每个属性约束a 如果x满足a 那么不做任何处理 否则将h中a替换为x满足的另一个更一般约束 3. 输出假设h h← h← h← h← 表 FIND-S算法

The List-Then-Eliminate algorithm 1. Version Space < a list containing every hypothesis in H 2. For each training example, (a, c(a) remove from Version Space any hypothesis h fo widh(x)≠c(x) 3. Output the list of hypotheses in Version space