Log

2022.01.14開始本章學習
2022.01.15把剩下的弄完

一、過擬合問題（overfitting）

①線性回歸中的過擬合問題

• 仍然用房價預測的例子來解釋什么是過擬合
  

• 欠擬合（underfitting）： 最開始的線性擬合（上圖左），這個演算法并沒有很好地擬合訓練集，即這個演算法具有高偏差（high bias），

• 剛剛好（just right）： 上圖中間添加了二次項的式子則能很好地擬合資料，

• 過擬合（overfitting）： 最后一個四階多項式擬合的演算法（上圖右）看似可以很好地擬合資料，因為通過了所有的資料點，但是這是一條不斷上下波動的曲線，所以并不認為是一個很好的模型，即過擬合，也可以說是具有高方差（high variance），過擬合問題的表現是假設函式太過龐大，變數太多，沒有足夠的資料來約束他（給定的資料都被很好地擬合），

• 過擬合問題會在變數過多時出現，這時訓練出的假設能很好地你和訓練集，代價函式可能十分接近 0 ，但是會得到上圖右的影像，努力的去迎合給定的資料導致它無法泛化到新的樣本中（無法預測新的樣本價格），該說法同樣可以應用到邏輯回歸中，

②邏輯回歸中的過擬合問題

• 左面的擬合的不夠好，即欠擬合；中間的擬合的比較好；右面的則是過擬合，加入了很多高階項來符合所有預測，導致影像變得扭曲

③如何解決過擬合問題

• 首先要明確，過擬合問題一般出現在變數（特征）過多，樣本資料過少的情況下，所以根據問題產生的這兩個原因，就得到了以下對應的解決方法：
  1. 減少選取變數的數量
     ①人工挑選保留那些特征（manually select）
     ②通過模型選擇演算法（model selection algorithm）來解決（后續會講到）
     （舍棄特征量的缺點在于，舍棄變數的同時也舍棄了一部分資訊，而有時所有資訊都是有用的）
  2. 正則化（regularization）
     ①保留所有特征，但是減少量級（magnitude），或是減少引數 θ_j 的大小
     ②當有很多變數時，這種方法非常有效，其中的每一個變數都能對預測的 y 值產生一點影響（或多或少都是有用的）

二、代價函式（正則化的應用）

①正則化的思想

• 圖左為剛好擬合，圖右為過擬合，下面說明如何實作正則化，

• 根本目的：簡化假設函式

• 直接目標：減少 θ3，θ4 的量級（或大小）

• 具體實作：通過添加懲罰項（Penalty）

• 原來的優化目標（要最小化其均方誤差代價函式）：
  min ? θ 1 2 m ∑ i = 1 m ( h θ ( x ( i ) ) ? y ( i ) ) 2 {\min\limits_θ}\frac{1}{2m}\sum_{i=1}^m(h_θ(x^{(i)})-y^{(i)})^2 θmin?2m1?i=1∑m?(hθ?(x(i))?y(i))2

• 對其進行修改：
  min ? θ 1 2 m ∑ i = 1 m ( h θ ( x ( i ) ) ? y ( i ) ) 2 + 1000 θ 3 2 + 1000 θ 4 2 {\min\limits_θ}\frac{1}{2m}\sum_{i=1}^m(h_θ(x^{(i)})-y^{(i)})^2\blue{+1000θ_3^2+1000θ_4^2} θmin?2m1?i=1∑m?(hθ?(x(i))?y(i))2+1000θ32?+1000θ42?

• (1000只是任意的一個比較大的數)

• 如果要最小化修改后的函式，使其盡可能小的方法只有一個，就是使 θ3、θ4盡量小（因為二者在函式中的系數很大），變得近似于 0，在擬合的式中就相當于去掉了這兩項一樣（二次函式加上一些很小的項），得到新的擬合函式的影像如下：
  

• 以上內容就是正則化背后的思想：

• 正則化思想（如果引數值較小）

  1. 簡化假設模型
  2. 更不容易出現過擬合問題

②正則化的實作

• 對于具體的例子，很難預先挑選出相關度較低的變數，所以在正則化中要做的就是修改代價函式來縮小所有的引數，以線性回歸的代價函式為例：
  H o u s i n g : ? F e a t u r e s : x 1 , x 2 , . . . , x 100 ? P a r a m e t e r s : θ 0 , θ 1 , θ 2 , . . . , θ 100 J ( θ ) = 1 2 m [ ∑ i = 1 m ( h θ ( x ( i ) ) ? y ( i ) ) 2 + λ ∑ j = 1 n θ j 2 ] min ? θ J ( θ ) \begin{aligned} &Housing:\\ &\qquad-\ Features:x_1,x_2,...,x_{100}\\ &\qquad-\ Parameters:θ_0,θ_1,θ_2,...,θ_{100}\\ &\large J(θ)=\frac{1}{2m}[\sum_{i=1}^m(h_θ(x^{(i)})-y^{(i)})^2+\red{λ\sum_{j=1}^nθ_j^2}]\\ &{\min\limits_θ}J(θ) \end{aligned} ?Housing:? Features:x1?,x2?,...,x100?? Parameters:θ0?,θ1?,θ2?,...,θ100?J(θ)=2m1?[i=1∑m?(hθ?(x(i))?y(i))2+λj=1∑n?θj2?]θmin?J(θ)?

• 這里有一個細節就是求和函式是從 1 開始計數的，因此不對 θ0 進行處理，實際上這樣的影響也不大

• λ 是正則化引數，其作用為控制兩個不同目標之間的取舍（平衡），從而保持假設模型的相對簡單，避免出現過擬合情況，第一個目標與函式方括號里的第一項有關，想要更好地去擬合訓練集，第二個目標與括號里的第二項有關，想要保持引數盡量小，與正則化目標有關

• 當 λ 取值過大時，導致對 θ1 到 θn 的懲罰度過大，每一個引數的值都接近于 0 ，使得函式中只剩下了 θ0，影像呈現為一條水平直線，發生欠擬合問題，

三、線性回歸的正則化（Regularized linear regression）

• 主要內容：將之前線性回歸中所學的兩種推導演算法，分別基于梯度下降和正規方程，推廣到正則化線性回歸中去，

1. 梯度下降

• 在沒有正則化的情況下進行常規的線性回歸使用梯度下降：
  R e p e a t { θ 0 : = θ 0 ? α 1 m ∑ i = 1 m ( h θ ( x ( i ) ) ? y ( i ) ) x 0 ( i ) θ j : = θ j ? α 1 m ∑ i = 1 m ( h θ ( x ( i ) ) ? y ( i ) ) x j ( i ) ( j = 0 , 1 , 2 , . . . , n ) } \begin{aligned} &Repeat\{ \\ &θ_0:=θ_0-α\frac{1}{m}\sum_{i=1}^m (h_θ(x^{(i)}) - y^{(i)} )x^{(i)}_0\\ &θ_j:=θ_j-α\frac{1}{m}\sum_{i=1}^m (h_θ(x^{(i)}) - y^{(i)} )x^{(i)}_j\qquad(j=\red{\bcancel{0}},1,2,...,n) \\ &\} \end{aligned} ?Repeat{θ0?:=θ0??αm1?i=1∑m?(hθ?(x(i))?y(i))x0(i)?θj?:=θj??αm1?i=1∑m?(hθ?(x(i))?y(i))xj(i)?(j=0 ?,1,2,...,n)}?
• （由于懲罰項中不含有 θ0，故上式中將 θ0 對應項單獨寫出）
• 更新了正則化后只對剩下的項進行了修改：
  θ j : = θ j ? α [ 1 m ∑ i = 1 m ( h θ ( x ( i ) ) ? y ( i ) ) x j ( i ) + λ m θ j ] ( j = 1 , 2 , . . . , n ) θ_j:=θ_j-α\left[\frac{1}{m}\sum_{i=1}^m (h_θ(x^{(i)}) - y^{(i)} )x^{(i)}_j+\red{\frac{λ}{m}θ_j}\right]\qquad(j=1,2,...,n) θj?:=θj??α[m1?i=1∑m?(hθ?(x(i))?y(i))xj(i)?+mλ?θj?](j=1,2,...,n)
• 不難看出，方括號中的內容是對正則化后的線性回歸的代價函式 J(θ) 求偏導后得到的結果，
• 將式子中和 θ 有關的項提出來合并可以得到以下等價的式子：
  θ j : = θ j ( 1 ? α λ m ) ? α 1 m ∑ i = 1 m ( h θ ( x ( i ) ) ? y ( i ) ) x j ( i ) θ_j:=θ_j(1-α\frac{λ}{m})-α\frac{1}{m}\sum_{i=1}^m (h_θ(x^{(i)}) - y^{(i)} )x^{(i)}_j θj?:=θj?(1?αmλ?)?αm1?i=1∑m?(hθ?(x(i))?y(i))xj(i)?
• 通常學習率 α 會比較小而 m 卻很大，所以合并后的 θ 的系數是一個略小于 1 的數，所以可以看成以下的式子，每次迭代都將引數縮小一點（向 0 更靠近一點），然后按照之前的梯度下降進行：
  θ j : = 0.99 ? θ j ? α 1 m ∑ i = 1 m ( h θ ( x ( i ) ) ? y ( i ) ) x j ( i ) θ_j:=0.99*θ_j-α\frac{1}{m}\sum_{i=1}^m (h_θ(x^{(i)}) - y^{(i)} )x^{(i)}_j θj?:=0.99?θj??αm1?i=1∑m?(hθ?(x(i))?y(i))xj(i)?

2. 正規方程

X = [ ( x ( 1 ) ) T . . . ( x ( m ) ) T ] y = [ y ( 1 ) . . . y ( m ) ] min ? θ J ( θ ) X=\left[\begin{matrix} (x^{(1)})^T\\ ...\\ (x^{(m)})^T\\ \end{matrix}\right]\qquad\qquad y=\left[\begin{matrix} y^{(1)}\\ ...\\ y^{(m)}\\ \end{matrix}\right]\\\quad\\ \min\limits_θJ(θ) X=???(x(1))T...(x(m))T????y=???y(1)...y(m)????θmin?J(θ)

• 沒有正則化時：
  θ = ( X T X ) ? 1 X T y θ=(X^TX)^{-1}X^Ty θ=(XTX)?1XTy
• 正則化后：
  θ = ( X T X + λ [ 0 1 1 . . . 1 ] ? ( n + 1 ) × ( n + 1 ) ) ? 1 X T y θ=\left(X^TX+\blue{\underbrace{λ\left[\begin{matrix} 0&\ &\ &\ &\ \\ \ &1&\ &\ &\ \\ \ &\ &1&\ &\ \\ \ &\ &\ &...&\ \\ \ &\ &\ &\ &1 \\ \end{matrix}\right]}_{(n+1)×(n+1)}}\right)^{-1}X^Ty θ=????????????XTX+(n+1)×(n+1) λ???????0 ? 1 ? 1 ? ... ? 1???????????????????????1XTy
• 對于不可逆的情況：
  • 當樣本數 m ≤ 特征數 n 時會出現 X’X 不可逆的情況（奇異矩陣/退化矩陣），
  • 在 Octave 中仍然可以使用 pinv 對不可逆的矩陣進行計算，但是在其他的編程語言的線性庫里是算不出來的，
  • 在正則化中已經考慮到了這一點，只要保證 λ 嚴格大于 0 （λ ＞ 0），那么以下式子就一定可逆：
    ( X T X + λ [ 0 1 1 . . . 1 ] ) ? 1 \left(X^TX+\blue{{λ\left[\begin{matrix} 0&\ &\ &\ &\ \\ \ &1&\ &\ &\ \\ \ &\ &1&\ &\ \\ \ &\ &\ &...&\ \\ \ &\ &\ &\ &1 \\ \end{matrix}\right]}}\right)^{-1} ???????XTX+λ???????0 ? 1 ? 1 ? ... ? 1????????????????1

四、邏輯回歸的正則化（Regularized logistic regression）

1. 梯度下降

• 邏輯回歸原來的代價函式：
  J ( θ ) = ? [ 1 m ∑ i = 1 m y ( i ) l o g ( h θ ( x ( i ) ) ) + ( 1 ? y ( i ) ) l o g ( 1 ? h θ ( x ( i ) ) ) ] J(θ)=-\left[\frac{1}{m}\sum^{m}_{i=1}{y^{(i)}}log(h_θ(x^{(i)}))+{(1-y^{(i)})}log(1-h_θ(x^{(i)}))\right] J(θ)=?[m1?i=1∑m?y(i)log(hθ?(x(i)))+(1?y(i))log(1?hθ?(x(i)))]
• 正則化以后：
  J ( θ ) = ? [ 1 m ∑ i = 1 m y ( i ) l o g ( h θ ( x ( i ) ) ) + ( 1 ? y ( i ) ) l o g ( 1 ? h θ ( x ( i ) ) ) ] + λ 2 m ∑ j = 1 n θ j 2 J(θ)=-\left[\frac{1}{m}\sum^{m}_{i=1}{y^{(i)}}log(h_θ(x^{(i)}))+{(1-y^{(i)})}log(1-h_θ(x^{(i)}))\right]+\red{\frac{λ}{2m}\sum^n_{j=1}θ^2_j} J(θ)=?[m1?i=1∑m?y(i)log(hθ?(x(i)))+(1?y(i))log(1?hθ?(x(i)))]+2mλ?j=1∑n?θj2?
• 新添加的項用于懲罰變數 θ1 到 θn，避免過擬合情況的發生，
• 具體實作：
  • 原梯度下降：
    R e p e a t { θ 0 : = θ 0 ? α 1 m ∑ i = 1 m ( h θ ( x ( i ) ) ? y ( i ) ) x 0 ( i ) θ j : = θ j ? α 1 m ∑ i = 1 m ( h θ ( x ( i ) ) ? y ( i ) ) x j ( i ) ( j = 0 , 1 , 2 , . . . , n ) } \begin{aligned} &Repeat\{ \\ &θ_0:=θ_0-α\frac{1}{m}\sum_{i=1}^m (h_θ(x^{(i)}) - y^{(i)} )x^{(i)}_0\\ &θ_j:=θ_j-α\frac{1}{m}\sum_{i=1}^m (h_θ(x^{(i)}) - y^{(i)} )x^{(i)}_j\qquad(j=\red{\bcancel{0}},1,2,...,n) \\ &\} \end{aligned} ?Repeat{θ0?:=θ0??αm1?i=1∑m?(hθ?(x(i))?y(i))x0(i)?θj?:=θj??αm1?i=1∑m?(hθ?(x(i))?y(i))xj(i)?(j=0 ?,1,2,...,n)}?
• 更新了正則化后只對剩下的項進行了修改：
  θ j : = θ j ? α [ 1 m ∑ i = 1 m ( h θ ( x ( i ) ) ? y ( i ) ) x j ( i ) + λ m θ j ] θ_j:=θ_j-α\left[\frac{1}{m}\sum_{i=1}^m (h_θ(x^{(i)}) - y^{(i)} )x^{(i)}_j+\red{\frac{λ}{m}θ_j}\right] θj?:=θj??α[m1?i=1∑m?(hθ?(x(i))?y(i))xj(i)?+mλ?θj?]
• 迭代公式雖然與線性回歸的一樣，但是由于二者的假設不同，故并不是同一個演算法，
• 上式方括號中的式子是新定義的正則化的代價函式的偏導

2. 高級優化演算法中使用正則化

• 在原來的基礎上繼續定義代價函式：
  f u n c t i o n [ j V a l , g r a d i e n t ] = c o s t F u n c t i o n ( t h e t a ) j V a l = [ c o d e t o c o m p u t e J ( θ ) ] ; J ( θ ) = ? [ 1 m ∑ i = 1 m y ( i ) l o g ( h θ ( x ( i ) ) ) + ( 1 ? y ( i ) ) l o g ( 1 ? h θ ( x ( i ) ) ) ] + λ 2 m ∑ j = 1 n θ j 2 g r a d i e n t ( 1 ) = [ c o d e t o c o m p u t e ? ? θ 0 J ( θ ) ] ; 1 m ∑ i = 1 m ( h θ ( x ( i ) ) ? y ( i ) ) x 0 ( i ) g r a d i e n t ( 2 ) = [ c o d e t o c o m p u t e ? ? θ 1 J ( θ ) ] ; 1 m ∑ i = 1 m ( h θ ( x ( i ) ) ? y ( i ) ) x 1 ( i ) + λ m θ 1 g r a d i e n t ( 3 ) = [ c o d e t o c o m p u t e ? ? θ 1 J ( θ ) ] ; 1 m ∑ i = 1 m ( h θ ( x ( i ) ) ? y ( i ) ) x 2 ( i ) + λ m θ 2 . . . g r a d i e n t ( n + 1 ) = [ c o d e t o c o m p u t e ? ? θ n J ( θ ) ] ; \begin{aligned} &\blue{function\ [jVal,\ gradient] = costFunction(theta)}\\ &\qquad\qquad\blue{jVal=[}\ code\ to\ compute\ J(θ)\blue{];}\\ &\qquad \qquad \tiny J(θ)=-\left[\frac{1}{m}\sum^{m}_{i=1}{y^{(i)}}log(h_θ(x^{(i)}))+{(1-y^{(i)})}log(1-h_θ(x^{(i)}))\right]+\red{\frac{λ}{2m}\sum^n_{j=1}θ^2_j}\\ &\qquad\qquad\blue{gradient(1)=[}\ code\ to\ compute\ \frac{\partial}{\partial θ_0}J(θ)\blue{];}\\ &\qquad\qquad\qquad \small\frac{1}{m}\sum_{i=1}^m (h_θ(x^{(i)}) - y^{(i)} )x^{(i)}_0\\ &\qquad\qquad\blue{gradient(2)=[}\ code\ to\ compute\ \frac{\partial}{\partial θ_1}J(θ)\blue{];}\\ &\qquad\qquad\qquad \small\frac{1}{m}\sum_{i=1}^m (h_θ(x^{(i)}) - y^{(i)} )x^{(i)}_1+\red{\frac{λ}{m}θ_1}\\ &\qquad\qquad\blue{gradient(3)=[}\ code\ to\ compute\ \frac{\partial}{\partial θ_1}J(θ)\blue{];}\\ &\qquad\qquad\qquad \small\frac{1}{m}\sum_{i=1}^m (h_θ(x^{(i)}) - y^{(i)} )x^{(i)}_2+\red{\frac{λ}{m}θ_2}\\ &\qquad\qquad\blue{...}\\ &\qquad\qquad\blue{gradient(n+1)=[}\ code\ to\ compute\ \frac{\partial}{\partial θ_n}J(θ)\blue{];}\\ \end{aligned} ?function [jVal, gradient]=costFunction(theta)jVal=[ code to compute J(θ)];J(θ)=?[m1?i=1∑m?y(i)log(hθ?(x(i)))+(1?y(i))log(1?hθ?(x(i)))]+2mλ?j=1∑n?θj2?gradient(1)=[ code to compute ?θ0???J(θ)];m1?i=1∑m?(hθ?(x(i))?y(i))x0(i)?gradient(2)=[ code to compute ?θ1???J(θ)];m1?i=1∑m?(hθ?(x(i))?y(i))x1(i)?+mλ?θ1?gradient(3)=[ code to compute ?θ1???J(θ)];m1?i=1∑m?(hθ?(x(i))?y(i))x2(i)?+mλ?θ2?...gradient(n+1)=[ code to compute ?θn???J(θ)];?
• 與正則化之前相比的變化：
  • 計算 J(θ) 時后面要多加一項
  • 梯度除了第一個以外其余的后面都要多加一項，
• 運行 costFunction 后，對它呼叫 fminuc 函式或者其他類似的高級優化函式，就實作了新的正則化代價函式 J(θ) 的最小化，回傳的兩個引數代表的就是正則化邏輯回歸的解，

總結

• 本文主要介紹了正則化的相關內容，先是通過過擬合問題來引出正則化，隨后講了正則化的應用，進而講解了如何在線性回歸和邏輯回歸中對不同的演算法實作正則化，
• 簡單來說，過擬合問題是對資料的擬合過度，像是為了擬合資料而擬合，導致假設函式不能實作對資料的泛化，其影像上下波動扭曲變形，
• 正則化是通過添加懲罰項來減小特征量的在假設函式中的量級，進而實作假設模型的簡化，使其更不容易出現過擬合問題，
• 正則化在線性回歸以及邏輯回歸中的應用都是通過在代價函式中添加變數的懲罰項來實作的，