机器学习-Ch4-6

主要内容:SVM、PCA、LDA

Contents

[TOC]

Ch4&5 Linear Classification and SVM

属于statistical ML。

Primal Problem VS Dual Problem: 原始问题is hard。对偶问题的解恰好对应着原始问题的解，因此只要能解决对偶问题，就意味着我们解出了原始问题。

Linear Classifiers

在线性的分类器中处理分类，就是计算特征的线性组合：

$$s_c=\sum_iw_i^cx_i+b_c\\ s_c=w_c^Tx+b_c$$

如果是二分类问题：结果大于0，属于class 1，结果小于0，属于class 2。

SVM

目标：find a hyperplane 使得距离两类samples的距离都比较远。

Hard-margin

因此我们一开始的goal function是：

该形式可以转化成:

$$\min \frac1 2 ||w||^2\\ s.t.\ y_i*(w\cdot x+b)\ge 1$$

该形式符合凸优化理论，可以使用拉格朗日乘子法解决问题（Lagrangian Dual Problem）

$$\mathcal{L}=\frac 1 2||w||^2-\sum\alpha_i[y_i*(w\cdot x_i+b)-1]$$

: Lagrange Multiplier

对求解偏导：

$$\frac{\partial \mathcal{L}}{\partial w}=w-\sum\alpha_iy_ix_i=0\\ w=\sum\alpha_iy_ix_i\\\\ \frac{\partial \mathcal{L}}{\partial b}=\sum\alpha_iy_i=0$$

• : is a weighted sum of the input vectors ( )
• 很多情况下: because this point doesn’t contribute to the margin

再把代进中，使得中没有，只有一个参数。

$$\mathcal{L}=&\frac 1 2w^Tw-\sum\alpha_i[y_i*(w\cdot x_i+b)-1]\\ =&\frac 1 2 (\sum\alpha_iy_ix_i)(\sum\alpha_jy_jx_j)-\sum\alpha_i[y_i\sum\alpha_jy_jx_j\cdot x_i]+b\sum\alpha_iy_i+\sum\alpha_i\\$$

因为：

$$\mathcal{L}=&\frac 1 2 (\sum\alpha_iy_ix_i)(\sum\alpha_jy_jx_j)-\sum\alpha_i[y_i\sum\alpha_jy_jx_j\cdot x_i]+\sum\alpha_i\\ =&\sum\alpha_i-\frac 1 2 (\sum\alpha_iy_ix_i)(\sum\alpha_jy_jx_j)\\ =&\sum\alpha_i-\frac 1 2 \sum_i\sum_j\alpha_i\alpha_jy_iy_jx_ix_j$$

Soft-margin

其goal function：

$$\min \frac 1 2 ||w||^2+C\sum^m_i\xi_i\\ s.t.\ y_i*(w\cdot x+b)\ge 1-\xi_i\\ \xi_i\ge0$$

对于参数:

• Low C: we don’t pay anything for these violations (width is king)
• High C: we pay a lot for violations (no violations is king)

突然在PPT中介绍了一下hinge loss——

Hinge Loss: 一种常用的损失函数。Hinge Loss用于衡量样本的分类错误和分类边界的间隔。其在soft-margin中的定义如下：

$$\min \frac 1 2||w||^2+C\sum^m_i\max(0,1-y_i*(w\cdot x+b))$$

: 表示样本的真实标签（通常为-1或1）

: 表示样本的预测分类（即决策函数输出的值）。

Hinge Loss的目标是使正确分类的样本的损失为0，并增大错误分类样本的损失。在软间隔分类中，Hinge Loss通常与正则化项结合使用，以平衡分类错误和模型复杂度。通过最小化Hinge Loss和正则化项，可以得到一个具有较小间隔违规和较小模型复杂度的分类模型，从而在训练集上和测试集上获得良好的性能。

接下来继续我们soft-margin的求解部分：

$$\mathcal{L}=\frac 1 2 ||w||^2+C\sum^m_i\xi_i+\sum_i\alpha_i(1-\xi_i-y_i(w^Tx_i+b))-\sum_i\beta_i\xi_i$$

求解偏导，因为只是加了其他项，所以不变，此处求解

$$\frac{\partial \mathcal{L}}{\partial \xi_i}=C-\alpha_i-\beta_i=0\\ \alpha_i=C-\beta_i$$

其他的以及均不变。

KKT条件：

$$\begin{cases} stationarity:&\nabla\mathcal{L}(x^*,{\mu_i})=\nabla f(x^*)+\sum_i\mu_i\nabla g_i(x^*)=0\\ primary\ feasibility:&g_i(x^*)\le 0\\ dual\ feasibility:&\mu_i^*\ge0\\ complementary\ slackness:&\mu_i^*g_i(x^*)=0 \end{cases}$$

对比一下hard-margin以及soft-margin的拉格朗日函数：

$$\mathcal{L}=\frac 1 2||w||^2-\sum\alpha_i[y_i*(w\cdot x_i+b)-1]\\ \mathcal{L}=\frac 1 2 ||w||^2+C\sum^m_i\xi_i+\sum_i\alpha_i(1-\xi_i-y_i(w^Tx_i+b))-\sum_i\beta_i\xi_i$$

我们容易发现：以及均不变。

对于soft-margin将代进去：

$$\mathcal{L}=&\frac 1 2 ||w||^2+C\sum^m_i\xi_i+\sum_i\alpha_i(1-\xi_i-y_i(w^Tx_i+b))-\sum_i\beta_i\xi_i\\ =&\frac 1 2 \sum_i\sum_j\alpha_i\alpha_jy_iy_jx_ix_j+C\sum^m_i\xi_i+\sum_i\alpha_i-\sum_i\alpha_i\xi_i-\sum_i\sum_j\alpha_i\alpha_jy_iy_jx_ix_j+b\sum_i\alpha_iy_i-\sum_i\beta_i\xi_i\\$$

因为：()以及

$$\mathcal{L}=\sum\alpha_i-\frac 1 2 \sum_i\sum_j\alpha_i\alpha_jy_iy_jx_ix_j$$

你会发现soft-margin计算出来的和hard-margin的也是一样的。

因此对偶问题是：

$$\max_{\alpha_i}[\sum_i\alpha_i-\frac 1 2 \sum_i\sum_j\alpha_i\alpha_jy_iy_jx_ix_j]\\ s.t.\ 0\le\alpha_i\le C,\sum_i\alpha_iy_i=0$$

我们的原问题是：

$$\min \frac 1 2 ||w||^2+C\sum^m_i\xi_i\\ s.t.\ y_i*(w\cdot x+b)\ge 1-\xi_i\\ \xi_i\ge0$$

怎么从对偶问题转化为原问题呢？

比较简单：

$$w^*=\sum\alpha_i^*y_ix_i$$

对于：

• Find a vector
• Thus,
• Thus,

在soft margin的情况下，由于存在一些样本落在间隔边界内部，因此选择多个支持向量计算偏置b可能更合适。一种常见的做法是选择所有满足的支持向量，并计算它们的平均值作为偏置b。

$$\mu_i^*g_i(x^*)=0\ \forall i\\$$

Ch6 PCA, LDA and Dimensionality reduction

Dimensionality reduction

其基本原理是：Preserve “useful” information in low dimensional data.

其常用的方法：PCA，LDA

reasons:

• Extract underlying factors
• Reduce data noise
  • Face recognition
  • Applied to image de-noising
• Reduce the number of model parameters
  • Avoid over-fitting
  • Reduce computational cost
• Visualization

PCA(Principal Component Analysis)

==无监督学习方法。==

PCA：

• Transform data to remove redundant information
• Keep the most informative dimensions after the transformation

其步骤:

• 去中心化(De-correlating data): Correlation can be removed by rotating the data point or coordinate

• 计算协方差矩阵，找特征向量与特征值(Eigen decomposition)

  $$A=Q\Lambda Q^T\\ QQ^T=Q^TQ=I$$

  此处的是单位矩阵，A是对称矩阵，式2式正交矩阵Q的性质，是协方差矩阵。

英文版：

1. Subtract mean
2. Calculate the covariance matrix
3. Calculate eigenvectors and eigenvalues of the covariance matrix
4. Rank eigenvectors by its corresponding eigenvalues
5. Obtain P with its row vectors corresponding to the top k eigenvectors

其数学原理：是中心化数据矩阵（每个数据减去其均值向量之后的结果）

因此原始的协方差矩阵为：

$$C_X=\frac 1 n X_cX_c^T$$

我们想找到一个矩阵P,可以对数据去中心化：

$$Y=PX_c\\ C_Y=\frac 1 n PX_c(PX_c)^T=\frac 1 nPX_cX_c^TP^T$$

有因为：，代进去得：

$$C_Y=\frac 1 nPX_cX_c^TP^T=\frac 1 {n^2}PC_XP^T$$

对进行特征分解：

$$C_Y=\frac 1 nPX_cX_c^TP^T=\frac 1 nPQ\Lambda Q^TP^T$$

令,

High dimensionality issue（Kernel PCA）

1. Centralize data
2. Calculate the kernel matrix
3. Perform Eigen-decomposition on the kernel matrix and obtain its eigenvector
4. Obtain the Eigenvector of the covariance matrix by

LDA(Linear Discriminative Analysis)

有监督学习：利用了样本的类别标签信息来进行模型训练和分类。

Supervised information ：

1. Class label
2. Data from the same class => Become close
3. Data from different classes => far from each other

LDA假设数据满足高斯分布，并且根据类别信息进行有监督训练。它的目标是通过最大化不同类别之间的距离（类间散度）和最小化同一类别内部的方差（类内散度），来实现在新的低维空间中使得不同类别更好地可分的投影。

将数据投影到低维空间，其新的均值以及方差如下：

$$\hat \mu=&\frac 1 N\sum^N_{i=1}p^Tx_i=p^T\frac 1 N \sum^N_{i=1}x_i=p^T\mu\\ \hat \sigma^2=&\frac 1 N \sum^N_{i=1}(p^Tx_i-p^T\mu)^2\\ =&\frac 1 N \sum^N_{i=1}p^T(x_i-\mu)(x_i-\mu)^Tp\\ =&p^T(\frac 1 N \sum^N_{i=1}(x_i-\mu)(x_i-\mu)^T)p$$

类内(between)以及类间(within)散度:

$$S_b=(\mu_1-\mu_2)(\mu_1-\mu_2)^T\\ S_w=\sum_{j=1,2}\frac 1 {N_j}\sum^{N_j}_{i=1}(x_i-\mu)(x_i-\mu)^T$$

其目标函数是：

$$\max \frac{p^TS_bp}{p^TS_wp}$$

将上述形式化为拉格朗日对偶问题的形式：

$$\max p^TS_bp\\ s.t.\ p^TS_wp=1\\\\ \mathcal{L}=p^TS_bp-\lambda(p^TS_wp-1)$$

对其求偏导得：

$$\frac{\partial \mathcal{L}}{\partial p}=0\\ 2S_bp-2\lambda S_wp=0\\ S_bp=\lambda S_wp\\ S_w^{-1}S_bp=\lambda p$$

得到的形式刚好是求解特征向量的标准形式()

At optimum, we have $p^{^T}S_bp^=\lambda$

表示在最优条件下，投影向量的转置与类内散度矩阵的乘积再与相乘的结果等于。

这个方程用于确定最佳的投影向量，使得类别之间的差异最大化，同时类内方差最小化。是类间散度矩阵，表示不同类别之间的差异程度。是一个标量，表示投影向量在最优条件下的特征值。

如果 不是可逆的(invertible)的：就使用(这个是可逆的)

如果LDA且Multi-class:

$$S_b=\sum^C_{i=1,j=1}(\mu_i-\mu_j)(\mu_i-\mu_j)^T=\sum_i(\mu_i-\mu)(\mu_i-\mu)^T\\ S_w=\sum^C_{j=1}\sum_{i\in C_j}(x_i-\mu)(x_i-\mu)^T\\ \max \frac{trace(P^TS_bP)}{reace(P^TS_wP)}$$

在中选择前C个特征向量，最多可以有C个投影，这取决与矩阵的秩：

$$rank(S_w^{-1}S_b)\le rank(S_b)\le C$$