大数据集学习
数据集过大,使用梯度下降法计算的代价太大(每一次都需要遍历数据集中所有数据),而且误差函数对各样本对待无差别(无论偏差大小,均以相同的学习率进行更新)。故我们可以考虑使用小样本进行梯度下降。
假设算法的假设函数如下:
$$
h_\theta (x^{(i)}) = \sum_{j=0}^n\theta_jx_j^{(i)}
$$
其中,$x^{(i)}$为数据集中第i个样本,$x_j^{(i)}$为其第j个特征。
批量梯度下降法
批量梯度下降算法使用所有样本的误差进行参数更新,损失函数如下:
$$
J_{train}(\theta)=\frac{1}{2m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2
$$
所以各参数的更新公式为
$$
\theta_j:=\theta_j-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x^{(i)}_j
$$
随机梯度下降法
使用的损失函数仍为(2)式不变,但每次迭代样本计算出单个损失后,就开始做参数更新。 无序的样本能够使得算法收敛速度更快,所以算法初始需要先随机打乱数据集。
各参数的更新公式为
$$
\theta_j:=\theta_j-\alpha(h_\theta(x^{(i)})-y^{(i)})x^{(i)}_j
$$
小批量随机梯度下降法
取前两种梯度下降法的所长,对b个样本做一次梯度更新。优点是比批量梯度下降算法快,并行计算后比随机梯度下降算法快。缺点是超参数b需要另外确定。
梯度下降算法的收敛问题
- 如何判定已经收敛?
- 如何选择学习率$\alpha$?
检查是否收敛
批量梯度下降算法:求取全部样本的损失,画出学习曲线。
随机梯度下降算法:每次计算单独样本的损失,用于更新模型权重,每固定量次后进行平均损失的计算,画出学习曲线。
学习曲线解析
图中的蓝色的学习曲线是学习率$\alpha$过高的情形,红线是$\alpha$过低的情形。
图中的蓝色的学习曲线是求取均值误差的总样本数$m$小的情形(小批量随机梯度下降算法),红线是$m$大的情形。
图中的蓝色的学习曲线是求取均值误差的总样本数$m$小的情形(随机梯度下降算法),红线是$m$大的情形,紫线是没有进行学习的情形。
图中的蓝色的学习曲线代表学习算法发散,需要使用更小的学习率$\alpha$进行学习。
选择学习率
随机梯度下降法如果最终无法很好地收敛到最优解,则需要使它在迭代过程中不断减小数值:
$$
\alpha=\frac{const1}{iterationNumber+const2}
$$
式中,学习率$\alpha$随着迭代次数的增大而减小,但需要额外确定两个参数,少人用;且因为原本不变的学习率便能够使得最终结果很好接近最优解,故更少人用。
在线学习
网站有连续的数据流流入,数据不断地在在线更新。这种场景下,因为数据量巨大,不可能保存所有的数据样本,
故可以使用在线学习技术,不断通过在线数据流进行学习,适应偏好的变化。
场景1:某用户需要寄快递,已知$o=x_1,d=x_2$,给出运费$x_3$,顾客对本公司快递服务选择与否记为y=1/0,
对顾客选择本公司快递服务的概率进行建模$P(y=1|x;\theta) $;
场景2:用户搜索商品,返回部分排序商品,商品特征为$x$,用户是否点击推荐商品记为y=1/0,对顾客选择点击推荐商品的概率进行建模$P(y=1|x;\theta)$。
Map-Reduce
MapReduce是一种分布式计算框架 ,以一种可靠的,具有容错能力的方式并行地处理上TB级别的海量数据集。主要用于搜索领域,解决海量数据的计算问题。MR有两个阶段组成:
- Map()负责把一个大的block块进行切片并计算;
- Reduce() 负责把Map()切片的数据进行汇总、计算。
例如,批量梯度下降算法计算损失函数时,便可以分布进行计算。将数据集均分为4份,
1 | graph LR |
其中$Computer_k(k=1,2,3,4)$对应的计算为
$$temp_j^{(k)}=\sum_{i=100(k-1)+1}^{100k}(h_\theta(x^{(i)})-y^{i})x_j^{(i)}$$
对于参数更新公式(3),可改写为
$$\theta_j:=\theta_j-\alpha\frac{1}{m}(temp_j^{(1)}+temp_j^{(2)}+temp_j^{(3)}+temp_j^{(4)})$$
但Map-Reduce使用也是需要条件的,学习算法的损失函数需要可以表示为一系列的求和形式,或者表示成在训练集上对函数的求和。
当然我们不一定需要多台计算机才能做到Map-Reduce,现在的多和计算机器也可以做到这一步,图示如下:
1 | graph LR |