程序员的机器学习笔记－第三篇 线性回归

        前三篇笔记介绍了机器学习的一些基本概念以及理论基石，从这篇笔记开始我们就进入到具体的一个个模型的学习了。其实关于理论和概念还有很多内容没有介绍到，但是不结合具体的模型来谈这些概念和理论的话总觉得有点泛泛，所以后面将结合着模型来介绍某些概念和理论。

        在这篇笔记里介绍我们的第一个也是最简单的一个模型：线性回归模型。线性回归模型是线性模型的一种，我们在前面的笔记中说到过“模型决定了假设空间”，线性模型就是指假设空间是特征的线性函数的一类模型。线性模型的基本形式是：

        给定由d个特征描述的示例𝒙 = (x1; x2; ... ; xd)，其中，xi是𝒙在第i个特征上的取值，线性模型试图学得一个通过特征的线性组合来进行预测的函数，即

也可写成向量形式：

其中𝒘= (w1; w2; ...; wd)。通过学习算法学到𝒘和b后，模型就确定了。

        线性模型应该是我们会介绍的模型中的最简单且最古老的模型了，它一般只会在各种教材中会单独作为主角登场，在实际项目中它几乎没有单独出场的机会。但是它的确又是很重要的一类模型，它甚至是很多复杂模型的基础，比如支持向量机、神经网络等模型中都有线性模型的身影。如果在机器学习模型圈评选奥斯卡最佳配角奖，那非线性模型莫属了。

        线性模型大体可以分为线性回归模型和线性分类模型，这篇笔记只介绍线性回归模型，在以后的笔记中会介绍线性分类模型。下面先介绍一下回归的概念。

一、什么是回归？

百度搜索回归，可以看到如下的解释：

回归，指研究一组随机变量(Y1 ，Y2 ，…，Yi)和另一组(X1，X2，…，Xk)变量之间关系的统计分析方法，又称多重回归分析。通常Y1，Y2，…，Yi是因变量，X1、X2，…，Xk是自变量。

        我不知道大家在看到这个解释的时候是什么感觉，我自己第一次看到这个词时是感觉到疑惑的：为什么这种统计分析方法要叫回归，而不叫其他的？而对于机器学习的另一个问题“分类”，相信大家和我一样看到“分类”这个词就能对这个分类问题有个基本的认知。直到后来看到了AIMA（参考文献一）中介绍的亚里士多德提出的一个算法时我才明白了为什么这种方法叫回归。AIMA中的原文：

亚里士多德主张通过目标与行动结果的知识之间的逻辑关系来证明行动是正当的……<省略>……并进一步提出了一个算法：

我们要深思的不是结果，而是手段。因为医生不会深思病人是否会治愈，演说家也不会深思他是否会说服听众，……他们假设了结果并考虑如何以及通过什么手段来获得该结果，他们还要考虑手段是否容易实现，从而产生最好的手段；当只有一种手段来达到结果时，他们会考虑如何根据这种手段来达到结果，以及通过什么手段来实现这种手段，直到他们得到第一原因，……在分析序列中最后出现的手段在实现序列中似乎是第一个手段。如果我们碰到了不可能实现的事情，例如，如果我们需要金钱而又得不到，那么我们就放弃搜索；但是如果一件事情看似可能，我们就尝试着去做。

        亚里士多德的算法在2300年后被纽厄尔河西蒙实现在他们的“通用问题求解器”程序中。现在称其为回归规划系统。

        从亚里士多德的算法中我们可以看到它蕴含着一种“由果寻因”的思想，即，由结果出发如何一步一步逆推达到这个结果所需要的手段。

        这个过程就是regress，我们看到现在所说的回归，即regression，这个单词本身就有逆行或更通俗的“倒推”的意思。所以，如果在中文中我们不是使用“回归”而是使用“倒推”那么我们就也能和“分类”一样见名知义了。

        顺便提一下，对于什么是“回归”什么是“分类”有一种普遍的说法是：“对连续型变量做预测叫回归，对离散型变量做预测叫分类”。这种说法在遇到logistic回归时就不太适用了，因为logistic回归实际上解决的是分类问题，这种说法显然不具有普适性。而logistic回归的得名应该是这种方法在建模时也是应用了回归的思想（由果寻因）。

        了解了回归的思想那么具体地，在数据分析的时候回归究竟是怎么做的呢？接下来我以最简单的线性回归为例来介绍在数据分析时“回归”思想的具体应用。

二、线性回归

线性回归模型属于监督学习，其训练数据集的形式为

线性回归的任务是找到一个从特征空间X到输出空间Y的最优的线性映射函数，我们先从最简单的单变量线性回归说起。

单变量线性回归

        在单变量线性回归中，输入特征的数目只有一个，训练数据集可表示为：

        在之前的笔记中曾提过，机器学习方法的三要素，即模型、策略和算法，下面我们从这三要素的角度来分析一下单变量线性回归方法。

        模型：

        线性回归假设数据集中每个yi和xi之间存在一种线性关系，针对这种未知的线性关系可以提出如下的假设函数h(x)：

        上式中对于每一个不同的w0和w1都对应了一个不同的假设函数h，那么所有可能的h就构成了线性回归模型的假设空间H。

        策略：

        有了假设空间，接下来我们需要找出一种策略来衡量假设空间中各个假设函数的优劣。机器学习中策略一般是某种损失函数，最优的假设函数有最小的损失，后面的算法要做的就是找出使损失函数具有最小值所对应的那个假设函数即可。

        那么，问题来了，如何定义这个损失函数呢？我们在前面讲PAC理论的笔记中提到过“经验误差越小往往泛化误差也会越小”（对于单变量线性回归不用担心过拟合问题，对于多变量的情况即便考虑过拟合，经验误差最小也是学习算法应该努力保证的），所以这个损失函数如果能反映出假设函数在训练数据集上的误差，并且误差越大损失函数值越大误差越小损失函数值越小的话，那么选取最优假设就方便了，损失函数越小其对应的假设函数就越好。那么自然的，我们就会想到可以使用假设函数在整个训练集上与真实值之间差距来作为损失函数，即，损失函数具有如下的形式：

        上式中的L(yi, h(xi))是对于样本(xi, yi)假设函数的预测值h(xi)和真实值yi之间的差距。对于这种差距我们可以想到很多种计算形式，比如：

        L(yi, h(xi)) = yi - h(xi)                  (1)

        L(yi, h(xi)) = |yi - h(xi)|               (2)

        L(yi, h(xi)) = (yi - h(xi))^2           (3)

        在机器学习中最常使用第三种也就是平方函数来计算损失。因为(1)式中正负损失加总后会互相抵消，(2)式中绝对值函数不是连续可导函数求解不方便，而(3)式是凸函数存在全局最优值而且求解方便。（关于凸函数的定义可以自行百度，机器学习中基本上所有的算法都致力于把最后的问题转换为一个凸优化问题，因为现在对于凸优化问题的求解是很成熟的，凸优化问题可以查看参考资料4，当然也可以不看，对于程序员来说去了解凸优化意义不是很大，列在这里仅供感兴趣的童鞋参考）

        于是，对于单变量线性回归我们的损失函数的定义就出来了：

        因为很多其它资料中都是实用J作为损失函数的记号，另外h是由w0和w1的决定的，所以这里使用J(w0, w1)来代替Loss(h)的记号。在上式右边除以2是为了计算方便，我们在后面的算法中可以看到这个2可以抵消求偏导时产生的2，另外除以m表示我们采用的是均方误差。其实有的书中也不除2m，比如参考资料1和2，对计算结果没有影响。

        把h(x)带入到这个损失函数，可得：

        算法：

        有了损失函数后我们要做的就是依据损失函数寻找最优的假设函数，也就等价于求解下面的最优化问题：

        上式中左边带*号的w0和w1是右边成立时，即在J(w0, w1)取最小值时，对应的w0和w1的值。

        对于上面的最优化问题的求解，我们只需将(4)式分别对w0和w1求偏导，然后令导数为0求出w0和w1即可得到w0和w1的解析解。

令（5）和（6）式为0，解得w0和w1：

多变量线性回归

        单变量线性回归的情况很容易扩展到多变量的情况。在多变量线性回归中每一个输入有多个属性，即xj=(xj1, xj2, ..., xjd)，其模型变为：

为了统一形式，我们引入一个哑输入属性x0，并令x0恒等于1。于是，上式可写为如下形式：

将其写成矩阵形式，可得下式：

        上面的式子都是对于一个输入x而言的，对于训练数据集中所有的m个输入，我们引入哑属性后，数据集中的属性应该是如下的形式：

        x1=(1, x11, x12, ..., x1d)

        x2=(1, x21, x22, ..., x2d)

        x3=(1, x31, x32, ..., x3d)

        ……

        xm=(1, xm1, xm2, ..., xmd)

可以用下面的矩阵X来表示数据集中所有的数据属性集合：

我们把所有的输出yj也写成向量向量形式：

在多变量的情况下损失函数为：

按照矩阵运算规则，将损失函数写为矩阵形式：

对W求导得：

令导数为0，可以解得解析解：

        至此单变量和多变量线性回归的情况就都讨论过了。

        上面给出了单变量线性回归和多变量线性回归的解析解（有的书上也称闭式解），可以看出这种解析解计算原理简单。但是，在实际情况中我们常常无法按令偏导数为0的方法求出解析解，这是因为要么损失函数没有解析解，比如损失函数不是处处可导的函数；要么求解解析解太耗时，比如特征空间维度太高。另外，在多变量的情况下我们也可以看出，求解解析解要求X转置乘X可逆，实际中这个条件不一定满足，而且即便能满足，当矩阵的维度很高时求解解析解也是极为耗时。所以我们常常只能使用数值计算的方法求取近似的数值解，梯度下降法就是常用的数值计算的方法。Andrew NG在其课程中曾说过，即便是解析解存在，当特征超过10000维时，他也会考虑使用数值解，因为求解解析解太耗时了。关于梯度下降算法将放在下篇笔记中说明。

        最后要说的是，单变量线性回归不必担心过拟合的问题，但是对于多变量线性回归我们需要考虑如何避免过拟合。实践中采用引入正则化项的办法来避免过拟合，关于正则化的内容也会在后面的笔记中说明。

参考资料：

1. Stuart J. Russelll《人工智能 一种现代的方法》

2. 周志华《机器学习》

3. Stephen Boyd《凸优化》