Table of contents
抑制过拟合
- 增加样本数据
- 正则化：增加约束限制参数空间
- 降维
维度灾难
References:
Notes:
-
数学角度： 比如每增加一个二值属性，要想完全cover样本空间，所需样本数会以2的指数增长
几何意义： 在高维空间中，立方体的内切球的体积趋近于零，也就是说把立方体的四个角削掉，只剩下内切球，基本就一点不剩了知乎:机器学习中的维度灾难，四个角所占比例不高，却拥有几乎全部的体积。 所以如果在高维空间中取一超立方体，其中存在样本的概率很低，因为样本只存在于四个角中，这就是数据的稀疏性，并且分布不均匀。很难做分类。
维度 超立方体体积 超内切球体积 2 1 π (0.5)² 3 1 4/3 π (0.5)³ D 1 K(0.5)ᴰ; 当 D→∞, V(超球体)→0 几何意义2: 两个同心圆的半径相差 $\varepsilon \ (0<\varepsilon<1)$，内圆的半径为 $1-\varepsilon$，外超球体的体积为：$V_外=K \cdot 1^D = K$；环形带的体积：$V_{环形带} = V_外-V_内 = K - K(1-\varepsilon)^D$。
两体积之比：$\frac{V_环}{V_外} = \frac{K- K(1-\varepsilon)^D}{K} = 1-(1-\varepsilon)^D$。 不论$\varepsilon$取多小，当维度趋于无穷，$\underset{D\rightarrow \infin}{lim} (1-\varepsilon)^D = 0$，也就是比值为1，环形带(壳)体积等于外球的体积 球内的样本只存在与球壳上 -
维度灾难会导致过拟合
-
需要降维
(2025-04-13T21:19:49)
-
评价一个人的维度很多，多到让每个人只是空间中的一个点，一个独一无二的点，每个人都是不一样的。
-
Supports:
- 从一个维度比较两个人，比的是长度，从两个维度比较，比的是面积，从三个维度比较，比的是体积，这都是指数级的增长哦， 因为两项技能在一个人身上，确实像是乘法一般将人的能力放大。
- 维度？唯独！
特征向量维度那么高，所以两个特征向量之间的距离很大吧？维度数量与距离之间无因果关系r1-DS
-
降维
- 避免过拟合，减小泛化误差
-
- 直接降维/特征选择: 只保留重要的维度; LASSO带来系数的系数性，使某些属性对应的系数等于0。
- 线性降维: PCA, MDS
- 非线性降维: 流形（ISOmap, LLE）
Data:
$$ \mathbf X_{p\times 1} = (\mathbf x_1, \mathbf x_2, \cdots, \mathbf x_N)^T_{N\times p} = \begin{pmatrix} \mathbf x_1^T \ \mathbf x_2^T \ \vdots \ \mathbf x_N^T \end{pmatrix}_{N \times p},\quad
\mathbf x_i \in \R^p,\ i=1, 2, \cdots, N
$$
Sample Mean:
$$ \begin{aligned} \bar{\mathbf X} &= \frac{1}{N} \sum_{i=1}^N \mathbf x_i \ & = \frac{1}{N} (\mathbf x_1, \mathbf x_2,\cdots, \mathbf x_N) \begin{pmatrix} 1 \ 1 \ \vdots \ 1 \end{pmatrix}_{N\times 1} \ & = \frac{1}{N} \ \mathbf X^T \ \mathbf 1_N
\end{aligned} $$
Sample Covariance:
$$ S = \frac{1}{N} \sum_{i=1}^N (\mathbf x_i - \bar{\mathbf X})^2 \quad (一维样本) $$$$ \begin{aligned} S_{p\times p} &= \frac{1}{N} \sum_{i=1}^N (\mathbf x_i - \bar{\mathbf X}) (\mathbf x_i - \bar{\mathbf X})^T \quad (p维样本) \
& = \frac{1}{N} (\mathbf x_1 - \bar{\mathbf X} \quad \mathbf x_2 - \bar{\mathbf X}\ \cdots \ \mathbf x_N - \bar{\mathbf X}) \begin{pmatrix} (\mathbf x_1 - \bar{\mathbf X})^T \ (\mathbf x_2 - \bar{\mathbf X})^T \ \vdots \ (\mathbf x_N - \bar{\mathbf X})^T \end{pmatrix} \
& = \frac{1}{N} \left[(\mathbf x_1 \ \mathbf x_2 \cdots \mathbf x_N) - \mathbf{\bar{X}} \ (1 \ 1 \cdots 1)\right] (\mathbf x_i - \bar{\mathbf X})^T \
& = \frac{1}{N} [ \ \mathbf X^T_{p\times N} - \frac{1}{N} \mathbf{X}^T \mathbf 1_N \ \mathbf 1_N^T \ ]\ (\mathbf x_i - \bar{\mathbf X})^T \
& = \frac{1}{N} [ \ \mathbf X^T (I_N - \frac{1}{N} \mathbf 1_N \mathbf 1_N^T) ]\ (\mathbf x_i - \bar{\mathbf X})^T \quad \text{($I_N$是NxN方阵)} \
& = \frac{1}{N} [ \ \mathbf X^T \underline{(I_N - \frac{1}{N} \mathbf 1_N \mathbf 1_N^T)} ] \cdot [ \underline{(I_N - \frac{1}{N} \mathbf 1_N \mathbf 1_N^T)^T} \mathbf X] \
& = \frac{1}{N} \mathbf X^T H \cdot H^T \mathbf X \ & = \frac{1}{N} \mathbf X^T H \mathbf X
\end{aligned} $$
H 是中心矩阵，把数据的均值移动到原点(中心化).
$$ \begin{aligned} H &= (\mathbf I_N - \frac{1}{N} \mathbf 1_N \mathbf 1_N^T) \ H^T &= (\mathbf I_N - \frac{1}{N} \mathbf 1_N \mathbf 1_N^T) =H & (对称性)\ H^2 &= H \cdot H & (幂等性)\ &= (I_N - \frac{1}{N} \mathbf 1_N \mathbf 1_N^T) (I_N - \frac{1}{N} \mathbf 1_N \mathbf 1_N^T) \ &= I_N - \frac{2}{N} \mathbf 1_N \mathbf 1_N^T + \frac{1}{N^2} 1_N \mathbf 1_N^T 1_N \mathbf 1_N^T \
&= I_N - \frac{2}{N}
\begin{pmatrix}
1 & 1 & \cdots & 1 \\
\vdots & \vdots & \vdots & \vdots \\
1 & 1 & \cdots & 1 \\
\end{pmatrix}
+
\frac{1}{N^2}
\begin{pmatrix}
N & N & \cdots & N \\
\vdots & \vdots & \vdots & \vdots \\
N & N & \cdots & N \\
\end{pmatrix} \\
&= I_N - \frac{1}{N} \mathbf 1_N \mathbf 1_N^T \\
&= H \\
H^n &= H \end{aligned} $$
经典PCA
-
一个中心，两个基本点
-
核心：将一组可能线性相关的变量，通过正交变换，变换成一组线性无关的变量/基/投影方向（对原始特征空间的重构）
基本点：最大投影方差；最小重构距离（两种角度,效果相同）
最大投影方差
- 最能体现原来样本的分布
- Steps:
-
中心化：把样本均值移动到原点 ($\mathbf x_i - \bar{\mathbf X}$)
-
样本点在 $\mathbf u_1$ 方向上的投影，也是在$\mathbf u_1$方向上的坐标：
$$ (\mathbf x_i - \bar{\mathbf X})^T \mathbf u_1 $$其中 $\| \mathbf u_1\| = 1$ (或$\mathbf u_1^T \mathbf u_1 = 1$)，所以内积等于投影。 两个向量的内积写成一个向量的转置乘以另一个向量，$\mathbf a_{p\times 1} \cdot \mathbf b_{p \times 1} = \mathbf a^T_{1\times p} \ \mathbf b_{p \times 1} = n_{1\times 1}$
-
投影方差：因为均值已经为0，投影直接平方
$$ \begin{aligned} J &= \frac{1}{N} \sum_{i=1}^N \left( (\mathbf x_i - \bar{\mathbf X})^T \mathbf u_1 \right)^2 \
&= \sum_{i=1}^N \ \frac{1}{N} \ \mathbf u_1^T (\mathbf x_i - \bar{\mathbf X}) \ (\mathbf x_i - \bar{\mathbf X})^T \mathbf u_1 \
&= \mathbf u_1^T \left(\frac{1}{N} \ \sum_{i=1}^N (\mathbf x_i - \bar{\mathbf X}) \ (\mathbf x_i - \bar{\mathbf X})^T \right) \mathbf u_1 \
&= \mathbf u_1^T \cdot S \cdot \mathbf u_1 \end{aligned} $$
找到使 J 最大的方向 $\mathbf u_1$
$$ \begin{cases} \hat \mathbf u_1 = \operatorname{arg\ max}\ \mathbf u_1^T \cdot S \cdot \mathbf u_1 \\ s.t. \quad \mathbf u_1^T \mathbf u_1 = 1 \end{cases} $$带约束的优化问题，用拉格朗日乘子法，写出拉格朗日函数：
$$ L(\mathbf u_1, \lambda) = \mathbf u_1^T \cdot S \cdot \mathbf u_1 + \lambda (1 - \mathbf u_1^T \mathbf u_1) $$求导：
$$ \begin{aligned} \frac{\partial L}{\partial \mathbf u_1} = 2 S \cdot \mathbf u_1 &- \lambda \cdot 2 \mathbf u_1 = 0 \\ S \underbrace{\mathbf u_1}_{\text{Eigen vector}} &= \underbrace{\lambda}_{\text{Eigen value}} \mathbf u_1 \end{aligned} $$
-
最小代价重构
- 从重构空间恢复到原始空间，代价最小
- Steps:
-
向量$\mathbf x_i$在新的特征空间中的表示：
$$ \begin{aligned} \mathbf x_i &= ((\mathbf x_i - \bar{\mathbf X})^T \mathbf u_1)\cdot \mathbf u_1 + ((\mathbf x_i - \bar{\mathbf X})^T \mathbf u_2)\cdot \mathbf u_2 + \cdots + ((\mathbf x_i - \bar{\mathbf X})^T \mathbf u_p)\cdot \mathbf u_p \\ &= \sum_{k=1}^p ((\mathbf x_i - \bar{\mathbf X})^T \mathbf u_k) \cdot \mathbf u_k \end{aligned} $$ -
降维：根据特征值，取前q个最大的特征向量(方向)。
$$ \hat{\mathbf x}_i = \sum_{k=1}^q ((\mathbf x_i - \bar{\mathbf X})^T \mathbf u_k) \cdot \mathbf u_k $$ -
重构代价: $\| \mathbf x_i - \hat{\mathbf x}_i \|^2$
N个样本的重构代价最小：
$$ \begin{aligned} J &= \frac{1}{N} \sum_{i=1}^N | \mathbf x_i - \hat{\mathbf x}i |^2 \ &= \frac{1}{N} \sum{i=1}^N | \sum_{k=q+1}^p ((\mathbf x_i - \bar{\mathbf X})^T \mathbf u_k) \cdot \mathbf u_k |^2 \
&= \frac{1}{N} \sum_{i=1}^n \sum_{k=q+1}^p \left( (\mathbf x_i - \bar{\mathbf x})^t \mathbf u_k \right)^2 \quad \text{(向量的模等于坐标的平方和)} \
&= \sum_{k=q+1}^p \underline{ \sum_{i=1}^n \frac{1}{N} \left( (\mathbf x_i - \bar{\mathbf X})^T \mathbf u_k \right)^2 } \
&= \sum_{k=q+1}^p \mathbf u_k^T \cdot S \cdot \mathbf u_k \qquad\ \rm s.t.\ \mathbf u_k^T \mathbf u_k = 1 \
\end{aligned} $$
最优化问题：
$$ \begin{cases} \mathbf u_k = \operatorname{arg\ min} \sum_{k=q+1}^p \mathbf u_k^T \cdot S \cdot \mathbf u_k \\ s.t. \quad \mathbf u_k^T \mathbf u_k = 1 \end{cases} $$因为各特征向量互不相关，所以可以一个一个解，也就是求剩余的每个特征向量的最小重构代价对应的特征值$\lambda$
$$ \begin{cases} \operatorname{arg\ min} \mathbf u_{q+1} \cdot S \cdot \mathbf u_{q+1}\\ s.t. \quad \mathbf u_{q+1}^T \ \mathbf u_{q+1} = 1 \end{cases} $$$$ J = \sum_{i=q+1}^p \lambda_i $$当J最小时，对应的就是最小的几个特征值
-
PCA 找最大的投影方向(特征向量)，就是主成分
求解主成分：对方差矩阵做特征值分解：$S = G K G^T$（因为S是对称矩阵，所以它的奇异值分解就是特征值分解）， 其中特征向量是正交的: $G^T G = I$；K是对角矩阵，元素都是特征值，其排列满足： $k_1 > k_2 > \cdots > k_p$。降到q维，就取前 q 个值，作为G的q个列向量。
$$ K= \begin{pmatrix} k_1 & 0 & 0 & 0 \\ 0 & k_2 & 0 & 0 \\ 0 & 0 & \ddots & 0 \\ 0 & 0 & 0 & k_p \end{pmatrix} $$探索一下：
-
对中心化之后的原始数据做SVD奇异值分解：
$$ H X = U \Sigma V^T \rightarrow SVD: \begin{cases} U^T U = I & \text{(列正交)} \\ V^T V = V V^T = I & \text{(正交)} \\ \Sigma & \text{(对角)} \end{cases} $$然后代入协方差矩阵（推导省略常数$\frac{1}{N}$）：
$$ \begin{aligned} S_{p\times p} &= X^T H X \\ &= X^T H^T H X & \text{(等幂性)} \\ &= V \Sigma \underline{U^T \cdot U} \Sigma V^T \\ &= V \Sigma I \Sigma V^T & \text{(U列正交)}\\ &= V \Sigma^2 V^T & \text{($\Sigma$对角阵)} \end{aligned} $$就相当于对 S 做了奇异值分解了，对应于上面 S 的特征值分解：
$$ 特征向量G = V, 特征值K = \Sigma^2 $$所以，不用直接对 S做特征值分解，直接对数据做完中心化之后，做奇异值分解，就可以得到特征向量V。
-
定义一个矩阵 T（S反过来，对数据内积分解）:
$$ \begin{aligned} T_{N\times N} &= H X X^T H^T \\ &= U \Sigma V^T \cdot V \Sigma U^T \\ &= U \Sigma^2 U^T \end{aligned} $$T 和 S 有相同的特征值(eigen value): $\Sigma^2$。
PCA：先对 S 做特征值分解，找到了主成分（特征向量/投影方向）；然后样本点 $HX$ 乘以方向向量$V$（投影），得到各方向上的坐标。 坐标矩阵：$HX \cdot V = U \Sigma \underline{V^T \cdot V} = U \Sigma$
而对T做特征分解，可以直接得到坐标，这叫主坐标分析（PCoA）
对T两边左乘$U\Sigma$（做一个缩放）：
$$ \begin{aligned} T &= U \Sigma^2 U^T \\ T U \Sigma &= U \Sigma^2 \underline{U^T U} \Sigma \\ &= U \Sigma^3 \\ T \underbrace{U \Sigma}_{特征向量} &= U \Sigma \underbrace{\Sigma^2}_{特征值} \end{aligned} $$也就是说，对T做SVD奇异值分解后，直接得到的特征向量就是坐标。
如果数据的维度太高，$S_{p\times p}$ 不好计算，可以对$T_{N\times N}$分解。