玩命加载中...
<![CDATA[
## 二、随机梯度下降法
随机梯度下降法（Stochastic Gradient Decent, SGD）是对全批量梯度下降法计算效率的改进算法。本质上来说，我们预期随机梯度下降法得到的结果和全批量梯度下降法相接近；SGD的优势是更快地计算梯度。
我们先回顾以下全批量法是如何计算每次迭代中的梯度的：
$$\nabla L = \left(\frac{\partial L}{\partial \beta\_0}, \frac{\partial L}{\partial \beta\_1}\right)=\left(\frac{2}{N}\sum\_{j=1}^N(\beta\_0+\beta\_1x\_j-\hat y\_j), \frac{2}{N}\sum\_{j=1}^Nx\_j(\beta\_0+\beta\_1x\_j-\hat y\_j)\right)$$
其中$N$是样本数量，我们很容易看出，对于最小二乘法来说，每计算一次梯度的代价是$O(N)$，运算次数与$N$成线性关系。
而随机梯度下降法能将计算一次梯度的代价降低到$O(1)$，也就是运算次数为常数次，与$N$无关。所以SGD特别适合大训练样本的计算。
SGD在计算$\nabla L $时，并不使用全部样本，而是随机地挑选了一个样本$(x\_r,\hat y\_r)$，
$$\nabla L = \left(\frac{\partial L}{\partial \beta\_0}, \frac{\partial L}{\partial \beta\_1}\right)=\left(2(\beta\_0+\beta\_1x\_r-\hat y\_r), 2x\_r(\beta\_0+\beta\_1x\_r-\hat y\_r)\right)$$
根据上面的式子，我们修改了上面使用过的`compute_grad`函数。新函数`compute_grad_SGD(beta, x, y)`会每次随机选择一个样本，并且根据这个样本计算出梯度。这就是所谓的**随机梯度**下降法。
```python
def compute_grad_SGD(beta, x, y):
grad = [0, 0]
r = np.random.randint(0, len(x))
grad[0] = 2. * np.mean(beta[0] + beta[1] * x[r] - y[r])
grad[1] = 2. * np.mean(x[r] * (beta[0] + beta[1] * x[r] - y[r]))
return np.array(grad)
```
在原来的第（4）步中，我们每次迭代都要计算损失函数的变化$\left|L(\beta^{i+1})-L(\beta^{i})\right|$。而计算这个损失函数的代价是和全批量法中计算梯度的代价相等的。我们可以改成每进行100次迭代，检查一次$\left|L(\beta^{i+1})-L(\beta^{i})\right|$。
在原来的程序中，我们用`compute_grad_SGD`代替`compute_grad`。并且修改终止迭代的条件。
```python
# 引用模块
import pandas as pd
import numpy as np
# 导入数据
train = pd.read_csv('train.csv')
test = pd.read_csv('test.csv')
submit = pd.read_csv('sample_submit.csv')
# 初始设置
beta = [1, 1]
alpha = 0.2
tol_L = 0.1
# 对x进行归一化
max_x = max(train['id'])
x = train['id'] / max_x
y = train['questions']
# 定义计算随机梯度的函数
def compute_grad_SGD(beta, x, y):
grad = [0, 0]
r = np.random.randint(0, len(x))
grad[0] = 2. * np.mean(beta[0] + beta[1] * x[r] - y[r])
grad[1] = 2. * np.mean(x[r] * (beta[0] + beta[1] * x[r] - y[r]))
return np.array(grad)
# 定义更新beta的函数
def update_beta(beta, alpha, grad):
new_beta = np.array(beta) - alpha * grad
return new_beta
# 定义计算RMSE的函数
def rmse(beta, x, y):
squared_err = (beta[0] + beta[1] * x - y) ** 2
res = np.sqrt(np.mean(squared_err))
return res
# 进行第一次计算
np.random.seed(10)
grad = compute_grad_SGD(beta, x, y)
loss = rmse(beta, x, y)
beta = update_beta(beta, alpha, grad)
loss_new = rmse(beta, x, y)
# 开始迭代
i = 1
while np.abs(loss_new - loss) > tol_L:
beta = update_beta(beta, alpha, grad)
grad = compute_grad_SGD(beta, x, y)
if i % 100 == 0:
loss = loss_new
loss_new = rmse(beta, x, y)
print('Round %s Diff RMSE %s'%(i, abs(loss_new - loss)))
i += 1
print('Coef: %s \nIntercept %s'%(beta[1], beta[0]))
```
Round 100 Diff RMSE 1517.68063478
Round 200 Diff RMSE 59.121501507
Round 300 Diff RMSE 57.6261183472
Round 400 Diff RMSE 12.4878329725
Round 500 Diff RMSE 30.7707789755
Round 600 Diff RMSE 528.307198648
Round 700 Diff RMSE 459.412195353
...
Round 28700 Diff RMSE 28.1667190227
Round 28800 Diff RMSE 49.0252502725
Round 28900 Diff RMSE 0.0963260007679
Coef: 4636.29068335
Intercept 805.078482893
经过28900次迭代（对于全批量梯度下降法来说相当于是28900/2253=12.83次迭代），SGD得到的模型系数为
```python
print('Our Coef: %s \nOur Intercept %s'%(beta[1] / max_x, beta[0]))
```
Our Coef: 2.05782986389
Our Intercept 805.078482893
训练误差RMSE为
```python
res = rmse(beta, x, y)
print('Our RMSE: %s'%res)
```
Our RMSE: 610.133277988
SGD尽管加快了每次迭代的计算速度，但是也带了收敛不稳定的缺陷（具体可以查看**[SGD的收敛问题](http://sofasofa.io/forum_main_post.php?postid=1000762)**）。
有时候，我们可以设置衰减步长来强行使得SGD的系数收敛。
有时候，我们可以设置一个较大的固定的迭代次数。
但是如果仅仅通过比较两次系数的变化或者损失函数的变化，有时候会带来一种**假收敛**的现象。
全批量梯度下降虽然稳定，但速度较慢；SGD虽然快，但是不够稳定。**为了综合两者的优缺点，小批量随机梯度下降法应运而生。**
<ul class="pagination">
<li><a href="index.php">第1页</a></li>
<li><a href="2.php">第2页</a></li>
<li><a href="3.php">第3页</a></li>
<li class="active"><a href="#">第4页</a></li>
<li><a href="5.php">第5页</a></li>
<li><a href="6.php">第6页</a></li>
</ul>
<ul class="pager">
<li class="previous"><a href="3.php"><b>← 返回前一页</b></a></li>
<li class="next"><a href="5.php"><b>进入下一页 →</b></a></li>
</ul>
]]>
