文章目录

2020-06学习报告线性回归LASSO 回归Ridge 岭回归感知机算法PLApocket算法线性判别分析逻辑回归高斯判别分析PCAhard-margin SVMsoft-margin SVM

2020-06学习报告

本月学习机器学习常见算法，并做相应的数学推导。

具体的数学推导见文件夹中的pdf文件。本word是对上面的算法进行简单的总结。

机器学习模型 主要包括以下流程：

首先根据实际问题(比如 一些 先验信息的假设)，思考自己的解决方案 (算法思路)将这个解决方案 用 数学的公式 表达出来,这个数学模型其实是一个最优化问题（建模）这个最优化问题 一般为 极大似然估计拉格朗日法获得误差损失函数loss 求解上面的最优化问题，一般方法： 如果好解，可以直接求偏导即可。如果样本很大，可以 使用 梯度下降法，每次用小样本集迭代更新参数如果不好解，可以假定其有隐藏变量，从而使用EM算法求解参数

下面，通过上面的流程理清各个算法：

线性回归

模型思路：

我们可以用一条线y = wx+b尽可能逼进原样本点,但是

原本我们的样本x都是由模型f(w)生成的，但是在外界干扰的条件下，模型f(w)对x的输出(即y)会有所改变。我们 假设这个干扰 服从高斯分布 均值为0，方差为 σ

建成数学模型

$$\begin{gathered} 误差干扰\epsilon \sim N(0,{\sigma }^2) \\ 干扰下样本标签y=f(w)+\epsilon =w^{T}x+\epsilon \\ 则y也服从正态分布y|x:w\sim N(w^{T}x,{\sigma }^2) \\ 即p(y|x;w=\frac{1}{\sqrt{2\ast \pi }\ast \sigma }\ast exp-\frac{(y-w^{T}x{)}^2}{2{\sigma }^2}) \end{gathered}$$

转为优化问题（这里通过极大似然估计MLE）(如果是用损失函数的方法那就是最小二乘估计) $$\begin{gathered} 希望找到一组w,使得模型的似然P(Y|X;w)=\prod _{i=1}^{N}p(y_i|x_i:w)最大化 \\ 这里p(y_i|x_i:w)上面已经给出，所以我们已经可以完全表示出模型的似然P(Y|X;w) \\ 即w=argmax(logP(Y|X;w)) \end{gathered}$$

求解上面的最优化问题

使用梯度下降发，求偏导即可。（具体数学看文件夹里面的pdf） $$\begin{gathered} 求解出最终模型w=(x^{T}x{)}^{-1}{x}^{T}Y \\ 模型y=w^{T}x \end{gathered}$$

模型其他重要知识点

线性回归也可使用最小二乘的思想建立模型，与上面不同的是，上面是最大化似然，而这里是最小化样本误差。二者最终还是通过梯度下降法求解参数

事实上，最小二乘估计 就是 干扰服从高斯分布(均值为0)的极大似然法则

即最小二乘的argmin(loss) 就相对于 MLE的argmax(P(Y|X:w))

正则化的频率派 == 贝叶斯派

LASSO 回归

与上面线性回归类似，只是在上面的模型上加了一个L1正则化 $$w=argmin(loss+\lambda ||w||)$$

Ridge 岭回归

与上面线性回归类似，只是在上面的模型上加了一个L2正则化 $$w=argmin(loss+\lambda w^{T}w)$$

感知机算法PLA

模型思想： $$\begin{gathered} 首先前提要求样本数据是线性可分的。 \\ 现在就找一条线y=w^{T}x将样本分开，且错误的情况尽可能的小 \end{gathered}$$

建成数学模型 $$\begin{gathered} f(x)=sign(w^{T}x) \\ sign(a)=\{\begin{array}{cc}+1& a>=0\\ -1& a<0\end{array} \end{gathered}$$

转为优化问题（这里通过构建损失函数loss） $$\begin{gathered} 想要分错的个数尽可能的少，即 \\ Loss(w)=\sum _{i=1}^N-y_i{w}^T{x}_i \\ 注意:\begin{array}{cc}{w}^T{x}_i>0& y_i=+1\\ w^T{x}_i<0& y_i=-1\end{array}\}==>y_i{w}^T{x}_i>0表示样本(x_i,y_i)被正确分类，y_i{w}^T{x}_i<0表示样本(x_i,y_i)被错误分类 \end{gathered}$$

$$注意不要使用Loss(w)=\sum _{i=1}^{N}I(y_i{w}^T{x}_i<0),因为这个函数不好求导$$

求解上面的最优化问题

使用梯度下降法，求偏导即可 $$\begin{gathered} 求解出最终模型w=w+\lambda y_i{x}_i \\ 模型y=sign(w^{T}x) \end{gathered}$$

模型其他重要知识点

知道发展趋势： 感知机 ----> 多层感知机（神经网络）----->深度学习

PLA算法可以理解为 错误驱动算法。

上面结论中，w的迭代方式为 $$w=w+\lambda y_i{x}_i$$ 这个来一个错误样本，就对w进行一次更新，其实就是来一个样本就微调一次分割线。具体可见林轩田的https://blog.csdn.net/MosBest/article/details/52029217

PLA算法具有局限性

当遇到一个错误样本(x_i, y_i)，微调一次w后，改正后的w可以使得(x_i, y_i)分类正确。但是前面的0~i-1个样本，可能分类结果发生改变。

即PLA只有运行到最后，最终的模型才有效。中间的w不能用。

PLA前提必须要求样本集线性可分。不然w迭代不会收敛。

pocket算法

pocket算法是PLA的一种改进。

pocket算法是一种贪心算法的思想。即w在迭代的过程中 $$w=w+\lambda y_i{x}_i$$ 如果迭代后w可以使得前面i个样本都分类正确，那么修改w, 否则跳过本次修改，直接进行下一步迭代。

所以，pocket算法手里拿着的参数w永远是当前最优的解。

线性判别分析

模型思路

线性判别分析是一种降维的思想。它将样本从高维重新投射到低维，认为样本在重新构建的低维特征中是可以线性可分的。

（ 这个和SVM的核方法正好相反。SVM核方法是将样本从低维投射到高维，认为样本在高维是可以线性可分 ）

建模思想： **类内小，类间大 **

可以理解为 高类聚，低耦合。即将样本集投射到低维后，相同类别的样本的方差小（高类聚），不同类别的样本的均值离得很远（低耦合）

建成数学模型 $$\begin{gathered} 假设是二分类问题,则样本集N可分为类别1的样本N1,类别1的样本N2.其中N=N1+N2 \\ 新的低维特征为w \\ 则样本x_i在向量w上的投影值为z_i=w^T{x}_i(如果不理解，看文件夹中的pdf有详细证明) \\ 则类别1的均值为\overline{z_1}=\frac{1}{N_1}\sum _{i=1}^{N_1}{w}^T{x}_i \\ 则类别1的方差为\overline{S_1}=\frac{1}{N_1}\sum _{i=1}^{N_1}(w^T{x}_i-\overline{z_1})(w^T{x}_i-\overline{z_1}{)}^T \end{gathered}$$ $$\begin{gathered} 则类别2的均值为\overline{z_2}=\frac{1}{N_2}\sum _{i=2}^{N_1}{w}^T{x}_i \\ 则类别2的方差为\overline{S_2}=\frac{1}{N_2}\sum _{i=1}^{N_2}(w^T{x}_i-\overline{z_2})(w^T{x}_i-\overline{z_2}{)}^T \\ 则类间：(\overline{z_1}-\overline{z_2}{)}^2 \\ 类内:S_1+S_2 \end{gathered}$$

$$\begin{gathered} 则类间：(\overline{z_1}-\overline{z_2}{)}^2 \\ 类内:S_1+S_2 \\ 则类内小，类间大可表示为J(w)=\frac{(\overline{z_1}-\overline{z_2}{)}^2}{S_1+S_2} \end{gathered}$$

转为优化问题

这里是自定义的一个优化函数:最大化 类内小，类间大J(w) $$argmaxJ(w)=\frac{(\overline{z_1}-\overline{z_2}{)}^2}{S_1+S_2}$$

求解上面的最优化问题

涉及到矩阵运算，求偏导。(不是用梯度下降法) $$\begin{gathered} w=\lambda \ast （\overline{x_{c1}}-\overline{x_{c2}}） \\ 即，最终的w就是两个类别样本均值点连起来的方向。 \end{gathered}$$

逻辑回归

模型思路

逻辑回归是一个概率判别模型。是要对P(y|x)进行建模，即给定样本x时，计算它的标签y=k的概率值，然后选择概率最大的类别作为它的标签。

建成数学模型 $$\begin{gathered} 逻辑回归已给定：对p(y|x)建模时，使用sigmoid函数 \\ p1=p(y=1|x)=\frac{1}{1+exp\{-w^{T}x\}} \\ p0=p(y=0|x)=1-p1=\frac{exp\{-w^{T}x\}}{1+exp\{-w^{T}x\}} \\ p(y|x)=p_1^y\ast p_0^{1-y} \end{gathered}$$

转为优化问题

使用极大似然估计MLE $$MLE\overline{w}=argmax(log(P(Y|X)))=argmax(log\prod _{i=1}^{N}p(y+i|x_i))$$

求解上面的最优化问题

求偏导，梯度下降法

模型其他重要知识点

事实上，你咋计算时，你会发现

极大似然 argmax P(Y|X) 相对于 最小化loss argmin loss . (在逻辑回归中你会发现loss function就是交叉熵)

即在逻辑回归中 极大似然法则 == 最小化交叉熵

高斯判别分析

模型思路

先假设

标签y服从伯努利分布(假设2分类)每一个类别的样本集都服从高斯分布。且不同类别的样本集之间均值不同，但是方差相同。

模型和逻辑回归类型，也是对p(y|x)进行建模。不同的是，逻辑回归使用sigmoid函数，而高斯判别分析使用的是贝叶斯定理。 $$\begin{gathered} p(y_i|x_i)\propto p(x_i|y_i)\ast p(y_i) \\ 因为我们这里最后只需比较样本x_i取各个标签的概率大小，没必要把概率值求出来。所以分母不用求，因为大家的分母都是一样的大小。 \end{gathered}$$

建成数学模型 $$\begin{gathered} 其中y服从伯努利分布（公式就不写了） \\ p(x_i|y_i)服从高斯分布 \\ p(y_i|x_i)\propto p(x_i|y_i)\ast p(y_i) \\ 则只要求出上面分布的参数，就可求出p(y_i|x_i) \\ \overline{y}=argmax(p(y|x))=argmax(p(y)p(x|y)) \end{gathered}$$

转为优化问题

极大似然估计 $$\begin{gathered} L(\theta )=log\prod _{i=1}^{N}P(y_i|x_i)=log\prod _{i=1}^{N}P(x_i|y_i)\ast P(y_i)=log\prod _{i=1}^{N}P(x_i,y_i) \\ \theta =argmaxL(\theta ) \end{gathered}$$

求解上面的最优化问题

求偏导 $$\begin{gathered} 伯努利分布的参数：{\varphi }_1=N_1/N{\varphi }_2=N_2/N \\ 则我们就可以表示出p(y_1)和p(y_2)了 \\ 高斯分布的参数:u_1=\frac{{\sum }_{i=1}^N{y}_i{x}_i}{N_1}{u}_2=\frac{{\sum }_{i=1}^N{y}_i{x}_i}{N_2}方差S=没算 \\ 则我们就可以表示出p(x_i|y_i) \\ 最终我们就可以通过p(y_i|x_i)\propto p(x_i|y_i)\ast p(y_i)比较概率，得出样本标签 \end{gathered}$$

PCA

模型思路

PCA是用于降维的，希望将 高维的具有相关性的特征 降成 低维的无关的特征

思想：

​ 有两个，这两个本质上相同。

最大投影方差最小重构距离

下面仅仅讲最大投影方差的原理，而最小重构距离看pdf即可。

建成数学模型 $$\begin{gathered} 首先要将样本中心化x_i-\overline{x} \\ 令新的特征为u,其模值为1，即u^{T}u=1。则点x_i-\overline{x}在向量u上的投影值为(x_i-\overline{x}{)}^{T}u \\ 则样本x_i-\overline{x}的投影方差为((x_i-\overline{x}{)}^{T}u-0{)}^2 \\ 则N个样本的总方差为J=\frac{1}{N}\sum _{i=1}^N((x_i-\overline{x}{)}^{T}u-0{)}^2=...=u^{T}Su \\ 我们的目标就是找到合适的u，使得总投影方差J最大。 \\ 而这个u就是我们的新特征 \end{gathered}$$

转为优化问题

拉格朗日定理 $$\begin{gathered} J=\frac{1}{N}\sum _{i=1}^N((x_i-\overline{x}{)}^{T}u-0{)}^2=...=u^{T}Su \\ \overline{u}=argmaxJ=argmax{u}^{T}Su且要求u^{T}u=1 \\ 则可供偶见拉格朗日定理，L(u,\lambda )=u^{T}Su+\lambda (1-u^{T}u) \end{gathered}$$

求解上面的最优化问题

求偏导, 得 $$\begin{gathered} Su=\lambda u \\ 其中S是样本集的协方差矩阵,则，根据线性代数，要求解的特征u就是要求样本集的协方差矩阵的特征向量。 \\ 即新特征u是样本的协方差矩阵的特征向量 \end{gathered}$$

hard-margin SVM

模型思路

这里假设样本数据本就线性可分。

在感知机算法中，我们是只要找一条分割线将样本集分开即可。但是，一般满足这样的分割线（能够全部正确分类样本）其实有很多条，那么如何从这些分割线选出最优的一条，使得这条分割线的健壮性，容错性更强。

SVM就是用来干这个的。

思想：SVM是最大间隔分类器，在数据本就可分的前提下，我们希望我们的分割线离它最近的样本点尽可能的远。

建成数学模型

最开始为： $$\begin{gathered} maxmargin(w,b) \\ s.t.w^T{x}_i+b>0,y_i=+1; \\ {w}^T{x}_i+b<0,y_i=-1 \end{gathered}$$ 其中 $$\begin{gathered} maxmargin(w,b)化简为min\frac{1}{2}{w}^{T}w \\ 具体看pdf,主要用到w,b可以等比缩放 \\ 所以，就变为 \\ min\frac{1}{2}{w}^{T}w \\ s.t.w^T{x}_i+b>0,y_i=+1; \\ {w}^T{x}_i+b<0,y_i=-1 \end{gathered}$$

转为优化问题

将上面的优化问题，

先利用拉格朗日定理把带约束的优化问题转为无约束的优化问题 $$\begin{gathered} L(w,b,\lambda )=\frac{1}{2}{w}^{T}w+\sum _{i=1}^N{\lambda }_i(1-y_i(w^T{x}_i+b)) \\ mi{n}_{w,b}ma{x}_{\lambda }L(w,b,\lambda ) \\ s.t.{\lambda }_i>=0 \end{gathered}$$

然后利用强对偶关系 $$\begin{gathered} L(w,b,\lambda )=\frac{1}{2}{w}^{T}w+\sum _{i=1}^N{\lambda }_i(1-y_i(w^T{x}_i+b)) \\ ma{x}_{w,b}mi{n}_{\lambda }L(w,b,\lambda ) \\ s.t.{\lambda }_i>=0 \end{gathered}$$

对 min的一次偏导计算，得到

$$\begin{gathered} mi{n}_{\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 \\ s.t.{\lambda }_i>=0 \\ \sum _{i=1}N{\lambda }_i{y}_j=0 \end{gathered}$$

求解上面的最优化问题

先求偏导，然后利用KKT条件（特别是其中中松弛互补条件），可得 $$\begin{gathered} w^{\ast }=\sum _{i=0}^N{\lambda }_i{y}_i{x}_i \\ {b}^{\ast }=y_k-\sum _{i=0}^N{\lambda }_i{y}_i{x}_i^T{x}_k \end{gathered}$$ 最终的模型为 $$f(x)=sign(w^{\ast }x+b^{\ast })$$

soft-margin SVM

模型思路

​ 上面讲解hard-margin SVM时，我们假设了样本时线性可分的。

但是实际情况下，因为外界干扰等因素，样本(x,y)实际上是有波动的。

为了能够让我们的模型可以适应这种情况（即模型允许有少量的误差），我们就引入soft-margin SVM.

建成数学模型

我们的分割面方程为wx+b = 0, 则wx+b = 1 和 wx+b = -1 正好经过 模型的两个支持向量。

为了能让SVM允许有少量误差，我就假定支持向量可以适当的向wx+b=0移动一些，则经过该支持向量的超平面将会变成 wx+b=+1- \xi 或者 wx+b=-1 + \xi

即 $$\begin{gathered} y_i(w^T{x}_i+b)=1-{\xi }_i \\ 这个{\xi }_i就相对于是样本x_i的误差，则总loss=C\sum _{i=1}^N{\xi }_i \\ 则最终的模型是在hard-marginSVM的基础上再加上loss=C\sum _{i=1}^N{\xi }_i \end{gathered}$$ 所以，最终模型为 $$\begin{gathered} {\xi }_i=1-y_i(w^T{x}_i+b) \\ mi{n}_{w,b}\frac{1}{2}{w}^{T}w+C\sum _{i=1}^N{\xi }_i \\ s.t.y_i(w^T{x}_i+b)>=1-{\xi }_i \\ {\xi }_i>=0 \end{gathered}$$

转为优化问题

同hard-margin SVM

求解上面的最优化问题

同hard-margin SVM