一種改進的SVM增量學習算法研究

黃建校　邵曦

摘要：通過對訓練樣本集的幾何特征和機器學習迭代過程中支持向量的變化情況分析，文章提出一種改進的基于KKT條件和殼向量的SVM增量學習算法。算法使用包含原支持向量集的小規模擴展集——殼向量，將其作為新一輪迭代的初始訓練樣本集。同時，基于樣本是否違背KKT6件的錯誤驅動策略，對新增的大量樣本進行篩選，以此得到更加精簡有效的新增樣本集。實驗結果表明，與傳統的增量學習算法相比，改進的算法在模型訓練的收斂速度和對未知樣本集的分類準確度方面都有明顯的提高。

關鍵詞：SVM；殼向量；KKT條件；增量學習

1.SVM算法研究背景

隨著互聯網時代和多媒體信息技術的飛速發展，大量的網絡資源也隨之產生，其中也包括受眾面非常廣泛的數字音樂。面對數量龐大和風格多樣的數字音樂，一個非常重要的需求是準確而快速地查詢出符合用戶喜好的音樂。為此，人們需要設計一個高效快速的音樂分類系統。

針對音樂分類，許多研究者已經提出了各自的方法，大體可以分為3類：一是在音樂特征提取的選擇和特征向量的維度上作改進；二是在分類算法的選擇上作改進；三是在多分類問題的解決方法上作改進。其中，研究最多的是對分類算法的改進。而在這些研究當中，應用最為廣泛的技術就是支持向量機（Support Vector Machine，SVM）。

雖然經典的SVM算法應用廣泛，但其依然存在一定的局限性。由于SVM是一種監督式的學習算法，它不具備增量學習的能力，只能使用少量給定的己標注的樣本作為訓練樣本進行訓練，以此來得到分類模型。然而，在現實應用中，數字音樂的數據量通常呈現出在線式增長的特點，對這樣級別數據量的音樂樣本進行類別標注，無論是在人力上還是在時間成本上，都是不現實的。因此尋找更高效率的svM增量學習算法，篩選可以涵蓋大量未標注樣本所含信息量的代表性樣本進行標注來改善分類模型的訓練速度和分類精度，具有十分重要的意義。

從提高增量學習訓練速度的角度出發，sved等基于SVM提出一種簡單增量學習算法，該算法使用能夠代表初始樣本集但數量較小的支持向量進行訓練。然而，該算法完全忽略了非支持向量，而有些非支持向量可能攜帶著由于訓練前期樣本不夠豐富而沒有顯性表現出來的重要分類信息。申曉勇等通過分析訓練樣本的特點，結合KKT條件，提出一種計數器淘汰算法，有效地去除了少量無用樣本，但該算法在增量學習的過程中需要對所有的歷史訓練樣本進行學習，這將在很大程度上增加存儲空間成本，同時也會使得增量學習的速度減慢。文獻使用訓練樣本到類樣本中心點的距離和該樣本到分類決策平面的距離的比值，無異于改善分類模型性能的樣本剔除，但算法存在一定的主觀性，分類模型的穩定性無法得到保證。

研究發現，不同類別的訓練樣本在空間中呈現聚類分布，并且類樣本集的邊緣樣本相比支持向量，包含更多的分類信息，這類樣本被稱之為殼向量。文獻基于樣本的幾何分布特點，使用訓練樣本集中的殼向量和類與類之間邊界上的殼向量作為初始訓練樣本集參與訓練。文獻提出一種基于殼向量的增量式快速增量學習算法，該算法使得求解二次優化問題的計算量大大減少，提高了增量學習的收斂速度。但利用該算法只適用于線性空間中的兩分類問題，不適合在現實中推廣使用。

本文算法在總結分析前人學習算法的基礎上，提出一種改進的SVM增量學習算法，將KKT條件和殼向量相結合，分別從新增樣本集和初始訓練樣本集的角度，降低學習過程中的存儲空間占有量，提高用于模型訓練的樣本集的豐富性和可靠性，從而改善分類模型的收斂速度和分類性能。

2.SVM相關理論

SVM是在嚴謹的統計學習理論的基礎上發展起來的一種用于解決分類問題的機器學習算法，該算法將結構風險最小化原則和統計學習當中的VC維理論相結合，采用核函數映射的方式實現非線性的SVM，通過尋找使得分類間隔最大化的最優超平面，實現對不同類別樣本的分類，在解決小樣本、非線性以及高維模式識別等問題中效果顯著。相比傳統的分類學習方法有著更好的學習性能和泛化能力，被廣泛應用于文本分類、目標識別和時間序列預測等領域U5471。

對于線性二分類問題，假設給定類別標簽的訓練樣本集為（X₁，y₁），（x₂，y₂），…（x_n，y_n），x_i∈R^d，y_i∈{+1，-1}。其中，n為訓練樣本集的總數，d樣本特征的維度，y樣本的類別標號。尋找最優超平面可以歸納為求解平面f（x）=wx+b的最優解，使得該平面能夠正確地將兩類已知樣本分離開，同時要求如圖1所示的分類間隔Margin最大化。

定理2若新增樣本中存在某些違反KKT條件的樣本，則這些違反KKT條件的樣本中肯定存在新的支持向量；若新增樣本中不存在違反KKT條件的樣本，則新增樣本中肯定不存在新的支持向量。

定理3若新增樣本中存在違反KKT條件的樣本，則上次訓練結果中的非支持向量有可能轉化為支持向量。

根據上述定理可知，y_if（xi）<1是新增樣本（x_i，y_i）違背KKT條件的充要條件。若新增樣本滿足原分類器對應的KKT條件，那么該新增樣本的加入對原支持向量集不會產生影響，也不會改善原分類器的性能，可舍棄該樣本。反之，如果新增樣本不滿足當前分類器對應的KKT條件，那么該新增樣本將使得原支持向量集發生變化，應當將其加入到下一輪的模型迭代中參與訓練。通過這種方式，新一輪的迭代訓練只需考慮不滿足KKT條件的新增樣本，從而大大減少對新增樣本的學習時間，同時又不會影響新增樣本集原本所包含的分類信息。

3.2利用殼向量代替支持向量

根據支持向量機的原理可知，在訓練分類器的過程中，所利用的是對分類器的性能起決定性的支持向量。而在SVM增量學習的過程中，支持向量會隨著新增樣本的加入發生變化。

原支持向量可能轉變為非支持向量，原非支持向量也可能轉變為有助于改善分類器性能的支持向量。而傳統的SVM增量學習算法，僅僅利用了支持向量，對于可能包含重要分類信息的非支持向量則完全舍棄，這將在很大程度上影響分類器的訓練收斂速度和分類準確率。因此，在增量學習的過程中，新一輪的迭代訓練樣本集應該將歷史訓練樣本集中的非支持向量考慮在內。

根據對訓練樣本集幾何分布特征的分析，發現最有可能轉變為支持向量的樣本是類樣本的邊界附近的樣本，即每個類對應的樣本集中位于幾何邊緣的樣本。這種特征的樣本，就是本文算法所用到的殼向量。它不僅保留了原來的支持向量，而且還包括了最可能轉變為支持向量的非支持向量，這使得原本被舍棄的可能包含重要分類信息的樣本得以保留。獲取殼向量的方法如下：首先求出訓練樣本集中各類別樣本對應的最小超求體，然后以超球面上的點作為初始的殼向量，通過迭代方法求出其極點集合，最后從所得集合中舍棄多余的內點，從而得到訓練樣本集所對應的殼向量。

3.3算法描述

在傳統的SVM增量學習算法中，每一輪的迭代訓練只考慮支持向量，而對于可能轉變為新的支持向量的非支持向量采取了全盤丟棄的措施，所訓練得到的分類器的泛化性能較差。同時，該算法對于新增樣本的選擇策略是將其全部加入到原訓練集，這將大大增加分類器訓練的時間成本。基于上述不足之處，本文綜合考慮原訓練樣本集和新增樣本集的特點，使用包含更多樣本分類信息的殼向量代替支持向量，它不僅包含了原來的支持向量集，而且保留了最有可能轉變為新的支持向量的非支持向量。同時，根據樣本是否違背KKT條件，從新增樣本集中篩選出包含更多分類信息量的樣本，以此減少模型訓練時間。該算法使得訓練得到的分類器在性能和訓練時間上都能得到較好的優化。具體算法如下：

（1）設初始訓練樣本集為Traino，對應的初始殼向量為Hullo，第k次增量樣本集為Addk，第k次增量學習中違背KKT條件的增量樣本集為Add_k-violateo其中，k=l，2…n，n為加入增量樣本的最大次數。

（2）利用上述求解殼向量的方法，求解初始訓練樣本集Traino中各類樣本對應的殼向量并求并集，得到Traino的殼向量Hullo。

（3）將殼向量Hullo作為新的訓練樣本集，使用標準SVM算法訓練得到分類模型Modelo。

加入新增樣本集Addk，如果k>，2，則算法終止；否則轉

（3）。

（4）根據分類模型Modelk-1，從Addk中選擇違背KKT條件的增量樣本，確定參與第k次增量學習的新增樣本集Addk violate。

（5）如果Add_k-violateo=φ，置HUllk=HUllk-1，Modelk=Modelk-1，k=-k+l，轉（3）；否則轉（6）。

（6）對殼向量Hullk=Hullk-1UAddk_k-violateo進行增量學習，得到新的分類模型Modelk，并置k=-k+l，轉（3）。

4.實驗結果與分析

為了驗證本文算法的可行性和有效性，本節分別從收斂速度和分類準確率兩個角度，將本文提出的改進的增量學習算法與經典的SVM增量學習算法進行對比分析。實驗所用的數據集為UCI數據庫中的Balance Scale數據集和人工采集的音樂樣本數據集。

Balance scale數據集：共有625個樣本，樣本特征維數為4，樣本類別數為3，訓練樣本數為470，測試樣本數為155。

人工采集的音樂樣本數據集：共有3 301個樣本，樣本特征維數為100，樣本類別數為5，訓練樣本數為2 500，測試樣本數為801。

實驗采用的分類環境為SVMlight，并根據實驗數據的特點，選用徑向基核函數。實驗所需的初始訓練樣本集通過聚類算法生成。為排除單次實驗結果的偶然性，實驗將10次同樣條件下的運行結果取平均值作為該條件下的實驗結果。兩個數據集的實驗結果如表1-2所示。

由表1-2所示的實驗結果可知，與經典的SVM增量學習算法相比，本文算法的分類精度明顯高于前者，該結果表明，相比之前的支持向量，殼向量包含了更多有用的分類信息。同時，本文算法的訓練時間相比前者縮短了接近一半。這也說明，選擇違背KKT條件的新增樣本參與訓練的方法是可行的，不僅縮短了訓練時間，而且無用樣本的剔除也進一步改善了模型的分類性能。以上結果驗證了本文算法的可行性和有效性。

5.結語

本文基于支持向量機的特性和前人的研究成果，提出一種改進的增量學習算法。該算法綜合考慮歷史訓練樣本和新增訓練樣本的特點，使用殼向量代替支持向量，以此來保留更多的歷史分類信息。同時利用KKT條件對新增的訓練樣本集進行約簡，只保留最有可能轉變為支持向量的樣本參與新一輪的增量訓練。實驗結果表明，相比經典的SVM增量學習算法，該算法具備較短的訓練時間和較高的分類精度，并且能夠保證良好的推廣效果。