线性模型

机器学习(Machine Learning)是指面对一个特定问题，我们不直接给出特定的算法，而是通过某种方式让计算机自身获得一个解决这个特定问题的算法的编程模式。机器学习面对的问题主要有两种，一种称为监督学习(Supervised Learning)，一种称为非监督学习(Unsupervised Learning)。监督学习本质上是函数的拟合，对于数据集中的每个样本我们已知它对应的答案是多少，我们通过训练得到一个函数，这个函数可以对在样本中没有出现的输入给出输出。手写数字识别、预测房价等等都属于监督学习。其中，监督学习主要分为回归问题(Regression)和分类问题(Classification)，前者是要预测一个实数值，后者是将样本分为有限分类中的一类。另一方面，非监督学习的数据集是没有相应的输出的，训练的目的是发现数据集本身具有的特征。例如，聚类问题(Clustering)就是非监督学习问题，它希望把样本分成几个不同的类。例如，网站上相关内容的推荐算法就可以看作是聚类问题。

线性回归(Linear Regression)

我们首先来考虑监督学习中的回归问题，其中最简单的回归问题就是线性回归：对于\(n\)个用于训练的数据点（分别对应着\(p+1\)维空间中的一个坐标\((x_{i1},\cdots,x_{ip},y_i)\)，其中\(x_{i1},\cdots,x_{ip}\)是输入，\(y_i\)是输出。）我们要找到一个函数\(f_{\beta}(x)\)来拟合训练的数据集。在线性回归中，我们假定\(f\)是一个线性函数。换言之，我们只用线性的模型来考虑这个拟合问题。这样，寻找\(f\)就是寻找\(p+1\)个系数\(\beta_0,\beta_1,\cdots,\beta_p\)，令\(f_\beta(x)=\beta_0+\beta_1x_{i1}+\cdots+\beta_px_{ip}\)即可。为了方便起见，我们给输入增添上常数\(1\)来构成\(p+1\)维向量\(x_i=(1,x_{i1},\cdots,x_{ip})\)，这样就可以把\(f\)用向量形式写作\(f_\beta(x_i)=\beta\cdot x_i\)。

如何来判断\(f_\beta\)好不好呢？在机器学习中，我们定义一个代价函数(Cost Function)来定量刻画拟合函数的优劣，希望代价函数越小说明拟合越成功。在线性回归中，我们常用“误差平方和”作为代价函数：\(J(\beta)=\dfrac{1}{2}\sum\limits_{i=1}^{n}(f_\beta(x_i)-y_i)^2\)。代入\(f_\beta(x_i)=\beta\cdot x_i\)得到\(J(\beta)=\dfrac{1}{2}\sum\limits_{i=1}^{n}(\beta\cdot x_i-y_i)^2\)。这是一个关于\(\beta\)的二次函数，因此是一个凸函数，我们可以用梯度下降求出最小值。在梯度下降中我们做计算：\(\dfrac{\part J}{\part \beta_j}=\dfrac{1}{2}\sum\limits_{i=1}^{n}\dfrac{\part}{\part \beta_j}(\beta\cdot x_i-y_i)^2\)\(=\sum\limits_{i=1}^{n}(\beta\cdot x_i-y_i)x_{ij}\)，因此我们的训练就是做迭代\(\beta'=\beta+\alpha \sum\limits_{i=1}^{n}(y_i-\beta\cdot x_i)x_{i}\)，其中\(\alpha\)称为学习率(Learning Rate)。我们看到，梯度下降的步长正比于整体的误差\(\sum\limits_{i=1}^{n}(y_i-\beta\cdot x_i)\)，因此称为批量梯度下降(Batch Gradient Descent)。我们也可以把迭代分\(n\)次执行，每次只做\(\beta'=\beta+\alpha(y_i-\beta\cdot x_i)x_i\)，这时步长正比于\((y_i-\beta\cdot x_i)\)，可见每次我们是针对某一个样本点做优化，这个算法称为随机梯度下降(Stochastic Gradient Descent)。随机梯度下降的每一步迭代也都会让代价函数更小，在实践中当训练样本集很大时，随机梯度下降一般会更常用。

事实上，这个误差恰好是最小二乘法做线性拟合的误差函数，因此我们也可以选择不用梯度下降而直接代入最小二乘法的结论求出最优的\(\beta\)。设\(X=\begin{bmatrix}x_1^\top \\\vdots\\ x_n^\top\end{bmatrix}\)，\(y=\begin{bmatrix}y_1\\\vdots\\y_n\end{bmatrix}\)，有\(\beta=(X^\top X)^{-1}X^\top y\)。这个方法在数分课的多元函数微分学与线性代数课的正交性中我们都推导过。

为什么选择误差平方和作为代价函数呢？我们可以在一个概率假设下来解释这种选择。对于线性回归，假设对于样本集\(X\)我们选定了系数\(\beta\)，我们第\(i\)个样本点上的预测误差为\(\epsilon_i=y_i-\beta\cdot x_i\)。如果我们假设\(\epsilon\)总是独立同分布地满足正态分布的，即\(\epsilon_i\sim \mathcal{N}(0,\sigma^2)\)，于是有density \(p(\epsilon_i=a)=\dfrac{1}{\sqrt{2\pi}\sigma}e^{-\frac{a^2}{2\sigma^2}}\)。那么在给定\(X,\beta\)时，模型恰好预测出\((y_1,\cdots,y_n)\)的概率密度就是\(L(X,\beta)=\prod\limits_{i=1}^{n}\dfrac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(y_i-\beta\cdot x_i)^2}{2\sigma^2}}\)，这称为我们预测的似然函数(Likelihood Function)。我们希望模型预测正确的概率尽量大，因此也就要最大化似然函数。这个方法称为最大似然估计(Maximum Likelihood Estimate)。对\(L(X,\beta)\)取对数，有\(\ell(X,\beta)=\log L(X,\beta)=n\log \dfrac{1}{\sqrt{2\pi}\sigma}-\dfrac{1}{2\sigma^2}\cdot \dfrac{1}{2}\sum\limits_{i=1}^{n}(y_i-\beta\cdot x_i)^2\)。这等价于最小化\(\dfrac{1}{2}\sum\limits_{i=1}^{n}(y_i-\beta\cdot x_i)^2\)，这正是代价函数\(J(\beta)\)。

逻辑回归(Logistic Regression)

接下来我们来考虑监督学习中的分类问题。作为最简单的分类问题，我们考虑二分类，也即对于输入\(x_{i1},\cdots,x_{ip}\)，输出只有\(y_i\in {0,1}\)两种情况。此时我们应该选择怎么样的模型来拟合这样非连续的数据点呢？

一个最简单的想法是，我们只在空间\(\R^p\)中选取一个平面（等价的，一个带有截距的方向向量\(\beta\)）从而把空间分为两个半空间，就以此作为分类的依据。那么写出函数\(f(x,\beta)=\mathbb{1}[x_i^\top \beta>0]\)：对于一侧的点，它们全都满足\(X_i^\top \beta>0\)，这时我们就认为它们属于\(y_i=1\)的一类；对于\(X_i^\top\beta<0\)的一侧，我们就认为它们属于\(y_i=0\)的一类。这个模型就是感知机(Perceptron)。很显然，大多数情况下是不能仅由一个平面来对样本点做分类的。但是如果数据确实是呈现以某个分界面为界在两侧分布的，感知机就能取得良好效果。

如何为感知机中的分离平面\(\beta\)设计一个代价函数呢？如果继续使用线性回归中的误差平方和函数\(J(\beta)=\sum\limits_{i=1}^{n}(f(x,\beta)-y_i)^2\)，我们发现这并不再是一个凸函数了，而且事实上也无法良好刻画误差。一个最常用的解决方法称为逻辑回归，它通过引入概率后把问题转化为了线性回归，取得了良好的效果。

在逻辑回归中，我们希望\(f\)把\(x_i\)映射到某个实数\(p_i\in [0,1]\)，令\(p_i\)表示模型预测的\(y_i=1\)的概率。当\(p_i\)接近\(1\)时，我们把它分类为\(1\)；当\(p_i\)接近\(0\)时，我们把它分类为\(0\)。当实际做分类时，我们可以选定一个分界线，比如\(0.5\)。当\(f(x_i)>0.5\)时，我们就返回1；当\(f(x_i)<0.5\)就返回0。经验表明，选取\(f(X_i)=\dfrac{1}{1+e^{-x_i^\top \beta}}\)是好的。其中，\(g(z)=\dfrac{1}{1+e^{-z}}\)称为sigmoid函数，它形如一个\(S\)形分布在\([0,1]\)值域上。可以看到，要求\(f(x_i)\)大于某个值本质上就是在要求\(X_i^\top \beta\)大于某个值，因此实际上我们还是在做一个感知机，因为我们的模型本质上只是在选取一个分离平面。然而有了\(f\)以后，我们就有了一个简洁的定义代价函数的方法：假如\(y_i\)的真实值为\(y_i^*\)，那么由于我们把\(p_i\)看作了概率，“预测正确的概率”就可以写作\(p_i^{y_i^*}(1-p_i)^{1-y_i^*}\)，因为当\(y_i^*=0\)时它就取\(1-p_i\)，\(y_i^*=1\)时它就取\(p_i\)。代入sigmoid函数，\(p_i=\dfrac{e^{x_i^\top \beta}}{1+e^{x_i^\top\beta}}\)，得到\(p_i^{y_i^*}(1-p_i)^{1-y_i^*}=\dfrac{e^{y_i^*x_i^\top \beta}}{1+e^{x_i^\top \beta}}\)。可见整体全部预测正确的概率，也即逻辑回归的似然函数\(L(\beta)=\prod\limits_{i=1}^{n}\dfrac{e^{y_i^*x_i^\top\beta}}{1+e^{x_i^\top \beta}}\)。其对数形式是\(\ell(\beta)=\sum\limits_{i=1}^{n}\left[y_i^*x_i^\top \beta-\log(1+e^{x_i^\top \beta})\right]\)。相应的，预测错误的概率就可以表示为\(1-\ell(\beta)\)。

因此我们令代价函数：\(J(\beta)=-\ell(\beta)\)。这是关于\(\beta\)是一个凸函数！我们依然可以用梯度下降来求最小值。\(\dfrac{\part J}{\part \beta_j}=-\sum\limits_{i=1}^{n}\left[y_i^*-\dfrac{e^{x_i^\top \beta}}{1+e^{x_i^\top \beta}}\right]x_{ij}=-\sum\limits_{i=1}^{n}(y_i^*-p_i)x_{ij}\)，因此批量梯度下降的迭代公式就是\(\beta'=\beta+\alpha\sum\limits_{i=1}^{n}(y_i^*-p_i)x_i\)，相应地随机梯度下降的迭代公式是\(\beta'=\beta+\alpha(y_i^*-p_i)x_i\)。可见，梯度下降的步长正比于误差\((y_i^*-p_i)\)，这一形式与线性回归是完全相同的，依然是一种“从错误中学习(learn from mistakes)”。

这一相似性不是巧合，如果我们将\(f(x_i)=p_i=\dfrac{1}{1+e^{-x_i^\top\beta}}\)变形为\(x_i^\top\beta=\ln \dfrac{p_i}{1-p_i}\)。其中，\(\ln\dfrac{p_i}{1-p_i}\)称为logit函数，是\([0,1]\)到\(\R\)的单射。逻辑回归本质上是对\(x_i\)的一种线性拟合，使得实数可以对应某个概率，并使得这个概率尽可能地接近带有监督的样本\(y_i\)。而由于sigmoid函数中代入的是线性项\(x_i^\top \beta\)，这只不过是选取了一个分离平面罢了。如果将\(x_i^\top\beta\)替换为非线性的函数\(\phi(x_i)\)，那么分离面就可以拓展为曲面，而这就不能称为逻辑回归了，此时的代价函数可能不再是凸的，在求解\(\beta\)时可能会遇到诸多困难。

正则化(Regularization)

当我们用数据集训练出我们的模型时，我们可能会发现模型过拟合(Overfitting)了。例如对于一个\(n\)个点的样本集，我们总是可以用一个\(n-1\)次函数使得它能够精确穿过所有样本点，然而这样训练得到的模型是没有价值的，拟合的结果过于奇怪以至于它没有预测的价值。

为了解决过拟合问题，常见地有以下几种策略：第一，我们可以增加样本，扩大样本集的规模，这一定程度上总是可以使模型有更好的预测能力的。当然，这有时可能是难以实现的。第二，我们可以删掉我们用来训练模型的输入数据的某些维度，例如在房价预测中面积、房间数等等比较重要，而长度、宽度这些feature就不那么重要，可以提前删除来防止过拟合。第三，我们可能并不需要真的删除一些feature，而是让某些feature的参数的取值不能过大而足以影响整个函数的形态，这称为正则化。

我们可以修改代价函数来实现正则化。例如，假如我们挑选出了\(m\)个我们不希望它对函数产生较大影响的维度，那么我们就在代价函数中加上\(\dfrac{\lambda}{2m}\sum\limits_{i=1}^{m}\beta_i^2\)这一项。由于我们要最小化代价函数，因此新增的一项就保证了每个\(\beta_i\)都不会有过大的取值（软约束）。调整系数\(\lambda\)的大小，我们可以获得不同程度的对\(\beta_i\)大小的限制。在线性回归（或逻辑回归）中，正则化后的代价函数就写作\(J(\beta)=\dfrac{1}{2n}\sum\limits_{i=1}^{n}(X_i^\top \beta-y_i)^2+\dfrac{\lambda}{2m}\sum\limits_{i=1}^{m}\beta_i^2\)。我们发现，在梯度下降中，\(\nabla J(\beta)=\dfrac{1}{n}\sum\limits_{i=1}^{n}(X_i^2\beta-y_iX_i)+\dfrac{\lambda}{m}\beta\)。设梯度下降的步长为\(\alpha\)，那么有了新的项以后\(\beta\)每次还会新迭代一次\(\beta\to\beta-\dfrac{\alpha\lambda}{m}\beta\)。这相当于把\(\beta\)的每一维系数大小都缩减了一个系数\(1-\dfrac{\alpha\beta}{m}\)，可见我们通过梯度下降的迭代次数控制着\(\beta\)系数的大小。