SVM_支持向量機(jī)基本原理及應(yīng)用.ppt

支持向量機(jī) supportvectormachine SVM WangJiminNov18 2005 Outline SVM的理論基礎(chǔ)線性判別函數(shù)和判別面最優(yōu)分類面支持向量機(jī)SVM的研究與應(yīng)用 SVM的理論基礎(chǔ) 傳統(tǒng)的統(tǒng)計(jì)模式識(shí)別方法只有在樣本趨向無(wú)窮大時(shí) 其性能才有理論的保證 統(tǒng)計(jì)學(xué)習(xí)理論 STL 研究有限樣本情況下的機(jī)器學(xué)習(xí)問(wèn)題 SVM的理論基礎(chǔ)就是統(tǒng)計(jì)學(xué)習(xí)理論 傳統(tǒng)的統(tǒng)計(jì)模式識(shí)別方法在進(jìn)行機(jī)器學(xué)習(xí)時(shí) 強(qiáng)調(diào)經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化 而單純的經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化會(huì)產(chǎn)生 過(guò)學(xué)習(xí)問(wèn)題 其推廣能力較差 推廣能力是指 將學(xué)習(xí)機(jī)器 即預(yù)測(cè)函數(shù) 或稱學(xué)習(xí)函數(shù) 學(xué)習(xí)模型 對(duì)未來(lái)輸出進(jìn)行正確預(yù)測(cè)的能力 過(guò)學(xué)習(xí)問(wèn)題 過(guò)學(xué)習(xí)問(wèn)題 某些情況下 當(dāng)訓(xùn)練誤差過(guò)小反而會(huì)導(dǎo)致推廣能力的下降 例如 對(duì)一組訓(xùn)練樣本 x y x分布在實(shí)數(shù)范圍內(nèi) y取值在 0 1 之間 無(wú)論這些樣本是由什么模型產(chǎn)生的 我們總可以用y sin w x 去擬合 使得訓(xùn)練誤差為0 SVM 根據(jù)統(tǒng)計(jì)學(xué)習(xí)理論 學(xué)習(xí)機(jī)器的實(shí)際風(fēng)險(xiǎn)由經(jīng)驗(yàn)風(fēng)險(xiǎn)值和置信范圍值兩部分組成 而基于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化準(zhǔn)則的學(xué)習(xí)方法只強(qiáng)調(diào)了訓(xùn)練樣本的經(jīng)驗(yàn)風(fēng)險(xiǎn)最小誤差 沒有最小化置信范圍值 因此其推廣能力較差 Vapnik提出的支持向量機(jī) SupportVectorMachine SVM 以訓(xùn)練誤差作為優(yōu)化問(wèn)題的約束條件 以置信范圍值最小化作為優(yōu)化目標(biāo) 即SVM是一種基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化準(zhǔn)則的學(xué)習(xí)方法 其推廣能力明顯優(yōu)于一些傳統(tǒng)的學(xué)習(xí)方法 形成時(shí)期在1992 1995年 SVM 由于SVM的求解最后轉(zhuǎn)化成二次規(guī)劃問(wèn)題的求解 因此SVM的解是全局唯一的最優(yōu)解SVM在解決小樣本 非線性及高維模式識(shí)別問(wèn)題中表現(xiàn)出許多特有的優(yōu)勢(shì) 并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問(wèn)題中Joachims最近采用SVM在Reuters 21578來(lái)進(jìn)行文本分類 并聲稱它比當(dāng)前發(fā)表的其他方法都好 Outline SVM的理論基礎(chǔ)線性判別函數(shù)和判別面最優(yōu)分類面支持向量機(jī)SVM的研究與應(yīng)用 線性判別函數(shù)和判別面 一個(gè)線性判別函數(shù) discriminantfunction 是指由x的各個(gè)分量的線性組合而成的函數(shù)兩類情況 對(duì)于兩類問(wèn)題的決策規(guī)則為如果g x 0 則判定x屬于C1 如果g x 0 則判定x屬于C2 如果g x 0 則可以將x任意分到某一類或者拒絕判定 線性判別函數(shù) 下圖表示一個(gè)簡(jiǎn)單的線性分類器 具有d個(gè)輸入的單元 每個(gè)對(duì)應(yīng)一個(gè)輸入向量在各維上的分量值 該圖類似于一個(gè)神經(jīng)元 超平面 方程g x 0定義了一個(gè)判定面 它把歸類于C1的點(diǎn)與歸類于C2的點(diǎn)分開來(lái) 當(dāng)g x 是線性函數(shù)時(shí) 這個(gè)平面被稱為 超平面 hyperplane 當(dāng)x1和x2都在判定面上時(shí) 這表明w和超平面上任意向量正交 并稱w為超平面的法向量 注意到 x1 x2表示超平面上的一個(gè)向量 判別函數(shù)g x 是特征空間中某點(diǎn)x到超平面的距離的一種代數(shù)度量 從下圖容易看出 上式也可以表示為 r g x w 當(dāng)x 0時(shí) 表示原點(diǎn)到超平面的距離 r0 g 0 w w0 w 標(biāo)示在上圖中 總之 線性判別函數(shù)利用一個(gè)超平面把特征空間分隔成兩個(gè)區(qū)域 超平面的方向由法向量w確定 它的位置由閾值w0確定 判別函數(shù)g x 正比于x點(diǎn)到超平面的代數(shù)距離 帶正負(fù)號(hào) 當(dāng)x點(diǎn)在超平面的正側(cè)時(shí) g x 0 當(dāng)x點(diǎn)在超平面的負(fù)側(cè)時(shí) g x 0 多類的情況 利用線性判別函數(shù)設(shè)計(jì)多類分類器有多種方法 例如可以把k類問(wèn)題轉(zhuǎn)化為k個(gè)兩類問(wèn)題 其中第i個(gè)問(wèn)題是用線性判別函數(shù)把屬于Ci類與不屬于Ci類的點(diǎn)分開 更復(fù)雜一點(diǎn)的方法是用k k 1 2個(gè)線性判別函數(shù) 把樣本分為k個(gè)類別 每個(gè)線性判別函數(shù)只對(duì)其中的兩個(gè)類別分類 廣義線性判別函數(shù) 在一維空間中 沒有任何一個(gè)線性函數(shù)能解決下述劃分問(wèn)題 黑紅各代表一類數(shù)據(jù) 可見線性判別函數(shù)有一定的局限性 廣義線性判別函數(shù) 如果建立一個(gè)二次判別函數(shù)g x x a x b 則可以很好的解決上述分類問(wèn)題 決策規(guī)則仍是 如果g x 0 則判定x屬于C1 如果g x 0 則判定x屬于C2 如果g x 0 則可以將x任意分到某一類或者拒絕判定 廣義線性判別函數(shù) 廣義線性判別函數(shù) 設(shè)計(jì)線性分類器 Fisher線性判別方法 如 Fisher線性判別方法 主要解決把d維空間的樣本投影到一條直線上 形成一維空間 即把維數(shù)壓縮到一維 然而在d維空間分得很好的樣本投影到一維空間后 可能混到一起而無(wú)法分割 但一般情況下總可以找到某個(gè)方向 使得在該方向的直線上 樣本的投影能分開的最好 目的是降維 在低維空間中分割 Outline SVM的理論基礎(chǔ)線性判別函數(shù)和判別面最優(yōu)分類面支持向量機(jī)SVM的研究與應(yīng)用 最優(yōu)分類面 SVM是從線性可分情況下的最優(yōu)分類面發(fā)展而來(lái)的 基本思想可用圖2的兩維情況說(shuō)明 圖中 方形點(diǎn)和圓形點(diǎn)代表兩類樣本 H為分類線 H1 H2分別為過(guò)各類中離分類線最近的樣本且平行于分類線的直線 它們之間的距離叫做分類間隔 margin 所謂最優(yōu)分類線就是要求分類線不但能將兩類正確分開 訓(xùn)練錯(cuò)誤率為0 而且使分類間隔最大 推廣到高維空間 最優(yōu)分類線就變?yōu)樽顑?yōu)分類面 最優(yōu)分類面 如何求最優(yōu)分類面 最優(yōu)分類面 Outline SVM的理論基礎(chǔ)線性判別函數(shù)和判別面最優(yōu)分類面支持向量機(jī)SVM的研究與應(yīng)用 支持向量機(jī) 上節(jié)所得到的最優(yōu)分類函數(shù)為 該式只包含待分類樣本與訓(xùn)練樣本中的支持向量的內(nèi)積運(yùn)算 可見 要解決一個(gè)特征空間中的最優(yōu)線性分類問(wèn)題 我們只需要知道這個(gè)空間中的內(nèi)積運(yùn)算即可 對(duì)非線性問(wèn)題 可以通過(guò)非線性變換轉(zhuǎn)化為某個(gè)高維空間中的線性問(wèn)題 在變換空間求最優(yōu)分類面 這種變換可能比較復(fù)雜 因此這種思路在一般情況下不易實(shí)現(xiàn) 支持向量機(jī) 核函數(shù)的選擇 SVM方法的特點(diǎn) 非線性映射是SVM方法的理論基礎(chǔ) SVM利用內(nèi)積核函數(shù)代替向高維空間的非線性映射 對(duì)特征空間劃分的最優(yōu)超平面是SVM的目標(biāo) 最大化分類邊際的思想是SVM方法的核心 支持向量是SVM的訓(xùn)練結(jié)果 在SVM分類決策中起決定作用的是支持向量 SVM是一種有堅(jiān)實(shí)理論基礎(chǔ)的新穎的小樣本學(xué)習(xí)方法 它基本上不涉及概率測(cè)度及大數(shù)定律等 因此不同于現(xiàn)有的統(tǒng)計(jì)方法 從本質(zhì)上看 它避開了從歸納到演繹的傳統(tǒng)過(guò)程 實(shí)現(xiàn)了高效的從訓(xùn)練樣本到預(yù)報(bào)樣本的 轉(zhuǎn)導(dǎo)推理 transductiveinference 大大簡(jiǎn)化了通常的分類和回歸等問(wèn)題 SVM方法的特點(diǎn) SVM的最終決策函數(shù)只由少數(shù)的支持向量所確定 計(jì)算的復(fù)雜性取決于支持向量的數(shù)目 而不是樣本空間的維數(shù) 這在某種意義上避免了 維數(shù)災(zāi)難 少數(shù)支持向量決定了最終結(jié)果 這不但可以幫助我們抓住關(guān)鍵樣本 剔除 大量冗余樣本 而且注定了該方法不但算法簡(jiǎn)單 而且具有較好的 魯棒 性 這種 魯棒 性主要體現(xiàn)在 增 刪非支持向量樣本對(duì)模型沒有影響 支持向量樣本集具有一定的魯棒性 有些成功的應(yīng)用中 SVM方法對(duì)核的選取不敏感 Outline SVM的理論基礎(chǔ)線性判別函數(shù)和判別面最優(yōu)分類面支持向量機(jī)SVM的研究與應(yīng)用 SVM應(yīng)用 近年來(lái)SVM方法已經(jīng)在圖像識(shí)別 信號(hào)處理和基因圖譜識(shí)別等方面得到了成功的應(yīng)用 顯示了它的優(yōu)勢(shì) SVM通過(guò)核函數(shù)實(shí)現(xiàn)到高維空間的非線性映射 所以適合于解決本質(zhì)上非線性的分類 回歸和密度函數(shù)估計(jì)等問(wèn)題 支持向量方法也為樣本分析 因子篩選 信息壓縮 知識(shí)挖掘和數(shù)據(jù)修復(fù)等提供了新工具 支持向量機(jī)的研究 對(duì)支持向量機(jī)的研究主要集中在對(duì)SVM本身性質(zhì)的研究以及加大支持向量機(jī)應(yīng)用研究的深度和廣度兩方面 SVM訓(xùn)練算法傳統(tǒng)的利用標(biāo)準(zhǔn)二次型優(yōu)化技術(shù)解決對(duì)偶問(wèn)題的方法 是SVM訓(xùn)練算法慢及受到訓(xùn)練樣本集規(guī)模制約的主要原因 目前已提出了許多解決方法和改進(jìn)算法 主要是從如何處理大規(guī)模樣本集的訓(xùn)練問(wèn)題 提高訓(xùn)練算法收斂速度等方面改進(jìn) 主要有 分解方法 修改優(yōu)化問(wèn)題法 增量學(xué)習(xí)法 幾何方法等分別討論 SVM分類算法 SVM分類算法訓(xùn)練好SVM分類器后 得到的支持向量被用來(lái)構(gòu)成決策分類面 對(duì)于大規(guī)模樣本集問(wèn)題 SVM訓(xùn)練得到的支持向量數(shù)目很大 則進(jìn)行分類決策時(shí)的計(jì)算代價(jià)就是一個(gè)值得考慮的問(wèn)題 解決方法如 縮減集 Red