gradient descent algorithm for multivariate linear regression

目標函數:
$h_w (x) = w_0 + w_1 x_1 + w_2 x_2 + \cdots +w_nx_n$

演算法:
$w_j \leftarrow w_j - \alpha \frac{1}{m} \sum\limits_{i=1}^{m} (h_w(x^{(i)}) - y^{(i)}) \cdot x_j^{(i)} \; \text{for j = 0...n}$
$do$ $this$ $until$ $convergence$

其中:
$x_j^{(i)} :\text{第j組資料的第i個特徵}$
$x^{(i)}:\text{由第i組資料的所有特徵組成的column vector}$
$m  : \text{餵的資料組數}$
$n  :\text{特徵的數量}$


我想第一眼看到這個演算法應該頗傻眼吧,感覺很複雜,其實還好,這個演算法在machine learning中被稱為gradient descent algorithm,主要是用來從資料中學習的演算法
我想有學過線性代數的人都知道最小平方法,其重點是求出一條直線,使直線和其他點的平方誤差最小,這個演算法也是類似道理,希望從資料中得到誤差最小的直線,至於如何做呢,就如同上面提到的演算法一樣,利用逐次逼近來使目標函數誤差最小,其中選取$\alpha$是一門學問,選太小會使演算法收斂太慢,選太大可能會導致演算法無法收斂,因此實務上選取$\alpha$都是慢慢嘗試,這個演算法因為是採用嘗試的,且一旦到local minima就不會動了,因此可能找到的不會是全域最佳解(不過在linear regression的情況下並不會發生local manima的情況)! 這個想法非常好用,並不只限於線性回歸,以後會再出現歐XD

gradient descent 方法有一些優化的方法:
1. feature scaling
2. stochastic gradient descent
3. adagrad



資料來源:
1. coursera: machine learning by andrew ng
2. artificial intelligence a modern approach 3rd
3. 李宏毅教授youtube