斯坦福大學機器學習梯度算法總結

1、-斯坦福大學機器學習梯度下降算法學習心得和相關概念介紹。1根底概念和記號線性代數(shù)對于線性方程組可以提供一種簡便的表達和操作方式，例如對于如下的方程組：4*1-5*2=13-2*1+3*2=-9可以簡單的表示成下面的方式：*也是一個矩陣，為(*1,*2)T，當然你可以看成一個列向量。1.1根本記號用A 表示一個矩陣A，有m行，n列，并且每一個矩陣元素都是實數(shù)。用* , 表示一個n維向量. 通常是一個列向量. 如果要表示一個行向量的話，通常是以列向量的轉置后面加T來表示。1.2向量的積和外積根據(jù)課的定義，如果形式如*T y，或者yT *，則表示為積，結果為一個實數(shù)，表示的是：，如果形式為*yT，則

2、表示的為外積:。1.3矩陣-向量的乘法給定一個矩陣A Rmn，以及一個向量* Rn，他們乘積為一個向量y = A* Rm。也即如下的表示：如果A為行表示的矩陣即表示為，則y的表示為：相對的，如果A為列表示的矩陣，則y的表示為：即：y看成A的列的線性組合，每一列都乘以一個系數(shù)并相加，系數(shù)由*得到。同理，yT=*T*A表示為：yT是A的行的線性組合，每一行都乘以一個系數(shù)并相加，系數(shù)由*得到。1.4矩陣-矩陣的乘法同樣有兩種表示方式:第一種：A表示為行，B表示為列第二種，A表示為列，B表示為行：本質上是一樣的，只是表示方式不同罷了。1.5矩陣的梯度運算這是教師自定義的定義函數(shù)f，是從m * n矩陣到

3、實數(shù)的一個映射，則對于f在A上的梯度的定義如下：這里我的理解是，fA=關于A中的元素的表達式，是一個實數(shù)，然后所謂的對于A的梯度即是和A同樣規(guī)模的矩陣，矩陣中的每一個元素就是f(A)針對原來的元素的求導。1.6其他概念因為篇幅原因，所以不在這里繼續(xù)贅述，其他需要的概念還有單位矩陣、對角線矩陣、矩陣轉置、對稱矩陣AT=A、反對稱矩陣A=-AT、矩陣的跡、向量的模、線性無關、矩陣的秩、滿秩矩陣、矩陣的逆當且僅當矩陣滿秩時可逆、正交矩陣、矩陣的列空間(值域)、行列式、特征向量與特征值2用到的公式在課程中用到了許多公式，羅列一下。嗯，局部公式的證明很簡單，局部難的證明我也不會，也懶得去細想了，畢竟感覺

4、上數(shù)學對于我來說更像是工具吧。轉置相關： (AT)T = A (AB)T = BT AT (A + B)T = AT + BT跡相關： For A Rnn, trA = trAT . For A, B Rnn, tr(A + B) =trA + trB. For A Rnn, t R, tr(tA) = t trA. For A, B such that AB issquare, trAB = trBA. For A, B, C such that ABC issquare, trABC = trBCA = trCAB。當乘法變多時也一樣，就是每次從末尾取一個矩陣放到前面去，這樣的矩陣乘法所得

5、矩陣的跡是一致的。秩相關 For A Rmn,rank(A) min(m, n). If rank(A) = min(m, n), 則A稱為滿秩 For A Rmn,rank(A) = rank(AT). For A Rmn, B Rnp,rank(AB) min(rank(A), rank(B). For A, B Rmn,rank(A + B) rank(A) +rank(B).逆相關： (A1)1 = A If A* = b, 左右都乘以A1 得到 * = A1b. (AB)1 = B1A1 (A1)T = (AT)1. F通常表示為AT.行列式相關： For A Rnn, |A| =

6、|AT |. For A, B Rnn, |AB| = |A|B|. For A Rnn, |A| = 0，表示矩陣A是奇異矩陣，不可逆矩陣 For A Rnn and A 可逆, |A|1 = 1/|A|.梯度相關：*(f(*) + g(*) = *f(*) + *g(*). For t R, *(t f(*) = t*f(*).*bT * = b*T A* = 2A* (if A 對稱)2*T A* = 2A (if A 對稱)A|A| =(adj(A)T = |A|AT . adj=adjoint3梯度下降算法和正規(guī)方程組實例應用例子用的是上節(jié)課的房價的例子，有一組數(shù)據(jù)，有房子面積和房子

7、價格，輸入格式舉例：教師定義的變量如下：m:訓練樣本的數(shù)目*：輸入的變量輸入的特征，在這個例子中為房子面積，后來又加了一個房子的臥室數(shù)目y :輸出變量目標變量，這個例子中就是房價(*,y)：表示的是一個樣本：表示的第i個樣本，表示為。3.1監(jiān)視學習概念所謂的監(jiān)視學習即為告訴算法每個樣本的正確答案，學習后的算法對新的輸入也能輸入正確的答案。監(jiān)視指的是在訓練樣本答案的監(jiān)視下，h即為監(jiān)視學習函數(shù)。此例中我們假設輸出目標變量是輸入變量的線性組合，也就是說，我們的假設是存下如下的h*：Theta表示是特征前面的參數(shù)也稱作特征權重。也就是經(jīng)過h(*)之后得到的就是預測的結果了。如果假設*0=1，則原來的h

8、(*)就可以簡單的表示為如下形式：，其中n為特征數(shù)目，我們?yōu)榱吮磉_簡便，把theta和*都寫成向量的形式。下面就是如何求出向量使得h(*)盡可能接近實際結果的,至少在訓練集接近訓練集中的正確答案。我們定義一個花費函數(shù)(costfunction)，針對每一組，計算出h(*)與實際值的差值。定義如下：這也是用的最小二乘法的思想，但是之所以乘以1/2是為了簡化后面的計算。針對訓練集中的每一組數(shù)據(jù)。剩下的問題就是求得minJ時的取值，因為J()是隨著變化而變化，所以我們要求得minJ時的就是我們想要的這個min也叫做最小花費函數(shù))，怎么樣求出這組theta呢.采用的方法就是梯度下降算法和正規(guī)方程組。我

9、們首先來看梯度下降算法。3.2梯度下降算法梯度下降算法是一種搜索算法，根本思想可以這樣理解：我們從山上的*一點出發(fā)，找一個最陡的坡走一步也就是找梯度方向，到達一個點之后，再找最陡的坡，再走一步，直到我們不斷的這么走，走到最“低點最小花費函數(shù)收斂點。如上圖所示，*,y表示的是theta0和theta1，z方向表示的是花費函數(shù)，很明顯出發(fā)點不同，最后到達的收斂點可能不一樣。當然如果是碗狀的，則收斂點就應該是一樣的。算法的theta更新表示如下：對每一個theta(j),都先求J()對theta(j)的偏導(梯度方向)，然后減少，然后將現(xiàn)在的theta(j)帶入，求得新的theta(j)進展更新。其

10、中為步長，你可以理解為我們下山時走的步子的大小。步子太小了，收斂速度慢，步子太大了，可能會在收斂點附近來回擺動導致無法到達最低點。P.S.這個符號根據(jù)教師所說理解為程序中的賦值符號(=號)，如果是=號，則理解為值是相等的(編程里面的=號)。下面我們先理解下，假設現(xiàn)在訓練集只有一組數(shù)據(jù)求關于theta(j)的偏導：帶入可以得到關于一組數(shù)據(jù)的theta(j)的表達式，不妨，這組數(shù)據(jù)就是第i組，則表示為：然后我們將這個更新theta(j)的方法擴大到m個訓練樣本中，就可以得到下面的式子：P.S.最外面的那個*j(i)的理解為：第i組數(shù)據(jù)中的第j個特征(feature)值。批量梯度下降算法batch

11、g*d* algorithm重復執(zhí)行上面的這個更新步驟，直到收斂，就可以得到這組的值了。就是這個過程：。這個算法就是批量梯度下降算法，為什么叫批量梯度下降.因為注意到上式中每更新一個j都需要計算所有的樣本取值，所以當樣本數(shù)目非常大的時候(例如上萬條甚至數(shù)十萬條的時候)，這樣的更新非常慢，找也非常慢，所以就有了另外一種改進的梯度下降算法。隨機梯度下降算法/增量梯度下降算法做一個小小的改進，用一個樣本做一個theta的更新，比方用樣本1做theta(1)的更新，用樣本2做theta(2)的更新，以此類推。這種方法的好處是速度上肯定比批量梯度下降算法快，而且樣本數(shù)據(jù)越多，表達應該就越明顯。劣勢是得到的收斂點的值和批量梯度算法比起來也許不是最優(yōu)的值。梯度下降算法總結不管是批量梯度算法還是隨機梯度下降算法，他們的共同點有以下：1.時間復雜度都是O(mn) (m為樣本數(shù)目，n為特征值/影響因子數(shù)目)2.都有梯度下降性質：接近收斂時，每次“步子指實際減去的數(shù)，而不是前面定義的，是手動設置參數(shù)，人為改變才會變會越來越小。其原因是每次減去乘以梯度，但是隨著收斂的進展，梯度會越來越小，所以減去的值會。3.判定收斂的方法都是如下兩種:1)兩次迭代值改變量極小極小2)J()的值改變量極小極小3.3正規(guī)方程組寫在前面：這種方法是另一種方法了，和梯度下降算法就沒啥聯(lián)系了！首先回憶下前面定義的矩