10-10 10:23 阅读 111

15.降维技术（Dimensionality Reduction）

15.降维技术

当数据有繁杂大量的特征的情况下，我们更倾向于去降低其维数，或去找到一个在保持属性的同时也能够低维表示的方法。降维(或流形学习)技术的关键论点是:

计算:首先要进行预处理步骤——压缩原始数据，以加快后续数据操作。
可视化:将输入数据映射到二维或三维空间，可视化数据进行探索性分析。
特征提取:希望生成更小、更有效或有用的特征集。

降维的好处通常是通过模拟数据来说明的，比如瑞士卷（Swiss Roll）数据集的生成。在本例中，输入数据 (如图 15.1a)所示是三维的，但它位于一个二维流形上，该流形在二维空间中“展开”，如图15.1b所示。需要注意的是，在实践中很少遇到精确的低维流形。因此，这个理想化的例子更有助于说明降维的概念，而不是验证降维算法的有效性。

降维可以形式化如下。考虑一个示例 $S=(\mathcal S=($ $X_{_1}$ , . . . . . . , $X_{_m}$ ) , 一个特征映射是 $Φ\Phi$ $:x\mathcal :x$ $→\rightarrow$ $Rn\mathbb{R}^{n}$ 和数据矩阵 $X\mathcal X$ $∈\in$ $RN×m\mathbb{R}^{N \times m}$ 定义为（ $Φ\Phi$ （ $x1\mathcal x_{_1}$ ), . . . . , $Φ\Phi$ （ $xm\mathcal x_{_m}$ ). 第一个数据点用表示 $X_{_i}$ $=\mathcal =$ $Φ\Phi$ （ $xi\mathcal x_{_i}$ ),或者 $x\mathcal x$ 的第 $i\mathcal i$ 列，它是 $n\mathcal n$ 维向量。降维技术的主要目标是找到， $K\mathcal K$ $≤\leq$ $N\mathcal N$ , 这个问题 $k\mathcal k$ 维的数据表示, $Y\mathcal Y$ $∈\in$ $Rk×m\mathbb{R}^{k\times m}$ 在某种程度上忠实于原始的表示法 $x\mathcal x$ 。在本章中，我们将讨论解决这个问题的各种技术。我们首先介绍了最常用的降维技术，它被称为主成分分析(PCA)。然后我们介绍了一个内核化版本的PCA (KPCA)，并向我们展示了KPCA和流形学习之间的算法联系
第十五章降维

$(a)\mathcal (a)$ $(b)\mathcal (b)$
图 $15.1\mathcal 15.1$
“瑞士卷”数据集。 $(a)\mathcal (a)$ 表示高维。 $(b)\mathcal (b)$ 表示低维。

最后，我们介绍了Johnson-Lindenstrauss引理，这是一个经典的理论结果，启发了各种基于随机投影概念的降维方法。本章的讨论依赖于附录A中回顾的基本矩阵性质。

$15.1\mathcal 15.1$ 主成分分析

修正 $k\mathcal k$ $∈\in$ $[N]\left [ N \right ]$ 让 $x\mathcal x$ 成为以均值为中心的数据矩阵也就是说， $∑mi=1\sum _{m}^{i=1}$ 定义 $Pk\mathcal P_{k}$ 作为N维秩正交投影矩阵集。主成分分析将多维输入数据投影到K维线性子空间的方法这使构造误差最小化，即平方距离的和在原始数据和预测数据之间。因此，PCA算法是可行的完全由正交投影矩阵解 $p∗\mathcal p\ast$ 定义以下各项最小化问题：

$minp∈pk∥px−x∥F2\underset{p \in \mathcal p_{k}}{\mathbb min} \left \| \mathcal px-x \right \|_{\mathcal F}^{\mathcal 2}$

$(15.1)\mathcal (15.1)$
下面的定理表明，主成分分析与每个主成分的投影一致样本协方差矩阵K个顶部奇异向量上的数据点，即。， $C=\mathcal C=$ $1mXX⊤\frac{1}{m}XX^{\top}$ 为以均值为中心的数据矩阵。图15.2说明了PCA背后的基本直觉，显示了具有高度相关特征的二维数据点如何可以用一维表示更简洁地表示，这种一维表示捕获了数据中的大多数方差。定理15.1假设 $p∗∈pk\mathcal p\ast \in p_{k}$ 为PCA解，即正交投影（15.1）的矩阵解。然后， $p∗=UkUK⊤\mathcal p\ast = U_{k}U_{K}^{\top }$ ，其中 $Uk∈RN×kU_{k}\in \mathbb R^{N \times k}$ 是由 $C=\mathcal C=$ $1mXX⊤\frac{1}{m}XX^{\top}$ 的前k个奇异向量形成的矩阵，即样本协方差矩阵对应于 $X\mathcal X$ 。此外， $X\mathcal X$ 的关联K维表示是由 $Y=UK⊤X\mathcal Y= U_{K}^{\top }X$ 给出。

15.2核主成分分析(KPCA)

证明：设 $P=P⊤\mathcal P=P^{\top}$ 为正交投影矩阵。根据定义Frobenius范数、矩阵的迹的线性和 $p\mathcal p$ 为幂等元，即 $P2=P\mathcal P^{2}=P$ ，我们观察到
$∥px−x∥F2=Tr[(PX−X)⊤(PX−X)]=Tr[X⊤P2X−2X⊤PX+X⊤X]=−Tr[X⊤PX]+Tr[X⊤X]\left \| \mathcal px-x \right \|_{\mathcal F}^{\mathcal 2}=Tr\left [ \left ( PX-X \right )^{\top }\left ( PX-X \right ) \right ]=Tr\left [ X^{\top }P^{2}X-2X^{\top }PX+X^{\top }X \right ]= - Tr \left [X^{\top}PX\right]+Tr \left [X^{\top}X\right]$
由于 $\left [X^{\top}X\right]$ 是关于 $P\mathcal P$ 的常数，我们有
$argminp∈pk∥px−x∥F2=argminp∈pkTr[X⊤PX]\underset{p \in \mathcal p_{k}}{\mathbb argmin}\left \| \mathcal px-x \right \|_{\mathcal F}^{\mathcal 2}=\underset{p \in \mathcal p_{k}}{\mathbb argmin}Tr\left[X^{\top}PX\right]$ $(15.2)\mathcal (15.2)$
根据 $Pk,P=UUT\mathcal P_{k},P=UU^{T}$ 中正交投影的定义，对于某些 $U\mathcal U$ 包含正交列的。利用矩阵的迹的不变性循环置换和 $U\mathcal U$ 列的正交性，我们有
$Tr[X⊤PX]=Tr[U⊤XX⊤U]=Tr\left[X^{\top}PX\right]=Tr\left [U^{\top}XX^{\top}U\right ]=$ $∑i=1kuiXX⊤ui\overset{k}{\underset{i=1}{\sum }}u_{_i}XX^{\top}u_{i}$
其中 $ui\mathcal u_{i}$ 是 $U\mathcal U$ 的第i列。根据瑞利熵（第 $A.2.3\mathcal A.2.3$ 节），它很明显， $XX⊤XX^{\top}$ 的最大 $k\mathcal k$ 个奇异向量使最右边的和最大化在上面由于 $XX⊤XX^{\top}$ 和 $C\mathcal C$ 仅因比例因子不同而不同，因此它们具有相同的比例因子奇异向量，因此 $U_{k}$ 使这个和最大化，这证明了第一个语句这是定理的一部分。最后，因为 $PX=U_{k}U_{k}^{T}X,Y=U_{k}^{T}X$ 是k维的以 $U_{k}$ 为基向量表示 $X\mathcal X$ 。
根据协方差矩阵的定义， $C\mathcal C$ 的顶部奇异向量是数据中最大方差的方向，相关奇异值为等于这些方差。因此，PCA也可以被视为投射到最大方差子空间。根据这一解释，第一个主成分是从最大方差方向的投影导出的，由下式给出 $C\mathcal C$ 的上奇异向量。类似地，第i个主成分，例如 $1≤i≤k1\leq i\leq k$ ，是从投影到最大方差的第i个方向，受到前i个主成分的正交性约束而得到的−1最大方差的方向（参见练习15.1了解更多详细信息）。
15.2核主成分分析(KPCA)
在前一节中，我们介绍了PCA算法，其中涉及到投影到样本协方差矩阵c的奇异向量上。在这一节中，我们呈现PCA的内核化版本，称为KPCA。在KPCA设置中， $Φ\mathcal \Phi$ 为一个特征映射到一个任意的RKHS（不一定是 $RN\mathbb R^{N}$ ），我们工作专用于内核函数 $K\mathcal K$ ，对应于此函数中的内积RKHS。因此，KPCA算法可以定义为PCA的推广将输入数据投影到RKHS中的顶部主要组件上。我们将利用深层次的数据展示PCA和KPCA之间的关系 $X\mathcal X$ 、 $C\mathcal C$ 和 $K\mathcal K$ 的SVD之间的连接。然后，我们将说明各种流形学习算法可以解释为KPCA的特殊实例。
第15章降维

$(a)\left (a\right )$ $(b)\left (b\right )$
图15.2
主成分分析的例子。(a)二维数据点，具有捕获不同单位测量鞋尺寸的特征。(b)一维表示，通过投射到以均值为中心的数据点的最大主成分(红线)而产生，以捕获数据中最大的方差。
设 $K\mathcal K$ 是在 $χ×χ\chi\times \chi$ 上定义的PDS内核，并将内核矩阵定义为 $K=X⊤X\mathcal K=X^{\top}X$ 。由于 $X$ 允许以下奇异值分解： $X=U∑V⊤,X=U\tiny\sum V^{\top} ,$ $C\mathcal C$ 和 $K\mathcal K$ 可以重写如下：
$C=1mUΛU⊤\mathcal C=\frac{1}{m}U\Lambda U^{\top}$ $K=VΛV⊤\mathcal K=V \Lambda V^{\top}$ $(15.3)\left(15.3\right)$
其中 $Λ=∑2\Lambda=\scriptsize\sum^{2}$ 是 $mC\mathcal mC$ 的奇异值（相当于特征值）的对角矩阵， $U\mathcal U$ 是 $C\mathcal C$ （和 $mC\mathcal mC$ ）的奇异向量（相当于特征向量）的矩阵。
从 $X$ 的奇异值分解开始，请注意右方乘以 $V∑−1V\scriptsize\sum ^{-1}$ 并使用 $Λ\Lambda$ 和 $∑\tiny\sum$ 之间的关系产生 $U=XVΛ−12。此时奇异向量U=XV\Lambda ^{-\tfrac{1}{2}}。此时奇异向量$ u $与奇异值λ/m相关的与奇异值\lambda/m相关的$ C $与Xvλ一致，其中与\frac{X_{v}}{\sqrt{\lambda }}一致，其中$ v $为奇异值与λ相关的k向量。现在修复X=Φ(x)为奇异值与\lambda相关的k向量。现在修复X=\Phi\left(x\right)$ 的任意特征向量 $x∈Xx\in X$ 然后，根据定理15.1中 $y\mathcal y$ 的表达式，通过投影到 $Pu=uu⊤P_{u}=uu^{\top}$ 上导出的 $x\mathcal x$ 的一维表示形式定义为
$x⊤u=x⊤xvλ=Kx⊤vλx^{\top}u=x^{\top}\frac{x_{v}}{\sqrt{\lambda }}=\frac{K_{x}^{\top}v}{\sqrt{\lambda }}$ $(15.4)\left(15.4\right)$
其中 $Kx=(K(x1,x),....,K(xm,x)⊤K_{x}=\left(K(x_{1},x),....,K(x_{m},x\right)^{\top}$ 。如果 $x$ 是其中一个数据点，即 $x=x_{i}$ 或 $1≤i≤m1\leq i\leq m$ ，则 $K_{x}$ 是 $K$ 的第 $i$ 列，且（15.4）可简化如下：
$x⊤u=Kx⊤vλ=λviλ=λvix^{\top}u=\frac{K_{x}^{\top}v}{\sqrt{\lambda }}=\frac{\lambda v_{i}}{\sqrt{\lambda }}=\sqrt{\lambda }v_{i}$ $(15.5)\left(15.5\right)$
其中 $v_{i}$ 是 $v$ 的第 $i$ 个分量。更一般地说，定理15.1的PCA解可以完全由 $K$ ， $v_{1},...,v_{k}$ 的顶奇异向量（或特征向量）和相应的奇异值（或特征值）定义。这个选择基于 $K$ 的PCA解的推导精确定义了KPCA解，通过使用PDS核提供了PCA的泛化（有关核方法的更多详细信息，请参见第6章）。

15.3 KPCA和流形学习

作为非线性降维方法，提出了几种流形学习技术。这些算法隐含地假设高维数据位于输入空间中嵌入的低维非线性流形上或附近。他们的目标是通过寻找一个低维空间来学习这种流形结构，这个低维空间在某种程度上保留了高维输入数据的局部结构。例如，Isomap算法旨在保持所有数据点对之间的近似测地线距离，或沿着流形的距离。其他算法，如拉普拉斯特征映射和局部线性嵌入，只关注保持高维空间中的局部邻域关系。接下来我们将描述这些经典的流形学习算法，然后将它们解释为KPCA的具体实例。

15.3.1 Isomap

用等值线图提取是最能保留的低维数据表示方法它将输入点之间的所有成对距离，由它们的测地线距离测量沿着下面的流形。它近似测地距离，假设 L2 距离为附近的点和远处的点提供了很好的近似值它将距离估计为相邻点之间的一系列跳跃。等值线图算法的工作原理如下：
1.基于L2距离找到每个数据点的最近邻，并构造一个无向邻域图，用G表示，点作为节点，邻域之间的链接作为边。
2.通过使用例如 Floyd-Warshall 算法计算 $G$ 中的所有对最短距离，计算所有节点对 $(i,j)\left (i,j \right )$ 之间的近似测地距离 $Δij\Delta _{ij}$ 。
3.通过执行双重定心，将平方距离矩阵转换为 $\times m$ 相似性矩阵，即计算 $KIso=−12HΔHK_{Iso}=-\frac{1}{2}H\Delta H$ ，其中 $Δ\Delta$ 为平方距离矩阵， $H=Im−1m11⊤H=I_{m}-\frac{1}{m}11^{\top}$ 是定心矩阵， $I_{m}$ 是 $\times m$ 单位矩阵， $1\mathcal 1$ 是所有单位的列向量（有关双定心的更多详细信息，请参见练习15.2）。
4.求最优k维表示， $Y={yi}i=1nY=\left \{ y_{i} \right \}_{i=1}^{n}$ ，这样， $Y=argmin_{_Y}$ ， $∑i,j(∥yi′−yj′∥22−Δij2)\sum _{i,j}\left ( \left \| y_{i}{}'-y_{j}{}' \right \|_{2}^{2}-\Delta _{ij}^{2} \right )$ 。解由下式给出：
$Y=(∑Iso,k)12UIso,k⊤Y=\left ( \sum _{Iso,k} \right )\tfrac{1}{2}U_{Iso,k}^{\top }$ $(15.6)\left(15.6\right)$
其中 $∑Iso,k\sum_{Iso,k}$ 是 $K_{Iso,k}$ 的前k个奇异值的对角矩阵，并且 $U_{Iso,k}$ 是相关的奇异向量。
$K_{Iso,k}$ 自然可以看作是一个核矩阵，从而提供了 Isomap 和 KPCA 之间的简单连接。然而，请注意，只有当 $K_{Iso,k}$ 实际上是正半无限体时，这种解释才有效，这在光滑流形的连续极限中确实如此。

15.3.2拉普拉斯特征映射

拉普拉斯特征映射算法旨在寻找低维表示它很好地保留了由权重矩阵 $W$ 度量的邻域关系。该算法的工作原理如下：
1.查找每个点的最近邻。
2.构造 $W$ ，一个稀疏对称的矩阵 $m×mm\times m$ ，其中 $Wij=exp(−∥xi−xj∥22/σ2)W_{ij}=exp\left ( -\left \| x_{i}-x_{j} \right\|_{2}^{2}/\sigma ^{2} \right )$ 如果 $(xi,xj)\left (x_{i},x_{j} \right )$ 没有位于附近，则结果为0，而 $σ\sigma$ 是缩放参数。
3.构造对角矩阵 $D$ ，使 $Dii=∑jWijD_{ii}=\sum _{j}W_{ij}$
4.通过最小化邻域之间的加权距离找到 $k$ 维表示，如下所示：，
$Y=Y′agrmin∑ijwij∥yi′−yj′∥22Y=\overset{agrmin}{\tiny Y{}'}\underset{ij}{\sum }w_{ij}\left \| y_{i}{}'-y_{j}{}' \right \|_{2}^{2}$ $(15.7)\left ( 15.7 \right )$
该目标函数惩罚映射到远处的邻近输入输出，由权重矩阵 $W$ 测量的“接近度”。该（15.7）中的最小值为 $Y=UL,k⊤Y=U^{\top}_{L,k}$ ，其中 $L = D - W$ 是图Laplacian， $UL,k⊤U^{\top}_{L,k}$ 是L的底k个奇异向量，不包括最后一个奇异向量对应于奇异值0的向量（假设基础邻域图是连通的）。
（15.7）的解也可以解释为求最大奇异向量对于 $L†L^{\dagger}$ ，是 $L\mathcal L$ 的伪逆。德宁 $KL=L†K_{L}=L^{\dagger}$ 因此我们可以看到拉普拉斯作为KPCA实例的特征映射，其中输出维度被归一化具有与设置 $λ=1\lambda =1$ （在15.5中提到）相对应的单位方差。而且,可以看出， $K_{L}$ 是与车辆通勤时间相关联的核心矩阵基础邻域图上的扩散，其中图中的节点i和j是随机行走开始的预期时间节点i，到达节点j，然后返回到节点i。

15.3.3 局部线性嵌入（LLE）

局部线性嵌入（LLE）算法也旨在找到低维保留邻域关系的表示法，如权重矩阵 $W$ 所测量。该算法的工作原理如下：
1.找到每个点的 $t$ 个最近邻。
2. 构造 $W$ ，一个稀疏对称的 $m×mm\times m$ 矩阵，其第 $i$ 行总和为 1，并包含从其 $t$ 个邻居中最优重构 $x_{i}$ 的线性系数。更具体地说，如果我们假设 $W$ 的第 $i$ 行总和为 1，则重建误差是
$(xi−∑j∈NiWijxj)2=(∑j∈NiWij(xi−xj))2=∑j,k∈NiWijWikCjk′\left ( x_{i}-\underset{j\in N_{i} }{\sum }W_{ij}x_{j} \right )^{2}=\left ( \underset{j\in N_{i}}{\sum }W_{ij}\left ( x_{i}-x_{j} \right ) \right )^{2}=\underset{j,k\in N_{i}}{\sum }W_{ij}W_{ik}C{}'_{jk}$ $(15.8)\left ( 15.8 \right )$
3.其中 $Ni\mathcal N_{i}$ 是局部协方差矩阵第 $x_{i}$ 点和第 $Cj,k′=(xi−xj)⊤(xi−xk)C{}'_{j,k}=\left (x_{i}-x_{j} \right )^{\top }\left (x_{i}-x_{k} \right )$ 点的邻域的索引集。使用约束 $∑jwij=1\sum _{j}w_{ij}=1$ 给出了解决方案
$Wij=∑k(C′−1)jk∑st(C′−1)stW_{ij}=\frac{\sum _{k}\left ( C{}'^{-1} \right )_{jk}}{\sum _{st}\left ( C{}'^{-1} \right )_{st}}$ $(15.9)\left(15.9\right)$
请注意，可以通过首先求解线性方程组 $∑j\scriptsize \sum _{j}$ $W_{ij}=1$ 然后进行归一化以使权重和为 $1$ 来等效地获得解。
3. 找到最符合 $W$ 指定的邻域关系的 $K$ 维表示，即
$Y=Y′agrmin∑i(yi′−∑jwijyj′)2Y=\overset{agrmin}{\tiny Y{}'}\underset{i}{\sum }\left ( y{}'_{i}-\underset{j}{\sum }w_{ij}y{}'_{j} \right )^{2}$ . $(15.10)\left ( 15.10 \right )$
(15.10) 中最小化的解为 $Y=UM,k⊤Y=U^{\top }_{M,k}$ ，其中 $\left(I-W^{\top}\right) \left(I-W^{\top}\right)$ 和 $UM,k⊤U^{\top}_{M,k}$ 是 $M$ 的底部 $k$ 个奇异向量，不包括与奇异值 0 对应的最后一个奇异向量。
正如练习 15.5 中所讨论的， $L L E$ 与 $K P C A$ 与使用特定核矩阵 $K_{LLE}$ 的 $K P C A$ 一致，由此输出维度被归一化为具有单位方差（如拉普拉斯特征图的情况）。

15.4 Johnson-Lindenstrauss定理

Johnson-Lindenstrauss引理是降维的一个基本结果，它表明高维空间中的任意 $m$ 点都可以映射到一个更低的维度 $k≥O(logmϵ2)k\geq O\left ( \frac{log_{m}}{\epsilon ^{2}} \right )$ ，而不会使任何两点之间的成对距离失真超过 $(1±ϵ)\left ( 1\pm \epsilon \right )$ 。事实上，通过将高维点投影到随机选择的 $k$ 维线性子空间，可以在随机多项式时间内找到这样的映射。 Johnson-Lindenstrauss 引理在引理 15.4 中正式提出。这个引理的证明取决于引理 15.2 和引理 15.3，它是“概率方法”的一个例子，其中概率论证导致确定性陈述。此外，正如我们将看到的，约翰逊-林登施特劳斯引理如下所示当向量投影到 k 维随机子空间时，随机向量的平方范数急剧集中在其均值附近。首先，我们证明 $X2\mathcal X^{2}$ 平方分布的以下性质（参见附录中的定义 C.7），将在引理 15.3 中使用。
引理15.2假设 $Q$ 是一个随机变量，服从具有 $k$ 个自由度的 $X^{2}$ 平方分布。然后，对于任何 $0<ϵ<120<\epsilon<\frac{1}{2}$ ，以下不等式成立：
$P[(1−ϵ)k≤Q≤(1+ε)k]≥1−2e−(ε2−e3)k4\mathbb{P}\left [ \left ( 1-\epsilon \right ) k\leq Q\leq \left ( 1+\varepsilon \right )k\right ]\geq 1-2e^{-\left ( \varepsilon ^{2}-e^{3} \right )\frac{k}{4}}$ . $(15.11)\left ( 15.11 \right )$
证明：通过马尔可夫不等式，我们可以使得
$P[Q≥(1+ϵ)k]=P[exp(λQ)≥exp(λ(1+ϵ)k)]≤E[exp(λQ)]exp(λ(1+ϵ)k)=(1−2λ)−k2exp(λ(1+ϵ)k)\mathbb{P}\left [ Q\geq \left ( 1+\epsilon \right )k \right ]=\mathbb{P}\left [ exp\left ( \lambda Q \right ) \geq exp\left ( \lambda \left ( 1+\epsilon \right )k \right )\right ]\leq \frac{\mathbb{E}\left [ exp\left ( \lambda Q \right ) \right ]}{exp\left ( \lambda \left ( 1+\epsilon \right )k \right )}=\frac{\left ( 1-2\lambda \right )^{\frac{-k}{2}}}{exp\left ( \lambda \left ( 1+\epsilon \right )k \right )}$
其中，我们使用 $X^{2}$ 平方分布的矩母函数表达式 $E[exp(λQ)]\mathbb{E}\left [ exp\left ( \lambda Q \right ) \right ]$ 表示 $λ<12\lambda < \frac{1}{2}$ （方程式（C.25）），选择 $λ=ϵ2(1+ϵ)<12\lambda =\frac{\epsilon }{2\left ( 1+\epsilon \right )}<\frac {1}{2}$ ，使最终等式的右侧最小化，并使用不等式 $1+ϵ≤exp(ϵ−(ϵ2−ϵ32))1+\epsilon \leq exp\left ( \epsilon -\left ( \frac{\epsilon ^{2}-\epsilon ^{3} }{2}\right ) \right )$ 得到结果：
$P[Q≥(1+ϵ)k]≤(1+ϵexp(ϵ))k2≤(exp(ϵ−ϵ2−ϵ32)exp(ϵ))k2=exp(−k4(ϵ2−ϵ3))\mathbb{P}\left [ Q\geq \left ( 1+\epsilon \right ) k\right ]\leq \left ( \frac{1+\epsilon }{exp\left ( \epsilon \right )} \right )^{\frac{k}{2}}\leq \left ( \frac{exp\left ( \epsilon -\frac{\epsilon ^{2}-\epsilon ^{3}}{2 } \right )}{exp\left ( \epsilon \right )} \right )^{\frac{k}{2}}=exp\left ( -\frac{k}{4}\left ( \epsilon ^{2} -\epsilon ^{3}\right ) \right )$ .
引理的说明是通过使用与绑定 $P[Q≤(1−ϵ)k]\mathbb{P}\left [ Q\leq \left ( 1-\epsilon \right )k \right ]$ 类似的技术和应用联合绑定来实现的。
引理 15.3 让 $x∈RNx\in \mathbb{R}^{N}$ ，定义 $k < N$ 并假设 $A∈Rk×NA\in \mathbb{R}^{k\times N}$ 中的条目是从标准正态分布 N(0,1) 独立采样。那么，对于任何 $\epsilon < \frac{1}{2}$ ,满足
$P[(1−ϵ∥x∥2≤∥1kAX∥2)≤(1+ϵ∥x∥2)]≥1−2e−(ϵ2−ϵ3)k4\mathbb{P}\left [ \left ( 1-\epsilon \left \| x \right \|^{2} \leq \left \| \frac{1}{\sqrt{k}}AX \right \|^{2}\right )\leq \left ( 1+\epsilon \left \| x \right \|^{2} \right ) \right ]\geq 1-2e^{-\left ( \epsilon ^{2}-\epsilon ^{3} \right )^{\frac{k}{4}}}$ $(15.12)\left ( 15.12 \right )$
证明：设 $x^=Ax\hat{x}=Ax$ 并观察
$E[x^j2]=E[(∑i=1NAjixi)2]=E[∑i=1NAji2xi2]=∑i=1Nxi2=∥x∥2\mathbb{E}\left [ \hat{x}_{j}^{2} \right ]=\mathbb{E}\left [\left ( \overset{N}{\underset{i=1}{\sum }}A_{ji}x_{i}\right )^{2}\right ]=\mathbb{E}\left [ \overset{N}{\underset{i=1}{\sum }}A_{ji}^{2}x_{i}^{2} \right ]=\overset{N}{\underset{i=1}{\sum }}x_{i}^{2}=\left \| x \right \|^{2}$ .
第二个和第三个等式分别来自 $A_{ij}$ 的独立性和单位方差。现在，定义 $Tj=x^j/∥x∥T_{j}=\hat{x}_{j}/\left \| x \right \|$ ，注意 $T_{j}s$ 是独立的标准正态随机变量，因为 $A_{ij}$ 是独立的标准正态随机变量，独立同分布是独立的标准正态随机变量。因此，由 $Q=∑j=1kTj2Q=\sum_{j=1}^{k}T_{j}^{2}$ 定义的变量 $Q$ 遵循具有 $k$ 个自由度的 $X^{2}$ 平方分布，我们得到
$P[(1−ϵ)∥x2∥≤∥x^2∥k≤(1+ϵ)∥x∥2]=P[(1−ϵ)k≤∑j=1kTj2≤(1+ϵ)k]=P[(1−ϵ)k≤Q≤(1+ϵ)k]≥1−2e−(ϵ2−ϵ3)k4\mathbb{P}\left [ \left ( 1-\epsilon \right )\left \| x^{2} \right \| \leq \frac{\left \| \hat{x}^{2} \right \|}{k}\leq \left ( 1+\epsilon \right )\left \| x \right \|^{2}\right ]=\mathbb{P}\left [ \left ( 1-\epsilon \right )k\leq \overset{k}{\underset{j=1}{\sum }}T_{j}^{2} \leq \left ( 1+\epsilon \right )^{k}\right ]=\mathbb{P}\left [ \left ( 1-\epsilon \right )k\leq Q\leq \left ( 1+\epsilon \right )k \right ]\geq 1-2e^{-\left ( \epsilon ^{2}-\epsilon ^{3} \right )^{\frac{k}{4}}}$
其中最终的不等式由引理 15.2 成立，从而证明了引理的陈述。
引理 15.4 (JohnsonLindenstrauss) 对于任何 $\epsilon < \frac{1}{2}$ 和任何整数 $m > 4$ ，令 $k=20logmϵ2k=\frac{20log_{m}}{\epsilon ^{2}}$ 。那么对于 $RN\mathbb{R}^{N}$ 中 $m$ 个点的任意集合 $V$ ，存在一个映射 $f:RN→RKf:\mathbb{R}^{N}\rightarrow \mathbb{R}^{K}$ ，使得对于所有 $u,v∈V，u,v\in V，$
$(1−ϵ)∥u−v∥2≤∥f(u)−f(v)∥2≤(1+ϵ)∥u−v∥2\left ( 1-\epsilon \right )\left \| u-v \right \|^{2}\leq \left \| f\left ( u \right )-f\left ( v \right ) \right \|^{2}\leq \left ( 1+\epsilon \right )\left \| u-v \right \|^{2}$ $(15.13)\left ( 15.13 \right )$
证明：设 $f=1kAf=\frac{1}{\sqrt{k}}A$ 其中 $K < N$ 和 $A∈Rk×NA\in \mathbb{R}^{k\times N}$ 中的条目独立于标准正态分布 $N (0, 1)$ 进行采样。对于固定的 $u,v∈Vu,v\in V$ ，我们可以应用引理 15.3 和 $x = u - v$ ，将成功概率下限为 $1−2e−(ϵ2−ϵ3)k41-2e^{-\left ( \epsilon ^{2}-\epsilon ^{3} \right )^{\frac{k}{4}}}$ 。在 $V$ 中的 $O(m2)O\left ( m^{2} \right )$ 对上应用联合边界，设置 $k=20ϵ2logmk=\frac{20}{\epsilon ^{2}}log\tiny m$ 和上限 $12\frac{1}{2}$ ，我们有
$P[success]≥1−2m2e−(ϵ2−ϵ3)k4=1−2m5ϵ−3>1−2m−12>0.\mathbb{P}\left [ success \right ]\geq 1-2m^{2}e^{-\left ( \epsilon ^{2}-\epsilon ^{3} \right )^{\frac{k}{4}}}=1-2m^{5\epsilon -3}> 1-2m^{-\frac{1}{2}}> 0.$
由于成功概率严格来说一般来说是大于零的，所以满足期望的条件必然是存在的，从而证明引理的陈述。

15.5 章节注释

PCA 在 1900 年代早期由 Pearson [1901] 引入。引入 KPCA大约一个世纪之后，我们对 KPCA 的介绍是一个更简洁的推导Mika 等人给出的结果。 [1999]。 Isomap 和 LLE 是开创性的工作Tenenbaum 等人引入的非线性降维。 [2000]，罗维斯和扫罗 [2000]。 Isomap 本身是标准线性维度的概括减少技术称为多维缩放 [Cox and Cox, 2000]。等值线图和 LLE 导致开发了几种用于流形学习的相关算法，例如，拉普拉斯特征图和最大方差展开 [Belkin 和 Niyogi，2001，温伯格和索尔，2006]。如本章所示，经典流形学习算法是 KPCA [Ham et al., 2004] 的特殊实例。约翰逊——Lindenstrauss 引理由 Johnson 和 Lindenstrauss [1984] 引入，尽管我们对引理的证明遵循 Vempala [2004]。这方面的其他简化证明引理也被提出，包括 Dasgupta 和 Gupta [2003]。

15.6练习

15.1 主成分分析和最大方差。设 $X$ 为非中心数据矩阵，设 $xˉ=1m∑ixi\bar{x}=\frac{1}{m}\sum _{i}x_{i}$ 为 $X$ 列的样本平均值。

（a）显示数据在任意向量 $u$ 上的一维投影方差等于 $u⊤Cuu^{\top }Cu$ ，其中 $C=1m∑i(xi−xˉ)(xi−xˉ)⊤C=\frac{1}{m}\sum _{i}\left ( x_{i}-\bar{x} \right )\left ( x_{i}-\bar{x} \right )^{\top }$ 是样本协方差矩阵。
（b）表明 $k = 1$ 的主成分分析将数据投影到最大方差的方向（即 $u⊤u=1u^{\top }u=1$ ）。

15.2 双居中。在这个问题中，我们将证明在使用欧几里得距离时等距特征映射中双重居中步骤的正确性。按照练习 15.1 定义 $X$ 和 $xˉ\bar x$ ，并将 $X∗X^{\ast}$ 定义为 $X$ 的中心版本，即让 $xi∗=xi−xˉx_{i}^{\ast }=x_{i}-\bar{x}$ 是 $X∗X^{\ast}$ 的第 i 列。让 $K=X⊤XK=X^{\top }X$ ，让 $D$ 表示欧几里得距离矩阵，即 $Dij=∥xi−xj∥D_{ij}=\left \| x_{i}-x_{j} \right \|$ 。

( $a$ ) 证明 $Kij=12(Kii+kjj+Dij2)K_{ij}=\frac{1}{2}\left ( K_{ii}+k_{jj} +D_{ij}^{2}\right )$
( $b$ ) 证明 $K∗=X∗⊤X∗=K−1mK11⊤−1m11⊤K+1m211⊤K11⊤K^{\ast }=X^{\ast \top }X^{\ast }=K-\frac{1}{m}K11^{\top }-\frac{1}{m}11^{\top }K+\frac{1}{m^{2}}11^{\top }K11^{\top }$
( $c$ ) 使用 ( $a$ ) 和 ( $b$ ) 的结果表明
$Kij∗=−12[Dij2−1m∑k=1mDik2−1m∑k=1mDkj2+Dˉ],K_{ij}^{\ast }=-\frac{1}{2}\left [ D_{ij}^{2}-\frac{1}{m}\overset{m}{\underset{k=1}{\sum }}D_{ik}^{2} -\frac{1}{m}\overset{m}{\underset{k=1}{\sum }}D_{kj}^{2}+\bar{D}\right ],$
其中 $Dˉ=1m2∑u∑vDu,v2\bar{D}=\frac{1}{m^{2}}\sum _{u}\sum _{v}D_{u,v}^{2}$ 是 $D$ 中 $m^{2}$ 条目的平均值。
( $d$ ) 证明证明 $K∗=−12HDHK^{\ast }=-\frac{1}{2}HDH$ ，其中 $H=Im−1m11⊤H=I_{m}-\frac{1}{m}11^{\top }$ 。
15.3 拉普拉斯特征图。假设 $k = 1 ，$ 我们寻求一维表示 $y$ 。证明 (15.7) 等价于 $=argmin_{y{}'}y{}'^{\top }Ly{}'$ ，其中 $L$ 是图拉普拉斯算子。

15.4 Nystr $o¨\ddot{o}$ m 方法。定义内核矩阵的以下块表示：

$k=[WK21⊤K21K22]和C=[WK21]k=\begin{bmatrix} W &K_{21}^{\top } \\ K_{21} & K_{22} \end{bmatrix}和C=\begin{bmatrix}W\\ K_{21}\end{bmatrix}$ .
Nystr $o¨\ddot{o}$ m方法使用 $W∈Rl×lW\in \mathbb{R}^{l\times l}$ 和 $C∈Rm×lC\in \mathbb{R}^{m\times l}$ 生成近似值 $K~=CW†C⊤≈K\tilde{K}=CW^{\dagger }C^{\top }\approx K$ 。
$(a)$ 证明 $W 是$ SPSD且 $∥K−K~∥F=∥K22−K21W†K21⊤∥F\left \| K-\tilde{K} \right \|_{F}=\left \| K_{22}-K_{21}W^{\dagger } K_{21}^{\top }\right \|_{F}$
$(b)$ 让 $K=X⊤XK=X^{\top }X$ 代表一些 $X∈RN×mX\in \mathbb{R}^{N\times m}$ ，让 $X′∈RN×l{X}'\in \mathbb{R}^{N\times l}$ 成为前 $l$ 列的 $X$ 。证明 $K~=X⊤PUX′X,\tilde{K}=X^{\top }P_{U_{X{}'}}X,$ 其中 $P_{U_{X{}'}}$ 是到 ${X}'$ 的左奇异向量的跨度上的正交投影。
$（ c ）$ $K~\tilde{K}$ 是SPSD吗？
$(d)$ 如果 $=r\ll m$ ，证明 $K~=K\tilde{K}=K$ 。注意：这个陈述在 $r a n k (K) = r a n k (W)$ 时成立，但主要是在低 $r a n k$ 设置中实现的。
$（ e ）$ 如果 $m = 20 M$ 且 $K$ 为稠密矩阵，则每个条目存储为双精度矩阵，需要多少空间来存储 $K$ ？如果 $l = 10 K$ ，那么Nystr $o¨\ddot{o}$ m方法会用到多少空间？

15.5

表示 $K_{LLE}$ 。通过推导 $K_{LLE}$ 的表达式，来显示LLE和KPCA之间的关系。

15.6随机投影、PCA和最近邻。

（a）在以下位置下载手写数字的MNIST测试集点击这里下载
从该数据集的第一个 $m = 2, 000$ 的实例中创建数据矩阵 $X∈RN×mX\in \mathbb{R}^{N\times m}$ （每个实例的维度应为 $N = 784$ ）。
$(b)$ 为 $X$ 中的每个点找到十个最近邻，即计算 $Ni,10\mathcal N_{i,10}$ 为 $1≤i≤m1\leq i\leq m$ ，其中 $Ni,t\mathcal N_{i,t}$ 表示第 $i$ 个数据点的 $t$ 个最近邻的集合，最近邻是根据 $L_{2}$ 范数定义的。还计算所以 $i$ 的结果 $Ni,50\mathcal N_{i,50}$ 。
$（ c ）$ 生成 $x^=AX\hat{x}=AX$ ，其中对 $A∈Rk×N,K=100A\in \mathbb{R}^{k\times N},K=100$ 和 $A$ 的条目进行采样独立于标准正态分布。找到 $X~\tilde{X}$ 中每个点的十个最近邻，即为在 $1≤i≤m1\leq i\leq m$ 的条件下计算 $N~i,10\tilde{N}_{i,10}$ 。
$（ d ）$ 通过计算 $score10=1m∑i=1m∣Ni,10∩N~i,10∣score_{10}=\frac{1}{m}\sum_{i=1}^{m}\left | N_{i,10}\cap \tilde{N}_{i,10} \right |$ 来报告近似的质量。同样，计算
$score50=1m∑i=1m∣Ni,50∩N~i,10∣score_{50}=\frac{1}{m}\sum_{i=1}^{m}\left | N_{i,50}\cap \tilde{N}_{i,10} \right |$ 。
$（ e ）$ 生成两个显示 $score_{10}$ 和 $score_{50}$ 作为 $k$ 函数的图（即，针对 $k={1,10,50,100,250,500}k=\left \{ 1,10,50,100,250,500 \right \}$ 执行步骤 $（ c ）和（ d ））$ 提供这些图的一句或两句解释。
$（ f ）$ 使用PCA（具有不同的 $k$ 值）生成 $（ e ）$ 中的类似图，以生成 $X~\tilde{X}$ ，然后计算最近邻。通过PCA生成的最近邻近似值相比于通过随机投影生成的最近邻近似值好还是差？解释原因。

作者：用户2903215823838
链接：https://juejin.cn/post/7017373378579267614

15.降维技术 （Dimensionality Reduction）