第十章 降维与度量学习

此系列文章旨在提炼周志华《机器学习》的核心要点，不断完善中…

---

10.1 k近邻学习

1、描述
常用的监督学习方法
工作机制：给定测试集，基于某距离度量找出最靠近的k个样本，基于k个邻居的信息预测

• 分类——投票法
• 回归——平均法

懒惰学习的代表

2、懒惰学习与急切学习

• 懒惰学习(lazy study)：没有显式训练过程，仅把样本保存，训练时间无开销，待收到测试样本后再进行处理
• 急切学习(eager learning)：在训练阶段就对样本进行学习处理的方法

3、重要参数：k、距离计算方式

4、结论：最近邻分类器的泛化错误率不超过贝叶斯最优分类的错误率的两倍
* 证明过程：

5、重要假设
密度采样(dense sample)：任意测试样本x附近任意小的距离范围内总能找到一个训练样本（训练样本的采样密度足够大）

10.2 低维嵌入(embedding)

1、问题
密集采样假设在现实任务中通常很难满足
维数灾难(dimension curse)：高维时样本稀疏、距离计算困难等问题

2、降维（维数约简）

• 1）简述
  缓解维数灾难：特征选择/降维
  定义：通过某种数学变换将原始高维属性空间转变为一个低维子空间（在此样本密度大幅提高，距离计算容易）
• 2）经典降维方法
  • 多维缩放(Multiple Dimensional Scaling, MDS)
    • 目标：让原始空间中样本之间的距离在低维空间中得以保持
    • 假定：m个样本在原始空间的距离矩阵为$\bm D\in\mathbb{R}^{m*m}$D∈Rm∗m，其第i行j列的元素$dist_{ij}$distij​为样本$\bm x_i$xi​到$\bm x_j$xj​的距离。我们的目标是获得样本在d’维空间的表示$\bm Z\in\mathbb{R}^{d'*m}，d'≤d$Z∈Rd′∗m，d′≤d，且任两个样本在d’维空间中的欧氏距离等于原始空间中的距离，即$||\bm z_i-\bm z_j||=dist_{ij}$∣∣zi​−zj​∣∣=distij​
    • 公式推导：
      降维后样本的内积矩阵
      令将为后的降本Z被中心化
      设定
      结论公式
    • 结论：可通过降维前后保持不变的距离矩阵D求内积矩阵B
    • 对B做特征值分解：尽可能接近而不必完全相等
    • MDS算法
  • 主成分分析：线性变换方法（最简单）
  • 核化线性降维：非线性变换方法
• 3）对降维效果评估：比较降维前后学习器的性能

10.3 主成分分析

1、概述

• 起源：对于正交属性空间中的样本点如何用一个超平面对所有样本进行恰当表达
• 超平面性质
  最近重构性：样本点到这个超平面的距离都足够近
  最大可分性：样本点在这个超平面上的投影尽可能分开

2、两种等价推导

• 1）从最近重构性来推导
  假定
  原样本点与基于投影重构的样本点之间的距离
  主成分分析的优化目标
  $min_{\bm W}\ -tr(\bm{W^TXX^TW})$minW​ −tr(WTXXTW)
  $s.t.\ \bm{W^TW=I}.$s.t. WTW=I.
• 2）从最大可分性推导
  样本点$\bm x_i$xi​在新空间中超平面上的投影：$\bm{W^Tx_i}$WTxi​（应该使得投影后样本点的方差最大化）
  投影后的样本点方差：$\sum_i\bm{W^Tx_ix_i^TW}$∑i​WTxi​xiT​W
  主成分分析的优化目标：
  $max_{\bm W}\ tr(\bm{W^TXX^TW})$maxW​ tr(WTXXTW)
  $s.t.\ \bm{W^TW=I}.$s.t. WTW=I.
• 3）等价性分析
  拉格朗日乘子法：$\bm{XX^TW=\lambda W}$XXTW=λW
  PCA算法

3、降维后维数空间的维数d的选择
1）用户实现制定
2）通过在d’值不同的地位空间中对k近邻分类器进行交叉验证选取
3）从重构的角度设置一个重构阈值（如t=95%），选取使得下式成立的最小d’值：
$\frac{\sum_{i=1}^{d'}\lambda_i}{\sum_{i=1}^d\lambda_i}≥t.$∑i=1d​λi​∑i=1d′​λi​​≥t.

4、降维导致的结果

• 对应于最小的d-d’个特征值的特征向量被舍弃
• 样本的采样密度增大
• 一定程度上起到去噪的效果

10.4 核化线性降维

1、问题
线性降维方法的空间函数映射为线性，然而可能要非线性映射才能找到恰当的低维嵌入

2、解决方案：核主成分分析(Kernelized PCA, KPCA)

• 非线性降维方法常用，基于核技巧对先行将为方法进行核化(kernelized)
• 推导过程
  假定将高维特征空间中把数据投影到由W确定的平面上（欲求解式）:
  $(\sum_{i=1}^mz_iz_i^T)\bm W=\lambda\bm W$(i=1∑m​zi​ziT​)W=λW
  可知：
  公式变换：$(\sum_{i=1}^m\phi(\bm x_i)\phi(\bm x_i)^T)\bm W=\lambda \bm W$(i=1∑m​ϕ(xi​)ϕ(xi​)T)W=λW
  公式变换：$\bm W=\sum_{i=1}^m\phi(\bm x_i)\bm\alpha_i$W=i=1∑m​ϕ(xi​)αi​
  引入核函数：$\mathcal{K}(\bm x_i,\bm x_j)=\phi(\bm x_i)^T\phi(\bm x_j)$K(xi​,xj​)=ϕ(xi​)Tϕ(xj​)
  带入化简:
  投影后的第j维坐标

10.5 流形学习

1、概述
一类借鉴了拓扑流行概念的降维方法
在局部具有欧式空间的性质，能用欧式距离来进行距离计算

2、等度量映射(Isometric Mapping, Isomap)

• 目的：保持近邻样本之间的距离
• 测地线(geodesic)距离：高维空间两点之间的本真距离
• 测地线距离计算
  1.利用流形在局部上与欧式空间同胚性质，对每个点基于欧氏距离找出其近邻点
  2.建立一个近邻连接图，图中近邻点之间存在连接，而非近邻点之间不存在连接
  3.问题转化为计算近邻连接图上两点之间的最短路径(用Dijkstra/Floyd)
• Isomap算法（仅得到了训练样本在低维空间的坐标）
• 将新样本映射到低维空间权宜之计：将训练样本的高维空间坐标作为输入、低维空间坐标作为输出，训练一个回归学习器来对新样本的低维空间坐标进行预测
• 对近邻图构建常用的两种做法：指定近邻点个数、指定距离阈值

3、局部线性嵌入(Locally Linear Embedding, LLE)

• 目的：保持领域内样本之间的线性关系
  $\bm x_i=w_{ij}\bm x_j+w_{ik}\bm x_k+w_{il}\bm x_l$xi​=wij​xj​+wik​xk​+wil​xl​
• LLE算法解释
  
  
• LLE算法

10.6 度量学习

1、基本动机

• 降维目的
  找到一个合适的低维空间
  在空间中进行学习能比原始空间性能更好
• 直接尝试学习出一个适合的距离度量：
  每个空间对应了在样本属性上定义的一个距离度量
  寻找合适的空间，实质上就是在寻找一个合适的距离度量

2、距离度量表达式推广

• 对两个d’维样本$\bm x_i$xi​和$\bm x_j$xj​，平方欧式距离：
  $dist_{ed}^2(\bm x_i,\bm x_j)=||\bm x_i-\bm x_j||_2^2=dist_{ij,1}^2+...+dist_{ij,d}^2$disted2​(xi​,xj​)=∣∣xi​−xj​∣∣22​=distij,12​+...+distij,d2​
• 假定不同属性重要性不同（引入属性权重）：
  $dist_{wed}^2(\bm x_i,\bm x_j)=||\bm x_i-\bm x_j||_2^2=w_1*dist_{ij,1}^2+...+w_d*dist_{ij,d}^2=\bm{(x_i-x_j)^TW(x_i-x_j)}$distwed2​(xi​,xj​)=∣∣xi​−xj​∣∣22​=w1​∗distij,12​+...+wd​∗distij,d2​=(xi​−xj​)TW(xi​−xj​)
• 将W替换为普通半正定对称阵M得到马氏距离：
  $dist_{mah}^2(\bm x_i,\bm x_j)=\bm{(x_i-x_j)^TM(x_i-x_j)}=||\bm x_i-\bm x_j||_M^2$distmah2​(xi​,xj​)=(xi​−xj​)TM(xi​−xj​)=∣∣xi​−xj​∣∣M2​

3、学习M而设置的目标

• 提高近邻分类器的性能：将M直接嵌入到近邻分类器的评价指标，优化该指标求得M
• 例子：近邻成分分析(Neighbourhood Component Analysis, NCA)
  • 通常：多数投票法（领域中样本投1票，外0票）
  • 替换为概率投票法
    对任意样本的$\bm x_j$xj​，对$\bm x_i$xi​分类结果的影响概率：
    
    求解（随机梯度下降）可得最大化近邻分类器LOO正确率的距离度量矩阵M

4、在度量中引入领域知识

• 必连(must-link)约束：$(\bm x_i,\bm x_j)\in\mathcal{M}$(xi​,xj​)∈M 样本相似
• 勿连(cannot-link)约束：$(\bm x_i,\bm x_j)\in\mathcal{C}$(xi​,xj​)∈C 样本不相似
• 希望相似样本距离小，不相似距离大：求解凸优化问题获得适当的度量矩阵M
  $min_{\bm M}\ \sum_{(\bm x_i,\bm x_j)\in\mathcal{M}}||\bm x_i-\bm x_j||_{\bm M}^2$minM​ (xi​,xj​)∈M∑​∣∣xi​−xj​∣∣M2​
  $s.t.\ \sum_{(\bm x_i,\bm x_j)\in\mathcal{C}}||\bm x_i-\bm x_k||_{\bm M}^2≥1,\bm M≥0$s.t. (xi​,xj​)∈C∑​∣∣xi​−xk​∣∣M2​≥1,M≥0