第十章 降维与度量学习

10.1 k近邻学习

• $k$近邻（k-NearestNeighbor，简称KNN）学习是一种常见的监督学习方法。
  • 给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测。
  • 在分类任务中常使用“投票法”，即选择这k个样本中出现最多的类别标记作为预测结果；
  • 在回归任务中可使用“平均法”，即将这k个样本的实值输出标记的平均值作为预测结果。
• k近邻学习是“懒惰学习”（lazy learning）的代表：在训练阶段仅仅把样本保存起来，待收到测试样本后再进行处理。（在训练阶段就对样本进行学习处理的方法称为“急切学习”eager learning）

• 最近邻分类器虽然简单，但它的繁华错误率不超过贝叶斯最优分类器的错误率的两倍。

10.2 低维嵌入

• k近邻学习基于一个重要假设：任意测试样本$x$附近任意小的$\delta$距离范围内总能找到一个训练样本，即训练样本的采样密度足够大，称为“密采样”（dense sample）
• 高维情形下出现的数据样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的严重障碍，被称为“维数灾难”（curse of dimensionality）
  • 缓解途径是降维（dimension reduction），亦称“维数约简”。通过某种数学变换将原始高维属性空间转变为一个低维“子空间”（subspace）
  • 在子空间中样本密度大幅提高，距离计算也变得更为容易。

• 多维缩放（Multiple Dimensional Scaling，简称DMS）是一种经典降维方法。
  • 假定$m$个样本在原始空间的距离矩阵为$D\in \mathbb{R}^{m\times m}$，其第$i$行第$j$列的元素$dist_{ij}$为样本$x_i$到$x_j$的距离。目标是获得样本在$d’$维空间的表示$Z\in \mathbb{R}^{d’\times m},d’\leq d$，且任意两个样本在$d’$维空间中的欧式距离等于原始空间中的距离，即$\lVert z_i-z_j\rVert=dist_{ij}$
  • 令$B=Z^TZ\in\mathbb{R}^{m\times m}$，其中$B$为降维后样本的内积矩阵，$b_{ij}=z_i^Tz_j$
    • $dist^2{ij}=\lVert z_i\rVert^2+\lVert z_j\rVert^2-2z_i^Tz_j=b{ii}+b_{jj}-2b_{ij}$
    • 令降维后的样本$Z$被中心化，即$\sum_{i=1}^mz_i=0$。显然，矩阵$B$的行与列之和均为零，即$\sum_{i=1}^mb_{ij}=\sum_{j=1}^mb_{ij}=0$ 。
    • $\sum_{i=1}^mdist_{ij}^2=tr(B)+mb_{jj}$
    • $\sum_{j=1}^mdist_{ij}^2=tr(B)+mb_{ii}$
    • $\sum_{i=1}^m\sum_{j=1}^mdist_{ij}^2=2mtr(B)$
    • $tr(·)$表示矩阵的迹（trace），$tr(B)=\sum_{i=1}^m\lVert z_i\rVert^2$，令
      • $dist^2{i·}=\frac1m\sum{j=1}^mdist^2_{ij}$
      • $dist^2{·j}=\frac1m\sum{i=1}^mdist^2_{ij}$
      • $dist^2{··}=\frac1{m^2}\sum{i=1}^m\sum_{j=1}^mdist_{ij}^2$
  • 得到$b_{ij}=-\frac12(dist^2{ij}-dist^2{i·}-dist^2{·j}+dist^2{··})$，由此即可通过降维前后保持不变的距离矩阵D求取内积矩阵B。
    • 对矩阵B做特征值分解（eigenvalue decomposition），$B=V\Lambda V^T$，其中$\Lambda=diag(\lambda_1,\lambda_2,…,\lambda_d)$为特征值构成的对角矩阵，$\lambda_1\geq\lambda_2\geq…\geq\lambda_d$，$V$为特征向量矩阵。
    • 假定其中有$d^{\ast}$个非零特征值，它们构成对角矩阵$\Lambda_{\ast}=diag(\lambda_1,\lambda_2,…,\lambda_d)$，令$V_{\ast}$表示相应的特征向量矩阵，则$Z$可表达为：$Z=\Lambda_{\ast}^{1/2}V_{\ast}^T\in\mathbb{R}^{d^\ast\times m}$
  • 在现实中为了有效降维，仅需降维后的距离与原始空间中的距离尽可能接近，不必严格相等。可取$d’\ll d$个最大特征值构成对角矩阵$\tilde \Lambda=diag(\lambda_1,\lambda_2,…,\lambda_d’)$，令$\tilde V$表示相应的特征向量矩阵，则$Z=\tilde\Lambda^{1/2}\tilde V^T\in\mathbb{R}^{d’\times m}$

• 欲获得低维子空间，最简单的是对原始高维空间进行线性变换。给定$d$维空间中的样本$X=(x_1,x_2,…,x_m)\in\mathbb{R}^{d\times m}$，变换之后得到$d’\ll d$维空间中的样本$Z=W^TX$，其中$W\in\mathbb{R}^{d\times d’}$是变换矩阵，$Z\in\mathbb{R}^{d’\times m}$是样本在新空间中的表达。
  • 变换矩阵$W$可视为$d’$个$d$维基向量，$z_i=W^Tx_i$是第$i$个样本与这$d’$个基向量分别做内积而得到的$d’$维属性向量。
  • $z_i$是原属性向量$x_i$在新坐标系${w_1,w_2,…,w_{d’}}$中的坐标向量。若$w_i$与$w_j（i\neq j）$正交，则新坐标系是一个正交坐标系，此时$W$为正交变换。新空间中的属性是原空间中属性的线性组合。
• 基于线性变换来进行降维的方法称为线性降维方法。

10.3 主成分分析

• 主成分分析（Principal Component Analysis，简称PCA）是常见的一种降维方法。

• 对于正交属性空间中的样本点，使用超平面对所有样本进行恰当表达：

  • 最近重构性：样本点到这个超平面的距离都足够近；
  • 最大可分性：样本点在这个超平面上的投影能尽可能分开。

• 基于最近重构性和最大可分性，能分别得到主成分分析的两种等价推导。

• 最近重构性：

  • 假定数据样本进行了中心化，即$\sum_ix_i=0$；
  • 假定投影变换后得到的新坐标系为${w_1;w_2;…;w_d}$，其中$w_i$是标准正交基向量，$\lVert w_i\rVert_2=1$，$w_i^Tw_j=0(i\neq j)$。
  • 若丢弃新坐标系中的部分坐标，即将维度降低到$d’\ll d$，则样本点$x_i$在低维坐标系中的投影是$z_i=(z_{i1};z_{i2};…;z_{id’})$，其中$z_{ij}=w_j^Tx_i$是$x_i$在低维坐标系下第$j$维的坐标。
  • 若基于$z_i$来重构$x_i$，则会得到$\hat x_{i=}\sum_{j=1}^{d’}z_{ij}w_j$
  • 考虑整个训练集，原样本点$x_i$与基于投影重构的样本点$\hat x_i$之间的距离为：$\sum_{i=1}^m\lVert \sum_{j=1}^d’z_{ij}w_j-x_i\rVert_2^2=\sum_{i=1}^mz_i^Tz_i-2\sum_{i=1}^mz_i^TW^Tx_i+const \propto tr(W^T(\sum_{i=1}^mx_ix_i^T)W)$
  • 上式可以被最小化，考虑到$w_i$是标准正交基，$\sum_ix_ix_i^T$是协方差矩阵，得到：$\mathop{min}\limits_{W}-tr(W^TXX^TW)$，$s.t. W^TW=I$，这就是主成分分析的优化目标。

• 最大可分性：

  • 样本点$x_i$在新空间中超平面超平面上的投影是$W^Tx_i$，若所有样本点的投影尽可能分开，则应该使投影后样本点的方差最大化。
  • 投影后样本点的方差是$\sum_iW^Tx_ix_i^TW$，优化目标可写为：$\mathop{max}\limits_{W}tr(W^TXX^TW)$，$s.t. W^TW=I$

  

10.4 核化线性降维

• 线性降维方法假设从高维空间到低维空间的函数映射是线性的。
• 非线性降维的一种常用方法：基于核技巧对线性降维方法进行“核化”（kernelized）。
• 核主成分分析（Kernelized PCA）：
  • 假定在高维特征空间中把数据投影到由$W$确定的超平面上，即PCA欲求解：$(\sum_{i=1}^mz_iz_i^T)W=\lambda W$
  • 其中$z_i$是样本点$x_i$在高维特征空间中的像。$W=\frac1\lambda(\sum_{i=1}^mz_iz_i^T)W=\sum_{i=1}^mz_i\frac{z_i^TW}{\lambda}=\sum_{i=1}^mz_i\alpha_i$，其中$\alpha_i=\frac1\lambda z_i^TW$。
  • 假定$z_i$是由原始属性空间中的样本点$x_i$通过映射$\phi$产生，即$z_i=\phi(x_i),i=1,2,…,m$。若$\phi$能被显示表达出来，则通过它将样本映射至高位特征空间，再在特征空间中实施PCA即可。$(\sum_{i=1}^m\phi(x_i)\phi(x_i)^T)W=\lambda W$
  • $W=\sum_{i=1}^m\phi(x_i)\alpha_i$
  • 引入核函数$\kappa(x_i,x_j)=\phi(x_i)^T\phi(x_j)$，化简得$KA=\lambda A$，其中$K$为$\kappa$对应的核矩阵，$K_{ij}=\kappa(x_i,x_j),A=(\alpha_i;\alpha_2;…;\alpha_m)$

10.5 流形学习

• 流形学习是借鉴了拓扑流形概念的降维方法
  • 流形式在局部与欧式空间同胚的空间。
  • 流形具有欧氏空间的性质，能用欧氏距离来进行距离计算。
• 低维流形嵌入到高维空间中，数据样本在高维空间的分布虽然看上去非常复杂，但在局部上仍具有欧式空间的性质。
  • 在局部建立降维映射关系，设法将局部映射关系推广到全局。

10.5.1 等度量映射

• 等度量映射（Isometric Mapping，简称Isomap）：
  • 基本出发点：低维流形嵌入到高维空间之后，直接在高维空间中计算直线距离具有误导性，因为高维空间中的直线距离在低维嵌入流形上是不可达的。

• 计算测地距离：
  • 利用流形在局部上与欧式空间同胚的性质。
  • 对每个点基于欧氏距离找出其近邻点，然后就能建立一个近邻连接图，图中近邻点之间存在连接，而非近邻点之间不存在连接。
  • 计算两点之间测地线距离的问题，转变为计算近邻图上两点之间的最短路径问题。
• Isomap仅是得到了训练样本在低维空间的坐标，对新样本，需要将其映射到低维空间：
  • 将训练样本的高维空间坐标作为输入、低维空间坐标作为输出，训练一个回归学习器来对新样本的低维空间坐标进行预测。
  • 上述方法仅为权宜之计。
• 构建近邻图：
  • 指定近邻点的个数，$k$近邻图。
  • 指定距离阈值$\epsilon$，距离小于$\epsilon$的点被认为是近邻点，$\epsilon$近邻图。

10.5.2 局部线性嵌入

• 局部线性嵌入（Locally Linear Embedding，简称LLE）试图保持邻域内样本之间的线性关系。

  • 假定样本$x_i$的坐标能通过它的邻域样本$x_j,x_k,x_l$的坐标通过线性组合而重构出来，即$x_i=w_{ij}x_j+w_{ik}x_k+w_{il}w_l$
  • LLE希望上述关系能够在低维空间中得到保持。

  

• LLE先为每个样本$x_i$找到其近邻下标集合$Q_i$，然后计算出基于$Q_i$中的样本点对$x_i$进行现行重构的系数$w_i$：$\mathop{min}\limits_{w_1,w_2,…,w_m}\sum_{i=1}^m\lVert x_i-\sum_{j\in Q_i}w_{ij}x_j\rVert_2^2$，$s.t. \sum_{j\in Q_i}w_{ij}=1$

  • $x_i$和$x_j$均为已知，令$C_{jk}=(x_i-x_j)^T(x_i-x_k)$
  • $w_{ij}$有闭式解，$w_{ij}=\frac{\sum_{k\in Q_i}C_{jk}^{-1}}{\sum_{l,s\in Q_i}C_{ls}^{-1}}$
  • LLE在低维空间中保持$w_i$不变，于是$x_i$对应的低维空间坐标$z_i$可通过下式求解：$\mathop{min}\limits_{z_1,z_2,…,z_m}\sum_{i=1}^m\lVert z_i-\sum_{j\in Q_i}w_{ijz_j}\rVert_2^2$
    • $z_j$的坐标需要确定

10.6 度量学习

• 对高维数据进行降维的主要目的是希望找到一个合适的低维空间，在此空间中进行学习能比原始空间性能更好。

• 度量学习（metric learning）的基本动机：直接尝试“学习”出一个合适的距离度量。

  • 必须有一个便于学习的距离度量表达式。

• 对两个$d$维样本$x_i$和$x_j$，它们之间的平方欧氏距离为：$dist^2{ed}(x_i,x_j)=\lVert x_i-x_j\rVert^2_2=dist^2{ij,1}+dist^2{is,2}+…+dist^2{ij,d}$

  • $dist^2_{ij,k}$表示$x_i$与$x_j$在第$k$维上的距离。
  • 若假定不同属性的重要性不同，可引入属性权重$w$，得到：$dist^2{wed}(x_i,x_j)=\lVert x_i-^x_j\rVert=w_1·dist^2{ij,1}+w_2·dist^2{ij,2}+…+w_d·dist^2{jk,d}=(x_i-x_j)^TW(x_i-x_j)$
    • $w_i\geq 0,W=diag(w)$是一个对角阵，$(W)_{ii}=w_i$
  • $W$可以通过学习确定：
    • $W$的非对角元素均为零，坐标轴是正交的，即属性之间无关。
    • 现实中问题往往不是这样。因此$W$需要替换为一个普通的半正定对阵矩阵$M$，得到马氏距离（Mahalanobis distance）：$dist^2_{mah}(x_i,x_j)=(x_i-x_j)^TM(x_i-x_j)=\lVert x_i-x_j\rVert^2_M$
      • $M$亦称度量矩阵，度量学习即是对$M$进行学习。
      • 为了保持距离非负且对称，$M$必须是（半）正定对阵矩阵，即必有正交基$P$使得$M$能写为$M=PP^T$

• 对$M$进行学习需要设置一个目标：

  • 假定希望提高近邻分类器 的性能，则可将$M$直接嵌入到近邻分类器的评价指标中。
  • 近邻分类器在进行判别时通常使用多数投票法，邻域内的每个样本投1票，邻域外的样本投0票。
  • 对任意样本$x_j$，它对$x_i$结果分类影响的概率为：$p_{ij}=\frac{exp(-\lVert x_i-x_j\rVert^2M)}{\sum{l}exp(-\lVert x_i-x_l\rVert^2_M)}$
    • 当$i=j$时，$p_{ij}$最大。
    • $x_j$对$x_j$的影响随着它们之间距离的增大而减小。
  • 以留一法（LOO）正确率最大化为目标，可计算$x_i$的留一法正确率，即它被自身之外的所有样本正确分类的概率为：$p_i=\sum_{j\in\Omega_i}p_{ij}$
    • 其中$\Omega_i$表示与$x_i$属于相同类别的样本的下标合集。
    • 整个样本集上的留一法正确率为：$\sum_{i=1}^mp_i=\sum_{i=1}^m\sum_{j\in\Omega_i}p_{ij}$
  • NCA的优化目标为：$\mathop{min}\limits_{P}\text{ }1-\sum_{i=1}^m\sum_{j\in\Omega_i}\frac{exp(\lVert P^Tx_i-P^Tx_j\rVert^22)}{\sum{l}exp(-\lVert P^Tx_i-P^Tx_l\rVert^2_2)}$
    • 求解上式即可得到最大化近邻分类器LOO真确率的距离度量矩阵M。

• Previous
  第九章 聚类
• Next
  第一周-一元线性回归