英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
直观无协方差的增量主成分分析
Juyang Weng, Yilu Zhang and Wey-Shiuan Hwang
摘要：基于外观的图像分析技术需要快速计算高维图像向量的主成分。我们引入快速增量主成分分析（IPCA）算法，称为直观无协方差主成分分析（CCIPCA），以逐渐计算样本序列的主成分，而不估计协方差矩阵（也就是无协方差）。新方法是由统计效率的概念推动的（估计具有给定观察数据的最小方差）。虽然在我们的案例下由于样本分布未知而不能保证最高的效率，但是对于一些众所周知的分布（例如高斯分布）的估计，该方法保持观测的规模，并逐渐计算观测值的平均值。该方法用于实时应用，因此不允许迭代。它对于高维图像向量收敛非常快。本文对于IPCA与大脑皮质发育之间的一些联系也有所研究。
关键词：主成分分析，增量主成分分析，随机梯度上升（SGA），广义hebbian算法（GHA），正交补码。
1.介绍
一类被称为外观方法的图像分析技术现在已经变得非常受欢迎。 导致其普及的一个主要原因是使用统计工具来自动导出特征而不是依靠人来定义特征。 虽然主成分分析是一种众所周知的技术，但是Kirbyamp;Sirovich 似乎是第一个直接将该技术用于人脸表征的，人脸表征就是每个图像被视为高维向量，每个像素对应于成分。 Turk和Pentland 是第一个使用这种表示法进行面部识别的人。 该技术已经扩展到3-D对象识别，符号识别和自主导航，以及许多其他图像分析问题。
PCA，作为众所周知的计算方法，涉及到使用数值方法如幂方法和QR方法，来解决特征系统问题，例如计算样本协方差矩阵的特征向量和特征值。这种方法要求在可以估计主要成分之前，所有训练图像都可用，这被称为批处理方法。批处理方法不在满足日益兴起的计算机视觉研究的要求，这种方法所有视觉过滤器都是在动态视觉系统发展的激励下，从长时间的在线实时视频流中逐步推导出来的。在线视觉过滤器的开发要求系统在新的感知信号流动的同时进行。此外，当图像的尺寸高时，计算和存储复杂度都会大大增加。例如，在本征面方法中，64行和88列的中等灰度图像导致具有d = 5632的d维向量。对称协方差矩阵需要d（d 1）/ 2个元素，其数量增加至15,862,528个条目！当图像数量小于图像中的像素数量时，可以使用一种巧妙的保存方法。然而，在线开发系统必须观察到开放数量的图像，其数量大于观察矢量的维数。因此，需要一种增量方法来计算连续到达的观测值的主成分，主分量的估计是由每个到达的观测向量更新。没有协方差矩阵被允许估计为中间结果。有证据表明生物神经网络使用增量方法来执行各种学习，例如Hebbian学习。
目前已经提出了几种IPCA技术来计算无协方差矩阵的主成分。 然而，当面对高维图像向量时，它们会遇到收敛问题。 我们在这篇文章中解释为什么。 我们提出了一种基于Oja 和Sanger所做研究的新方法，直观无协方差IPCA（CCIPCA）。 它是由一个称为高效估计的知名统计概念所推导出来的。 一种记忆平均技术也用于动态地确定旧数据和新数据的保留率，而不是固定的学习率。
2. 算法推导
2.1第一特征向量
假设顺序获取的样本向量可能是无穷的。 每个，n = 1,2，...，是d维向量，d可以达到5000以上。 在不失一般性的情况下，我们可以假设具有零均值（平均值可以递增地估计和减去）。是协方差矩阵，其值未知，也不允许被估计为中间结果。
根据定义，矩阵的特征向量满足
（1）
其中是相应的特征值。 通过用样本协方差矩阵替换未知，并将等式 （1）中的用每个时间步长的估计来替换，我们获得的具有启发性的变体表达式，
（2）
其中是的第个阶段估计值。正如我们将要看到的那样，这个方程式是由统计效率推动的。 一旦我们估计了，很容易得到特征向量和特征值，因为和。
现在的问题是如何估计公式（2）中的。 考虑，我们可以选择
为，这推导出递增表达式，
（3）
首先，我们设置第一个方向的数据传播。 对于增量估计，方程式 （3）以递归的形式写成
（4）
其中是最后估计的权重，是新数据的权重。 我们已经证明，使用等式 （4），当时，其中是的协方差矩阵的最大特征值，是相应的特征向量[12]。
方程（2）-（4）的推导是以统计效率为基础的。 一个中肯的参数为的估计，
被认为是分配函数的类的有效估计的方差(平方误差)的每个分布密度函数达到由下面的等式给出的最小值：
（5）
不等式（5）的右侧被称为Cram#39; ER-Rao界。 它表示，有效估计是与实数参数有最小差异的估计，其方差在Cram#39;r-Rao界限之下。 例如，样本均值是具有标准偏差为sigma;的高斯分布的平均值的有效估计。 对于矢量版本所述Cram#39; ER-Rao界的，读者可参考文献14的[203-204页]。
如果我们定义，是等式（2）中的，可以被视为“样本”的平均值。这就是为什么我们的方法受到统计效率的影响，在方程式（2）中使用平均值的时候。 换句话说，统计学上，该方法趋向于最快地收敛或估计有给出当前观察到的样本的最小误差方差。 当然，不是必须的从高斯分布独立绘制，因此使用样本均值的估计在等式 （4）不是严格有效。 然而，估计仍然具有很高的统计效率并且具有相当低的误差方差，我们将在实验中显示。
Cram#39;Er-Rao在公式 （5）也可以用Wain等人提出和实验的高斯分布模型来估计误差方差或等效收敛速度。这是一个合理的估计，因为我们附近最优统计效率。 翁等 [14]证明实际误差方差对于分布（例如均匀或高斯分布）不是很敏感。 该误差估计器对于给定可容忍误差大致估计需要多少样本是特别有用的方差。
IPCA算法已被几位研究人员研究。 早期的工作Ojaamp;Karhunen [9] [10]给出了一个严格的衔接证明，他们介绍了他们随机梯度上升（SGA）算法。 SGA计算，
（6）
（7）
其中，是样本协方差矩阵的第i个主要特征向量的估计，是新的估计。 在实践中，方程（7）中的正交归一化可以通过标准的Gram-Schmidt正交归一化（GSO）方法来完成。 参数是随机近似增益。 SGA的融合已被证明在一些和的假设。
SGA本质上是一种梯度方法，与选择的学习速率有关。简单来说，学习率应该是适当的，使得方程式右侧的第二项（校正项） （6）与第一项相当，既不太大也不太小。实际上，在很大程度上取决于数据的性质，通常需要一个试错过程，这对于在线应用是不切实际的。 Oja提出了一些建议在[9]中的上，其通常为1 / n乘以一些常数。然而，程序（6）受到观察量的限制，其中第一项具有单位范数，但第二项可以采取任何幅度。如果u（n）的幅度非常小，则第二项将太小，无法对新估计进行任何改变。如果具有较大的幅度，这是高维图像的情况，则第二项将在非常大的数n，因此已经达到小的。在任一情况下，更新效率低下，收敛速度将会很慢。
与SGA相反，等式（4）右侧的第一项是没有正交化。实际上，等式（4）中的收敛于而不是，如同式（6），其中是特征值，是特征向量。在等式（4），通过将估计的比例保持在新观测的相同阶数（方程（4）右侧适当加权的第一和第二项获得样本均值），实现统计效率，这允许在统计效率方面充分利用每一个观测值。注意，等式（4）中的系数与第二项的“学习率”一样重要，以实现样本均值。 N很大时时，接近1大，与早期样品的快速收敛非常重要。关键在于，如果估计在开始时并不能很好地收敛，那么在大的时候更难被拉回来。因此，人们不必担心观测值的本质。这也是我们在命名新算法时使用“直观”的原因。
的确，SGA中的一系列参数可以在离线应用中手动调整，以便考虑到。 但是，无论如何调整，预定义的都不能达到统计效率。 这是真的，因为所有的“观测值”，例如等式 （4）和等式 （6）的最后一项，有助于方程式的估计。 等式（4）具有统计效率相同的权重，但它们在等式 （6）由于第一项中的归一化，从而降低效率。 此外，手动调谐不适合在线学习算法，因为用户不能预先预测信号。 在线算法必须自动计算数据敏感参数。
对等式（4）进一步改进。 在等式 （4），所有的“样本”是等权重的。然而，由于由生成，在早期估计阶段远离其实际值，所以是具有大的“ 噪音“，当我很小 为了加快估计的收敛，优选对这些早期的“样本”给予较小的权重。 实现这个想法的一个方法是通过改变方程式来使用一个遗忘的平均值，将等式（4）转入
（8）
其中正参数被称为记忆参数。 注意两个修改的权重仍然总和为1。随着的存在，更大的权重被给予新的“样本”，旧的 “样本”将逐渐淡出。 通常，的范围为2至4。
2.2直观的解释
步骤（4）的直观解释如下。考虑一组具有高斯概率分布函数的二维数据（对于任何其他物理上出现的分布，我们可以考虑其PCA的前两个统计数据）。数据由椭圆表示，如图1所示。根据特征向量的几何意义，我们知道第一个特征向量与椭圆的长轴（）对齐。假设是第一特征向量的步估计。注意是一个标量，我们知道本质上是的缩放向量。根据步骤（4），是最后估计值和的定标向量的加权组合。因此，在几何学上，通过将向拉小一点来获得。
与正交的线，将整个平面分成上半部和下半部分。因为下半平面中的每个点与具有钝角，是负标量。所以，对于， 等式（4）可以写成，
其中是通过将旋转180度w.r.t获得的上半平面点。由于椭圆是中心对称的，我们可以将所有下半平面点旋转到上半平面，只考虑上半平面点的拉动效应。对于上半平面中的点，纯力将向的方向拉，因为有比右侧更多的数据点左边。只要前两个特征值是不同的，这种拉力总是存在，拉向是朝向对应于较大特征值的特征向量。当两侧的拉力平衡时，将不会停止移动，直到与对齐。换句话说，等式1中的将收敛到第一特征向量。我们可以想象，第一特征值与第二特征值的比值越大，力越不平衡，拉力越快衔接将会。然而，当时，椭圆退化为圆。运动不会停止，这似乎算法不会收敛。实际上，由于该圆中的任何向量可以表示特征向量，所以它不会不会收敛。我们将回到第2.4节中相同特征值的情况。
2.3 高阶特征向量
步骤（4）仅估计第一个显性特征向量。计算其他更高阶特征向量的一种方法是遵循SGA所做的：从一组正交归一化向量开始，使用建议的迭代步骤更新它们，并使用GSO恢复正交性。对于实时在线计算，我们需要避免耗时的GSO。此外，与保持正交性相比，断开恢复的正交性减慢了收敛。我们知道特征向量彼此正交。因此，它只能在用于计算高阶特征向量的互补空间中产生“观察”。例如，为了计算二阶特征向量，我们首先从数据中减去估计的第一个特征向量的投影阶特征向量，如等式（9），
（9）
当。在的互补空间中获得的残差用作迭代步骤的输入数据。以这种方式，当达到收敛时，正态性总是被强制执行，尽管在早期阶段并不完全如此。这实际上很好地利用了可用的样本，从而加快了收敛。
图1 PCA增量算法的直观解释。
一些其他研究人员也使用了类似的想法。 Kreyszig提出了一种算法，它使用等效于SGA的方法找到第一个特征向量，并在计算下一个分量之前从样本中减去第一个分量。 Sanger提出了一种算法，称为广义hebbian算法（GHA），基于相同的想法，除了所有的组件都在同一时间计算[11]。 然而，在这两种情况下，统计效率都没有被考虑。
新的CCIPCA还可以节省计算量。 可以注意到，SGA和CCIPCA中的昂贵步骤是高维数据空间中的点产品。 CCIPCA需要一个额外的点积，即等式（9）中的，对于每个估计步骤中的每个主要分量。 对于SGA，要使用GSO对个特征向量的新估计进行平均归一化，我们具有完全个点积。 因此，CCIPCA在SGA上为每个特征向量保存的点积的平均数为。
2.4 等特征值
让我们考虑有相同特征值的情况。假设和之间的有序特征值相等：
.
根据第2.2节的解释，向量估计将首先收敛于具有较大特征值的估计。因此，其中的特征向量的估计将不会受到影响。
到的向量估计将收敛到由相应的特征向量跨越的子空间中。由于它们的特征值相等，所以分布的形状如图1所示,是子空间内的超球体。因此，多个特征向量的估计将会收敛到任何一个该子空间的正交基的集合。其收敛主要取决于早期样品，因为方程式的平均效应（2），当n增加而不受限制时，新数据的贡献无限小。这正是我们想要的。这些特征向量的收敛与一般情况一样快。
2.5 算法总结
结合上面讨论的机制，我们有直观的协方差IPCA算法如下。 程序1直接从计算第k个主要特征向量
对于，执行以下步骤，
1.
2. 对于
（a）如果，则将第个特征向量初始化为。
（b）否则， （10）
（11）
可以在文献[12]中建立CCIPCA收敛的数学证明。
3. 收敛的实证结果
我们进行实验来研究新算法的统计效率以及现有的IPCA算法，特别是对于诸如图像的高维数据。我们将样本 - 维数比定义为，其中是样本数，是样本空间的维数。比例越低，统计估计问题就越难。
首先提出的是我们在
全文共11698字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[144365]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
