机器学习笔记1: 线性回归

监督学习与非监督学习

机器学习是指给定一些训练数据，使机器能够利用它们分析未知数据。任何机器学习问题都可以分为两类：监督学习(Supervised Learning)和非监督学习(Unsupervised Learning)。这两类的区别在于：监督学习的训练数据有特征有标签，而非监督学习的训练数据没有。

监督学习问题一般是指给定输入预测输出，根据输出值的不同可以分为两类：回归(regression)和分类(classification)。回归预测的是连续值，分类预测的是离散值。

举例来说，给定房子的面积来预测房价是一个回归问题，因为房价是个连续值。如果把它改成预测房价是否超过某个阈值，那么这是一个离散问题，因为输出是个“是”或“否”的离散值。同理，给定一个人的图片预测TA的年龄是个回归问题，预测TA的性别是个分类问题。

而非监督学习问题在给定输入时，不知道预测的结果长什么样子，我们是从一堆数据里推导出其中的结构。

线性回归

让我们先从监督学习中最简单的一个问题开始，假设我们有一个数据集如下，我们假设房价受住房面积的影响。

我们的目标是对给定数据集学习出一个函数h: x → y，使得对每个输入x，h(x)都能很好的预测出输出y。由于历史原因，我们把h称为假设函数(Hypothesis Function)。下图描述了这一过程：

我们需要对假设函数进行建模，最简单的方式是将它视为线性函数，因而可表示成：

其中θ_i称之为参数(parameter)或者权重(weight)。为了简化表述，我们定义θ₀=1，那么：

其中最右面等式中的θ和x都是向量表示，n是输入变量的个数（在这个例子中n=1）。

那么我们应该如何选取θ，使得h(x)和y的误差最小。为此我们定义代价函数(cost function)如下：

其中x⁽ⁱ⁾这种上标表示方式是指第i个训练集的输入数据，y⁽ⁱ⁾是第i个训练集的输出值，m是训练集的个数。

梯度下降算法

引入了代价函数后，我们的目标变成了：选择合适的θ，使得J(θ)最小。在这方面我们主要介绍梯度下降算法(Gradient Descent)。这个算法的主要思想是先选取一个初始点θ₀，然后不断改变θ的值使得J(θ)变小，直到J(θ)收敛到最小值。特别的，为了使J(θ)变得最小，我们选择下一个θ值时应该选择能使J(θ)下降最快的那个值，在数学上就是对J(θ)求导，具体来说下一个选取的θ值就是：

其中α是学习率(learning rate)，它会影响梯度下降的幅度。在每次迭代中，可以选取不同的α值。下图是梯度下降算法的图示，在选取初始点后，每次都按下降速率最快的方式寻找下一个点，直到找到最低点。

我们将J(θ)展开进行推导，由此得到：

因而迭代规则更新为：

这个规则被称为最小均方算法(Least Mean Squares，缩写为LMS)或者Widrow-Hoff算法。

这个算法在每次迭代时都要计算一遍训练集的数据，因而被称为批量梯度下降法(Batch Gradient Descent)。当训练集数据量很大时，计算速度将变得很慢。为了解决这个问题，我们可以在每次迭代时随机选取训练集数据的一部分来代替整体，这种方法称之为随机梯度下降法(Stochastic Gradient Descent)。随机梯度下降法由于只选取了部分样本数据，因此迭代过程会比较不稳定，虽然每次迭代不一定按着全体最优解靠近，但整体上趋于全体最优解。

正规方程

梯度下降法求解的缺点是需要很多次迭代，是否存在更好的方法呢。正规方程(Normal Equation)就是一个不需要进行迭代就能求解的方法，其公式如下：

其中X和y定义如下，X^T是矩阵X的转置。

这个公式证明需要大量线性代数的知识，详细证明可以查阅参考资料。下表给出了梯度下降和正规函数两个算法的对比。

在实践中，当n>=10000时不适合用正规函数，推荐改用梯度下降算法。

另外正规方程还有一个问题，就是X^TX可能是不可逆的。不可逆的可能原因是我们使用了冗余的特征(比如两个特征线性相关)或者使用了太多的特征(比如特征数超过了样本数)。解决方法是删除一些多余的特征。

总结

• 机器学习问题可以分为监督学习和非监督学习，区别在于训练数据是否有特征
• 监督学习问题根据预测值的不同分为两类：预测值是连续值的叫回归，预测值是离散值的叫分类
• 最简单的回归模型是线性回归，求解线性回归的两个方法是：梯度下降和正规方程
• 当训练数据量较大时(n>=10000)时推荐用梯度下降，数据量较小时用正规函数

参考资料

• Coursera机器学习课程讲义
• 斯坦福大学机器学习课CS229讲义
• 网易公开课：机器学习课程