支持向量機畢業(yè)外文翻譯

支持向量機1.1引言第8章的結果表明：對于已定和欠定的系統(tǒng)，內核嶺回歸量(KRR)提供了一個統(tǒng)一的處理。另外一種方式實現統(tǒng)一這些兩種線性系統(tǒng)的方法是被Vapnik提出的通過支持向量機(SVM)學習模式。支持向量機學習的關鍵組成部分是確認一組具有代表性的被認為最有助于形成(線性或非線性)決策邊界的訓練向量。這些訓練向量被稱為“支持向量”，其余的訓練向量被稱為非支持向量。要注意的是只有支持向量才可以直接參與進支持向量機的決策邊界特性化。支持向量機已成功地應用于一個非常廣泛的應用范圍域，包括信號處理和分類，圖像檢索，多媒體，故障檢測，通信，計算機視覺，安全/認證，時間序列預測，生物醫(yī)學預測，生物信息學。本章將討論以下課題：1.2節(jié)推導線性支持向量機（SVM）的二元分類。主要目標是再次創(chuàng)建一個最大的極限來區(qū)分對立的兩類——正如以前在欠定系統(tǒng)中使用的公式一樣。支持向量機學習的關鍵組成部分是確認一組具有代表性的被認為最有助于形成(線性或非線性)決策邊界的訓練向量。這些訓練向量被稱為“支持向量”，并且，對于支持向量機來說，只有支持向量需要處于正確的邊際超平面。1.3節(jié)將基本的支持向量機算法推廣到模糊分離的數據集分類。1.4節(jié)將線性支持向量機推廣到它的非線性變量。通過強加額外的約束給拉格朗日乘子，被懲罰因子參數化，從相同的優(yōu)化公式中得到穩(wěn)健的非線性支持向量機。在1.5節(jié)中，給出了一些關于多類支持向量機的應用研究。對訓練和預測精度進行了比較。此外，探究了預測精度和訓練數據集的大小之間的關系。1.6節(jié)探討通過削減支持向量來減少實驗間隙維數的可能性。提議通過支持向量機削減算法的目的是最終只保留一小部分的訓練向量，還產生高性能的決策規(guī)則。這可能進一步降低分類的復雜性。1.2線性支持向量機給一個二元分類訓練數據集，一個基本的SVM學習模式是找到兩平行的邊際超平面分離的正面和負面的訓練矢量。理想的情況是，兩平行超平面應區(qū)分兩類，正向量落在第一平面的一側，而負向量落在第二平面的另一邊。在圖1.1中，以兩條虛線表示邊際超平面，而實線用來強調線性分類器的決策邊界，兩個平面之間的地區(qū)則是安全帶。由區(qū)域創(chuàng)建的安全邊際可以被一個邊際超平面（兩條虛線中的一條）和決策邊界（實線）之間的距離D測量出來?？赏昝谰€性分離的支持向量機回憶一下，前面介紹的線性學習模式的目的是找到一個決策向量W以產生一個沒有誤差的可以滿足被公式（8.37）嚴格規(guī)定的等式的解決方案。在這方面，支持向量機公式有著不一樣的目的：將嚴格的等式轉化為不等式。對于所有的積極訓練向量：（1.1）圖1.1 SVM中相應邊際超平面的圖解。虛線表示邊際超平面，而實線用來表示決策超平面。同時：對于所有的積極訓練向量：（1.2）這兩個不等式可以通過一個簡單的限制從而更簡潔的表達： 在松弛條件下，支持向量機提供了一個可以適用于已定（M≥N）和欠定（N＞M）場景的統(tǒng)一的學習模式。1.2.1原始向量空間中的優(yōu)化公式就像在以前的學習模式中，誤差項可對應一個訓練向量，叫做，表示為：，被公式（1.3）限制后，變?yōu)椋?，培訓的目標是通過最小化w來最大限度地分離邊緣約束下2/w。這將導致以下優(yōu)化公式：受約束后：（1.4）由于SVM方法采用比LSE較少限制的約束，其解決方案熊w值低于規(guī)定的LSE學習模型實現參照公式（8.32）。注意,小w的值更廣泛的分離的安全裕度。1.2.2經驗空間中的沃爾夫對偶優(yōu)化等式（1.4）表示的式子是一個通過使用標準的凸優(yōu)化方法可解的二次規(guī)劃優(yōu)化問題。更具體地說，可以從中推導出拉格朗日的相關結論。（1.5）拉格朗日乘子必須是非負的，即：（1.6）以確保通過聚焦的一階梯度對w,我們可以建立太陽能發(fā)電:（1.7）對于SVM，這已對LSP驗證的標準方法。這應該是顯而易見的，在公式的優(yōu)化配方，由定理1.1符合規(guī)定的條件，從而提供一個獨立的LSP的驗證。此外，通過相對于B的歸零階指令，我們得到如下的正交平面性（OHP）條件：（1.8）將式（1.7）和式（1.8）帶入式（1.5），并化簡，得：（1.9）沃爾夫對偶優(yōu)化讓我們來表示，fori=1,...,N，然后，支持向量機的目標函數可以改寫如下：其中，K是內核矩陣，并且是經驗空間里的決策向量。注意,約束控制方程（1.8）可以被一個新的形成條件取代,即：這導致了下面的沃爾夫雙優(yōu)化公式的實證決策向量：服從OPM的條件后：受符號約束后：（1.9）注意，由于式（1.6）符號的約束，是必要的。然而，如果我們暫時忽略符號上的約束，那么我們只需要考慮控制約束。對于控制約束，采用拉格朗日乘子B，我們將獲得一個新的拉格朗日公式。以F（a，b）一階梯度相對于和B和均衡到零，我們得到：這說明了一個事實，如果它忽略符號限制，分析解決方案將是可行的。讓我們用一個算例表明如果只有符號約束可以忽略這個問題可以大大簡化。示例1.1(SVM分類器的三個三維(2D)訓練向量)如圖1.2（a）所示，為三個訓練向量根據式（1.9），目標函數是：（1.11）受和，對于等式限制，拉格朗日乘子B,可以導致了一種新的拉格朗日函數： 以就和B和均衡他們零階梯度，我們得到：圖1.2 一個簡單的支持向量機分類：（a）數據集。(b)支持向量機分類的決策邊界。在這種情況下，所有三個訓練數據都是支持向量。這個收益率，和閾值b=?1。如圖1.2（b）虛線所示，決策邊界是： 在一般情況下，通過求解方程（1.11）是不能直接得到支持向量機的解決方案。根據KKT條件，式（1.11）僅部分有效。更準確地說,它適用于支持向量相關的行,但不適用于非支持向量相關的行。上述數值示例中，所有三個培訓向量恰好是支持向量。因此，自動滿足限制，通過切結一組線性方程提供一個分析的解決方案。一般來說，執(zhí)行符號限制嘗嘗帶來繁瑣的數值程序，沒有封閉的解。這樣一個過程是在識別SVM中的支持向量和非支持向量時時必要的。1.2.3卡羅需-庫恩-塔克（KKT）條件在SVM學習模型中,等式(1.11)只適用于選擇性的子集訓練向量。與這相關的訓練向量子集將被命名為支持向量,而其余培訓向量將稱為非支持向量。更確切地說,積極的訓練向量可以再細分如下:(1)支持向量必須滿足等式: (1.12)并且（2）支持向量滿足不等式： 同樣,訓練向量可以類似地細分:(1)支持向量滿足等式： （1.13）并且（2）支持向量滿足不等式： 目前，將變得明確，與支持向量相關聯(lián)是，而非支持向量是。因此，因此,只有支持向量定義判別函數有一個積極的作用,，見表（1.19）。為方便起見，支持向量的指標表示，其中S表示支持向量的個數。支持向量最優(yōu)子集的識別在支持向量機學習模型中起著關鍵性的作用。換句話說，如果這樣的子集是已知的，解決方案會通過簡單地解決下列等式得：1.2.4支持向量約束是與是與知名的卡羅需-庫恩-塔克（KKT）條件密切相關。更準確地說,根據KKT條件、最優(yōu)的解決方案必須滿足下列等式:（1.14）對于所有的訓練向量。這有效的將約束分為兩類。支持向量。滿足（即）的向量被稱為支持向量。當時，相應的培訓向量必須滿足： （1.15） 因此，支持向量處于正確的邊際超平面：。這也被成為支持超平面。同樣，利用式（1.7）的LSP，我們得到： （1.16） 總之，只有當時，第k個訓練向量是一個支持向量。非支持向量。如果那么KKT條件(式(1.14)總是會被遇到不管或者。因此，第k個訓練向量沒有必要滿足零點誤差條件：。這進一步意味著第k個訓練向量不會直接參與塑造決策邊界。為此，第k個訓練向量應標記為非支持向量。在給出的式（1.10）中，求解沃爾夫對偶優(yōu)化的困難點在于正確識別一組適當的支持向量。決策邊界一旦乘數已經確定,可以由式（1.17）獲得決策向量w: （1.17）閾值b可以被求出： （1.18）是任一個處于正面無誤差平面上的支持向量。它遵循的判別函數可以表示為： （1.19）并且決策邊界的特征可以用f(x)=0來描述?，F在讓我們來探討一個數值例子來幫助說明KKT條件所發(fā)揮的關鍵作用。示例1.2（帶有四個二維訓練向量的SVM分類器）如圖1.3所示的數據集,有四個訓練向量：數據矩陣為：對應的線性核矩陣為：圖1.3 比較兩個分離率表明SVM分類器的產量比LSE分類器較大幅度。（一）LSE的分類器，正面和負面的利潤率顯示為實線。決策邊界是由所有四個訓練向量共同決定的，正（負）的安全邊際是由正（或負）的訓練模式，這是最接近的決策邊界。（二）支持向量機分類器的決策邊界是由三個支持向量決定的。對于支持向量機，正面和負面的利潤率（如虛線）是相同的。由此推導出下列的拉格朗日公式：（1.20）通過調整相對于和B的拉格朗日一階導數，我們得到： 方程組的線性系統(tǒng)不存在可行解。然而，隨著一個訓練向量,可能是一個非支持向量，然后通過KKT條件的美德，其相應的乘數為零，即。更重要的是，根據KKT條件，相對于必須是零，因此由上面第一個方程的約束可以被忽略。通過求解余下的四個方程，我們可以得到一個可行的解.和b=-1；它遵循決策向量w:最后，如圖1.3（b）所示，決策邊界是1.2.5LSE和SVM分離率的比較從理論上講，支持向量機產生一個最佳的分離裕度之間的類。特別是，它應該有一個比LSE對應更好的邊緣。這個結果可以通過比較得到的分類器驗證通過LSE（例8.1）和支持向量機（例1.2）。對于數據集（四個二維向量），SVM對LSE的微弱優(yōu)勢。這兩個分類的決策邊界和分離的利潤率顯示在圖1.3。下面的例子提供了更詳細的比較。示例1.3（LSE和SVM分類器的比較）對于給出的示例1.2中數據集（四個二維訓練向量），我們有以下意見：對于LSE分類器，決策邊界被規(guī)定為：正面和負面的安全邊際是圖1.3（1）的2條短的實心線所示。正類的安全邊際是由最近的正訓練模式的決策邊界。負邊緣被定義為類似的方式。例如，兩者的利潤率分別為0.382和0.318。平均等于0.35。對于SVM分類器，決策邊界被規(guī)定為：圖1.3（二）的虛線表示，正、負利潤率均為相同值：注意：0.354＞0.35，因此SVM對LSE在平均利潤率方面稍占優(yōu)勢。讓我們舉個例子來說明比較LDA，RR，SVM的數值：示例1.4（案例研究：比較LDA，RR，SVM）考慮到同一個數據集作為例8.6。其中有四個訓練向量：同時，以及SVM的決策邊界是，與第一特征主導的決策規(guī)則。另一方面，LSE或FDA的決策邊界是，作為唯一的決策特征。對于RR，兩特征之間的平衡取決于所選擇的價值ρ。當0≤ρ＜32，相比SVM，RR更強調第二特征。當ρ=32，RR和SVM具有完全相同的解決方案。當32＜ρ，相比SVM，RR解決方案更強調第一特征。通過定義，訓練向量沿決策向量投影之后，支持向量機提供了最廣泛的（任一）正面和（任一）負面分離之間的差距。在這種情況下，最寬的寬度是：沒有其他的分類可以產生一個更廣泛的正面和負面分離的投影。記得，當ρ→∞，RR的解決方案產生了最廣泛的后投影分離陽性和陰性的質心之間的寬度：見式（8.61）1.3模糊分離的支持向量機：松弛變量的作用在現實世界中的應用程序，訓練向量是不太可能清楚地分離。然而，基于最大可分性相同的配方是可行的只要一些選擇性的訓練矢量的豁免，即允許違反最低保證金規(guī)則。顯然，該豁免向量寬間隔的數量越多。這是由圖1.4所示。首先，我們注意到，有一個明確的保證金（薄的固體線），其特征是由三個原始的支持向量。然而，一個相當大的分離區(qū)（虛線之間）可以通過人為免六違反了培訓載體。盡管如此，一個良好的訓練向量的大部分仍然是清楚的可分離的，這些載體被保持在禁區(qū)外。這些向量將被視為不支持向量的模糊支持向量機分類。圖1.4 這一圖解說明了如何通過允許一些違規(guī)行為創(chuàng)建一個更廣泛的分離裕度。1.3.1優(yōu)化原有空間在模糊支持向量中，一組正松弛變量，是用來放松規(guī)定的約束式（1.4）。與松弛變量，我們得到以下的軟約束：，?i=1,...,N,(1.21)當為了防止過度放松懲罰項，其中C是一個預選的懲罰因子，將被添加到原來的損失函數（方程（1.4）），導致：受一系列軟限制：同時，并且（1.22）注意，式（1.22）滿足定理1.1規(guī)定的條件下，進一步保證了學習子空間的性質（LSP）。LSP可以通過如下一個標準的優(yōu)化分析進行闡述。1.3.2學習子空間特性和優(yōu)化經驗空間將式（1.22）與拉格朗日公式相照應，得到：（1.23）這應用了兩種拉格朗日乘子（1）時，（2），時。對偶優(yōu)化問題可以用以下最小-最大公式來表示： 通過對照于W調整L（W，B，α，β，ξ）的一階梯度，我們得到了LSP的條件：（1.24）通過對照于b調整L（W，B，α，β，ξ）的指令，我們得到了：（1.25）通過對照于ξ調整L（W，B，α，β，ξ）的指令，我們得到了： （1.26）將式（1.24）-式（1.26）帶入到式（1.23），我們得到一種改良的沃爾夫雙優(yōu)化公式：（1.27）受和的限制（注意由于公式（1.25）和（1.26）的限制）。一旦已從式（1.27）獲得，向量W和閾值可以通過式（1.24）獲得。閾值b可從下式獲得：(1.28)對于任意整數k，（在這種情況下，是一個支持向量，正是在于對（正或負）無誤差平面。然后，可以得出決策邊界,如下：（1.29）讓經驗決策向量a變?yōu)橹械南蛄?。那么成本函數可用a和來表達:（1.30）且，i=1,…,N分離裕度向量C分離裕度即，可以通過改變懲罰因子C，其邊緣效應（模糊）的分離是由圖1.5注意較大值C產生一個窄的模糊分離區(qū)為例，區(qū)內含有更少的SVS。相比之下，C產生一個更廣泛的范圍內，可以找到更多的SVS。最合適的C在數據分布上，往往是通過試驗和誤差得到的。在確定學習支持向量機模型的魯棒性中，懲罰因子也起著重要的作用。當C是足夠小的，它會創(chuàng)建一個體面的大池的支持向量，它們都參與決策。這意味著，由此產生的決策邊界成為一個更大的子集的訓練向量的一致性。人們普遍認為，包括更多的支持向量的方法。圖1.5 線性支持向量機的決策邊界（實心線）和邊際邊界（虛線）的20個數據點。（一）C=10時的線性支持向量機。（乙）C=0.1時的線性支持向量機。這兩種情況下的決策邊界幾乎是相同的。兩條虛線之間的區(qū)域被認為是“模糊區(qū)域”，一個小的區(qū)域創(chuàng)建一個更大的模糊區(qū)域。數據集來源于A.Schwaighofer。該分類器具有更強的預測能力。在實際應用中，請參見圖1.11中C的作用。示例1.5（模糊可分數據集。）在這個例子中，一個線性的支持向量機被施加到的非線性可分20個數據點。圖1.5描述了兩個（略有不同）的決策邊界（顯示為實心線）和兩個（非常不同）的分離邊界（有界的兩個虛線）為10和0.1。值得注意的是，大多數（但不是全部）支持向量在平面之間的邊際。很明顯，當C是小的，分離裕度更寬，允許更多的支持向量。1.3.3支持向量的研究和WEC分析對于明確分離的況下，有一個非常簡單的特征支持向量。眾所周知，第K個訓練向量是一個支持向量，當時，。KKT條件和支持向量在明確可分或模糊可分的情況下，支持向量可以被簡單描述為有且只有時，由第i個訓練向量是一個支持向量。注意表示式中的KKT條件（1.14），即：，fori=1,2,...,N,(1.31)或者：fori=1,2,...,N,(1.32)這僅適用于明確可分離的情況。對于模糊可分的情況下，KKT條件需要修改為：，?i=1,...,N.(1.33)這將導致一個更復雜的支持和非支持向量的特性。支持向量的特性如果乘子，然后訓練矢量將支持向量必須嚴格遵守： 對比于方程不等式（1.21）。圖1.5（b）中，點1，2，4，9，和10是負數據集的支持向量，而分11，12，15，19，和20是正數據集的支持向量。嚴格來說,當為支持向量時，條件只是一個必要條件(但不是充分條件)。一般說來,另一方面,當為非支持向量時，條件是必要充分條件。非支持向量的特性如果乘子,這意味著。在這種情況下，相應的訓練向量將是一個非支持向量，并將保持在禁區(qū)外。圖1.5（b），點3，5，6，7，和8為負數據集的支持向量，而分13，14，16，17，和18是正數據集的支持向量。嚴格來說,當為非支持向量時，條件只是一個必要條件(但不是充分條件)。一般說來,另一方面,當為非支持向量時，條件是必要充分條件。總之,如圖1.6所示,所有的支持向量是由兩個邊際超平面有界,一個由f(x)=1(等價于)正訓練樣本和一個f(x)=?1(等價于)負訓練樣本。這形成了的支持向量機的WEC，如圖1.6所示。對于正訓練數據集,根據KKT條件是一個支持向量(SV)只有在時,這也進一步表明。然而,幾乎是一個充分條件為作為支持向量,是減輕(罕見)數據分布,如重復或共面訓練向量。因此,它也是一般化的充分條件。(參數為負的數據集是相似的。)圖1.6 為一個支持向量的條件的必要（且充分）條件是。 這是通過SVM轉化為WEC的幫助。（一）負向量的WEC。因為，決策邊界是f(x)=0時，這對應于點。（b）正向量的WEC?，F在，，決定點對應于。這兩個WECS都表明了，幾乎所有的支持向量具有恒定的值，唯一的例外是那些相應的EI=0。這（開放）分離區(qū)也可稱為恒α區(qū)。1.4內核支持向量機要達成一個可變的決策邊界，求助于一個支持向量機的非線性核函數是可取的。一個非正式的推導是可以通過非線性核函數代替線性內積得到，即。根據式（1.27），這直接產生以下的一個非線性模糊支持向量機的優(yōu)化公式：且，又1.4.1內核空間的初始算法對于一個正式的推導，首先讓我們來表示的內在空間的判別函數：其誤差為：接下來在以式（1.4）的剛性限制同樣的理論是為了獲得一個清晰可分的模糊支持向量機,另一方面,引入一組松弛變量的為了放松這樣的剛性約束。更確切的說,放松約束變?yōu)椋?i=1,...,N.(1.34)為了防止過度的違規(guī)操作，懲罰項被再次納入目標函數?，F在的模糊支持向量機學習模型在本質空間中有以下的優(yōu)化公式：受以下公式限制：同時又,?i=1,...,N.(1.35)注意，該公式滿足定理1.1中規(guī)定的條件，從而進一步保證了學習內在空間中子空間的性質（LSP）。在隨后的討論中，LSP將再一次地獨立確認通過標準的優(yōu)化分析。1.4.2經驗空間中的雙重優(yōu)化器與式（1.35）相對應的拉格朗日公式：（1.36）在拉格朗日乘子確保，而提供類似的目的確保。對偶優(yōu)化問題可以表示為以下公式：在相同的數學操作下進行式（1.27）的推導，為線性的情況下，我們就得到下面的沃爾夫對偶公式： （1.37）且又用取代，我們有一個關于a的等價優(yōu)化公式： （1.38）就像在式（1.28），可以再次得到閾值b： （1.39）對于任何的整數k，都有這將推導出以下支持向量機學習算法。算法1.1（支持向量機學習模型）給出了核矩陣K和引導向量y，支持向量機學習量為乘子系數決策向量： 且又(1.40)或者，等價地，通過解決實證決策向量a： 且又（1.41）LSP明確對于支持向量機，我們有： 因此判別函數是： （1.42）a可以從方程（1.41）和式（1.39）中得出。最后，可以用作結果。再一次，讓我們用OCR數據作為優(yōu)化公式的例子。示例1.6（OXR數據的非線性支持向量機）OXR數據是線性不可分的；有必要采用非線性核函數。非線性支持向量機的分類可以通過最大化得到：其限制條件為，且其中的懲罰因子被設置為C=1。優(yōu)化解