从凸函数到梯度下降和牛顿法

记得我在和优男一起研究logistic regression的时候，他问了我几个非常尖锐的问题，让我顿时哑口无言

• 怎么保证logistic regression通过gradient descent找到的是最优解；
• 为什么logistic regression可以用newton’s method呢？
• Newton’s method中Hessian matrix必须positive definite有什么意义呢，log cost function能保证吗？

这些细节问题，说实话我也没有认真的想过。在夸奖他之余，我们也一起开始了研究，希望从中学习到一些更深层的东西，趁着现在有个blog分享给大家

凸函数(Convex function)

在开始之前，我有一个关于术语的倡议。中文里的“凸函数”，看上去是凹下去的，对应的，中文里的“凹函数”看上去凸起来的，amazing吧？这是有一定历史原因的，感兴趣的朋友可以去查阅下资料，这里我们不再复述。所以为了避免让大家产生误解，我鼓励大家使用英文，convex function和concave function.这样会避免很多不必要的麻烦。

OK，我们来一起看看，convex function

对于一维函数 $f(x)$来说，在定义域内的任意值 $a$和$b$，对于任意的 $0 \leq \theta \leq 1$，如果满足以下条件，则称为convex function
$$f(\theta a+(1-\theta) b) \leq \theta f(a) + (1- \theta)f(b)$$
我们再用图片直观的感受一下

显而易见的是，当公式中等号去掉的时候，函数就是strictly convex function.

Convex function具有一定的性质，我们简单的描述一下。

First order condition

对于 function $f$，在定义域内一阶可导，且导数为
$$\nabla f=( \frac{\partial f(x)}{x_1}, \frac{\partial f(x)}{x_2},…, \frac{\partial f(x)}{x_n})$$
那么 $f$是convex function的充要条件是：对于定义域内任意 $x$ 和 $y$
$$f(y) \geq f(x) + \nabla f(x)^T (y - x)$$
OK，再来张图片直观感受一下：

其实简单的来讲，就是对于convex function $f$，它的函数值永远大于等于切线上的值！

Second order condition

对于 function $f$，在定义域内二阶可导，且 $n$ 维方阵Hessian matrix的元素为
$$\nabla ^2 f(x) = \frac{ \partial ^2 f(x)}{ \partial x_i \partial x_j}, \quad i,j = 1,2,…,n$$
当且仅当Hessian matrix positive semi-defnite的时候，$f$ 是convex function。以上互为充要条件。这里的证明我不想展开讲，在后面我会给出reference链接。

下面给出一些 $\Bbb R$ 空间下常见的convex function：

• 线性函数：$f(x) = ax+b$
• 指数函数：$f(x)=e^ {ax}$
• 负熵函数： $f(x)=xlogx \quad on \quad \Bbb R_{++}$

对应的，一些常见的concave function：

• 线性函数：$f(x) = ax+b$
• 对数函数： $f(x)=logx \quad on \quad \Bbb R_{++}$

其中大家可以看到，线性函数既是convex也是concave函数，比较特殊，这和它本身的first order condition为常数有关。

以上就是convex function的一个简单介绍，你也许会问，为什么花这么多力气来介绍convex function. 其实，在machine learning中，convex function的优化是非常重要的，很多算法说到底，都是要optimize一个convex function，我们会用liner regression和logistic regression为例子，进一步从convex function的简介过渡到gradient descent和newton’s method.

梯度下降法(Gradient descent)

关于gradient descent，我们使用liner regression作为例子来讨论。Liner regression算法的实质是least square method，他的cost function是
$$J( \theta)= \frac{1}{2} \sum_{i=1} ^m (h_ \theta (x ^{(i)})-y^{(i)})^2, \quad h_ \theta (x)= \theta ^Tx$$
对于liner regression来说，算法的实质就是去求出$J( \theta)$ 以$\theta$为参数的minimum，gradient descent算法的作用就是去实现了这个过程，gradient descent的基础知识详见reference.

那么针对cost function，gradient descent是如何保证收敛的呢，我们一起来看看

对于$J( \theta)$，我们将其带入convex function的定义公式中，注意这里我们的自变量是$\theta$，我们可以通过推导证明该式成立，也就是说，least square cost function是convex function.

既然有这个结论了，那么我们可以想象一下，least square cost function作为convex function，是存在全局最小值的，也就是说，gradient descent不会出现陷入局部最优无法自拔的现象，只要gradient descent保证参数足够好的情况下，理论上，是完全可以很好的逼近全局最优的解的。

Gradien descent算法本身并不能保证获得全局最小值，只有在objective function是convex function的时候才可以保证

下图可以看出，右边的object function是non-convex function，因而很容易陷入到局部最小值无法自拔，而左边的objective function是一个标准的convex function，在gradient descent参数合理的前提下，可以逼近全局最优。

当然，gradien descent的一些改进方法，例如stochastic gradient descent在解决non-convex optimization上有一些帮助，但是我们在这里不做讨论，后面有时间我会专门再写。

由此，我们可以得出，gradient descent不仅仅是minimize liner regression的一个很好的方法，也是convex optimization的一种理想方法

牛顿法(Newton’s method)

Newton’s method 这块内容，我们将会用logistic regression作为例子。同样，我们先来关注下log cost function，这里，我们取label为-1和+1，因为这样得到的cost function比0,1下的计算更加简单
$$J( \omega)= - \frac{1}{m} \sum_{i=1} ^{m} log(1+e^{-y^{(i)} \omega^T x^{(i)}})$$
这里我们采用了-1和+1作为标签值，和大多数教材中不一样，大家可以下来自己推导一下$J( \omega)$，这种写法广泛的应用在了比较logistic regression和SVM两大分类器的文献中，希望大家熟知。

此处我们对原始的likehood function加上了 $- \frac{1}{m}$的系数，同样，当我们把 $J( \omega)$带入到convex function的定义中，可以验证上式为convex function，值得注意的是，$J( \omega)$是$\omega$的函数。

其实，我们也可以将log cost function展开后，利用最基本的函数convex和concave性质来获得上式是convex function的结论，碍于公式实在太难打，就留给大家去证明吧。

OK，既然log cost function是convex function，我们一定是可以用gradient descent去求解的。问题是，如果我们用newton’s method呢？

Newton’s method的基本原理详见reference，这里我们可以发现，既然log cost function是convex function，那么根据second order condition可以知道，它的Hessian matrix一定是positive semi-definite的。如果我们加上了L2 regularizer，由于L2 regularizer本身就是一个strict convex function，那么log cost function就一定是strict convex function了，也就是：
$$J( \omega)= - \frac{1}{m} \sum_{i=1} ^{m} log(1+e^{-y^{(i)} \omega^T x^{(i)}})+ \frac{1}{2}|| \omega||^2$$
因此，在log cost function中，Hessian matrix是positive definite的，完全满足newton’s method 的要求。同样，类似于上一部分，newton’s method也可以找到log cost function的全局最优。

Sum up

OK，我们说到这里也确实讲了不少，这篇blog有些冗长，希望朋友们不要焦虑。总体来说，我想表达的是以下几个观点：

• Machine learning中我们寻求的其实就是objective function一个全局最优值，这些问题是通过gradient descent等方法解决的；
• Gradient descent和newton’s method都是convex optimization的好方法，他们都可以对于convex function获得全局最优；
• 对于non-convex optimization问题，stochastic gradient descent也很有效果，我们后续再慢慢学习。

好了，核心思想就这三点，今天先说这么多！

Reference

• EE364, Convex Optimization Stanford University
• Regularized Logistic Regression is Strictly Convex
• XinyiLI大神的blog
• Liner regression
• Logsitc regression
• Gradient descent
• Newton’s method