Ch 07 線性判別函數(shù)

1、ch 07. 線性判別函數(shù)模式分類的途徑 途徑途徑1：估計(jì)類條件概率密度 通過 和 ，利用貝葉斯規(guī)則計(jì)算后驗(yàn)概率 ，然后通過最大后驗(yàn)概率做出決策 兩種方法 方法方法1a：概率密度參數(shù)估計(jì)基于對(duì) 的含參數(shù)的描述 方法方法1b：概率密度非參數(shù)估計(jì)基于對(duì) 的非參數(shù)的描述 途徑途徑2：直接估計(jì)后驗(yàn)概率 不需要先估計(jì) 途徑途徑3：直接計(jì)算判別函數(shù) 不需要估計(jì) 或者判別函數(shù) 分類器最常用的表述方式為判別函數(shù) ，每個(gè)類別對(duì)應(yīng)一個(gè)判別函數(shù) 基于判別函數(shù)的判決規(guī)則如果 ，則模式為判別函數(shù) 假設(shè)每一類別的判別函數(shù)形式已知 利用訓(xùn)練樣本集可估計(jì)判別函數(shù)中的參數(shù) 判別函數(shù)例子線性判別函數(shù)線性判別函數(shù)二次判別函數(shù)二次判

2、別函數(shù)線性判別函數(shù) 每個(gè)判別函數(shù)是特征向量x的分量的線性組合 對(duì)c類問題，每個(gè)類i對(duì)應(yīng)一個(gè)線性判別函數(shù) 例：兩維情況線性判別函數(shù)兩類情況 兩類的判別函數(shù) 可用一個(gè)判別函數(shù)來(lái)實(shí)現(xiàn) 判別規(guī)則 判決面：線性判別函數(shù)多類情況 由c個(gè)線性判別函數(shù)構(gòu)成的c類分類器稱為線性機(jī)線性機(jī)器器（線性機(jī)線性機(jī)） 線性機(jī)器的決策規(guī)則為 設(shè) 和 是兩個(gè)相鄰的判決域，則它們之間的邊界為超平面hij的一部分， hij由 和 分別對(duì)應(yīng)的判別函數(shù)決定 hij的方向由 決定線性判別函數(shù)多類情況 線性機(jī)的判決域和判決面廣義線性判別函數(shù) 二次判別函數(shù)（quadratic discriminant function） 多項(xiàng)式判別函數(shù)（p

3、olynomial discriminant function）111dddijkijkijkw x x x廣義線性判別函數(shù) 廣義線性判別函數(shù)廣義線性判別函數(shù)（generalized linear discriminant function） 是 維權(quán)向量 分量函數(shù) 可以是x的任意函數(shù)，可視為特征提取子系統(tǒng)的結(jié)果 雖然 不是x的線性函數(shù)，但卻是y的線性函數(shù)，稱為廣義線性判別函數(shù)廣義線性判別函數(shù)廣義線性判別函數(shù) 例子1 二次型判別函數(shù) 定義三維向量y 則112233( )tg xa ya ya y a y廣義線性判別函數(shù) 例子1 當(dāng) 時(shí)廣義線性判別函數(shù) 例子2廣義線性判別函數(shù) 線性判別函數(shù) 增廣

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

5、兩類問題的規(guī)范化 對(duì)于樣本 ，如果 ，則標(biāo)記為 ，如果 ，則標(biāo)記為 規(guī)范化：將所有標(biāo)記為 的樣本取負(fù)（ ），則問題可以簡(jiǎn)化為：尋找一個(gè)對(duì)所有樣本都有 的權(quán)向量a a：分離向量（separating vector）或解向量（solution vector）ii yy權(quán)空間與解區(qū)域 所有可能的權(quán)向量構(gòu)成“權(quán)空間權(quán)空間”（weight space）。 解向量為權(quán)空間中的一點(diǎn) 對(duì)每個(gè) ， 確定一個(gè)權(quán)空間中穿過原點(diǎn)的超平面， 為其法向量 解向量必然在每個(gè)訓(xùn)練樣本確定的超平面的正側(cè)，即解向量必然在n個(gè)樣本確定的n個(gè)正半空間的交疊區(qū)中，該交疊區(qū)稱為“解區(qū)域解區(qū)域”（solution region），其中任意

6、向量都是解向量權(quán)空間與解區(qū)域規(guī)范化前規(guī)范化前規(guī)范化后規(guī)范化后梯度下降算法 求解向量可通過最小化某個(gè)準(zhǔn)則函數(shù)j(a)來(lái)實(shí)現(xiàn) 梯度下降法用于解決函數(shù)極小化問題 基本思想： 隨意選擇一個(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í)率（學(xué)習(xí)率（learning rate）梯度下降算法梯度下降算法 基本梯度下降算法梯度下降算法 學(xué)習(xí)率的選擇 如果 太小，算法收斂非常緩慢 如果 太大，算法可能會(huì)過沖（overshoot），甚至無(wú)法收斂 能否找到每次迭代時(shí)的最優(yōu)學(xué)習(xí)率最

7、優(yōu)學(xué)習(xí)率？ 使得 到達(dá)沿梯度負(fù)方向的最低點(diǎn)梯度下降算法 最優(yōu)學(xué)習(xí)率 準(zhǔn)則函數(shù)在a(k)附近的二階展開式其中， 為j(a)在a(k)的梯度向量，h為赫森矩陣，即j(a)在a(k)的二階偏導(dǎo)代入 得當(dāng) 時(shí)， 最小化2ijijjha a 最優(yōu)學(xué)習(xí)率最優(yōu)學(xué)習(xí)率牛頓下降法 直接求使得最小化的a作為a(k+1) 迭代公式 算法牛頓下降法 優(yōu)點(diǎn)優(yōu)點(diǎn) 牛頓下降法在每一步給出了比梯度下降法更優(yōu)的步長(zhǎng) 缺點(diǎn)缺點(diǎn) 赫森矩陣h奇異時(shí)，無(wú)法應(yīng)用牛頓下降法 即使h非奇異，計(jì)算h的逆矩陣的計(jì)算復(fù)雜度o(d3)牛頓下降法學(xué)習(xí)率實(shí)戰(zhàn)的選擇 直接將 設(shè)為某個(gè)足夠小的常數(shù) 雖然比每一步采用最優(yōu)學(xué)習(xí)率需要更多步驟來(lái)調(diào)整 但是，由于不

8、用計(jì)算最優(yōu)學(xué)習(xí)率，總的時(shí)間開銷往往更小 實(shí)踐中的最常見選擇實(shí)踐中的最常見選擇感知器準(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ò)分的樣本集 感知器準(zhǔn)則函數(shù)正比于錯(cuò)分樣本到判決面距離之和感知器準(zhǔn)則函數(shù)最小化 感知器準(zhǔn)則函數(shù)的梯度 梯度下降法迭代公式 其中， 表示被a(k)錯(cuò)分的樣本集感知器準(zhǔn)則函數(shù)最小化 批處理感知器算法批處理批處理：每次修正權(quán)向量：每次修正權(quán)向量

9、a時(shí)，需要時(shí)，需要“成批成批”考慮所有訓(xùn)練樣本考慮所有訓(xùn)練樣本感知器準(zhǔn)則函數(shù)最小化 單樣本校正 在批處理感知器算法中，每次校正需要考察所有樣本 單樣本校正每次僅考察一個(gè)錯(cuò)分樣本 順序考慮輸入樣本，一旦發(fā)現(xiàn)某個(gè)樣本錯(cuò)分，立即對(duì)當(dāng)前權(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)即 迭代公式( )1k感知器準(zhǔn)則函數(shù)最小化 固定增量單樣本感知器算法kaay感知器準(zhǔn)則函數(shù)最小化感知器準(zhǔn)則函數(shù)最小化感知器準(zhǔn)則函數(shù)最小化感知器準(zhǔn)則函數(shù)最小化感

10、知器準(zhǔn)則函數(shù)最小化 帶邊沿裕量的變?cè)隽扛兄魉惴?tkba ytkba y( )kkaay線性不可分情況 感知器算法本質(zhì)上是“誤差校正方法”（error-correcting procedure） 如果問題本身線性不可分，則校正過程可能永遠(yuǎn)無(wú)法結(jié)束最小平方誤差 包含所有樣本的準(zhǔn)則函數(shù)（不僅僅是錯(cuò)分樣本） 不再追求 ，轉(zhuǎn)而令 ，其中 為任意取定的正常數(shù)正常數(shù) 將線性不等式組線性不等式組求解轉(zhuǎn)換成線性方程組線性方程組求解0tia ytiiba yib最小平方誤差 樣本個(gè)數(shù)為n，維數(shù)為d y為 矩陣（ ），其第i行為 b為列向量 則線性方程組可寫為 如果y是非奇異的，則解為 通常情況下， ，即y的行

11、數(shù)大于列數(shù)，線性方程組超定（overdetermined），a通常無(wú)精確解n d1ddtiynd最小平方誤差 定義誤差向量 在a無(wú)解的情況下，求使得誤差向量長(zhǎng)度的平方最小的a，作為線性方程組的近似解 最小平方誤差最小平方誤差（最小誤差平方和最小誤差平方和）準(zhǔn)則函數(shù)widrow-hoff算法 采用梯度下降法來(lái)求 的極小值遞歸公式widrow-hoff算法 考慮單樣本情況：widrow-hoff算法或最小均方（lms）算法算法描述widrow-hoff算法 widrow-hoff算法將訓(xùn)練點(diǎn)到超平面的距離平方和最小化 即使在線性可分情況下， widrow-hoff算法的解也可能不能將所有訓(xùn)練樣本完

12、全正確分類 但是， widrow-hoff算法在線性可分和不可分情況下，都能得到不錯(cuò)的近似解支持向量機(jī) 支持向量機(jī)（support vector machine, svm）依賴于對(duì)數(shù)據(jù)的一種特殊預(yù)處理，從而實(shí)現(xiàn)對(duì)線性不可分?jǐn)?shù)據(jù)的較好分類 該預(yù)處理通過一個(gè)非線性映射 將原數(shù)據(jù)映射到一個(gè)更高維的空間 ，使得在此高維空間中的映射點(diǎn) 線性可分盡管盡管svm自上世紀(jì)自上世紀(jì)90年代開始成為一個(gè)非常熱門的領(lǐng)域，年代開始成為一個(gè)非常熱門的領(lǐng)域，其基本思想?yún)s早在其基本思想?yún)s早在1963年就由年就由v.n. vapnik提出來(lái)了。提出來(lái)了。1 vladimir n. vapnik, “statistical l

13、earning theory”, wiley-interscience, 19982 vladimir n. vapnik, “the nature of statistical learning theory”, springer , 1995支持向量機(jī) 哪個(gè)線性判決面最好？支持向量機(jī) 間隔間隔（margin） 模式到判決面的最小距離稱為分類間隔（margin） 一般認(rèn)為，分類一般認(rèn)為，分類間隔越大的判決間隔越大的判決面越好面越好 離判決面最近的樣本點(diǎn)稱為支持支持向量向量（support vector）支持向量支持向量支持向量支持向量支持向量支持向量支持向量機(jī) 高維空間中權(quán)向量a和映射點(diǎn)y都

14、是增廣的，則判別函數(shù)為 類別標(biāo)記 表示 屬于 表示 屬于 設(shè)邊沿裕量為1，則有1kz kx11kz kx2支持向量機(jī) 樣本點(diǎn)到判決面的距離 優(yōu)化目標(biāo)最大化 ，即最小化約束條件()()1kkkgz gyyaaa分類間隔分類間隔1aa支持向量機(jī) svm的訓(xùn)練kuhn-tucker構(gòu)造法構(gòu)造法二次規(guī)劃問題二次規(guī)劃問題最大化最小化 共軛梯度法共軛梯度法 內(nèi)點(diǎn)法內(nèi)點(diǎn)法 active set s.t.支持向量機(jī) 非線性映射基本思想：當(dāng)原訓(xùn)練樣本線性不可分時(shí)，可利用某個(gè)非線基本思想：當(dāng)原訓(xùn)練樣本線性不可分時(shí)，可利用某個(gè)非線性變換，將原數(shù)據(jù)空間中的樣本點(diǎn)映射到更高維空間中，性變換，將原數(shù)據(jù)空間中的樣本點(diǎn)映射到

15、更高維空間中，使得在此高維空間中的映射點(diǎn)線性可分使得在此高維空間中的映射點(diǎn)線性可分:()kkyx支持向量機(jī) 非線性映射支持向量機(jī) 非線性映射 非線性映射 反映了設(shè)計(jì)者的先驗(yàn)知識(shí) 在缺乏先驗(yàn)知識(shí)的前提下，常用的非線性映射函數(shù)有：多項(xiàng)式函數(shù)多項(xiàng)式函數(shù)、高斯函數(shù)高斯函數(shù)等支持向量機(jī) 核技巧（kernel trick） 線性分類器僅僅依賴于內(nèi)積計(jì)算內(nèi)積計(jì)算 如果所有樣本點(diǎn)都映射到高維（甚至可能為無(wú)限維）空間中 ，在此高維空間中的內(nèi)積計(jì)算 往往很難計(jì)算或根本無(wú)法計(jì)算 核函數(shù)指原數(shù)據(jù)空間中對(duì)應(yīng)于變換后空間中內(nèi)積計(jì)算的某種函數(shù)tijx x:()kkyx()()tijxx(,)()()tijijkx xxx這

16、表明：較復(fù)雜的高維空間中的內(nèi)積計(jì)算可以通過低維空間中這表明：較復(fù)雜的高維空間中的內(nèi)積計(jì)算可以通過低維空間中的核函數(shù)間接進(jìn)行的核函數(shù)間接進(jìn)行如果一個(gè)問題僅包含內(nèi)積計(jì)算，則可以不指定具體的映射函數(shù)，如果一個(gè)問題僅包含內(nèi)積計(jì)算，則可以不指定具體的映射函數(shù)，而僅需知道該映射函數(shù)對(duì)應(yīng)的核函數(shù)而僅需知道該映射函數(shù)對(duì)應(yīng)的核函數(shù)支持向量機(jī) 核技巧（kernel trick） 什么樣的函數(shù)可以作為核函數(shù)？ mercer定理定理任何半正定對(duì)稱函數(shù)都可以作為核函數(shù)任何半正定對(duì)稱函數(shù)都可以作為核函數(shù) 半正定半正定由由 組成的矩陣組成的矩陣a為半正定矩陣，即對(duì)任意非零實(shí)數(shù)為半正定矩陣，即對(duì)任意非零實(shí)數(shù)向量向量z，有，有

17、 對(duì)稱對(duì)稱(,)ijijakx x0tz az(,)(,)ijjikkx xx x支持向量機(jī) 核技巧（kernel trick） 常用的核函數(shù) 多項(xiàng)式核多項(xiàng)式核 高斯核高斯核 反曲函數(shù)反曲函數(shù)( , )(1)tdkx yx y22( , )exp2xykx y( , )tanh()tkkx yx y推廣到多類問題 前述算法多假設(shè)兩類前提 推廣到多類 如果 線性可分，則存在一個(gè)權(quán)向量集 ，當(dāng) 時(shí)，對(duì)所有 ，有 確定后，對(duì)測(cè)試樣本y，如果對(duì)所有 ，有則判斷y屬于第i類ttija ya y推廣到多類問題 kesler構(gòu)造法 假設(shè) ，則 等價(jià)的， 維權(quán)向量能將c-1個(gè) 維樣本集（如下頁(yè)所示）正確分類10,2,ttjjc a ya y推廣到多類問題 kesler構(gòu)造法每個(gè)每個(gè) 對(duì)應(yīng)于將屬于對(duì)應(yīng)于將屬于 和和 的樣本規(guī)范化，即屬于的樣本規(guī)范化，即屬于 的的樣本取負(fù)，這樣可以保證樣本取負(fù)，這樣可以保證 ，多類問題多類問題成功轉(zhuǎn)化為成功轉(zhuǎn)化為兩類問題兩類問題10tj 推廣到多類問題 kesler構(gòu)造法 當(dāng) 時(shí)，可類似構(gòu)造c-1個(gè) 維訓(xùn)練樣本 ，其中第i個(gè)子向量為y，第j個(gè)子向量為-y，其余都為0 如果對(duì)于所有 ，都有 ，則 中的分量構(gòu)成能將多類樣本集正確分類的線性機(jī)的c個(gè)權(quán)向量小結(jié) 判別函數(shù) 基于判別函數(shù)的判決規(guī)則 線性判別函數(shù) 二次判別函數(shù) 多項(xiàng)式判別函數(shù)如果 ，則模式為小