Gradient Descent Algorithm

从生活中的例子我们可以发现，房价和房屋面积是近似成正比的，城市面积和人口是近似成正比的，在很多情况下，我们都可以用linear function来拟合现实中的情况，而有的时候，比如我们知道房屋的长和宽以及价格，如果长、宽做feature来预测价格的话，显然很难预测，这时我们就可以把长宽相乘得到新的feature即房屋面积，用面积做feature来预测，这样又可以用linear fucntion来拟合数据。

而很多时候我们又会发现数据的分布不是线性相关的，可能更接近 y = x^3，或者 y = x^-1等等函数图像，这时仍然是一个计算新feature的问题，我们把x^3,x^-1等等作为新的feature，就又将问题转换为寻找最合适的linear function的问题了。

我们已经讨论过了hypothesis是linear function的情况，gradient descent就是一个用来寻找最符合输入数据分布的linear function 的方法，也就是一个linear regression方法。

• 目的：求出局部最优的hypothesis:H(x)(使cost function J(θ1,θ2,…) 局部最优)

• 定义:

• cost function：J(θ1,θ2,…)

• J(θ1,θ2,…)的梯度(即导数):d(J)/d(θ), 如d(J)(θ1,θ2,…)/d(θ1)即J在(θ1,θ2,…)处关于θ1的导数

• 步骤

• (1):选取一个起点:Point:(a1,b1,…)，J(a1,b1,…)

• (2) θ1 := θ1 - α * d(J)/d(θ1)(a1,b1,…)，不断替换θ1,θ2,… ，直到最终收敛(convergence)。

gradient descent实际上就是在某一个hypothesis的cost function值上向四周看，找到cost function下降的那个方向，然后向那个方向更改参数，得到一个新的hypothesis，重复这个过程，直到到达cost function的最低点。

对于复杂的函数，Gradient Descent只能找到一个局部最优的解，但是对于Hypothesis 是 linear function的情况，Gradient肯定能找到一个全局最优的解。

如图，对于y = θx+θ0这种形式的hypothesis，θ取值不同对应的cost function值也不同，如图一和图二所示，gradient descent就是要找到图中的最低点

matlab示例

theta_for = theta;
for iter = 1:num_iters
    for thetaindex = 1:size(X,2)
        theta(thetaindex) = theta(thetaindex) - alpha / m * sum((X * theta_for - y) .* X(:,thetaindex));
    end
    theta_for = theta;
    J_history(iter) = computeCostMulti(X, y, theta);
end

α控制每一步迈出的大小

• 太小增加了循环的次数

• 太大会越过optimize point，无法达到convergence

Batch :

Batch GD Algorithm是指使用了所有数据的GD Algorithm