主成分提取信息准则的加权规则

杜柏阳 孔祥玉 罗家宇

在信息处理领域,主成分分析(Principal component analysis,PCA)又称为KL 变换(Karhunen-Loéve transform),广泛应用于信号压缩[1]、模式识别[2]、图像处理[3]、噪声估计[4]、神经网络建模[5]等问题.通常,主成分(Principal component,PC)可以通过求解自相关矩阵的特征分解求得,具体是指自相关矩阵中前个最大特征值对应的特征向量.由这些特征向量张成的特征子空间被称为主子空间(Principal subspace,PS).

当前,在大量跟踪输入信号主成分主子空间的算法中,神经网络算法因为计算复杂度低等多种优良的性能而引起许多学者的兴趣[6].学者们提出大量的神经网络学习算法,用于提取主成分或者跟踪主子空间.例如,建立在启发推理机制上的Oja 主子空间跟踪算法[7]、对称误差校正算法[8],以及建立在信息准则基础上的最小均方误差重构(Least mean square error reconstruction,LMSER) 算法[9]、投影近似子空间跟踪(Projection approximation subspace tracking,PAST)算法[10].

早期的算法结构简单,但是在自稳定性、平滑性以及鲁棒性等方面还有待于优化.针对这些问题,Kong 等[11]提出了双目的的自稳定主成分提取神经网络算法,Kakimoto 等[12]提出了基于最小噪声准则的平滑自适应特征提取方法,Ouyang 等[13]提出了递归的鲁棒主成分分析算法.不仅如此,算法提取的对象还扩展到信号次成分[14]和广义特征成分[15].通过研究这些算法,可以知道提取信号多个成分和跟踪信号子空间的算法虽然实现提取的对象不同,但是在算法的原理上存在一定程度的关联.以主成分提取算法为例分析,多个主成分提取算法和主子空间跟踪算法都能够退化为单一主成分的提取算法,这反映出两个类型的算法具有某种相同的基本特性.反过来,如果存在一个能够提取单个主成分的提取算法,是否能遵循一定的原理或者规律,使得该算法能够转化为提取多个主成分或者跟踪主子空间的算法？这个问题的解答对灵活转换各种先进的成分提取算法,增加人们对提取算法本质和多种性质的理解具有十分重要的意义.

多个主成分可以张成一个主子空间,因而通常认为多个主成分的提取算法是主子空间跟踪算法的进步.一般而言,多个主成分的提取算法的提出方式有两种.一种是根据实际需求直接提出一种新的信息准则,通过推导信息准则的梯度函数得出对应的提取算法;另一种是在已有的主子空间跟踪算法的基础上,引入加权规则,使得转变后的算法能够提取多个主成分.Tanaka[16]通过研究多个主成分提取算法的广义加权规则,分析出广义加权规则的参数对提取算法的收敛速度有影响.加权规则的参数变化会引起算法的性质变化.当参数的取值沿着实数轴负方向变化时,加权矩阵则逐渐近似为单位阵,算法的提取能力逐渐由多个主成分提取退化为主子空间跟踪.

实际上,有的主子空间提取算法在使用加权规则后可以转化为多个主成分的提取算法,而有的算法则不具有这种能力.主子空间的组成向量与主成分之间的夹角能够说明主子空间与主成分的偏离程度.有的主子空间跟踪算法能够转化为多个主成分提取算法,原因在于这些跟踪算法在运行过程中能够减小夹角的大小.而本质上,确定这个夹角关系的是信息准则,信息准则函数在算法对信息的归类方式、算法提取信息的方式等具有非直接的规定.因此,在信息准则的角度分析加权规则对主子空间跟踪算法和多个主成分提取算法的作用能够反映算法的一些本质特性.

本文主要针对加权规则对主成分提取算法的信息准则的作用进行分析,以Oja 主子空间跟踪算法为例,通过构建提取算法的动力学表达,对比存在和缺失加权规则下的主子空间跟踪信息准则,挖掘出信息准则对状态矩阵与主成分的方向夹角的梯度差异.

1 加权规则

根据文献[7]和文献[17]可知,Oja 算法的信息准则为

其中,Ir∈Rr×r表示单位阵,W∈Rn×r为算法的状态矩阵,n为输入信号的维数,r为需要提取的主成分个数,R=E[xxT]∈Rr×r为随机输入信号x的自相关矩阵,E[·] 表示计算方括号内的数学期望.假设R是满秩矩阵,特征值互不相同.那么,输入信号有n个特征向量φi,i=0,1,···,n-1,容易理解,当存在一个矩阵W=Wn,使得信息准则函数值J1(W)能够取得最大时,Wn就等价于信号的主子空间,也就是前r个特征向量φi张成的子空间.

另外,Oja 还首先提出加权规则下的信息准则[18]

其中,D=diag{d1,d2,···,dr}∈Rr×r为一个对角矩阵,它的作用就是为状态向量加权.在主成分提取的算法中,加权矩阵的各个元素通常设置为d1＞d2＞···＞dr.其余变量的含义与式(1)相同.类似于Oja 算法的信息准则,当W=Wn时,J2(W)能够取得最大时,此时Wn不仅是前r个特征向量φi张成的子空间,而且组成Wn的各个向量与对应的特征向量φi相同.

通过以往研究可知,由以上两个信息准则求取相应跟踪或者提取算法通过梯度下降法实现,其基本的表达式为

其中,ηΔW(k)为算法的搜索方向,根据文献[16]可知,该方向为信息准则的梯度下降方向ηΔW(k)=;W(k)为第k步迭代中的状态矩阵,维度与式(1)中W相同;η∈(0,1)为算法的学习因子.实际上,有的加速算法中的学习因子并不是固定长度的,为了简化算法分析过程,此处假设学习因子是固定长度的.

相应地,由信息准则(1)推导得到的算法常微分方程形式[7]为

该算法能够有效地在线跟踪信号的主子空间.假设子空间相对于多个主成分的旋转矩阵为M1∈Rn×r,P=[φ0,φ1,···,φr-1],于是有W=PM1,主子空间的跟踪过程就是M1的前r行元素变化为某个旋转矩阵,后n-r行元素变化为零的过程.

由信息准则(2)推导得到的算法常微分方程形式[18]为

该算法也能够有效地在线跟踪信号的主子空间.与上文相似,存在一个M2∈Rn×r,W=PM2.这说明两种算法的信息准则都能够敏感到前r个特征值对应的特征信息.而不同之处在于,主子空间的跟踪过程中,M2的前r行元素变化为一个对角阵.本文主要针对M1和M2变化的差别展开分析,从微观角度探究加权规则对算法作用的动力学变化.

2 主成分提取过程动力学分析

只考虑一维特征的情况可以通过确定离散时间(Determinate discrete time,DDT)方法分析[19].直接分析高维特征提取过程非常复杂,不容易说明清楚.因而首先从二维特征情况开始.

定理1.信息准则J2(W)不能确定状态矩阵的各个向量与信号主成分方向之间的关系.

证明.假设M1的旋转角度为θ,那么M1可以写为

此时,信息准则(1)表示为

那么,信息准则对角度的梯度需要通过梯度下降公式解为

因而可以计算得

注1.定理1 可得的另外一个结论是,信息准则(1)的梯度算法提取出的主子空间与信号主成分存在一个夹角,并且该夹角与算法设置的状态矩阵初值有关.

注2.信息准则J1(W)并不能直接导出状态矩阵的变化方式,通常是通过梯度下降法、牛顿法、Nestrove 加速下降法等等利用信息准则的一阶、二阶甚至是高阶导数或者偏导数得到迭代更新公式.当迭代公式收敛时,对信息准则J1(W) 而言,收敛结果只能确保状态矩阵的模值收敛到某固定值而不能确定状态矩阵的各个向量与输入信号自相关矩阵的主成分方向的关系.信息准则在本质上规定了状态矩阵的变化方式.

实际上,加权规则能够改变信息准则的这个性质.具体过程可以通过定理2 说明.

定理2.信息准则J2(W)能够确定状态矩阵的各个向量与信号主成分方向之间的关系.

证明.假设M2的旋转角度为θ,那么M2可以写为

此时,信息准则(2)表示为

同样地,该信息准则对角度的梯度也可通过梯度下降公式解为

此时,可得

以上分析本质上是在n=2,r=2 这种特殊情况的讨论.下面需要对上述结论推广到n ＞2,r=2的情况.

推论1.对于n＞2,r=2, 信息准则J1(W)不能规定状态向量与信号主成分方向的关系,而信息准则J2(W)能够规定状态向量与信号主成分方向的关系.

证明.显然对于n＞2,r=2情况下的J1(W)和J2(W)而言,对应的梯度算法都能够跟踪主子空间,这在原作者的论文中已有明确的证明.也就是说,W的后n-r行元素总是逐渐变化为零.不妨认为,当迭代次数大于某一个大数时,状态矩阵可以表达为W=P[0]T, 其中,* 位置为1或2.此时根据定理1和定理2 的分析过程得知,信息准则J1(W) 不能敏感状态向量与信号主成分方向的变化,而信息准则J2(W) 能够敏感状态向量与信号主成分方向的变化.□

对于n=r,r ＞2 的情况而言,主要考虑欧拉转角描述所有的角度变化.第1 个相角变化为θ1,第2 个相角变化为θ2, 以至于第r个相角变化为θr.每一个角总是在上一个旋转角度基础上继续旋转,例如r=3时旋转矩阵M*表示为

以此类推.即将1 放在不动轴的位置,并且该元素所在行和列的其他元素均为0.不动轴的数量为r-2. 旋转次数为.

推论2.对于n=r,r ＞2, 信息准则J1(W)不能敏感状态向量与信号主成分方向的变化,而信息准则J2(W)能够敏感状态向量与信号主成分方向的变化.

证明.与定理1 和定理2 的证明步骤相似,信息准则(1)表示为

此时的旋转矩阵变为

同时信息准则对角度的梯度表达为多个公式

因为M1*具有旋转对称性,为了描述简便,此处仅以θ1为例进行说明.

由此可得,

显然,对于未加权的信息准则J1(W)而言,对于任意θ1恒成立.与此同时,对于加权信息准则J2(W) 而言,经过与上述推导过程相似的步骤可得,

注3.对于n＞r,r ＞2 情况的讨论,其基本思路同推论1,都是考虑在一定条件下,状态矩阵各个向量的长度发生变化,最终转化为n=r,r ＞2 的情况,结合推论2 的结论实现对该情况的讨论.

注4.通过定理和推论的分析可知,加权规则对提取算法产生影响的本质因素是加权算法改变信息准则在方向上的梯度变化.这对后续该类算法研究的启发是,在考虑将主子空间提取算法转变成并行提取算法时,其核心步骤是使算法在状态矩阵与实际主成分的夹角方向上产生梯度.为验证该思路对于Oja 信息准则以外的信息准则也有效,本文考察M iao 信息规则在加权规则下的性质变化.

3 数值分析与仿真实验

为保证算法具有可比性,在生成数据的时候对输入信号做出统一规定.各个仿真实验的输入信号自相关矩阵的特征值为同一组数值,在此考虑Λ=diag{1.052,2.335,5.002,5.251,6.012,6.123}.通过算法提取出信息的主成分P=[φ0,φ1,···,φn-1].另外,加权矩阵的数值也是任意选取一组满足定义的 数值,此处选为P=diag{1,2}.

3.1 Oja信息准则与Oja加权信息准则

如图1 所示,外侧的曲面圆锥为Oja 信息准则函数值变化,内侧的曲面圆锥为加权Oja 信息准则函数值变化.首先,两个函数值变化情况共同印证了信息准则能够良好地敏感状态矩阵的模值变化.为更加清晰地表征这个特点,该算例在某一个固定的角度投影两个信息准则函数,如图2.其次,两个曲面变化都具有对称性.其中,内侧的曲面圆锥是随着θ周期对称的,印证了定理2 中的一个结论,外侧的曲面圆锥是处处对称的.

另外,两个曲面的变化也是存在差别的.这首先表现在θ从 (0,2π] 变化的过程中,外侧的曲面圆锥在固定模值下,数值没有变化,如图3 所示,以θ为横坐标,将图1 中状态矩阵模长为 1.5 处的曲面函数值投影并展开,作为纵坐标;内侧的曲面圆锥在固定模值下,数值一直处在变化中,如图4 所示,以θ为横坐标,将图1 中状态矩阵模长为1.5 处的曲面函数值投影并展开作为纵坐标.其次,在θ固定的时候,两个曲面函数变化的梯度也不相同,如图2 所示,明显外侧的曲面圆锥的下降坡度小于内侧的曲面圆锥的下降坡度.这一点能够解释所有以Oja 信息准则为基础的梯度下降算法,加权规则下的信息准则具有更好的收敛速度.

图1 Oja 信息准则和加权Oja 信息准则在 θ 变化情况下的数值变化Fig.1 Curves of the information criterion Oja and weighted Oja algorithms on θ

图2 Oja信息准则和加权Oja 信息准则在处的投影Fig.2 Projection of the information criterion Oja and weighted Oja algorithms when

图3 Oja 信息准则在θ变化情况下的数值变化Fig.3 Curves of Oja information criterion on θ

图4 加权Oja 信息准则在θ变化情况下的数值变化Fig.4 Curves of weighted Oja information criterion on θ

综合上述分析,该算例能够验证Oja 信息准则与加权Oja 信息准则对提取算法在理论上分析的结论.

3.2 Miao信息准则与Ouyang信息准则

本文所研究的结论不仅适用于Oja 信息准则,还适用于其他信息准则,此处考虑Miao 信息准则[20]和Ouyang 信息准则[21].的初始设置与第3.1节中的算例相同.

Miao 信息准则的基本表达式为

Ouyang 信息准则的基本表达式为

从上述公式可以看出,Miao 信息准则在加权规则下的讨论就是Ouyang 信息准则.从图5～8 中可以看出,Miao 和Ouyang 信息准则的变化特性都能够呈现出第3.1 节的三个特性,这表明经过与Oja 及加权Oja 信息准则相似的动力学分析过程,也能够得到一致的结论.实际上,不仅Oja 算法、Miao 算法和Ouyang 算法,作者经过仿真验证,Yang[10]和Lei[9]的LMSER 算法也具有相似的动力学特性,由于篇幅限制在这里不做展示.这些算法的不同之处在下降的速度以及在平衡位置的信息准则函数值上.

图5 Miao 信息准则和Ouyang 信息准则在θ变化情况下的数值变化Fig.5 Curves of the information criterion Miao and Ouyang algorithms on θ

图6 Miao信息准则和Ouyang 信息准则在处的投影Fig.6 Projection of the information criterion Miao and Ouyang algorithms when

图7 Miao 信息准则在θ变化情况下的数值变化Fig.7 Curves of Miao information criterion on θ

图8 Ouyang 信息准则在θ变化情况下的数值变化Fig.8 Curves of Ouyang information criterion on θ

3.3 加权规则的应用案例

图像压缩是计算机图形图像学领域的热点问题.通过图像压缩技术都可通过压缩图像数据实现更加高效地存储和传输.基于主成分分析方法的压缩是图像压缩领域中的常用方法[22].本节采用主成分分析对Lena 图像进行压缩和重构.Lena 的原图如图9 左上角所示,分辨率为 512×512 像素.这里将图像分解为 4× 4 像素的不重叠小块.这些小块是按照从左到右由上到下的顺序排列,可得一个16×16 384 的数据向量.该数据经过预处理后作为主成分分析算法的输入序列.采用本文研究的加权Oja算法和Ouyang 算法对图像压缩后重建.

图9 原始和重建的Lena 图像Fig.9 Original and reconstructed Lena images

加权Oja 算法使用两次.第1 次只取一个主元,学习因子为 0.01,第2 次并行提取两个主元,学习因子也为 0.01,主要对比单个主元和多个主元情况的重建误差.Ouyang 算法使用一次,提取两个主元,学习因子也取 0.01.两个主元提取的算法加权矩阵为D.比较不同算法提取主元的精度.图9 右上角为一元Oja 提取算法的重建效果,重建误差为0.0829.图9 左下角为二元Oja 提取算法的重建效果,重建误差为0.0602.图9 右下角为二元Ouyang提取算法的重建效果,重建误差为0.0402.对比实验效果可以发现,多元并行提取算法相比单个主元提取算法具有优势,Ouyang 算法相比Oja 算法具有优势.这进一步表明先进算法需要通过加权算法确 保算法具有并行提取多个主成分的能力.

4 结论

本文通过分析Oja 信息准则和加权Oja 信息准则的差异,推导出加权规则能够改变状态矩阵和信号主成分的旋转矩阵梯度的结论.一方面这对于其他主子空间跟踪算法的转变提供了理论支撑,提高在信息准则层次影响算法性能的认识;另一方面,对于不能通过加权规则转化为多个主成分提取算法的主子空间跟踪算法,本文也给出转变的基本思路.研究为推进未来并行提取多个主成分分析算法发展提供了研究思路和转变方向,最后通过数值实例仿真验证了理论的有效性.