0%

白板推导 - 机器学习 (降维和 SVM)

1. 降维 - 背景

  • 过拟合的解决方法:

    • 增加数据集
    • 正则化
    • 降维
  • 维度灾难:每增加一个特征, 数据集往往需要以 2(或者 category 的 个数)的 指数级递增。

2. 降维 - 样本均值 & 样本方差矩阵

  • 假设:

    Data: $X = (x_1, x_2, …, x_N)_{Nxp}^T, x_i \in R^p, i=1,…,N$

    Sample Mean: $\overline{X}{p\times1} = \frac{1}{N}\sum{i=1}^N x_i$

    SampleCovariance: $S_{pxp} = \frac{1}{N}\sum_{i=1}^N(x_i - \overline{x})(x_i - \overline{x})^T$

    单位矩阵: $1_N = (1; 1; …; 1)_{Nx1}$

  • 改进则:
    $$\overline{x} = \frac{1}{N}\sum_{i=1}^Nx_i = \frac{1}{N}(x_1,…,x_N)(1; …; 1) = \frac{1}{N}X^T1_N$$
    $$S = \frac{1}{N}\sum_{i=1}^N (x_i-\overline{x})(x_i-\overline{x})^T$$
    $$ = \frac{1}{N}(x_1-\overline{x}, x_2-\overline{x}, …, x_N-\overline{x}) ((x_1-\overline{x})^T; (x_2-\overline{x})^T; …; (x_N - \overline{x})^T)$$

$$(x_1-\overline{x}, x_2-\overline{x}, …, x_N-\overline{x}) = (x_1,x_2,…,x_N) - (\overline{x}, \overline{x}, …, \overline{x})$$
$$= x^T - \overline{x}(1,1,…,1) = x^T - \overline{x}\cdot1_N^T = x^T - \frac{1}{N}x^T\cdot1_N\cdot 1_N^T$$

令 $H_N = I_N - \frac{1}{N}\cdot 1_N \cdot 1_N^T$
$$\to S = \frac{1}{N}x^T H_N H_N^T X = \frac{1}{N}x^TH_Nx$$

3. 降维 -PCA- 最大投影方差

  • 一个中心: 对于原始特征空间的重构(从相关 到 不相关)

  • 两个基本点: ①: 最大投影方差 ②: 最小重构误差

  • 投影方差:寻找到一个方向 $u_1$ 使得样本在该方向的方差更大
    $$J = \frac{1}{N}\sum_{i=1}^N ((x_i - \overline{x})^T u_1)^2$$
    $$ = u_1^T \frac{1}{N}\sum_{i=1}^N(x_i - \overline{x})(x_i - \overline{x})^T u_1$$
    $$ = u_1^T\cdot S \cdot u_1$$

  • 优化函数

    ①:$\hat{u_1} = \argmax u_1^T \cdot S \cdot u_1$

    ②:$u_1^T\cdot u_1 = 1$
    $$L(u_1, \lambda) = u_1^T\cdot S \cdot u_1 + \lambda(1 - u_1^T \cdot u_1)$$
    $$\frac{\partial L}{\partial u_1} = 2\cdot S \cdot u_1 - 2\cdot \lambda \cdot u_1 = 0$$
    $$\to S\cdot u_1 = \lambda\cdot u_1$$
    即协方差矩阵的 特征值 特征向量 即为最终需要求解的内容

4. 降维 -PCA- 最小重构误差

$x_i = \sum_{k=1}^p (x_i^T u_k) u_k$

$\hat{x_i} = \sum{k=1}^q(x_i^T u_k) u_k$

  • 重构损失: $u_i, u_j$ 是相互正交的
    $$J = \frac{1}{N}\sum_{i=1}^N ||x_i - \hat{x_i}||^2$$
    $$ = \frac{1}{N}\sum_{i=1}^N ||\sum_{k=q+1}^p (x_i^T u_k) u_k||^2$$
    $$ = \frac{1}{N}\sum_{k=q+1}^p (x_i^T u_k)^2$$
    $$ = \frac{1}{N}\sum_{i=1}^N\sum_{k=q+1}^p((x_i - \overline{x})^T u_k)^2$$
    $$ = \sum_{k=q+1}^p\sum_{i=1}^N \frac{1}{N}((x_i - \overline{x})^T u_k)^2$$
    $$ = \sum_{k=q+1}^p u_k^T \cdot S \cdot u_k$$
    即:
    $$u_k = \argmin \sum_{k=q+1}^p u_k^T \cdot S \cdot u_k$$
    $$u_k^T \cdot u_k = 1$$

5. 降维 -SVD 角度看 PCA 和 PCoA

  • 协方差矩阵的奇异值分解:
    $$S = GKG^T$$
    $$G^TG = I$$
    $$k = diag(k_1, k_2, …, k_p), k_1\ge k_2\ge k_3 … \ge k_p$$

  • SVD 的分解:
    $$U^TU = I$$
    $$V^TV = VV^T = I$$
    $$\Sigma 对角矩阵 $$
    $$HX = U\Sigma V^T$$

  • 推导:
    $$S_{pxp} = X^THX = X^TH^THX = V\Sigma U^T\cdot U\Sigma V^T = V\Sigma^2V^T$$
    $$T_{NxN} = HXX^TH = U\Sigma V^T \cdot V\Sigma U^T = U\Sigma^2 U^T$$

    由此 T 和 S 有相同的 eigen value

    S: 特征分解: 得到方向(主成分)

    T: 特征分解: 直接得到坐标 (PCoA[principle coordinate analysis], 主坐标分析)

6. 降维 - 主成分分析 - 概率角度(重点要看)

  • 假设:

    oberved data: $x \in R^P$

    latent variabel: $z \in R^q, q < p$

    $z \sim N(O_q, I_q)$

    $x = w\cdot z+ \mu + \varepsilon$ :线性高斯模型

    $\varepsilon \in N(0, \delta I_p)$

  • 求解:

    • Inference: $P(z|x)$

    • Learning: $w, \mu, \delta^2 \to$ EM 算法

7. SVM- 硬间隔 - 模型定义

  • svm 有三宝: 间隔、对偶、核技巧

  • svm: hard-margin svm; soft-margin svm; kernel svm

  • 数据假设: ${(x_i, y_i)}_{i=1}^N, x_i\in R^p, y_i \in {(-1, 1)}$

  • 原理: 最大间隔分类器, max margin(w, b), 且 $y_i(w^T x_i + b) > 0$
    $$\max_{w,b} \min_{x_i} \frac{1}{||w||}y_i(w^T x_i + b) = \max_{w,b}\frac{1}{||w||}\min_{x_i}y_i(w^Tx_i+b)$$
    $$y_i(w^Tx_i+b)>0; \exist r>0, \min_{x_i}y_i(w^Tx_i+b) = r$$

    转化为凸优化问题(convex optimization):
    $$\max_{w,b} \frac{1}{||w||} \to \min_{w,b}\frac{1}{2}w^Tw$$
    $$\min y_i(w^Tx_i+b)=1 \to y_i(w^Tx_i+b) \ge 1$$

8. SVM- 硬间隔 - 模型求解(对偶问题)

  • 拉格朗日函数:$L(w, b, \lambda) = \frac{1}{2}w^Tw+\sum_{i=1}^N \lambda_i(1-y_i(w^Tx+b))$

  • 从有约束变成无约束:

    • $\min_{w,b} \max_{\lambda} L(w, b, \lambda)$
    • $s.t. \lambda_i \ge 0$
  • 对偶问题(dual problem)

    • $\max_\lambda \min_{w, b} L(w, b, \lambda)$
    • $\lambda_i \ge 0$
  • 求偏导数得到结果:$\min_{w,b} L(w, b, \lambda)$
    $$\frac{\partial L}{\partial b} = 0 \to \sum_{i=1}^N \lambda_i y_i = 0$$
    $$L(w, b, \lambda) = \frac{1}{2}w^Tw + \sum_{i=1}^N \lambda_i - \sum_{i=1}^N \lambda_i y_i (w^T x_i + b)$$
    $$ = \frac{1}{2}w^Tw + \sum_{i=1}^N \lambda_i - \sum_{i=1}^N \lambda_i y_i w^T x_i + \sum_{i=1}^N \lambda_i y_i b$$
    $$= \frac{1}{2}w^Tw + \sum_{i=1}^N \lambda_i - \sum_{i=1}^N \lambda_i y_i w^T x_i$$

    $$\frac{\partial L}{\partial w} = \frac{1}{2}\cdot 2w - \sum_{i=1}^N \lambda_i y_i x_i = 0 \to w^* = \sum_{i=1}^N \lambda_i y_i x_i$$

    $$\min L(w, b, \lambda) = -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i \lambda_j y_i y_j x_i^T x_j + \sum_{i=1}^N \lambda_i$$

  • 最终的求解为:

    • $\max_\lambda -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i \lambda_j y_i y_j x_i^T x_j + \sum_{i=1}^N \lambda_i$
    • $\lambda_i \ge 0$
    • $\sum_{i=1}^N \lambda_i y_i = 0$

9. SVM- 硬间隔 - 模型求解 -KKT 条件

  • KKT: 原问题和对偶问题之间具有强对偶关系的充要条件

  • KKT 条件:

    • $\frac{\partial L}{\partial w} = \frac{\partial L}{\partial b} = \frac{\partial L}{\partial \lambda} = 0$
    • 互补充斥:$\lambda_i(1-y_i(w^Tx_i+b) = 0$
    • 对偶问题可行:$\lambda_i \ge 0$
    • 原问题可行: $1-y_i(w^Tx_i+b) \le 0$
  • 求解结果:

    • $w^* = \sum_{i=1}^N \lambda_i y_i x_i$: 只和决策向量的那些样本有关。
    • $b^* = y_k - \sum_{i=1}^N \lambda_i y_i x_i^T x_k$

10. SVM- 软间隔 - 模型定义

  • soft: 允许有一点点错误: $\min\frac{1}{2}w^Tw + loss$

    • ① loss = $\sum_{i=1}^N I{y_i(w^Tx_i + b) < 1}$ , 即错误的点的个数, 缺点是关于 w 不连续。

    • ② loss 为距离

    • 如果: $y_i(w^Tx_i+b) \ge 1$, loss = 0

    • 如果: $y_i(w^Tx_i+b) < 1$, loss = $1-y_i(w^Tx_i+b)$

    • 即: loss = $\max{0, 1-y_i(w^Tx_i+b)}$

  • 软间隔:假设 $\xi_i = 1 - y_i(w^Tx_i+b), \xi_i \ge 0$
    $$\min_{w,b} \frac{1}{2}w^Tw + C\sum_{i=1}^N \xi_i$$
    $$y_i(w^Tx_i+b) \ge 1-\xi_i$$
    $$\xi_i \ge 0$$

11. SVM- 约束优化问题 - 若对偶性证明

  • 需要证明的内容: 对偶问题 <= 原问题; $\max_{\lambda, \eta} \min_x L(x, \lambda, \eta) <= \min_x \max_{\lambda, \eta} L(x, \lambda, \eta), \lambda_i \ge 0$

  • 若对偶性质证明:
    $$\min_x L(x, \lambda, \eta) \le L(x, \lambda, \eta) \le \max_{\lambda, \eta}L(x, \lambda, \eta)$$
    $$A(\lambda, \eta) \le C \le B(x)$$
    $$\max A(\lambda, \eta) \le \min B(x)$$
    证毕

12. SVM- 约束优化问题 - 对偶关系之几何角度解释(需要理解)

13. SVM- 约束优化问题 - 对偶关系 -slater condition

  • 凸优化 + slater condition 强对偶 的 充分条件

  • 定义: 存在一个点 x 在 定义域 相对内部。 对于所有的 i, 有 $m_i(x) < 0$

    • 对于大多数凸优化, slater 成立
    • 松弛的 slater: M 中有 k 个放射函数

14. SVM- 约束优化问题 - 对偶关系 -KKT 条件

  • 对偶问题(dual problem) ,原问题(primal problem), 强对偶关系($d^*=p^*$). 强对偶关系是 KKT 条件的充分条件

  • KKT 条件

    • 可行条件($m_i(x^*)\le 0, n_j(x^*)=0, \lambda^* \ge 0$)
    • 互补松弛: $\lambda_i m_i = 0$
    • 梯度为 0: ${\frac{\partial L(x, \lambda^*, \eta^*)}{\partial x}|}_{x = x^*} = 0$

15. 核方法 - 背景介绍

  • 非线性带来高维转化(从模型角度)

  • 对偶表示带来内积(从优化角度)

  • Cover Theonem: 高维空间比低纬空间更容易线性可分

坚持原创技术分享,您的支持将鼓励我继续创作!