机器学习算法面试-1.3 优化理论

Doris232 · 发表于 2022-7-26 15:56

更多资料请关注&#34;机器学习算法面试&#34;，回复“资料”即可获取

<hr/>1.3 优化理论

1.3.1 什么是凸优化？

凸优化问题（OPT，convex optimization problem）指定义在凸集中的凸函数最优化的问题。尽管凸优化的条件比较苛刻，但仍然在机器学习领域有十分广泛的应用。
1.3.2 凸优化的优势是什么？

凸优化问题的局部最优解就是全局最优解
很多非凸问题都可以被等价转化为凸优化问题或者被近似为凸优化问题（例如拉格朗日对偶问题）
凸优化问题的研究较为成熟，当一个具体被归为一个凸优化问题，基本可以确定该问题是可被求解的

1.3.3 如何判断函数是否为凸的?

熟悉凸函数的定义，即在凸的定义域上取两个点 $x,y$ ，其凸组合的值应该小于等于其值的凸组合，对任意 $\lambda \in [0,1]$ ,有的话 $f(\lambda x + (1 - \lambda )y) \le \lambda f(x) + (1 - \lambda )f(y)$ ,那么它就是凸函数。
1.3.4 什么是鞍点？

鞍点（Saddle point）在微分方程中，沿着某一方向是稳定的，另一条方向是不稳定的奇点，叫做鞍点。在泛函中，既不是极大值点也不是极小值点的临界点，叫做鞍点。在矩阵中，一个数在所在行中是最大值，在所在列中是最小值，则被称为鞍点。在物理上要广泛一些，指在一个方向是极大值，另一个方向是极小值的点。从海塞矩阵的角度来说，Hessian矩阵不定的点称为鞍点，它不是函数的极值点。

1.3.5 解释什么是局部极小值，什么是全局极小值？

局部极值点：假设是一个可行解，如果对可行域内所有点 $X$ 都有，则称为全局极小值。全局极值点。对于可行解，如果存在其邻域 $\delta$ ，使得该邻域内的所有点即所有满足 $||x - x*|| \le \delta$ 的点 $x$ ，都有，则称为局部极小值。
1.3.6 既然有全局最优，为什么还需要有局部最优呢？

对于优化问题，尤其是最优化问题，总是希望能找到全局最优的解决策略，但是当问题的复杂度过于，要考虑的因素和处理的信息量过多的时候，我们往往会倾向于接受局部最优解，因为局部最优解的质量不定最差的。尤其是当我们有确定的评判标准标明得出的解释可以接受的话，通常会接受局部最优的结果。这样，从成本、效率等多考虑，才是实际程中会才去的策略。
1.3.7 机器学习有哪些优化方法？

机器学习和深度学习中常用的算法包含不局限如下：梯度下降、牛顿法和拟牛顿、动量法momentum、Adagrad、RMSProp、Adadelta、Adam等，无梯度优化算法也有很多，像粒子群优化算法、蚁群算法、遗传算法、模拟退火等群体智能优化算法。几个常见的优化方法的比较如下：

1.3.8 梯度下降法和牛顿法能保证找到函数的极小值点吗，为什么？

不能，可能收敛到鞍点，不是极值点。
1.3.9 解释一元函数极值判别法则是什么？

假设为函数的驻点，可分为以下三种情况。情况一：在该点处的二阶导数大于0，则为函数的极小值点；情况二：在该点处的二阶导数小于0，则为极大值点；情况三：在该点处的二阶导数等于0，则情况不定，可能是极值点，也可能不是极值点。
1.3.10 解释多元函数极值判别法则是什么？

假设多元函数在点M的梯度为0，即M是函数的驻点。其Hessian矩阵有如下几种情况。
情况一：Hessian矩阵正定，函数在该点有极小值。情况二：Hessian矩阵负定，函数在该点有极大值。情况三：Hessian矩阵不定，则不是极值点，称为鞍点。 Hessian矩阵正定类似于一元函数的二阶导数大于0，负定则类似于一元函数的二阶导数小于0。
1.3.11 什么是对偶问题？

可以将对偶问题看成是关于原问题松弛问题的优化问题，对偶问题的目标，是以一定方式，找到最贴近原问题的松弛问题。如果将原问题以对偶变量为参数进行松弛，将得到一系列以对偶变量为参数的松弛问题（例如拉格朗日松弛问题，是以拉格朗日乘子为参数，将原问题约束松弛到目标函数后得到的松弛问题）对偶问题则是通过优化对偶变量，找到最逼近原问题的松弛问题（例如拉格朗日对偶问题，是优化拉格朗日乘子，得到最接近原问题的松弛问题，即原问题的下界）
1.3.12 随机梯度下降法、批量梯度下降法有哪些区别？

批量梯度下降：
(1) 采用所有数据来梯度下降。
(2) 批量梯度下降法在样本量很大的时候，训练速度慢。
随机梯度下降
(1) 随机梯度下降用一个样本来梯度下降。
(2) 训练速度很快。
(3) 随机梯度下降法仅仅用一个样本决定梯度方向，导致解有可能不是全局最优。
(4) 收敛速度来说，随机梯度下降法一次迭代一个样本，导致迭代方向变化很大，不能很快的收敛到局部最优解。
1.3.13 各种梯度下降法性能对比？

img

1.3.14 说一下梯度下降法缺点?

靠近极小值时收敛速度减慢
在极小值点附近的话，梯度比较小了，毕竟那个点的梯度都快为零了，收敛的就慢了
直线搜索时可能会产生一些问题
步子大或者小会导致来回的震荡，导致不太好收敛
可能会“之字形”地下降
如下所示，梯度下降会来回走之字，导致优化速度慢

1.3.15 如何对梯度下降法进行调优?

算法迭代步长选择
在算法参数初始化时，有时根据经验将步长初始化为1。实际取值取决于数据样本。可以从大到小，多取一些值，分别运行算法看迭代效果，如果损失函数在变小，则取值有效。如果取值无效，说明要增大步长。但步长太大，有时会导致迭代速度过快，错过最优解。步长太小，迭代速度慢，算法运行时间长。 2. 参数的初始值选择
初始值不同，获得的最小值也有可能不同，梯度下降有可能得到的是局部最小值。如果损失函数是凸函数，则一定是最优解。由于有局部最优解的风险，需要多次用不同初始值运行算法，关键损失函数的最小值，选择损失函数最小化的初值。 3. 标准化处理
由于样本不同，特征取值范围也不同，导致迭代速度慢。为了减少特征取值的影响，可对特征数据标准化，使新期望为0，新方差为1，可节省算法运行时间。

1.3.16 随机梯度下降法、批量梯度下降法有哪些区别？

批量梯度下降：
(1) 采用所有数据来梯度下降。
(2) 批量梯度下降法在样本量很大的时候，训练速度慢。
随机梯度下降
(1) 随机梯度下降用一个样本来梯度下降。
(2) 训练速度很快。
(3) 随机梯度下降法仅仅用一个样本决定梯度方向，导致解有可能不是全局最优。
(4) 收敛速度来说，随机梯度下降法一次迭代一个样本，导致迭代方向变化很大，不能很快的收敛到局部最优解。
1.3.17 梯度下降法缺点

梯度下降法是最早最简单，也是最为常用的最优化方法。梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法“。最速下降法越接近目标值，步长越小，前进越慢。梯度下降法缺点有以下几点：
（1）靠近极小值时收敛速度减慢。
在极小值点附近的话，梯度比较小了，毕竟那个点的梯度都快为零了，收敛的就慢了
（2）直线搜索时可能会产生一些问题。
步子大或者小会导致来回的震荡，导致不太好收敛
（3）可能会“之字形”地下降。
如下所示，梯度下降会来回走之字，导致优化速度慢 https://blog.csdn.net/qq_40722827/article/details/107297535、
1.3.18 批量梯度下降和随机梯度下降法的缺点？

批量梯度下降
a）采用所有数据来梯度下降。
b）批量梯度下降法在样本量很大的时候，训练速度慢。
随机梯度下降
a）随机梯度下降用一个样本来梯度下降。
b）训练速度很快。
c）随机梯度下降法仅仅用一个样本决定梯度方向，导致解有可能不是全局最优。
d）收敛速度来说，随机梯度下降法一次迭代一个样本，导致迭代方向变化很大，不能很快的收敛到局部最优解。
1.3.19 如何对梯度下降法进行调优?

实际使用梯度下降法时，各项参数指标不能一步就达到理想状态，对梯度下降法调优主要体现在以下几个方面：（1）算法迭代步长 $\alpha$ 选择。在算法参数初始化时，有时根据经验将步长初始化为1。实际取值取决于数据样本。可以从大到小，多取一些值，分别运行算法看迭代效果，如果损失函数在变小，则取值有效。如果取值无效，说明要增大步长。但步长太大，有时会导致迭代速度过快，错过最优解。步长太小，迭代速度慢，算法运行时间长。（2）参数的初始值选择。初始值不同，获得的最小值也有可能不同，梯度下降有可能得到的是局部最小值。如果损失函数是凸函数，则一定是最优解。由于有局部最优解的风险，需要多次用不同初始值运行算法，关键损失函数的最小值，选择损失函数最小化的初值。（3）标准化处理。由于样本不同，特征取值范围也不同，导致迭代速度慢。为了减少特征取值的影响，可对特征数据标准化，使新期望为0，新方差为1，可节省算法运行时间。
1.3.20 各种梯度下降法性能比较

对比维度-BGD-SGD-Mini-batch GD-Online GD
训练集-固定-固定-固定-实时更新
单次迭代样本数-整个训练集-单个样本-训练集的子集-根据具体算法定
算法复杂度-高-低-一般-低
时效性-低-一般-一般-高
收敛性-稳定-不稳定-较稳定-不稳定
1.3.21 为什么归一化能加快梯度下降法求优化速度？

归一化后的数据有助于在求解是缓解求解过程中的参数寻优的动荡，以加快收敛。对于不归一化的收敛，可以发现其参数更新、收敛如左图，归一化后的收敛如右图。可以看到在左边是呈现出之字形的寻优路线，在右边则是呈现较快的梯度下降。

1.3.22 标准化和归一化有什么区别？

归一化是将样本的特征值转换到同一量纲下把数据映射到[0,1]或者[-1, 1]区间内，仅由变量的极值决定，因区间放缩法是归一化的一种。 $x' = \frac{{x - \min (x)}}{{\max (x) - \min (x)}}$
标准化是依照特征矩阵的列处理数据，其通过求z-score的方法，转换为标准正态分布，和整体样本分布相关，每个样本点都能对标准化产生影响。它们的相同点在于都能取消由于量纲不同引起的误差；都是一种线性变换，都是对向量X按照比例压缩再进行平移。 $x' = \frac{{x - \bar x}}{\sigma }$
1.3.23 批量梯度下降和随机梯度下降法的缺点

批量梯度下降
a）采用所有数据来梯度下降。
b）批量梯度下降法在样本量很大的时候，训练速度慢。
随机梯度下降
a）随机梯度下降用一个样本来梯度下降。
b）训练速度很快。
c）随机梯度下降法仅仅用一个样本决定梯度方向，导致解有可能不是全局最优。
d）收敛速度来说，随机梯度下降法一次迭代一个样本，导致迭代方向变化很大，不能很快的收敛到局部最优解。
1.3.24 极大似然估计和最小二乘法区别？

对于最小二乘法，当从模型总体随机抽取n组样本观测值后，最合理的参数估计量应该使得模型能最好地拟合样本数据，也就是估计值和观测值之差的平方和最小。而对于最大似然法，当从模型总体随机抽取n组样本观测值后，最合理的参数估计量应该使得从模型中抽取该n组样本观测值的概率最大。在最大似然法中，通过选择参数，使已知数据在某种意义下最有可能出现，而某种意义通常指似然函数最大，而似然函数又往往指数据的概率分布函数。与最小二乘法不同的是，最大似然法需要已知这个概率分布函数，这在实践中是很困难的。一般假设其满足正态分布函数的特性，在这种情况下，最大似然估计和最小二乘估计相同。最小二乘法以估计值与观测值的差的平方和作为损失函数，极大似然法则是以最大化目标值的似然概率函数为目标函数，从概率统计的角度处理线性回归并在似然概率函数为高斯函数的假设下同最小二乘建立了的联系。

		自动登录	找回密码
密码			立即注册

机器学习算法面试-1.3 优化理论

本帖子中包含更多资源