Gradient descent Algorithm

Gradient descent

Introduction to Gradient

很在一元函数中，梯度就是微分，然而在多元函数中梯度就是一个向量，而向量又是有方向的，梯度的方向就指明了函数在给定点的上升最快方向。(假设$$J(\theta)$$由$$\theta_{0},\theta_{1},\theta_{2}$$确定，那么梯度就是$$ \nabla(J) = <\frac{\partial J}{\partial \theta_{0}},\frac{\partial J}{\partial \theta_{1}},\frac{\partial J}{\partial \theta_{2}}>$$)

为了让代价函数尽可能的小，我们使用梯度下降算法进行优化找到最小值，就是因为梯度的方向指明了函数在给定点的上升最快的方法，那么梯度的反方向也就是下降最快的方向，所以一直沿着梯度走，最后就可以得到代价函数的最小值。

Gradient descent expression

$$\Theta^{1} = \Theta^{0}-\alpha\nabla J(\Theta)$$

$$这里\Theta^{1}代表下一个位置，\Theta^{0}代表当前位置,\alpha可以理解为步长或者学习率，\nabla J(\Theta)为梯度$$

Tips:

  • 对于$$\alpha$$来说，如果过于小，那么我们每次优化的幅度也就相当小，这也就意味着我们的梯度优化很慢，如果过于大，那么我们可能直接越过了最小值，或者函数最后发散。
  • 在梯度下降的过程中，变化幅度会逐渐减小，在一元函数中，我们可以理解为，函数的导数或者说斜率变化越来越小，趋于平缓直到最后的导数为0。
  • 这里$$\Theta$$可以理解成每一个过程，假设$$J(\theta_{0},\theta_{1})$$，那么$$\Theta_{1}也就是表示(\theta_0,\theta_1)在梯度下降中的取值$$

Gradient descent with one variable

$$Hypothesis: h_{\theta}(x) = \theta_{0} + \theta_{1}x$$

Example1

假设$$J(\theta) = \theta^{3},\alpha=0.2,\Theta^{0} = 1$$

$$\Theta^{0} = 1$$

$$\Theta^{1} = \Theta^{0} - \alpha J^{‘}(\Theta^{0}) = 1 - 0.2*3=0.4$$

$$\Theta^{2} = \Theta^{1} - \alpha J^{‘}(\Theta^{1}) = 0.4 - 0.2*0.48=0.304$$

$$…$$

经过两次的梯度优化结果比之前要相对小一些

Matrix

在计算结果时我们一般借助矩阵来进行预测

如上图，我们已经有了$$h_{\theta}(x) = -40+0.25x$$，那么我们只需要构造如上图一样的矩阵，就可以同时算出四个结果对于python代码来说，这仅仅是一行矩阵相乘的代码。

以上就是关于单一变量变量的梯度下降算法

Gradient descent with multiple variables

$$Hypothesis:h_{\theta}(x) = \theta_{0} + \theta_{1}x_{1} + \theta_{2}x_{2}+\theta_{3}x_{3}+…+\theta_{n}x_{n}$$

$$Simplify:$$

Example2

假设$$J(\theta) = \theta_{1}^{2} + \theta_{2}^{2},同时\Theta^{0} = (1,3),\alpha=0.1,\nabla J(\Theta) = <2\theta_{1},2\theta_{2}>$$

$$\Theta^{0} = (1,3)$$

$$\Theta^{0} = \Theta^0-\alpha\nabla J(\Theta^{0}) = (1,3)-0.1*(2,6) = (0.8,2.4)$$

$$\Theta^{1} = \Theta^1-\alpha\nabla J(\Theta^{1}) = (0.8,2.4)-0.1*(1.6,4.8) = (0.64,1.92)$$

$$…$$

同样经过两次的梯度优化结果比之前要相对小一些

Feature Scaling

一般来说我们要保证$$-1\leq x_{i} \leq 1$$，当然，如果在这个区间附近，我们也可以接受，但是范围不能太大或太小。

Mean normalization

Replace $$x_i$$with $$x_i-\mu_i$$ to make features have approximately zero mean (Do not apply to $$x_0=1$$)

E.g.

$$x_1=\frac{size-1000}{2000}$$

$$x_2=\frac{bedrooms-2}{5}$$

1000 and 2 are mean value of the size of houese and the number of bedrooms

After the mean normalization,

$$-0.5\leq x_1 \leq 0.5,-0.5 \leq x_2 \leq 0.5$$

$$x_i=\frac{x_i-\mu_i}{s_i},\mu_i \rightarrow avg,s1\rightarrow maximum -minimum$$

$$h_{_\theta}(x) = W^{T}x$$