《机器学习》扩张矩阵算法

4扩张矩阵算法: 定义1(扩张矩阵):已知et=及反例矩阵NE.对每 ∈N用“死元素”*对在NE中第列的所有出现做代换,这 样得出的矩阵叫做正例e在反例NE背景下的扩张矩阵。记为 EM(e+NE)或简记为EM(e) 表27正例矩阵与反例矩阵 k Ⅹ1X2X3k XI X2X3 0200 0002 2345 1110 002

4.扩张矩阵算法： 定义1(扩张矩阵)：已知e += 及反例矩阵NE. 对每一 j∈N, 用“死元素”*对 在NE中第j列的所有出现做代换，这 样得出的矩阵叫做正例e +在反例NE背景下的扩张矩阵。记为 EM(e+ |NE), 或简记为EM(e+ )。 表2.7正例矩阵与反例矩阵 + + 1 v n v ,  , + j v k X1 X2 X3 k X1 X2 X3 1 0 0 0 1 1 0 1 2 1 2 0 2 0 1 0 3 1 0 0 3 1 1 0 4 0 0 2 4 1 1 2 5 0 0 1

又1X2xx1x2X3x1Ⅹ2X3X1X2X3 * * 234 0①* 水 水 * ①①① 00* * **0 * * eM(e Em(e)) EM(e) EM( e4 图22正例在反例背景下的扩张矩阵 定义2:在一个扩张矩阵中,由分别来自不同行的m个非死元 素连接组成它的一条路(径);在两个以上的扩张矩阵中, 具有相同值的对应的非死元素叫做它们的公共元素;只由公 共元素组成的路叫做它们的公共路;具有公共路的两个扩张 矩阵叫做相交的,否则叫做不相交的

X1 X2 X3 X1 X2 X3 X1 X2 X3 X1 X2 X3 1 1 * ① * 0 ① * * 1 * * ① 2 * ① * 0 ① * 0 ① * * ① 0 3 1 ① * * ① * * ① * 1 ① 0 4 1 ① 2 * ① * * ① 2 1 ① * 5 * * ① 0 0 ① 0 * ① * * ① EM( ) EM( ) EM( ) EM( ) 图2.2 正例在反例背景下的扩张矩阵 定义2: 在一个扩张矩阵中，由分别来自不同行的m个非死元 素连接组成它的一条路（径）；在两个以上的扩张矩阵中， 具有相同值的对应的非死元素叫做它们的公共元素；只由公 共元素组成的路叫做它们的公共路；具有公共路的两个扩张 矩阵叫做相交的，否则叫做不相交的。 + 1 e + 2 e + 3 e + 4 e

1)算法AE1 优先选择“最大公共元素”,即在最多数目的扩张矩阵中出 现的元素。 2)广义扩张矩阵与AE9算法 ①广义扩张矩阵:已知反例矩阵NE和一个公式L=x=A] 对NE的每一列j∈N,如果J则用死元素“*”对NE中第j列 的所有元素做代换;如果j∈J,则用“*”对NE中第j列属于Aj 的所有元素做代换。这样得到的矩阵叫做公式L的广义扩张 矩阵。记为EML) ⑨必选元素:设EM(L)是一致公式L的扩张矩阵,如果在 EM(L)中的某一行中只有一个非死元素,则该元素叫做必选 元素。 ④公式的合并:已知公式Ax=A]及公式F=∧[Xx=B 则将L和F对应的选择子的取值合并得到一个新的公式,叫做 L和F的合并,记为L⊕F。即L⊕F=∧[X1=A∪B

1) 算法AE1 优先选择“最大公共元素”，即在最多数目的扩张矩阵中出 现的元素。 2) 广义扩张矩阵与AE9算法 ① 广义扩张矩阵：已知反例矩阵NE和一个公式L= 对NE的每一列j∈N,如果j J,则用死元素“*”对NE中第j列 的所有元素做代换；如果j∈J,则用“*”对NE中第j列属于Aj 的所有元素做代换。这样得到的矩阵叫做公式L的广义扩张 矩阵。记为EM(L). 必选元素：设EM(L)是一致公式L的扩张矩阵，如果在 EM(L)中的某一行中只有一个非死元素，则该元素叫做必选 元素。 公式的合并：已知公式 及公式F= 则将L和F对应的选择子的取值合并得到一个新的公式，叫做 L和F的合并，记为LF。即LF= . [x A ] j j j J  =    [ ] ' j j j J  X = B  [ ] ' j j j j J J  X = A B   [x A ] j j j J  = 

X4 式L{0,3}{0,1}{1,3} NE 034 223 (a)公式L(L=[X1=0V3X2=01X3=1V3与反例矩阵NE XI X2 X3 Ⅹ4 式 1**4 水 **

x1 x2 x3 x4 公式L {0,3} {0,1} {1,3} 1 1 1 1 1 2 0 2 2 2 3 3 1 2 2 4 4 0 3 3 NE (a) 公式L(L=[X1=0 3][X2=0 1][X3=1 3])    与反例矩阵NE X1 X2 X3 X4 公式 1 * * * * 2 2 * * * 2 * 4 * * *

(b)L的扩张矩阵EM(L)箭头经过的路对应于公式 [X1≠1,4][X3≠2]=X1=0,2,3][X3=0,1,3] 算法AE9 设正例集为TPE, (1)PE←TPE,从正例集PE中选择一个种子e.F<-e, path<φ,CPE←φ (2)做F的扩张矩阵EM(F)。如果有必选元素则放入path中,同 时删去NE中该必选元素出现的行(反例),如果NE空则将 F覆盖的正例从TPE中删去,如果TPE空则终止,否则转(1) 如非空则删去PE和CPE中出现该必选元素的对应行,重复 执行直至EM(F)中不存在必选元素为止。 (3)如果PE非空,检查PE中的每一正例,看它与F的合并是否是 致公式;如不是则从PE中删去该正例;若是则保留一个 覆盖正例数目最多的一个合并取代F,将PE中被F覆盖的正 例放入CPE中,重复步骤(2)和(3),直至PE变空。 (4)如果PE空而CPE非空,则检查CPE中的每一个正例,看它 与F合并后是否为一致公式,若不是则从CPE中删去该正例;

(b)L的扩张矩阵EM(L)箭头经过的路对应于公式 [X11,4][X32]=[X1=0,2,3][X3=0,1,3] [算法AE9] 设正例集为TPE， (1) PE←TPE,从正例集PE中选择一个种子e. Fe, path ,CPE . (2) 做F的扩张矩阵EM(F)。如果有必选元素则放入path中，同 时删去NE中该必选元素出现的行（反例），如果NE空则将 F覆盖的正例从TPE中删去，如果TPE空则终止，否则转(1)； 如非空则删去PE和CPE中出现该必选元素的对应行，重复 执行直至EM(F)中不存在必选元素为止。 (3)如果PE非空，检查PE中的每一正例，看它与F的合并是否是 一致公式；如不是则从PE中删去该正例；若是则保留一个 覆盖正例数目最多的一个合并取代F, 将PE中被F覆盖的正 例放入CPE中，重复步骤(2)和(3),直至PE变空。 (4) 如果PE空而CPE非空，则检查CPE中的每一个正例，看它 与F合并后是否为一致公式，若不是则从CPE中删去该正例；

若是则生成合并公式,保留一个覆盖最多正例的合并取代F 从CPE中删去被新的F覆盖的正例,重复(2)(4)直至CPE变空

若是则生成合并公式，保留一个覆盖最多正例的合并取代F, 从CPE中删去被新的F覆盖的正例，重复(2),(4)直至CPE 变空

(5)此时PE和CPE均空,但NE非空,做EM(F)将其中含有最多 非死元素的列中的非死元素放入path中,并从NE中删去含这 些非死元素的行,重复这一过程,直到NE变空。将path转变 为相应的公式。 [应用举例] 将表27的第一个反例改为 1)选择第一个正例e=做种子,Fe1path←￠ (2)做F的扩张矩阵EM(F),如图23 XI X2 XI X2 公式F0 公式F{0,1}{0,2}0,2} ② 2345 2

(5) 此时PE和CPE均空，但NE非空，做EM(F). 将其中含有最多 非死元素的列中的非死元素放入path中，并从NE中删去含这 些非死元素的行，重复这一过程，直到NE变空。将path转变 为相应的公式。 [应用举例] 将表2.7的第一个反例改为 (1) 选择第一个正例 做种子，F ,path , (2) 做F的扩张矩阵EM(F), 如图2.3 =  + e1 0,0,0 + 1 e X1 X2 X3 公式F 0 0 0 1 1 * 2 2 *  * 3 1 1 * 4 1 1 2 5 * *  X1 X2 X3 公式F {0,1} {0,2} {0,2} 1 * * 

22与13是“必选元素” path.F是一致的,F F⊕(e)=是一致的 F←F(e)=是不一致的。从PE中删去e, 保留覆盖最多正例的F=0.1,402,0)>.做EMF如, 示,13=2是必选元素。放入 path path<{2l3l13}.转换成公式。 [X2≠l[X3≠1,2]=[x2=0y2[X3=0] 对 重复执行AE9 参考文献: 归纳学习—算法,理论,应用。洪家荣著P.11-24

L22与l53是“必选元素” pathpath {L22， l53} (3) 将path转变为相应的公式，path= {L22， l53},公式为 [X21][X3 1]=[X2=0 2][X3=0 2] (4) 删去path涉及的行 (5) 做合并 FF( )=. F是一致的，F F( )=是一致的。 F F( )=是不一致的。从PE中删去 ， 保留覆盖最多正例的F=. 做EM(F) 如图2.4所 示， l13=2是必选元素。放入path,path{l22,l53,l13}. 转换成公式。 [X21][X3 1,2]=[X2=0 2][X3=0] 对 ,重复执行AE9. 参考文献： 归纳学习—算法，理论，应用。 洪家荣著 P.11-24    + 3 e + 3 e + 4 e + 4 e  + 4 e

3.机器学习:实现人工智能的途径.科学出版社P23-77 3)FCV算法 反例NE PE NE 序号X1X2X3X4序号X1X2X3X4 0 00 3456 020 20 278 220000 0000 101 14 1220 01

3. 机器学习:实现人工智能的途径 实现人工智能的途径. 科学出版社. P.23-77. 3) FCV算法 表2.4正例集PE和反例集NE PE NE 序号 X1 X2 X3 X4 序号 X1 X2 X3 X4 3 1 0 0 0 1 2 0 0 0 4 1 1 1 1 2 2 2 1 0 5 2 0 0 1 7 0 0 1 0 6 1 2 1 0 8 0 1 0 0 9 0 1 1 1 13 0 0 0 1 10 1 1 1 1 14 0 2 1 1 11 2 2 1 1 12 2 0 0 1

表25PE和NE的频率矩阵 FM (PE) FM NE XI 2 X4 Ⅹ1X2X3X4 320 332 561 402 132

表2.5 PE和NE的频率矩阵 FM (PE) FM (NE) X1 X2 X3 X4 X1 X2 X3 X4 0 1 3 3 2 0 4 3 3 4 1 4 3 5 6 1 0 1 3 2 2 3 2 2 2 2