第2期 魏彩锋，等：图正则化字典对学习的轻度认知功能障碍预 ·373· 响，提高模型的判别能力。用ADNI1数据集进行 3.2收敛性分析 验证，具体的实验结果在第4部分中，使用编码系数 在目标函数式(1)中对于{(D,P),(A)》的迭代 用分类器分类效果比直接使用分类器的效果好。 更新是一个双凸问题。在优化求解的过程中，固 在分类模型中，输入训练样本X使用算法1 定A对D和P求解是一个凸问题；固定D和P 训练出来的综合字典D和分析字典P,由A,计算 对A求解也是一个凸问题，因此目标函数是一个 出训练集在分析字典上的投影系数即稀疏表示中 双凸问题。根据文献[10]的补充材料，收敛时目 的编码系数Arm=PX,由测试样本Xe和分析字 标函数的能量值达到一个局部最小值。为了避免 典P,可以计算出测试集的编码系数Aet=PXe。 在更新过程中达到收敛条件，不同类之间单个样 将编码系数作为特征，用分类器对测试样本进行 本的能量不在同一个数量级上，所以，本文的收 分类。 敛条件是单个样本的能量到达某一局部最小。目 3算法分析 标函数中各项的曲线如图1所示。图1只是以 GDPL算法过程中使用其中一类迭代过程中的目 本节主要对提出的图正则化字典对算法 标函数值画出曲线为例。算法1中while后面的 (GDPL)进行时间复杂度分析和收敛性分析，该算 收敛条件为前后两次迭代的整个目标函数值之差 法通过联合学习一个综合字典和分析字典，将样 小于0，单个样本的重构误差的绝对值小于1，保 本在分析字典上的投影作为表示系数，减小了算 证目标函数值在每次迭代过程中逐渐减小，最大 法的时间复杂度。 迭代次数为50。 3.1时间复杂度分析 ×109 损失函数值 在GDPL算法中主要是计算训练阶段的时间 2 0 复杂度。在训练阶段Ak和{P,D}交替更新，每 -2 次更新过程相同，在此以一次更新为例。固定 -4 {P,D}由式(1O)更新Ak,Ak更新的时间复杂度 -6 -8 是一个逆矩阵和一个矩阵相乘的时间复杂度即 mXm的矩阵，{DDk+x的时间复杂度为O(m), -12 -14 在mXk的矩阵{rPX+DTX}中，PX的时间复 -16 杂度为O(mpm),DX的时间复杂度也是O(mpm), -18 10 2030405060 所以矩阵{rPXk+DX}的时间复杂度为Omp)。 迭代次数 矩阵(DD+tD'和(rPX+DX)相乘的时间复 图1目标函数值随迭代次数变化 杂度为O(m2),整个更新Ak的时间复杂度为 Fig.1 The value of the objective function varies with the Om3+mpm4+m2)。固定Ak,更新{P,D}。Pk由 number of iterations 式(12)进行更新，在式(14)中p×p的矩阵 图1中单个样本的整个目标函数值在开始到 (rXx+3+yl+BXLX的时间复杂度为 40次的变化趋势是平行趋于0，之后变成一个比 O(p2ne+p2(n-n)+pm2+p2n),但是在迭代过程中该 较大的负值，由于相似度矩阵不是半正定矩阵， 矩阵值不变，在初始化阶段提前计算出来，在迭 由此使图正则项的值变成负值，并引起其他项的 代过程中不需要重复计算，因此不影响更新P的 变化。并且由于图像的损失函数一般都不会小 时间复杂度。只需计算（πXX+3可+yl+BXLX 于0，所以，从图1可以看出算法在2~40次之间 逆矩阵的时间复杂度为O(p)。A?的时间复杂 是局部收敛的。所以，有的实验在第2次迭代就 度为O(mmp),两矩阵相乘的时间复杂度为 达到最优值。 Omp2),更新P.的时间复杂度为O(mmp+p23+mp2)。 4实验结果与分析 使用ADMM更新Dk,将ADMM算法中迭代更新 次数记为H,ADDM算法中，主要计算在式 为了验证图正则化字典对学习算法在图像分 (13)中D更新过程的时间复杂度。D根据式 类中的性能，本文在ADNI1数据集上进行验证。 (14)更新的，式(14)中XA、AkA、(AkA+pl)的 ADNI由国际老年研究所、生物医学成像和生物 逆矩阵、XAT(AAT+p)-1的时间复杂度分别为 工程研究所、美国食品和药物管理局、民营医药 O(pnm)、Om2n)、O(m3)、O(pm2),更新Dk整个过 企业和非营利组织在2003年启动，资金为60万 程的时间复杂度为O(H(pmm,+m2n:+m3+pm2)》。 美元。ADNI的主要目标是测试是否能通过组合响，提高模型的判别能力。用 ADNI1 数据集进行 验证，具体的实验结果在第 4 部分中，使用编码系数 用分类器分类效果比直接使用分类器[14]的效果好。 Atrain = PX Xtest Atest = PXtest 在分类模型中，输入训练样本 X 使用算法 1 训练出来的综合字典 D 和分析字典 P，由 A，计算 出训练集在分析字典上的投影系数即稀疏表示中 的编码系数 ，由测试样本 和分析字 典 P，可以计算出测试集的编码系数 。 将编码系数作为特征，用分类器对测试样本进行 分类。 3 算法分析 本节主要对提出的图正则化字典对算 法 (GDPL) 进行时间复杂度分析和收敛性分析，该算 法通过联合学习一个综合字典和分析字典，将样 本在分析字典上的投影作为表示系数，减小了算 法的时间复杂度。 3.1 时间复杂度分析 Ak {Pk , Dk} {Pk , Dk} Ak Ak m×m {D T k Dk +τI} O(m 3 ) m×nk {τPkXk + D T k Xk} PkXk O(mpnk) D T k Xk O(mpnk) {τPkXk + D T k Xk} O(mpnk) (D T k Dk +τI) −1 (τPkXk + D T k Xk) O(m 2nk) Ak O(m 3 +mpnk +m 2nk) Ak {Pk , Dk} Pk p× p (τXkX T k +λ3X¯ kX¯ T k +γI+βXLXT ) O(p 2nk + p 2 (n−nk)+ pn2 + p 2n) Pk (τXkX T k +λ3X¯ kX¯ T k +γI+βXLXT ) O(p 3 ) AkX T k O(mnp) O(mp2 ) Pk O(mnk p+ p 3+mp2 ) Dk Dk XkA T k AkA T k (AkA T k +ρI) XkA T k (AkA T k +ρI) −1 O(pnkm) O(m 2nk) O(m 3 ) O(pm2 ) Dk O(H(pmnk +m 2nk +m 3 + pm2 )) 在 GDPL 算法中主要是计算训练阶段的时间 复杂度。在训练阶段 和 交替更新，每 次更新过程相同，在此以一次更新为例。固定 由式 (10) 更新 ， 更新的时间复杂度 是一个逆矩阵和一个矩阵相乘的时间复杂度即 的矩阵， 的时间复杂度为 ， 在 的矩阵 中， 的时间复 杂度为 ， 的时间复杂度也是 ， 所以矩阵 的时间复杂度为 。 矩阵 和 相乘的时间复 杂度为 ，整个更新 的时间复杂度为 。固定 ，更新 。 由 式 (12 ) 进行更新，在 式 (14 ) 中 的矩阵 的时间复杂度为 ，但是在迭代过程中该 矩阵值不变，在初始化阶段提前计算出来，在迭 代过程中不需要重复计算，因此不影响更新 的 时间复杂度。只需计算 逆矩阵的时间复杂度为 。 的时间复杂 度 为 ，两矩阵相乘的时间复杂度为 ，更新 的时间复杂度为 。 使用 ADMM 更新 ，将 ADMM 算法中迭代更新 次数记 为 H ， ADD M 算法中，主要计算在 式 (13) 中 D 更新过程的时间复杂度。 根据式 (14) 更新的，式 (14) 中 、 、 的 逆矩阵、 的时间复杂度分别为 、 、 、 ，更新 整个过 程的时间复杂度为 。 3.2 收敛性分析 在目标函数式 (1) 中对于 {(D, P),(A)} 的迭代 更新是一个双凸问题。在优化求解的过程中，固 定 A 对 D 和 P 求解是一个凸问题；固定 D 和 P 对 A 求解也是一个凸问题，因此目标函数是一个 双凸问题。根据文献[10]的补充材料，收敛时目 标函数的能量值达到一个局部最小值。为了避免 在更新过程中达到收敛条件，不同类之间单个样 本的能量不在同一个数量级上，所以，本文的收 敛条件是单个样本的能量到达某一局部最小。目 标函数中各项的曲线如图 1 所示。图 1 只是以 GDPL 算法过程中使用其中一类迭代过程中的目 标函数值画出曲线为例。算法 1 中 while 后面的 收敛条件为前后两次迭代的整个目标函数值之差 小于 0，单个样本的重构误差的绝对值小于 1，保 证目标函数值在每次迭代过程中逐渐减小，最大 迭代次数为 50。 2 0 −2 −4 −6 −8 −10 −12 −14 −16 −18 0 10 20 30 40 50 60 迭代次数 损失函数值 目标函数值 ×109 图 1 目标函数值随迭代次数变化 Fig. 1 The value of the objective function varies with the number of iterations 图 1 中单个样本的整个目标函数值在开始到 40 次的变化趋势是平行趋于 0，之后变成一个比 较大的负值，由于相似度矩阵不是半正定矩阵， 由此使图正则项的值变成负值，并引起其他项的 变化。并且由于图像的损失函数一般都不会小 于 0，所以，从图 1 可以看出算法在 2～40 次之间 是局部收敛的。所以，有的实验在第 2 次迭代就 达到最优值。 4 实验结果与分析 为了验证图正则化字典对学习算法在图像分 类中的性能，本文在 ADNI1 数据集上进行验证。 ADNI 由国际老年研究所、生物医学成像和生物 工程研究所、美国食品和药物管理局、民营医药 企业和非营利组织在 2003 年启动，资金为 60 万 美元。ADNI 的主要目标是测试是否能通过组合 第 2 期 魏彩锋，等：图正则化字典对学习的轻度认知功能障碍预测 ·373·