降维：当我们遇到样本数据的特征维度很高但数据稀疏，并且一些特征还可能是多余的，对任务目标没有贡献，这时机器学习任务会面临一个比较严重的障碍，我们称之为维数灾难（Curse of Dimensionality）；维数灾难不仅仅会导致计算困难，还会对机器学习任务的精度造成不良影响。缓解维数灾难的一个重要途径就是降维，即通过某些数学变换关系，将原始的高纬度空间映射到另一个低维的子空间，在这个子空间中，样本的密度会大幅提高，更容易进行学习

3、强化学习（Reinforcement Learning）

强化学习，又称再励学习、评价学习，是从动物学习、参数扰动自适应控制等理论发展而来的，ta把学习过程看作一个试探评价过程

机器学习选择一个初始动作作用于环境，环境接收到该动作后状态发生变化，同时产生一个强化信号（奖赏或惩罚）反馈给机器，机器再根据强化信号和环境当选择下一个动作，选择的原则是使受到正强化（奖赏）的概率增大

强化学习在智能机器人及分析预测等领域有许多应用，比如在围棋界打败世界冠军的AlphaGo就运用了强化学习

1.3 机器学习方法三要素

机器学习方法 = 模型 + 策略 + 算法

1.3.1 模型

我们可以将模型理解为函数: $y = f(x)$

$x$ 为数据的特征， $y$ 为特征为x的数据所对应的结果值， $f$ 是该数据类型对应的映射逻辑

举例说明：

我们现在要帮助银行建立一个模型来判别是否可以给某个用户办理信用卡，我们可以获得用户的性别、年龄、学历、工作年限和负债情况等基本信息，如图：

对用户的各个特征属性数值化：

性别：男用“1”表示，女用“2”表示

学历：高中、本科、硕士、博士分别用“1”、“2”、“3”、“4”表示

然后将每一个用户看作一个向量 $x_{i}$ ，其中 $i = 1,2,3,......,n$ ，向量 $xi$ 的维度就是第 $i$ 个用户的性别、年龄、学历、工作年限和负债情况等特征：

$x_{i}= \left ( xi^{(1)},xi^{(2)},...,xi^{(j)},...,xi^{(N)} \right )$ (N为特征数量)

给每个特征维度赋予一个权重 $w_{j}$ ，我们可以计算出向量的加权和 $W_{i}$ ：

$W_{i}= \sum_{j=1}^{N}wjxi^{j}$

并设定一个门限值（threshold），当某用户加权和大于门限值，则给其办理信用卡，反之则不办理，即：当 $W_{i}$ > threshould，准予办理；当 $W_{i}$ < threshould，不准予办理

进一步，我们将“是”和“否”分别用 “1” 和 “0” 表示，即：

$f(x_{i})=\begin{cases} & 1,\text{ } W_{i}-threshould>0\\ &0, \text{ } W_{i}-threshould<0 \end{cases}$

$f(x_{i})$ 就是我们对上述用户信用卡额度问题建立的一个模型，有了该模型后，每当有一个新用户来办理信用卡时，我们就可以将其填写的基本信息输入到该模型中，自动判别是否同意给其办理

上述模型中，含有未知参数 $w_{j}$ ， $j=1,2,...,N$ ，我们通过训练集将其学习出来，即为接下来要讲的策略问题

1.3.2 策略

训练集：指一批已经知道结果的数据，它具有和预测集相同的特征，比预测集多了已知的结果项

用户信用模型数据（训练集）

要由给定结果的训练集学习出模型中的位置参数 $w_{j}$ ， $j=1,2,...,N$ ，我们采取的策略是为模型定义一个“损失函数”（Loss Function）(也称作“风险函数”)，该损失函数可用来描述每一次预测结果与真实结果之间的差异

（1）0-1损失函数

$L(Y,f(X))=\begin{cases} & 1,\text{ } Y\neq f(x) \\ & 0,\text{ } Y=f(x) \end{cases}$

0-1损失函数在朴素贝叶斯模型的推导中会用到

（2）绝对损失函数

$L(Y,f(X))=|Y-f(X)|$

（3）平方损失函数

$L(Y,f(X))=(Y-f(X))^{2}$

平方损失函数一般用于回归问题中

（4）指数损失函数

$L(Y,f(X))=e^{-Yf(X)}$

指数损失函数在AdaBoost模型的推导中会用到

（5）Hinge损失函数

$L(Y,f(X))=max(0,1-Yf(X))$

Hinge损失函数是SVM模型的基础

（6）对数损失函数

$L(Y,P(Y|X))=-logP(Y|X)$

对数损失函数在Logistics回归模型的推导中会用到

对于上述案例，我们采用平方损失函数，对于训练集中的每一个用户 $xi$ ，我们可以由上面建立的模型对其结果产生一个预测值，则有 $l(x_{i})=(y_{i}-f(x_{i}))^{2}$ ，那么对于训练集中所有M个用户，我们得到模型的总体损失函数为

$L(w,b)=\sum_{i=1}^{M}(y_{i}-f(x_{i}))^{2}$

其中 $w$ 指模型中的权重参数向量， $b$ 为设置的门限值，我们需要让损失函数最小化，此时预测值与真实值最接近。所以，求解模型未知参数的问题实际上就转化为求解公式：

$minL(w,b)=\sum_{i=1}^{M}(y_{i}-f(x_{i}))^{2}$

1.3.3 算法

通过定义损失函数并采用最小化损失函数策略，我们将案例问题转换为一个最优化问题，接下来求解该最优化问题，可采用的优化算法有梯度下降法、牛顿法、拟牛顿法......

1、梯度下降法

（1）引入

计算机在运用迭代法做数值计算（比如求解某个方程组的解）时，只要误差能够收敛，计算机经过一定次数的迭代后可以得到一个近似解，而计算机是沿梯度方向进行迭代的，因此引入梯度下降法

（2）梯度下降法原理

在多元微分学中，梯度就是函数的导数方向

根据导数的定义，函数 $L(w,b)$ 的导数就是目标函数在在变量 $w$ 和 $b$ 上的变化率，在多元的情况下，目标函数 $L(w,b)$ 在某点的梯度 $\bigtriangledown L(w,b)=(\frac{\partial L}{\partial w},\frac{\partial L}{\partial b})$ 是一个由各个分量的偏导数构成的向量，负梯度方向是 $L(w,b)$ 减小最快的方向

当要求 $L(w,b)$ 的最小值时，我们可以先任意选取一个函数的初始点，让其沿负梯度方向移动，即可最快到达极小值点

（3）梯度下降法的推导

先将 $f(x)$ 在 $x=x_{k}$ 处进行一阶泰勒展开，即

$f(x)\approx f(x_k)+\bigtriangledown f(x_k)(x-x_k)$

再取 $x=x_{k+1}$ ，得：

$f(x_{k+1})\approx f(x_k)+\bigtriangledown f(x_k)(x_{k+1}-x_k)$

整理得：

$f(x_{k+1})-f(x_k)\approx \bigtriangledown f(x_k)(x_{k+1}-x_k)$

又因为要使 $f(x)$ 下降，使得 $f(x_{k+1})\leqslant f(x_k)$ 恒成立

结合上式即等价于要使 $f^{'}(x_k)(x_{k+1}-x_k)\leqslant 0$ 恒成立

显然，我们取

$x_{k+1}-x_k = -\lambda \bigtriangledown f(x_k)$

即

$x_{k+1}=x_k-\lambda \cdot \bigtriangledown f(x_k)$

时，上面的等式是恒成立的

（4）梯度下降法得过程

输入：目标函数 $f(x)$ ，每一次的迭代步长为 $\lambda$ ，计算精度为 $\varepsilon$

输出： $f(x)$ 的极小值点 $x^{*}$

步骤如下：

第 1 步：任取初始值 $x_{0}$ ，即置 $k = 0$

第 2 步：计算 $f(x)$ 在 $x_k$ 处的函数值 $f(x_k)$ 和 $f(x)$ 在 $x_k$ 处的梯度值 $\bigtriangledown f(x)|_{x = x_k}=\bigtriangledown f(x_k)$

第 3 步：若 $\bigtriangledown f(x_k)<\varepsilon$ ，则停止迭代，极小值点为 $x^{*}=x_k$

第 4 步：置 $x_{k+1}=x_k-\lambda \cdot \bigtriangledown f(x_k)$ ，计算 $f(x_{k+1})$

第 5 步：若 $|f(x_{k+1})-f(x_k)|<\varepsilon$ 或 $|x_{k+1}-x_k|<\varepsilon$ 时，停止迭代，极小值点为 $x^{*}=x_{k+1}$

第 6 步：否则，置 $k = k+1$ ，转到第 2 步

对于于多维情况，如损失函数 $L(w,b)$ ，求解过程中的梯度应换成各自的偏导数

上述过程称为批量梯度下降法

（5）随机梯度下降法

在梯度下降法的迭代中，除梯度值本身的影响外，每一次取的步长 $\lambda$ 也很关键：步长取值越大，收敛速度越快，但容易越过函数的最优点，导致发散；步长取值越小，算法的收敛速度又会明显降低

另外，当目标函数不是凸函数时，使用梯度下降法求得的结果可能只是某个局部的最优点

为解决上述两个问题，引入随机梯度下降法，与批量梯度下降法原理相同，改进如下：

a. 将固定步长 $\lambda$ 改为动态步长 $\lambda _k$

b. 引入随机样本抽取方式，即每次迭代只是随机取了训练集中的一部分样本数据进行梯度计算

优点：有效避免陷入局部最优的情况

缺点：会稍微降低优化过程的收敛速度，并导致最后得到的最优点可能只是全局最优点的一个近似

（6）随机梯度下降法过程

输入：目标函数 $f(x)$ ，计算精度为 $\varepsilon$

输出： $f(x)$ 的极小值点 $x^{*}$

步骤如下：

第 1 步：任取初始值 $x_{0}$ ，即置 $k = 0$

第 2 步：计算 $f(x)$ 在 $x_k$ 处的函数值 $f(x_k)$ 和 $f(x)$ 在 $x_k$ 处的梯度值 $\bigtriangledown f(x)|_{x = x_k}=\bigtriangledown f(x_k)$

第 3 步：若 $\bigtriangledown f(x_k)<\varepsilon$ ，则停止迭代，极小值点为 $x^{*}=x_k$

第 4 步：否则求解最优化问题： $minf(x_k-\lambda _k\cdot \bigtriangledown f(x_k))$ ，得到第 $k$ 轮的迭代步长 $\lambda _k$ ；

再置 $x_{k+1}=x_k-\lambda_k \cdot \bigtriangledown f(x_k)$ ，计算 $f(x_{k+1})$

第 5 步：当 $|f(x_{k+1})-f(x_k)|<\varepsilon$ 或 $|x_{k+1}-x_k|<\varepsilon$ 时，停止迭代，极小值点为 $x^{*}=x_{k+1}$

第 6 步：否则，置 $k = k+1$ ，转到第 2 步

2、牛顿法

（1）牛顿法介绍

牛顿法也是求解无约束最优化问题的常见方法，最大的优点是收敛速度快

（2）牛顿法的推导

将目标函数 $f(x)$ 在 $x=x_{k}$ 处进行二阶泰勒展开，可得：

$f(x)\approx f(x_k)+\bigtriangledown f(x_k)(x-x_k)+\frac{1}{2}\bigtriangledown ^{2}f(x_k)(x-x_k)^{2}$

因为目标函数 $f(x)$ 有极值的必要条件是在极值点处一阶导数为0，即 $f{}'(x)=0$ ，所以对上面的展开式两边同时求导（只有 $x$ 为变量，其余皆为常量），并令 $f{}'(x)=0$ ，可得：

$f{}'(x)=\bigtriangledown f(x_k)+\bigtriangledown ^{2}f(x_k)(x-x_k)=0$

取 $x = x_{k+1}$ ，可得：

$\bigtriangledown f(x_k)+\bigtriangledown ^{2}f(x_k)(x_{k+1}-x_k)=0$

整理后得到：

$x_{k+1}=x_k-\bigtriangledown ^{2}f(x_k)^{-1}\cdot \bigtriangledown f(x_k)$

上式中， $\bigtriangledown f(x)$ 是关于未知变量 $x^{(1)},x^{(2)},...x^{(N)}$ 的梯度矩阵表达式，即

$\bigtriangledown f(x)=\begin{bmatrix} \frac{\partial f}{\partial x^{(1)}}\\ \frac{\partial f}{\partial x^{(2)}}\\ ...\\ \frac{\partial f}{\partial x^{(N)}} \end{bmatrix}$

$\bigtriangledown^{2} f(x)$ 是关于未知变量 $x^{(1)},x^{(2)},...x^{(N)}$ 的Hessen矩阵表达式，一般记作 $H(f)$ ，即

$H(f)=\bigtriangledown ^{2}f(x)=\begin{bmatrix} \frac{\partial^2 f}{\partial x^{(1)^2}} & \frac{\partial^2 f}{\partial x^{(1)}\partial x^{(2)}} & ... & \frac{\partial^2 f}{\partial x^{(1)}\partial x^{(N)}} \\ \frac{\partial^2 f}{\partial x^{(2)}\partial x^{(1)}} & \frac{\partial^2 f}{\partial x^{(2)^2}} & ... & \frac{\partial^2 f}{\partial x^{(2)}\partial x^{(N)}} \\ ... & ... & ...&... \\ \frac{\partial^2 f}{\partial x^{(N)}\partial x^{(1)}} & \frac{\partial^2 f}{\partial x^{(N)}\partial x^{(2)}} & ... & \frac{\partial^2 f}{\partial x^{(N)^2}} \\ \end{bmatrix}$

（3）牛顿法的过程

输入：目标函数 $f(x)$ ，计算精度为 $\varepsilon$

输出： $f(x)$ 的极小值点 $x^{*}$

步骤如下：

第 1 步：任取初始值 $x_{0}$ ，即置 $k = 0$

第 2 步：计算 $f(x)$ 在 $x_k$ 处的函数值 $f(x_k)$ 和， $f(x)$ 在 $x_k$ 处的梯度值 $\bigtriangledown f(x)|_{x = x_k}=\bigtriangledown f(x_k)$ ， $f(x)$ 在 $x_k$ 处的Hessen矩阵值 $\bigtriangledown^{2} f(x_k)$

第 3 步：若 $-\bigtriangledown ^{2}f(x_k)^{-1}\cdot \bigtriangledown f(x_k)< \varepsilon$ ，则停止迭代，极小值点为 $x^{*}=x_k$

第 4 步：置 $x_{k+1}=x_k-\bigtriangledown ^{2}f(x_k)^{-1}\bigtriangledown f(x_k)$ ，计算 $f(x_{k+1})$

第 5 步：若 $|f(x_{k+1})-f(x_k)|<\varepsilon$ 或 $|x_{k+1}-x_k|<\varepsilon$ 时，停止迭代，极小值点为 $x^{*}=x_{k+1}$

第 6 步：否则，置 $k = k+1$ ，转到第 2 步

从本质上看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法更快

从几何上说，牛顿法是用一个二次曲面去拟合当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部平面，通常情况下，二次曲面的拟合会比平面更好

（4）阻尼牛顿法

牛顿法的问题：当初始点 $x_0$ 远离极小值点时，牛顿法可能不收敛

原因：牛顿方向 $d = -\bigtriangledown ^{2}f(x_k)^{-1}\cdot \bigtriangledown f(x_k)$ 不一定是下降方向，经迭代，目标函数值可能上升；此外，即使目标函数是下降的，得到的点 $x_{k+1}$ 也不一定是沿牛顿方向最好的点或极小值点

解决：阻尼牛顿法

（5）阻尼牛顿法的过程

输入：目标函数 $f(x)$ ，计算精度为 $\varepsilon$

输出： $f(x)$ 的极小值点 $x^{*}$

步骤如下：

第 1 步：任取初始值 $x_{0}$ ，即置 $k = 0$

第 3 步：若 $-\bigtriangledown ^{2}f(x_k)^{-1}\bigtriangledown f(x_k)< \varepsilon$ ，则停止迭代，极小值点为 $x^{*}=x_k$

第 4 步：否则求解最优化问题： $minf(x_k-\lambda_k\cdot \bigtriangledown ^{2}f(x_k)^{-1}\bigtriangledown f(x_k))$ ，得到第 $k$ 轮的迭代步长 $\lambda _k$ ，再置 $x_{k+1}=x_k-\bigtriangledown ^{2}f(x_k)^{-1}\bigtriangledown f(x_k)$ ，计算 $f(x_{k+1})$