机器学习笔记中文翻译

machine_learning

---

课程地址
https://www.coursera.org/learn/machine-learning

第一周

何为机器学习

两种定义：
“关于赋予计算机一种不需要显式编码的学习能力的研究领域”——来自Arthur Samuel的旧定义
“一个计算机程序可以从一些类别任务T和表现衡量P相关的经验E中进行学习，如果它在任务中的表现T，由P来衡量，随着经验E而完善。”——来自Tom Mitchell的更现代的定义
例子：玩西洋棋
E = 玩很多西洋棋的经验
T = 玩西洋棋的任务
P = 程序赢得下一盘游戏的概率

通常来说，任何机器学习问题都可以分为两大类：监督学习和无监督学习

监督学习

在监督学习中我们拥有一个数据集并已经知道正确的输出是怎样的，知道输入和输出之间有关系。
监督学习可以分为“回归”和“分类”问题。在回归问题中，我们尝试在连续输出中预测结果，意味着我们把输入变量映射到一些连续函数。在分类问题中，我们尝试以离散输出形式预测结果，把输入变量映射到离散类别中。

无监督学习

无监督学习允许我们解决不知道或者很少知道结果是怎样的问题。我们可以从数据中获得结构，在这些数据中我们不必知道变量的效果。
我们可以根据数据中变量的关系对数据进行聚集，来获得这个结构。
无监督学习没有根据预测结果的反馈，即没有老师来更正你。
分为聚类问题和非聚类问题（鸡尾酒派对问题）

单变量线性回归

模型表现

在回归问题中，我们用输入变量把输出值拟合到一个连续函数上。
单变量线性回归也叫“通用线性回归”。
当你想从一个单输入变量X预测一个单输出变量y的时候，通用线性回归就得到使用。
我们这时在做监督学习，所以这意味着我们已经知道输入输出的原因和效果应该是怎样。

假设函数

我们的假设函数有以下一般形式：

$$y = h_{\theta}(x) = \theta_0 + \theta_1 x$$
注意到这跟直线方程很相似。我们给$h_\theta(x)$以$\theta_0$和$\theta_1$值来得到我们的估计 输出$y$。换句话说，我们尝试创造一个叫$h_\theta$的函数来把输入数据（X）映射到输出数据（y）。

损失函数

我们可以用一个损失函数来衡量假设函数的精准性。
这采用所有从X的输入得到的假设结果与实际的输出y之间比较的平均值（实际上是一种更新奇的平均数版本）。

$$J(\theta_0,\theta_1)=\frac{1}{2m}\sum_{i=1}^m(h_\theta(x_i)-y_i)^2$$
分开来讲，$\frac{1}{2}x$，当$x$是$h_\theta(x_i)-y$的平方的均值，或者说预测值与实际值的差异。
这个函数也叫做“平方误差函数”(square error function)，或者“均值平方误差”(mean squared error)。该均值被对半分（$\frac{1}{2m}$），为了方便计算梯度下降，因为平方函数的导数项会把$\frac{1}{2}$消掉。
现在我们能够精确地衡量预测函数关于我们拥有的正确值的精确度，于是我们可以预测我们没有的新结果。

如果我们尝试从视觉角度来看，我们的训练数据集分散在x-y平面上。我们正尝试画一条直线（由$h_\theta(x)$定义），它穿过这个分散的数据集。我们的目标是得到最合适的直线。最合适的直线将会使得分散的点到直线的垂直距离的平方的的均值最小。在最好的情况下，这条线会穿过所有训练集中的点。在这中情况下$J(\theta_0,\theta_1)$的值是0。

梯度下降

现在我们有了假设函数和衡量它能多好地拟合数据的方法。现在我们需要估计假设函数中的参数。
这就是梯度下降的用武之处。
假想我们根据$假设函数的域\theta_0$和$\theta_1$画出来假设函数（实际上我们画出损失函数作为参数估计的函数）。这有点令人疑惑；我们开始更高层的抽象。我们不是在画x和y自身，而是假设函数的参数范围和选择特定参数集带来的损失。

我们把$\theta_0$放在x轴上，$\theta_1$放在y轴上，损失函数放在垂直的z轴上。图像上的点将会是随着那些特定的theta参数使用我们的假设得到的损失函数的结果。

我们都知道当我们的损失函数在图像的凹点的底部时我们就成功了，即当它的值最小时。

做到这个的方法是通过计算损失函数的导数（函数的切线）。切线的斜率就是那个点的导数，并给予我们移动的方向。我们沿着梯度最陡峭的方向一步步走下损失函数，每步 的大小由一个参数$\alpha$决定，叫做学习率。

梯度下降算法是：
重复直到收敛：

$$\theta_j:=\theta_j-\alpha\frac{\alpha}{\alpha\theta_j}J(\theta_0,\theta_1)$$
这里
j=0,1表示特征索引数字
直观地，这可以认为是
重复直到收敛：
$$\theta_j:=\theta_j-\alpha[j维度的导数][i维度的导数]$$

线性回归中的梯度下降

当应用到线性回归的情况时，一种新的梯度下降等式就衍生出来了。我们代替实际的损失函数和实际的假设函数，并把等式修改为

$$重复直到收敛:{\\ \theta_0:=\theta_0-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x_i)-y_i)\\ \theta_1:=\theta_1-\alpha\frac{1}{m}\sum_{i=1}^m((h_\theta(x_i)-y_i)x_i)\\ }$$

这里m是训练集的大小，$\theta_0$是随着$\theta_1$同步改变的常量，$x_i,y_i$是给定训练集的值。
注意到我们把两个关于$\theta_j$的情况分开成单独的关于$\theta_0$和$\theta_1$的等式；针对$\theta_1$由于导数我们在末尾乘了个$x_i$。

这里的要点是如果我们用一个假设而且随后不断重复应用这些梯度下降算法，我们的假设会变得越来越精确。

线性代数要点

记号和术语

• $A_{ij}$指的是矩阵A的i行j列的元素
• 一个有n行的向量称为n维向量
• $v_i$指的是向量第i行的元素
• 一般地，我们所有的矩阵和向量都是从1开始编号的。注意到有些编程语言的数组是从0开始编号的。
• 矩阵用大写字母表示，向量用小写字母表示
• 标量(scale)意味着一个对象是一个单独的值，不是向量或矩阵
• $R$指实数集
• $R^n$指n维实数向量的集合（编者按：准确来讲是向量空间）

加法和标量乘法

加法和标量乘法都是针对元素的,所以你可以简单地加或减每个对应元素。
加或减的两个矩阵的维度一定相等。
在标量乘法中，我们简单地把每个元素乘以标量值。

矩阵-向量 乘法

我们把向量的每一列映射到矩阵的每一行上，乘以每一个元素并把结果求和。
一个m*n矩阵乘一个n*1向量的结果是m*1向量。

矩阵-矩阵 乘法

两个矩阵相乘是通过把它分成几个向量乘法并把结果连在一起。
一个m*n矩阵乘一个n*o矩阵的结果是m*o矩阵。
两个矩阵相乘，第一个矩阵的列数等于第二个矩阵的行数。

矩阵乘法的性质

• 不满足交换律
• 满足结合律
• 单位阵是什么（省略）

逆阵和转置

一个方阵和逆阵相乘等于单位阵。
非方阵没有逆阵。
没有逆阵的矩阵叫奇异或退化(singular or degenerate)。
矩阵的转置就像把矩阵顺时针转九十度然后翻转。

第二周

多元线性回归

定义以下记号：

$$x_j^(i): 第i个训练例子的第j个特征的值 x^(i): 第i个训练例子的所有特征列向量 m: 训练例子个数 n: 特征数$$
向量形式$h_{\theta}(x) = \theta^{T}x$
一般来说，$X$以行向量形式储存每个训练例子，$\theta$是列向量，那么
$$h_{\theta}(X) = X\theta$$

损失函数

$\theta$是$R^{n+1}$的向量

$$J(\theta) = {1 \over 2m} \sum_{i=1}^m(h_{\theta}(x^{(i)}-y^{(i)})^{2}$$
向量版本是
$$J(\theta) = {1 \over 2m} (X\theta - y)^T(X\theta - y)$$

多元梯度下降

$$重复直到收敛:{ \\ for j:= 0...n \\ \theta_{j} := \theta_{j} - \alpha{1 \over m}\sum_{i=1}^{m}(h_{\theta}(x^{(i)}-y^{(i)})x_{j}^{(i)} }$$

向量形式：

$$\theta := \theta - \alpha \nabla J(\theta) \\ = \theta - {\alpha \over m} X^T(X\theta - y)$$

特征正则化

• 特征放缩：输入值除以范围（最大值与最小值的差）
• 均值归一：输入值减去均值
  两个方法一起用

梯度下降tips

• 画图看损失函数，如果有上升说明学习率太大
• 设一个足够小的判定收敛的阀值

特征与多项式回归

改善模型，考虑把多个特征合成一个

多项式回归

通过对特征取幂形成新的特征，得到多项式假设函数
或者取个平方根
使用这些方法时，特征放缩非常重要

标准方程

是一种不用迭代寻找最优值的方法

$$\theta = (X^TX)^{-1}X^Ty$$
推导：令误差的平方的一次导数为零

注意：

• 不用特征放缩
• 复杂度是立方，比梯度下降的平方慢
• $X^TX$有可能不可逆，原因是特征之间线性相关或者特征太多了

第三周

逻辑斯特回归
虽有回归之名，其实解决的是分类问题

二元分类

0为负类，1为正类
当假设满足

$$0 \leq h_\theta(x) \leq 1$$
使用Sigmoid函数，也叫逻辑斯特函数：
$$g(x) = {1\over 1+e^{-z}}\\ let z = \theta^Tx \\ h_\theta(x) = g(z) = g(\theta^Tx)$$
输出结果为1的概率

决策边界

为了得到二元分类，我们约定：
逻辑斯特函数输出大于等于0.5，表示$y = 1$
逻辑斯特函数输出小于0.5，表示$y = 0$
记住逻辑斯特的函数图像
决策边界就是y=0和y=1的分界线

损失函数

原来的用不了了，原来那个已经不是凸函数了

$$J(\theta) = -{1 \over m}\sum_{i=1}^m y^{(i)}log(h_\theta(x^{(i)})) + (1-y^{(i)})log(1-h_\theta(x^{(i)}))$$

向量形式：

$$h = g(X\theta) \\ J(\theta) = {1 \over m}(-y^Tlog(h)-(1-y)^Tlog(1-h))$$

梯度下降

与之前的没区别
向量形式多套一个$g(\theta X)$而已

损失函数$J(\theta)$的偏导数推导

先算逻辑斯特函数的导数：
$g(z)^{'} = ... = g(z)(1-g(z))$
再对损失函数关于$\theta_j$求偏导：
和式的偏导等于偏导的和式，找到变量$\theta$所在的项，复合函数求导，
注意到${\partial \over \partial \theta_j} \theta^T x^{(i)} = x_j^{(i)}$
(x的各个分量的线性组合对第j个分量求导的结果)
分子分母约一下，合并一下，得到

$${\partial \over \partial \theta_j} J(\theta) = {1\over m}\sum_{i=1}^m[h_{\theta}(x^{(i)})-y^{(i)}]x_j^{(i)}$$

向量形式：

$$\nabla J(\theta) = {1\over m}X^T(g(X\theta)-y)$$

高级优化

更好的优化手段：共轭梯度、BFGS、L-BFGS

• BFGS算法（以四个人的名字首字母命名）：
  对二阶优化方法————牛顿算法的一种改进，因为牛顿算法考虑二阶导数，而计算Hassian矩阵很耗时，BFGS提出一种方法近似求得Hassian矩阵。
  http://www.cnblogs.com/kemaswill/p/3352898.html

• L-BFGS算法：
  当Hassian矩阵比较大的时候，用Limited-memory BFGS
  https://en.wikipedia.org/wiki/Limited-memory_BFGS

多类别分类：一对多

目标是把数据分成n+1类(y={0,1...n})
把问题分割成n+1个二元分类问题
在每个问题中，计算y属于第k个类的概率$P(y=k|x;\theta)$
然后求概率最大值

选择一个类，然后把其他剩下的类看作一个整体，反复运用二元逻辑斯特回归，然后求概率最大值

正则化

过拟合

正则化用来解决过拟合问题

高偏差(high bias)/欠拟合：假设函数不能很好地预测数据的趋势。原因是函数太简单或者特征太少
高方差(high variance)/过拟合：能够拟合已有数据的假设函数没有很好地泛化来预测新数据。原因是函数太复杂，产生太多与数据无关的曲线和角

解决过拟合的手段：

• 减少特征的数量：

  1. 手工选择保留哪个特征
  2. 使用模型选择(model selection)算法

• 正则化
  保留所有特征，但减小参数$\theta$
  当我们有很多稍微有用(slightly useful)的特征时，正则化有效。

损失函数

通过增加损失来减小假设函数中某些项的权重($\theta$值)
例如：如果我想让一个四阶函数更像平方函数，那么就要减小三阶和四阶变量的影响（而不是把它们从假设函数中移除），我们可以在损失函数中加上三阶和四阶变量对应的$\theta$参数，并赋予很大的权值。如果想要损失函数接近零，那么就要使得三阶和四阶变量对应的$\theta$参数接近零，从而达到减小三阶和四阶变量影响的目的。

也可以通过求和来正则化所有的$\theta$参数

$$min_{\theta} {1 \over 2m} \sum_{i=1}^m(h_{\theta}(x^{(i)}-y^{(i)})^{2} + \lambda \sum_{j=1}^n \theta_j^2$$
其中$\lambda$是正则化参数，决定$\theta$参数的损失（或惩罚）应该“放大”多少。

使用带有求和项的损失憾事，我们可以把假设函数的输出光滑化(smooth)，从而减小过拟合。但是如果正则化参数太大，会导致过于平滑而欠拟合。

正则化线性回归

• 梯度下降
  $$重复直到收敛:{ \\ \theta_{0} := \theta_{0} - \alpha[{1 \over m}\sum_{i=1}^{m}(h_{\theta}(x^{(i)}-y^{(i)})x_{0}^{(i)}] \\ for j:= 1...n \\ \theta_{j} := \theta_{j} - \alpha[{1 \over m}\sum_{i=1}^{m}(h_{\theta}(x^{(i)}-y^{(i)})x_{j}^{(i)} + {\lambda \over m} \theta_j] }$$

把$\theta_0$跟其他参数分开，因为没必要惩罚它（它不控制x分量）

• 标准方程
  $$\theta = (X^TX + \lambda L)^{-1}X^T y$$
  $$L = \begin{bmatrix} 0 \\ & 1 \\ &　& 1 \\ & & & \ddots \\ & & & & 1 \end{bmatrix}_{(n+1)\times(n+1)}$$
  $\lambda$是正则化参数
  保证可逆

正则化逻辑回归

• 损失函数
  

  $$J(\theta) = -{1 \over m}\sum_{i=1}^m y^{(i)}log(h_\theta(x^{(i)})) + (1-y^{(i)})log(1-h_\theta(x^{(i)})) + {\lambda \over 2m}\sum_{j=1}^n \theta_j^2$$
  明确排除偏项(bias term) $\theta_0$
  平方保证是非负

• 梯度下降
  跟上文一样

初始全一特征向量

常量特征

在训练开始之前，加一个常量特征到特征集中是很重要的。这个特征一般是一个全1的集合。
例如，当特征矩阵是X时，$X_0$就是全一向量。

解释：

1. 电子工程的角度：交流电和直流电
   非常量特征捕捉模型中的动态特征，由于输入改变导致的输出变化，相当于DC交流电。
   常量特征代表不变部分，就像交流电的直流部分。
   而对时序信号做微分就能清除模型中的静态部分。
2. 几何角度
   不是所有直线都会经过原点，因此y=ax+b中的b有存在的必要
3. 实际情况
   有常量特征和没有常量特征的训练结果相差一个常数。
   例如用两套模型（一套有常量特征，一套没有）预测房子A和房子B的价格，两套模型的预测结果可能完全不一样，但是房子A和B的价格差值是一样的。
   偏项是当输入全为零时的稳态，代表模型固有的偏差，其他特征产生张力来移动这个偏差位置。

第四周

神经网络之表示

非线性假设

线性回归很少见
有若干个变量，两两相乘组成一个多项式，配以相关系数，加上常数项，外面套一个函数，形成假设函数。
如果变量一多，这种方法会产生大量特征，不实际。

神经元和大脑

神经网络是对我们大脑工作原理的有限模拟。它们最近经历了一个很大的复兴，因为计算机硬件的发展。
大脑只用一种学习算法来完成不同函数。这个准则就是“神经可塑性”。

模型表示

• 输入层
• 隐藏层
• 输出层
• 偏移单元（bias unit）
• 激活函数
• 激活单元：隐藏层节点
  $$a_i^{(j)} = 第j层第i个节点的激活(activation) \\ \theta^{(j)} = 控制函数从第j层映射到第j+1层的权重矩阵\\ \theta_{ik}^{(j)} = 第j层第k个特征映射到第j+1层第i个激活点的权值$$

权重矩阵的维度是$d_{j+1}\times (d_j+1)$
其中+1来自偏移单元$\theta_j^{0}$和$x_0$。
输入包含偏移单元，而输出不包含。

向量表示

令输入层n+1维向量$x = a^{(1)}$，那么

$$z^{(j)} = \theta^{(j-1)}a^{(j-1)}$$
其中$\theta^{(j-1)}$维度是$n\times (n+1)$，z^{(j)}是n维向量
然后 $$a^{(j)} = g(z^{(j)})$$
其中g作用于每个元素
最后增加一个$a_0^{(j)}=1$到$a^{(j)}$当中，继续重复计算
直到最后一层，输出一个值，情况跟逻辑斯特回归一样。

多元分类

输出层是一个由0和1组成的向量，1表示属于该分类。

第五周

神经网络之学习

损失函数

定义：
$L$是网络总层数
$s_l$是第l层除去偏移单元之外的节点数
$K$是输出节点数，即分类数
$h_{\theta}(x)_k$是产生第k个输出的假设

假设函数：

$$J(\theta) = -{1\over m}\sum_{i=1}^m\sum_{k=1}^K[y_k^{(i)}log(h_{\theta}(x^{(i)})_k) + (1-y_k^{(i)})log(1-h_{\theta}(x^{(i)})_k)] + {\lambda \over 2m}\sum_{l=1}^{L-1}\sum_{i=1}^{s_l}\sum_{j=1}^{s_l+1}(\theta_{j,i}^{(l)})^2$$

对所有样本的所有输出节点求和。
正则化项对把所有参数平方求和。

Backpropagation算法

用来最小化损失函数的算法
给定训练集${(x^{(1)},y^{(1)}...(x^{(m)},y^{(m)})}$

• 设定$\Delta_{i,j}^{(l)}$初始值为0
  对于从1到m的第t个训练样本：

• 令$a^{(1)}:=x^{(t)}$

• 执行forward propagation计算$a^{(l)}$（l=2,3...L）
• 计算$\delta^{(L)}=a^{(L)}-y^{(T)}$
• 使用$\delta^{(L)}=((\theta^{(l)})^T\delta^{(l+1)}).*a^{(l)}.*(1-a^{(l)})$计算$\delta^{(L-1)},\delta^{(L-2)}...\delta^{(2)}$
• $\Delta_{i,j}^{(l)}:=\Delta_{i,j}^{(l)}+a_j^{(l)}\delta_i^{(l+1)}$ 或者向量形式$\Delta^{(l)}:=\Delta^{(l)}+\delta^{(l+1)}(a^{(l)})^T$
• $D_{i,j}^{(l)}:={1\over m}(\delta_{i,j}^{(l)}+\lambda\theta_{i,j}^{(l)})$ if j!=0
• $D_{i,j}^{(l)}:={1\over m}\delta_{i,j}^{(l)}$ if j=0

说明：
1. $\delta_j^{(l)}$代表第l层第j个节点的“误差”
2. $\Delta$作为一个“误差累加器”，累计所有层误差以激活为权重的和
3. $D_{i,j}^{(l)}$是把$\Delta$经过正则化、取平均后的结果，表示损失函数对$\theta$的偏导数

$$D_{i,j}^{(l)} = {\partial J(\theta) \over \partial \theta_{i,j}^{(l)}} = {1\over m}\sum_{t=1}^m a_j^{(t)(l)}\delta_{i}^{(t)(l+1)}$$

直觉理解

当输出只有一个节点时，第t个样本的损失是

$$cost(t) = y^{(t)}log(h_{\theta}(x^{(t)}))+(1-y^{(t)})log(1-h_{\theta}(x^{(t)})) \\ \approx (h_{\theta}(x^{(t)})-y^{(t)})^2$$
$$\delta_j^{(l)} = {\partial\over \partial z_j^{(l)}}cost(t)$$

展开参数

把多个矩阵合成一个矩阵，为了方便调用优化函数
得到结果后展开

检查梯度

使用数值方法求一个梯度

$${\partial\over \partial \theta_j}J(\theta) \approx {J(\theta_1,...,\theta_j+\epsilon,...,\theta_n)-J(\theta_1,...,\theta_j-\epsilon,...,\theta_n) \over 2\epsilon}$$
这招用来验算，很慢

随机初始化

如果初始权重全为零，那么所有节点的值将会是相同的。
所以需要随机初始化。
一种初始化方法是：

$$\epsilon = {\sqrt{6} \over \sqrt{输出节点数+输出节点数}} \\ \theta^{(l)}=2\epsilon * (维度为输出节点数\times (输入节点数+1)的0-1随机矩阵) - \epsilon$$

设计与训练

首先选择一个网络构架

• 输入节点个数 = 训练样本特征维数
• 输出节点个数 = 分类数
• 每个隐藏层的节点个数： 越多越好，但要平衡计算成本
• 隐藏层个数： 默认1个，多于1个时每层节点个数相同

训练神经网络
1. 随机初始化权重
2. 通过forword propagation求得假设函数
3. 求损失函数
4. 通过back propagation求偏导
5. 使用梯度验证确保back propagation有效
6. 使用梯度下降或者内置优化函数通过权重最小化损失函数

forword propagation和back propagation在遍历样本的循环中进行。

back propagation公式推导

https://github.com/FengZiYjun/Markdown-Notes/blob/master/image/backpropagation.png

第六周

应用机器学习的建议

排除预测误差的手段：

• 使用更多训练样本
• 采用更小的特征集
• 增加特征
• 尝试多项式特征
• 改变正则化参数

评价假设

把数据集分为训练集和测试集：

• 使用训练集学习参数并最小化损失函数
• 计算测试集误差，即测试集中的损失函数值

测试集误差

1. 线性回归
   误差平方求和取平均
2. 分类误差
   正确分类给个1，错误分类给个0，求和取平均

模型选择

• 一个学习算法很好地拟合一个训练集，不意味这是一个好的假设
• 用来训练参数的数据集得到的误差小于其他数据集

为了选择最好的模型，需要检查每个多项式的次数和误差结果

使用交叉验证集(cross validation set)

用来作为一个训练多项式次数的中间数据集

划分数据集的例子：

• 训练集：60%
• 交叉验证集：20%
• 测试集：20%

（从不同次数的多项式中选择最合适的）
1. 对每个多项式次数使用训练集优化参数
2. 使用交叉验证集找出误差最小的多项式次数
3. 使用测试集把误差最小的多项式次数代入损失函数，估计总的误差

诊断偏差或方差(bias vs. variance)

• 如何判别bias或者variance导致了不准确的预测？

• high bias 是欠拟合，high variance 是过拟合，怎样平衡？

  1. 随着多项式次数增加，训练误差倾向于减小，而交叉验证误差先减后增。
  2. high bias(underfitting): 次数太小时，训练集和交叉验证集的误差很高，近乎相等。
  3. high variance(overfitting): 次数太大时，训练集误差小，交叉验证集误差大得多。

正则化和bias/variance

考察正则化参数对bias/variance的影响

• 很大的$\lambda$:high bias, underfitting，训练集和交叉验证集误差大

• 很小的$\lambda$:high variance, overfitting, 训练集误差小，交叉验证集误差大

  1. 构造一组$\lambda$
  2. 构造一组有变量不同的模型
  3. 遍历所有$\lambda$，每个$\lambda$应用在所有模型中学习$\theta$
  4. 使用学到的$\theta$计算交叉验证集误差（不考虑正则化）
  5. 选择交叉验证误差最小的那一组$\lambda$和$\theta$
  6. 应用到测试集

学习曲线

• 随着训练集增大，误差会增大
• 训练集增大到一定程度之后，误差值会趋于平滑

high bias

小训练集：训练集误差小，交叉验证集误差大
大训练集：都很大，近似相等

增加训练样本对high bias于事无补

high variance

小训练集：训练集误差小，交叉验证集误差大
大训练集：训练集误差增加，交叉验证集误差减小，但差距依然显著

增加训练样本对high variance可能有用

总结

修补high variance:
1. 增加训练样本
2. 减少特征
3. 增大正则化参数

修补high bias:
1. 增加特征
2. 减小正则化参数

诊断神经网络

• 参数少的神经网络容易欠拟合，但计算成本低
• 参数多的神经网络容易欠拟合，但计算成本高，可以增大正则化参数

用交叉验证在很多隐藏层上训练网络？

模型选择

怎样选择哪个多项式次数？

• 获取更多数据
• 选择拟合数据最好而且没有过拟合的模型
• 通过正则化减少过拟合的可能

bias是估计的误差，是期望值和最优值之间的差距
variance是由于有限数据引起的估计误差

bias-variance权衡：

• 复杂模型: 对数据敏感，容易受X的变化影响，high variance, low bias
• 简单模型：更僵硬，X的变化影响不大，low variance, high bias

正则化的影响

正则化参数

• 小，模型更容易受噪音影响，倾向于过拟合
• 大，把权重参数的重要性降低，倾向于欠拟合

模型复杂性效应

• 低阶多项式，有较低模型复杂度，有high bias和low variance
• 高阶多项式，有较高模型复杂度，有low bias和high variance
• 实际上我们需要一个模型，能够很好地抽象泛化也能很好地拟合数据

进行诊断

• 获取更多的训练数据能解决high variance，但不是high bias
• 减少特征能解决high variance但不是high bias
• 增加特征能解决high bias但不是high variance
• 增加多项式和特征交叉能解决high bias而不是high variance
• 使用梯度下降时，减小正则化参数能够解决high bias，增加正则化参数能够解决high variance
• 使用神经网络时，网络的大小有影响。交叉验证对网络大小的选择有帮助

机器学习系统设计

优先处理什么？

• 搜集数据
• develop sophisticated features
• develop算法以不同的方法来处理输入

误差分析

解决机器学习问题的推荐方法

• 从一个简单的算法开始，快速实现它，尽早测试
• 画学习曲线来决定更多数据、更多特征是否有帮助
• 手动检查交叉验证集的误差

误差结果应该是一个单一数值。然而评估算法很难。

对输入数据的预处理

偏类的误差矩阵

有时候很难说误差的减少是否真的是算法的改进。
例如：二元分类中把所有输入都归入一类，会得到低误差，但算法没有改进

这就是偏类(skewed class)的情况：当某一个类在整个数据集里非常稀罕
另一种说法是，数据集中某一类的样本远多于其他类
这种情况下，我们用准确/回召(Precision/Recall)：

-	预测真	预测假
实际真	true positive	false negative
实际假	false positive	true negative

准确率(pricision)：预测为真的样本当中实际为真的比例

$$Presicion = {true positive \over true positive + false positive}$$
召回率(Recall):实际为真的样本当中预测为真的比例
$$Recall = {true positive \over true positive + false negative}$$

好的分类器两者都应该很高

权衡准确率和回召率

当我们在做逻辑斯特回归时，如果需要一个确信的结果，其中一种方法是提高预测为真的阀值
但这样就会使得准确率很高，但回召率很低
相反地，如果我们降低阀值，就会得到安全的预测，但是回召率很高而准确率很低

为了把这两种指标合起来，我们采用F值(F value)
而简单地取平均不能反应我们的需求（两个都要高）
所以应该取调和平均数

$$F score = 2{PR \over P+R}$$
只有P和R都很高时，F才高
一般利用交叉验证集来计算准确率和回召率

机器学习的数据

训练要用多少数据？
很多时候，有足够数据的差算法能够胜于不足数据的好算法
我们必须选择特征来确保有足够的信息（以人类专家的角度来判断？）
大数原理：一个low bias的算法拥有越多数据，越不容易过拟合，在测试集上越准确

第七周

支持向量机(SVM, support vector machine)
一种监督学习方法，有时更简洁更强大

在逻辑斯特回归的损失函数当中，$-log({1\over {1+e^{-z}}})$是一条凹曲线，可以用一条折线近似，折线转折点在(1,0)
对另外包含log的一项，同理也可以用折线来近似，转折点在(-1,0)
折线使用分段函数表示，所以原来的损失函数中$-log$关于z的函数被替换成分段函数关于$z=\theta^TX$的函数，分别用$cost_0$和$cost_1$表示
由

$$J(\theta) = -{1 \over m}\sum_{i=1}^m y^{(i)}log({1\over {1+e^{-z^{(i)}}}}) + (1-y^{(i)})log(1-{1\over {1+e^{-z^{(i)}}}}) + {\lambda \over 2m}\sum_{j=1}^n \theta_j^2$$
变成
$$J(\theta) = C\sum_{i=1}^m y^{(i)}cost_0(\theta^Tx^{(i)}) + (1-y^{(i)})cost_1(\theta^Tx^{(i)})+ {1\over 2}\sum_{j=1}^n \theta_j^2$$
C是常量，用来代换m

支持向量机是一个判别函数

$$cost_0(z)=max\{0,k(1+z)\} \\ cost_1(z)=max\{0,k(1-z)\}$$

大边缘

把支持向量机看作大边缘分类器

若y=1，我们希望$\theta^Tx \geq 1$
若y=0，我们希望$\theta^Tx \leq -1$

逻辑斯特回归中的决策边界是区分正负样本的一条直线
在SVM中，决策边界有一种特殊的性质——尽可能远离正负样本
决策边界到最邻近的样本的距离成为边缘(margin)
SVM最大化这种边缘，故称之为大边缘分类器
SVM会通过一个大边缘区分正负样本
只有当C很大时，才能使用SVM。因为C很大，为了最小化损失函数，对$\theta$的要求更高
此时损失函数简化成

$$J(\theta) = C\times0 + {1\over 2}\sum_{j=1}^n \theta_j^2 \\ = {1\over 2}\sum_{j=1}^n \theta_j^2$$

当数据能被一根直线分为正负时，称数据为线性可分的

如果出现离群值，我们可以降低C值，不让它影响决策边界

C的调增与正则化参数的调整效果相反

大边缘分类器背后的数学原理

向量内积

向量的长度$||v|| = 各分量平方和的开方$
向量的投影$u^Tv = ||v||cos\theta ||u|| = 对应分量乘积的和$
記$p = ||v||cos\theta$是v在u方向上的投影，则

$$u^Tv = p||u||$$

把SVM的损失函数重写成

$$J(\theta) = {1\over 2}||\theta||^2$$
决策边界也重写成:
$$\theta^T x^{(i)} = p^{(i)}||\theta|| = \sum_{i=1}^n \theta_i x_1^{(i)}$$
这里p是样本向量往$\theta$方向的投影
若y=1，我们希望$p^{(i)}||\theta|| \geq 1$
若y=0，我们希望$p^{(i)}||\theta|| \leq -1$

这造成大边缘的原因是：向量$\theta$垂直于决策边界
为了实现优化目标（最小化损失函数,最小化$\theta$长度），我们需要投影$p^{(i)}$的绝对值尽可能大
在样本向量长度一定的情况下，只能找到某个位置的$\theta$，使得样本向量与它之间的夹角最小，而决策边界也随之确定

核

核方法允许我们通过SVM构造复杂的非线性分类器

给定x，依据到标志$l^{(1)},l^{(2),l^{(3)}}$的接近度计算新特征
先定义相似度

$$f_i = similarity(x,l^{(i)}) = exp(-{||x-l^{(i)}||^2 \over 2\sigma^2})$$
这就是高斯核，核方法中的一种

相似度函数的性质：

• 如果$x \approx l^{(i)}$那么$f_i \approx 1$
• 如果x远离$l^{(i)}$那么$f_i \approx 0$
• $\sigma^2$是高斯核的参数，用来修正相似度函数下降的速率

把每个标志代入相似度函数得到一个$f_i$，把这些$f_i$作为特征，与$\theta$的线性组合构成关于X的假设函数

得到标志的一种方法是，把所有训练样本的空间位置都当作标志，所以就有了m个标志
对于样本中的每一个向量，可以通过高斯核转化为关于自身到m个标志的相似度向量

$$x^{(i)} -> f^{(i)} = \begin{bmatrix} f_1^{(i)} = similarity(x^{(i)},l^{(1)}) \\ f_2^{(i)} =similarity(x^{(i)},l^{(2)}) \\ \vdots \\ f_m^{(i)} = similarity(x^{(i)},l^{(m)}) \\ \end{bmatrix}$$

现在$f^{(i)}$就代替了$x^{(i)}$，我们可以对$f^{(i)}$使用SVM算法

核方法并不只能用来SVM中，但SVM与核方法结合会使得速度很快

选择SVM参数

• 选择C(=${1\over \lambda}$)
  C很大，high variance, low bias
  C很小，low variance, high bias

• 选择$\sigma^2$
  很大，f特征很光滑，high bias, low variance
  很小，f特征不光滑，low bias, high variance

使用SVM

用库函数，不要自己写
真正需要选择的是：

• 参数C
• 核（相似度函数）
• 当n很大、m很小的时候，不需要核，相当于“线性核”，就是典型的线性分类器
• 当n很小、m很大的时候，采用高斯核，要选择$\sigma^2$

注意：
1. 在使用高斯核之前，要进行特征放缩(feature scaling)
2. 不是所有相似度函数都是合理的核，必须满足Mercer's Theorem，保证优化结果不出偏差
3. 可以用训练集和交叉验证集训练C和核参数

多元分类

就像逻辑斯特回归那样，用一对多方法

逻辑斯特回归 vs. SVM

• 当n相对m很大时，用逻辑斯特回归或者无核SVM（也叫线性核）
• 当n很小、m很大时，手动增加特征，变成第一种情况
• 当n很小、m适中时，使用高斯核SVM
• 上述所有情况都可以用神经网络，但很慢

第八周

聚类

非监督学习

跟监督学习相对，使用未标注的数据集
换句话说，没有y向量，只有特征数据集
聚类有助于

• 市场组分分隔
• 社交网络分析
• 管理计算机群
• 天文数据分析

K-Means算法

最普遍最常用的自动分类算法，把数据自动分类成凝聚的子集

1. 在数据集中随机初始化两个点，成为聚类中心(cluster centroids)
2. 聚类分配：根据靠近哪个聚类中心，把所有样本分配给两个聚类中的一个
3. 移动中心：计算在每个聚类点群中所有点的中心位置，然后把聚类中心移到那个点
4. 重复2和3，直到找到聚类

我们主要的变量是：

• K——聚类的数目
• 训练集$x^{(1)},x^{(2)},...x^{(m)}$, where $x^{(1)} \in R^n$

算法

Randomly initialize K cluster centroids mu(1), mu(2), ..., mu(K)
Repeat:
   for i = 1 to m:
      c(i):= index (from 1 to K) of cluster centroid closest to x(i)
   for k = 1 to K:
      mu(k):= average (mean) of points assigned to cluster k

第一个循环是聚类分配，c(i)表示x(i)被分配到第几个类
以数学形式表示为

$$c^{(i)} = argmin_k ||x^{(i)}-\mu_||^2$$
这样每个c(i)包含距离x(i)最近的聚类中心的编号

一般的欧拉距离是要开方的，但这里没有开方，为了计算方便而且增长快速

第二个循环是移动中心。
数学形式为

$$\mu_k = {1\over n}[x^{(k_1)}+x^{(k_2)}+...+x^{(k_n)}]$$
其中$x^{(k_n)}$是分配给聚类$m_{\mu_k}$的训练样本

如果有一个聚类没有分配到点，那么可以重新随机初始化到一个新的点，也可以简单地去除这个聚类。

在一定次数的迭代之后，算法会收敛，新的迭代不影响现有聚类情况

对于没有内在分隔或者自然结构的数据，K-Means算法也能均匀地把数据分隔成K份

优化目标

参数如下

• $c^{(i)}$ = 样本$x^{(i)}$分配到的聚类的编号
• $\mu_k$ = 聚类中心向量
• $\mu_{c^{(i)}}$ = 样本$x^{(i)}$分配到的聚类的中心

定义损失函数：

$$J(c^{(i)},...,c^{(m)},\mu_1,...,\mu_k) = {1\over m}\sum_{i=1}^m||x^{(i)}-\mu_{c^{(i)}}||^2$$

优化目标是
$min_{c,\mu}J(c,\mu)$

即寻找集合c（代表所有聚类）以及$\mu$(代表所有中心)来最小化每个训练样本到相应聚类中心的平均距离

上述损失函数也成为训练样本的失真(distortion)
在聚类分配的步骤，我们的目标是保持$\mu$不变，用c来最小化J
在移动中心的步骤，我们的目标是用$\mu$来最小化J

K-Means算法的损失函数不可能递增，只能递减。

随机初始化

一种推荐的方法

1. 令K
2. 随机选取K个样本
3. 令$\mu_1,...\mu_k$等于这K个样本

K-Means会陷入局部最优解。为了降低这种事发生的几率，你可以在多个不同的随机初始化上进行算法。当K<10的情况，推荐在一个随机初始化的循环里跑一下。

for i = 1 to 100:
   randomly initialize k-means
   run k-means to get 'c' and 'm'
   compute the cost function (distortion) J(c,m)
pick the clustering that gave us the lowest cost

选择聚类的数目

K的选择是相当随意和模凌两可的

The elbow method： 画出损失函数J和聚类数目K。J应当随着K的增加而减小（除非陷入局部最优），然后趋于平滑。选择损失函数开始平滑的那个K值。
但是通常曲线变化很平缓(gradual)，没有一个清晰的elbow。

另一种选择K的方法是观察K-Means怎样在下游的目的(downstream purpose)中表现，即根据使用这些聚类的实际需求。

K-Means的缺陷

https://stats.stackexchange.com/questions/133656/how-to-understand-the-drawbacks-of-k-means

有三个assumption：
1. k-means assumes the variance of the distribution of each attribute (variable) is spherical;
2. all variables have the same variance;
3. the prior probability for all k clusters is the same, i.e., each cluster has roughly equal number of observations;

失效情况：
Clustering non-clustered data
Sensitive to scale
Even on perfect data sets, it can get stuck in a local minimum.
If you want a theoretical model of what k-means does, consider it a quantization approach, not a clustering algorithm.
k-means finds (sometimes) the best reduction to k values of a multidimensional data set. Where "best" is the least squared error.

降维

目的1：数据压缩

• 数据冗余需要对特征的维度进行压缩
  找两个高度相关的特征，画出它们，构造一条新的直线准确地表述两个特征。然后在这一条直线上放置所有的新特征。
  降维可以减少储存的数据总量并加快算法
  注意：降的是特征数，不是样本数

目的2：可视化

把数据降到3维就可以可视化了
我们要找新的三个特征来有效归纳(summarize)所有其他特征

PCA

最常用的降维算法Principal Component Analysis (PCA)

问题形成

给定两个特征，我们项找一条直线能够一次性有效描述它们，然后把旧的特征映射到这条新的线上。
三个特征也一样，映射到一个平面
PCA的目标是减小所有特征到投影直线的平均距离，这叫投影误差

从n维降到k维：寻找K个向量，使得数据在它们上的投影的误差最小

PCA不是线性回归

• 线性回归最小化的是每个点到预测直线的平方误差（squared error），是垂直距离

• PCA最小化的是到数据点的最短距离，或者叫最短正交距离

• 线性回归做的是拿x来“预测”y

• PCA做的是拿x来“找向量”

PCA算法

给定训练集x(1),x(2),...,x(m)
1. 预处理（特征放缩、均值正则化）
2. 计算协方差矩阵(covariance matrix)

$$\sum = {1\over m}\sum_{i=1}^m x^{(i)} (x^{(i)})^T$$
得到$n\times n$维矩阵
3. 计算协方差矩阵的特征向量
使用执行singular value decomposition(SVD)的内置函数，得到的U矩阵是我们需要的
[U,S,V] = svd(\sigma)
4. 取U矩阵的前k列并计算z
取U矩阵的前k列，得到一个$n\times k$的矩阵$U_{reduce}$，然后计算z
z值是一个实数，表示原有特征往压缩后的特征的投影
$$z^{(i)} = U_{reduce}^T x^{(i)}$$

从压缩表示重建

$$x_{approx}^{(i)} = U_{reduce} z^{(i)}$$
只能得到近似值

注意：U矩阵的特殊性质
U矩阵是一个酋矩阵(unitary matrix)
其逆矩阵是自身的共轭矩阵，在实数范围内就是自身的转置

选择主成分的数目

怎样选择k，也就是主成分的数目？k是降维到达的维度。
使用一下公式：
给定平均平方投影误差: ${1\over m}\sum_{i=1}^m||x^{(i)}-x_{approx}^{(i)}||^2$
也给定数据的总偏移(total variation): ${1\over m}\sum_{i=1}^m||x^{(i)}||^2$
选择最小的k使得

$${{1\over m}\sum_{i=1}^m||x^{(i)}-x_{approx}^{(i)}||^2 \over {1\over m}\sum_{i=1}^m||x^{(i)}||^2} \leq 0.01$$
换句话说，平方投影误差除以总偏移应该小于百分之一，即99%的variance得到保留。

选择K的算法
1. 令k=1,2...使用PCA
2. 计算$U_{reduce} ,z, x$
3. 检查上述公式

实际上有更快的方法：利用矩阵S
[U,S,V] = svd(\sigma)

$${\sum_{i=1}^k S_{ii} \over \sum_{i=1}^n S_{ii}} \leq 0.99$$

使用PCA的建议

常用来加速监督学习
把一万维度的特征减到一千维度

注意：

• 降维只用来训练集，不用在交叉验证集和测试集，所以需要升维
• PCA不推荐用来防止过拟合
• PCA不是机器学习的必须步骤，而是附加手段

第九周

异常检测

问题来源

给定数据集，想知道一个新的样本是否异常
构造一个模型，用来判定这个样本正常的概率
设定阀值，如果概率小于阀值，就判定为异常
如果这个异常检测器标记出太多异常样本，那么有必要减小阀值了

高斯分布

高斯分布类似于一个钟形曲线，能用函数$N(\mu,\sigma^2)$表述
x是一个实数，如果x的概率分布是高斯分布
$x \approx N(\mu,\sigma^2)$
$\approx$: is distributed as
其中$\mu$是均值，决定曲线的中心
$\sigma$是标准差，决定曲线的宽度

$$p(x;\mu,\sigma^2) = {1\over \sigma \sqrt{2\pi}}e^{-{1\over 2}({x-\mu \over \sigma})^2}$$
$$\mu = {1\over m}\sum_{i=1}^m x^{(i)} \\ \sigma^2 = {1\over m}\sum_{i=1}^m (x^{(i)}-\mu)^2$$

算法

独立性假设：训练集样本的各个特征直接没有相关性
記

$$p(x) = \prod_{j=1}^n p(x_j;\mu_j,\sigma^2)$$
注意：$x_j$不是样本向量，而是特征分量

1. 在各特征分量上计算均值和标准差
2. 计算待检测的$p(x)$
3. 与阀值比较

开发与评价异常检测系统

为了评估我们的算法， 拿来一些标记数据，把它们分为正常和异常样本
在数据中，拿极大部分好的、非异常数据作为训练集来训练$p(x)$
然后拿一小部分异常与非异常混合的样本（异常依然是少数）作为交叉验证集和测试集

1. 在训练集上拟合模型$p(x)$
2. 在交叉验证集或者测试集上，依据阀值做出预测
3. 使用一些评价指标： true/false positive/negative, precision/recall, F1 score

注意：交叉验证集可以用来选择阀值

异常检测vs. 监督学习

使用异常检测的情况：

• 有非常少的正样本和非常多的负样本
• 异常种类有很多种，很难用算法从正样本中学习到异常长什么样；未来的异常可能跟以前看过的都不一样

使用监督学习的情况：

• 有大量正负样本，训练集可以大概均分
• 有足够多的正样本帮助算法学习到新的正样本长什么样，未来的正样本会跟训练集中的类似。

选择使用什么特征

通过画出数据的柱状图、检查钟形曲线来检查特征是否成高斯分布

一些有用的变换：取对数、开方等

选择出现在异常中的过大或者过小的特征

多元高斯分布

一次性为$p(x)$建模
参数是$\mu \in R^n, \sum \in R^{n\times n}$

$$p(x;\mu,\sum) = {1\over (2\pi)^{\frac n 2} |\sum|^{\frac 1 2}} exp(-{1\over 2(x-\mu)^T\sum^{-1}(x-\mu)})$$
这样就可以构建一个椭圆高斯轮廓，可以更好比圆形轮廓更好地拟合数据
改变$\sum$会改变轮廓的形状、宽度和方向
改变$\mu$会改变分布的中心

使用多元高斯分布检测异常

正常计算$\mu$和$\sum$，然后利用上述公式
多元高斯模型能够自动检测不同特征之间的相关性
但缺点是需要更多数据、计算成本高

推荐系统

问题提出

假设要给用户推荐电影

• $n_u$ = 用户数目
• $n_m$ = 电影数目
• $r(i,j) = 1$ 如果用户j评价过电影i
• $y(i,j) = rating$ 用户j对电影i的评价

基于内容的推荐

对每个用户评价过的电影使用线性回归

• $\theta^{(j)}$ = 用户j的参数向量
• $x^{(i)}$ = 电影i的特征向量
  对于用户j和电影i，预测评价是$(\theta^{(j)})^T(x^{(i)})$
  优化目标是
  $$min_{\theta^{(1)}\dots \theta^{(n_u)}} = {1\over 2} \sum_{j=1}^{n_u} \sum_{i:r(i,j)=1} ((\theta^{(j)})^T(x^{(i)}) - y^{(i,j)})^2 + {\lambda \over 2}\sum_{j=1}^{n_u} \sum_{k=1}^{n} (\theta_k^{(j)})^2$$

除了消除了常数$\frac1 m$之外跟线性回归没有什么不同

协同过滤

让用户告诉我们他们喜欢哪些种类的电影，通过提供他们的参数向量
从用户的参数$\theta$推断电影参数$x$，需要以下的平方误差函数

$$min_{x^{(1)}\dots x^{(n_m)}} = {1\over 2} \sum_{j=1}^{n_m} \sum_{i:r(i,j)=1} ((\theta^{(j)})^T(x^{(i)}) - y^{(i,j)})^2 + {\lambda \over 2}\sum_{j=1}^{n_m} \sum_{k=1}^{n} (x_k^{(j)})^2$$
可以随机猜测$\theta$的值，最终都会收敛到一个好的特征集

协同过滤算法

为了加速，我们可以同步最小化特征和参数

$$J(x,\theta) = {1\over 2}\sum_{(i,j):r(i,j)=1} ((\theta^{(j)})^T x^{(i)} - y^{(i,j)})^2 + {\lambda \over 2}\sum_{i=1}^{n_m}\sum_{k=1}^n (x_k^{(i)})^2 + {\lambda\over 2}\sum_{j=1}^{n_m}\sum_{k=1}^n (\theta_k^{(j)})^2$$

1. 用一些随机小值初始化$x^{(1)} \dots x^{(n_m)},\theta^{(1)} \dots \theta^{(n_u)}$，用来打破对称性并保证算法学习到的特征x是彼此不同的
2. 使用梯度下降或者其他优化算法最小化$J(x,\theta)$
3. 根据用户参数和电影特征，预测评价$\theta^Tx$

向量化：低阶矩阵分解

给定矩阵X（每行包含一部电影的特征）和矩阵$\theta$（每行包含对于一个特定用户来说那些特征的权重），那么所有用户评价所有电影的预测就是$Y = X\theta^T$

预测两部电影如何类似可以用它们向量之间的距离（各种距离）

实现细节：均值归一化

新用户没有看过电影，会把所有电影评估为0，不合理
解决这个问题要把数据归一化到平均值
首先用一个矩阵Y储存从以前的评价中得到的数据，每行对应电影，每列对应用户
然后计算一个新的向量
$\mu = [\mu_1, \dots \mu_{n_m}]$

$$\mu_i = {\sum_{j:r(i,j)=1} Y_{i,j} \over \sum_j:r(i,j)}$$
计算第i部电影的评分均值（只有看过电影的用户的评分才计算入内）
现在可以通过把Y矩阵的每列减去$\mu$来归一
最后只需要在线性回归项中加上这个$\mu_i$
因此对于新用户来说，最初的预测值将会是

第十周

大数据集机器学习

大数据集通常有m=100,000,000
传统的梯度下降（也叫批量梯度下降batch gradient descent）每次要对很大的m求和，我们想办法避免这一点

随机梯度下降(stochastic gradient descent)

是梯度下降的变种，对大数据集更加灵活

$$cost(\theta,(x^{(i)},y^{(i)})) = {1\over 2}(h_{\theta}(x^{(i)}) - y^{(i)})^2$$
损失函数消除了常数m
$$J_train(\theta) = {1\over m}\sum_{i=1}^m cost(\theta,(x^{(i)},y^{(i)}))$$
现在J就是所有训练样本的平均损失

算法如下：
1. 随机捣乱数据集
2. 对于i从1到m：

$$\theta_j := \theta_j - \alpha(h_{\theta}(x^{(i)}) - y^{(i)})x_j^{(i)}$$

算法每次只拟合一个训练样本。这样我们可以在无需扫描全部m个样本的前提下在梯度下降取得进步。
随机梯度下降不太可能会收敛到全局最小值，而是会在它旁边随机游荡，但通常会产生一个足够靠近的结果。
随机梯度下降通常会采取1-10次遍历数据集来接近全局最小值。

小批量梯度下降(Mini-Batch Gradient Descent)

有时候比随机梯度下降更快
每次使用一定数量b的样本
b的取值可以是2-100

对i从1,1+b,1+2b...m-b+1

$$\theta_j := \theta_j - \alpha{1\over b}\sum_{k=i}^{i+b}(h_{\theta}(x^{(i)}) - y^{(i)})x_j^{(i)}$$
每次对b个样本求和
可以向量化

随机梯度下降收敛

怎样选择学习率？
怎样确保它尽量靠近全局

一种策略是画出每1000左右个样本的假设的平均损失，我们可以在迭代中保存这些值
一个较小的学习率可能会得到一个更好的结果，因为随机梯度下降会在全局最优附近震荡跳跃，小学习率会带来小步伐的随机跳跃

如果增加画图的平均样本数，曲线变得平滑。
如果取平均的样本数太小，曲线会变得聒噪并很难找到趋势
一种真正收敛到全局最优的策略是慢慢降低学习率
$\alpha = {常数1 \over 迭代次数 + 常数2}$

但这很少做到，因为人们不想瞎搞那么多参数了

在线学习(online learning)

伴随着连续的网站用户流，我们可以运行一个永不停止的循环来收集用户行为作为特征X来预测一些行为y
你可以收集到的数据对每个用户修改参数$\theta$，这样就可以适应新的用户群，因为你在不停地修改参数

Map Reduce 和数据并行

把批量梯度下降分开，把对一个数据子集的损失函数分配到不同的机器中，于是就可以并行训练算法了
不同机器求不同部分的和
Map Reduce会负责这些调度(map)工作并通过计算减少(reduce)它们

你的算法是可以用Map Reduce的(MapReduceable)，如果它能被表示成训练集函数的求和。
线性回归和逻辑斯特回归很容易并行处理。

对于神经网络，你可以在数据的子集上用不同机器计算forward propagation和back propagation，然后把导数回报给主机。