梯度下降算法

http:\/\/blog.csdn.net\/luo123n\/article\/details\/48239963 http:\/\/sebastianruder.com\/optimizing-gradient-descent\/

* 算法

$x_{k+1} = x_k + \mu_k \bigtriangleup x_k$

* 以最小二乘问题为版本

$J(\theta)=\frac{1}{2}\sum\limits_{i=1}^m(h_{\theta}(x)-y)^2$

1. 梯度下降算法

* step1: 初始化 $\theta$\ (随机初始化)

* step2: 迭代

* step3:

$\displaystyle \theta_j := \theta_j -\alpha\frac{\partial}{\partial\theta_j}J(\theta)$

• $\alpha 是学习率$

• 梯度方向：$\displaystyle \frac{\partial}{\partial\theta_j}J(\theta)=(h_{\theta}(x)-y)x_j$

2. 批梯度下降算法

* 算法

• $(1.0) \ \ \ \ \ \ $ repeat until convergence
• $(1.1) \ \ \ \ \ \ $ $\displaystyle \theta_j := \theta_j+\alpha\sum\limits_{i=1}^m(y^{(i)}-h_{\theta}(x^{(i)}))x_j^{(i)}$

3. 随机梯度下降算法

http://www.cnblogs.com/murongxixi/p/3467365.html

• 每次使用一个样本点来更新回归的系数

3.1 算法

所有的回归系数初始化

对数据中的每个样本：

    计算该样本的梯度

    使用alpha*gradient更新回归系数

返回回归系数

• loop:
  • for i=1 to m:
    • $\theta_j:=\theta_j+\alpha(y^{(i)}-h_{\theta}(x^{(i)}))x_j^{(i)}$

4. 批处理梯度下降算法的步长的选择

* 步长选择的基础

• 线性搜索的方法
• 信頼域的算法

* 步长

• $h(\alpha)=f(x_k+\alpha d_k)$

搜索方向是:$d_k$; 学习率：$\alpha$

• 在斜率大的地方，使用小的学习率
• 在斜率大的地方，使用大学习率

* 步长选择的推导

• $h(\alpha)=f(x_k+\alpha d_k)$

• 当$\alpha=0$, h(0)=$f(x_k)$;

导数：$\bigtriangledown h(\alpha)=f(x_k+\alpha d_k)^T d_k$

• 当$x_k$和$d_k$是定值情况，寻找最小值：

$\alpha=arg \min\limits_{\alpha>0}h(\alpha)=arg \min\limits_{\alpha>0} f(x_k+\alpha d_k)$

• 若$h(\alpha)$可导，局部最小值处的$\alpha$ 满足：

$h^{'}(\alpha)=\bigtriangledown f(x_k+\alpha d_k)^T d_k = 0$

• 将$\alpha=0$带入:

$h^{'}(0)=\bigtriangledown f(x_k+0*d_k)^T d_k=-\bigtriangledown f(x_k)d_k$

• 先选定下降方向：$d_k$是负梯度方向

• 则：$h^{'}(0)=-\bigtriangledown f(x_k)d_k < 0$

• 若可以找到足够大的$\alpha$，使得$h^{'}(\alpha)>0$

• 则：存在$\alpha$,使得$h^{'}(\alpha^*)=0$

• 则：$\alpha^*$是所求的学习率

* 步长的确定方法

• 二分线性
• 线性回溯搜索
• 二次差值

6 随机梯度下降的步长的选择

http://blog.csdn.net/luo123n/article/details/48239963

• adagrad
• adadelta
• adam

上述方法速度较差