第10章統計學習理論與支持向量機 統計學習理論為基于小樣本的統計理論支持向量機為基于統計學習理論的應用工具 統計學習理論的提出 傳統模式識別理論的基礎為樣本數目足夠大 實際上 樣本的數目是有限的 統計學習理論為基于小樣本的統計理論 應用目標 有限樣本條件下 統計模式識別與機器學習問題的理論框架 為當前國際上機器學習領域的研究熱點 10 1引言 基于數據的機器學習問題 現代智能技術的一個重要方面 研究對象 現實世界中 大量的 目前無法準確認識 但可以觀測的事物 由觀測數據表征 研究目的 利用觀測數據 得到目前不能通過原理分析來得到的規律 規律 為各學科方向的規律 用于分類學 即模式識別用于模型學 即參數模型的辯識用于系統控制 即學習控制問題 傳統統計學 漸進理論 即樣本數目趨于無窮大 表現為 統計學中關于估計的一致性 無偏性與估計方差的有界性 統計學習理論研究的歷史 60年代 著手研究有限樣本條件下的機器學習問題 研究成果為 經驗風險最小化與有序風險最小化問題 90年代 由于需要 人工神經網絡用于機器學習中的問題引出 網絡結構的確定問題 高維空間 過學習與欠學習問題 局部極值問題等等 統計學習理論是研究機器學習問題中更為本質的問題 92年提出支持向量機 SupportVectorMachine SVM 統計學習理論的一個應用模型 其優勢表現在 小樣本 非線性 高維數空間的模式識別中 可以推廣到其他有關機器學習問題的應用中如 函數擬合 參數辯識 學習控制等 10 2機器學習的基本問題與方法 基本問題有 1機器學習問題的表示方法2經驗風險最小化與期望風險最小化3機器學習中的復雜性與推廣性 10 2 1機器學習問題的表示 模型 數學描述 已知輸入x與輸出y之間存在未知的依賴關系 未知的聯合概率F x y 確定性關系為特例 根據n個獨立同分布觀測樣本在一組函數 f x 中 尋找一個最優函數 f x 0 使得預測的期望風險最小 其中 f x 預測函數集合 任意函數 又稱學習函數 學習模型 學習機器 損失函數 使用某預測函數 f x 對y做預測的損失 3類基本的機器學習問題 模式識別 函數擬合 概率密度估計 模式識別中的機器學習問題 有監督 有導師模式識別問題 系統輸出y為類別標號 兩類情況時y 0 1 或者y 1 1 為二值函數 預測函數又稱 指示函數 判別函數損失函數定義為例如該定義下的期望風險就是平均錯誤率 期望風險最小的決策即貝葉斯決策 函數擬合中的機器學習問題y為變量x的連續函數 損失函數定義為 平方誤差 通過將輸出y做閾值的二值轉換 函數擬合問題化為模式識別問題 概率密度估計中的機器學習問題學習目的為 根據訓練樣本來確定x的概率分布 損失函數定義為其中 為估計的密度函數 10 2 2經驗風險最小化與期望風險最小化 期望風險最小化的條件期望風險其最小化必須依賴于聯合概率F x y 中的信息 在模式識別問題中就是 必須已知類先驗概率P 和類條件概率密度p x 但是在機器識別中 僅有樣本信息 n個獨立同分布觀測樣本 是不能計算期望風險的 經驗風險 根據大數定律 由算術平均來替代數學期望有即由該式來逼近期望風險 在該式中 Remp 是由訓練樣本 經驗數據 來定義的 因此 定義該式為經驗風險 經驗風險最小化原則 參數w的Remp w 最小化代替R w 的最小化稱經驗風險最小化原則 依據該原則 提出了各種基于數據的分類器設計方法 但是存在問題 理論依據不足 問題1 首先都是w的函數 概率論中的大數定律僅指明 n 時 在概率意義上 Remp w R w 不能保證Remp w 與R w 中的w是同一個點 w 與w 更不能保證能夠使Remp w R w 問題2 即使可以保證 n 時 Remp w R w 也無法認定 在樣本數目有限時 經驗風險最小化方法得到的結果更好 統計學習理論的研究解決的幾個基本問題 1用經驗風險最小化解決期望風險最小化問題的前提是什么 2前提不成立時 經驗風險最小化的性能如何3是否存在更合理的原則 10 2 3機器學習的復雜性與推廣性 機器學習的復雜性可以定義為 對于復雜問題的跟蹤能力 搜索能力 探尋能力 機器學習的推廣性學習機器對于未來目標的預測能力 或者可使用性 兩者是矛盾的 學習與過學習 實驗數據1 已知小樣本n 5 使用學習機器作曲線擬合 設擬合函數為y exp ax sin bx 經學習訓練后 由訓練誤差為零 總可以找到參數a b滿足擬合函數 當使用更復雜的函數去擬合一個有限樣本時 其學習結果便產生了過學習 產生過學習的原因 1學習樣本不夠充分 已知小樣本n 5 2學習機器設計不合理 擬合函數為y exp ax sin bx 機器學習的復雜性與推廣性的矛盾學習能力過強 用復雜函數去記憶有限樣本 可以使經驗風險最小 訓練誤差為零 但是無法保證對未來樣本的預測能力 即喪失了推廣性 實驗數據2實驗數據為二次曲線加隨機噪聲生成 n 6 學習機器依經驗風險最小原則 對數據分別作一次曲線擬合與二次曲線擬合 擬合結果為 無論實驗多少次 一次曲線總比二次曲線擬合的誤差小得多 即一次曲線的期望風險小于二次曲線 其原因是 數據有限 小樣本時 對于機器學習的基本結論 1經驗風險最小不一定是期望風險最小 2學習機器的復雜性一定要與學習樣本的有限性相適應 10 3統計學習理論的核心內容 是小樣本統計估計與預測學習的最佳理論 從理論上系統地研究了經驗風險最小化原則的條件 有限樣本條件下經驗風險與期望風險的關系以及如何應用該理論找到新的學習原則與方法等問題 核心內容如下1 經驗風險最小化原則下 統計學習的一致性條件 Consistency 2 在這些條件下關于統計學習方法推廣性的界的結論 3 在這些界的基礎上建立小樣本歸納推理原則 4 實現這些新的原則的實際算法 10 3 1學習過程一致性的條件 學習過程一致性訓練樣本數n 時 有Remp w R w 經驗風險的最優值可以收斂到真實風險最優值 稱該學習過程是一致的 又稱該學習過程滿足一致性 一個學習過程 只有滿足學習過程一致性的條件 才可以保證在經驗風險最小化原則下得到的最優方法 在訓練樣本數n 時 得到期望風險最小的最優結果 定義 給定n個獨立同分布觀測樣本預測函數 f x w 為該樣本集合下在函數集合中使經驗風險取最小的預測函數損失函數 L y f x w n 最小經驗風險值 Remp w n 期望風險 R w n 在L y f x w n 下的 由式得到的真實風險值 如果滿足其中為實際真實風險的下確界 則稱為經驗風險最小化學習過程是一致的 幾何意義 定理 學習理論關鍵定理 如果損失函數有界 則經驗風險最小化學習一致的充分必要條件是即經驗風險一致收斂于真實風險其中 P 表示概率Remp w 經驗風險R w 同一w的真實風險 定理說明 1在統計學習理論中是即為重要的 2將學習一致性問題轉化為公式的一致收斂問題 3定理既依賴于預測函數集合 又依賴于樣本的概率分布 4雙邊一致收斂表達式為 5經驗風險與期望風險都是泛函 預測函數的函數 6目的不是用經驗風險取逼近期望風險而是通過求使經驗風險最小化的函數來逼近能使期望風險最小化的函數 7與傳統統計學中的一致性條件相比 該一致性條件更加嚴格 8由公式可知 該一致性條件是取決于預測函數中最差的函數的 因此是最壞情況分析 9定理本身雖然給出了經驗風險最小化原則成立的充分必要條件 但是該定理并沒有給出什么樣的方法能夠滿足這些條件 基于上述討論 統計學習理論研究了一些評價預測函數集合的性能指標 10 3 1函數集合的學習性能與VC維 統計學習理論研究了一些評價預測函數集合的性能指標 這些性能指標是基于兩類分類函數提出的 擴展到一般函數1指示函數集的熵和生長函數設指示函數集和訓練樣本集為 函數集中的函數能夠對樣本集實現不同的分類方法數目 記為N Zn 定義1 隨機熵將上述不同的分類方法數目的對數定義為隨機熵H Zn lnN Zn 說明 隨機熵與分類函數集合有關 且與樣本集有關 定義2 指示函數的熵將隨機熵取期望 稱為指示函數的熵H n E lnN Zn 又稱VC熵 定義3 退火VC熵Hann n lnE N Zn 定義4 生長函數函數集的生長函數定義為 在所有可能的樣本集上的最大隨機熵說明 1生長函數描述了函數集把n個樣本分成兩類的最大可能的分法數目2最大值 3由于是在所有可能的樣本集中取最大 因此與樣本分布無關 VC熵 退火VC熵 生長函數之間的關系為下面是幾個關鍵定理定理1 函數集學習過程雙邊一致收斂充分必要條件為 由指示函數熵來表示學習理論關鍵定理 與學習理論關鍵定理等價 定理2 函數集學習過程收斂速度快的充分必要條件為定理3 函數集學習過程一致收斂的充分必要條件是對任意樣本分布 有而且學習過程一致收斂的速度一定是快的 2生長函數的性質與VC維定理1 所有函數集的生長函數或者與樣本數成正比或者以下列樣本數的某個對數函數為上界其中 h為整數 n h時 為上兩式的轉折點 生長函數的該性質如圖所示 定義 VC維 Vapnike Chervonenkis 如果存在一個h個樣本的樣本集能夠被一個函數集中的函數按照所有可能的2n種形式分為兩類 或者說函數集能夠把樣本數為h的樣本集 打散 或者 粉碎 shattering 則指示函數集的VC維就是用該函數集中的函數能夠 打散 的最大樣本集的樣本數目 換句話說 如果存在有h個樣本的樣本集能夠被函數集中的函數 打散 而不存在有h 1個樣本的樣本集能夠被函數集中的函數 打散 則函數集的VC維就是h 如果對于任意的樣本數 總能找到一個樣本集能夠被這個函數集 打散 則該函數集的VC維就是無窮大 由此 如果對于一個指示函數集 其生長函數是線性的 則其VC維即為無窮大 如果生長函數以參數h的對數函數為上界 則函數集的VC維是有限的且其VC維等于h 由此 由前面的定理3 經驗風險最小化學習過程一致的充分必要條件是函數集的VC是有限的 且收斂速度是快的 關于VC維定義的說明 1可以證明 損失函數集與預測函數集有相同的VC維 2d維空間中的閾值分類器的VC維是d 1 3d維空間中的實值線性分類器其VC維也是d 1 4VC維是統計學習理論的一個核心概念 目前為止對函數集學習性能的最好描述指標 5遺憾的是 目前為止 沒有通用的計算任意函數集VC維的理論 只有一些特殊函數集的VC維可以準確知道 6對于復雜的學習機器 比如神經網絡 其VC維的確定除了與函數集的選擇有關 而且受到學習算法的影響 確定其VC維更為困難 7前沿研究課題 如何使用理論的或者實驗的方法來計算預測函數的VC維 10 3 3推廣性的界 10 4支持向量機 SupportVectorMachine SVM 統計學習理論思想的實現方法 支持向量機 由非線性變換將問題由低維空間變換到高維空間來解決經驗風險最小化問題 支持向量機得到的解具有很好的推廣性 最好地利用了分類邊界樣本信息 因此與樣本分布無關 10 4 1最優分類面與支持向量 設線性可分樣本集為d維向量 2類樣本 y為類別標簽 則線性判別函數為分類面方程為 作判別函數歸一化 即滿足 g x 1 即距離分類面最近的樣本距離為 g x 1 則兩類的分類間隔為2 w 如圖所示 最優分類面令分類間隔2 w 最大 等價于 w 或者 w 2最小 使得分類面對于所有的樣本能正確分類 即滿足則該分類面為最優分類面 支持向量過兩類樣本中離分類面最近的點 且平行于最優分類面的超平面H1 H2上的訓練樣本則稱為支持向量 顯見 最優分類面是由支持向量來 支撐 的 最優分類面的求取由最優分類面的條件建立目標函數 為二次型由滿足條件作為約束條件 樣本條件 則有約束優化問題 由拉格朗日乘子法求解最優分類面的條件 定義拉格朗日函數為式中 i 0 為拉格朗日乘子 L對w b求極小值 由得到最優化條件 求原約束優化問題的對偶問題 可以得到單一變量 的優化函數為 Q的求極大值 如果 i 為最優解 則有最優分類面的權系數向量為訓練樣本向量的線性組合 該最優解滿足 因此有 對于多數樣本xi來說 i 為零 而不為零的 i 對應于使等號成立的樣本xi即支持向量 通常支持向量的個數很少 對應于最優權系數向量 則最優分類函數為上式中 只對支持向量進行作求和運算 分類閾值b 則由任意一個支持向量滿足等式解出 10 4 2廣義最優分類面 前面的最優分類面式在線性可分條件下推導出來的 不能應用于線性不可分情況 改造 約束條件1 對于線性不可分情況 許多樣本不能滿足正確分類條件式因此 增加松弛項 分類條件式為 約束條件2 線性可分條件下的分類間隔最大 線性不可分時引入約束在兩個約束條件下對錯分樣本最小函數求極小值 10 4 3支持向量機 支持向量機的數學表達最優分類的優化函數與最優分類函數表達式中都含有內積運算 如果將表達式中的內積運算由內積函數來代替 將原來的特征空間作非線性變換 則優化函數成為最優分類函數成為則稱為支持向量機 支持向量機的基本思想使用非線性的內積函數 將輸入空