随机梯度下降

目标函数通常是训练数据集中有关各个样本的损失函数的平均，所以梯度下降的情况，每次自变量迭代的计算开销是O(n)【n是样本数】，它随着n线性增长，尤其是n很大的时候，每次迭代的计算开销很高。
随机梯度下降(stochastic gradient descent,SGD)就减少了每次迭代的开销，在SGD中，我们随机均匀采样的一个样本索引(i),并计算此处的梯度▽f(x)来迭代x： $x \leftarrow x-\eta \triangledown f_{i}(x)$ （η为学习率）
这样迭代的话，开销就从O(n)降到了O(1)
值得强调的是，随机梯度i处的梯度▽f(x)是对梯度▽f(x)的无偏估计：
$E_{i} \triangledown f_{i}(x)=\frac{1}{n}\sum_{i=1}^{n} \triangledown f_{i}(x)=\triangledown f(x)$ 【对随机梯度求数学期望就是把n个加起来再求平均，即原始梯度】，意味着，平均来说，随机梯度是对梯度的一个良好的估计。
我们来比较梯度下降和随机梯度下降的区别，其中梯度下降可以参看上一篇文章?梯度下降
现在使用随机噪声来模拟随机梯度下降：

eta=0.1
def f_2d(x1,x2):
    return x1**2 + 2*x2**2

def sgd_2d(x1,x2,s1,s2):
    return (x1-eta*(2*x1 + np.random.normal(0.1)),x2-eta*(4*x2 + np.random.normal(0.1)),0,0)

d2l.show_trace_2d(f_2d,d2l.train_2d(sgd_2d))

从图中可以看出，相比较梯度下降来说，没有那么光滑，显得更为曲折，这是由于添加的噪声模拟的随机梯度下降的准确度下降，在实际中，这些噪声通常是指训练数据集中的无意义的干扰。

小批量随机梯度下降

同样的，梯度下降使用的是整个训练数据集来计算梯度，因此我们常称为批量梯度下降(Batch Gradient Descent,BGD)，而上面介绍的随机梯度下降是每次随机一个样本，现在我们将在每轮迭代中随机均匀采样(分为重复采样和不重复采样)多个样本组成一个小批量，然后使用小批量去求梯度，这种情况我们就称之为小批量随机梯度下降。那可以得出一个结论，当批量大小是1，就是上面的随机梯度下降，当批量大小是整个数据集大小，就是批量梯度下降。
设迭代开始前的时间步为0，小批量为B，得到如下公式：

$g_{t}\leftarrow \triangledown f_{B _{t}}(x_{t-1})=\frac{1}{|B|}\sum_{i\in B_{t}}\triangledown f_{i}(x_{t-1})$

时间步t的小批量B上的目标函数位于 $x_{t-1}$ 处的梯度 $g_{t}$ ，给定学习率η，自变量的迭代如下：

$x_{t}\leftarrow x_{t-1}-\eta_{t}g_{t}$

由于随机采样得到的梯度的方差在迭代过程中无法减小，因此在实际中，小批量随机梯度下降的学习率可以在迭代过程中自我衰减，例如? $\eta_{t}=\eta t^{\alpha}$ (通常α=-1或-0.5)、 $\eta_{t}=\eta \alpha ^{t}$ (如：α=0.95)
或者每迭代若干次后将学习率衰减一次，这样一来学习率和小批量随机梯度乘积的方差就会减小。另：梯度下降不需要，因为迭代过程使用的是目标函数的真实梯度。

我们通过实例测试来比较梯度下降、随机梯度下降、小批量梯度下降。

三者区别

import d2lzh as d2l
from mpl_toolkits import mplot3d
import numpy as np
from mxnet import nd,autograd,gluon,init
from mxnet.gluon import nn,data as gdata,loss as gloss
import time

data1=np.genfromtxt('data/airfoil_self_noise.dat',delimiter='\t')
print(data1.shape)#(1503, 6),1503个样本，5个特征加最后一列是标签值

#已包含在d2lzh中(注意路径，直接调用的话路径是../data)
#截取前1500个样本和5个特征值以及最后的标签值
def get_data_ch7():
    data=np.genfromtxt('data/airfoil_self_noise.dat',delimiter='\t')
    data=(data-data.mean(axis=0)) / data.std(axis=0)
    return nd.array(data[:1500,:-1]),nd.array(data[:1500,-1])
features,labels=get_data_ch7()#(1500, 5),(1500,)

def sgd(params,states,hyperparams):
    for p in params:
        p[:] -= hyperparams['lr'] * p.grad
    
#已包含在d2lzh中
def train_ch7(trainer_fn,states,hyperparams,features,labels,batch_size=10,num_epochs=2):
    net,loss=d2l.linreg,d2l.squared_loss#线性回归，平方损失
    w=nd.random.normal(scale=0.01,shape=(5,1))
    b=nd.zeros(1)
    w.attach_grad()
    b.attach_grad()
    
    def eval_loss():
        return loss(net(features,w,b),labels).mean().asscalar()
    ls=[eval_loss()]
    data_iter=gdata.DataLoader(gdata.ArrayDataset(features,labels),batch_size,shuffle=True)
    for _ in range(num_epochs):
        start=time.time()
        for batch_i,(X,y) in enumerate(data_iter):
            with autograd.record():
                l=loss(net(X,w,b),y).mean()
            l.backward()
            trainer_fn([w,b],states,hyperparams)#迭代模型参数
            if(batch_i+1)*batch_size % 100==0:
                ls.append(eval_loss())#每100个样本就记录当前训练误差
    print('loss:%f,%f sec per epoch' % (ls[-1],time.time()-start))
    d2l.set_figsize()
    d2l.plt.plot(np.linspace(0,num_epochs,len(ls)),ls)
    d2l.plt.xlabel('epoch')
    d2l.plt.ylabel('loss')

def train_sgd(lr,batch_size,num_epochs=2):
    train_ch7(sgd,None,{'lr':lr},features,labels,batch_size,num_epochs)
    
train_sgd(1,1500,6)#1个迭代周期对模型只迭代1次，属于梯度下降
#可以看到6次迭代之后目标函数值的下降趋向了平稳

train_sgd(0.005,1)#1个迭代周期对自变量进行1500次更新，属于随机梯度下降
#可以看到目标函数值在1个迭代周期后就变得较为平缓

train_sgd(0.05,10)#属于小批量随机梯度下降
#首先从耗时可以看出介于梯度下降与随机梯度下降之间，因为随机梯度下降在一个迭代周期里做了更多次的自变量迭代
#而且单样本的梯度计算难以有效利用矢量计算

简洁实现，使用Trainer实例来调用优化算法

def train_gluon_ch7(trainer_name,trainer_hyperparams,features,labels,batch_size=10,num_epochs=2):
    net=nn.Sequential()
    net.add(nn.Dense(1))
    net.initialize(init.Normal(sigma=0.01),force_reinit=True)
    loss=gloss.L2Loss()
    
    def eval_loss():
        return loss(net(features),labels).mean().asscalar()
    
    ls=[eval_loss()]
    data_iter=gdata.DataLoader(gdata.ArrayDataset(features,labels),batch_size,shuffle=True)
    #创建Trainer实例来迭代模型参数
    trainer=gluon.Trainer(net.collect_params(),trainer_name,trainer_hyperparams)
    
    for _ in range(num_epochs):
        start=time.time()
        for batch_i,(X,y) in enumerate(data_iter):
            with autograd.record():
                l=loss(net(X),y)
            l.backward()
            trainer.step(batch_size)#在Trainer实例里做梯度平均
            if (batch_i+1)*batch_size % 100==0:
                ls.append(eval_loss())

    print('loss:%f,%f sec per epoch' % (ls[-1],time.time()-start))
    d2l.set_figsize()
    d2l.plt.plot(np.linspace(0,num_epochs,len(ls)),ls)
    d2l.plt.xlabel('epoch')
    d2l.plt.ylabel('loss')

train_gluon_ch7('sgd',{'learning_rate':0.05},features,labels,10)