掌握機器學習數學基礎之優化[1]（重點知識）

01-30

是的，你沒有看錯，本來計劃四篇可以寫完的，現在要不止了，優化部分分為一二，一主要是微積分的知識，二主要是約束優化，凸優化，對偶等知識。本來想一篇解決的，但文章之大，一篇放不下.......下面開始分節敘述：

計算複雜性與NP問題
上溢和下溢
導數，偏導數及兩個特殊矩陣
函數導數為零的二三事
方嚮導數和梯度
梯度下降法
牛頓法

計算複雜性與NP問題

演算法的複雜性：現實中大多數問題都是離散的數據集，為了反映統計規律，有時數據量很大，而且多數目標函數都不能簡單地求得解析解。而為了記錄在解決問題的演算法的性能或者說好壞，就引入了演算法的複雜性。

演算法理論被認為是解決各類現實問題的方法論。而衡量演算法理論的計算複雜度可分為：時間複雜度和空間複雜度，這是對演算法執行所需要的兩類資源——時間和空間的估算。其中，演算法的時間複雜度是一個函數，它定性描述了該演算法的運行時間，空間複雜度是對一個演算法在運行過程中臨時佔用存儲空間大小的量度

另為，一般的，衡量問題是否可解的重要指標是：該問題能否在多項式時間內求解，還是只能在指數時間內求解？在各類演算法理論中，通常使用多項式時間演算法即可解決的問題看作是易解問題，需要指數時間演算法解決的問題看作是難解問題。
指數時間演算法的計算時間隨著問題規模的增長而呈指數化上升，這類問題雖然有解，但並不適用於大規模問題。所以當前演算法研究的一個重要任務就是將指數時間演算法變換為多項式時間演算法。

確定性和非確定性 ：除了問題規模與運算時間的比較，衡量一個演算法還需要考慮確定性和非確定性的概念。

先說說自動機：是有限狀態機(FSM)的數學模型。實際上是指一種基於狀態變化進行迭代的演算法。也就是在給定輸入和狀態時，自動機的狀態會發生改變的模型。在演算法領域常把這類演算法看作一個機器，比較知名的有圖靈機、玻爾茲曼機、支持向量機等。或者，在日常生活中的自動售賣機就是一種有限狀態機。

確定性：所謂確定性，是指針對各種自動機模型，根據當時的狀態和輸入，若自動機的狀態轉移是唯一確定的，則稱具有確定性；

非確定性：若在某一時刻自動機有多個狀態可供選擇，並嘗試執行每個可選擇的狀態，則稱具有不確定性。

換個說法就是：確定性是程序每次運行時產生下一步的結果是唯一的，因此返回的結果也是唯一的；非確定性是程序在每個運行時執行的路徑是並行且隨機的，所有路徑都可能返回結果，也可能只有部分返回結果，也可能不返回結果，但是只要有一個路徑返回結果，那麼演算法就結束。

NP問題：簡單的說，存在多項式時間的演算法的一類問題，稱之為P類問題；在多項式時間內可由非確定機解決的一類問題，稱之為NP問題。另外，很多人相信P類問題是NP問題的一個子集，但既沒有人證明出有某個問題屬於NP但不屬於P，也沒有人證明所有NP問題都能在多項式時間內有解，如圖：

來自百度百科

P類問題：就是能夠以多項式時間的確定性演算法來對問題進行判定或求解，實現它的演算法在每個運行狀態都是唯一的，最終一定能夠確定一個唯一的結果——最優的結果。

NP問題：是指可以用多項式時間的非確定性演算法來判定或求解，即這類問題求解的演算法大多是非確定性的，但時間複雜度有可能是多項式級別的。

對於上面的知識，我們只要了解知道他們的概念就好了，機器學習中多數演算法都是針對NP問題（包括NP完全問題）的。

上溢和下溢

下溢：當接近零的數被四捨五入為零時發生下溢。許多函數會在其參數為零而不是一個很小的正數時才會表現出質的不同。例如，我們通常要避免被零除。

上溢(overflow)：當大量級的數被近似為 $+infty$ 或者 $-infty$ 時發生上溢。進一步的運算通常將這些無限值變為非數字。

為什麼會下溢或者上溢：數字計算機上實現連續數學的基本困難是我們需要通過有限數量的位模式來表示無限多的實數，這意味著我們在計算機中表示實數時幾乎都會引入一些近似誤差。在許多情況下，這僅僅是舍入誤差。如果在理論上可行的演算法沒有被設計為最小化舍入誤差的累積，可能會在實踐中失效，也就是可能產生下溢或者上溢

一個例子：必須對上溢和下溢進行數值穩定的一個例子是softmax 函數。softmax 函數經常用於預測與Multinoulli分布相關聯的概率，定義為：

$softmax(x)_{i}=frac{exp(x_{i})}{sum_{j=1}^{n}{exp(x_{j})}}$

當式中的 $x_{i}$ 都是很小的負數時， $exp(x_{i} )$ 就會發生下溢，這意味著上面函數的分母會變成0，導致結果是未定的；同理，當式中的 $x_{i}$ 是很大的正數時， $exp(x_{i} )$ 就會發生上溢導致結果是未定的。

這個概念是比較重要的，我們需要了解清除！

導數和偏導數

導數：當函數定義域和取值都在實數域中的時候，導數可以表示函數曲線上的切線斜率。當然除了切線的斜率，導數還表示函數在該點的變化率。或者從物理意義來說，就是瞬時變化率。

上面是一維導數的定義式，其中涉及極限的知識，簡單來說極限就是「無限靠近而永遠不能到達」，當然，高中初中就學過導數，這個也可以用之前斜率的角度去理解，多維的話也就是在此之上的推廣。

將上面的公式轉化為下面圖像為：

注意：在一元函數中，只有一個自變數變動，也就是說只存在一個方向的變化率，這也就是為什麼一元函數沒有偏導數的原因。

偏導數：偏導數是指對至少兩個自變數或以上對其中一個變數進行的求導，以兩個自變數為例， $z=f(x,y)$ . 從導數到偏導數，也就是從曲線來到了曲面. 曲線上的一點，其切線只有一條。但是曲面的一點，切線有無數條。

從幾何意義來說，偏導數就是指的是多元函數沿坐標軸的變化率.其中， $f_{x}(x,y)$ 指的是函數在y方向不變，函數值沿著x軸方向的變化率。而 $f_{y}(x,y)$ 指的是函數在x方向不變，函數值沿著y軸方向的變化率。

對應的圖像形象表達如下：

$x_{0}∈I$ 通過上圖，一目了然的是： $f_{x}(x,y)$ 指的就是曲面被平面所截得的曲面在點處的切線對x軸的斜率， $f_{y}(x,y)$ 就是曲面被平面所截得的曲面在點處的切線對y軸的斜率。

Jacobian矩陣：有時我們需要計算輸入和輸出都為向量的函數的所有偏導數。包含所有這樣的偏導數的矩陣被稱為Jacobian矩陣。具體來說，如果我們有一個函數： $f:R^mrightarrow R^n$ ， $f$ 的Jacobian矩陣 $Jin R^{ntimes m}$ 定義為 $J_{i,j}=frac{partial}{partial x_{j}} f(x)_i$

Hessian矩陣：當我們的函數具有多維輸入時，二階導數也有很多。我們可以將這些導數合併成一個矩陣，稱為Hessian矩陣。 Hessian矩陣 $H(f)(x)$ 定義為

注意：Hessian等價於梯度的Jacobian矩陣。

微分運算元在任何二階偏導連續的點處可交換，也就是它們的順序可以互換：

這意味著 $H_{i,j} = H_{j,i}$ ，因此也就是說Hessian矩陣在這些點上是對稱的。

這些知識是前置知識，下面都要用到，記住兩個特殊矩陣指的是什麼？然後偏導數是什麼？

函數導數為零的二三事

注意：為了便於理解，下面將詳細分析導數為0在低維的情況，而在高維情況下都是類似的。下面先介紹一些概念：

極值的定義如下：若函數 $f(x)$ 在 $x_{0}$ 的一個鄰域D有定義，且對D中除 $x_{0}$ 的所有點，都有 $f(x)<f(x_{0})$ ，則稱 $f(x_{0})$ 是函數 $f(x)$ 的一個極大值。同理，若對D的所有點，都有 $f(x)>f(x_{0})$ ，則稱f(x?)是函數 $f(x)$ 的一個極小值。

對應的，函數最值的定義如下：

最小值:設函數 $y=f(x)$ 的定義域為 $I$ ，如果存在實數M滿足：①對於任意實數 $x∈$ $I$ ，都有 $f(x)≥M$ ，②存在 $x_{0}∈I$ 。使得 $f (x_{0})=M$ ，那麼，我們稱實數M 是函數 $y=f(x)$ 的最小值。

最大值:設函數 $y=f(x)$ 的定義域為 $I$ ，如果存在實數M滿足：①對於任意實數 $x∈I$ ，都有 $f(x)≤M$ ，②存在 $x_{0}∈I$ 。使得 $f (x_{0})=M$ ，那麼，我們稱實數M 是函數 $y=f(x)$ 的最大值

以上都是在一元函數中的定義，如下圖所示，而二維或以上可簡單推之：

鞍點（saddle point）： 目標函數在此點上的梯度（一階導數）值為 0，但從改點出發的一個方向是函數的極大值點，而在另一個方向是函數的極小值點。

為什麼叫做鞍點？鞍點這詞來自於不定二次型 $x^2-y^2$ 的二維圖形，它的形狀就像馬鞍，而鞍點就是中心那個點，圖中x軸方向往上曲，在y軸方向往下曲。這樣也讓我們更容易理解。

判斷鞍點的一個充分條件是：函數在鞍點處的Hessian矩陣為不定矩陣。這樣為什麼在這裡不做詳細解釋，有興趣可以了解。

進入正題：當 $f^prime(x)=0$ ，導數無法提供往哪個方向移動的信息。 $f^prime(x)=0$ 的點稱為臨界點或駐點。一個局部極小點意味著這個點的 $f(x)$ 小於所有鄰近點，因此不可能通過移動無窮小的步長來減小 $f(x)$ 。一個局部極大點意味著這個點的 $f(x)$ 大於所有鄰近點，因此不可能通過移動無窮小的步長來增大 $f(x)$ 。有些臨界點既不是極小點也不是極大點。這些點被稱為鞍點。

圖來自《deep learning》

上圖列出臨界點的類型。在一維情況下,三種臨界點的示例。臨界點是斜率為零的點。這樣的點可以是局部極小點(local minimum),其值低於相鄰點; 局部極大點(local maximum),其值高於相鄰點; 或鞍點,同時存在更高和更低的相鄰點

使 $f (x)$ 取得絕對的最小值(相對所有其他值)的點是全局最小點(globalminimum)。函數可能有一個全局最小點或存在多個全局最小點,還可能存在不是全局最優的局部極小點。在機器學習和深度學習的背景下,我們要優化的函數可能含有許多不是最優的局部極小點,或者還有很多處於非常平坦的區域內的鞍點。尤其是當輸入是多維的時候,所有這些都將使優化變得困難。因此,我們通常尋找使 $f$ 非常小的點,但這在任何形式意義下並不一定是最小。方嚮導數和梯度方嚮導數和梯度

圖來自《deep learning》

上圖展示了近似最小化，當存在多個局部極小點或者平坦區域時，優化演算法可能無法找到全局最小點，在機器學習和深度學習中,即使找到的解不是真正最小的,但只要它們對應於代價函數顯著低的值,我們通常就能接受這樣的解。

這些知識點都是基本知識，不做過多解釋，低維的我們理解了，高維的就類推就行了，比如高維也臨界點也有局部最優或者鞍點的情況。但在深度學習中優化演算法比如SGD往往可以避免鞍點，然後使得其效果不錯，這也是深度學習為什麼可行的一個原因吧。

方嚮導數和梯度：

方嚮導數:在之前講偏導數的時候，相信很多人已經看出，偏導數求的都是沿著坐標軸的變化率，不管多少維也好，都只是求的變化率，那現在問題來了，如果我想求在某個方向而不是沿著坐標軸方向的變化率怎麼求呢？那方嚮導數，簡單來說，就是我們指定任意一個方向，函數對對這個任意方向的變化率.

假設 $z=f(x,y)$ 為一個曲面， $p(x_{0} ,y_{0} )$ 為 $f$ 定義域中一個點，單位向量 $u =costheta i+sintheta j$ 的斜率，其中 $theta$ 是此向量與 $x$ 軸正向夾角.單位向量 $u$ 可以表示對任何方嚮導數的方向.如下圖：

那麼我們來考慮如何求出 $u$ 方向的斜率，可以類比於前面導數定義，得出如下：

設 $f(x,y)$ 為一個二元函數， $u =costheta i+sintheta j$ 為一個單位向量，如果下列的極限值存在

$lim_{t rightarrow 0}{frac{f(x_{0}+tcostheta ,y_{0}+tsintheta )-f(x_{0},y_{0})}{t} }$ 此方嚮導數記為 $D_{u}f$

則稱這個極限值是 $f$ 沿著 $u$ 方向的方嚮導數，那麼隨著 $theta$ 的不同，我們可以求出任意方向的方嚮導數.這也表明了方嚮導數的用處，是為了給我們考慮函數對任意方向的變化率.

或者說，如下圖，我們知道在一維的時候，函數的導數就是在某點對應切線的斜率，那麼對於函數 $f(x,y)$ 的 $A$ 點在這個方向上也是有切線的，其切線的斜率就是方嚮導數。當然，注意這個切線是任意的，這裡我們要限定其方向，也就是圖中中的矢量y的方向。

梯度：是一個矢量或者說是一個向量，其方向上的方嚮導數最大，其大小正好是此最大方嚮導數。

梯度的理解很重要，很重要，很重要！下面解決兩個問題，梯度怎麼求和梯度有什麼用？

怎麼算？--（介紹一種比較簡單之間的方法）

方嚮導數可以如下的方法算： $D_{u}f(x,y)=f_{x}(x,y)costheta +f_{y}(x,y)sintheta$ ，對於該式子的推導，我們可以自行了解，這裡不做過多討論。

回到正題：

$D_{u}f(x,y)=f_{x}(x,y)costheta +f_{y}(x,y)sintheta$

設 $A=(f_{x}(x,y) ,f_{y}(x,y))$ , $I=(costheta ,sintheta )$

則得：

$D_{u}f(x,y)=Abullet I=left| A right| *left| I right| cosalpha$ ( $alpha$ 為向量 $A$ 與向量 $I$ 之間的夾角)

則當 $alpha$ 為0度的時候，也就是向量 $I$ （這個方向是一直在變，在尋找一個函數變化最快的方向）與向量 $A$ （這個方向當點固定下來的時候，它就是固定的）平行的時候，那麼此時如果 $D_{u}f(x,y)$ 要取得最大值。這個時候，我們也就求得梯度：A(這其中的A向量)

梯度有什麼用？

簡單的講，假如你在一座山上，蒙著眼睛，但是你必須到達山谷中最低點的湖泊，你該怎麼辦？然後我們想到一個簡單的方法，在每走一步時，都是走那個離谷底最近的那個方向，那怎麼求才能使得每一步都下降更大的高度，這個時候我們就完全可以用梯度來幫助我們，就可以完成任務啦！

當然了，我們是在寫機器學習數學基礎吶，你會說下山有什麼用，我們看這篇文章又不是為了下山的。Emmm...別急，下面我們就講梯度的大用處

不知道講清楚沒有，這兩個概念非常重要，下面的優化演算法的前提就是梯度，要重點理解

梯度下降法

大多數機器學習或者深度學習演算法都涉及某種形式的優化。優化指的是改變 $x$ 以最小化或最大化某個函數 $f(x)$ 的任務。我們通常以最小化 $f(x)$ 指代大多數最優化問題。最大化可經由最小化演算法最小化 $-f(x)$ 來實現。

我們把要最小化或最大化的函數稱為目標函數或準則。當我們對其進行最小化時，我們也把它稱為代價函數、損失函數或誤差函數。

下面，我們假設一個損失函數為 $J(theta)=frac{1}{2}sum_{i=1}^{m}({h_theta(x)-y})^2$ ，其中 $h_θ(x)=θ_0+θ_1x_1+θ_{2}x_2....+θ_{n}x_n$ 然後要使得最小化它。

注意：這裡只是假設，不用知道這個目標函數就是平方損失函數等等，然後肯定有人問既然要最小化它，那求個導數，然後使得導數等於0求出不就好了嗎？Emmmm...是的，有這樣的解法，可以去了解正規方程組求解。說下這裡不講的原因，主要是那樣的方式太難求解，然後在高維的時候，可能不可解，但機器學習或深度學習中，很多都是超高維的，所以也一般不用那種方法。總之，梯度下降是另一種優化的不錯方式，比直接求導好很多。

梯度下降：我們知道曲面上方嚮導數的最大值的方向就代表了梯度的方向，因此我們在做梯度下降的時候，應該是沿著梯度的反方向進行權重的更新，可以有效的找到全局的最優解。這個 $theta_i$ 的更新過程可以描述為

[a表示的是步長或者說是學習率（learning rate）]

好了，怎麼理解？在直觀上，還是下山，我們可以這樣理解，看下圖，一開始的時候我們隨機站在一個點，把他看成一座山，每一步，我們都以下降最多的路線來下山，那麼，在這個過程中我們到達山底（最優點）是最快的，而上面的a，它決定了我們「向下山走」時每一步的大小，過小的話收斂太慢，過大的話可能錯過最小值，扯到蛋...）。這是一種很自然的演算法，每一步總是尋找使J下降最「陡」的方向（就像找最快下山的路一樣）。

當然了，我們直觀上理解了之後，接下來肯定是從數學的角度，我們可以這樣想，先想在低維的時候，比如二維，我們要找到最小值，其實可以是這樣的方法，具體化到1元函數中時，梯度方向首先是沿著曲線的切線的，然後取切線向上增長的方向為梯度方向，2元或者多元函數中，梯度向量為函數值f對每個變數的導數，該向量的方向就是梯度的方向，當然向量的大小也就是梯度的大小。現在假設我們要求函數的最值，採用梯度下降法，結合如圖所示：

如圖所示，我們假設函數是 $y=x^2+1$ ,那麼如何使得這個函數達到最小值呢，簡單的理解，就是對x求導，得到 $y『=frac{1}{2}x$ ，然後用梯度下降的方式，如果初始值是（0的左邊）負值,那麼這是導數也是負值，用梯度下降的公式，使得x更加的靠近0,如果是正值的時候同理。注意：這裡的梯度也就是一元函數的導數，高維的可以直接類推之

批量梯度下降：在每次更新時用所有樣本，要留意，在梯度下降中，對於 $theta_i$ 的更新，所有的樣本都有貢獻，也就是參與調整 $theta$ .其計算得到的是一個標準梯度，也肯定可以達到一個全局最優。因而理論上來說一次更新的幅度是比較大的。如果樣本不多的情況下，當然是這樣收斂的速度會更快啦。但是很多時候，樣本很多，更新一次要很久，這樣的方法就不合適啦。下圖是其更新公式

隨機梯度下降：在每次更新時用1個樣本，可以看到多了隨機兩個字，隨機也就是說我們用樣本中的一個例子來近似我所有的樣本，來調整θ，因而隨機梯度下降是會帶來一定的問題，因為計算得到的並不是準確的一個梯度，容易陷入到局部最優解中，但是相比於批量梯度，這樣的方法更快，更快收斂，雖然是局部最優，但很多時候是我們可以接受的，所以這個方法用的也比上面的多。下圖是其更新公式

mini-batch梯度下降：在每次更新時用b個樣本,其實批量的梯度下降就是一種折中的方法，他用了一些小樣本來近似全部的，其本質就是我1個指不定不太准，那我用個30個50個樣本那比隨機的要准不少了吧，而且批量的話還是非常可以反映樣本的一個分布情況的。在深度學習中，這種方法用的是最多的，因為這個方法收斂也不會很慢，收斂的局部最優也是更多的可以接受！

}

梯度下降演算法是機器學習或者深度學習中經典演算法，現在絕大部分演算法都是這個，就算是改進，也是在此基礎上做出的改進，所以，要知道這個演算法是什麼，了解它的思想，甚至推薦直接看論文。

牛頓法

先來講怎麼找一個函數的零點(也就是函數值為0的點)，我們提出如下公式。

該公式的大概流程為：先做對 $θ$ 做一次猜測 $θ=θ_1$ ，然後過 $f(θ_1)$ 做 $f$ 的切線，切線交橫軸於點 $θ_2$ （也就是切線函數值的零點），此時更新 $θ_2$ ，再過 $f(θ_2)$ 做 $f$ 的切線，這樣θ就可以逼近使函數值為零的θ取值，下面是牛頓法圖解：

在最左的圖中為函數 $f$ 的圖像，我們希望找到零 $f(θ)=0$ 的點，從圖中看這個點大約取在1.3附近。假設我們初始化演算法時猜測 $θ(0)=4.5$ ，牛頓法會計算出函數 $f$ 在 $(4.5, f(4.5))$ 點的切線並解出切線的零點（即切線與 $y=0$ 的焦點，如中圖所示）。這就是第二次猜測的起點，在圖中 $θ(1)$ 大約在2.8附近。而最右側的圖像顯示了再一次迭代的結果，這使得 $θ(2)$ 取到了1.8附近。在幾輪迭代之後，θ會快速向1.3附近收斂，得到零點

牛頓法：從之前講的知道極值點就是導數為0的地方，但直接求導數等於0得到最優解在很多時候是不可行的，那我們現在試一下用就用上面的方式來求得極值點，也就是求導數的零點，也上面的方法應用到求導數為0時的點來求最值的方法就叫做牛頓法，對應的，牛頓方法的迭代規則如下：

當參數θ不止一個時，牛頓方法的迭代規則：

其中H是一個n階方陣（如果算上截距項應該是n+1階方陣）的Hessian矩陣（兩個特殊矩陣）。

相較於批量梯度下降，牛頓方法通常來說有更快的收斂速度，只需要少得多的迭代次數就能得到很接近最小值的結果。但是當模型的參數很多時（參數個數為n）Hessian矩陣的計算成本將會很大，導致收斂速度變慢，所以在深度學習中也很少使用牛頓法，就是因為計算Hessian矩陣太麻煩了，但是當參數個數不多時，牛頓方法通常又是比梯度下降快得多的。這也是他的優勢吧

偽牛頓法：上述的牛頓法需要計算Hessian矩陣的逆矩陣，運算複雜度太高。在動輒百億、千億量級特徵的大數據時代，模型訓練耗時太久。因此，很多牛頓演算法的變形出現了，這類變形統稱擬牛頓演算法。擬牛頓演算法的核心思想用一個近似矩陣B替代逆Hessian矩陣H?1。不同演算法的矩陣B的計算有差異，但大多演算法都是採用迭代更新的思想在tranning的沒一輪更新矩陣B。

由於這些偽牛頓法比較複雜，而且在機器學習中也較少用，所以在這裡先不細講了，有興趣的小夥伴可以看下這篇博文
牛頓法在基礎機器學習中有用到，但在深度學習中很少用，我們知道是什麼，基本了解就好

熬夜寫完一，可能有些錯別字，見諒！接下來就是二了，二比較燒腦了，寫的也比較多，堅持！寫的有什麼不好，有任何建議可以大膽提出，感謝！