SVM_支持向量機基本原理及應用.ppt

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