写在前面

因为看的是英文版所以不能准确翻译的请见谅。

先说记号，指输入features，指输出或目标值target，一对(, )是一个训练样本training example，训练集training set则是这样的i对样本组成的集合。

对于一个监督学习算法，他的目的是通过一个训练集学到一个方程，输入一个x得到一个比较接近真实的y的预测prediction，这个方程 h 被成为一个猜测hypothesis，这个过程图示为：

当我们要预测的是连续数值，就称这个问题为线性回归linear regression，当预测结果是离散的，就是分类问题classification了。

---

Part1:线性回归

对于一个线性回归的预测我们有如下形式：

在这里是参数parameter（亦可称作权制weight），为方便以后都用h(x)来表示，同时为了简化这一表示方法，增加x0=1这一项之后可以化为：

在这里theta和x都是向量，d代表特征数量。

为了考量h(x)的预测是否符合真实情况即y，引入代价函数cost function：

这与统计线性回归的普通最小二乘不谋而合，对于算法来说，目标就是减小这一代价函数值。

---

1.最小均方差算法LMS

正如前面所说，我们想在选择各theta值时尽量明智，使得预测值尽量接近实际值。为了达到这个目的我们可以设定初始值，并不断改变各theta的值使得越来越小，然后祈祷它最后收敛到一组theta使得到达最小值。在这里我们特别使用梯度下降算法gradient descent algorithm，在这个算法中我们先设定theta们的初值，然后重复以下更新算法：

在这个更新规则中，所有的theta（j=0,1,...,d）会在同一时间一起更新，而alpha在这里指学习速率leaning rate。

鉴于我们已经有的函数方程了，为了部署更新算法，我们需要求出的偏导数。我们先假设我们只有一对训练样本x和y，其偏导数计算结果是：

这样我们就有了更新规则：

这一更新规则我们称为最小均方差更新规则。

现在我们可以把这一规则推广到有多个样本的训练集的情形，这里有两种办法来应用LMS更新规则到多样本训练集，第一种是替换为如下算法：

重复直至收敛：{

}

这个算法每次计算都会访问所有数据一次，称为批量梯度下降法batch gradient descent。注意梯度下降会对局部最小值很敏感，而在我们的线性回归问题中只有一个整体最优解而没有其他局部最优解，所以梯度下降总会收敛至整体最优解。并且J也是一个二次凸函数，下图是一个线性回归例子执行时的轨迹：

另一种算法也可以很好的完成这一任务：

这个算法会一个训练样本一个训练样本读取，每次更新只根据一个训练样本，称为随机梯度下降法stochastic gradient descent。对比两个算法会发现批量梯度下降每次会扫描所有的训练样本，对数据集大小很敏感。而随机梯度下降会挨个访问，适合于大型的数据集。而且大部分情况下随机梯度下降会比批量梯度下降更快地接近最小值（注意随机梯度下降可能不会收敛而会在最小值附近“晃悠”，但是在实际应用中这个结果已经足够精确了），所以通常更推荐随机梯度下降法。

---

2.正规方程  The normal equations

梯度下降法给出了最小化J的一个方法，这次我们给出一个直截了当不经过任何递归与循环求出最小值的方法。为了更好地介绍这一方法我们先介绍一些线性代数的记号。

2.1 矩阵导数 Matrix deriatives

对于一个从n*d的矩阵映射到实数的方程f，我们定义f关于矩阵A的导数是：

所以这个本身也是一个n*d的矩阵，它的第(i,j)个元素是。

2.2 重提最小二乘

根据这个矩阵导数，我们现在有了更好的办法去计算能最小化的theta值。

给出一组训练集，定义一个n*d的设计矩阵X（其实是n*d+1，算上x0那项的话），这个矩阵包含了所有训练集的输入，每行都是一个训练样本的输入：

并且让作为所有目标值的n维的向量：

由于有：

所以：

对于一个向量z，有，所以：

最后，为了最小化J，让我们求出它的导数：

在推导过程的第三步，我们使用了规则aTb=bTa，在第五步运用了在对称矩阵中的事实和。

为了最小化J，我们令这个导数为0，就得到了正规方程：

所以能使J取得最小值的theta的解析解为：

以上。