机器学习优化算法

越来越觉得做机器学习有关的时候思维才是最重要的,这和你使用什么算法其实没有什么关系,也不是一个调用一个牛逼的算法就能解决问题,方法还是得人想,问题也得人来发现,数据处理和特征工程有时候也很重要。想用一些博客记录一下学习的过程,也想练一下自己的“内功”。

1.定义目标函数

定义目标函数是非常重要的一步,有时候在深度学习中或者在某些时候也叫损失函数,通常是argmax或者argmin,使得损失最小或者负的损失最大。

那么什么是目标函数呢,像这种:

这里优化用的就是最大似然估计,最大似然估计又叫极大似然估计(MLE),它是通过数据去预测模型的参数theta,但是这个概率表达式是我们预先知道的,和模型有关,或者说我们得知道概率怎么求,有什么参数,才能得到最大似然的表达式,最后通过优化来得到这些参数。而估计方法对于我们求得目标函数非常重要。那么有哪些估计方法呢?主要有MLE(最大似然估计),MAP(最大后验估计)以及Bayesian(贝叶斯估计)。贝叶斯思想以及与最大似然估计、最大后验估计的区别

MLE

先说例子,上图中逻辑回归用的就是MLE,朴素贝叶斯也是用的MLE来得到目标函数:

这是一个用贝叶斯计算文本分类的例子,同样来自于李文哲老师,正常来说,我们首先用MLE求其目标函数P(D),如第一行所示,这一行只是一个正常的求解目标函数的过程,并没有用到朴素贝叶斯,如果不用朴素贝叶斯,有可能根据这个公式推出一些判别式模型如逻辑回归或者CRF,在后面的2,3行才用到了朴素贝叶斯定理,假设x中各变量独立。也就是说,朴素贝叶斯其实只是提供了一个求解P(X|Y)的一种计算方法,这点让我想到前面博客中写到的语言模型或者拼写纠错,有了目标函数我们只需要思考如何更好更准确的求出目标函数中的某一项,而目标函数是用迭代的方法优化,还是其他的方法优化,就是另外的工作了。

MAP

一种克服数据不充分下得到错误估计的方法,就是引入人对θ的经验认识。比如,实验者以前掷过图钉,在进行掷图钉实验之前,会对尖朝上的概率有一个大致的认识(如果他能肯定该概率是多少,那就不用实验了)事实上,不同的图钉和不同的环境下,该概率并不一定一样,所以是没法肯定的。因此,先验只是表明了θ的取值的大致猜测,它通常是关于θ的一个连续型的分布。

MAP最大化后验分布要求MLE与prior乘积最优, 取log likelihood。

Bayesian

实在写不动了,给两个链接,介绍MLE,MAP,Bayesian等参数估计的,说的很好。参数估计的三种方法-MLE,MAP与BayesianEstimation,机器学习中的MLE、MAP和贝叶斯估计/贪心学院/李文哲,尤其第二篇。

在实际项目中有时候不一定有存在的如逻辑回归线性回归就能直接解决的,这个时候需要我们对目标函数进行修改,这样很多开源的框架或者工具没法使用,需要我们自己使用合适的公式和优化算法,结合具体问题进行改进。

MLE&&MAP

MLE和MAP的关系网上也有很多,无非就是一个最大似然估计,一个是最大后验估计,形式上看就是多乘了一个P(θ),实际上我们在用MLE求argmaxP(D|θ)的时候,我们模型其实已经定义了,逻辑回归也好,还是其他模型也好,这是我们人为设计好的模型,因此这个概率是建立在模型上的,使用的是模型参数求出的概率,然后最大化这个概率,通过优化算法如梯度下降求出参数。那MAP呢,同样也是模型建立好的,它通过贝叶斯公式转化成P(D|θ)P(θ)/P(D),因为求argmax和一个固定的分母没有关系,就写成P(D|θ)P(θ),这个P(θ)就是后验概率,但是这个概率和我们定义好的模型并没有关系,而是和模型的参数有关,如果说θ服从高斯分布,那么只是我们的模型参数服从高斯分布,用其概率密度函数带入即可计算了。

我们对逻辑回归使用MLE和MAP估计,假设后验概率P(θ)服从正态分布,发现MAP的作用就相当于加了一个L2的正则项。假设P(θ)服从拉普拉斯分布,MAP就相当于在MLE后面加了一个L1正则。这只是在逻辑回归,实际上任意一个模型都满足高斯->L2-norm,拉普拉斯->L1-norm。你细品。

当然,样本足够大的时候MLE和MAP应该是趋近于相同的。因为前面一项加了log其实是个相加的过程,样本足够大就没有后面的P(θ)什么事了。

2.常用的优化算法

优化算法

常用的优化算法有很多,机器学习或深度学习领域经常用到的类似于梯度下降,但实际最优化是一门非常深的学科,并且优化也不仅仅就是梯度下降。

任何的AI模型都要考虑定义目标函数和优化函数这两个步骤。首先考虑好一个模型,这是我们需要的一个总体框架,有了模型以后将模型实例化,这时候就要考虑它的目标函数,最后在考虑如何对它进行优化,当然有很多现成的工具,但是还是要有深入理解才能使用好这些工具。具体来说,模型是认为定义的,以深度学习模型举例,训练模型需要有一个目标函数,使得模型或者说模型参数最佳。而如何训练或者说优化(Optimize)这个模型呢,等价于求解目标函数的最优解。那为什么有的模型用SGD,有的用Adam,有的用Adagrad等等呢,这就是优化理论中的东西了,我不了解这个,也没学过这门课,但是还是有必要补一下,毕竟深度学习接触多了,见到的很多都是SGD,甚至淡化了优化的这个概念,因为都是直接调用框架没什么印象这一块究竟是什么。一般我们在真正结合实际场景,设计出模型以及相应的目标函数,我们首先得给目标函数简单的分个类,例如QP问题、SDP问题,Integer问题,Integer QP问题等,然后根据不同的问题求出相应的合适的一些优化算法。例如加了L1正则之后很多优化算法就不能用了。

优化不仅非常重要,而且在实际情况中无处不在。假设一个量化投资的例子,从已有预算所有股票中选择最佳的投资组合,并分配不同的权重。再考虑到针对不同的人有不同的风险偏好,在后面的正则项项加上λ系数,再比如,我们不可能选择所有股票,我们可以再加一个L1的正则,再比如,有些股票是必须要买的,比如预算的10%用来买茅台,等等,可以加上这样的限制。

我还写了个过程。因为这和我现在做的一个抖音的项目有很大相似之处。那如何优化呢?根据之前说的,我们看他是哪个问题,一看就是QP问题,但是加了L1正则,看看哪些优化算法可以解决这样的有限制的QP问题。

目标函数类型上分有平滑和非平滑,凸函数和非凸函数,连续和离散,有限制和无限制这几类。一般机器学习中见到的都是平滑的连续的函数,离散的较难并且不能用传统的优化算法优化,经常会是NPhard问题,所以我们主要研究一下凸和非凸性质。

如何判断凸函数我觉得是一个比较重要的一个点,至少自己构建模型费劲巴拉写了目标函数之后,能够判断是不是凸函数,不是的话怎么优化。

当然还有很多判定定理如第一准则第二准则,然后就是多看看博客了。我来学习几个:

再来一个用到优化算法的老题目–最大流,本来这个题的解法很多,我们这里用优化的思路来看:

因为线性问题,条件都是线性的,并且是凸函数,一定可以求得全局的最优解。文哲老师说,这时候就可以直接搜索linear programming solver,再加上一些sklearn,scipy等关键字,找到对应的包,就可以直接使用了。还是很方便的。可能有些不好入手,就拿这题举例,就把这些条件转化成矩阵相乘即可。

对了,linear programming,quadratic programming等属于凸优化的内容,给个链接:知乎

文哲老师又介绍了一个set cover problem,如图,并给出了目标函数:

定义域是0,1根据定义可以判断是一个非凸函数,所以可能比较难以解决,再由他的限定条件可以看出是以一个linear programming的问题,但是定义域是离散的,所以是一个Integer类型。对于这种离散的变量无法使用梯度的,精准的解在有限时间内很可能无法获得。我们可以退而求其次通过近似算法求解,也叫做把问题松弛化(relaxation),如图我们将0和1的离散值转化为连续值,非常像逻辑回归中分类结果的思想。

优化算法的复杂度

深度学习中一般我们只考虑模型本身而很少去考虑优化算法,因为优化算法用的都是梯度下降,只需要改变其学习率就可以了,但是即使是梯度下降我们有时候也需要简单的了解一下其复杂度,以利于训练我们的模型,并且优化的复杂度和模型的复杂度通常是正相关的。而梯度下降算法最重要的复杂度衡量指标是什么呢,当然是迭代次数。

公式上看,只要不等式右边的第二项随着迭代次数下降的越快,其实就说明梯度下降算法越好,反之亦然。

凸函数之前说过了,用一些方法或者根据已知的凸函数种类去判断,并且凸+凸还是凸,那么另外一个L-Lipschitz如何判断及证明呢,也是用定理,下面放一下笔记(怕写在本子上没了,还是存这儿吧):

再接着证明那个梯度下降法的收敛性公式:

3.模型复杂度

模型复杂度是机器学习中非常重要的一块内容。来看这样一张图:

从左到右复杂度逐渐增加,泛化性能逐渐减弱,最复杂的那个模型出现了过拟合。它很可能把训练数据中的一些噪音当成了正确的数据并将其区分开。这也是一种很不稳定的现象,在项目中的置信度比较低。那么哪些因素会影响到模型的复杂度呢?

  • 模型本身的选择

模型一旦确定了,它本身就会有复杂度的区别,像LR本身就比较简单,而神经网络、深度学习本身就会比较复杂,要说明一点的是,复杂的模型一般用在复杂的环境中,反之同理。怎么去评判简单或者复杂的环境呢?简单的说就是数据量的多少以及需要考虑的因素,比如说垃圾邮件分类考虑的很少,数据量也不需要太大,但是无人驾驶这样的,需要考虑的因素很多,因此需要复杂的模型。

  • 模型参数的设置

最经典的例子就是神经网络。一旦选择了神经网络,需要去设计神经网络的结构的。并且神经网络的维度、网络的深度等等都会影响到训练的效果。

  • 模型的参数空间的选择

一旦定义了一个具体的模型,那么模型的会有一个参数空间。我们的目标其实就是从模型参数空间中选择最好的参数。我们可以通过限制参数空间来选择不同复杂度的模型,或者说选择让模型比较简单的几个参数,例如正则,可以动态的筛选比较简单的参数空间,然后在这些空间里在选择比较合适的解。其实正则的本事就是过滤了我们的参数空间,他也可以用来控制模型的复杂度。

  • 模型拟合过少的样本

这个较好理解,样本越少越容易过拟合。

通过以上几点,可以知道,解决过拟合就可以从这几方面来处理,例如选择简单的模型、降低模型的参数、增大正则项的λ,选择更多的样本。

4.正则

这个是个小知识点。 正则项有很多种形式,例如L0-Norm,L1-Norm,L2-Norm。最常用的就是L1和L2了。其他还有很多很多,但是见的较少。L1求绝对值,他最大的特性就是稀疏,他会使参数中很多项为0,所以某些稀疏性问题中可以使用L1-Norm。L2则不同,下面具体介绍这两者:

L1 vs. L2

L1和L2还是有一定区别的,虽然二者都是为了降低参数的值,但是在具体使用的时候,使用L1-Norm会得到一个稀疏解,使得很多项都为0。但是L2尽管也是使得参数变得更小较为平滑,但是他不会出现很多个为0的参数。这样说来,对于某些我们不需要许多参数,或者我们只需要几个对我们的目标求解问题最重要的几个参数这样的情况时,我们呢可以使用L1,因为它可以把不那么重要的因素的参数变成0。为啥L1会产生sparse solution这样的问题呢?可以从几何的角度来考虑,我们让参数θ为二维好在图上进行展示:

f(θ)和θ的L1-Norm的数值等高线的交集为其最小值的取值范围,从图可以很容易看出L1会有稀疏项的原因。

文哲老师举了个很有意思的例子,大脑中神经元分为若干个区域,通过神经元的触发来判断目前的大脑在思考哪一类问题,这是个很经典的分类问题,用逻辑回归,但是在思考某一类问题的时候,可能只有很少量的神经元区域工作,这个时候用L1-Norm就很好,并且解释性更好。

虽然尽管我认为L2应该也没啥问题,况且这个你还得了解了这个的前提,要是不了解很多神经元区域不参与这样的前提认识反而会有反作用。L1还有个缺点,拿逻辑回归来说,如果特征重复了,或者相关度很高,他并不会选择最好的而是随机选择。但是线性回归可能会有用,自己体会。总之如果你知道本来结果应该稀疏的,不需要考虑很多因素或者说很多因素自己是随便找的,OK,L1可以,否则我觉得还是L2更好。

还有一点,使用了正则以后在训练集上的效果一般情况下会比不加正则的效果略差,也很好理解,因为加了限制条件。

正则的高级应用

还是用上图的例子,说的再具体一点,神经科学中,大脑内分区域工作,每个区域负责一块功能,区域内有很多神经元,这就可以看作是一个参数。如图所示:

w就是参数,不同区域有一个参数集,现在要用正则实现两个功能,第一个是某一个区域内只有少部分被激活,体现在参数上就是只有少部分不为0,我们可以用一个L1正则来实现,第二是在空间上相邻的神经元作用相似,这一点可以用图中右下角的L2正则来实现。

再讲一个例子,经常用在推荐系统领域的,叫做矩阵分解。推荐系统的user-item评分矩阵通常是一个稀疏的矩阵,Rij指的就是用户i对产品j的打分。通过分解可以到user和item的特征向量U和V。这两个矩阵是学习到的,目标函数是什么呢,就是Ui和Vj的内积与真实评分Rij的差距,当然(i,j)是R中有值的项。再加上正则项,正则项是对items和users的L1或者L2 norm。这就是传统的推荐系统的矩阵分解方法。如图,但是我们想要构建一个动态的推荐系统怎么办呢,毕竟用户的喜爱是随着时间变化而变化的。

于是我们考虑一个时间的维度,目标函数里前两项和之前一样只是多了一个时间的维度,考虑到用户的偏好改变不会很大, 我们在时间维度上对相邻两个时间的用户向量和商品向量做差取L1或L2正则。

再结合上面可以缩小参数空间的功能,其实会用正则还是大有可为的,不是简简单单的一个绝对值和一个平方。主要看如何使用。

5.参数搜索

像正则前面的λ,是一个超参数,通常超参数可以使用分组交叉验证的方式得到,但是一般不会仅仅只有一个超参数,多个超参数如何搜索到最好的取值呢?一般用的最多的,也是最简单的就是Grid search,在sklearn包中也有,最大的优点就是可并行化。

除此之外,还有其他的一些方法,例如随机搜索、遗传算法或者贝叶斯优化。其核心都是不断缩小空间,降低无用的搜索。这些方法可以叫做Heuristic search,一般会用grid search就可以了,只是说,用一些这样高级的搜索方参数的方法会更容易找到一些更好的参数区域,然后将注意力集中在这一块,而不是把计算资源用到一看就不可能的地方。

我们现在所研究的深度学习模型通常会包含大量的超参数。尤其是对于深层的网络,而训练这样一个网络是很费时的,这也是目前的研究热点之一如autoML等。


  转载请注明: April 机器学习优化算法

 上一篇
机器学习 机器学习
发现之前课上学的机器学习太粗糙了,自己学的也不咋样,想好好整理一下。 1.逻辑回归(Logistic regression)Logistic Regression最常见的应用场景就是预测概率。比如知道一个人的 年龄、性别、血压、胆固醇水平、
2020-03-16
下一篇 
Scrapy入门&&如何写一个好爬虫 Scrapy入门&&如何写一个好爬虫
我之前一直不想学习Scrapy,觉得不就是一个框架嘛,爬虫难的是分析,是逆向,牛逼的人只靠着requests,用正则和xpath就可以获取需要的数据了。但是随着代码量多了以及爬取的字段多了以后,还是觉得有必要学习一下框架,以及一个爬虫项目需
2020-03-02
  目录