掌握机器学习数学基础之优化基础（一）

目录：

计算复杂性与NP问题

上溢和下溢

导数，偏导数及两个特殊矩阵

函数导数为零的二三事

方向导数和梯度

梯度下降法

牛顿法

读完估计需要10min，这里主要讲解第一部分，剩余部分期待下期～

计算复杂性与NP问题

算法的复杂性：现实中大多数问题都是离散的数据集，为了反映统计规律，有时数据量很大，而且多数目标函数都不能简单地求得解析解。而为了记录在解决问题的算法的性能或者说好坏，就引入了算法的复杂性。

算法理论被认为是解决各类现实问题的方法论。而衡量算法理论的计算复杂度可分为：时间复杂度和空间复杂度，这是对算法执行所需要的两类资源——时间和空间的估算。其中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间，空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度

另为，一般的，衡量问题是否可解的重要指标是：该问题能否在多项式时间内求解，还是只能在指数时间内求解？在各类算法理论中，通常使用多项式时间算法即可解决的问题看作是易解问题，需要指数时间算法解决的问题看作是难解问题。

指数时间算法的计算时间随着问题规模的增长而呈指数化上升，这类问题虽然有解，但并不适用于大规模问题。所以当前算法研究的一个重要任务就是将指数时间算法变换为多项式时间算法。

确定性和非确定性：除了问题规模与运算时间的比较，衡量一个算法还需要考虑确定性和非确定性的概念。

先说说自动机：是有限状态机(FSM)的数学模型。实际上是指一种基于状态变化进行迭代的算法。也就是在给定输入和状态时，自动机的状态会发生改变的模型。在算法领域常把这类算法看作一个机器，比较知名的有图灵机、玻尔兹曼机、支持向量机等。或者，在日常生活中的自动售卖机就是一种有限状态机。

确定性：所谓确定性，是指针对各种自动机模型，根据当时的状态和输入，若自动机的状态转移是唯一确定的，则称具有确定性；

非确定性：若在某一时刻自动机有多个状态可供选择，并尝试执行每个可选择的状态，则称具有不确定性。

换个说法就是：确定性是程序每次运行时产生下一步的结果是唯一的，因此返回的结果也是唯一的；非确定性是程序在每个运行时执行的路径是并行且随机的，所有路径都可能返回结果，也可能只有部分返回结果，也可能不返回结果，但是只要有一个路径返回结果，那么算法就结束。

NP问题：简单的说，存在多项式时间的算法的一类问题，称之为P类问题；在多项式时间内可由非确定机解决的一类问题，称之为NP问题。另外，很多人相信P类问题是NP问题的一个子集，但既没有人证明出有某个问题属于NP但不属于P，也没有人证明所有NP问题都能在多项式时间内有解，如图：

来自百度百科

P类问题：就是能够以多项式时间的确定性算法来对问题进行判定或求解，实现它的算法在每个运行状态都是唯一的，最终一定能够确定一个唯一的结果——最优的结果。

NP问题：是指可以用多项式时间的非确定性算法来判定或求解，即这类问题求解的算法大多是非确定性的，但时间复杂度有可能是多项式级别的。

对于上面的知识，我们只要了解知道他们的概念就好了，机器学习中多数算法都是针对NP问题（包括NP完全问题）的。

上溢和下溢

下溢：当接近零的数被四舍五入为零时发生下溢。许多函数会在其参数为零而不是一个很小的正数时才会表现出质的不同。例如，我们通常要避免被零除。

上溢(overflow)：当大量级的数被近似为时发生上溢。进一步的运算通常将这些无限值变为非数字。

为什么会下溢或者上溢：数字计算机上实现连续数学的基本困难是我们需要通过有限数量的位模式来表示无限多的实数，这意味着我们在计算机中表示实数时几乎都会引入一些近似误差。在许多情况下，这仅仅是舍入误差。如果在理论上可行的算法没有被设计为最小化舍入误差的累积，可能会在实践中失效，也就是可能产生下溢或者上溢

一个例子：必须对上溢和下溢进行数值稳定的一个例子是softmax 函数。softmax 函数经常用于预测与Multinoulli分布相关联的概率，定义为：

这个概念是比较重要的，我们需要了解清楚！

导数和偏导数

导数： 当函数定义域和取值都在实数域中的时候，导数可以表示函数曲线上的切线斜率。 当然除了切线的斜率，导数还表示函数在该点的变化率。或者从物理意义来说，就是瞬时变化率。

上面是一维导数的定义式，其中涉及极限的知识，简单来说极限就是“无限靠近而永远不能到达”，当然，高中初中就学过导数，这个也可以用之前斜率的角度去理解，多维的话也就是在此之上的推广。

将上面的公式转化为下面图像为：

注意：在一元函数中，只有一个自变量变动，也就是说只存在一个方向的变化率，这也就是为什么一元函数没有偏导数的原因。

对应的图像形象表达如下：

注意：Hessian等价于梯度的Jacobian矩阵。

微分算子在任何二阶偏导连续的点处可交换，也就是它们的顺序可以互换：

这意味着， 因此也就是说Hessian矩阵在这些点上是对称的。

这些知识是前置知识，下面都要用到，记住两个特殊矩阵指的是什么？然后偏导数是什么？