《西瓜书》笔记10:降维与度量学习(三)
4. 核化线性降维
线性降维方法假设:从高维空间到低维空间的函数映射是线性的。
现实任务中,可能需要非线性映射才可找到适当的低维嵌入。
如上图,样本点从二维空间中的矩形区域采样后,以S形曲面嵌入到三维空间。若直接使用线性降维方法对三维空间观察到的样本点进行降维,将丢失原本的低维结构。
“原本采样的”低维空间称为本真低维空间。
非线性降维的一种常用方法:基于核技巧对线性降维方法进行核化。
如核主成分分析,KPCA。和SVM中的核技巧类似,引入核函数,将x到非线性空间的转换隐含计算出来。
5. 流形学习
manifold learning。
流形:在局部和欧式空间同胚的空间,即在局部具有欧式空间的性质。
给降维带来的启发:若低维流形嵌入到高维空间中,则数据样本在高维空间的分布虽然复杂,但在局部仍具有欧式空间的性质。
5.1 等度量映射
Isometric Mapping,Isomap
基本出发点:低维流形嵌入到高维流形中,直接在高维空间中计算直线距离具有误导性,因为高维空间中的直线距离在低维嵌入流形中不可达。
一只虫子从一点爬到另一点,不能脱离曲面,则红实线为最短距离,即S曲面上的测地线距离,测地线距离是两点之间的本真距离。
直接在此高维空间计算直线距离(黑直线)是不恰当的。如何计算低维嵌入流形上的测地线距离(红虚线)呢?可用近邻距离(黑色折线)代替。
可利用流形在局部上与欧式空间同胚的性质:对每个点基于欧式距离找出近邻点,然后建立一个近邻连接图,图中近邻点之间存在连接,非近邻点之间不存在连接。则两点之间测地线距离的问题,转变为计算邻近连接图上两点之间的最短路径问题。可用Dijkstra或者Floyd算法。
得到任意两点的距离之后,可通过MDS(多维缩放,获得样本在低维空间的表示,且任意两个样本在低维空间的欧氏距离等于原始空间中的距离)方法,来获得样本点在低维空间的坐标,起到降维的作用。
Isomap仅得到训练样本在低维的坐标。对于新样本如何映射?
常用解决方案:将训练样本的高空间为输入,低维空间为输出,训练一个回归学习器,来对新样本的低维空间预测。权宜之计,目前似无更好法。
邻近图构建:可指定临近点个数,可指定距离阈值。若临近点范围较大,则距离很远的点可能认为近邻,造成短路问题;若邻近范围很小,有些区域可能不连,造成断路。
5.2 局部线性嵌入
Locally Linear Embedding,L I E。待续。
6. 度量学习
ML中,对高维数据进行降维的目的是希望找到一个合适的低维空间,此空间中进行学习能比原始空间好。
实际上,每个空间对应了在样本属性定义的一个距离度量,寻找合适空间,实质是在寻找一个合适的距离度量。
举个例子,原始空间是3维,相当于每一个属性权重都是1。而降维后是2维,相当于某个属性对应的那一维权重为0了。
于是,距离度量学习的基本动机是:学习出一个合适的距离度量。
对两个d维样本
每一维上的距离平方和。
该式中的W可通过学习确定,即得到某个合适空间。
其大体思想如此。详细待续。