Gradient Decent With Large Datasets
Learning with large datasets
在前面的章节(week6)中我们已经知道了当我们已经有了一个low bias的算法时，最重要的就是数据的量的大小，数据量越大最终模型的效果越好。但是，我们不能盲目的增加数据量，必须针对模型的问题来分析是high bias问题还是high variance问题。如果是high bias问题，则盲目增加数据量并没有什么用，必须改进算法才行。回忆下之前的high bias和high variance问题的Jerror对比图：
Stochastic Gradient Decent
此小节主要讲了什么是随机梯度下降(stochastic gradient decent)，以及为什么要使用随机梯度下降。
首先，回忆了利用梯度下降算法计算的过程，如下图：
- 在梯度下降的每一步都需要针对所有的样本有一个加总，如图蓝色方框中圈示。因此，当我们的m非常大时，梯度下降的每一步都需要大量计算。
- 我们称之前一直在用的梯度下降算法叫做批量梯度下降(batch gradient decent)
那么，如何解决这个问题呢？这就引入了随机梯度下降。如下图：
- 首先，我们看下公式J(θ)，其本质就是将所有的预测值和实际值的平方差相加然后求平均值，那么，如果将每个样本值的cost记作如图右上角的公式，那么可以认为所有的样本的cost相加再求平均值。由此，我们也可以理解到当我们针对每个样本求其cost最小值的时候，也就是求J(θ)的最小值。因此，我们可以将原先的梯度下降过程转化为图右的计算过程。其本质就是逐个样本缩小预测值和实际值的差距。
- 随机梯度下降的第一步是shuffle，实际就是打乱样本顺序，让其随机排列。
- 第二步是两层循环，最里层循环实际是针对每个样本的cost function求导，从而针对θ进行梯度下降。需要注意的是，这里每个样本的计算都在做“梯度下降”，而不需要像批量梯度下降那样针对所有样本进行计算之后才能下降一小步。
这个过程中，由于单个样本可能导致的偏离，实际下降过程是非常曲折的，如下图所示：
- 相比较而言，batch gradient decent每一步都是向global minimum靠近，而随机梯度下降并不是每一步都向global minimum靠近，而是曲折靠近。
- 使用随机梯度下降最终可能不是J的global minimum，但是是一个非常接近的结果，会限定在某一个区域，因此，在实际应用中已经可以满足我们的要求了（实际可用的模型）
Mini-Batch Gradient Decent
在前一节我们已经了解了随机梯度下降的过程，将每次计算所有样本的cost平均值，然后再梯度下降，拆解为每次只针对一个样本进行梯度下降。利用同样的思想，我们可以每次针对一小批样本进行梯度下降，既不是全部样本，也不是单个样本。如下图所示：
- 通常我们需要选择mini-batch每次使用的样本数b，一般b的范围在2~100之间。
- 上图，Andrew使用了一个b=10的例子来展示如何计算。
mini-batch gradient decent完整的计算过程如下：
- 相比较batch gradient decent每次需要针对所有样本进行计算然后才能下降一小步，而mini-batch gradient decent每次只需要针对一个小批量样本进行计算就可以下降一次。
- 相比较随机梯度下降，当我们可以使用vectorization的时候，我们可以针对一批数据进行并行计算，这种情况下，其计算效率要远高于单个样本的计算，因此，当可以使用vectorization的时候，mini-batch gradient decent的效率是最高的。
Stochastic Gradient Decent Convergence
此小节的主要问题是解决如何判断我们的随机梯度下降随着迭代次数的增加而收敛，以及如何调节𝛼，之前的章节其实我们已经学习过可以通过画J与iteration次数的关系图来判断是否收敛，同理，我们也可以画类似的图形来判断，但是问题是我们不可能每次都计算这个总的J(θ)，所以我们必须找一个别的方法来替代，由此我们引出了新的J的计算方法，如下图：
- 在随机梯度下降中，每次训练某个样本之前就计算其cost(针对当前样本计算)
- 可以每1000次计算一下cost的平均值，然后将其作为一个点画到图形当中
然后，我们可以通过这个cost平均值与迭代次数的关系图可以做判断，如下图：
- 其它图形比较好理解，唯一需要说明的是当出现左下角的图形时，需要首先判断是否是噪音导致的，可以增加计算平均值的数量(比如原先1000次计算一次平均值，可以改为5000次计算一次平均值)。当排除噪音干扰的情况后，仍然无法下降收敛，那就说明是我们算法的问题，需要调整算法。
Advanced Topics
Online Learning
本节主要讲如何运用在线学习算法实时地进行模型训练。首先Andrew举了一个在线的包裹运输服务的报价系统的例子，如下图所示：
- 在线学习算法本质上是随机梯度下降，每一个样本都进行一次随机梯度下降。
- 由于是实时获取数据实时训练，因此我们的模型实际上也是在不断进化的，最终会随着用户的使用偏好而调整自身的参数。这一点是在线学习算法的一大优势。
- 另外，由于每一个样本我们只使用一次，因此使用完之后我们不需要保留这些样本的数据(除非有其它需求)
- 在线学习算法对大流量网站非常有效因为会不停地有数据过来进行训练，但是对于小流量网站可能就不适用，数据量不够大，模型训练出来的效果不足够好。
之后，Andrew又举了一个手机展示的例子，如下图：
- 此示例中每次展示10个查询结果，相当于有10个样本，因此借用的是mini-batch gradient decent的思想。
- 此处展示了网站的常用技巧即根据用户的点击来判断结果的优劣。因此，当用户点击时，我们可以认为y=1，没有点击则为0
此种算法会导致最初展示的结果有非常大的先发优势，最终导致其被点击的概率越来越高。从另一个侧面可以看出很多时候先发优势是非常重要的。先发优势获取头部效应，然后资源进一步向头部靠拢，最后形成鸿沟。这就是马太效应的生动写照啊。
Map Reduce and Data Parallelism
此小节主要讲了如何通过map reduce的方式来并行计算，从而加快训练的速度。尤其是当数据量非常大的时候，有时我们不得不通过map reduce的方式将数据先拆分计算再聚合计算。示例如下：
- 很多算法都可以类似的将数据切分成多份，然后分发给多台机器并行计算，然后将计算结果在一台机器上进行聚合
- 并行计算既可以在多台机器上并行，也可以在一台机器上的多核进行并行，而且有些算法库会自动利用并行计算。
