开心六月综合激情婷婷|欧美精品成人动漫二区|国产中文字幕综合色|亚洲人在线成视频

梯度下降和牛頓法都是用來(lái)求解最優(yōu)化問(wèn)題的，在機(jī)器學(xué)習(xí)中應(yīng)用甚廣，尤其是梯度下降，它在各種分類和回歸模型的求解中都會(huì)用到。那什么是梯度下降，什么是牛頓法呢，本文就帶你一探究竟。

梯度下降

假定最優(yōu)化的目標(biāo)是求解使得

1 初始化待估參數(shù)

初始化

2 循環(huán)迭代

采用如下公式對(duì)待估參數(shù)就行循環(huán)迭代：

其中，

為步長(zhǎng)，如果步長(zhǎng)太小，迭代可能導(dǎo)致太慢，如果步長(zhǎng)太大，可能可能跳過(guò)局部最小值，不能保證收斂，所以計(jì)算時(shí)需要選取合適的

3 計(jì)算完成

當(dāng)

實(shí)際上，上述梯度下降算法為批量梯度下降，本文以僅此為例來(lái)講解，因?yàn)楫?dāng)你理解之后你會(huì)發(fā)現(xiàn)，其他類型的梯度下降算法均為此算法的變種。

牛頓法

待優(yōu)化問(wèn)題同上述梯度下降算法。

1 初始化待估參數(shù)

同上。

2 循環(huán)迭代

循環(huán)迭代的公式如下：

其中，

3 計(jì)算完成

當(dāng)

R語(yǔ)言實(shí)現(xiàn)

了解了兩種算法的基本概念后，我們嘗試封裝R函數(shù)，來(lái)實(shí)現(xiàn)對(duì)一元線性回歸模型系數(shù)的估計(jì)。

1 樣例數(shù)據(jù)

采用蒙特卡洛模擬生成一組變量數(shù)據(jù)x和y：

# generate random data 
# y ~ a + b*x
set.seed(2017)
n <- 100
x <- runif(n,1,10)
y <- x + rnorm(n)
plot(x,y,pch=20,main = "Monte Carlo Simulation for Simple Linear Regression")

可以看到這兩組數(shù)據(jù)之間存在明顯的線性相關(guān)。于是我們可以采用一元線性回歸模型去擬合，形如：

求解上述模型就是要估計(jì)出上式中截距項(xiàng)

2 編寫函數(shù)

構(gòu)造普通線性回歸的損失函數(shù)：

梯度下降和牛頓算法的目的就是要極小化上述殘差平方和。上代碼：

# gradient descent algorithm
gd <- function(x,y,a0,a1,alpha=0.01,tol=1e-5,M=5000){  # Args:  #   x     -- independent variable  #   y     -- dependent variable  #   a0    -- initial value for intercept  #   a1    -- initial value for slope  #   alpha -- step size  #   tol   -- tolerance  #   M     -- Maximum Iterations    # Returns:  # Iterated value sequence, is a dataframe.      i <- 1  res <- data.frame(a0=a0,a1=a1)  repeat{        J0 <- 1/2*sum((a0+a1*x-y)^2)    a0_hat <- a0 - alpha*mean(a0+a1*x-y)    a1_hat <- a1 - alpha*mean((a0+a1*x-y)*x)        a0 <- a0_hat    a1 <- a1_hat    J1 <- 1/2*sum((a0_hat+a1_hat*x-y)^2)        res <- rbind(res,data.frame(a0=a0,a1=a1))        if( abs(J1-J0) < tol | i >= M )      break    i <- i + 1  }  return(res)
}

# Newton's method
nt <- function(x,y,a0,a1,tol=1e-5,M=500){  # Args:  #   x     -- independent variable  #   y     -- dependent variable  #   a0    -- initial value for intercept  #   a1    -- initial value for slope  #   tol   -- tolerance  #   M     -- Maximum Iterations    # Returns:  # Iterated value sequence, is a dataframe.      i <- 1  res <- data.frame(a0=a0,a1=a1)    repeat{        J0 <- 1/2*sum((a0+a1*x-y)^2)    a0_hat <- a0 - mean(a0+a1*x-y)    a1_hat <- a1 - mean((a0+a1*x-y)*x)/mean(x^2)            a0 <- a0_hat    a1 <- a1_hat    J1 <- 1/2*sum((a0_hat+a1_hat*x-y)^2)        res <- rbind(res,data.frame(a0=a0,a1=a1))    if( abs(J1-J0) < tol | i >= M )      break    i <- i + 1  }  return(res)
}

3 對(duì)比算法效果

查看梯度下降和牛頓算法的效果，并將其與系統(tǒng)自帶函數(shù)的估計(jì)結(jié)果做對(duì)比：

# compare two algorithms
res.gd <- gd(x = x,y = y,a0 = 0,a1 = 0,tol=1e-8)
tail(res.gd,1)

##             a0        a1## 2964 0.2515242 0.9429152

res.nt <- nt(x = x,y = y,a0 = 0,a1 = 0,tol=1e-8)
tail(res.nt,1)

##            a0        a1## 123 0.2520766 0.9428287

# use lm function
fit <- lm(y~x)
(a <- coef(fit))

## (Intercept)           x ##   0.2520778   0.9428331

可以看到，梯度下降經(jīng)過(guò)2964步后收斂，牛頓算法經(jīng)過(guò)僅僅123步就收斂。這是因?yàn)榕ｎD算法考慮了二階導(dǎo)，即梯度的變化，所以他在迭代次數(shù)上顯得比梯度下降更有優(yōu)勢(shì)。

3 迭代路徑可視化

# plot for gradient descent algorithm 
nr <- nrow(res.gd)
ind <- c(1:10,1:floor(nr/100)*100,nr)
a0 <- res.gd$a0[ind]
a1 <- res.gd$a1[ind]
plot(a0,a1,cex=0.5,xlim = c(0,0.3),ylim = c(0,1),pch=20,main = "Gradient Descent Algorithm")
arrows(head(a0,-1),head(a1,-1),tail(a0,-1),tail(a1,-1),length=0.05)
points(a[1],a[2],col=2,cex=1.5,pch=20)

# plot for Newton's method 
a0 <- res.nt$a0
a1 <- res.nt$a1
plot(a0,a1,xlim = c(0,6),ylim = c(0,1),pch=20,main = "Newton's method")
arrows(head(a0,-1),head(a1,-1),tail(a0,-1),tail(a1,-1),length=0.08)
points(a[1],a[2],col=2,cex=1.5,pch=20)

總結(jié)

梯度下降算法和牛頓法各有優(yōu)劣：

梯度下降法考慮了目標(biāo)函數(shù)的一階偏導(dǎo)、以負(fù)梯度方向作為搜索方向去尋找最小值，需要認(rèn)定合適的步長(zhǎng)，迭代次數(shù)多，容易陷入局部最小值。

牛頓法同時(shí)考慮了目標(biāo)函數(shù)的一、二階偏導(dǎo)數(shù)，相當(dāng)于考慮了梯度的梯度，所以能確定合適的搜索方向加快收斂，但牛頓法要求也更嚴(yán)格，目標(biāo)函數(shù)必須存在連續(xù)的一、二階偏導(dǎo)數(shù)，且海森矩陣必須正定，迭代次數(shù)雖少，但是當(dāng)待估參數(shù)較多時(shí)，單次的運(yùn)算量會(huì)遠(yuǎn)大于梯度下降算法。

所以在具體的數(shù)據(jù)分析和挖掘中，需要權(quán)衡利弊后再選擇更為合適的算法。