363怎样使用不完全学习概念 Instance Sk Air Temp Humidit Wind Water Forecast EnjoySp S unn W arm Normal Strong Cool Change B Rainy Cold Norm Warm Same Sunny Normal Light Warm Same S unn Cold normal Strong Warm Same 3.7归纳偏置 3.71一个有偏的假设空间 372无偏的学习器 373无偏学习的无用性 学习器如果不对目标概念的形式做预先假定,它从根本上无法对 未见实例进行分类
3.6.3怎样使用不完全学习概念 Instance Sky AirTemp Humidit Wind Water Forecast EnjoySp A Sunny Warm Normal Strong Cool Change ? B Rainy Cold Normal Light Warm Same ? C Sunny Warm Normal Light Warm Same ? D Sunny Cold Normal Strong Warm Same ? 3.7 归纳偏置 3.7.1 一个有偏的假设空间 3.7.2 无偏的学习器 3.7.3 无偏学习的无用性 学习器如果不对目标概念的形式做预先假定,它从根本上无法对 未见实例进行分类
定义:考虑对于实例集合X的概念学习算法L令c为X上定义的任 概念,并令D={}为c的任意训练样例集合令L(x,Dc)表 示经过数据Dc的训练后L赋予实例的分类L的归纳偏置是最小断 言集合B,它使任意目标概念c和相应的训练样例Dc满足 (vxi∈X(B∧Dc∧xi)FL(xiD)
定义:考虑对于实例集合X的概念学习算法L.令c为X上定义的任 一概念,并令Dc={}为c的任意训练样例集合.令L(xi ,Dc)表 示经过数据Dc的训练后L赋予实例的分类.L的归纳偏置是最小断 言集合B,它使任意目标概念c和相应的训练样例Dc满足: (xiX)[(BDc xi) L(xi,Dc)]
第三章学习的计算理论 示例学习的优化问题 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…,S},其中 Sicko 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的一个覆盖:F'F,∪S=∪S=T并且 F=最小;其中符号表示基数。M 定理33最优覆盖问题(MCV)是NP难题。 设T={12…,7},F={S1,…,S6} S={1,4,5,7),S2={34},S3={2,57S4={1,2,6}2S5={1,3,7 S6={3,5,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 e 000000 EM# X1 X2 X3 X4 X5 X6 EM# X1 X2 X3 X4 X5 X6 2345 **1* 00 0(00 234567 11*** 1***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 ● e 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 l i=1
归纳到 MCOMP PO+ ∑ 三.最小属性子集问题 定理36最小属性子集问题(MAS)是NP难题
Li MCOMP P0+ 三. 最小属性子集问题 定理3.6 最小属性子集问题(MAS)是NP难题。 归纳到 Pi = l i 1 Pi
Point# S1 S2 S3 S4 S5 S6 Point# X1 X2 X3 $4 S5 S6 00①00 2② e2|00①①00 e4①①0000 ①00① 000①0① ⑦ 7 7 ①0①0①0 000000 算法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); 这里联合扩张矩阵是将所有正例的扩张矩阵 罗在一起。 e - 0 0 0 0 0 0
(3)在EM(PENE找到一列,记为第j列,它含有最少数目 的死元素“*”,A←人{x (4)从EM(PENE)删去所有在第列含有非死元素的行; (5)如果EM(PENE=中则终止,并返回A否则←i计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.
Example Sky AirTemp Humidit Wind Water Forecass EnjoySp S unn W arm Normal Strong Cool ChangeYes Cloudy Warm Normal Strong Cool ChangeYes Rainy W arm normal Strong Cool Change N
Example Sky AirTemp Humidit Wind Water Forecass EnjoySp 1 Sunny Warm Normal Strong Cool Change Yes 2 Cloudy Warm Normal Strong Cool Change Yes 3 Rainy Warm Normal Strong Cool Change No