机器学习数学基础(1)---导数优化问题
一、前言
熟悉机器学习的童靴会发现，机器学习中许多算法都是如下思路：问题提出、建立损失函数（loss function）、求出最优解。最优解的求解过程，往往是个迭代过程，使损失函数达到最优（或一定阈值范围内）。这里列举几类机器学习常见优化问题：
可见，最优化方法在机器学习中的重要地位。本文介绍几种常用的导数优化方法，希望对更加深入（ｃｕｉ）学（ｎｉｕ）习（ｂｉ）机器学习有所帮助。
二、最优化问题及凸优化问题
2.1 最优化问题(optimization)
这里我先直接上度娘
如果对以上的解释还有些迷糊，那看一下如下例题：
例1.
看完，我们基本上就都熟悉了，上面的例题是我们在高中一口气做20道都不会错的题目(如果忘了怎么解，请翻看《5年高考3年模拟精装版》)
以上例1便是一个典型的最优化问题，更准确地说，是一个线性规划问题。这里，我给出最优化问题的大白话解释:
最优化问题:
1.根据应用场景找到目标函数（如例1中的盈利）,这个目标函数将是你要优化的
2.找到一个能让目标函数最优的方法
3.利用这个方法进行求解
2.2 最优化问题定义及分类
2.2.1 最优化问题定义
这里，给出最优化问题数学上形式化的定义：
（摘自Stephen Boyd《Convex Optimization》一书）
其中x为n维向量，也是我们最终要求出的解;subject to (s.t.)为受限于，第一项为不等式约束，第二项为等式约束
2.2.1 最优化问题的分类
最优化问题有多种多样的分类方法，主要依据不同的分类角度，这里列举最简单的两种分类
1.根据约束函数分类：无约束优化、等式约束优化、不等式约束优化
2.根据目标函数是否为凸：凸优化、非凸优化
后面讲到的都是无约束+凸的问题，无约束的凸优化是比较好求解(一定有最优解)同时很容易掌握的。
2.3 凸优化问题(convex optimization)
可以看到，凸优化问题只是在优化问题上加上了凸的限制。之所以要研究凸优化问题，是因为凸优化是一类特别“优”的优化问题，它的优体现在：
1.凸优化问题的可行域是凸集
2.凸优化问题的局部最优解均是全局最优解
凸集 非凸集
凸函数最优解情况 非凸函数最优解情况
有关凸集、凸函数的数学解释不展开讲，在求解最优化问题时记住以下形象比喻即可：
1.凸优化问题，好比你面对的是一个峡谷，只要你一直往下走，一定能达到峡谷的最低点（最优解）
2.非凸优化，你可能面对的是一个坑坑洼洼的大草原，你可能走到了某个低洼地带（局部最优），但这不是整个草原的最低点（全局最优）
常用的线性回归、逻辑回归都是凸问题。值得指出的是，很多童鞋认为k-means也是凸问题，其实k-means的目标函数是非凸的，所以k-means不保证能找到全局最优解，但每次都能找到局部最优解，所以k-means受初始点影响很大，一般都是多次计算取最优（相当于在几个局部最优解选最优）。
三、导数优化问题
前面两个章节，我们从最优化问题讲到了凸优化问题，主要还是提纲挈领地讲了一些概念性的知识点。那么，如何具体求解凸优化问题呢，本节主要介绍无约束条件下的导数优化方法。
导数优化方法的套路都是下降方法(descent method)，通俗的说，就是以一定的步长、一定的方向往最优解（峡谷底部）靠近。下降方法的形式化定义如下：
导数优化问题基本套路
以上的套路是比较通用的，不同方法的差异仅仅在搜索方向上。值得说明的是，如果遵循步子迈太大容易扯着蛋的原则，同时最优步长可计算的情况下，可以在每次迭代时选择最优步长，但在实际应用中我们往往也使用固定步长。
步子迈太大容易扯着蛋
依据搜索方向的不同，可以细分为许多不同的方法：
常用导数优化方法
上述（1）~（4）为非常常用的几类方法，（1）、（2）、（3）选择了三种不同的搜索方向，（4）在（3）的基础上做了改进，主要避免了Hesse矩阵逆的计算。由于篇幅所限，主要讲解（1）和（2）
3.1 梯度下降法（Gradient descent/Steepest descent）
例2.
3.2 牛顿法
在梯度下降法中，我们看到，该方法主要利用的是目标函数的局部性质，具有一定的“盲目性”。牛顿法则是利用局部的一阶和二阶偏导信息，推测整个目标函数的形状，进而可以求得出近似函数的全局最小值，然后将当前的最小值设定近似函数的最小值。相比梯度下降法，牛顿法带有一定对全局的预测性，收敛性质也更优良。
对牛顿方向的推导：
将上述最后一项与下降方法一般式进行比较，会发现，牛顿法是以牛顿方向为搜索方向，1为固定步长进行迭代计算:
优点：二次终止性。对于二次凸函数，经过有限次迭代必达到极小点
缺点：步长恒等于1，并不能保证函数值稳定的下降
牛顿法迭代步骤：
牛顿法迭代步骤
例3.
牛顿法适用的情形:要求目标函数具有连续的一、二阶导数；Hesse矩阵非奇异。但现实情况是，就算是满足以上条件，由于要求解二阶偏导及其逆矩阵，计算所需资源会很大，这时候DFP、BFGS等会是很好的替代方法。
四、小结
最优化方法是机器学习的重要基础，上述的方法能很好的解决相关算法问题。比如。可以利用梯度下降法求解线性回归以及矩阵分解问题，LR问题也可由牛顿法求解，后续会介绍相关应用。
