梯度下降算法說(shuō)明.doc

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