Low-dimension Embedding详解

第四十二次写博客，本人数学基础不是太好，如果有幸能得到读者指正，感激不尽，希望能借此机会向大家学习。机器学习任务中的“维数灾难”（Curse of Dimensionality）会导致高维样本空间中的样本稀疏与距离计算困难等问题，为了解决该问题，本文介绍一种被称为“多维缩放”（Multiple Dimensional Scaling，简称MDS）的降维手段。

  在k近邻学习中存在这样一条假设，“给定测试样本$\bf{x}$x，若其最近邻样本为$\bf{z}$z，则最近邻分类器出错的概率就是$\bf{x}$x与$\bf{z}$z类别标记不同的概率，即

$P(err)=1-\sum_{c\in{y}}{P(c|{\bf{x}})P(c|{\bf{z}})}$P(err)=1−c∈y∑​P(c∣x)P(c∣z)

对于任意样本点，总能在任意近的范围内找到上式中的训练样本$\bf{z}$z”，要满足上述的假设条件需要训练样本的采样密度足够大，或者称为“密采样”，然而这个假设在现实任务中很难满足，尤其是当属性维数成千上万时，要满足密采样条件所需的样本数目是无法达到的“天文数字”，另外高维样本空间中的距离计算也是一个难点。
  上面提到的，在高维样本空间中的样本稀疏与距离计算困难等问题，是所有机器学习方法共同面临的严重障碍，被称为“维数灾难”（Curse of Dimensionality），缓解这种问题的一个重要途径就是“降维”（Dimension Reduction），也称为“维数约减”，即通过某种数学变换使得高维属性空间转变为一个低维“子空间”（Subspace），在这个样本空间中样本密度将大大提高，而且距离计算也变得更加容易，这是由于与学习任务密切相关的也许只是数据集的某个低维分布，即高维空间中的一个低维“嵌入”（Embedding），基于密度聚类算法中的子空间聚类可以看做是一种简单降维手段的应用。

图1 高维样本空间的子空间

为了将原始空间中样本点之间的距离在低维空间中得到保持，我们可以使用一种称为“多维缩放”（Multiple Dimensional Scaling，简称MDS）的降维手段，下面对MDS方法进行描述。
  假定$m$m个样本点在原始空间中的距离矩阵为$D\in{\Bbb{R}^{m\times{m}}}$D∈Rm×m，其中元素$dist_{ij}$distij​为样本点${\bf{x}}_i$xi​与${\bf{x}}_j$xj​之间的距离，MDS的目标是习得样本点在$d'$d′维空间中的表示${\bf{z}}\in{\Bbb{R}^{d'\times{m}}}$z∈Rd′×m，其中$d'\ll{d}$d′≪d，且任意两个样本点在$d'$d′维空间之间的欧氏距离等于原始空间中这两个样本点之间的距离，即$||{\bf{z}}_{i}-{\bf{z}}_{j}||=dist_{ij}$∣∣zi​−zj​∣∣=distij​。如果令${\bf{B}}={\bf{Z}}^{T}{\bf{Z}}\in{\Bbb{R}^{m\times{m}}}$B=ZTZ∈Rm×m表示$d'$d′维空间中样本点的内积矩阵，其中元素$b_{ij}={\bf{z}}_{i}^{T}{\bf{z}}_{j}$bij​=ziT​zj​，那么上述条件可以表示为

$dist_{ij}^{2}=||{\bf{z}}_{i}||^{2}+||{\bf{z}}_{j}||^{2}-2{\bf{z}}_{i}^{T}{\bf{z}}_{j} \\ =b_{ii}+b_{jj}-2b_{ij} \tag{1}$distij2​=∣∣zi​∣∣2+∣∣zj​∣∣2−2ziT​zj​=bii​+bjj​−2bij​(1)

现在将降维后的样本点集$\bf{Z}$Z进行中心化，即$\sum_{i=1}^{m}{{\bf{z}}_{i}}=0$∑i=1m​zi​=0，那么矩阵$\bf{B}$B的行与列之和均为零，即$\sum_{i=1}^{m}{b_{ij}}=\sum_{j=1}^{m}{b_{ij}}=0$∑i=1m​bij​=∑j=1m​bij​=0，那么可以推出

$\sum_{i=1}^{m}{dist_{ij}^{2}}={\rm{tr}}({\bf{B}})+mb_{jj} \\ \sum_{j=1}^{m}{dist_{ij}^{2}}={\rm{tr}}({\bf{B}})+mb_{ii} \\ \sum_{i=1}^{m}{\sum_{j=1}^{m}{dist_{ij}^{2}}}=2m{\rm{tr}}({\bf{B}}) \tag{2}$i=1∑m​distij2​=tr(B)+mbjj​j=1∑m​distij2​=tr(B)+mbii​i=1∑m​j=1∑m​distij2​=2mtr(B)(2)

其中，$\rm{tr}(\cdot)$tr(⋅)代表矩阵的迹（trace），$\rm{tr}({\bf{B}})=\sum_{i=1}^{m}{||{\bf{z}}_{i}||^{2}}$tr(B)=∑i=1m​∣∣zi​∣∣2，令

$dist_{i\cdot}^{2}=\frac{1}{m}\sum_{j=1}^{m}{dist_{ij}^{2}} \\ dist_{\cdot{j}}^{2}=\frac{1}{m}\sum_{i=1}^{m}{dist_{ij}^{2}} \\ dist_{\cdot\cdot}^{2}=\frac{1}{m^2}\sum_{i=1}^{m}{\sum_{j=1}^{m}{dist_{ij}^{2}}} \tag{3}$disti⋅2​=m1​j=1∑m​distij2​dist⋅j2​=m1​i=1∑m​distij2​dist⋅⋅2​=m21​i=1∑m​j=1∑m​distij2​(3)

由式（1）~（3）可以求得

$b_{ij}=-\frac{1}{2}(dist_{ij}^{2}-dist_{i\cdot}^{2}-dist_{\cdot{j}}^{2}+dist_{\cdot\cdot}^{2}) \tag{4}$bij​=−21​(distij2​−disti⋅2​−dist⋅j2​+dist⋅⋅2​)(4)

由上式即可通过原始空间中的距离矩阵$\bf{D}$D求得降维后的内积矩阵$\bf{B}$B，然后对$\bf{B}$B做特征分解，得到${\bf{B}}={\bf{V}}{\bf{\Lambda}}{\bf{V}}^{T}$B=VΛVT，其中${\bf{\Lambda}}={\rm{diag}}(\lambda_{1},\lambda_{2},\dots,\lambda_{d})$Λ=diag(λ1​,λ2​,…,λd​)是特征值（$\lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{d}$λ1​≥λ2​≥⋯≥λd​）构成的对角矩阵，$\bf{V}$V是特征向量矩阵。假设有$d^{*}$d∗个非零的特征值，他们构成的对角矩阵${\bf{\Lambda}}_{*}={\rm{diag}}(\lambda_{1},\lambda_{2},\dots,\lambda_{d^{*}})$Λ∗​=diag(λ1​,λ2​,…,λd∗​)，令${\bf{V}}_{*}$V∗​表示相应的特征向量矩阵，那么样本点在$d^{*}$d∗维空间下的表示可以写做

${\bf{Z}}={\bf{\Lambda}}_{*}^{1/2}{\bf{V}}_{*}^{T}\in{\Bbb{R}^{d^*\times{m}}}$Z=Λ∗1/2​V∗T​∈Rd∗×m

现实应用中为了有效的降维，可以仅仅取前$d'\ll{d}$d′≪d个最大特征值构成的对角矩阵${\tilde{\bf{\Lambda}}}={\rm{diag}}(\lambda_{1},\lambda_{2},\dots,\lambda_{d^{'}})$Λ~=diag(λ1​,λ2​,…,λd′​)，令${\bf{V}}'$V′表示相应的特征向量矩阵，那么样本点在$d'$d′维空间下的表示可以写做

${\bf{Z}}={\tilde{\bf{\Lambda}}}^{1/2}{\tilde{\bf{V}}}^{T}\in{\Bbb{R}^{d'\times{m}}} \tag{5}$Z=Λ~1/2V~T∈Rd′×m(5)

下面是MDS的伪代码

图2 MDS伪代码

  最简单的降维方法是采用线性变换，将原始空间（$d$d维）中的样本点${\bf{x}}_{i}$xi​属性向量通过下式转化为低维（$d'$d′维）空间中的对应属性向量${\bf{z}}_{i}$zi​，

${\bf{z}}_{i}={\bf{W}}^{T}{\bf{x}}_{i}$zi​=WTxi​

其中${\bf{W}}\in{\Bbb{R}^{d'\times{}d'}}$W∈Rd′×d′是变换矩阵，若${\bf{W}}$W中任意两个不同的向量${\bf{w}}_{i}$wi​和${\bf{w}}_{j}$wj​正交，那么就成为正交变换，得到的新坐标系称为正交坐标系。对于降维效果的评估，一般是比较降维前后学习器的性能，还可以将维度约减到二维或者三维以便直接观察。

---

参考资料

【1】《机器学习》周志华