線性回歸算法梳理（打卡task-1）

1.從不同的角度看線性回歸（傳統的統計學的角度+機器學習角度）

2.機器學習概述：

機器學習(Machine Learning, ML)，顧名思義，讓機器去學習。這裡，機器指的是計算機，是算法運作的實體載體，你也可以把各種算法本身當做一個有輸入和輸出的機器。那麼到底讓計算機去學習什麼呢？對于一個任務及其表現的度量方法，設計一種算法，讓算法能夠提取中資料所蘊含的規律，這就叫機器學習。如果輸入機器的資料是帶有标簽的，就稱作有監督學習。如果資料是無标簽的，就是無監督學習。

監督學習：

1. 監督學習是使用已知正确答案的示例來訓練網絡。已知資料和其一一對應的标簽，訓練一個預測模型，将輸入資料映射到标簽的過程。
2. 監督式學習的常見應用場景如分類問題和回歸問題。
3. 常見的有監督機器學習算法包括支援向量機(Support Vector Machine, SVM)，樸素貝葉斯(Naive Bayes)，邏輯回歸(Logistic Regression)，K近鄰(K-Nearest Neighborhood, KNN)，決策樹(Decision Tree)，随機森林(Random Forest)，AdaBoost以及線性判别分析(Linear Discriminant Analysis, LDA)等。深度學習(Deep Learning)也是大多數以監督學習的方式呈現。

非監督式學習：

1. 在非監督式學習中，資料并不被特别辨別，适用于你具有資料集但無标簽的情況。學習模型是為了推斷出資料的一些内在結構。
2. 常見的應用場景包括關聯規則的學習以及聚類等。
3. 常見算法包括Apriori算法以及k-Means算法。

半監督式學習：

1. 在此學習方式下，輸入資料部分被标記，部分沒有被标記，這種學習模型可以用來進行預測。
2. 應用場景包括分類和回歸，算法包括一些對常用監督式學習算法的延伸，通過對已标記資料模組化，在此基礎上，對未标記資料進行預測。
3. 常見算法如圖論推理算法（Graph Inference）或者拉普拉斯支援向量機（Laplacian SVM）等。

弱監督學習：

1. 弱監督學習可以看做是有多個标記的資料集合，次集合可以是空集，單個元素，或包含多種情況（沒有标記，有一個标記，和有多個标記）的多個元素。
2. 資料集的标簽是不可靠的，這裡的不可靠可以是标記不正确，多種标記，标記不充分，局部标記等。
3. 已知資料和其一一對應的弱标簽，訓練一個智能算法，将輸入資料映射到一組更強的标簽的過程。标簽的強弱指的是标簽蘊含的資訊量的多少，比如相對于分割的标簽來說，分類的标簽就是弱标簽。
4. 舉例，給出一張包含氣球的圖檔，需要得出氣球在圖檔中的位置及氣球和背景的分割線，這就是已知弱标簽學習強标簽的問題。

​ 在企業資料應用的場景下， 人們最常用的可能就是監督式學習和非監督式學習的模型。 在圖像識别等領域，由于存在大量的非辨別的資料和少量的可辨別資料， 目前半監督式學習是一個很熱的話題。

線性回歸代價函數作用原理

​ 在回歸問題中，通過代價函數來求解最優解，常用的是平方誤差代價函數。有如下假設函數：

h ( x ) = A + B x h(x) = A + Bx h(x)=A+Bx

​ 假設函數中有 A A A和 B B B兩個參數，當參數發生變化時，假設函數狀态也會随着變化。

​ 想要拟合圖中的離散點，我們需要盡可能找到最優的 A A A和 B B B來使這條直線更能代表所有資料。如何找到最優解呢，這就需要使用代價函數來求解，以平方誤差代價函數為例，假設函數為 h ( x ) = θ 0 x h(x)=\theta_0x h(x)=θ0​x。

​ 平方誤差代價函數的主要思想就是将實際資料給出的值與拟合出的線的對應值做差，求出拟合出的直線與實際的差距。在實際應用中，為了避免因個别極端資料産生的影響，采用類似方差再取二分之一的方式來減小個别資料的影響。是以，引出代價函數：

J ( θ 0 , θ 1 ) = 1 m ∑ i = 1 m ( h ( x ( i ) ) − y ( i ) ) 2 J(\theta_0, \theta_1) = \frac{1}{m}\sum_{i=1}^m(h(x^{(i)})-y^{(i)})^2 J(θ0​,θ1​)=m1​i=1∑m​(h(x(i))−y(i))2

​ 最優解即為代價函數的最小值 min ⁡ J ( θ 0 , θ 1 ) \min J(\theta_0, \theta_1) minJ(θ0​,θ1​)。如果是1個參數，代價函數一般通過二維曲線便可直覺看出。如果是2個參數，代價函數通過三維圖像可看出效果，參數越多，越複雜。

當參數為2個時，代價函數是三維圖像。

線性回歸的損失函數

損失函數（Loss Function）又叫做誤差函數，用來衡量算法的運作情況，估量模型的預測值與真實值的不一緻程度，是一個非負實值函數，通常使用$

L(Y, f(x))$來表示。損失函數越小，模型的魯棒性就越好。損失函數是經驗風險函數的核心部分，也是結構風險函數重要組成部分。

優化方法（梯度下降）

梯度下降

機器學習中為什麼需要梯度下降？

1. 梯度下降是疊代法的一種，可以用于求解最小二乘問題。
2. 在求解機器學習算法的模型參數，即無限制優化問題時，主要有梯度下降法（Gradient Descent）和最小二乘法。
3. 在求解損失函數的最小值時，可以通過梯度下降法來一步步的疊代求解，得到最小化的損失函數和模型參數值。
4. 如果我們需要求解損失函數的最大值，可通過梯度上升法來疊代。梯度下降法和梯度上升法可互相轉換。
5. 在機器學習中，梯度下降法主要有随機梯度下降法和批量梯度下降法。

梯度下降法缺點？

1. 靠近極小值時收斂速度減慢。
2. 直線搜尋時可能會産生一些問題。
3. 可能會“之字形”地下降。

梯度概念需注意：

1. 梯度是一個向量，即有方向有大小。
2. 梯度的方向是最大方向導數的方向。
3. 梯度的值是最大方向導數的值。

核心思想歸納：

1. 初始化參數，随機選取取值範圍内的任意數；

2. 疊代操作：

   a）計算目前梯度；

   b）修改新的變量；

   c）計算朝最陡的下坡方向走一步；

   d）判斷是否需要終止，如否，傳回a）；

3. 得到全局最優解或者接近全局最優解。

梯度下降法算法描述

1. 确定優化模型的假設函數及損失函數。

   ​ 舉例，對于線性回歸，假設函數為：

h θ ( x 1 , x 2 , . . . , x n ) = θ 0 + θ 1 x 1 + . . . + θ n x n h_\theta(x_1,x_2,...,x_n)=\theta_0+\theta_1x_1+...+\theta_nx_n hθ​(x1​,x2​,...,xn​)=θ0​+θ1​x1​+...+θn​xn​

其中， θ i , x i ( i = 0 , 1 , 2 , . . . , n ) \theta_i,x_i(i=0,1,2,...,n) θi​,xi​(i=0,1,2,...,n)分别為模型參數、每個樣本的特征值。

對于假設函數，損失函數為：

J ( θ 0 , θ 1 , . . . , θ n ) = 1 2 m ∑ j = 0 m ( h θ ( x 0 ( j ) , x 1 ( j ) , . . . , x n ( j ) ) − y j ) 2 J(\theta_0,\theta_1,...,\theta_n)=\frac{1}{2m}\sum^{m}_{j=0}(h_\theta (x^{(j)}_0 ,x^{(j)}_1,...,x^{(j)}_n)-y_j)^2 J(θ0​,θ1​,...,θn​)=2m1​j=0∑m​(hθ​(x0(j)​,x1(j)​,...,xn(j)​)−yj​)2

1. 相關參數初始化。

   ​ 主要初始化 θ i {\theta}_i θi​、算法疊代步長${\alpha} 、 終 止 距 離 、終止距離 、終止距離{\zeta} 。 初 始 化 時 可 以 根 據 經 驗 初 始 化 ， 即 。初始化時可以根據經驗初始化，即 。初始化時可以根據經驗初始化，即{\theta} 初 始 化 為 0 ， 步 長 初始化為0，步長 初始化為0，步長{\alpha} 初 始 化 為 1 。 當 前 步 長 記 為 初始化為1。目前步長記為 初始化為1。目前步長記為{\varphi}_i $。當然，也可随機初始化。

2. 疊代計算。

   1）計算目前位置時損失函數的梯度，對${\theta}_i $，其梯度表示為：

∂ ∂ θ i J ( θ 0 , θ 1 , . . . , θ n ) = 1 2 m ∑ j = 0 m ( h θ ( x 0 ( j ) , x 1 ( j ) , . . . , x n ( j ) ) − y j ) 2 \frac{\partial}{\partial \theta_i}J({\theta}_0,{\theta}_1,...,{\theta}_n)=\frac{1}{2m}\sum^{m}_{j=0}(h_\theta (x^{(j)}_0 ,x^{(j)}_1,...,x^{(j)}_n)-y_j)^2 ∂θi​∂​J(θ0​,θ1​,...,θn​)=2m1​j=0∑m​(hθ​(x0(j)​,x1(j)​,...,xn(j)​)−yj​)2

​ 2）計算目前位置下降的距離。

φ i = α ∂ ∂ θ i J ( θ 0 , θ 1 , . . . , θ n ) {\varphi}_i={\alpha} \frac{\partial}{\partial \theta_i}J({\theta}_0,{\theta}_1,...,{\theta}_n) φi​=α∂θi​∂​J(θ0​,θ1​,...,θn​)

​ 3）判斷是否終止。

​ 确定是否所有 θ i {\theta}_i θi​梯度下降的距離 φ i {\varphi}_i φi​都小于終止距離 ζ {\zeta} ζ，如果都小于 ζ {\zeta} ζ，則算法終止，當然的值即為最終結果，否則進入下一步。

​ 4）更新所有的 θ i {\theta}_i θi​，更新後的表達式為：

θ i = θ i − α ∂ ∂ θ i J ( θ 0 , θ 1 , . . . , θ n ) {\theta}_i={\theta}_i-\alpha \frac{\partial}{\partial \theta_i}J({\theta}_0,{\theta}_1,...,{\theta}_n) θi​=θi​−α∂θi​∂​J(θ0​,θ1​,...,θn​)

θ i = θ i − α 1 m ∑ j = 0 m ( h θ ( x 0 ( j ) , x 1 ( j ) , . . . , x n ( j ) ) − y j ) x i ( j ) \theta_i=\theta_i - \alpha \frac{1}{m} \sum^{m}_{j=0}(h_\theta (x^{(j)}_0 ,x^{(j)}_1,...,x^{(j)}_n)-y_j)x^{(j)}_i θi​=θi​−αm1​j=0∑m​(hθ​(x0(j)​,x1(j)​,...,xn(j)​)−yj​)xi(j)​

​ 5）令上式 x 0 ( j ) = 1 x^{(j)}_0=1 x0(j)​=1，更新完畢後轉入1)。

​ 由此，可看出，目前位置的梯度方向由所有樣本決定，上式中 1 m \frac{1}{m} m1​、 α 1 m \alpha \frac{1}{m} αm1​ 的目的是為了便于了解。

如何對梯度下降法進行調優？

實際使用梯度下降法時，各項參數名額不能一步就達到理想狀态，對梯度下降法調優主要展現在以下幾個方面：

1. 算法疊代步長 α \alpha α選擇。

   在算法參數初始化時，有時根據經驗将步長初始化為1。實際取值取決于資料樣本。可以從大到小，多取一些值，分别運作算法看疊代效果，如果損失函數在變小，則取值有效。如果取值無效，說明要增大步長。但步長太大，有時會導緻疊代速度過快，錯過最優解。步長太小，疊代速度慢，算法運作時間長。

2. 參數的初始值選擇。

   初始值不同，獲得的最小值也有可能不同，梯度下降有可能得到的是局部最小值。如果損失函數是凸函數，則一定是最優解。由于有局部最優解的風險，需要多次用不同初始值運作算法，關鍵損失函數的最小值，選擇損失函數最小化的初值。

3. 标準化處理。

   由于樣本不同，特征取值範圍也不同，導緻疊代速度慢。為了減少特征取值的影響，可對特征資料标準化，使新期望為0，新方差為1，可節省算法運作時間。

随機梯度和批量梯度差別？

​ 随機梯度下降（SDG）和批量梯度下降（BDG）是兩種主要梯度下降法，其目的是增加某些限制來加速運算求解。

下面通過介紹兩種梯度下降法的求解思路，對其進行比較。

假設函數為：

h θ ( x 0 , x 1 , . . . , x 3 ) = θ 0 x 0 + θ 1 x 1 + . . . + θ n x n h_\theta (x_0,x_1,...,x_3) = \theta_0 x_0 + \theta_1 x_1 + ... + \theta_n x_n hθ​(x0​,x1​,...,x3​)=θ0​x0​+θ1​x1​+...+θn​xn​

損失函數為：

J ( θ 0 , θ 1 , . . . , θ n ) = 1 2 m ∑ j = 0 m ( h θ ( x 0 j , x 1 j , . . . , x n j ) − y j ) 2 J(\theta_0, \theta_1, ... , \theta_n) = \frac{1}{2m} \sum^{m}_{j=0}(h_\theta (x^{j}_0 ,x^{j}_1,...,x^{j}_n)-y^j)^2 J(θ0​,θ1​,...,θn​)=2m1​j=0∑m​(hθ​(x0j​,x1j​,...,xnj​)−yj)2

其中， m m m為樣本個數， j j j為參數個數。

1、 批量梯度下降的求解思路如下：

a) 得到每個$ \theta $對應的梯度：

∂ ∂ θ i J ( θ 0 , θ 1 , . . . , θ n ) = 1 m ∑ j = 0 m ( h θ ( x 0 j , x 1 j , . . . , x n j ) − y j ) x i j \frac{\partial}{\partial \theta_i}J({\theta}_0,{\theta}_1,...,{\theta}_n)=\frac{1}{m}\sum^{m}_{j=0}(h_\theta (x^{j}_0 ,x^{j}_1,...,x^{j}_n)-y^j)x^{j}_i ∂θi​∂​J(θ0​,θ1​,...,θn​)=m1​j=0∑m​(hθ​(x0j​,x1j​,...,xnj​)−yj)xij​

b) 由于是求最小化風險函數，是以按每個參數 $ \theta $ 的梯度負方向更新 $ \theta_i $ ：

θ i = θ i − 1 m ∑ j = 0 m ( h θ ( x 0 j , x 1 j , . . . , x n j ) − y j ) x i j \theta_i=\theta_i - \frac{1}{m} \sum^{m}_{j=0}(h_\theta (x^{j}_0 ,x^{j}_1,...,x^{j}_n)-y^j)x^{j}_i θi​=θi​−m1​j=0∑m​(hθ​(x0j​,x1j​,...,xnj​)−yj)xij​

c) 從上式可以注意到，它得到的雖然是一個全局最優解，但每疊代一步，都要用到訓練集所有的資料，如果樣本資料很大，這種方法疊代速度就很慢。

相比而言，随機梯度下降可避免這種問題。

2、随機梯度下降的求解思路如下：

a) 相比批量梯度下降對應所有的訓練樣本，随機梯度下降法中損失函數對應的是訓練集中每個樣本的粒度。

損失函數可以寫成如下這種形式，

J ( θ 0 , θ 1 , . . . , θ n ) = 1 m ∑ j = 0 m ( y j − h θ ( x 0 j , x 1 j , . . . , x n j ) ) 2 = 1 m ∑ j = 0 m c o s t ( θ , ( x j , y j ) ) J(\theta_0, \theta_1, ... , \theta_n) = \frac{1}{m} \sum^{m}_{j=0}(y^j - h_\theta (x^{j}_0 ,x^{j}_1,...,x^{j}_n))^2 = \frac{1}{m} \sum^{m}_{j=0} cost(\theta,(x^j,y^j)) J(θ0​,θ1​,...,θn​)=m1​j=0∑m​(yj−hθ​(x0j​,x1j​,...,xnj​))2=m1​j=0∑m​cost(θ,(xj,yj))

b）對每個參數 $ \theta$ 按梯度方向更新 $ \theta$：

θ i = θ i + ( y j − h θ ( x 0 j , x 1 j , . . . , x n j ) ) \theta_i = \theta_i + (y^j - h_\theta (x^{j}_0, x^{j}_1, ... ,x^{j}_n)) θi​=θi​+(yj−hθ​(x0j​,x1j​,...,xnj​))

c) 随機梯度下降是通過每個樣本來疊代更新一次。

随機梯度下降伴随的一個問題是噪音較批量梯度下降要多，使得随機梯度下降并不是每次疊代都向着整體最優化方向。

小結：

随機梯度下降法、批量梯度下降法相對來說都比較極端，簡單對比如下：

方法	特點
批量梯度下降	a）采用所有資料來梯度下降。 b）批量梯度下降法在樣本量很大的時候，訓練速度慢。
随機梯度下降	a）随機梯度下降用一個樣本來梯度下降。 b）訓練速度很快。 c）随機梯度下降法僅僅用一個樣本決定梯度方向，導緻解有可能不是全局最優。 d）收斂速度來說，随機梯度下降法一次疊代一個樣本，導緻疊代方向變化很大，不能很快的收斂到局部最優解。

下面介紹能結合兩種方法優點的小批量梯度下降法。

3、 小批量（Mini-Batch）梯度下降的求解思路如下

對于總數為 m m m個樣本的資料，根據樣本的資料，選取其中的 n ( 1 &lt; n &lt; m ) n(1&lt; n&lt; m) n(1<n<m)個子樣本來疊代。其參數 θ \theta θ按梯度方向更新 θ i \theta_i θi​公式如下：

θ i = θ i − α ∑ j = t t + n − 1 ( h θ ( x 0 j , x 1 j , . . . , x n j ) − y j ) x i j \theta_i = \theta_i - \alpha \sum^{t+n-1}_{j=t} ( h_\theta (x^{j}_{0}, x^{j}_{1}, ... , x^{j}_{n} ) - y^j ) x^{j}_{i} θi​=θi​−αj=t∑t+n−1​(hθ​(x0j​,x1j​,...,xnj​)−yj)xij​

各種梯度下降法性能比較

​ 下表簡單對比随機梯度下降（SGD）、批量梯度下降（BGD）、小批量梯度下降（Mini-batch GD）、和Online GD的差別：

BGD	SGD	Mini-batch GD	Online GD
訓練集	固定	固定	固定	實時更新
單次疊代樣本數	整個訓練集	單個樣本	訓練集的子集	根據具體算法定
算法複雜度	高	低	一般	低
時效性	低	一般	一般	高
收斂性	穩定	不穩定	較穩定	不穩定

BGD、SGD、Mini-batch GD，前面均已讨論過，這裡介紹一下Online GD。

​ Online GD于Mini-batch GD/SGD的差別在于，所有訓練資料隻用一次，然後丢棄。這樣做的優點在于可預測最終模型的變化趨勢。

​ Online GD在網際網路領域用的較多，比如搜尋廣告的點選率（CTR）預估模型，網民的點選行為會随着時間改變。用普通的BGD算法（每天更新一次）一方面耗時較長（需要對所有曆史資料重新訓練）；另一方面，無法及時回報使用者的點選行為遷移。而Online GD算法可以實時的依據網民的點選行為進行遷移。

複習！