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

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

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

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

4、域和判決面,廣義線性判別函數(shù),二次判別函數(shù)（quadratic discriminant function）多項式判別函數(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ù),例子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ù),判決面 必然穿過增廣空間的原點,,,通過調(diào)整a，可以投影到原空間（y0=1平面）中的任意線性判決面,兩類線性可分,假設(shè)有一個包含n個樣本的集合 ，用這些樣本來確定判別函數(shù) 中的權(quán)向量a如果存在一個權(quán)向量（即y空間中存在一個超平面），能將所有這些樣本正確分類，則這些樣本稱為“線性可分”（linear sep

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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