用支持向量機建模學習過程

劉宏義

(中國人民解放軍邊防學院信息化研究試驗室，陜西西安 710108)

在當前的游戲開發中，最具有挑戰性的工作是人工智能的編程。其中關鍵的部分就是學習過程。當游戲玩家不斷地變化玩游戲的策略，學習系統就會遇到很多困難。經典的學習系統需要花費很多時間忘記舊規則，同時學習新規則。作為一種解決方法，文中為學習分類器引進了一個時間概念，這樣，系統就可以很容易地忘記過去的事情。這里提出支持向量機(SVMs，Support Vector Machines)，這種技術可以應用于其他類型的分類器。

1 支持向量機

支持向量機(SVMs)是學習分類器。例如，神經網絡學習分類器。但它們使用的概念略有不同。支持向量機(SVMs)是一個線性分類器的概括，與神經網絡相比，SVMs關鍵的優越性是其創建和訓練算法［2］。

1.1 線性分類器

在超平面的幫助下，線性分類器可以把輸入空間分成兩個部分:類A為類B。位于超平面上部的每一點屬于類A，面位于超平面下部的每一點屬于類B。圖1顯示了一個已分類的數據集。在式(1)定義的平面D是分類器的唯一參數。如果xi被分為類A和類B，如果分類器是經過訓練的，這些數據的分類可以由式(2)和式(3)來實現。

〈x，y〉代表標準點積〈x，y〉=x1·y1+x2·y2+…

圖1 線形可分離數據集

然而，由兩個約束條件組成系統的訓練并非無足輕重。如果具備式(4)和式(5)，那么分類的條件就變成了式(6)

正如式(6)驗證的每個點，訓練就是要尋找w和d。但這里存在著無數個分離平面，需要從這些平面中選擇一個。盡量選擇一個最能概括分類器的平面。也就是說，使用一些沒有包含在訓練集合中的數據，也能得到比較好的結果。這決定使用式(7)，如同在圖3中顯示的那樣，有兩個分離平面，每一個平面對應一個yi值，平面間的距離稱為邊界。可以表明，邊界是與成比例的［4］。

驗證式(8)的那些點稱為支持向量。這些點支持此解決方法，其分布在限定平面上，并且位于它們類的邊緣

可以證明，向量w是支持向量的一個線性組合［1］。式(8)和式(9)的組合可被改寫為式(10)，現在分類的條件與訓練數據無關

現在的訓練在于尋找 ai和 d。每個不能驗證式(8)的點，系數ai將為空。因此可以把它從解決方法中移走，這是訓練所要達到的目標。支持向量及其相應的系數作為分類器的參數。

畢業論文要想設置不同的頁眉和頁腳，插入分節符是成功的關鍵。將光標定位到需要插入分節符的文字前。一般來講，畢業論文的封面、摘要、目錄和各章節都需要插入分節符，以便在這些內容處設置不同的頁眉和頁腳的內容。

圖4表明的解決平面都依賴于支持向量，因為它們都共享法線w，這些平面必定互相平行。可以證明，去掉一個非支持向量的向量，解決方法并不改變。這是合乎邏輯的，因為它們的ai為空，所以不會改變分類器的參數。

圖4 在支持向量中的平面

如果想用一個新數據集來訓練系統，沒有必要添加整個舊數據集，需要的僅是舊數據集中的支持向量。

1.2 非線性可分離數據集的擴展

如果輸入空間被轉換成一個高維空間，非線性可分離數據集也可以變成線性可分離的。圖5就顯示了這樣一個空間轉化的概念。

圖6(a)顯示了一個具體的例子。如果試圖用線性分類器為這些數據集分類，則無法獲得分離平面。如果在式(11)的幫助下，把一維的空間轉換成一個二維的空間，那么這時候數據集就是線性可分離的。圖6(b)表示轉換過程和一個成功的分離平面。這個舉例雖然簡單，但也表明這種轉化為更高維空間的可行性。

圖6 通過使用轉換成一個更高維空間來解決問題

1.3 核心函數

如果轉換應用于每一個向量xi和w，式(10)就變成了式(12)。〈?(xi)，?(x)〉是兩個轉換向量的點積。盡管轉換空間已成為高維的，但返回值將總是一個標量值。可以把〈?(i)，?(x)〉當成一個簡單的函數，其功能就是要返回一個標量。這個函數稱為kernel(K)。式(13)給出了這個函數K(x，y)定義。現在不需要強求知道?(x)的值。此時的?(x)也可以轉換數據到一個無限緯度空間。作為一個舉例，式(11)表示的等價核心的轉換將在式(14)中計算。現在可以重寫分類條件，最后形式如式(15)所示

核心函數必須驗證在文獻［1］中可以看到的條件。這種情況下，一些?(x)與核心函數匹配。式(16)中的核心函數具有如下的一些重要屬性

1.4 訓練

如前所述，在式(7)的約束下，訓練在于尋找w和b。使用式(9)，在式(15)的約束下，訓練就是要尋找ai和b。目標是要找到一個最概括的分離平面。必須最大化邊界或最小化于是算法訓練就變成了式(18)，這是一種有條件的優化。

應用拉格郞日優化理論，式(18)就變成了式(19)［2］。式(19)是一種二次優化問題。二次優化理論表明問題是凸起的，不存在局部最小化問題。在這個優化問題中，通常可以找到最好的結果。這是支持向量機(SVM)的一個重要優勢:當給定數據集并選中核心函數后，通常可以找到最好的結果。多次訓練這個系統都是得到一個完全相同的結果。雖然二次優化算法有很多種，此處僅介紹支持向量機，更多的信息可以在文獻［3］中找到

2 短期記憶模型化

分類器系統是采用收集的數據集進行訓練。在一個神經網絡中，不可能決定或者知道何時網絡忘記過去學到的東西。在支持向量機(SVM)中，分類是支持向量和它們的系數ai來描述的。這些向量是收集到的數據集的一部分。這樣就有可能給每個向量標定日期。然后，經過一定的時間段，為取消向量的影響，可以把它從解法集中移走。整個數據集就可以不斷地減少最老的向量，增加最新的向量。圖7顯示了移走一個過時的支持向量時，相應的解法集的變化情況。圖8顯示了添加一個新的支持向量時，相應的解法集的變化情況。

一方面，只要支持向量沒有改變，訓練就會給出完全一樣的結果，解法集也不會改變，并且訓練速度也非常快。另外一方面，如果移走一個支持向量，與第一情況相比，訓練需要的時間會更長一些，但訓練速度也很快，因為非支持向量的數據權重(ai)仍然為零。

系統派生可能會是一個問題，而且除了支持向量和它們的系數ai，解法也受到所選擇核心函數的約束。雖然這或許是一個優點，或是一個缺點，因為要選擇這樣的一個核心就可能會非常棘手。

這種技術在一個充滿變化的環境中相當有用，因為過去學習到的知識對現在不會有無止境的影響。對于神經網絡，如果環境發生了變化，一些決策可能就不再有效。有時為了糾正這種趨勢，會犯多次錯誤。而對于帶有標定日期的支持向量機(SVM)，只會有一次錯誤或一次長時間的等待。

雖然只在SVM中介紹了這種技術，顯然，這種技術也可適用到其他的分類器，只要分類器是從訓練數據集中得到的數據來表示它們的參數，例如最鄰近算法(KNN，K－Nearest Neighbors)。在加強學習方面，這種SVM可以代替神經網絡。

3 CPU的消耗限制

評估點x的值，需要計算方程。這種分類需要計算K(x，y)的值和每個支持向量的兩個乘積。重要的是限制分類器對CPU的消耗。降低CPU消耗的唯一方法是限制支持向量的數目，并限制到一個固定值。使用這些帶有日期的系統，支持向量數目太高時，最老的支持向量在評估時可以拋開不計。然而，拋開不計的支持向量不能從訓練數據集中移走。由此，支持向量必將被另外一個取代。這種行為將會降低分類器的有效性。在游戲中，限制支持向量的數目非常重要，因為它在決策中引入了一些噪音，所以效率下降并非總是壞事

4 結束語

介紹了支持向量機(SVMs)，引出了老化數據的概念。盡管這一概念可以用于大多數的分類器系統，但SVM是個很好的候選者，因為分類器的參數是用訓練數據集來表示的，還為支持向量的數量限制和CPU消耗的限制提出了解決方法。

［1］ BURGES C.A tutorial on support vector machines for pattern recognition ［J］.Knowledge Discovery and Data Mining，1998，2(2):955 －974.

［2］ CRISTIANINI N.Tutorial on support vector machines and kernel methods［EB/OL］.(2010 －08 －26)［2011 －12 －19］http://www.support－ vector.net/icml－ tutorial.pdf.

［3］ GOULD N，PHILIPPE T.A quadratic programming page［EB/OL］.(2010－03－17)［2011－12－10］http://www.numerical.rl.ac.uk/qp/qp.html.

［4］ MOORE A W.Support vector machines［EB/OL］.(2009 －09－19)［2011 －12－21］http://www.autonlab.org/trtorial/svm.html.