1、丁尧相,第十章：降维与度量学习,大纲,k近邻学习多维缩放主成分分析流形学习度量学习,k近邻学习,k近邻学习的工作机制,k近邻(k-NearestNeighbor,kNN)学习是一种常用的监督学习方法:确定训练样本，以及某种距离度量。对于某个给定的测试样本，找到训练集中距离最近的k个样本，对于分类问题使用“投票法”获得预测结果，对于回归问题使用“平均法”获得预测结果。还可基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。投票法：选择这k个样本中出现最多的类别标记作为预测结果。平均法：将这k个样本的实值输出标记的平均值作为预测结果,懒惰学习”与“急切学习,懒惰学习”(
3、）在二分类问题上的性能做一个简单的讨论。给定测试样本，若其最近邻样本为，则最近邻出错的概率就是与类别标记不同的概率，即,k近邻学习,分析1NN二分类错误率,令表示贝叶斯最优分类器的结果，有最近邻分类虽简单，但它的泛化错误率不超过贝叶斯最优分类器错误率的两倍,低维嵌入,维数灾难(curseofdimensionality,上述讨论基于一个重要的假设：任意测试样本附近的任意小的距离范围内总能找到一个训练样本，即训练样本的采样密度足够大，或称为“密采样”。然而，这个假设在现实任务中通常很难满足：若属性维数为1，当=0.001，仅考虑单个属性，则仅需1000个样本点平均分布在
4、归一化后的属性取值范围内，即可使得任意测试样本在其附近0.001距离范围内总能找到一个训练样本，此时最近邻分类器的错误率不超过贝叶斯最优分类器的错误率的两倍。若属性维数为20，若样本满足密采样条件，则至少需要个样本。现实应用中属性维数经常成千上万，要满足密采样条件所需的样本数目是无法达到的天文数字。许多学习方法都涉及距离计算，而高维空间会给距离计算带来很大的麻烦，例如当维数很高时甚至连计算内积都不再容易。在高维情形下出现的数据样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的严重障碍，被称为“维数灾难,低维嵌入,缓解维数灾难的一个重要途径是降维(dimensionreducti
6、于原始空间中的距离，即令，其中为降维后的内积矩阵，，有,多维缩放,为便于讨论，令降维后的样本被中心化，即。显然，矩阵的行与列之和均为零，即易知其中表示矩阵的迹(trace)，。令由此即可通过降维前后保持不变的距离矩阵求取内积矩阵,多维缩放,对矩阵做特征值分解(eigenvaluedecomposition)，其中为特征值构成的对角矩阵,为特征向量矩阵，假定其中有个非零正特征值，它们构成对角矩阵，为特征向量矩阵。令表示相应的特征矩阵，则可表达为,多维缩放,对矩阵做特征值分解(eigenvaluedecomposition)，其中为特征值构成
7、的对角矩阵，在现实应用中为了有效降维，往往仅需降维后的距离与原始空间中的距离尽可能接近，而不必严格相等。此时可取个最大特征值构成对角矩阵，令表示相应的特征向量矩阵，则可表达为,为特征向量矩阵，假定其中有个非零正特征值，它们构成对角矩阵，为特征向量矩阵。令表示相应的特征矩阵，则可表达为,多维缩放,MDS算法的描述,线性降维方法,一般来说，欲获得低维子空间，最简单的是对原始高维空间进行线性变换。给定维空间中的样本，变换之后得到维空间中的样本变换矩阵可视为个维属性向量。换言之，是原属性向量在新坐标系中的坐标轴向量。若与正交，则新坐标系是一个正交坐标系，
8、此时为正交变换。显然，新空间中的属性是原空间中的属性的线性组合。基于线性变换来进行降维的方法称为线性降维方法，对低维子空间性质的不同要求可通过对施加不同的约束来实现,其中是变换矩阵，是样本在新空间中的表达,主成分分析,主成分分析(PrincipalComponentAnalysis,简称PCA,对于正交属性空间中的样本点，如何用一个超平面对所有样本进行恰当的表达？容易想到，若存在这样的超平面，那么它大概应具有这样的性质：最近重构性：样本点到这个超平面的距离都足够近；最大可分性：样本点在这个超平面上的投影能尽可能分开。基于最近重构性和最大可分性，能分别得到主成分分析的两种
9、等价推导,主成分分析,最近重构性,对样本进行中心化，，再假定投影变换后得到的新坐标系为，其中是标准正交基向量，若丢弃新坐标系中的部分坐标，即将维度降低到，则样本点在低维坐标系中的投影是，是在低维坐标下第维的坐标，若基于来重构，则会得到,主成分分析,最近重构性,考虑整个训练集，原样本点与基于投影重构的样本点之间的距离为根据最近重构性应最小化上式。考虑到是标准正交基,是协方差矩阵，有,这就是主成分分析的优化目标,主成分分析,最大可分性,样本点在新空间中超平面上的投影是，若所有样本点的投影能尽可能分开，则应该使得投影后样本点的方差最大化。若投影后样本点的方差是，
10、于是优化目标可写为,显然与等价,主成分分析,PCA的求解,对优化式使用拉格朗日乘子法可得,只需对协方差矩阵进行特征值分解，并将求得的特征值排序：，再取前个特征值对应的特征向量构成，这就是主成分分析的解,主成分分析,PCA算法,主成分分析,降维后低维空间的维数通常是由用户事先指定，或通过在值不同的低维空间中对k近邻分类器（或其它开销较小的学习器）进行交叉验证来选取较好的值。对PCA，还可从重构的角度设置一个重构阈值，例如，然后选取使下式成立的最小值：PCA仅需保留与样本的均值向量即可通过简单的向量减法和矩阵-向量乘法将新样本投影至低维空间中。降维虽然会导致信息的损失，但
11、一方面舍弃这些信息后能使得样本的采样密度增大，另一方面，当数据受到噪声影响时，最小的特征值所对应的特征向量往往与噪声有关，舍弃可以起到去噪效果,核化线性降维,线性降维方法假设从高维空间到低维空间的函数映射是线性的，然而，在不少现实任务中，可能需要非线性映射才能找到恰当的低维嵌入,核化线性降维,核化主成分分析(KernelizedPCA,简称KPCA,非线性降维的一种常用方法，是基于核技巧对线性降维方法进行“核化”(kernelized)。假定我们将在高维特征空间中把数据投影到由确定的超平面上，即PCA欲求解其中是样本点在高维特征空间中的像。令,核化线性降维,核化主成分分析(
12、KernelizedPCA,简称KPCA,假定是由原始属性空间中的样本点通过映射产生，即,若能被显式表达出来，则通过它将样本映射至高维空间，再在特征空间中实施PCA即可，即有,并且,核化线性降维,一般情形下，我们不清楚的具体形式，于是引入核函数又由代入优化式，有上式为特征值分解问题，取最大的个特征值对应的特征向量得到解,核化主成分分析(KernelizedPCA,简称KPCA,其中为对应的核矩阵,核化线性降维,对新样本，其投影后的第维坐标为,核化主成分分析(KernelizedPCA,简称KPCA,其中已经过规范化，是的第个分量。由该式可知
13、，为获得投影后的坐标，KPCA需对所有样本求和，因此它的计算开销较大,流形学习,流形学习(manifoldlearning)是一类借鉴了拓扑流形概念的降维方法。“流形”是在局部与欧氏空间同胚的空间，换言之，它在局部具有欧氏空间的性质，能用欧氏距离来进行距离计算。若低维流形嵌入到高维空间中，则数据样本在高维空间的分布虽然看上去非常复杂，但在局部上仍具有欧氏空间的性质，因此，可以容易地在局部建立降维映射关系，然后再设法将局部映射关系推广到全局。当维数被降至二维或三维时，能对数据进行可视化展示，因此流形学习也可被用于可视化,流形学习,等度量映射(IsometricMapping，Isomap
14、,低维流形嵌入到高维空间之后，直接在高维空间中计算直线距离具有误导性，因为高维空间中的直线距离在低维嵌入流形上不可达。而低维嵌入流形上两点间的本真距离是“测地线”(geodesic)距离,流形学习,等度量映射(IsometricMapping，Isomap,测地线距离的计算：利用流形在局部上与欧氏空间同胚这个性质，对每个点基于欧氏距离找出其近邻点，然后就能建立一个近邻连接图，图种近邻点之间存在连接，而非近邻点之间不存在连接，于是，计算两点之间测地线距离的问题，就转变为计算近邻连接图上两点之间的最短路径问题。最短路径的计算可通过Dijkstra算法或Floyd算法实现。得到距离后可通过多维缩
15、放方法获得样本点在低维空间中的坐标,流形学习,等度量映射(IsometricMapping，Isomap,流形学习,局部线性嵌入(LocallyLinearEmbedding，LLE,局部线性嵌入试图保持邻域内的线性关系，并使得该线性关系在降维后的空间中继续保持,流形学习,局部线性嵌入(LocallyLinearEmbedding，LLE,LLE先为每个样本找到其近邻下标集合，然后计算出基于的中的样本点对进行线性重构的系数：其中和均为已知，令，有闭式解,流形学习,局部线性嵌入(LocallyLinearEmbedding，LLE,LLE在低维空间中保持
16、不变，于是对应的低维空间坐标可通过下式求解：令,则优化式可重写为右式，并通过特征值分解求解,流形学习,局部线性嵌入(LocallyLinearEmbedding，LLE,度量学习,研究动机,在机器学习中，对高维数据进行降维的主要目的是希望找到一个合适的低维空间，在此空间中进行学习能比原始空间性能更好。事实上，每个空间对应了在样本属性上定义的一个距离度量，而寻找合适的空间，实质上就是在寻找一个合适的距离度量。那么，为何不直接尝试“学习”出一个合适的距离度量呢,度量学习,欲对距离度量进行学习，必须有一个便于学习的距离度量表达形式。对两个维样本和，它们之间的平方欧氏距离可写为其中
18、希望提高近邻分类器的性能，则可将直接嵌入到近邻分类器的评价指标中去，通过优化该性能指标相应地求得,度量学习,近邻成分分析(NeighbourhoodComponentAnalysis,NCA,近邻成分分析在进行判别时通常使用多数投票法，邻域中的每个样本投1票，邻域外的样本投0票。不妨将其替换为概率投票法。对于任意样本，它对分类结果影响的概率为当时，最大。显然，对的影响随着它们之间距离的增大而减小。若以留一法(LOO)正确率的最大化为目标，则可计算的留一法正确率，即它被自身之外的所有样本正确分类的概率为其中表示与属于相同类别的样本的下标集合,度量学习,近邻成分分析(NeighbourhoodComponentAnalysis,NCA,整个样本集上的留一法正确率为由和，则NCA的优化目标为求解即可得到最大化近邻分类器LOO正确率的距离度量矩阵,度量学习,实际上，我们不仅能把错误率这样的监督学习目标作为度量学习的优化目标，还能在度量学习中引入领域知识。若已知某些样本相似、某些样本不相似，则可定义“必连”(must-link)约束集合与“勿连”(cannot-lin