AI疯狂进阶——凸优化


本文作者专注于AI进阶算法,正在推出AI疯狂进阶之基础理论进阶篇,如有兴趣可持续关注我。

核心导读:

1.什么是凸优化?

2.如何证明函数是凸函数?

3.神经网络是凸函数吗?


凸优化算法是机器学习里面比较重要的一个概念,理解凸优化需要掌握多个高等数学的概念,本文在讲解过程中逐步解析这些数学概念,深入浅出的解析整个凸优化相关的问题。

1.什么是凸优化?

神经网络通过线性和非线性单元的组合来拟合输入到输出的映射,其中有大量的参数需要求解,这是一个高维数据优化问题。高维数据优化求解是一个比较难的问题,比如说优化函数有多个局部极值,需要把所有局部极值找出来再对比得到全局极值(如下图左图),这个消耗是非常大的,另外可能还存在鞍点(导数为0的地方不是极值点)问题(如下图右图)。

AI疯狂进阶——凸优化

那么,有什么办法或者在什么样的情况下能简化这个问题容易求解呢?于是就有了凸优化概念。凸优化包括以下部分,下面对其中的概念进行解释下:

(1)凸优化的定义域必须为凸集。凸集的定义如下:

AI疯狂进阶——凸优化

按照上述定义,可以得出:实数空间R是凸集。

(2)凸优化的损失函数/约束函数都必须是凸函数。凸函数的定义为:在函数的定义域内,如果对于任意的x和y,都满足如下条件:

AI疯狂进阶——凸优化

则函数为凸函数,如下图的一元函数就是凸函数。在几何上可以看到,凸函数在任何点的切线都位于函数的下方。


AI疯狂进阶——凸优化

对于一元函数,凸函数的判定规则为其二阶导数大于等于0(如果去掉上面的等号,则函数是严格凸的),即:

AI疯狂进阶——凸优化

对于多元函数,如果它是凸函数,则其Hessian矩阵为半正定矩阵。如果Hessian矩阵是正定的,则函数是严格凸函数。Hessian矩阵的定义和性质如下:

AI疯狂进阶——凸优化

不论是一元函数的二阶导数,还是多元函数的Hessian矩阵,都是可以来衡量函数的凹凸性质。如果有同学对Hessian矩阵有不理解的地方,可以关注后续进阶系列,会专门讲解Hessian矩阵的应用。

上面讲述凸优化必须包含凸集和凸函数,这也导致凸优化问题有一个重要的特性:所有局部最优解都是全局最优解。这个特性可以保证我们在求解时不会陷入局部最优解,即如果找到了问题的一个局部最优解,则它一定也是全局最优解,这极大的简化了问题的求解,这也回答了上面提到的问题。


2.哪些函数是凸函数?如何证明?

我们在上面讲述了凸优化问题能相对容易的找到全局最优解,那么哪些函数是凸优化函数呢?这里介绍几个,例如线性回归函数,支持向量机,softamx回归等都是凸优化函数。下面以最简单的线性回归函数来证明下为啥是凸函数。

AI疯狂进阶——凸优化

损失函数去掉b的影响,MSE LOSS展开可以简化为:

AI疯狂进阶——凸优化

因此它的Hessian矩阵为:

AI疯狂进阶——凸优化

写成矩阵形式为:

AI疯狂进阶——凸优化

其中X是所有样本的特征向量按照列构成的矩阵。对于任意不为0的向量x,有:


AI疯狂进阶——凸优化

因此Hessian矩阵是半正定矩阵,上面的优化问题是一个不带约束条件的凸优化问题。


3.神经网络是凸函数吗?

先引用大神针对这个问题的回答:

AI疯狂进阶——凸优化

对于单节点感知器的神经网络,其优化问题是凸问题,在上述章节已经简单的证明了部分Loss函数是凸函数了;对于深层神经网络,由于多层线性和非线性单元的复合,大部分神经网络的损失函数变成非凸的。最直接的方法是在其2阶导数上证明其是非正定矩阵,找一些反例即可。因为是非凸的,神经网络损失函数可能存在多个局部最小值,因此,对其的优化是比较困难的,好在实践应用中,通过梯度下降法找到的局部最小值,大部分情况下已经可以满足我们的应用需求,并且有时候为了得到更好的结果,用随机初始化训练多次得到多个局部最小值进行比较得到更优的结果。


4.小结

在实际应用中,很多问题都是非凸的,虽然理论上很残酷,但实际上我们目前的一些优化算法却工作的还是挺好的,这也是神经网络目前如此盛行风靡的一大原因。目前一些理论研究也在持续研究这一块,后续的系列文章中将会持续解析这些成果,如果有兴趣,可以持续关注我。