劉宏義

(中國(guó)人民解放軍邊防學(xué)院信息化研究試驗(yàn)室，陜西西安 710108)

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

1 支持向量機(jī)

支持向量機(jī)(SVMs)是學(xué)習(xí)分類器。例如，神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)分類器。但它們使用的概念略有不同。支持向量機(jī)(SVMs)是一個(gè)線性分類器的概括，與神經(jīng)網(wǎng)絡(luò)相比，SVMs關(guān)鍵的優(yōu)越性是其創(chuàng)建和訓(xùn)練算法［2］。

1.1 線性分類器

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

〈x，y〉代表標(biāo)準(zhǔn)點(diǎn)積〈x，y〉=x1·y1+x2·y2+…

圖1 線形可分離數(shù)據(jù)集

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

正如式(6)驗(yàn)證的每個(gè)點(diǎn)，訓(xùn)練就是要尋找w和d。但這里存在著無數(shù)個(gè)分離平面，需要從這些平面中選擇一個(gè)。盡量選擇一個(gè)最能概括分類器的平面。也就是說，使用一些沒有包含在訓(xùn)練集合中的數(shù)據(jù)，也能得到比較好的結(jié)果。這決定使用式(7)，如同在圖3中顯示的那樣，有兩個(gè)分離平面，每一個(gè)平面對(duì)應(yīng)一個(gè)yi值，平面間的距離稱為邊界?？梢员砻鳎吔缡桥c成比例的［4］。

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

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

現(xiàn)在的訓(xùn)練在于尋找 ai和 d。每個(gè)不能驗(yàn)證式(8)的點(diǎn)，系數(shù)ai將為空。因此可以把它從解決方法中移走，這是訓(xùn)練所要達(dá)到的目標(biāo)。支持向量及其相應(yīng)的系數(shù)作為分類器的參數(shù)。

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

圖4表明的解決平面都依賴于支持向量，因?yàn)樗鼈兌脊蚕矸ň€w，這些平面必定互相平行?？梢宰C明，去掉一個(gè)非支持向量的向量，解決方法并不改變。這是合乎邏輯的，因?yàn)樗鼈兊腶i為空，所以不會(huì)改變分類器的參數(shù)。

圖4 在支持向量中的平面

如果想用一個(gè)新數(shù)據(jù)集來訓(xùn)練系統(tǒng)，沒有必要添加整個(gè)舊數(shù)據(jù)集，需要的僅是舊數(shù)據(jù)集中的支持向量。

1.2 非線性可分離數(shù)據(jù)集的擴(kuò)展

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

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

圖6 通過使用轉(zhuǎn)換成一個(gè)更高維空間來解決問題

1.3 核心函數(shù)

如果轉(zhuǎn)換應(yīng)用于每一個(gè)向量xi和w，式(10)就變成了式(12)?！?(xi)，?(x)〉是兩個(gè)轉(zhuǎn)換向量的點(diǎn)積。盡管轉(zhuǎn)換空間已成為高維的，但返回值將總是一個(gè)標(biāo)量值?？梢园选?(i)，?(x)〉當(dāng)成一個(gè)簡(jiǎn)單的函數(shù)，其功能就是要返回一個(gè)標(biāo)量。這個(gè)函數(shù)稱為kernel(K)。式(13)給出了這個(gè)函數(shù)K(x，y)定義。現(xiàn)在不需要強(qiáng)求知道?(x)的值。此時(shí)的?(x)也可以轉(zhuǎn)換數(shù)據(jù)到一個(gè)無限緯度空間。作為一個(gè)舉例，式(11)表示的等價(jià)核心的轉(zhuǎn)換將在式(14)中計(jì)算?，F(xiàn)在可以重寫分類條件，最后形式如式(15)所示

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

1.4 訓(xùn)練

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

應(yīng)用拉格郞日優(yōu)化理論，式(18)就變成了式(19)［2］。式(19)是一種二次優(yōu)化問題。二次優(yōu)化理論表明問題是凸起的，不存在局部最小化問題。在這個(gè)優(yōu)化問題中，通?？梢哉业阶詈玫慕Y(jié)果。這是支持向量機(jī)(SVM)的一個(gè)重要優(yōu)勢(shì):當(dāng)給定數(shù)據(jù)集并選中核心函數(shù)后，通?？梢哉业阶詈玫慕Y(jié)果。多次訓(xùn)練這個(gè)系統(tǒng)都是得到一個(gè)完全相同的結(jié)果。雖然二次優(yōu)化算法有很多種，此處僅介紹支持向量機(jī)，更多的信息可以在文獻(xiàn)［3］中找到

2 短期記憶模型化

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

一方面，只要支持向量沒有改變，訓(xùn)練就會(huì)給出完全一樣的結(jié)果，解法集也不會(huì)改變，并且訓(xùn)練速度也非?？?。另外一方面，如果移走一個(gè)支持向量，與第一情況相比，訓(xùn)練需要的時(shí)間會(huì)更長(zhǎng)一些，但訓(xùn)練速度也很快，因?yàn)榉侵С窒蛄康臄?shù)據(jù)權(quán)重(ai)仍然為零。

系統(tǒng)派生可能會(huì)是一個(gè)問題，而且除了支持向量和它們的系數(shù)ai，解法也受到所選擇核心函數(shù)的約束。雖然這或許是一個(gè)優(yōu)點(diǎn)，或是一個(gè)缺點(diǎn)，因?yàn)橐x擇這樣的一個(gè)核心就可能會(huì)非常棘手。

這種技術(shù)在一個(gè)充滿變化的環(huán)境中相當(dāng)有用，因?yàn)檫^去學(xué)習(xí)到的知識(shí)對(duì)現(xiàn)在不會(huì)有無止境的影響。對(duì)于神經(jīng)網(wǎng)絡(luò)，如果環(huán)境發(fā)生了變化，一些決策可能就不再有效。有時(shí)為了糾正這種趨勢(shì)，會(huì)犯多次錯(cuò)誤。而對(duì)于帶有標(biāo)定日期的支持向量機(jī)(SVM)，只會(huì)有一次錯(cuò)誤或一次長(zhǎng)時(shí)間的等待。

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

3 CPU的消耗限制

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

4 結(jié)束語

介紹了支持向量機(jī)(SVMs)，引出了老化數(shù)據(jù)的概念。盡管這一概念可以用于大多數(shù)的分類器系統(tǒng)，但SVM是個(gè)很好的候選者，因?yàn)榉诸惼鞯膮?shù)是用訓(xùn)練數(shù)據(jù)集來表示的，還為支持向量的數(shù)量限制和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.