ch 07 線性判別函數(shù) - 1

1、Ch 07. 線性判別函數(shù),,模式分類的途徑,途徑1：估計(jì)類條件概率密度通過(guò) 和 ，利用貝葉斯規(guī)則計(jì)算后驗(yàn)概率 ，然后通過(guò)最大后驗(yàn)概率做出決策兩種方法方法1a：概率密度參數(shù)估計(jì)基于對(duì) 的含參數(shù)的描述方法1b：概率密度非參數(shù)估計(jì)基于對(duì) 的非參數(shù)的描述途徑2：直接估計(jì)后驗(yàn)概率不需要先估計(jì)途徑3：直接計(jì)算判別函數(shù)不需要

2、估計(jì) 或者,,判別函數(shù),分類器最常用的表述方式為判別函數(shù) ，每個(gè)類別對(duì)應(yīng)一個(gè)判別函數(shù)基于判別函數(shù)的判決規(guī)則,如果 ，則模式為,判別函數(shù),假設(shè)每一類別的判別函數(shù)形式已知利用訓(xùn)練樣本集可估計(jì)判別函數(shù)中的參數(shù)判別函數(shù)例子,線性判別函數(shù),二次判別函數(shù),線性判別函數(shù),每個(gè)判別函數(shù)是特征向量x的分量的線性組合對(duì)c類問(wèn)題，每個(gè)類i對(duì)應(yīng)一個(gè)線

3、性判別函數(shù)例：兩維情況,線性判別函數(shù)——兩類情況,兩類的判別函數(shù)可用一個(gè)判別函數(shù)來(lái)實(shí)現(xiàn)判別規(guī)則判決面：,線性判別函數(shù)——多類情況,由c個(gè)線性判別函數(shù)構(gòu)成的c類分類器稱為線性機(jī)器（線性機(jī)） 線性機(jī)器的決策規(guī)則為設(shè) 和 是兩個(gè)相鄰的判決域，則它們之間的邊界為超平面Hij的一部分， Hij由 和 分別對(duì)應(yīng)的判別函數(shù)決定 Hij的方向由 決定,線性判別函數(shù)——多類情況,線性機(jī)的判決

4、域和判決面,廣義線性判別函數(shù),二次判別函數(shù)（quadratic discriminant function）多項(xiàng)式判別函數(shù)（polynomial discriminant function）,,廣義線性判別函數(shù),廣義線性判別函數(shù)（generalized linear discriminant function） 是 維權(quán)向量分量函數(shù) 可以是x的任意函數(shù)，可視為特征提取子系統(tǒng)的結(jié)果雖然 不

5、是x的線性函數(shù)，但卻是y的線性函數(shù)，稱為廣義線性判別函數(shù),,廣義線性判別函數(shù),例子1二次型判別函數(shù)定義三維向量y則,,廣義線性判別函數(shù),例子1當(dāng) 時(shí),,廣義線性判別函數(shù),例子2,,廣義線性判別函數(shù),線性判別函數(shù)增廣特征向量（augmented feature vector）y增廣權(quán)向量（augmented weight vector）a將尋找權(quán)向量w和權(quán)閾值

6、 轉(zhuǎn)化為尋找權(quán)向量a,,廣義線性判別函數(shù),判決面 必然穿過(guò)增廣空間的原點(diǎn),,,通過(guò)調(diào)整a，可以投影到原空間（y0=1平面）中的任意線性判決面,兩類線性可分,假設(shè)有一個(gè)包含n個(gè)樣本的集合 ，用這些樣本來(lái)確定判別函數(shù) 中的權(quán)向量a如果存在一個(gè)權(quán)向量（即y空間中存在一個(gè)超平面），能將所有這些樣本正確分類，則這些樣本稱為“線性可分”（linear sep

7、arable）兩類問(wèn)題的規(guī)范化對(duì)于樣本 ，如果 ，則標(biāo)記為 ，如果 ，則標(biāo)記為規(guī)范化：將所有標(biāo)記為 的樣本取負(fù)（ ），則問(wèn)題可以簡(jiǎn)化為：尋找一個(gè)對(duì)所有樣本都有 的權(quán)向量aa：分離向量（separating vector）或解向量（solution vector）,,權(quán)空間與解區(qū)

8、域,所有可能的權(quán)向量構(gòu)成“權(quán)空間”（weight space）。解向量為權(quán)空間中的一點(diǎn)對(duì)每個(gè) ， 確定一個(gè)權(quán)空間中穿過(guò)原點(diǎn)的超平面， 為其法向量解向量必然在每個(gè)訓(xùn)練樣本確定的超平面的正側(cè)，即解向量必然在n個(gè)樣本確定的n個(gè)正半空間的交疊區(qū)中，該交疊區(qū)稱為“解區(qū)域”（solution region），其中任意向量都是解向量,,權(quán)空間與解區(qū)域,,,規(guī)范化前,規(guī)范化后,梯度下降算法,求解向量可通過(guò)最小化某

9、個(gè)準(zhǔn)則函數(shù)J(a)來(lái)實(shí)現(xiàn)梯度下降法用于解決函數(shù)極小化問(wèn)題基本思想：隨意選擇一個(gè)權(quán)向量a(1)作為初始值計(jì)算J(a)在a(1)的梯度向量 ，其負(fù)方向代表從a(1)處J(a)下降最快的方向下一個(gè)值a(2)為從a(1)沿梯度的負(fù)方向移動(dòng)一段距離而得到迭代公式,,,學(xué)習(xí)率（learning rate）,梯度下降算法,,,梯度下降算法,基本梯度下降算法,,梯度下降算法,學(xué)習(xí)率的選擇如果 太小，算

10、法收斂非常緩慢如果 太大，算法可能會(huì)過(guò)沖（overshoot），甚至無(wú)法收斂能否找到每次迭代時(shí)的最優(yōu)學(xué)習(xí)率？使得 到達(dá)沿梯度負(fù)方向的最低點(diǎn),,梯度下降算法,最優(yōu)學(xué)習(xí)率準(zhǔn)則函數(shù)在a(k)附近的二階展開(kāi)式其中， 為J(a)在a(k)的梯度向量，H為赫森矩陣，即J(a)在a(k)的二階偏導(dǎo)代入

11、 得當(dāng) 時(shí)， 最小化,牛頓下降法,直接求使得最小化的a作為a(k+1)迭代公式算法,,牛頓下降法,優(yōu)點(diǎn)牛頓下降法在每一步給出了比梯度下降法更優(yōu)的步長(zhǎng)缺點(diǎn)赫森矩陣H奇異時(shí)，無(wú)法應(yīng)用牛頓下降法即使H非奇異，計(jì)算H的逆矩陣的計(jì)算復(fù)雜度O(d3),,牛頓下降法,,,學(xué)習(xí)率實(shí)戰(zhàn)的選擇,直接將 設(shè)為某個(gè)足夠

12、小的常數(shù)雖然比每一步采用最優(yōu)學(xué)習(xí)率需要更多步驟來(lái)調(diào)整但是，由于不用計(jì)算最優(yōu)學(xué)習(xí)率，總的時(shí)間開(kāi)銷往往更小實(shí)踐中的最常見(jiàn)選擇,,感知器準(zhǔn)則函數(shù),如何構(gòu)建準(zhǔn)則函數(shù)J(a)來(lái)求解向量？令J(a)等于被a確定的決策面錯(cuò)分的樣本數(shù)分段常數(shù)函數(shù)，不利于梯度搜索（梯度往往為0）,,感知器準(zhǔn)則函數(shù),如何構(gòu)建準(zhǔn)則函數(shù)J(a)來(lái)求解向量？感知器準(zhǔn)則函數(shù)（perceptron criterion function）其中， 為被a錯(cuò)

13、分的樣本集感知器準(zhǔn)則函數(shù)正比于錯(cuò)分樣本到判決面距離之和,,感知器準(zhǔn)則函數(shù)最小化,感知器準(zhǔn)則函數(shù)的梯度梯度下降法迭代公式其中， 表示被a(k)錯(cuò)分的樣本集,,感知器準(zhǔn)則函數(shù)最小化,批處理感知器算法,批處理：每次修正權(quán)向量a時(shí)，需要“成批”考慮所有訓(xùn)練樣本,感知器準(zhǔn)則函數(shù)最小化,單樣本校正在批處理感知器算法中，每次校正需要考察所有樣本單樣本校正每次僅考察一個(gè)錯(cuò)分樣本順序考慮輸入樣本，一旦發(fā)現(xiàn)某個(gè)樣本錯(cuò)分，立即對(duì)當(dāng)

14、前權(quán)向量進(jìn)行修正為了保證每個(gè)樣本都可以在序列中無(wú)限次出現(xiàn)，可以使訓(xùn)練樣本按順序不斷循環(huán)出現(xiàn)在序列中，直至算法收斂,,感知器準(zhǔn)則函數(shù)最小化,固定增量單樣本校正假設(shè)樣本序列編號(hào)下標(biāo)表示樣本編號(hào)上標(biāo)表示分錯(cuò)的樣本編號(hào)即迭代公式,,感知器準(zhǔn)則函數(shù)最小化,固定增量單樣本感知器算法,,,感知器準(zhǔn)則函數(shù)最小化,,,感知器準(zhǔn)則函數(shù)最小化,,,感知器準(zhǔn)則函數(shù)最小化,,,感知器準(zhǔn)則函數(shù)最小化,,,感知器準(zhǔn)則函數(shù)最小化,帶邊沿裕量的變?cè)?/p>

15、量感知器算法,,,線性不可分情況,感知器算法本質(zhì)上是“誤差校正方法”（error-correcting procedure）如果問(wèn)題本身線性不可分，則校正過(guò)程可能永遠(yuǎn)無(wú)法結(jié)束,最小平方誤差,包含所有樣本的準(zhǔn)則函數(shù)（不僅僅是錯(cuò)分樣本）不再追求 ，轉(zhuǎn)而令 ，其中 為任意取定的正常數(shù)將線性不等式組求解轉(zhuǎn)換成線性方程組求解,最小平方誤差,樣本個(gè)數(shù)為n，維數(shù)為dY為 矩陣（

16、 ），其第i行為b為列向量則線性方程組可寫為如果Y是非奇異的，則解為通常情況下， ，即Y的行數(shù)大于列數(shù)，線性方程組超定（overdetermined），a通常無(wú)精確解,最小平方誤差,定義誤差向量在a無(wú)解的情況下，求使得誤差向量長(zhǎng)度的平方最小的a，作為線性方程組的近似解最小平方誤差（最小誤差平方和）準(zhǔn)則函數(shù),Widrow-Hoff算法,采用梯度下降法來(lái)求

17、 的極小值遞歸公式,,Widrow-Hoff算法,考慮單樣本情況：Widrow-Hoff算法或最小均方（LMS）算法算法描述,Widrow-Hoff算法,Widrow-Hoff算法將訓(xùn)練點(diǎn)到超平面的距離平方和最小化即使在線性可分情況下， Widrow-Hoff算法的解也可能不能將所有訓(xùn)練樣本完全正確分類但是， Widrow-Hoff算法在線性可分和不可分情況下，都能得到不錯(cuò)的近似解,支持向量機(jī),

18、支持向量機(jī)（Support Vector Machine, SVM）依賴于對(duì)數(shù)據(jù)的一種特殊預(yù)處理，從而實(shí)現(xiàn)對(duì)線性不可分?jǐn)?shù)據(jù)的較好分類該預(yù)處理通過(guò)一個(gè)非線性映射 將原數(shù)據(jù)映射到一個(gè)更高維的空間 ，使得在此高維空間中的映射點(diǎn) 線性可分,盡管SVM自上世紀(jì)90年代開(kāi)始成為一個(gè)非常熱門的領(lǐng)域，其基本思想?yún)s早在1963年就由V.N. Vapnik提出來(lái)了。,[1] Vladimir N. V

19、apnik, “Statistical Learning Theory”, Wiley-Interscience, 1998[2] Vladimir N. Vapnik, “The Nature of Statistical Learning Theory”, Springer , 1995,支持向量機(jī),哪個(gè)線性判決面最好？,,,,支持向量機(jī),間隔（margin）模式到判決面的最小距離稱為分類間隔（margin）一般認(rèn)為，分

20、類間隔越大的判決面越好離判決面最近的樣本點(diǎn)稱為支持向量（support vector）,,支持向量,,支持向量,,支持向量,支持向量機(jī),高維空間中權(quán)向量a和映射點(diǎn)y都是增廣的，則判別函數(shù)為類別標(biāo)記 表示 屬于 表示 屬于設(shè)邊沿裕量為1，則有,支持向量機(jī),樣本點(diǎn)到判決面的距離優(yōu)化目標(biāo)最大化 ，即最小化約束條件,,支持向量機(jī),SVM的訓(xùn)練,,Ku

21、hn-Tucker構(gòu)造法,二次規(guī)劃問(wèn)題,,最大化,最小化,共軛梯度法 內(nèi)點(diǎn)法 active set ……,s.t.,支持向量機(jī),非線性映射,基本思想：當(dāng)原訓(xùn)練樣本線性不可分時(shí)，可利用某個(gè)非線性變換，將原數(shù)據(jù)空間中的樣本點(diǎn)映射到更高維空間中，使得在此高維空間中的映射點(diǎn)線性可分,支持向量機(jī),非線性映射,支持向量機(jī),非線性映射非線性映射 反映了設(shè)計(jì)者的先驗(yàn)知識(shí)在缺乏先驗(yàn)知識(shí)的前提下，常用的非線性映射函數(shù)有：多項(xiàng)式函數(shù)、高斯函數(shù)等

22、,支持向量機(jī),核技巧（kernel trick）線性分類器僅僅依賴于內(nèi)積計(jì)算如果所有樣本點(diǎn)都映射到高維（甚至可能為無(wú)限維）空間中 ，在此高維空間中的內(nèi)積計(jì)算 往往很難計(jì)算或根本無(wú)法計(jì)算核函數(shù)指原數(shù)據(jù)空間中對(duì)應(yīng)于變換后空間中內(nèi)積計(jì)算的某種函數(shù),這表明：較復(fù)雜的高維空間中的內(nèi)積計(jì)算可以通過(guò)低維空間中的核函數(shù)間接進(jìn)行,如果一個(gè)問(wèn)題僅包含內(nèi)積計(jì)算，則可以不指定具

23、體的映射函數(shù)，而僅需知道該映射函數(shù)對(duì)應(yīng)的核函數(shù),支持向量機(jī),核技巧（kernel trick）什么樣的函數(shù)可以作為核函數(shù)？Mercer定理任何半正定對(duì)稱函數(shù)都可以作為核函數(shù)半正定由 組成的矩陣A為半正定矩陣，即對(duì)任意非零實(shí)數(shù)向量z，有對(duì)稱,支持向量機(jī),核技巧（kernel trick）常用的核函數(shù)多項(xiàng)式核高斯核反曲函數(shù),推廣到多類問(wèn)題,前述算法多假設(shè)兩類前提推

24、廣到多類如果 線性可分，則存在一個(gè)權(quán)向量集 ，當(dāng) 時(shí)，對(duì)所有 ，有 確定后，對(duì)測(cè)試樣本y，如果對(duì)所有 ，有則判斷y屬于第i類,推廣到多類問(wèn)題,Kesler構(gòu)造法假設(shè) ，則等價(jià)的， 維權(quán)向量能將c-1個(gè) 維樣本集（如下頁(yè)

25、所示）正確分類,推廣到多類問(wèn)題,Kesler構(gòu)造法,每個(gè) 對(duì)應(yīng)于將屬于 和 的樣本規(guī)范化，即屬于 的樣本取負(fù)，這樣可以保證 ，多類問(wèn)題成功轉(zhuǎn)化為兩類問(wèn)題,推廣到多類問(wèn)題,Kesler構(gòu)造法當(dāng) 時(shí)，可類似構(gòu)造c-1個(gè) 維訓(xùn)練樣本 ，其中第i個(gè)子向量為y，第j個(gè)子向量為-y，其余都為0如果對(duì)于所有 ，都有

26、 ，則 中的分量構(gòu)成能將多類樣本集正確分類的線性機(jī)的c個(gè)權(quán)向量,小結(jié),判別函數(shù)基于判別函數(shù)的判決規(guī)則線性判別函數(shù)二次判別函數(shù)多項(xiàng)式判別函數(shù),如果 ，則模式為,小結(jié),廣義線性判別函數(shù)兩類線性可分情況兩類問(wèn)題的規(guī)范化解向量權(quán)空間解區(qū)域,,小結(jié),梯度下降法牛頓下降法感知器準(zhǔn)則函數(shù)感知器準(zhǔn)則函數(shù)最小化批處理感知器算法單樣本校正固定增量單