手机端网站优化_b2b模式的企业例子_高端网站建设企业_营销案例100例小故事及感悟

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 \R^d$ ，d指的是特征数，而 $y_c \in \R$ 是标签值(label)。

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

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

Linear Classification 线性分类

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

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

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

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

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

因此我们得到训练集：
$(x_1,0),(x2,1),\dotsb$
其中标签值为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)$ 和损失函数 $\frac{1}{n}\Sigma(<x_i,h> - y_i)^2$ ，
模型生成之后我们给出测试集 $x *$ ，模型给出预测值 $y *$ 。损失函数计算预测值和实际值的垂直距离，使得模型可以持续优化。

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

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

选择初始点 $h_0$ ，步数 $T$ 和学习率 $\eta$ 。
在每步迭代中，计算当前点的梯度，并且迭代点 $h_{i+1} = h_i -\eta \nabla L(h)$
最后输出 $\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$ ，那么有
$\frac{df_i}{dh_j} = \frac{df_i}{dz}\frac{dz}{dh} \\ \frac{df_i}{dz} = 2z \\ \frac{dz}{dh} = x_{i,j}$
因此
$\frac{df_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},\dots>$

Overfitting 过拟合

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

过拟合

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

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

Ridge Regression 岭回归算法

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

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

Stochastic Gradient Descent SGD 随机梯度下降

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

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

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

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

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

Matrix Acceleration 矩阵加速计算

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

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

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

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

Feedforward Neural Network 前馈神经网络

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

神经网络节点

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

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