[學習筆記] 機器學習: 單變數線性回歸 (Machine learning: Linear Regression with One Variable)

Model of Supervised Learning



Supervised learning 的目標是要讓 learning algorithm 能夠根據 training set 學習到 function h, 使得 h(x) 能夠盡可能準確地預測 y.
h: hypothesis function.
當我們要預測的 y 是 continuous value, 此 learning problem 稱之為 regression problem.

當我們要預測的 y 是 discrete value, 此 learning problem 稱之為 classification problem.

舉例: 給定 20 組房屋坪數及其成交價的資料。對於坪數為 x 的房屋,預測其成交價 y。
Training set: 20 組房屋坪數及其成交價的資料

x: 坪數

y: 成交價

Linear regression with one variable



此 model 稱為 linear regression with one variable, 又稱為 univariate linear regression.

Cost Function



Cost function J(θ01) 又稱為 squared error function 或 mean squared error.


目標是要找出 θ01, 使得 cost function J(θ01) 是 minimized, 而使得 hθ(x) 能夠盡可能接近 y, for training examples (x,y).

Cost Function Intuition I






Cost Function Intuition II



對於特定的一組 θ0, θ1, hθ(x) is a function of x:


對於每一組 θ0, θ1, 都可以計算出 J(θ0, θ1):


以 contour plot 的形式來描繪 J(θ0, θ1), 在同一條曲線上, J(θ0, θ1) 的值是相同的:


下圖選定的 θ0, θ1 對應的 hθ(x) 比上圖的更接近 y, for training examples (x,y), 因此 cost function J(θ0, θ1) 的值比上圖更接近最低點:


當選定的 θ0, θ1 使得 hθ(x) 最可能接近 y, for training examples (x,y), 此時 cost function J(θ0, θ1) 的值處於最低點:


Gradient Descent


Gradient Descent 可以用來解決此問題: 給定 cost function J(θ0, θ1, ..., θn), 找出 θ0, θ1, ..., θn, 使得 J(θ0, θ1, ..., θn) 的值是 local minimum.

Gradient Descent Algorithm:


α: learning rate, 決定每一次的 iteration, 走的步伐有多大

Simultaneous update (以 n = 1 為例):


以 n = 1 為例, 首先選擇任一組 θ0, θ1, 然後在每一次的 iteration, 以 α 的步伐往最陡的方向往下走, 直到走到 local minimum:


當初始選定的 θ0, θ1 不同, 最終可能會走到不同的 local minimum:


Gradient Descent Intuition


以下圖為例, 對 J(θ1) 微分, 意義為在 θ1 這一點取切線, 而斜率為正值, 因此進行了一次 iteration 後, θ1 會往左邊跑, 而朝 local minimum 接近:


以下圖為例, 對 J(θ1) 微分, 意義為在 θ1 這一點取切線, 而斜率為負值, 因此進行了一次 iteration 後, θ1 會往右邊跑, 而朝 local minimum 接近:


如果 α 較小, 每一次 iteration 走的步伐較小, 會收斂得比較慢:


如果 α 太大, 可能會無法收斂, 甚至可能會發散:


如果 θ1 在 local minimum, 因為斜率為 0, 因此進行了一次的 iteration 後, θ1 的值不會改變, 仍然會停留在 local minimum:


由下圖可見, 每次的 iteration, 斜率會逐漸變小, 因此雖然 α 是固定的, 每一次 iteration 走的步伐仍會越來越小, 而逐漸走到 local minimum, 因此並不需要隨著 iteration 去降低 α:


Gradient Descent for Linear Regression


把 Gradient Descent Algorithm 用來解決 Linear Regression 問題:


需要把 Linear Regression 裡的 cost function J(θ0, θ1) 進行偏微分, 代入 Gradient Descent Algorithm:


對於 Linear Regression 問題, Cost Function 是 Bowl-shaped, 因此只有唯一的 global minimum:


下圖舉例說明, 首先選取了初始的一組 (θ0, θ1) = (900, -0.1), 以 Gradient Descent Algorithm 進行了 8 次的 iteration 後, cost function J(θ0, θ1) 達到了 global minimum, 而 hypothesis hθ(x) 的準確度也提升到最高水平.

這裡提到的 Gradient Descent Algorithm 稱之為 batch gradient descent, 因為在每一次的 iteration, 使用了整個 training set 裡的每一筆資料.

延伸閱讀


[Coursera] Machine Learning: Linear Regression with One Variable, by Andrew Ng, Stanford University