机器学习-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 \(w^Tx-b=0\) 使得距离两类samples的距离都比较远。

Hard-margin

因此我们一开始的goal function是：\(\max \frac 2 {||w||}\)

该形式可以转化成: \[ \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] \] \(\alpha_i\): Lagrange Multiplier

对\(\mathcal{L}\)求解偏导： \[ \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 \]

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

再把\(w=\sum\alpha_iy_ix_i\)代进\(\mathcal{L}\)中，使得\(\mathcal{L}\)中没有\(w\)，只有\(\alpha_i\)一个参数。 \[ \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\\ \] 因为：\(\frac{\partial \mathcal{L}}{\partial b}=\sum\alpha_iy_i=0\) \[ \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 \] 对于参数\(C\):

• 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)) \] \(y_i\): 表示样本的真实标签（通常为-1或1）

\(w\cdot x+b\): 表示样本的预测分类（即决策函数输出的值）。

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 w}\)不变，此处求解\(\frac{\partial \mathcal{L}}{\partial \xi_i}\) \[ \frac{\partial \mathcal{L}}{\partial \xi_i}=C-\alpha_i-\beta_i=0\\ \alpha_i=C-\beta_i \] 其他的\(\frac{\partial \mathcal{L}}{\partial w}\)以及\(\frac{\partial \mathcal{L}}{\partial b}\)均不变。

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 \] 我们容易发现：\(\frac{\partial \mathcal{L}}{\partial w}\)以及\(\frac{\partial \mathcal{L}}{\partial b}\)均不变。

对于soft-margin将\(w=\sum\alpha_iy_ix_i\)代进去： \[ \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\\ \] 因为：\(\sum_i\alpha_i\xi_i+\sum_i\beta_i\xi_i=C\sum_i^m\xi_i\)(\(\frac{\partial \mathcal{L}}{\partial \xi_i}=C-\alpha_i-\beta_i=0\))以及\(\frac{\partial \mathcal{L}}{\partial b}=\sum\alpha_iy_i=0\) \[ \mathcal{L}=\sum\alpha_i-\frac 1 2 \sum_i\sum_j\alpha_i\alpha_jy_iy_jx_ix_j \] 你会发现soft-margin计算出来的\(\mathcal{L}\)和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^*\)比较简单： \[ w^*=\sum\alpha_i^*y_ix_i \] 对于\(b\)：

• Find a $_i^*(0, 𝐶) $vector
• Thus, \(y_i(w^Tx_i+b^*)=1\)
• Thus, \(b^*=y_i-w^Tx_i\)

在soft margin的情况下，由于存在一些样本落在间隔边界内部，因此选择多个支持向量计算偏置b可能更合适。一种常见的做法是选择所有满足\(0 < \alpha_i < C\)的支持向量，并计算它们的平均值作为偏置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 \] 此处的\(I\)是单位矩阵，A是对称矩阵，式2式正交矩阵Q的性质，\(\Lambda\)是协方差矩阵。

英文版：

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

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

因此原始的协方差矩阵为： \[ 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_X=\frac 1 n X_cX_c^T\)，代进去得： \[ C_Y=\frac 1 nPX_cX_c^TP^T=\frac 1 {n^2}PC_XP^T \] 对\(X_cX_c^T\)进行特征分解：\(X_cX_c^T=Q\Lambda Q^T\) \[ C_Y=\frac 1 nPX_cX_c^TP^T=\frac 1 nPQ\Lambda Q^TP^T \] 令\(P=Q^T\),\(C_Y=\frac 1 n \Lambda\)

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 \(V\)
4. Obtain the Eigenvector of the covariance matrix by \(u=Xv\)

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 \] 得到的形式刚好是求解特征向量的标准形式(\(Ax=\lambda x\))

At optimum, we have \(p^{*^T}S_bp^*=\lambda\)

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

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

如果\(S_w\) 不是可逆的(invertible)的：就使用\((S_w+\lambda I)^{-1}\)(这个是可逆的)

如果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)} \] 在\(S_w^{-1}S_b\)中选择前C个特征向量，最多可以有C个投影，这取决与矩阵的秩： \[ rank(S_w^{-1}S_b)\le rank(S_b)\le C \]