加性成分分析：一种非线性扩展的PCA方法，可用于降维和探索性数据分析

2491加性成分分析Calvin Murdock机器学习部门卡内基梅隆大学cmurdock@cs.cmu.edu费尔南多·德拉托雷机器人研究所卡内基梅隆大学ftorre@cs.cmu.edu摘要主成分分析（PCA）是无监督学习中最通用的工具之一，其应用范围从降维到探索性数据分析和可视化。虽然已经付出了很大的努力，xif2wix^if1xi =gi1+gi2x^i=f1（wi1）+f2（wi2）gi1/f1（wi1）G1gi1w1投票通过鼓励有意义的陈述，(a) 加性成分分析正则化（例如，非负性或稀疏性），基础线性假设会限制其有效性。为了解决这个问题，我们提出了加性成分分析（ACA），一种新的PCA的非线性扩展。受加性模型的多元非参数回归的启发，ACA通过学习从低维潜在空间到Xiwib1x^iB2xi =gi1+gi2x^i=wi1b1+wi2b2gi1wi1b1G1gi1w1输入空间，这使得像去噪这样的应用此外，ACA可以用作许多算法中的插入式替换，这些算法通过学习流形的局部切空间将线性分量与许多其他非线性降维技术不同，ACA可以有效地应用于大型数据集，因为它不需要计算成对相似性或在测试期间存储训练数据。多个ACA层也可以通过基本相同的过程进行组合和学习，以提高表示能力，展示了非参数深度学习的令人鼓舞的潜力。我们评估了各种数据集上的ACA，表现出更好的鲁棒性，recruitc- tion性能和可解释性。1. 介绍识别数据的底层结构是机器学习中最重要的任务之一。随着技术进步促进了数据集的构建，数据集的大小和维数不断增加，由于计算约束和维数灾难，数据分析变得更具挑战性。特别是在计算机视觉领域，数据通常由数千甚至数百万个特征组成，导致训练数据需求急剧增加。然而，现实世界的数据往往集中在(b) 主成分分析（PCA）图1：ACA（a）与PCA（b）在将二维表面拟合到三维数据的任务上的比较概述。这两种方法都使数据与其正交投影之间的平方距离之和最小。然而，当PCA学习由基向量b j跨越的线性子空间时，ACA学习由沿着平滑曲线f j的点的总和定义的非线性流形，从而减少重建误差。我们的方法的关键是每个数据点的分解xi转换为目标分量gij的和，这允许通过简单的单变量回归来学习基函数。近流形与较低的内在维数[27]。例如，虽然数字照相机的典型图像分辨率很大，但是与所有可能的像素实例的空间相比，自然图像的空间占据极小的体积。由于数据的几何性质通常是未知的，因此已经提出了各种属性来鼓励提取有意义的低维表示。组件分析方法建立在隐含的假设，即有用的表示是那些可以准确地重建输入数据。然而，为了实现有效的推广和可解释性，通常必须采用建模假设或正则化主成分分析（PCA）通过寻找最大值的方向来拟合数据的低维子空间2492方差虽然潜在的线性假设对某些数据（例如，例如面部的Lambertian对象的对准图像[3]），甚至小的扰动（例如，图像平移）可以引入使结果有偏差的非线性。核PCA通过在更高维的再生核希尔伯特空间中执行PCA来处理非线性相互作用，但是没有被优化以有效地重构输入数据。另一方面，流形学习在假设有意义的表示应该保持输入数据的局部几何结构的情况下取得了很大的成功然而，这些方法通常计算昂贵，难以解释，并且对噪声敏感为了解决这些问题，我们提出了加法成分分析（ACA），一种新的方法，非线性成分分析，明确优化重建误差。我们的方法背后的动机假设是，重建的输入数据应该相对于低维表示缓慢变化，放松PCA的严格线性假设。这与慢特征分析（SFA）[38]的慢度原则密切相关，其中假设序列数据的不变高级视觉表示然而，我们的方法是更一般的，允许其应用程序无序的数据和自动发现的潜在dimens- sions的变化，而不是时间。我们的方法可以被解释为一个无监督的加法模型[10]，用于从潜在输入变量预测训练数据，有效地将光滑流形拟合到数据，其复杂性由直观的粗糙度惩罚控制图1示出了概述。1，以及与PCA的比较。我们的贡献可归纳如下：（1）ACA通过最小化重构误差来学习从低维潜在空间到原始输入空间的存储高效的显式映射。这与用于非线性分量分析和流形学习的大多数其他方法有很大不同，从而提高了对噪声的鲁棒性，同时避免了典型的复杂性，例如前像问题[18]和样本外推断[7]。(2)有效的学习是通过交替优化算法来完成的，该算法不需要计算或存储成对的相似性矩阵，从而使其能够有效地应用于大型数据集。(3)为了通过非参数深度学习提高表示能力(4)最后，我们通过在各种数据集上显示改进的性能来证明我们的方法的有效性1.1. 背景及相关工作非线性降维是近年来的一个研究热点。在本节中，我们简要概述了一些以前的方法以及非参数统计的一些背景。非线性分量分析：已经进行了许多尝试来在分量分析框架内对非线性进行建模。最突出的例子是核PCA[33]，它将隐式非线性函数应用于输入数据，并使用核技巧在该特征空间中执行PCA。虽然通过表示定理启用了样本外推理，但由于前像问题[ 18 ]，从潜在空间到原始输入空间没有明确的反向投影。此外，核PCA的计算类似地，高斯过程潜变量模型[19]提供了非线性PCA的一般概率解释，但由于核化协方差函数，仍然存在许多相同的问题。最近，已经提出了近似核方法来提高计算效率。在[30]中，数据被显式映射到随机化特征空间，其中内积近似核函数求值。使用这个想法，随机非线性特征导致了非线性PCA的可扩展算法[23]。然而，这些方法都首先对输入数据进行变换，从而阻止了它们有效地应用于数据重建和去噪。流形学习：流形学习的方法通过最小化局部几何失真来寻找低维数据表示，例如。[34，4]。这些算法通常被形式化为特征分解，它们不学习到潜在空间的显式映射，因此不能直接支持反投影或样本外扩展[7]。此外，这些技术往往是拓扑不稳定的，依赖于不直观的超参数（例如，邻域大小），需要仔细调整，以避免退化行为，如短路[1]。自动编码器和深度神经网络：或者，自动编码器试图通过学习与潜在表示之间的显式非线性映射来重建数据。虽然在线性情况下证明与PCA等效[2]，但非线性激活函数和堆叠可以实现丰富的非线性表示[36]。事实上，一些深度学习模型可以被解释为学习数据流形[5]或低维分布[16]。虽然这些方法采用显式非线性映射来重建原始数据，但目前尚不清楚不同的正则化技术和模型架构如何影响可学习的非线性函数的空间[39]，因此它们往往需要大量的工程工作，并且仍然经常导致过度拟合和可解释性差。非参数统计：与具有固定复杂性的参数方法不同，非参数方法可以适应数据，允许表示广泛的非线性。然而，它们在高维设置中是无效的，因为需要大量的训练数据来有效地表征完整的数据分布[37]。为了解决这个问题，加法模型考虑2493Σ）？s.t.G）MMΣ一类较小的非参数函数，通过平滑样条函数分解为独立考虑每个输入维度的单变量函数的总和[10]，具有粗糙度惩罚的分段多项式函数，该函数具有小的二阶导数[37]。其他非参数方法也将主成分的概念推广为通过数据中心的几何对象[15，29]，但它们通常不能用于降维。与ACA最相似的方法是[11]，它也学习显式非参数函数以最小化最小二乘目标，但需要主动后拟合算法，通常需要多次迭代才能收敛[10]。相反，我们推导出一个等价的公式，我们的问题，允许交替最小化与简单的，封闭形式的更新。2.1. 等效问题公式化为了实现更简单的优化，我们通过将xi分解为目标分量gij的总和来引入额外的辅助变量，我们使用af fine等式约束来强制执行。然后，我们的优化问题可以等价地写为：良好的初始化，并且对于大型数据集是棘手的。2. 加性成分分析arg minfj∈F，wi∈W，gijΣni=1恩¨¨j=1.吉吉−fj （wij）Σ¨2¨2Σmj=1吉吉=xi（二）在本节中，我们将ACA的学习形式化为一个优化问题，并描述了解决它的方法。给定一个向量数据集x i∈ Rd，i = 1，...， n，我们的目标是推断低维潜在表示w i∈ Rm，可以用来最佳地重建相应的-当展开时，平方范数引入了额外的交叉项，形式为（g ij − f j（w ij））<$（g ik − f k（w ik）），其中k/= j。有趣的是，我们可以简单地忽略这些交叉项而不影响解，从而得到方程。第三章：ing数据。回想一下，PCA通过最小化将数据近似为线性组合阿敏fj∈F，米¨伊伊-fj¨¨（wijé2ΣmS.T.吉吉=xi（三）学习的基向量bj对于j=1，…，m与较低-wi∈W，giji=1j=1j=1三维潜在表示给出相应的-的系数W。我们通过将数据近似为在某些潜在变量wij下评估的学习非线性基函数fj的和来推广这一思想，从而得到近似的由加性模型f（w i）= j fj（w ij）给出的方程。利用最小二乘重建目标，我们的优化问题可以在等式中形式化如下1.一、在这里，我们的目标是学习基函数fj和潜在变量wi。我们将基函数约束为-长到具有粗糙度参数ρ的三次光滑样条F的集合，该粗糙度参数ρ平衡逼近精度和平滑度此外，为了压缩潜在空间并约束基函数的域，我们强制潜在表示属于封闭集合W，这使用少量的W2正则化来要理解为什么这个问题等价于Eq。 1，con-仅对辅助目标分量g ij进行边求解，其中基函数f j和潜在表示w i是固定的。 这分解为每个数据实例i=1，.，n.然后，我们可以将变量联系起来，使Gi=[g i1，.，g im]，Fi =[f 1（w i1），.， fm（w im）]，且A = 1Id，其中de-Kronecker乘积。 Gi中的目标成分然后可以通过求解方程中的优化问题来找到。4.第一章请注意，这只是Fi中的估计基函数fj（wij）在等式约束定义的最小子因此，它的解是以封闭形式给出的，其中A+xi是有限子空间上的一个点，N的列形成A的零空间的正交基。一个固定的超参数λ = 0。01.arg min-F-2S.T. Avec（G）=x阿敏恩−¨2f（w）¨（一）i iFGi+100。我我（四）+fj∈F，wi∈W¨ii=1Jj=1伊杰2vec（Gi）=Axi+NNvec（Fi）−Axi.Σ这里，A+xi=1xi 1，NN=I−111毫米M我是。后这一目标基本上最大限度地减少了近似误差-通过将它们投影到m维非线性流形上来匹配数据优化这个问题提出了一个有趣的挑战。类似约束元件分析问题的通用方法（例如，非负一些简化，目标分量gij由等式给出。五、直观地，这可以被解释为在目标组件gi j之间均等地分布当前近似误差，使得它们的总和为xi。矩阵分解[8]、字典学习[17]等）是交替最小化有了一组固定的变量，所产生的问题通常要简单得多。在我们的例子中，1 .一、gij=fj（wij）+mxi- Σmj=1Σfj（wij）（五）但事实并非如此。在潜在表示固定的情况下，优化问题简化为监督加性模型的优化问题，必须使用iter-把这个插回到我们的问题中3给出了我们的原始目标函数方程。 1由m-1重新标度。因此，这两个问题有完全相同的解决方案。2ΣΣ2494.Q我I2Xi(a) Findwigiv enljxi=gi1+gi2(c)给定f（wi），求gij(b)找到wigiv enwi，fjgi1zh f 1wi1g1gi2zf 2w i2G2F2f1w1w2(d)给定wij，gij，求fj初始化迭代20迭代40迭代56 原始数据图3：我们的优化过程应用于噪声合成数据集的示例。原始数据点显示在右侧。左侧是在整个优化过程中使用学习的基函数（以黑色显示）从初始化时的线性子空间开始，基函数适应数据的非线性结构，从而几乎完美地重建真实的底层流形。图2：交替优化过程的一次迭代的可视化。（a）首先，通过将每个数据点xi投影到由线性基函数近似lj定义的子空间上，使用PCA初始化，来找到近似潜在变量w_i。（b）然后，通过将xi投影到点f（wi）处的切空间上来更新wi。此步骤重复多次，初始的wij可以通过将xi投影到由线性近似lj定义的子空间样条函数fj.在插入该近似之后，所得到的问题，如下面的Eq. 8是严格凸二次规划.此外，它的唯一的极小化子给出了简单的，封闭形式的表达式。更小的步长以增加精度，导致x1在流形上的近似正交投影。(c)目标Σm¨argminüg−u −wf′（w2.5米）？s. t.G=x（8）然后，通过在它们之间相等地重新分配重构误差来找到分量gij（d）最后，基函数fjwi∈W，gijijijj=1国际新闻报ij2伊日j=1（连同它们的线性近似Lj）使用简单的单变量回归找到。由于Eqs之间的等价性。1和3，我们可以将g ij的解替换为等式2。8并求解wi其中Di=[f′（w∈i j）， . ，f′（wij）]2.2. 交替优化与我们在Eq中的原始问题公式不同。1、在Eq。3自然适合于一个有效的交替最小化算法。在使用PCA初始化后，我们ii=Σjuij：arg minxi−uiwi∈W1-Dw200M（九）基函数fj和gij联合求解潜在表示wj和目标分量gij。然后，固定这些变量，我们求解基函数f j，重复这个过程直到收敛。尽管非凸-我们的问题的性质，这种交替优化程序已被证明是收敛一致的良好的解决方案，如经验证明，在实验中讨论的第二节。4.第一章图1示出了概述。2和一个例子，其进展的合成数据集显示在图。3 .第三章。这种近似可以通过以减小的步长重复更新wi来改进。之后，使用等式（1）中的封闭形式解找到目标分量gij。五、请注意，稍后可以使用相同的过程对测试数据执行推断。2.）的情况。 基函数：在w i和g ij固定的情况下，我们求解方程。 对于每个j = 1，...， m：Σn¨21.）的人。潜在变量：有f j每个数据实例i=1，...， 编号：解，我们解Eq。6因为argminfj∈Fi=1<$gij−fj（wij）<$2（10）Σm¨2.5米这是标准的单变量回归，其中潜在的arg minwi∈W，gijj=1<$gij− fj（w ij）<$2s.t.j=1gij=xi（6）变量w ij被映射到目标分量g ij。我们将基函数fj限制为粗糙惩罚光滑样条[13]，因为它们的通用性和有效性这仅仅是xi在学者身上的投影计算因此，集合F可以定义为：ifold。 由于非线性，直接基函数fj.然而，由于我们要求它们在二阶导数很小的情况下是光滑的，因此它们可以有效地近似为一阶泰勒展开式。，的。∫F= f：R → Rd. <$q ∈ [1，d]：、（f′′（x））2dx≤γ（十一）围绕着一些近似解w∈ij，它定义了点f（wi）处流形的切空间：L2wiL1fY（w）XiwifY（wi221I1f（wif1wi2wi1f2（wi2f1（wi1gi1gi22495fj（wij）<$uij+wijf′（w<$ij），uij=fj（w<$ij）−w<$ijf′（w<$ij）（7）这些约束是用粗糙度惩罚来实现的用粗糙度超参数ρ平衡近似精度和复杂性。在Eq中的问题的解决方案。10是一个三次样条，在每个训练点都J J2496不JΣJ点，其可以被表示为样条基函数b，tj的线性组合，其中t=1，...，n b[13]。具体-0.40.30.20.40.30.2从理论上讲，我们将目标分量gij建模为fj（wij）=0.100.10tct jbt j（wi j），其中系数向量ctj∈Rd。在我们-0.1-0.2-0.1-0.2在实现中，我们使用B样条基函数，因为-0.320 - 10 0 10 20-0.3-20-10 010 20他们有限制的支持，导致稀疏，带状马，trices和线性时间逆计算[14]。 此外─潜在维度(a) 原始基函数潜在维度(b) 更新的近似值此外，它们的估值和导数可以使用简单的递归公式有效地计算[37]。当量10然后可以被重新表述为简单的具有等式10中给出的封闭形式解的最小二乘问题。12下面对于i=1，...，n和s，t=1，...，n b，其中Cj=[c1j，...， c nb j]。∫图4：在我们的随机优化技术中使用的变分样条近似的一个例子，用于不同节点位置的基函数的参数平均。原始基函数（a）被拟合到目标组件，节点位置由垂直虚线表示，而更新的基函数（b）用不同的节点位置近似，而不需要昂贵的最小二乘拟合。Bj（i，t）=btj（wij），SJ TJ.⊺Σ−1⊺ ΣΣ⊺这些控制点具有坐标（τt，ct），其中τt=1（τt+1+τt+2+τt+3）是τ的结平均。同样地，Cj=ρBjBj+（1−ρ）<$j B g1j···gnj（12）3对任意一个函数f，它在每个训练实例处使用节点，基函数的数量将随着训练示例的数量线性增长，这对于大型数据集来说将变得计算上易处理。然而，如果ρ足够小，则可以通过将节点放置在随机选择的nb=20个训练实例的子集上来很好地近似解决方案，因此那是个好主意。 这允许基函数被定义为使用相对少量的参数。2.3. 近似随机优化虽然由于成本函数可分离为较小的子问题，因此在前面章节中描述的优化过程具有内存效率，但对于非常大的数据集，在每次迭代中求解所有潜在变量可能在计算上是理想地，我们更倾向于采取随机方法，在每次迭代中只考虑数据的随机子集。然后，可以通过对来自先前迭代的参数进行加权平均来以特定步长更新基函数。然而，由于样条函数的节点位置在每次迭代时都发生变化，因此它们对应的参数不具有可比性。为 了 克 服 这 个 问 题 ， 我 们 提 出 了 一 种 方 法 ，approximates的样条函数从以前的迭代使用结从当前迭代，使他们的参数可以平均。具体来说，我们使用Schoenberg2.2为了理解这种方法，首先回想一下，样条函数可以在几何上解释为其控制多边形的平滑版本，这些多边形是分段线性的函数的顶点位于特定的控制点。对于具有节点向量τ的三次样条f（w）=tct bt（w），近似由（Vf）（w）= tf（τ）b t（w）给出，其中系数直接作为节点平均值处的函数求值给出。因此，在更新基函数参数从先前的迭代，我们采取一个变化减少样条近似的控制多边形评估在新的结平均从当前迭代，基本上导致一个线性插值的控制点。虽然这只是一个粗略的近似，如图所示。4，它导致有效的学习，大大减少了培训时间，我们在SEC中通过实验证明了这一点。4.第一章3. 加法模型尽管它们具有普遍性，但加性模型只能表示相对较小的一组可能的多元函数。因此，可以用ACA学习的流形的空间也是有限的。例如，考虑一个包含平移圆的噪声图像数据集，如图1所示。5 b.它的内在维度等于2，因为只有两个独立的变量维度：水平和垂直位置。然而，潜在的非线性不能有效地与ACA建模，导致潜在的可分离性和重建性能差。这一点在图的顶部得到了证明。五、成分分析的这种基本局限性是潜在变量之间允许的有限的加性相互作用的结果。 为了解决这个问题，我们提出了一种深度扩展的方法，将多个ACA层堆叠在一起，通过组成由基函数fk（j=1，...，其中mk−1

下载后可阅读完整内容，剩余1页未读，立即下载