·86· 智能系统学报 第3卷 N*四和N',lN*1和N·⊙1表示N* 集U中删除.因此，在第2次迭代中，已标记样本数 和N·d的样本数目.用H表示ù具有标记-1， 为1+upp,未标记样本数为u(1-p.以此类推 H6表示i不具有标记-1，用H表示1具有标记 在第ⅰ次迭代中，已标记样本数和未标记样本数分 +1,Ho表示ù不具有标记+1.根据N+(和 别为I+p+upp2(1-p)++upp2(1- N·d计算标记的最大后验概率的公式如下： pm2=1+wpm(1-(1-pm))和u1-p)1.由 yi argmaxsero.u.P(H II N (W)= 此可知，任意一个半监督单标记迭代学习中，训练样 ar gmaxe(i Maxlter P(N(W 本总数为1+p:1·1·pW》= argmaxsEo.v.(P(HB)P(1 NHB). MaxIter(l+up:)up2 11-p)Mh ,由于 (8) 为计算，需要从训练集中计算先验概率 SML_SVM将半监督多标记学习问题转化为YI个 P(H)(q∈{+，-}，b∈0,1)和后验概率 半监督单标记学习问题，在SML_SVM中，参与训 PAN9(o‖H). 练的样本总数为|Y|(MaxIter(I+upm)·upm 在半监督单标记学习中，先用已标记数据集 1-11-p)Maxlte -).由于|Y (MaxIter(1+up)- p L,训练一个SVM分类器，然后对未标记数据集U 1-61-p)Maxker 进行标记，根据SVM分类器的分类结果，与分类超 up )<Y MaxIter(1+upz)<Y p 平面距离越远的点，越可能被正确分类，而在分类超 MaxIter(I+W,故SMLSVM算法的训练样本复 平面附近的点，错分的可能比较大，也就是说，与分 杂度为O(MaxIter)lI(1+W. 类超平面距离远的点分类结果的信任度高.从未标 记数据集中选择具有最高信任度的样本组成候选未 表1 SML_SVM算法步骤 标记数据集U',再根据最大后验概率原则，把U中 Table 1 Steps of SML_SVM algorithm 被正确标记的概率最大样本取出，组成己标记集 SML SVM(L.U.K,MaxIter,p,p2) L(·下一轮迭代的训练集为LUL,循环该过程， 输入参数： 直到达到算法的最大迭代次数.SML_SVM算法步 L:已标记数据集， 骤如表1所示」 U:未标记数据集： 2.2计算复杂度 K:近邻数： MaxIter:半监督训练最大迭代次数； SML SVM算法的复杂度与SVM的复杂度紧 p1:从U中选择构建U的未标记样本比例： 密相关，然而，SVM的不同优化求解方法的时间复 P2:从U中选择构建L的未标记样本比例 杂度和空间复杂度差异较大，因此直接计算SML 步骤： SVM的复杂度并不方便.根据文献[21]，文中通过 1)把多标记数据集L根据PT4策略转化为单标记数 计算SML SVM训练中所有样本的总数来衡量算 据集L', 法的复杂度.定理1表明，SML SVM算法与标记 2)根据训练若干个单标记SVM分类器，构成多标记 样本与未标记的数量是线性关系而不是指数关系 分类器SML SVM: 定理1 SML_SVM算法的训练中的样本复杂 3)Iter+1; 度为O(MaxIter|Y](I+l),其中MaxIter是最大 4)while (Iter <Maxlter) a)用SML SVM对U标记； 迭代次数，1Y为训练集中的标记类别数，1和“分 b)从U计算标记信任度最高的p1比例的样本，组 别是己标记样本数量和未标记样本数量， 成U'; 证明SML SVM将半监督多标记学习问题 c)计算U中样本标记的最大后验概率，取pm比例 转化为1个半监督单标记学习问题.首先计算任 的后验概率最高的样本组成L': 意一个半监督单标记迭代学习中的样本总数.设1由 d)跟据LUL',训练新的SML SVM: 为标记集Y中的任意1个标记，在第1次迭代训练 e)Iter +Iter+1; 中，1和u分别为已标记样本和未标记样本的数量. 5)end while. 在第1次迭代后，ppm个未标记样本被标记，且加 输出： 入到已标记样本中，且up个样本将从未标记样本 半监督多标记学习器SML SVM 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.netN + (‰u) 和 N - (‰u) ,| N + (‰u) | 和| N - (‰u) | 表示 N + (‰u) 和 N - (‰u) 的样本数目. 用 H - 1 表示 ‰u 具有标记 - 1 , H - 0 表示 ‰u 不具有标记 - 1 ,用 H + 1 表示 ‰u 具有标记 + 1 , H + 0 表示 ‰u 不具有标记 + 1. 根据 N + ( ‰u) 和 N - (‰u) 计算 ‰u 标记的最大后验概率的公式如下 : y‰u = argmaxb∈{ 0 ,1} , q∈{ + , - } { P( H q b ‖N q (‰u) | ) } = argmaxb∈{ 0 ,1} , q∈{ + , - } { P( H q b ) P(| N q (‰u) ‖H q b ) P(| N q (‰u) | ) } = argmaxb∈{ 0 ,1} , q∈{ + , - } { P( H q b ) P(| N q (‰u) ‖H q b ) } . (8) 为计算 y‰u , 需要从训练集中计算先验概率 P( H q p ) ( q ∈{ + , - } , b ∈{ 0 , 1 }) 和 后 验 概 率 P(| N q (‰u) ‖H q b ) . 在半监督单标记学习中 , 先用已标记数据集 L l ab训练一个 SVM 分类器 ,然后对未标记数据集 U 进行标记 ,根据 SVM 分类器的分类结果 ,与分类超 平面距离越远的点 ,越可能被正确分类 ,而在分类超 平面附近的点 ,错分的可能比较大 ,也就是说 ,与分 类超平面距离远的点分类结果的信任度高. 从未标 记数据集中选择具有最高信任度的样本组成候选未 标记数据集 U′,再根据最大后验概率原则 ,把 U′中 被正确标记的概率最大样本取出 , 组成已标记集 L′l ab . 下一轮迭代的训练集为 L ∪L′. 循环该过程 , 直到达到算法的最大迭代次数. SML_SVM 算法步 骤如表 1 所示. 212 计算复杂度 SML_SVM 算法的复杂度与 SVM 的复杂度紧 密相关 ,然而 ,SVM 的不同优化求解方法的时间复 杂度和空间复杂度差异较大 ,因此直接计算 SML _ SVM 的复杂度并不方便. 根据文献[ 21 ] ,文中通过 计算 SML_SVM 训练中所有样本的总数来衡量算 法的复杂度. 定理 1 表明 ,SML _SVM 算法与标记 样本与未标记的数量是线性关系而不是指数关系. 定理 1 SML_SVM 算法的训练中的样本复杂 度为 O(MaxIter| Y| ( l + u) ) ,其中 MaxIter 是最大 迭代次数 ,| Y| 为训练集中的标记类别数 , l 和 u 分 别是已标记样本数量和未标记样本数量. 证明 SML _SVM 将半监督多标记学习问题 转化为| Y| 个半监督单标记学习问题. 首先计算任 意一个半监督单标记迭代学习中的样本总数. 设 lab 为标记集 Y中的任意 1 个标记 ,在第 1 次迭代训练 中 , l 和 u 分别为已标记样本和未标记样本的数量. 在第 1 次迭代后 , u p1 p2 个未标记样本被标记 ,且加 入到已标记样本中 ,且 u p1 个样本将从未标记样本 集 U 中删除. 因此 ,在第 2 次迭代中 ,已标记样本数 为 l + u p1 p2 ,未标记样本数为 u(1 - p1 ) . 以此类推 , 在第 i 次迭代中 ,已标记样本数和未标记样本数分 别为 l + u p1 p2 + u p1 p2 (1 - p1 ) + …+ u p1 p2 ( 1 - p1 ) i - 2 = l + u p2 (1 - (1 - p1 ) i - 1 ) 和 u (1 - p1 ) i - 1 . 由 此可知 ,任意一个半监督单标记迭代学习中 ,训练样 本总 数 为 ∑ MaxIter i = 1 ( l + up2 (1 - (1 - p1 ) i- 1 ) ) = MaxIter ( l + up2 ) - up2 1 - (1 - p1 ) MaxIter p1 . 由于 SML_SVM 将半监督多标记学习问题转化为| Y| 个 半监督单标记学习问题 ,在 SML_SVM 中 ,参与训 练的样 本总数为 | Y| ( MaxIter ( l + u p2 ) - u p2 1 - (1 - P1 ) MaxIter p1 ) . 由于| Y| ( MaxIter ( l + u p2 ) - u p2 1 - (1 - p1 ) MaxIter p1 ) < | Y| MaxIter ( l + u p2 ) < | Y| MaxIter ( l + u) ,故 SML _SVM 算法的训练样本复 杂度为 O(MaxIter) | Y| ( l + u) . 表 1 SML_SVM 算法步骤 Table 1 Steps of SML_SVM algorithm SML_SVM(L ,U , K ,MaxIter , p1 , p2 ) 输入参数 : L :已标记数据集 ; U :未标记数据集 ; K:近邻数 ; MaxIter :半监督训练最大迭代次数 ; p1 :从 U 中选择构建 U′的未标记样本比例 ; p2 :从 U′中选择构建 L′的未标记样本比例. 步骤 : 1)把多标记数据集 L 根据 PT4 策略转化为单标记数 据集 L′; 2)根据训练若干个单标记 SVM 分类器 ,构成多标记 分类器 SML_SVM ; 3) Iter ←1 ; 4) while (Iter < = MaxIter) a) 用 SML_SVM 对 U 标记 ; b)从 U 计算标记信任度最高的 p1 比例的样本 ,组 成 U′; c) 计算 U′中样本标记的最大后验概率 ,取 p2 比例 的后验概率最高的样本组成 L′; d)跟据 L ∪L′,训练新的 SML_SVM ; e) Iter ←Iter + 1 ; 5) end while. 输出 : 半监督多标记学习器 SML_SVM · 68 · 智 能 系 统 学 报 第 3 卷