線性模型的封閉解與數值解

在前幾日,小編與同事的機器學習的讀書會中,與同事討論到了關於線性模型的參數最佳解,對於學統計或數學背景的人來說,如果模型存在封閉解,模型參數會存在最佳且唯一解是必然的事。並且在模型存在封閉解的情況下,將蒐集的資料帶入封閉解的公式,得到的就是最好的估計參數。然而資工背景的訓練下,認為一定要將資料分成 training set, validation set, testing set. 然後 climbing 找到最佳的參數解才是最全面的作法。姑且不論誰優誰劣,這篇嘗試創造假資料,利用最小平方法與 gradient desent 預測的簡單線性模型,比較兩個方法找到的最佳參數的差異。

封閉解 (Closed-form solution)

封閉解又稱解析解 (Analytical solution) 為一個數學表示式,以已知的數學運算表達 (e.g +, -, *, /) 或三角函數、指數、對數等等,得到的值為有限的數值。利用數學方法得到問題的唯一答案。以簡單線性回歸 Y = \beta_0 + \beta_1 X + \varepsilon  為例,我們設定 Lose function 為 L = \Sigma_{i=1}^n ( y - \hat y)^2,   \hat y =  \hat{\beta_0} + \hat{\beta_1} x可以使用最小平方法得到簡單線性模型的封閉解 \hat{\beta_1} = \frac{S_{xy}}{S_{xx}}, \hat{\beta_0} = \bar{Y} - \hat{\beta_1} \bar{X}

數值解 (Numerical solution

利用演算法估計最佳解,如 gradient desent,當無法透過數學方法得到封閉解時,便只能透過數值分析方法得到得到接近最佳解的數值。這裡透過 gradient desent 不斷修正模型,嘗試找到最小的 Cost。

R 實作

創造資料

創造一組資料,令 y 等於 x 加上 3 和 來自 N(0,1) 的雜訊。從這樣的上帝視角來看資料,可以了解到真正的模型來自 y = 3 + x + \varepsilon

x <- runif(1000, -5, 5)
y <- 3 + x + rnorm(1000)

最小平方法

在這裡小編直接使用最小平方法得到的最佳解 \hat{\beta_1} = \frac{S_{xy}}{S_{xx}}, \hat{\beta_0} = \bar{Y} - \hat{\beta_1} \bar{X}

sxy <- sum((x - mean(x))*( y - mean(y)))
sxx <- sum((x - mean(x))^2)

b1 <- sxy/sxx
b0 <- mean(y) - b1*mean(x)

# plot the data and the model
plot(x,y, col=rgb(0.2,0.4,0.6,0.4), main='Linear regression by least squares')
abline(a=b0, b=b1 ,col='blue')

linear_closed

Gradient desent

在這裡使用 gradient desent 方法,設定 learning rate 為 0.01,訓練 10000 次。

# squared error cost function

cost <- function(X, y, theta) {
  sum( (X %*% theta - y)^2 ) / (2*length(y))
}

# learning rate and iteration limit

alpha <- 0.01
num_iters <- 10000

# keep history
cost_history <- double(num_iters)
theta_history <- list(num_iters)

# initialize coefficients

theta <- matrix(c(0,0), nrow=2)

# add a column of 1's for the intercept coefficient

X <- cbind(1, matrix(x))

# gradient descent

for (i in 1:num_iters) {
  error <- (X %*% theta - y)
  delta <- t(X) %*% error / length(y)
  theta <- theta - alpha * delta
  cost_history[i] <- cost(X, y, theta)
  theta_history[[i]] <- theta
}

print(theta)

# plot cost decreasing of greadient desent

plot(cost_history, type='line', col='blue', lwd=2, main='Cost function', ylab='cost', xlab='Iterations')

linear_cost

# plot data and converging fit

plot(x,y, col=rgb(0.2,0.4,0.6,0.4), main='Linear regression by gradient descent')
for (i in c(1,3,6,10,14,seq(20,num_iters,by=10))) {
  abline(coef=theta_history[[i]], col=rgb(0.8,0,0,0.3))
}

abline(coef=theta, col='blue')

linear_gradient

上圖紅色的線為模型的調整過程,最後得到的結果是藍色的線,也就是以 gradient desnet 逼近 10000次後的最佳結果。

#compare two solutions

plot(x,y, col=rgb(0.2,0.4,0.6,0.4), main='Linear regression by gradient descent & least square')
abline(coef=theta, col='blue')
abline(res, col = 'green')
legend(-4.5,9, c("least square", "gradient descent"), 
       lty = c(1,1),lwd=c(2.5,2.5),col=c('green','blue'),
       border.col = "white")

linear_compare

最後將最小平方法和 gradient desent 的結果畫在同一張圖看看有什麼不一樣,可以發現,不管是最小平方法還是 gradient desent 結果都相當接近。

結論

以小編創造的資料來看,不論是封閉解或數值解,最後都會得到參數非常接近的模型,有趣的是兩個出發點不同的方法,卻得到一樣的結果。但是在處理實際資料時兩邊都會有自己的盲點與缺點,數學方法會受限於模型假設不符合實際狀況,或不存在封閉解;而數值方法則則會遇到模型過度最佳化,或是訓練時間過長等問題。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s