機器學習中用到的數(shù)值分析

1、第四章 背景知識condition number從優(yōu)化或者數(shù)值計算的角度來說，L2 范數(shù)有助于處理 condition number 不好的情況下矩陣求逆很困難的問題。如果方陣 A 是奇異的，那么 A 的 condition number 就是正無窮大了。實際上，每一個可逆方陣都存在一個 condition number。對condition number來個一句話總結：condition number 是一個矩陣（或者它所描述的線性系統(tǒng)）的穩(wěn)定性或者敏感度的度量，如果一個矩陣的 condition number 在1附近，那么它就是well-conditioned的，如果遠大于1，那么它就是

2、 ill-conditioned 的，如果一個系統(tǒng)是 ill-conditioned 的，它的輸出結果就不要太相信了。應用如果當我們的樣本 X 的數(shù)目比每個樣本的維度還要小的時候，矩陣X T X 將會不是滿秩的，也就是X T X 會變得不可逆，所以w 就沒辦法直接計算出來了。如果加上L2規(guī)則項，就變成了下面這種情況，就可以直接求逆了：condition number一般在矩陣里被定義做最大singular value和最小singular value的比值。一般說來，如果一個矩陣的condition number大于1000，數(shù)值計算inv(A)或者解線性方程AX=Y可能會遇到嚴重的舍入問題，

3、這樣的問題通常被稱為ill-conditioned。   最簡單的解決方法是把A的diagonal entries都加上一個微小量delta以后再計算這樣做雖然會引入誤差，但是可以改善ill-condition。 梯度設體系中某處的物理參數(shù)(如溫度、速度、濃度等)為w，在與其垂直距離的dy處該參數(shù)為w+dw，則稱為該物理參數(shù)的梯度，也即該物理參數(shù)的變化率。如果參數(shù)為速度、濃度、溫度或空間，則分別稱為速度梯度、濃度梯度、溫度梯度或空間梯度。其中溫度梯度在直角坐標系下的表達式如右圖。在向量微積分中，標量場的梯度是一個向量場。標量場中某一點上的梯度指向標量場增

4、長最快的方向，梯度的長度是這個最大的變化率。更嚴格的說，從歐氏空間Rn到R的函數(shù)的梯度是在Rn某一點最佳的線性近似。在這個意義上，梯度是雅戈比矩陣的一個特殊情況。在單變量的實值函數(shù)的情況，梯度只是導數(shù)，或者，對于一個線性函數(shù)，也就是線的斜率。梯度一詞有時用于斜度，也就是一個曲面沿著給定方向的傾斜程度?？梢酝ㄟ^取向量梯度和所研究的方向的點積來得到斜度。梯度的數(shù)值有時也被稱為梯度。在二元函數(shù)的情形，設函數(shù)z=f(x,y)在平面區(qū)域D內(nèi)具有一階連續(xù)偏導數(shù)，則對于每一點P(x,y)D，都可以定出一個向量(f/x)*i+(f/y)*j這向量稱為函數(shù)z=f(x,y)在點P(x,y)的梯度，記作gradf(

5、x,y)類似的對三元函數(shù)也可以定義一個：(f/x)*i+(f/y)*j+(f/z)*k 記為gradf(x,y,z)梯度的本意是一個向量（矢量），表示某一函數(shù)在該點處的方向?qū)?shù)沿著該方向取得最大值，即函數(shù)在該點處沿著該方向（此梯度的方向）變化最快，變化率最大（為該梯度的模）。方向?qū)?shù)（directional derivative）的通俗解釋是：我們不僅要知道函數(shù)在坐標軸方向上的變化率方向?qū)?shù)（即偏導數(shù)），而且還要設法求得函數(shù)在其他特定方向上的變化率。而方向?qū)?shù)就是函數(shù)在其他特定方向上的變化率。定義方向?qū)?shù)的精確定義（以三元函數(shù)為例）：設三元函數(shù)f在點P0（x0，y0，z0）的某鄰域內(nèi)有定義，l

6、為從點P0出發(fā)的射線，P（x，y，z）為l上且含于鄰域內(nèi)的任一點，以（rou）表示P和P0兩點間的距離。若極限lim（ (f(P)-f(P0) / ）= lim （l f / ）（當0時）存在，則稱此極限為函數(shù)f在點P0沿方向l的方向?qū)?shù)。雅可比矩陣 二階導數(shù)的集合意義：（1）斜線斜率變化的速度（2）函數(shù)的凹凸性.二階導數(shù)是比較理論的、比較抽象的一個量,它不像一階導數(shù)那樣有明顯的幾何意義,因為它表示的是一階導數(shù)的變化率.在圖形上,它主要表現(xiàn)函數(shù)的凹凸性,直觀的說,函數(shù)是向上突起的,還是向下突起的.應用：如果一個函數(shù)f(x)在某個區(qū)間I上有f''(x)（即二階導數(shù)）>0恒成

7、立,那么對于區(qū)間I上的任意x,y,總有：f(x)+f(y)2f(x+y)/2,如果總有f''(x)0恒成立,那么在區(qū)間I上f(x)的圖象上的任意兩點連出的一條線段,這兩點之間的函數(shù)圖象都在該線段的下方,反之在該線段的上方.機器學習中梯度下降法和牛頓法的比較在機器學習的優(yōu)化問題中，梯度下降法和牛頓法是常用的兩種凸函數(shù)求極值的方法，他們都是為了求得目標函數(shù)的近似解。在邏輯斯蒂回歸模型的參數(shù)求解中，一般用改良的梯度下降法，也可以用牛頓法。由于兩種方法有些相似，我特地拿來簡單地對比一下。下面的內(nèi)容需要讀者之前熟悉兩種算法。梯度下降法梯度下降法用來求解目標函數(shù)的極值。這個極值是給定模型給

8、定數(shù)據(jù)之后在參數(shù)空間中搜索找到的。迭代過程為：可以看出，梯度下降法更新參數(shù)的方式為目標函數(shù)在當前參數(shù)取值下的梯度值，前面再加上一個步長控制參數(shù)alpha。梯度下降法通常用一個三維圖來展示，迭代過程就好像在不斷地下坡，最終到達坡底。為了更形象地理解，也為了和牛頓法比較，這里我用一個二維圖來表示：懶得畫圖了直接用這個展示一下。在二維圖中，梯度就相當于凸函數(shù)切線的斜率，橫坐標就是每次迭代的參數(shù)，縱坐標是目標函數(shù)的取值。每次迭代的過程是這樣：1. 首先計算目標函數(shù)在當前參數(shù)值的斜率（梯度），然后乘以步長因子后帶入更新公式，如圖點所在位置（極值點右邊），此時斜率為正，那么更新參數(shù)后參數(shù)減小，更接近極小值

9、對應的參數(shù)。2. 如果更新參數(shù)后，當前參數(shù)值仍然在極值點右邊，那么繼續(xù)上面更新，效果一樣。3. 如果更新參數(shù)后，當前參數(shù)值到了極值點的左邊，然后計算斜率會發(fā)現(xiàn)是負的，這樣經(jīng)過再一次更新后就會又向著極值點的方向更新。根據(jù)這個過程我們發(fā)現(xiàn)，每一步走的距離在極值點附近非常重要，如果走的步子過大，容易在極值點附近震蕩而無法收斂。解決辦法：將alpha設定為隨著迭代次數(shù)而不斷減小的變量，但是也不能完全減為零。牛頓法原理是利用泰勒公式，在x0處展開，且展開到一階，即f(x) = f(x0)+(xx0)f'(x0)求解方程f(x)=0，即f(x0)+(x-x0)*f'(x0)=0，求解x =

10、 x1=x0f(x0)/f'(x0)，因為這是利用泰勒公式的一階展開，f(x) = f(x0)+(xx0)f'(x0)處并不是完全相等，而是近似相等，這里求得的x1并不能讓f（x）=0，只能說f(x1)的值比f(x0)更接近f（x）=0，于是乎，迭代求解的想法就很自然了，可以進而推出x(n+1)=x(n)f(x(n)/f'(x(n)，通過迭代，這個式子必然在f（x*）=0的時候收斂。整個過程如下圖：2、牛頓法用于最優(yōu)化在最優(yōu)化的問題中，線性最優(yōu)化至少可以使用單純行法求解，但對于非線性優(yōu)化問題，牛頓法提供了一種求解的辦法。假設任務是優(yōu)化一個目標函數(shù)f，求函數(shù)f的

11、極大極小問題，可以轉化為求解函數(shù)f的導數(shù)f'=0的問題，這樣求可以把優(yōu)化問題看成方程求解問題（f'=0）。剩下的問題就和第一部分提到的牛頓法求解很相似了。這次為了求解f'=0的根，把f（x）的泰勒展開，展開到2階形式：這個式子是成立的，當且僅當 x 無線趨近于0。此時上式等價與：求解：得出迭代公式：一般認為牛頓法可以利用到曲線本身的信息，比梯度下降法更容易收斂（迭代更少次數(shù)），如下圖是一個最小化一個目標方程的例子，紅色曲線是利用牛頓法迭代求解，綠色曲線是利用梯度下降法求解。在上面討論的是2維情況，高維情況的牛頓迭代公式是：其中H是hessian矩陣，定義為：&

12、#160;高維情況依然可以用牛頓迭代求解，但是問題是Hessian矩陣引入的復雜性，使得牛頓迭代求解的難度大大增加，但是已經(jīng)有了解決這個問題的辦法就是Quasi-Newton methond，不再直接計算hessian矩陣，而是每一步的時候使用梯度向量更新hessian矩陣的近似。Quasi-Newton method的詳細情況我還沒完全理解，且聽下回分解吧。首先得明確，牛頓法是為了求解函數(shù)值為零的時候變量的取值問題的，具體地，當要求解 f()=0時，如果 f可導，那么可以通過迭代公式來迭代求得最小值。通過一組圖來說明這個過程。當應用于求解最大似然估計的值時，變成()=0的問題。這個與梯度下降

13、不同，梯度下降的目的是直接求解目標函數(shù)極小值，而牛頓法則變相地通過求解目標函數(shù)一階導為零的參數(shù)值，進而求得目標函數(shù)最小值。那么迭代公式寫作：當是向量時，牛頓法可以使用下面式子表示：其中H叫做海森矩陣，其實就是目標函數(shù)對參數(shù)的二階導數(shù)。通過比較牛頓法和梯度下降法的迭代公式，可以發(fā)現(xiàn)兩者及其相似。海森矩陣的逆就好比梯度下降法的學習率參數(shù)alpha。牛頓法收斂速度相比梯度下降法很快，而且由于海森矩陣的的逆在迭代中不斷減小，起到逐漸縮小步長的效果。牛頓法的缺點就是計算海森矩陣的逆比較困難，消耗時間和計算資源。因此有了擬牛頓法。最優(yōu)化問題中，牛頓法為什么比梯度下降法求解需要的迭代次數(shù)更少？牛頓法是二階收

14、斂，梯度下降是一階收斂，所以牛頓法就更快。如果更通俗地說的話，比如你想找一條最短的路徑走到一個盆地的最底部，梯度下降法每次只從你當前所處位置選一個坡度最大的方向走一步，牛頓法在選擇方向時，不僅會考慮坡度是否夠大，還會考慮你走了一步之后，坡度是否會變得更大。所以，可以說牛頓法比梯度下降法看得更遠一點，能更快地走到最底部。根據(jù)wiki上的解釋，從幾何上說，牛頓法就是用一個二次曲面去擬合你當前所處位置的局部曲面，而梯度下降法是用一個平面去擬合當前的局部曲面，通常情況下，二次曲面的擬合會比平面更好，所以牛頓法選擇的下降路徑會更符合真實的最優(yōu)下降路徑。wiki上給的圖很形象，我就直接轉過來了：紅色的牛頓

15、法的迭代路徑，綠色的是梯度下降法的迭代路徑。利普希茨連續(xù)在在數(shù)學中，特別是實分析，利普希茨連續(xù)（Lipschitz continuity）以德國數(shù)學家魯?shù)婪?#183;利普希茨命名，是一個比通常連續(xù)更強的光滑性條件。直覺上，利普希茨連續(xù)函數(shù)限制了函數(shù)改變的速度，符合利普希茨條件的函數(shù)的斜率，必小于一個稱為利普希茨常數(shù)的實數(shù)（該常數(shù)依函數(shù)而定）。在微分方程中，利普希茨連續(xù)是皮卡-林德洛夫定理中確保了初值問題存在唯一解的核心條件。一種特殊的利普希茨連續(xù)，稱為壓縮應用于巴拿赫不動點定理。利普希茨連續(xù)可以定義在度量空間上以及賦范向量空間上；利普希茨連續(xù)的一種推廣稱為赫爾德連續(xù)。定義對于在實數(shù)集的子集的

16、函數(shù)  ，若存在常數(shù)K，使得  ，則稱 f 符合利普希茨條件，對于f 最小的常數(shù)K 稱為 f 的利普希茨常數(shù)。1 若K < 1，f 稱為收縮映射。利普希茨條件也可對任意度量空間的函數(shù)定義：給定兩個度量空間  。若對于函數(shù)  ，存在常數(shù)K 使得則說它符合利普希茨條件。2 若存在K  1使得則稱 f 為雙李普希茨(bi-Lipschitz)的。深入理解拉格朗日乘子法（Lagr

17、ange Multiplier) 和KKT條件p.94在求取有約束條件的優(yōu)化問題時，拉格朗日乘子法（Lagrange Multiplier) 和KKT條件是非常重要的兩個求取方法，對于等式約束的優(yōu)化問題，可以應用拉格朗日乘子法去求取最優(yōu)值；如果含有不等式約束，可以應用KKT條件去求取。當然，這兩個方法求得的結果只是必要條件，只有當是凸函數(shù)的情況下，才能保證是充分必要條件。KKT條件是拉格朗日乘子法的泛化。之前學習的時候，只知道直接應用兩個方法，但是卻不知道為什么拉格朗日乘子法（Lagrange Multiplier) 和KKT條件能夠起作用，為什么要這樣去求取最優(yōu)值呢？本文將首先把什么是拉格朗

18、日乘子法（Lagrange Multiplier) 和KKT條件敘述一下；然后開始分別談談為什么要這樣求最優(yōu)值。一. 拉格朗日乘子法（Lagrange Multiplier) 和KKT條件通常我們需要求解的最優(yōu)化問題有如下幾類：(i) 無約束優(yōu)化問題，可以寫為:                                      min f(x);  (ii) 有等式約束的優(yōu)化問題

19、，可以寫為:                                       min f(x),                                        

20、    s.t. h_i(x) = 0; i =1, ., n (iii) 有不等式約束的優(yōu)化問題，可以寫為：                                      min f(x),                        

21、;                     s.t. g_i(x) <= 0; i =1, ., n                                                  h_j(x) = 0; j =1, ., m

22、對于第(i)類的優(yōu)化問題，常常使用的方法就是Fermat定理，即使用求取f(x)的導數(shù)，然后令其為零，可以求得候選最優(yōu)值，再在這些候選值中驗證；如果是凸函數(shù)，可以保證是最優(yōu)解。對于第(ii)類的優(yōu)化問題，常常使用的方法就是拉格朗日乘子法（Lagrange Multiplier) ，即把等式約束h_i(x)用一個系數(shù)與f(x)寫為一個式子，稱為拉格朗日函數(shù)，而系數(shù)稱為拉格朗日乘子。通過拉格朗日函數(shù)對各個變量求導，令其為零，可以求得候選值集合，然后驗證求得最優(yōu)值。對于第(iii)類的優(yōu)化問題，常常使用的方法就是KKT條件。同樣地，我們把所有的等式、不等式約束與f(x)寫為一個式子，也叫拉格朗日函數(shù)

23、，系數(shù)也稱拉格朗日乘子，通過一些條件，可以求出最優(yōu)值的必要條件，這個條件稱為KKT條件。(a) 拉格朗日乘子法（Lagrange Multiplier)對于等式約束，我們可以通過一個拉格朗日系數(shù)a 把等式約束和目標函數(shù)組合成為一個式子L(a, x) = f(x) + a*h(x), 這里把a和h(x)視為向量形式，a是橫向量，h(x)為列向量，之所以這么寫，完全是因為csdn很難寫數(shù)學公式，只能將就了.。然后求取最優(yōu)值，可以通過對L(a,x)對各個參數(shù)求導取零，聯(lián)立等式進行求取，這個在高等數(shù)學里面有講，但是沒有講為什么這么做就可以，在后面，將簡要介紹其思想。(b) KKT條

24、件對于含有不等式約束的優(yōu)化問題，如何求取最優(yōu)值呢？常用的方法是KKT條件，同樣地，把所有的不等式約束、等式約束和目標函數(shù)全部寫為一個式子L(a, b, x)= f(x) + a*g(x)+b*h(x)，KKT條件是說最優(yōu)值必須滿足以下條件：1. L(a, b, x)對x求導為零；2. h(x) =0;3. a*g(x) = 0;求取這三個等式之后就能得到候選最優(yōu)值。其中第三個式子非常有趣，因為g(x)<=0，如果要滿足這個等式，必須a=0或者g(x)=0. 這是SVM的很多重要性質(zhì)的來源，如支持向量的概念。二. 為什么拉格朗日乘子法（Lagrange Multiplier) 和KKT條件

25、能夠得到最優(yōu)值？為什么要這么求能得到最優(yōu)值？先說拉格朗日乘子法，設想我們的目標函數(shù)z = f(x), x是向量, z取不同的值，相當于可以投影在x構成的平面（曲面）上，即成為等高線，如下圖，目標函數(shù)是f(x, y)，這里x是標量，虛線是等高線，現(xiàn)在假設我們的約束g(x)=0，x是向量，在x構成的平面或者曲面上是一條曲線，假設g(x)與等高線相交，交點就是同時滿足等式約束條件和目標函數(shù)的可行域的值，但肯定不是最優(yōu)值，因為相交意味著肯定還存在其它的等高線在該條等高線的內(nèi)部或者外部，使得新的等高線與目標函數(shù)的交點的值更大或者更小，只有到等高線與目標函數(shù)的曲線相切的時候，可能取得最優(yōu)值，如下圖所示，即等高線和目標函數(shù)的曲線在該點的法向量必須有相同方向，所以最優(yōu)值必須滿足：f(x)的梯度 = a* g(x)的梯度，a是常數(shù)，表示左右兩邊同向。這個等式就是L(a,x)對參數(shù)求導的結果。（上述描述，我不知道描述清楚沒，如果與我物理位置很近的話，直接找我，我當面講好理解一些，注：下圖來自wiki）。而KKT條件是滿足強對偶條件的優(yōu)化問題的必要條件，可以這樣理解：我們要求min f(x), L(a, b, x) = f(x) + a*g(x) + b*h(x)，a>=0，我們可以把f(x)寫為：max_a,b