GradientDescent
Pham Dinh Khanh
April 12, 2018
GRADIENT DESCENT
Trong các bài toán tối ưu hóa, qui hoạch tuyến tính và bất đẳng thức thì Gradient descent là một phương pháp phổ biến để tính toán các điểm cực trị địa phương của 1 hàm số. Ý tưởng của Gradient descent là tìm ra một phương tối ưu mà đi theo phương đó hàm số sẽ đạt được cực tiểu. Do đó trong thuật toán Gradient descent luôn phải có điểm xuất phát, phương di chuyển và tốc độ di chuyển. Điểm xuất phát là điểm khởi tạo của vòng lặp, tốc độ di chuyển hay còn gọi là learning rate là giá trị qui định sau mỗi vòng lặp sẽ dịch chuyển theo phương gradient descent với độ lớn là bao nhiêu. Phương di chuyển chính là hướng để đi đến điểm cực trị địa phương được tính theo Gradient descent.
- Mô tả về gradient descent: Gradient descent được tính toán dựa trên các quan sát của một hàm đa biến F(x) xác định và khả vi tại các điểm lân cận của a, khi đó F(x) giảm nhanh nhất khi đi từ a theo phương của gradient descent của F tại điểm a kí hiệu \(-\Delta F(a)\). Do đó nếu: \[a_{n+1} = a_{n} - \alpha \Delta F(a_{n})\] Với \(\alpha\) là tốc độ hội tụ đủ lớn thì \(F(a_{n}) \geq F(a_{n+1})\). Hay nói cách khác nhân tử \(\alpha \Delta F(a_{n})\) là phần được trừ đi từ a bởi chúng ta muốn di chuyển nhanh hơn tới điểm minimum dựa trên phương gradient. Với các quan sát xác định trước chúng ta bắt đầu với một điểm giả định \(x_{0}\) cho cực trị địa phương của F, và xét chuỗi \(x_{0},x_{1},x_{2},…\) sao cho: \[x_{n+1} = x_{n} - \alpha_{n} \Delta F(a_{n}), n \geq 0\] Chúng ta có: \[F(x_{0}) \geq F(x_{1}) \geq F(x_{2}) \geq ….\] Và chúng ta kì vọng chuỗi \(x_{n}\) sẽ hội tụ tới điểm cực trị địa phương. Chú ý rằng trong phương trình trên tốc độ hội tụ được kí hiệu là \(\alpha_{n}\) có nghĩa là nó được phép thay đổi sau mỗi bước hội tụ. Với một vài giả định về hàm F (chẳng hạn như F lồi và \(\Delta F\) liên tục dạng lipschipz) thì lựa chọn \(\alpha\) như sau: \(\alpha_{n} = \frac{(x_{n}-x_{n-1})^T[\Delta F(x_{n})-\Delta F(X_{n-1})]}{||\Delta F(x_{n})-\Delta F{x_{n-1}}||^2}\)
sẽ đảm bảo hàm số hội tụ đến cực trị địa phương. Mặt khác khi F(x) là hàm convex thì cực trị địa phương chính là cực trị toàn cục nên gradient descent có thể hội tụ tới điểm cực trị toàn cục khi F(x) là hàm lồi.
SỬ DỤNG GRADIENT DESCENT TÍNH TOÁN CỰC TIỂU ĐỐI VỚI ĐA THỨC
R code sau đây sẽ sử dụng tư tưởng cuả Gradient descent để tính toán cực tiểu của hàm số \(f(x) = x^4-2x^3+1\).
Phương trình đạo hàm: \[\Delta f(x)=4x^3-6x^2\] Khi đó sau mỗi vòng lặp giá trị của \(x\) sẽ được update theo phương của gradient descent như sau:
\(x_{n+1}=x_{n} - \alpha \Delta f(x_{n}) = x_{n} - \alpha (4x_{n}^3-6x_{n}^2)x_{n}\)
với \(k=1,2,...\) là các bước hội tụ và \(\alpha\) là learning rate.
Thực hiện vòng lặp trên code
library(ggplot2)
#thiet lap learning rate
alpha = 0.003
#thiet lap so buoc hoi tu
iter = 500
#ham f(x)
f <- function(x) (x^4-2*x^3+1)
#ham gradient cua f(x)=x^4-2x^3+1
gradient = function(x) return(4*x^3-6*x^2)
#Lua chon random diem xuat phat x_0
set.seed(100)
x = floor(runif(1)*10)
#Khoi tao vector luu tru ket qua cua x_i sau moi vong lap
x.All = vector("numeric")
f.All = vector("numeric")
#Gradient descent de tim gia tri cuc tieu
for(i in 1:iter){
x = x-alpha*gradient(x)
x.All[i] = x
fx <- f(x)
f.All[i] = fx
}
resultDf <- data.frame(x.All, f.All)
ggplot(resultDf, aes(x.All,f.All)) +
geom_line() +
geom_point(color="blue") +
labs(
title="Gradient descent convergence to minimum",
subtitle="Created by Pham Dinh Khanh",
caption="fx = x^4-2x^3+1",
x="x",
y="f(x)"
)
ỨNG DỤNG GRADIENT DESCENT ĐỐI VỚI BÀI TOÁN HỒI QUI TUYẾN TÍNH
Gradient descent có thể được sử dụng để ước lượng các phương trình tuyến tính trong các ước lượng OLS, Bài toán được qui về tìm cực trị địa phương của đa thức bậc 2 sử dụng phương pháp tổng bình tương tuyến tính nhỏ nhất.
- Phương pháp:
Giả sử chúng ta có X là matrix các biến ước lượng \[X = [X_{1},X_{2},…,X_{n}]\] Trong đó \(X_{i}\) là vector dòng của matrix X. \(X{i} = (x_{1},x_{2},…,x_{n})\) đại diện cho biến ước lượng thứ i của model. \(Y\) là vector biến được ước lượng. \[Y = (y_{1},{y_2},…,y_{n})^{T}\] vector \(\theta\) là vector hệ số ước lượng \[\theta = (\theta_{1},\theta_{2},…,\theta_{t})^{T}\] Khi đó chúng ta cần xác định \(\theta\) sao cho tổng bình phương sai số ngẫu nhiên là nhỏ nhất hay hàm Loss sau đây là nhỏ nhất: \(F(\theta) = \frac{1}{2n}\sum_{i=1}^{n} (\theta^{T}X_{i}-Y_{i})^2 \rightarrow min\) Hàm Gradient descent trong trường hợp này: \[\frac{\Delta F(\theta)}{\Delta\theta_{i}}=\frac{1}{n}\sum_{j=1}^{n} (\theta^{T}X_{i}-Y_{i})X_{i}\]
Sau mỗi vòng lặp giá trị của \(\theta\) sẽ được hội tụ như sau:
\[\theta_{i_{n+1}} := \theta_{i_{n}} - \alpha \frac{\Delta F(\theta)}{\Delta \theta_{i_{n}}} \] Trong đó n là các bước lặp. Quá trình hội tụ của các \(\theta_{i}\) khác nhau là đồng thời. Tức là trong quá trình \(\theta_{i}\) di chuyển theo gradient descent thì \(\theta_{j}\) cũng di chuyển theo gradient descent.
- Bài toán:
Sử dụng bộ số liệu mtcars. Giả sử chúng ta cần tìm mối liên hệ tuyến tính giữa mức tiêu thụ năng lượng/1 dặm mpg và dung tích động cơ disp của các dòng xe. Ta sẽ áp dụng gradient descent để tìm ước lượng không chệch của các hệ số \(\theta\).
attach(mtcars)
gradientDesc <- function(x, y, learn_rate, conv_threshold, n, max_iter) {
plot(x, y, col = "blue", pch = 20)
m <- runif(1, 0, 1)
c <- runif(1, 0, 1)
yhat <- m * x + c
MSE <- sum((y - yhat) ^ 2) / n
converged = F
iterations = 0
while(converged == F) {
## Implement the gradient descent algorithm
m_new <- m - learn_rate * ((1 / n) * (sum((yhat - y) * x)))
c_new <- c - learn_rate * ((1 / n) * (sum(yhat - y)))
m <- m_new
c <- c_new
yhat <- m * x + c
MSE_new <- sum((y - yhat) ^ 2) / n
if(MSE - MSE_new <= conv_threshold) {
abline(c, m)
converged = T
return(paste("Optimal intercept:", c, "Optimal slope:", m))
}
iterations = iterations + 1
if(iterations > max_iter) {
abline(c, m)
converged = T
return(paste("Optimal intercept:", c, "Optimal slope:", m))
}
}
}
gradientDesc(disp, mpg, 0.0000293, 0.001, 32, 2500000)
## [1] "Optimal intercept: 29.5998514965367 Optimal slope: -0.0412151089213438"Hoặc nếu không muốn dùng vòng while ta có thể dùng vòng for như sau:
attach(mtcars)
gradientDesc <- function(x, y, learn_rate, conv_threshold, max_iter) {
plot(x, y, col = "blue", pch = 20)
m <- runif(1, 0, 1)
c <- runif(1, 0, 1)
yhat <- m * x + c
n <- length(x)
MSE <- sum((y - yhat) ^ 2) / n
for(i in 1:max_iter){
m_new <- m - learn_rate * ((1 / n) * (sum((yhat - y) * x)))
c_new <- c - learn_rate * ((1 / n) * (sum(yhat - y)))
m <- m_new
c <- c_new
yhat <- m * x + c
MSE_new <- sum((y - yhat) ^ 2) / n
if(MSE - MSE_new < conv_threshold){
abline(c, m)
return(paste0("Optimal intercept:",c, " Optimal slope:", m," Iterations:", i," MSE min:",MSE_new))
}
}
abline(c, m)
return(paste0("Optimal intercept:",c, " Optimal slope:", m," Iterations:", max_iter," MSE min:",MSE_new))
}
gradientDesc(disp, mpg, 0.0000293, 0.001, 2500000)
## [1] "Optimal intercept:29.5998514871919 Optimal slope:-0.0412151088896899 Iterations:2500000 MSE min:9.91120904007061"Kết quả của hệ số ước lượng khi sử dụng hồi qui ols:
lm(mpg ~ disp)##
## Call:
## lm(formula = mpg ~ disp)
##
## Coefficients:
## (Intercept) disp
## 29.59985 -0.04122Ta thấy 2 kết quả không chênh lệch nhau quá nhiều chứng tỏ thuật toán gradient descent đã đến được đúng điểm tối ưu.