机器学习中的数学

平方误差
梯度下降法
矩阵求解
极大似然估计
熵的原理
启发式算法

平方误差

误差，指的是某个变量的错误程度，直白来说，误差就是“真实值-预测值”。那么，平方误差通过计算每一个样本误差的平方，再求和。即平方误差的公式是 $L=\sum_{i=1}^{N}(\hat{y}_{i}-y_{i})^{2}$。其中，$\hat{y}_{i}$ 为第 $i$ 个样本的真实值，$y_{i}$ 为第 $i$ 个样本的预测值。

梯度下降法

机器学习中的所有算法都依赖于最小化或最大化某一个函数，我们称之为“目标函数”。最小化的这组函数被称为“损失函数”。损失函数是衡量预测模型预测期望结果表现的指标。寻找函数最小值的最常用方法是“梯度下降”。把损失函数想象成起伏的山脉，梯度下降就像从山顶滑下，目的是到达山脉的最低点。
关于求解极小值问题，我们常用的方法是代数法和求导法：

代数法：$y=x^{2}+2x+3$ 可以化为 $y=(x+1)^{2}+2$，那么其最小值 $x$ = -1时取到。
求导法：令 $y=x^{2}+2x+3$ 的导数：$\frac{\mathrm{d}y}{\mathrm{d}x}=2x+2=0$。解得 $x$ = -1时 $y$ 取得最小值。

但是，求解函数$y=x^{2}+2x+e^{x}+3$的极小值时，代数法和求导法都不再适用，此时就需要用更通用的极值求解方法，这就是梯度下降法。
首先，梯度 (gradient) 是一阶偏导组成的向量，其表示函数变化率最快的方向，是相对于一个向量求导的导数： $f$ 的梯度是包含所有偏导数的向量，记为 ${\nabla}_{x}f(x)$。梯度的第 $i$ 个元素是 $f$ 关于 $x_i$ 的偏导数。在多维情况下，临界点是梯度中的所有元素都为 $0$ 的点。
在 $u$(单位向量)方向的方向导数 (directional derivative) 是函数 $f$ 在 $u$ 方向的斜率。换句话说，方向导数是函数 $f(x+{\alpha}u)$ 关于 $\alpha$ 的导数（在 $\alpha$ = 0 时取到）。使用链式法则，我们可以看到当 $\alpha$ = 0 时，$\frac{\partial}{\partial \alpha}f(x+{\alpha}u)=u^\top{\nabla}_{x}f(x)$。
为了最小化 $f$,我们希望找到使 $f$ 下降得最快的方向。计算方向导数为：$$\min_{u,u^\top u=1}u^\top{\nabla}_{x}f(x)$$$$=\min_{u,u^\top u=1}\left|\left|u\right|\right|_2 \left|\left|{\nabla}_{x}f(x)\right|\right|_2 \cos \theta$$
其中 $\theta$ 是 $u$ 与梯度的夹角。将 $ \left|\left|u\right|\right|_2 =1$ 带入，并忽略与 $u$ 无关的项，就能简化得到 $\min_u \cos \theta$。这在 $u$ 与梯度方向相反时取得最小。换句话说，梯度向量指向上坡，负梯度向量指向下坡。我们在负梯度方向上移动可以减小 $f$。这就是梯度下降法(gradient descent)，也称最速下降法(method of steepest descent)。
最速下降法建议新的点为$$x’=x-\epsilon{\nabla}_{x}f(x)$$
其中 $\epsilon$ 为学习率(learning rate)，是一个确定步长大小的正标量。我们可以通过几种不同的方式选择 $\epsilon$。普遍的方式是选择一个小常数。有时我们通过计算，选择使方向导数消失的步长。还有一种方法是根据几个 $\epsilon$ 计算 $f(x-\epsilon{\nabla}_{x}f(x))$,并选择其中能产生最小目标函数值的 $\epsilon$。这种策略是线搜索。
回到上面的题，求 $y=x^{2}+2x+e^{x}+3$ 的最小值。首先我们先随机初始化一个点 $x_0=0$ ，设置学习率 $\epsilon=0.3$,其次，计算梯度 ${\nabla}_{x}f(x)=\frac{\mathrm{d}y}{\mathrm{d}x}=2x+2+e^x$。之后的计算交给MATLAB，代码如下：

x = 0.0;  %初始化值
c = 0.5;  %设置学习率

fprintf('n\t\t更新前的点\t\t梯度\t\t更新后的点\n');
for n = 1 : 10
	xold = x;                 %本次循环前的 xt 值
	grad = 2*x+2+exp(x);   %梯度
	xnew = x - c*grad;    %梯度下降法更新后的点

	fprintf('%d\t\t%6.2f\t\t%6.2f\t\t%6.2f\n',n,xold,grad,xnew);
	
	x = xnew;
end

得到结果如下：

n	更新前的点	梯度	更新后的点
1	0.00	3.00	-1.50
2	-1.50	-0.78	-1.11
3	-1.11	-0.11	-1.16
4	-1.16	-0.02	-1.16
5	-1.16	-0.00	-1.16
6	-1.16	-0.00	-1.16
7	-1.16	-0.00	-1.16
8	-1.16	-0.00	-1.16
9	-1.16	-0.00	-1.16
10	-1.16	-0.00	-1.16

从上表中可以看到，在第4次循环后，$x’$ 的值不再改变，收敛于 $x=-1.16$，即，当 $x=-1.16$ 时，y取得最小值为 $y_{min}=(-1.16)^2+2*(-1.16)+e^{-1.16}+3=2.33908$

机器学习中的数学

2020-01-03
Algorithm

机器学习中的数学