多维放缩MDS算法

多维放缩MDS算法

在线性代数中我们接触到embedding(嵌入)这一术语,表示从高维到低维空间。考虑一个高维空间中的样本集在低维空间中的形态。

“embedding”也应用在计算机图形学的参数化领域中。

问题

给定高维空间$\mathbb{R}^n$中的$m$个样本点为$\{X_i\}_{i=1}^m $,考虑是否可以将$m$个样本嵌入到低维空间$\mathbb{R}^{d}$,$d< n$,使得高维空间中两样本点的度量距离在低维空间中保持不变。

embedding

分析

设高维空间中样本点${ X}_i$在低维空间中表示为${ Z}_i$,要保证度量距离不变,即:
$$
\Vert {X}_i-{ X}_j\Vert=\Vert { Z}_i-{ Z}_j\Vert\qquad i,j=1,2,\dots,m
$$

将等式(1)平方得到:
$$
\Vert {X}_i-{ X}_j\Vert^2=\Vert { Z}_i\Vert^2+\Vert { Z}_j\Vert^2-2{ Z}_i^{ T}{ Z}_j
$$

令${ B}={ Z}^{ T}{ Z}\in\mathbb{R}^{m\times m}$表示低维空间中样本的内积矩阵,内积矩阵第$i$行第$j$列元素为$B_{i,j}=Z_i^{\rm T}Z_j$,用$D$表示样本在原始空间中的距离矩阵,其中$D_{i,j}=\Vert X_i-X_j\Vert$,
$$
D_{i,j}^2=B_{i,i}+B_{j,j}-2B_{i,j}
$$

如果得到满足上式约束的矩阵${ B}$,假定${ B}$含有$k$个非零特征值,分别为$\lambda_1,\lambda_2,\dots,\lambda_k$且满足$\lambda_i\ge\lambda_j,i< j$,则有${ B}={ V\Lambda V^T}$,其中${ \Lambda}=diag\{\lambda_1,\lambda_2,\dots,\lambda_k\}$,${ V}$的第$i$列是特征值$\lambda_i$对应的特征向量。则有${ Z}={ \Lambda}^{\frac{1}{2}}{ V}^{ T}\in\mathbb{R}^{k\times m}$,如果$k< n$,则实现距离不变的降维。下面考虑如何求解满足上式约束的内积矩阵。

内积矩阵的推导

考虑低维样本的中心为原点,即$\sum_iZ_i=0$,根据第二等式有:
$$
\sum_iD_{i,j}^2=\sum_iB_{i,i}+mB_{j,j}
$$

$$
\sum_{i,j}D_{i,j}^2 =2m\sum_iB_{i,i}
$$

有:
$$
B_{j,j}=\frac{\sum_iD_{i,j}^2}{m}-\frac{\sum_{i,j}D_{i,j}^2}{2m^2}
$$

代入公式有:
$$
B_{i,j} = -\frac{1}{2}(D_{i,j}^2-\frac{\sum_jD_{i,j}^2}{m}+\frac{\sum_{i,j}D_{i,j}^2}{m^2}-\frac{\sum_iD_{i,j}^2}{m})
$$

由此则可得到内积矩阵。

距离不必严格相等的嵌入

特别地,在现实应用为了降低维度,多数情况下会损失一部分信息。即,如果目标空间维度$d$小于非零特征值的个数,则做不到距离严格相等。此时取${ \Lambda_*}=diag\{\lambda_1,\lambda_2,\dots,\lambda_d\}$,对应的特征向量矩阵为$V_*$。即$B\approx{ V_*\Lambda_*V^T_*}$。低维空间中的样本可表示为

$$
Z=\Lambda_*^{\frac{1}{2}}V^T_*\in\mathbb{R}^{d\times m}
$$

简单应用$\mathbb{R}^3\longmapsto\mathbb{R}^2$

embedding

发表评论

邮箱地址不会被公开。 必填项已用*标注