統計學習理論與支持向量機機器學習概述Simon對學習的論述：“如果一個系統能夠通過執行某個過程改進它的性能，這就是學習。”1983年simon進一步指出：“學習就是系統的適應性，這意味著這些改進使得系統能夠更有效的完成同樣的工作或者類似的工作。”機器學習就是通過對已知事實的分析總結規律，預測無法直接預測的事實。目的：設計某種方法，通過對已知數據的學習，找到數據內在的相互依賴關系，從而對未知數據進行預測或對其性質進行判斷。泛化能力：推廣能力，對未知數據進行預測和判斷的能力。機器學習問題的一般表示

系統S是研究對象，符合某一未知的聯合概率分布F(x,y)。在給定的輸入x下得到系統的輸出y。在訓練過程中，輸入與輸出組成獨立同分布的訓練樣本(x,y)求出學習機器，在測試過程中，訓練后的學習機器對于輸入x給出預測y’Assumption:(iid)Hypothesisspace:Lossfunction:Objectivefunction

從一組獨立同分布的觀測樣本出發，通過最小化期望風險R(w)，確定學習機器的廣義參數w的過程。經驗風險最小化根據概率論中大數定律的思想，用算術平均代替設計學習算法時，用對w求經驗風險的最小值代替求期望風險的最小值，實現所謂的經驗風險最小化原則。大數定律說明當樣本數趨于無窮多時，概率意義下趨于，并不保證在同一點上取最小值。當前提不成立時，能否找到更合理的原則？統計學習理論的簡介：統計學習理論研究小樣本情況下機器學習理論。始于60年代。1962年，rosenblatt提出了第一個機器學習的模型—感知機，標志人們對學習問題進行研究的真正開始。Vapnic在1974年提出的結構風險最小化原則對統計機器學習具有劃時代的意義。統計學習理論用VC維來描述學習機器的性能，并從控制學習機器的性能的角度出發，結合經驗風險和訓練樣本，導出學習機器的泛化上界。學習機器的VC維VC維的直觀定義：對一個指示函數集，如果存在h個樣本能夠被函數集中的函數按所有可能的2種形式分開，函數集的VC維是h目前沒有通用的關于任意函數集VC維的計算理論，只有一些特殊函數知道其VC維。n維實數空間中線性分類器和線性實函數的VC維是n+1，而的VC維則為無窮大。h推廣性的界統計學習理論從VC維的概念出發，推導出經驗風險和實際風險之間關系的重要結論，稱作推廣性的界。Vapnik證明，下列邊界以成立：

h是函數集的VC維，n是樣本數，是置信范圍。為最小化期望風險，應同時最小化經驗風險和假設空間的VC維。結構風險最小化原理把函數集分解為一個函數子集序列，使各個子集按照VC維的大小排列，在每個子集中尋找最小經驗風險，在子集間折衷考慮經驗風險和置信范圍，取得實際風險最小。實現結構風險最小化的兩種思路：一是在每個子集中求最小經驗風險，然后選擇使最小經驗風險和置信范圍之和最小的子集。顯然這種方法比較費時，當子集數目很大甚至是無窮時不可行。二是設計函數集的某種結構使每個子集中都能夠取得最小的經驗風險（如使訓練誤差為0），然后選擇適當的子集使置信范圍最小，則這個子集使經驗風險最小的函數便是最優函數。支持向量機簡介支持向量機(SVM)是由Vapnik領導的AT＆TBell實驗室研究小組在1963年提出。1995年Cortes和Vapnic首先提出比較完善的SVM方法。支持向量機是建立在統計學習理論的VC維理論和結構風險最小化原理基礎上的，根據有限樣本信息在模型復雜性和學習能力之間尋求最佳折衷，以期獲得最好的泛化能力。支持向量機優點針對有限樣本情況。算法最終將轉化為一個二次型尋優問題，從理論上講，得到的將是全局最優點，解決了在神經網絡中無法避免的局部極值問題。算法將實際問題通過特征映射，映射到高維特征空間，在高維空間中構造線性判別函數來實現原空間中的非線性判別函數。解決了維數災難問題，其算法復雜度與樣本維數無關。邊緣的概念及其泛化界統計學習理論中，泛化界是通過VC維得到的，通過控制函數集的VC維，以便獲得最好的學習機器泛化性能。引入一種基于邊緣的泛化界思想，將邊緣的概念引入到學習算法中去。難以計算泛化不等式泛化不等式告訴我們可以通過控制邊緣來控制泛化界，從而可以將優化目標定為求取最大邊緣分類器，也即所謂的最大邊緣算法。直觀上看，樣本點離分界面越遠，邊緣越大，泛化性能越好。線性可分情形最大邊緣算法假設給定訓練樣本集：其中服從獨立同分布，為樣本類別標簽。

支持向量機本質上是處理二分類問題的。支持向量機的目的是構造最優超平面，將兩類正確分開（錯誤率為0），且分類邊緣最大。分類面方程：歸一化：分類邊緣：使分類邊緣最大等價于使求解：利用Lagrange乘子法轉化為對偶優化問題構造Lagrange函數為對應的Lagrange乘子對w,b分別求偏導將和代入Lagrange化簡為對偶式：由上式求得最優解其中為一類的任意支持向量，為另一類的任意支持向量。支持向量是在中滿足等號的那些向量，也就是落在兩側邊界超平面上的向量。支持向量在w的展開式中對應的系數a非零，權向量w是支持向量集合的線性組合，各個支持向量對這個線性組合的貢獻就是它們Lagrange系數與y的乘積。分類超平面函數：支持向量方法的優點通過化簡為對偶優化形式，變成一個凸二次優化問題，其局部解一定是全局最優解，這是神經網絡研究多年沒有實現的目標。僅與樣本點內積運算有關，不涉及樣本點本身計算，為核技巧處理非線性問題奠定了基礎。支持向量只占全體樣本中很少一部分。線性不可分問題的軟邊緣算法由于樣本中小概率事件和噪聲的存在，極個別的樣本點就會嚴重影響分類器泛化性能，即導致對訓練樣本線性不可分。C.coters和V.Vapnic通過引入松弛變量提出軟邊緣算法。第一項控制的是泛化能力，第二項是懲罰項，控制分類錯誤。可看作是訓練樣本關于（廣義）分類超平面的偏差，為線性可分情況。C為預先確定好的正實數，實現算法復雜度與錯分樣本間的折中。當=1時，稱為l1范數C-SVM；當=2時，稱為l2范數C-SVM。采用Lagrange乘子法求解，約束條件為線性可分與不可分超平面對比非線性問題與核技巧非線性問題可以通過適當的特征映射變換為另一個空間的線性可分問題，變換空間的維數一般會增加。增加空間的維數會陷入“維數災難”。××××××××××××××××××x1、x2××××××××z3z1z2核技巧的基本思想我們注意到了在討論最大邊緣和軟邊緣算法時，其最終的分類判別函數式中只包含待分類樣本與訓練樣本中的內積運算，不涉及樣本本身的運算。于是要解決一個特征空間中的最優線性分類問題，只需要知道在原空間中的內積運算，而不需要具體的映射函數，因此可以避免“維數災難”問題這就是核技巧的基本思想。常用核函數類型：多項式類型:徑向基