机器学习

1、低维嵌入

事实上，在高维情形下出现的数据样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的严重障碍，被称为“维数灾难”。缓解维数灾难的一个重要途径是降维，即通过某种数学变换将原始高维属性空间转变为一个低维的“子空间”，在这个子空间中样本密度大幅度提高，计算距离也变得更加容易。

2、多维放缩（MDS-multiple dimensional scaling）

若要求原始空间样本之间的距离在低维空间中得以保持，就得到一种典型的降维方法MDS。

假定 $m$ 个样本在原始空间的距离矩阵为 $D \in \mathbb{R}^{m \times m}$ ,其第 $i$ 行 $j$ 列的元素 $Dist_{ij}$ 为样本 $\mathbf{x}_i$ 到 $\mathbf{x}_j$ 的距离。我们的目标是获得样本在低维 $d^\prime$ 维空间的表示 $\mathbf{Z} \in \mathbb{R}^{d^\prime \times m},d^\prime \le d$ ，且任意两个样本在 $d^\prime$ 维空间的欧氏距离等于原始空间的欧式距离，即 $||z_i - z_j|| = Dist_{ij}$ 。其中

$\mathbf{Z} = \left[ \begin{matrix} z_{11} & z_{12} & z_{13} & \cdots & z_{1m}\\ z_{21} & z_{22} & z_{23} & \cdots & z_{2m} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ z_{d^\prime1} & z_{d^\prime2} & z_{d^\prime3} & \cdots & z_{d^\prime m} \end{matrix} \right] = \left[ \begin{matrix} \mathbf{z_1} & \mathbf{z_2} & \mathbf{z_3} & \cdots & \mathbf{z_m} \end{matrix} \right] \\$

$\mathbf{z_i} = \left[ \begin{matrix} z_{1i} \\ z_{2i} \\ \vdots \\ z_{d^\prime i} \end{matrix} \right]$
表明第i个样本在 $d^\prime$ 空间的坐标

令 $\mathbf{B} = \mathbf{Z}^{\mathrm{T}}\mathbf{Z} \in \mathbb{R}^{m \times m}$ ,其中 $\mathbf{B}$ 为降维后样本的内积矩阵， $b_{ij} = \mathbf{z}_i^\mathrm{T}\mathbf{z_j}$ ,有

$\mathbf{B} = \left[ \begin{matrix} \mathbf{z_1^{\mathrm{T}}} \\ \mathbf{z_2^{\mathrm{T}}} \\ \vdots \\ \mathbf{z_m^{\mathrm{T}}} \\ \end{matrix} \right] \left[ \begin{matrix} \mathbf{z_1} & \mathbf{z_2} & \mathbf{z_3} & \cdots & \mathbf{z_m} \end{matrix} \right] = \left[ \begin{matrix} \mathbf{z_1}^\mathrm{T}\mathbf{z_1} & \mathbf{z_1}^\mathrm{T}\mathbf{z_2} & \mathbf{z_1}^\mathrm{T}\mathbf{z_3} & \cdots & \mathbf{z_1}^\mathrm{T}\mathbf{z_m} \\ \mathbf{z_2}^\mathrm{T}\mathbf{z_1} & \mathbf{z_2}^\mathrm{T}\mathbf{z_2} & \mathbf{z_2}^\mathrm{T}\mathbf{z_3} & \cdots & \mathbf{z_2}^\mathrm{T}\mathbf{z_m} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ \mathbf{z_m}^\mathrm{T}\mathbf{z_1} & \mathbf{z_m}^\mathrm{T}\mathbf{z_2} & \mathbf{z_m}^\mathrm{T}\mathbf{z_3} & \cdots & \mathbf{z_m}^\mathrm{T}\mathbf{z_m} \end{matrix} \right] = \left[ \begin{matrix} b_{11} & b_{12} & b_{13} & \cdots & b_{1m} \\ b_{21} & b_{22} & b_{23} & \cdots & b_{2m} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ b_{m1} & b_{m2} & b_{m3} & \cdots & b_{mm} \\ \end{matrix} \right] \\ Dist_{ij}^2 = ||\mathbf{z_i} - \mathbf{z_j}||^2 = (\mathbf{z_i} - \mathbf{z_j})^2 = ||\mathbf{z_i}||^2 + ||\mathbf{z_j}||^2 - 2\mathbf{z_i}^\mathrm{T}\mathbf{z_j} = b_{ii} + b_{jj} -2b_{ij}$

为了便于讨论，令降维后的样本 $\mathbf{Z}$ 被中心化，那么就可以得到 $\mathbf{B}$ 的行于列之和均为零，即 $\sum^{m}_{i=1}b_{ij} = \sum_{j=1}^{m}b_{ij} = 0$ 。易知道：
$Dist_{\cdot j}^2 = \sum_{i=1}^m Dist_{ij}^2 = \sum_{i=1}^m b_{ii} + b_{jj} -2b_{ij} = \sum_{i=1}^m b_{ii} + b_{jj} -2 \sum_{i=1}^mb_{ij} = tr(\mathbf{B}) + mb_{jj} \\$
$Dist_{i\cdot}^2 =\sum_{j=1}^m Dist_{ij}^2 = \sum_{j=1}^m b_{ii} + b_{jj} -2b_{ij} = \sum_{j=1}^m b_{ii} + b_{jj} -2 \sum_{j=1}^mb_{ij} = tr(\mathbf{B}) + mb_{ii} \\$
$Dist_{\cdot \cdot}^2 =\sum_{i=1}^{m}\sum_{j=1}^{m}Dist_{ij}^2 = \sum_{i=1}^{m} tr(\mathbf{B})+mb_{ii} = m\times tr(\mathbf{B}) + m \times tr(\mathbf{B}) = 2m\times tr(\mathbf{B})$
其中 $tr(\cdot)$ 表示矩阵的迹， $tr(\mathbf{B}) = \sum_{i=1}^{m} b_{ii}$ .则
$b_{ij} = - \frac{1}{2} ( \frac{Dist_{\cdot \cdot}^2}{m^2} - \frac{Dist_{i\cdot}^2}{m} - \frac{Dist_{\cdot j}^2}{m} + Dist_{ij}^2 ) = - \frac{1}{2} [\frac{2}{m}tr(\mathbf{B})-\frac{1}{m}tr(\mathbf{B})-b_{ii} -\frac{1}{m}tr(\mathbf{B})-b_{jj} + b_{ii} + b_{jj} -2b_{ij} ]$
因为所有的 $Dist_{ij}$ 都是已知的，那么 $Dist_{\cdot\cdot}^2,Dist_{i\cdot}^2,Dist_{\cdot j}^2$ 都可以算出来，那么就可以根据原空间的距离矩阵 $\mathbf{D}$ 求取 $d^\prime$ 维空间的内积矩阵 $\mathbf{B}$ 。

接下来对 $\mathbf{B}$ 做特征分解就可以啦， $\mathbf{B} = \mathbf{V\Lambda V^{\mathrm{T}}}$ ,其中 $\Lambda = diag(\lambda_1,\lambda_2,\cdots,\lambda_d)$ 为特征值构成的对角矩阵， $\lambda_1 \ge \lambda_2 \ge \cdots \lambda_d$ , $\mathbf{V}$ 为特征向量矩阵，假定其中有 $d^\star$ 个非零特征值，它们构成对角矩阵 $\Lambda_\star = diag(\lambda_1,\lambda_2,\cdots,\lambda_{d^\star})$ ，令 $\mathbf{V_\star}$ 表示相应的特征向量矩阵，则 $\mathbf{Z}$ 可表示为
$\mathbf{Z} = \Lambda_{\star}^{\frac{1}{2}}\mathbf{V_\star^{\mathrm{T}}} \in \mathbb{R}^{d^\star \times m}$
在现实应用中为了有效的降维，往往不需要降维后的空间距离与原空间相同，大致相近即可，此时可取 $d^{\prime}(d^{\prime} \ll d)$ 个最大特征值构成的对角矩阵 $\widetilde{\Lambda} = diag(\lambda_1,\lambda_2,\cdots,\lambda_{d^{\prime}})$ ,令 $\widetilde{\mathbf{V}}$ 表示相应的特征向量矩阵，则 $\mathbf{B}$ 可以表示为
$\mathbf{Z} = \widetilde{\Lambda}^{\frac{1}{2}}\widetilde{\mathbf{V}}^{\mathrm{T}} \in \mathbb{R}^{d^\prime \times m}$

1、低维嵌入

2、多维放缩（MDS-multiple dimensional scaling）

推荐阅读更多精彩内容