监督学习与非监督学习
机器学习是指给定一些训练数据，使机器能够利用它们分析未知数据。任何机器学习问题都可以分为两类：监督学习(Supervised Learning)和非监督学习(Unsupervised Learning)。这两类的区别在于：监督学习的训练数据有特征有标签，而非监督学习的训练数据没有。
监督学习问题一般是指给定输入预测输出，根据输出值的不同可以分为两类：回归(regression)和分类(classification)。回归预测的是连续值，分类预测的是离散值。
举例来说，给定房子的面积来预测房价是一个回归问题，因为房价是个连续值。如果把它改成预测房价是否超过某个阈值，那么这是一个离散问题，因为输出是个“是”或“否”的离散值。同理，给定一个人的图片预测TA的年龄是个回归问题，预测TA的性别是个分类问题。
而非监督学习问题在给定输入时，不知道预测的结果长什么样子，我们是从一堆数据里推导出其中的结构。
非监督学习最常见的应用是聚类(clustering)。举例来说，给定《美国经济》的1000篇文章，按照不同主题进行自动分类。另一个非聚类的典型例子是鸡尾酒会效应，指的是在一个嘈杂的鸡尾酒会环境中谈话中，尽管周围噪音很多，你仍能分辨出朋友对你说话的声音。
线性回归
让我们先从监督学习中最简单的一个问题开始，假设我们有一个数据集如下，我们假设房价受住房面积的影响。
| 住房面积(英尺2) | 房价(1000$) |
|---|---|
| 2104 | 400 |
| 1600 | 330 |
| 2400 | 369 |
| 1416 | 232 |
| 3000 | 540 |
| ... | ... |
我们的目标是对给定数据集学习出一个函数h: x → y，使得对每个输入x，h(x)都能很好的预测出输出y。由于历史原因，我们把h称为假设函数(Hypothesis Function)。下图描述了这一过程：
我们需要对假设函数进行建模，最简单的方式是将它视为线性函数，因而可表示成：
其中θi称之为参数(parameter)或者权重(weight)。为了简化表述，我们定义θ0=1，那么：
其中最右面等式中的θ和x都是向量表示，n是输入变量的个数（在这个例子中n=1）。
那么我们应该如何选取θ，使得h(x)和y的误差最小。为此我们定义代价函数(cost function)如下：
其中x(i)这种上标表示方式是指第i个训练集的输入数据，y(i)是第i个训练集的输出值，m是训练集的个数。
梯度下降算法
引入了代价函数后，我们的目标变成了：选择合适的θ，使得J(θ)最小。在这方面我们主要介绍梯度下降算法(Gradient Descent)。这个算法的主要思想是先选取一个初始点θ0，然后不断改变θ的值使得J(θ)变小，直到J(θ)收敛到最小值。特别的，为了使J(θ)变得最小，我们选择下一个θ值时应该选择能使J(θ)下降最快的那个值，在数学上就是对J(θ)求导，具体来说下一个选取的θ值就是：
其中α是学习率(learning rate)，它会影响梯度下降的幅度。在每次迭代中，可以选取不同的α值。下图是梯度下降算法的图示，在选取初始点后，每次都按下降速率最快的方式寻找下一个点，直到找到最低点。
我们将J(θ)展开进行推导，由此得到：
因而迭代规则更新为：
这个规则被称为最小均方算法(Least Mean Squares，缩写为LMS)或者Widrow-Hoff算法。
这个算法在每次迭代时都要计算一遍训练集的数据，因而被称为批量梯度下降法(Batch Gradient Descent)。当训练集数据量很大时，计算速度将变得很慢。为了解决这个问题，我们可以在每次迭代时随机选取训练集数据的一部分来代替整体，这种方法称之为随机梯度下降法(Stochastic Gradient Descent)。随机梯度下降法由于只选取了部分样本数据，因此迭代过程会比较不稳定，虽然每次迭代不一定按着全体最优解靠近，但整体上趋于全体最优解。
正规方程
梯度下降法求解的缺点是需要很多次迭代，是否存在更好的方法呢。正规方程(Normal Equation)就是一个不需要进行迭代就能求解的方法，其公式如下：
其中X和y定义如下，XT是矩阵X的转置。
这个公式证明需要大量线性代数的知识，详细证明可以查阅参考资料。下表给出了梯度下降和正规函数两个算法的对比。
| 梯度下降 | 正规函数 |
|---|---|
| 需要选择学习率α | 不需要选择学习率α |
| 需要很多次迭代 | 不需要迭代 |
| O(kn2) | O(n3)，需要计算XTX的逆矩阵 |
| n很大时也能正常工作 | n很大时计算很慢 |
在实践中，当n>=10000时不适合用正规函数，推荐改用梯度下降算法。
另外正规方程还有一个问题，就是XTX可能是不可逆的。不可逆的可能原因是我们使用了冗余的特征(比如两个特征线性相关)或者使用了太多的特征(比如特征数超过了样本数)。解决方法是删除一些多余的特征。
总结
- 机器学习问题可以分为监督学习和非监督学习，区别在于训练数据是否有特征
- 监督学习问题根据预测值的不同分为两类：预测值是连续值的叫回归，预测值是离散值的叫分类
- 最简单的回归模型是线性回归，求解线性回归的两个方法是：梯度下降和正规方程
- 当训练数据量较大时(n>=10000)时推荐用梯度下降，数据量较小时用正规函数
