梯度下降算法說明.doc

梯度下降算法說明及實現(xiàn) 哈爾濱工業(yè)大學深圳研究生院 生物計算研究中心 1 算法說明（1）目的假設我們有一個包含n個樣本的集合D=x1，x2，xn，一些標記為1，另一些標記為2，其中1，2記作y，作為樣本的輸出。我們希望用這些樣本來確定一個判別函數(shù)gx= atx的權向量a。對于一個樣本xi，如果有atxi0就標記為1，如果atxi0就標記為2。我們在尋找滿足線性不等式組atxi0的解時所采用的方法是：定義一個準則函數(shù)J(a)，當a是解向量時，J(a)最小。這樣就將問題簡化為一個標量函數(shù)的極小化問題通常可用梯度下降法來解決。（2）原理首先從隨意選擇的一個權向量a(0)開始，計算梯度向量J(a(0)，下一個值a(1)由自a(0)向下降最陡的方向移一段距離而得到，即沿著梯度的負方向。通常a(i+1)由等式ak+1=ak-kJ(a(k)計算，是正的比例因子，或者說是用于設定步長的“學習率”，可以是較小的常數(shù)，一般手工設置，J(a(k)是ak的梯度。我們希望這樣得到的一個權向量序列最終收斂到是J(a)極小化的解上。按照上面的梯度下降法迭代公式進行若干次迭代搜索，每次迭代的初始點取上次迭代的終點，即可使迭代點逐步逼近目標函數(shù)的極小點。其迭代的終止條件可采用點距準則或梯度準則，即當ak-ak+1或|J(a(k)|時終止。其中，Ja=Ja0,Ja1,Ja(n)T。注意：Ja本身是一個向量，它的成員是J對每個a(i)的偏導數(shù)。我們可以從度量標準訓練誤差：Ja=12xD(gx-y)2中得到組成這個梯度向量的分量Jai，其中g(x)是訓練樣例的目標輸出，即預測值，每一個訓練樣本X都有m個屬性值，Z是線性單元對訓練樣例的輸出，即已知的訓練樣本的取值。則推導過程如下，假設只有一個訓練樣本：J(a)ai=ai12gx -y 2 =122gx -y aigx -y =gx -y aigx -y =gx -y aia0x0+a1x1+amxm-yi =gx -y xi 其中xi 表示樣本的第i個屬性值。則有ai=ai-gx -y xi 推廣到有n個樣本的集合時則有：ai=ai-j=1ngx j-yj xij （3）一些變量及規(guī)格X 一個n行m列的矩陣y一個具有n列的行向量a一個具有m列的行向量 xj表示第j個樣本向量，是一個具有m個特征的行向量yj表示第j個樣本向量的輸出xi j表示第j個樣本的第i個特征值2 算法實現(xiàn)步驟(1) 給定初始點a(0)Rn,迭代精度，學習率k。(2) 置0k。(3) 計算迭代點a(k)的梯度J(a(k)=Ja0,Ja1,Ja(m)T(4) 計算迭代新點ak=ak-kJ(a(k)。(5) 檢驗是否滿足迭代終止條件|kJak|是否小于迭代精度，若小于，停止迭代，則返回最優(yōu)解a，否則下一步。(6) 置k+1k，返回步驟(3)進行下一次迭代計算。3 算法偽代碼Begin initialize a,閾值，k，k0 do kk + 1 a a-kJ(a) until |kJak| return aend4 梯度下降算法應用（1） 簡介訓練樣本集中一共有80張人臉樣本，主要來自于兩個不同的人，沒人四是張。首先處理人臉圖像數(shù)據(jù)，將其歸一化，一方面一張圖像累加為一行數(shù)據(jù)，灰度級處理為0-1之間，防止溢出。然后調(diào)用梯度下降算法，假設判別函數(shù)是線性的，找出最優(yōu)的權向量。最后輸入測試樣本，同樣對測試樣本歸一化處理，使用判別函數(shù)對人臉圖像進行判別。（2） 實現(xiàn)步驟A. 讀入測試樣本（80張人臉樣本，灰度圖像）。B. 將這些圖像做歸一化處理，即將整個圖像的數(shù)據(jù)歸一化為一行，如x= 123456789，歸一化之后為：X= 123456789。C. 得到測試樣本后，調(diào)用梯度下降算法，假設線性判定函數(shù)，獲得最優(yōu)權向量a。D. 輸入測試樣本，同樣做歸一化處理。E. 將測試樣本帶入假設的線性函數(shù)中，求出函數(shù)值。F. 通過函數(shù)值判斷測試樣本的類別。G. 輸出圖像。（3） 運行gradient.m文件，選擇訓練樣本集。Figure 1（4） 單擊Ok鍵，得到測試結果，如下圖所示：一共有10個測試樣本，測得的值分別為：Figure 2Figure 3Figure 4（1）徐勇教授個人主頁：/default.html （2）模式