算法岗面试——机器学习总结

作者: 早上起来闹钟又丢了 | 来源:发表于2019-06-24 11:46 被阅读37次

SVM！

参考资料支持向量机通俗导论（理解SVM的三层境界）
参考资料支持向量机（SVM）从入门到放弃再到掌握

支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的。

1.支持向量机主要是解决什么问题的？
SVM主要用于解决分类问题，它的目的是学会一个分类函数或分类模型(或者叫做分类器) 。

2.应用场景
支持向量机本身便是一种监督式学习的方法，它广泛地应用于统计分类以及回归分析中。

3.分类性质
通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，即支持向量机的学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。
以二维平面为例，如下图所示，二维空间中有粉色和蓝色的点，我们想用一条线来将他们分隔开，也就是图中红色这条直线，这条直线就是一个分类器。

此时我们称这些数据是线性可分的。
在一维空间中，分类器是一个点；在二维空间中，分类器是一条直线；在三维空间中，分类器是一个平面；在多维空间中，分类器是一个超平面。

4.分类的数学定义
以二维空间为例，给定训练样本集 $D={((x_{1},y_{1}),(x_{2},y_{2}),...,(x_{m},y_{m}))}, y_{i}\in \left \{ -1, 1\right \}$ , 线性分类器基于训练样本 $D$ 在二维空间中找到一条直线来分开二类样本。
接下来，我们拓展到多维数据。我们假定线性分类函数为 $f(x)=\omega^T x+b$ 。
显然，如果f(x) = 0 ，那么x 是位于超平面上的点。我们不妨要求对于所有满足f(x) < 0 的点，其对应的y 等于-1 ，而f(x) > 0 则对应y = 1 的数据点。

5.分类中会有许多个线性分类函数都满足要求，该如何选择？
在多维空间中，能够划分样本集的超平面有许多个，而我们要选择的，就是划分间隔最大的，也就是说这个超平面离两类样本都足够远，使得“间隔”最大。

6.“间隔”分类
“间隔”分为函数间隔和几何间隔。
函数间隔定义为： $\hat{\gamma}=y(\omega^Tx+b)=yf(x)$ ，定义超平面 $(\omega,b)$ 关于训练数据集 $T$ 的函数间隔为超平面 $(\omega,b)$ 关于 $T$ 中所有样本点 $(x_{i},y_{i})$ 的函数间隔最小值，其中， $x$ 是特征， $y$ 是结果标签， $i$ 表示第 $i$ 个样本，有： $\hat{\gamma}=min\hat{\gamma}_{i}(i=1,...,n)$ 。
但是这么定义会有一个问题，那就是如果将 $\omega$ 和 $b$ 进行成比例地改变，比如改变到 $2\omega$ 和 $2b$ ,，此时超平面并没有改变，但是函数间隔的值 $f(x)$ 已经变成了原来的2倍。

几何间隔其实就是将函数间隔除以 $||\omega||$ 。

函数间隔 $y*(\omega x+b)=y*f(x)$ 实际上就是
$|f(x)|$ ，只是人为定义的一个间隔度量；而几何间隔 $|f(x)|/||\omega||$ 才是直观上的点到超平面距离。

7.何为支持向量（Support Vector）
支持向量是一些点。如下图所示，黑色的实线是划分数据集最大间隔的超平面，存在这些点（紫色虚线和粉色虚线上的红蓝点）到超平面的距离为几何间隔，则这些点就是支持向量。

8.线性不可分
我们知道，数据是线性可分的是十分理想的情况，我们通常用到的数据都是线性不可分的。

再来看一下我们的目标函数： $max\frac{1}{||\omega||}s.t.,y_{i}(\omega ^Tx_{i}+b)\geq1,i=1,...,n$
求 $\frac{1}{||\omega||}$ 最大值就等同于求 $\frac{1}{2}||\omega||^2$ 最小值的问题，即： $min\frac{1}{2}||\omega||^2s.t.,y_{i}(\omega ^Tx_{i}+b)\geq1,i=1,...,n$
这样问题就转变成了一个凸优化问题，目标函数是二次的，约束条件也是线性的，因此是一个凸二次规划问题，因此这个问题可以用任何现成的QP (Quadratic Programming) 的优化包进行求解，归结为一句话即是：在一定的约束条件下，目标最优，损失最小。然而，能解决是能解决，解决起来的代价会非常大。由于它有特殊结构，Lagrange Duality 变换到对偶变量(dual variable) 的优化问题之后，可以找到一种更加有效的方法来进行求解，而且通常情况下这种方法比直接使用通用的QP 优化包进行优化要高效得多。

9.对偶形式
对偶算法的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。
Lagrange Duality：引入拉格朗日乘子 $\alpha$ ，这样可以通过拉格朗日函数将约束条件融合到目标函数里去： $L(\omega,b,\alpha)=\frac{1}{2}||\omega||^2 -\sum_{t=1}^{n}\alpha_{i}(y_{i}(\omega^T x_{i}+b)-1)$
令 $\theta(\omega)=\max_{\alpha_{i}\geq0}L(\omega,b,\alpha)$ 。
如果某个约束条件不满足时，例如 $y_{i}(\omega^T x_{i}+b)<1$ ，则 $\theta(\omega)=inf$ 。如果每个约束条件都满足，则有 $\theta(\omega)=\frac{1}{2}||\omega||^2$ 。
因此，在要求约束条件得到满足的情况下最小化 $\theta(\omega)=\frac{1}{2}||\omega||^2$ ，实际上等价于直接最小化 $\theta(\omega)$ ，此时目标函数变成了： $\min_{\omega,b}\theta(\omega)=\min_{\omega,b}\max_{\alpha_{i}\geq0}L(\omega,b,\alpha)=p^*$
这里用 $p^*$ 代表问题的最优值。
现在，把最小和最大的位置交换一下，便得到了对偶形式： $\max_{\alpha_{i}\geq0}\min_{\omega,b}L(\omega,b,\alpha)=d^*$
交换之后，用 $d^*$ 来表示新问题的最优值，并且有 $d^*\leq q^*$ ，直观上理解就是：最大值中最小的一个总也比最小值中最大的一个要大吧。
至此，我们现在要做的是先求 $L$ 对 $\omega、b$ 的极小，再求 $L$ 对 $\alpha$ 的极大。 $d^*$ 是 $p^*$ 的近似解，转化为对偶问题后，求解更容易。

待更新........

交叉熵损失函数

参考CSDN简单的交叉熵损失函数，你真的懂了吗？

1.交叉熵公式
$L=-[ylog\hat{y}+(1-y)log(1-\hat{y})]$

2.符号意义
$y$ 是数据的标签， $\hat{y}$ 是函数的预测。

3.公式推导
以二分类任务为例。
在二分类问题模型：例如逻辑回归「Logistic Regression」、神经网络「Neural Network」等，真实样本的标签为 [0，1]，分别表示负类和正类。模型最后会经过一个Sigmoid函数，函数输出结果表征当前样本标签概率为1的概率： $\hat{y}=P(y=1|x)$
那么我们可以知道，标签为0的概率为：
$1-\hat{y}=1-P(y=1|x)=P(y=0|x)$
从极大似然的角度出发，可以将上面两种情况整合到一起：
$P(y|x)=\hat{y}^y*(1-\hat{y})^{1-y}$
当y为1时， $P(y|x)$ 的结果为 $\hat{y}$ ；当y为0时， $P(y|x)$ 的结果为 $1-\hat{y}$ 。
对于概率表达式 $P(y|x)$ ，我们希望其越大越好，它越大也就说明我们预测得越准。在这里引入log函数，log函数并不会对函数本身的单调性产生影响，因此有： $logP(y|x)=log(\hat{y}^y*(1-\hat{y})^{1-y})=ylog\hat{y}+(1-y)log(1-\hat{y})$
接下来转变为损失函数。我们希望 $logP(y|x)$ 越大越好，将其转变为负值，那么我们就期望 $-logP(y|x)$ 越小越好，得到损失函数：
$L=-[ylog\hat{y}+(1-y)log(1-\hat{y})]$
我们上面得到的是单个样本的损失函数，对于N个样本的总体损失函数，将N个该式累加起来就好了：
$L=-\sum_{i=1}^{N}(ylog\hat{y}+(1-y)log(1-\hat{y}))$

4.对于多分类问题
上面我们讨论了，对于二分类问题，我们使用sigmoid函数作为概率计算函数，Sigmoid函数的表达式和图形如下所示：
$g(s)=\frac{1}{1+e^{-s}}$

那么对于多分类任务，该怎么办呢。
这时候要使用的是Softmax函数。Softmax函数的表达式如下所示：

$S_{i}=\frac{e^{z_{i}}}{\sum_{k=1}^{N}e^{z_{k}}}$

5.补充
Sigmoid和Softmax并不能作为损失函数，与损失函数没有关系，只是在分类任务中常常使用Softmax输出+交叉熵损失函数的求导。

Logistic Regression逻辑回归
原文CSDN逻辑回归（Logistic Regression, LR）简介

分类和回归是机器学习可以解决两大主要问题，从预测值的类型上看，连续变量预测的定量输出称为回归；离散变量预测的定性输出称为分类。

线性回归（Linear Regression）

1.目标
在多维空间，线性回归表示为 $h\theta (x)=\theta_{0}0 +\theta_{1}x_{1} +\theta_{2}x_{2} +...+\theta_{n} x_{n}$
简化形式为 $h\theta (x)=\sum_{i=0}^{n}\theta_{i} x_{i}=\theta ^Tx$ ，我们的目的，是要找到一个参数 $\theta$ 令 $h_{\theta}(x)$ 对数据拟合得最好。

2.损失函数
希望预测值与实际值尽可能接近，即看预测值与实际值之间的均方误差是否最小。
$J(\theta)=\frac{1}{2m}\sum_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)})^2$
定义均方误差有着非常好的几何含义，对应常用的欧式距离（Euclidean distance），基于均方误差最小化进行模型求解的方法称为“最小二乘法”（least square method）。

3.最小二乘法
矩阵表示： $J(\theta)=\frac{1}{2}(X\theta-Y)^2$ 展开并对其求偏导，令偏导 $\frac{\partial}{\partial\theta}J(\theta)=0$ 即可求得 $\theta$ :
$\theta=(X^TX)^{-1}X^TY$
然而现实任务中当特征数量大于样本数时， $X^TX$ 不满秩，此 $\theta$ 有多个解；而且当数据量大时，求矩阵的逆非常耗时；对于不可逆矩阵（特征之间不相互独立），这种正规方程方法是不能用的。所以，还可以采用梯度下降法，利用迭代的方式求解 $\theta$ 。

4.梯度下降法
梯度下降法的思想：
1）随机对 $\theta$ 赋初值（也可以直接置为0）。
2）改变 $\theta$ 的值，使得 $\theta$ 按梯度下降的方向进行减少。

利用梯度下降法，逐步最小化损失函数，找准梯度下降方向，即偏导数的反方向，每次前进一小步，直到收敛：

迭代更新的方式有多种
批量梯度下降（batch gradient descent），也就是是梯度下降法最原始的形式，对全部的训练数据求得误差后再对θθ进行更新，优点是每步都趋向全局最优解；缺点是对于大量数据，由于每步要计算整体数据，训练过程慢；
随机梯度下降（stochastic gradient descent），每一步随机选择一个样本对θθ进行更新，优点是训练速度快；缺点是每次的前进方向不好确定，容易陷入局部最优；
微型批量梯度下降（mini-batch gradient descent），每步选择一小批数据进行批量梯度下降更新θθ，属于批量梯度下降和随机梯度下降的一种折中，非常适合并行处理。

逻辑回归

虽然逻辑回归中有“回归”二字，但其实际上却是一种分类学习方法。
线性回归完成的是回归拟合任务，而对于分类任务，我们同样需要一条线，但不是去拟合每个数据点，而是把不同类别的样本区分开来。
对于二分类问题，y∈{0,1}，1表示正例，0表示负例。逻辑回归是在线性函数 $\theta^Tx$ 输出预测实际值的基础上，寻找一个假设函数函数 $h_\theta(x)=g(\theta^Tx)$ ，将实际值映射到到0，1之间，如果 $h_\theta(x)\geq0.5$ ，则预测 $y=1$ ，及 $y$ 属于正例；如果 $h_\theta(x)\leq0.5$ ，则预测 $y=0$ ，即 $y$ 属于负例。
如果说线性回归是对于特征的线性组合来拟合真实标记的话 $(y=\omega x+b)$ ，那么逻辑回归是对于特征的线性组合来拟合真实标记为正例的概率的对数几率 $(ln\frac{y}{1-y}=\omega x+b)$
对于输入 $x$ 分类结果为类别1和类别0的概率分别为： $P(y=1|x;\theta)=h_\theta(x)$ $P(y=0|x;\theta)=1-h_\theta(x)$

6.损失函数
逻辑回归的输出预测使用对数几率函数（logistic function）作为激活函数，对数几率函数是Sigmoid函数（形状为S的函数）的重要代表。 $g(z)=\frac{1}{1+e^{-z}}$
因此损失函数可以写成
$J(\theta)=\frac{1}{2m}\sum_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})^2=\frac{1}{2m}\sum_{i=1}^{m}(\frac{1}{1+e^{-\theta^Tx^{(i)}-b}}-y^{(i)})^2$
不是凸函数，引入交叉熵。

所以最后目标变成取最小值时的为最佳参数。与线性回归类似，利用梯度下降法更新.

除了梯度下降法，还有其他的一些用来求代价函数最小时参数θ的方法，如牛顿法、共轭梯度法（Conjugate Gradietn）、局部优化法（BFGS）和有限内存局部优化法（LBFGS）等。

SVM和LR之间的比较

原文：[机器学习笔记] 支持向量机SVM 和逻辑回归LR的异同
 LR与SVM的异同

1.相同点
①都是线性分类器。本质上都是求一个最佳分类超平面。
②都是监督学习算法。
③都是判别模型。通过决策函数，判别输入特征之间的差别来进行分类。
常见的判别模型有：KNN、SVM、LR。
常见的生成模型有：朴素贝叶斯，隐马尔可夫模型。

2.不同点
①优化目标不同
LR的损失函数是交叉熵

SVM的目标函数：

②支持向量机只考虑局部的边界线附近的点，而逻辑回归考虑全局（远离的点对边界线的确定也起作用）。
③第三，在解决非线性问题时，支持向量机采用核函数的机制，而LR通常不采用核函数的方法。
④线性SVM依赖数据表达的距离测度，所以需要对数据先做normalization，LR不受其影响。
⑤SVM的损失函数就自带正则！！！（损失函数中的1/2||w||^2项），这就是为什么SVM是结构风险最小化算法的原因！！！而LR必须另外在损失函数上添加正则项！！！

逻辑回归和线性回归之间的比较

线性回归用来做预测,LR用来做分类。
线性回归是来拟合函数,LR是来预测函数。
线性回归用最小二乘法来计算参数,LR用最大似然估计来计算参数。
线性回归更容易受到异常值的影响,而LR对异常值有较好的稳定性。

生成模型和判别模型基本形式

生成式：朴素贝叶斯、HMM、Gaussians、马尔科夫随机场
判别式：LR，SVM，神经网络，CRF，Boosting

分类算法列一下有多少种？

单一的分类方法主要包括：LR逻辑回归，SVM支持向量机，DT决策树、NB朴素贝叶斯、NN人工神经网络、K-近邻
集成学习算法：基于Bagging和Boosting算法思想，RF随机森林, GBDT，Adaboost, XGboost。

XGBoost和GBDT的区别

机器学习算法总结(四)——GBDT与XGBOOST
1）将树模型的复杂度加入到正则项中，来避免过拟合，因此泛化性能会由于GBDT。

2）损失函数是用泰勒展开式展开的，同时用到了一阶导和二阶导，可以加快优化速度。

3）和GBDT只支持CART作为基分类器之外，还支持线性分类器，在使用线性分类器的时候可以使用L1，L2正则化。

4）引进了特征子采样，像RandomForest那样，这种方法既能降低过拟合，还能减少计算。

5）在寻找最佳分割点时，考虑到传统的贪心算法效率较低，实现了一种近似贪心算法，用来加速和减小内存消耗，除此之外还考虑了稀疏数据集和缺失值的处理，对于特征的值有缺失的样本，XGBoost依然能自动找到其要分裂的方向。

6）XGBoost支持并行处理，XGBoost的并行不是在模型上的并行，而是在特征上的并行，将特征列排序后以block的形式存储在内存中，在后面的迭代中重复使用这个结构。这个block也使得并行化成为了可能，其次在进行节点分裂时，计算每个特征的增益，最终选择增益最大的那个特征去做分割，那么各个特征的增益计算就可以开多线程进行。

算法岗面试——机器学习总结

SVM！

交叉熵损失函数

LR

线性回归（Linear Regression）

逻辑回归

SVM和LR之间的比较

逻辑回归和线性回归之间的比较

生成模型和判别模型基本形式

分类算法列一下有多少种？

XGBoost和GBDT的区别

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

面试

和大叔走大数据应用之路

个人收藏

机器学习与数据挖掘

机器学习