Day 5 Optimization

关键词：Gradient Decent 梯度下降、Gradient Checking、mini-batch GD、Bag of words

第一种方法：Random search

随机产生w1，然后求损失值 Lost1，然后再随机生成w2, 如果lost2 < lost1，则把w2先记录下来，然后继续……很明显，效率很低。

Random Search

第二种方法：Follow the slope

简答来说，就是求斜率，看下图（为了引出微积分），对某个数增+delt_x，然后看 delt_y是变大还是变小，沿着delt_y变小的方向调整即可。

斜率

Numerical gradient

设定好h，更新w，对每个dimension分别计算当前w下的梯度，缺点很明显：计算速度很慢

Numerical gradient 

Analytic  gradient

所以引入了微积分 --> 计算analytic  gradient（解析梯度），其实就是对w求导。精确、快速、易错（容易陷入局部最优解）

微积分

Gradient check

numerical gradient 可以用来检查analytic gradient是否正确，用于debug。

第三种：Gradient Descent 梯度下降

梯度下降

之前看过Andrew Ng的课程，基本了解梯度下降，所以在这里就不多说了，下图觉得比较有代表性。

Gradient Descent

Hyper-parameterLearning rate (step_size) 每一步迈多大、Lambda（惩罚） 

如何设置这两个参数尤为重要

- 学习率太大，函数无法收敛，甚至发散 (very high learning rate)

- 学习率足够小，理论上是可以达到局部最优值的（非凸函数不能保证达到全局最优），但学习率太小却使得学习过程过于缓慢 (low learning rate)

- 合适的学习率应该是能在保证收敛的前提下，能尽快收敛。(good learning rate)

对于深度网络中，参数众多，参数值初始位置随机，同样大小的学习率，对于某些参数可能合适，对另外一些参数可能偏小（学习过程缓慢），对另外一些参数可能太大（无法收敛，甚至发散），而学习率一般而言对所有参数都是固定的，所以无法同时满足所有参数的要求。通过引入Momentum可以让那些因学习率太大而来回摆动的参数，梯度能前后抵消，从而阻止发散。

Learning Rate

随机梯度下降法（stochastic gradient descent，SGD）

SGD是最速梯度下降法（Batch Gradient Descent，BSD）的变种。

使用最速梯度下降法，将进行N次迭代，直到目标函数收敛，或者到达某个既定的收敛界限。每次迭代都将对m个样本进行计算，计算量大。

为了简便计算，SGD每次迭代仅对一个样本计算梯度，直到收敛。伪代码如下（以下仅为一个loop，实际上可以有多个这样的loop，直到收敛）

SGD Loop

（1）由于SGD每次迭代只使用一个训练样本，因此这种方法也可用作online learning。

（2）每次只使用一个样本迭代，若遇上噪声则容易陷入局部最优解。

SGD

Mini-batch Gradient Descent

1. 每次选取一定量的训练样本进行迭代。(一定量：32/64/128/256，因为内存是二进制，为了匹配GPU，所以样本都是2的指数次方）

2. 从公式上似乎可以得出以下分析：速度比BSD快，比SGD慢；精度比BSD低，比SGD高。

3. 因为每次是选取一定量的样本计算（所选样本的分布是随机的），所以噪声很大，但总体而言是呈下降趋势的。

总结：

批量梯度下降（BGD）：use all examples in each iteration. 

随机梯度下降（SGD）：use 1 example in each iteration 

mini-batch梯度下降：use b examples in each iteration

Image Features

线性分类器

对于图片而言，线性分类器不能处理像素类数据，所以需要人工提取特征，然后进行线性分类，比如：颜色、边缘等。

特征提取

词袋模型 bag of words

Bag-of-words模型是信息检索领域常用的文档表示方法。在信息检索中，BOW模型假定对于一个文档，忽略它的单词顺序和语法、句法等要素，将其仅仅看作是若干个词汇的集合，文档中每个单词的出现都是独立的，不依赖于其它单词是否出现。也就是说，文档中任意一个位置出现的任何单词，都不受该文档语意影响而独立选择的。例如有如下两个文档

    1：Bob likes to play basketball, Jim likes too.

    2：Bob also likes to play football games.

    基于这两个文本文档，构造一个词典：

Dictionary = {1:”Bob”, 2. “like”, 3. “to”, 4. “play”, 5. “basketball”, 6. “also”, 7. “football”, 8. “games”, 9. “Jim”, 10. “too”}。

    这个词典一共包含10个不同的单词，利用词典的索引号，上面两个文档每一个都可以用一个10维向量表示（用整数数字0~n（n为正整数）表示某个单词在文档中出现的次数）：

     1：[1, 2, 1, 1, 1, 0, 0, 0, 1, 1]

     2：[1, 1, 1, 1 ,0, 1, 1, 1, 0, 0]

    向量中每个元素表示词典中相关元素在文档中出现的次数。不过，在构造文档向量的过程中可以看到，我们并没有表达单词在原来句子中出现的次序。

词袋模型被广泛应用在文件分类，词出现的频率可以用来当作训练分类器的特征。

BOW

在使用CNN后，不需要人为提取特征，可以直接提取特征

CNN