[原创] 用人话解释机器学习中的Logistic Regression(逻辑回归)

转载请注明出处:http://www.codelast.com/
友情提示:如果觉得页面中的公式显示太小,可以放大页面查看(不会失真)。

Logistic Regression(或Logit Regression),即逻辑回归,简记为LR,是机器学习领域的一种极为常用的算法/方法/模型。
你能从网上搜到十万篇讲述Logistic Regression的文章,也不多我这一篇,但是,就像我写过的最优化系列文章一样,我仍然试图用“人话”来再解释一遍——可能不专业,但是容易看得懂。那些一上来就是几页数学公式什么的最讨厌了,不是吗?
所以这篇文章是写给完全没听说过Logistic Regression的人看的,我相信看完这篇文章,你差不多可以从无到有,把逻辑回归应用到实践中去。… Read More

[原创] 再谈 牛顿法/Newton's Method In Optimization

转载请注明出处:http://www.codelast.com/

牛顿法是最优化领域的经典算法,它在寻优的过程中,使用了目标函数的二阶导数信息,具体说来就是:用迭代点的梯度和二阶导数对目标函数进行二次逼近,把二次函数的极小点作为新的迭代点,不断重复此过程,直到找到最优点。… Read More

[原创] 再谈 梯度下降法/最速下降法/Gradient descent/Steepest Descent

转载请注明出处:http://www.codelast.com/

当今世界,深度学习应用已经渗透到了我们生活的方方面面,深度学习技术背后的核心问题是最优化(Optimization)。最优化是应用数学的一个分支,它是研究在给定约束之下如何寻求某些因素(的量),以使某一(或某些)指标达到最优的一些学科的总称。
梯度下降法(Gradient descent,又称最速下降法/Steepest descent),是无约束最优化领域中历史最悠久、最简单的算法,单独就这种算法来看,属于早就“过时”了的一种算法。但是,它的理念是其他某些算法的组成部分,或者说在其他某些算法中,也有梯度下降法的“影子”。例如,各种深度学习库都会使用SGD(Stochastic Gradient Descent,随机梯度下降)或变种作为其优化算法。
今天我们就再来回顾一下梯度下降法的基础知识。

『1』名字释义
在很多机器学习算法中,我们通常会通过多轮的迭代计算,最小化一个损失函数(loss function)的值,这个损失函数,对应到最优化里就是所谓的“目标函数”。
在寻找最优解的过程中,梯度下降法只使用目标函数的一阶导数信息——从“梯度”这个名字也可见一斑。并且它的本意是取目标函数值“最快下降”的方向作为搜索方向,这也是“最速下降”这个名字的来源。
于是自然而然地,我们就想知道一个问题的答案:沿什么方向,目标函数 f(x) 的值下降最快呢?

『2』函数值下降最快的方向是什么
先说结论:沿负梯度方向  d = - {g_k} ,函数值下降最快。此处,我们用  d  表示方向(direction),用  g  表示梯度(gradient)。
下面就来推导一下。
将目标函数 f(x) 在点 {x_k} 处泰勒展开(在最优化领域,这是一个常用的手段):
f(x) = f({x_k}) + \alpha g_k^T{d_k} + o(\alpha )
高阶无穷小 o(\alpha ) 可忽略,由于我们定义了步长 \alpha /> 0 (在ML领域,步长就是平常所说的learning rate),因此,当 g_k^T{d_k} < 0 时, f(x) < f({x_k}) ,即函数值是下降的。此时 {d_k} 就是一个下降方向。
但是 {d_k} 具体等于什么的时候,可使目标函数值下降最快呢?
文章来源:http://www.codelast.com/
数学上,有一个非常著名的不等式:Cauchy-Schwartz不等式(柯西-许瓦兹不等式)1,它是一个在很多场合都用得上的不等式:

({a_1}{b_1} + {a_2}{b_2} + \cdots + {a_n}{b_n}) \le \sqrt {(a_1^2 + a_2^2 + \cdots + a_n^2)} \sqrt {(b_1^2 + b_2^2 + \cdots + b_n^2)}
当且仅当:
\frac{{{a_1}}}{{{b_1}}} = \frac{{{a_2}}}{{{b_2}}} = \cdots = \frac{{{a_n}}}{{{b_n}}}
时等号成立。
 

由Cauchy-Schwartz不等式可知:
\left| {d_k^T{g_k}} \right| \le \left\| {{d_k}} \right\|\left\| {{g_k}} \right\|
当且仅当 {d_k} = {g_k} 时,等号成立, d_k^T{g_k} 最大(>0)。
所以 {d_k} = - {g_k} 时, d_k^T{g_k} 最小(<0), f(x) 下降量最大。
所以  - {g_k}下降方向。

『3』缺点
它真的如它的名字所描述的,是“最快速”的吗?从很多经典的最优化书籍你会了解到:并不是。
事实上,它只在局部范围内具有“最速”性质;对整体求最优解的过程而言,它让目标函数值下降非常缓慢。

『4』感受一下它是如何“慢”的
先来看一幅图2

文章来源:http://www.codelast.com/
这幅图表示的是对一个目标函数寻找最优解的过程,图中锯齿状的路线就是寻优路线在二维平面上的投影。从这幅图我们可以看到,锯齿一开始比较大(跨越的距离比较大),后来越来越小;这就像一个人走路迈的步子,一开始大,后来步子越迈越小。
这个函数的表达式是这样的:
f({x_1},{x_2}) = {(1 - {x_1})^2} + 100 \cdot {({x_2} - {x_1}^2)^2}
它叫做Rosenbrock function3(罗森布罗克函数),是个非凸函数,在最优化领域,它可以用作一个最优化算法的performance test函数。这个函数还有一个更好记也更滑稽的名字:banana function(香蕉函数)。
我们来看一看它在三维空间中的图形:

Rosenbrock function 3D
文章来源:http://www.codelast.com/
它的全局最优点位于一个长长的、狭窄的、抛物线形状的、扁平的“山谷”中。
找到“山谷”并不难,难的是收敛到全局最优解(在 (1,1) 处)。
正所谓:世界上最遥远的距离,不是你离我千山万水,而是你就在我眼前,我却要跨越千万步,才能找到你
文章来源:http://www.codelast.com/
我们再来看另一个目标函数 f(x,y) = \sin \left( {\frac{1}{2}{x^2} - \frac{1}{4}{y^2} + 3} \right)\cos \left( {2x + 1 - {e^y}} \right) 的寻优过程4
和前面的Rosenbrock function一样,它的寻优过程也是“锯齿状”的。
它在三维空间中的图形是这样的:
总而言之就是:当目标函数的等值线接近于圆(球)时,下降较快;等值线类似于扁长的椭球时,一开始快,后来很慢。
文章来源:http://www.codelast.com/
『5』为什么“慢”
从上面花花绿绿的图,我们看到了寻找最优解的过程有多么“艰辛”,但不能光看热闹,还要分析一下原因。
在最优化算法中,精确的line search满足一个一阶必要条件,即:梯度与方向的点积为零(当前点在 {d_k} 方向上移动到的那一点( {x_k} + {\alpha _k}{d_k} )处的梯度,与当前点的搜索方向 {d_k} 的点积为零)。
由此得知:
\nabla f{({x_k} + {\alpha _k}{d_k})^T}{d_k} = 0 ,即 g_{k + 1}^T{d_k} = 0
故由梯度下降法的 {d_k} = - {g_k} 得:
g_{k + 1}^T{d_k} = g_{k + 1}^T( - {g_k}) = - g_{k + 1}^T{g_k} = - d_{k + 1}^T{d_k} = 0 \Rightarrow d_{k + 1}^T{d_k} = 0
即:相邻两次的搜索方向是相互直交的(投影到二维平面上,就是锯齿形状了)。
文章来源:http://www.codelast.com/
如果你非要问,为什么 d_{k + 1}^T{d_k} = 0 就表明这两个向量是相互直交的?那是因为,由两向量夹角的公式:
\cos \theta = \frac{{{d_k}^T{d_k}}}{{\left\| {{d_k}} \right\|\left\| {{d_k}} \right\|}} = \frac{0}{{\left\| {{d_k}} \right\|\left\| {{d_k}} \right\|}} = 0\;
=> \theta = \frac{\pi }{2}
可知两向量夹角为90度,因此它们直交。

『6』优点
这个被我们说得一无是处的方法真的就那么糟糕吗?其实它还是有优点的:程序简单,计算量小;并且对初始点没有特别的要求;此外,许多算法的初始/再开始方向都是最速下降方向(即负梯度方向)。
文章来源:http://www.codelast.com/
『7』收敛性及收敛速度
梯度下降法具有整体收敛性——对初始点没有特殊要求。
采用精确的line search的梯度下降法的收敛速度:线性。
 

  • 引用
(1)https://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality
(2)https://en.wikipedia.org/wiki/Gradient_descent
(3)https://en.wikipedia.org/wiki/Rosenbrock_function
(4)https://en.wikipedia.org/wiki/Gradient_descent… Read More

[原创] Cauchy-Schwartz(柯西-许瓦兹)不等式复习

转载请注明出处:http://www.codelast.com/

柯西-许瓦兹不等式,又叫柯西不等式柯西-施瓦茨不等式施瓦茨不等式柯西-布尼亚科夫斯基-施瓦茨不等式,等等,中文名太多了,它是最重要的数学不等式之一,如下:
{({a_1}{b_1} + {a_2}{b_2} + \cdots + {a_n}{b_n})^2} \le (a_1^2 + a_2^2 + \cdots + a_n^2)(b_1^2 + b_2^2 + \cdots + b_n^2) Read More

[原创]使用一维搜索(line search)的算法的收敛性

转载请注明出处:http://www.codelast.com/

在最优化领域中,有一类使用一维搜索(line search)的算法,例如牛顿法等。这类算法采用的是 确定搜索方向→进行一维搜索→调整搜索方向→进行一维搜索 的迭代过程来求解。那么,这类算法应该满足什么条件的时候才能收敛?本文将略为讨论一下。请务必看清本文的标题:不是讨论line search的收敛性,而是讨论使用line search的算法的收敛性。… Read More

[原创]用“人话”解释不精确线搜索中的Armijo-Goldstein准则及Wolfe-Powell准则

转载请注明出处:http://www.codelast.com/

line search(一维搜索,或线搜索)是最优化(Optimization)算法中的一个基础步骤/算法。它可以分为精确的一维搜索以及不精确的一维搜索两大类。
在本文中,我想用“人话”解释一下不精确的一维搜索的两大准则:Armijo-Goldstein准则 & Wolfe-Powell准则。
之所以这样说,是因为我读到的所有最优化的书或资料,从来没有一个可以用初学者都能理解的方式来解释这两个准则,它们要么是长篇大论、把一堆数学公式丢给你去琢磨;要么是简短省略、直接略过了解释的步骤就一句话跨越千山万水得出了结论。
每当看到这些书的时候,我脑子里就一个反应:你们就不能写人话吗?… Read More

[原创]一维搜索中的划界(Bracket)算法

转载请注明出处:http://www.codelast.com/

很多最优化算法需要用到一维搜索(line search)子算法,而在众多的一维搜索算法中,大多数都要求函数被限制在一个单峰区间内,也就是说,在进行一维搜索的区间内,函数是一个单峰函数。尽管有一些改进的一维搜索算法(例如 H\ddot opfinger 建议的一种改进过的黄金搜索算法)可以处理函数非单峰的情况,但是,在没有确定函数在一个区间内是单峰的之前,即使在搜索过程中,函数值持续减小,我们也不能说极小值是一定存在的,因此,找出一个区间,在此区间之内使函数是单峰的,这个过程是必需的(我更倾向于接受这种观点)。这个过程就叫作划界Bracket)。Bracket这个单词是括号的意思,很形象——用括号包住一个范围,就是划界。在某些书中,划界算法也被称为进退法。… Read More

[原创]最优化/Optimization文章合集

转载请注明出处:https://www.codelast.com/

最优化(Optimization)是应用数学的一个分支,它是研究在给定约束之下如何寻求某些因素(的量),以使某一(或某些)指标达到最优的一些学科的总称。我一直对最优化比较感兴趣,所以写过一些相关的笔记,可能有不正确的地方,但请学术派、技术流们多多包涵。

➤ 拟牛顿法/Quasi-Newton,DFP算法/Davidon-Fletcher-Powell,及BFGS算法/Broyden-Fletcher-Goldfarb-Shanno

➤ 最速下降法/steepest descent,牛顿法/newton,共轭方向法/conjugate direction,共轭梯度法/conjugate gradient 及其他

➤ Ridders求导算法

➤ 选主元的高斯-约当(Gauss-Jordan)消元法解线性方程组/求逆矩阵
文章来源:http://www.codelast.com/
➤ 关于 最优化/Optimization 的一些概念解释

➤ 最小二乘的理论依据

➤ Powell共轭方向集方法(Powell's Conjugate Direction Method)的实现Read More

[原创]拟牛顿法/Quasi-Newton,DFP算法/Davidon-Fletcher-Powell,及BFGS算法/Broyden-Fletcher-Goldfarb-Shanno

转载须注明出处:http://www.codelast.com/

 

在最优化领域,有几个你绝对不能忽略的关键词:拟牛顿、DFP、BFGS。名字很怪,但是非常著名。下面会依次地说明它们分别“是什么”,“有什么用” 以及 “怎么来的”。

但是在进入正文之前,还是要先提到一个概念上的区别,否则将影响大家的理解:其实DFP算法、BFGS算法都属于拟牛顿法,即,DFP、BFGS都分别是一种拟牛顿法。Read More

[原创]最速下降法/steepest descent,牛顿法/newton,共轭方向法/conjugate direction,共轭梯度法/conjugate gradient 及其他

转载须注明出处:http://www.codelast.com/

 

在最优化的领域中,这“法”那“法”无穷多,而且还“长得像”——名字相似的多,有时让人觉得很迷惑。

在自变量为一维的情况下,也就是自变量可以视为一个标量,此时,一个实数就可以代表它了,这个时候,如果要改变自变量的值,则其要么减小,要么增加,也就是“非左即右“,所以,说到“自变量在某个方向上移动”这个概念的时候,它并不是十分明显;而在自变量为n(n≥2)维的情况下,这个概念就有用了起来:假设自变量X为3维的,即每一个X是(x1, x2, x3)这样的一个点,其中x1,x2和x3分别是一个实数,即标量。那么,如果要改变X,即将一个点移动到另一个点,你怎么移动?可以选择的方法太多了,例如,我们可以令x1,x2不变,仅使x3改变,也可以令x1,x3不变,仅使x2改变,等等。这些做法也就使得我们有了”方向“的概念,因为在3维空间中,一个点移动到另一个点,并不是像一维情况下那样“非左即右”的,而是有“方向”的。在这样的情况下,找到一个合适的”方向“,使得从一个点移动到另一个点的时候,函数值的改变最符合我们预定的要求(例如,函数值要减小到什么程度),就变得十分有必要了。Read More

[原创]选主元的高斯-约当(Gauss-Jordan)消元法解线性方程组/求逆矩阵

转载请注明出处:http://www.codelast.com/

 

选主元的高斯-约当(Gauss-Jordan)消元法在很多地方都会用到,例如求一个矩阵的逆矩阵、解线性方程组(插一句:LM算法求解的一个步骤),等等。它的速度不是最快的,但是它非常稳定来自网上的定义:一个计算方法,如果在使用此方法的计算过程中,舍入误差得到控制,对计算结果影响较小,称此方法为数值稳定的,同时它的求解过程也比较清晰明了,因而人们使用较多。下面我就用一个例子来告诉你Gauss-Jordan法的求解过程吧。顺便再提及一些注意事项以及扩展话题。

对本文中所提到的“主元”等概念的解释,可以参考此链接Read More