Machine Learning

• Goal of Machine Learning
• Linear Classification
• Solution
• Numerical output example: linear regression
• Stochastic Gradient Descent
• Matrix Acceleration

Goal of Machine Learning 机器学习的目标

假设现在有一组数据$x_i,y_i$，其中$x_c\in {\mathbb{R}}^d$，d指的是特征数，而$y_c\in \mathbb{R}$是标签值(label)。

上述数据被称为训练集(training data set)。而机器学习的目的就是训练一个模型(model)（或者假说）$h$在某种条件下最贴近该训练集数据。

现在假设出现了一个新的点$x\ast \in {\mathbb{R}}^d$，我们需要用我们的模型去预测其标签值$y\ast$，这个值$x\ast$就被称作检验数据(test data)，模型检测标签值的准确程度被叫做泛化误差(generalization error)。

Linear Classification 线性分类

上述情景的一个经典例子是线性分类。

条件：在平面上有一堆红色的点和黑色的点。

目标：找到一条直线，使得所有红色的点都在直线一侧，而黑色点都在直线另一侧。

我们保证这个直线是存在的，如何找到满足条件的直线呢？

我们将点到直线的垂直距离记为模型的标签值，并且希望所有红色点的垂直距离为正，而黑色点的垂直距离为负，这样他们就一定分布在直线的异侧。

因此我们得到训练集：
$$(x_1,0),(x2,1),\cdots$$
其中标签值为0表示红色点，为1表示黑色点。

目标：我们将所有的$x_i$丢到模型里面，模型给出的标签值可以和训练集的标签值尽量一致。

那么我们如何找到这个模型$h$呢?

Solution 解决办法

平面，直线，你想到了我们之前学过的什么东西？没错，线性规划。

所有的红色点和黑色点都对应一个约束条件，而我们的目标是寻找可行域。

实际上我们会有无数条直线满足上面的约束条件，我们如何定义其中最好的一条决定了我们如何训练模型。我们给出的答案是，有**最大边界(maximum margin)**的一条直线。也就是说，所有的点到直线的距离都大于一个常数$\sigma$，这个$\sigma$就是边界。

上面的最优化模型也有一个名称：支持向量机(support vector machine,SVM)
我们使用二分搜索来确定$\sigma$，而对于每一个$\sigma$我们解一个线性规划即可。

Numerical output example: linear regression 数值输出：线性回归

在更多的情况下，我们需要返回一个预测值，一个常见的例子就是线性回归。
我们定义了一系列训练集$(x_i,y_i)$和损失函数$L(h)=\frac{1}{n}\Sigma (<x_i,h>-y_i{)}^2$，
模型生成之后我们给出测试集$x\ast$，模型给出预测值$y\ast$。损失函数计算预测值和实际值的垂直距离，使得模型可以持续优化。

如何找到线性回归的模型呢？前面我们提到的梯度下降是一个好方法。

我们回忆一下梯度下降的方法：

1. 选择初始点$h_0$，步数$T$和学习率$\eta$。
2. 在每步迭代中，计算当前点的梯度，并且迭代点$h_{i+1}=h_i-\eta \nabla L(h)$
3. 最后输出$\frac{1}{T}\Sigma h_i$
   (或者直接输出$h_T$)

我们发现$L(h)$具有一个很好的性质：由于$x^2$是凸函数，因此其线性组合也是凸的。所以我们可以在这个问题中使用梯度下降法。

另外一个问题是：$L(h)$的梯度是什么?

要解决这个问题，我们需要关注损失函数$f_i$的梯度：

$$\nabla f_i=(<h,x_i>-y_i{)}^2$$

由于链式法则，令$z=<h,x_i>-y_i$，那么有
$$\begin{gathered} \frac{d{f}_i}{d{h}_j}=\frac{d{f}_i}{dz}\frac{dz}{dh} \\ \frac{d{f}_i}{dz}=2z \\ \frac{dz}{dh}=x_{i,j} \end{gathered}$$
因此
$$\frac{d{f}_i}{dh}=2(<h_j,x_{i,j}>-y_i)x_{i,j}$$
因此求和一下就得出损失函数的梯度：
$$\nabla L(h)=\frac{2}{n}<(\Sigma <h_1,x_{t,1}>-y_t)x_{t,1},\Sigma (<h_2,x_{t,2}>-y_t)x_{t,2},\cdots >$$

Overfitting 过拟合

过拟合是机器学习中一种另外的状况，这种情况下模型为了贴合数据而变得十分奇怪且复杂。这一样也是我们不希望看到的。如下图所示：

也就是说，我们希望我们的模型要好，而且要直观简单，要有鲁棒性。我们有什么方法来保证鲁棒性吗？

一种简单的方法是，控制模型$h$的范数。由前一小节我们看到，预测结果由$h_i{x}_{t,i}$控制，也就是说当$h_i$的范数很大时，单个数据的变化就会对整体造成很大的影响，这是我们不希望看到的。反过来看，控制模型的范数也就减小了单个数据的整体影响，提高了鲁棒性。

Ridge Regression 岭回归算法

岭回归算法在原来$L(h)$的基础上添加了一项正则项(regularization)，使得新的损失函数变为：
$$L(h)=\frac{1}{n}\Sigma (<h,x>-y{)}^2+\lambda ||h|{|}^2$$
在这个损失函数中，我们将模型的范数也加入考虑，在欠拟合和过拟合之间做出了平衡。

由于两个平方项都是凸的，因此新的损失函数很明显也是凸的。

Stochastic Gradient Descent SGD 随机梯度下降

另外一个问题在于，当训练数据量很大的时候，损失函数的计算就会变得十分缓慢，这种情况应该怎么办呢？

如果我们随机取一个样本点，并且用这个样本点直接代表$L(h)$，我们的计算量就只有这些点了，对吧？其实这种方法是有一定道理的，因为
$$E(\nabla L^{\prime })=\frac{1}{n}\sum f_i=\nabla L(h)$$
所以这种方法是无偏的。

假设我们随机采样$b$个点（这个值被称为批大小(batch size)），并且定义损失函数为
$$\hat{\nabla }L(h)=\frac{1}{b}\sum _i{f}_i$$

也就是说，当$b=n$时，这种方法是GD（梯度下降法）；当$b=1$时，这种方法是SGD（随机梯度下降法）。

随机取一个训练样本是有风险的，估计出来的模型可能是不准确的，而且一般需要更多的迭代步骤。但是如果$n$数量过大，这种开销比起每步计算$n$次要好上很多。这是一个方差和时间的权衡。

Matrix Acceleration 矩阵加速计算

我们将变量看作一个矩阵$\begin{array}{c}{\mathbf{x}}_1\\ {\mathbf{x}}_2\\ ...\\ {\mathbf{x}}_{\mathbf{n}}\end{array}$，这是一个$n\times d$矩阵，然后和$d\times 1$模型向量$\mathbf{h}相乘$得到最终结果$\mathbf{y}$，我们要计算$\min ||\mathbf{X}\cdot \mathbf{h}-\mathbf{y}|{|}^2$。

其实上述矩阵有一个近似解${{\mathbf{X}}^{\mathbf{T}}\mathbf{X}}^{-1}\mathbf{y}$，但是在$n$非常大的时候，求矩阵的转置和逆一样非常的麻烦，怎么办呢？

我们可以先找一个$b\times n(b<<n)$的稀疏矩阵$\mathbf{S}$，然后用$\mathbf{SX}$代替原来的$\mathbf{X}$，这样我们就把前面的矩阵变成了一个小得多的$b\times d$矩阵，这个小矩阵求转置和逆就轻松多了。

这种方法和SGD有异曲同工之妙，矩阵$\mathbf{S}$类似于一种随机采样矩阵，计算出来的$b\times d$矩阵就好像从$n$个样本点中采样$b$个。

Feedforward Neural Network 前馈神经网络

前馈神经网络是一种最简单的神经网络。他的结构是一个分层图，每层有节点，每层节点和下一层的节点之间有加权的边连接。如下图所示：

对于每层的节点，我们将所有的输入边加权作为总的输入，然后处理则使用一个非线性的函数得出本节点的输出，这个函数被称为激活函数。激活函数在不同的情况下一般不同，但是有一种比较常见的函数叫做整流线性单元(ReLU)函数，另外一种函数叫做Sigmoid函数。

OK，根据上面的说法，神经网络包含输入，加权，和每个节点的处理。关于输入和处理我们都给出了具体的例子，但是我们仅仅通过SGD减少了计算的样本数量，并没有实际的加快梯度的计算。这就是我们下节课要介绍的方法：反向传播(Back Propagation)。