遊戲人工智慧讀書筆記（七）遊戲與監督學習

07-07

來自專欄第九藝術魅影

作者： Jing-Wen Yang @ Tencent Game AI Research Center (TGAIRC)

本文內容包含（但不限於）以下章節：

Chapter 2 AI Methods

Chapter 2.5 Supervised Learning

本書英文版： Artificial Intelligence and Games - A Springer Textbook4

接下來幾篇文章我們要討論機器學習演算法在遊戲中大概可以有怎樣的應用。而在機器學習中，最基本的，研究最深遠，應用最廣泛的就是監督學習。甚至在某些外人觀念中看來機器學習幾乎等同於監督學習（事實當然不是這樣，但是監督學習確實是機器學習中非常重要的一塊）。這篇讀書筆記主要是簡單討論一下監督學習是什麼，以及它可以如何和遊戲智能相結合。

監督學習是什麼

那麼什麼是監督學習？學術界的術語一般為supervised learning，即在監管指導下的學習。就像我們從小到大上學一樣，需要一個老師來教我們加減乘除一樣，監督學習也是需要大量的教學才能讓機器學到東西的方法。舉個大家喜聞樂見的例子來說，假如我們想要讓機器能夠區分鋼鐵俠和美國隊長。

但是機器就像一個第一次看漫威的孩子，他是不知道誰是美國隊長，誰是鋼鐵俠的。因此這個時候就需要一個老司機告訴他「穿鋼鐵盔甲的，可以噴氣飛的，是鋼鐵俠」，「帶個圓盾的，跑很快但不會飛的，是美國隊長」。在這裡「穿盔甲的」「帶圓盾的」稱之為特徵，「美國隊長」「鋼鐵俠」稱為標記。監督學習所做的就是建立特徵與標記之間的關係，並將建立起這種關係用於預測沒有見過的數據，以後機器看到漫威的手辦或者海報也能知道區分鋼鐵俠和美國隊長了。

這裡我們更形式化一點來定義監督學習，監督學習需要從給定的 $N$ 個樣例數據（通常被稱為訓練數據） ${(x_1, y_1),ldots,(x_N, y_N) }$ 中（這裡 $x_i$ 就是第 $i$ 個樣例數據的特徵的表示向量， $y_i$ 就是它的標記），學習到一個函數 $f: X ightarrow Y$ 。

如何從訓練數據中得到這個函數呢？這就是演算法的訓練的過程。不同的演算法會對 $f$ 的形式作出不同的假設，比如是 $alpha x = y$ 這種簡單的線性形式，還是 $frac{1}{1+e^{alpha x + b}} = y$ 這種複雜一些的非線性形式。訓練的過程就是在假設的函數形式下尋找最佳的參數（比如這裡的 $alpha$ 和 $b$ ），使得函數能夠準確表達出訓練數據，並且在同類型的未見數據中也能給出正確預測。

在我們建立模型的時候，是不可能拿到所有數據的，模型好不好不能光看在訓練數據上的表現，在同樣的數據上，可能有成千上萬種模型可以很好的表達，但是對於未見數據，他們的性能則不一定相同了，這就是模型的泛化能力問題。

舉個例子而言，漫威中的戰爭機器穿著和鋼鐵俠很像的機甲，如果模型只學會從是否穿鋼鐵盔甲和是否會飛當做判斷標準，那麼戰爭機器就會被認為是鋼鐵俠了（實際上紅色的才是鋼鐵俠），那麼這樣的模型泛化性能無疑是很差的。

上面漫威的例子也可以更抽象的用下面的圖形來表示，其中紅色的叉和藍色的圈分別表示兩類事物，深藍色的線就是我們的監督學習模型，從左到右模型（線性，二次，多次）有不同的複雜度，都能在一定程度上區分這兩個類別，那麼哪個最好呢？這個其實很難給出答案，因為我們難以僅從圖上判斷出哪個模型的泛化性能更好。為什麼呢？因為除了我們可見的區域，其他區域的數據叉叉和圓圈的分布我們是不知道的，我們不知道我們這個藍線延伸的地方能不能把兩個隔開。

所以嚴格上來說，除非我們完全掌握一個數據的分布，知道每個數據的標記，我們才能測算一個模型的泛化性能。但是這往往是不可能的，如果數據的分布被我們知道的清清楚楚，那就不需要建立模型預測了，我們甚至可以自己生成數據了。因此只能用統計方法去估計，這樣的方法有很多，比如，交叉驗證是最常見的一種。具體來說核心思想就是從已知的數據集中劃分出一部分數據，不參加訓練過程，然後在模型訓練好之後，用來對模型進行評估。需要注意的是，訓練和測試數據的劃分應該要盡量保持數據分布的一致性（比如要保證各個標記比例一致），為了保持評估結果的穩定性，我們還會多次進行這個過程，比如下圖中，我們隨機將數據分為4次，然後做4次訓練和測試。這裡4的取值可以由我們確定，最常用的是10，此時稱為10折交叉驗證。

監督學習目前已經廣泛用於圖像識別、語音識別、醫療檢測、用戶建模等等若干重要領域。

當然它在遊戲中也可以有很多應用場景，拿我們熟悉的吃豆人遊戲為例，就可以設計如下的監督學習模型

{玩家的生命值，怪物的生命值，與玩家的距離} $ightarrow$ {操作（射擊，逃跑，靜止）} 有策略的去採取動作，而不是像大多數遊戲一樣固定模式的遊走
{玩家前一個位置，玩家當前的位置} $ightarrow$ {玩家下一個位置} 如果能夠預測出玩家的行為模式，就可以尋找更優的路徑去狙擊玩家
{擊殺數和爆頭數，子彈消耗} $ightarrow$ {技巧得分} 更靈活地評估玩家水平
{得分，探索過的地圖，平均心率} $ightarrow$ {玩家受挫程度} 這個數據難度高一些，但是用在遊戲開發過程中，是很好的輔助手段
{吃豆人和怪物的位置，炸彈是否可用} $ightarrow$ {吃豆人行走的方向} 更靈活地控制NPC的行動策略

上面這些看起來不起眼的關係，實際上卻與NPC的水平息息相關，在PvE的遊戲中，想想一個NPC能夠根據你的狀態聰明的選擇策略，那遊戲體驗一下就上去了。

常用監督學習模型

不同的模型假設引出不同的演算法，但是不存在一種假設能夠適應所有的監督學習問題，或者說如果不考慮具體的應用情景，不存在一個普遍適用的最優分類器，這也是著名的No-Free lunch理論，這個有比較簡單的證明可以參見周志華老師所著的《機器學習》第一章，也有比較深入討論這個問題的，可以參見論文 Simple Explanation of the No-Free-Lunch Theorem and Its Implications

這個理論也告訴我們不同的問題，應該要有不同的假設，才能夠取得比較好的模型，比如一個數據分布本來就是非線性的，非要用一條線去分隔開，肯定是分不好的。

但是另外一方面由於監督學習中特徵往往是我們自己造的，所以根據具體應用場景只要特徵提到位了，其實用一些常用的模型就可以勝任大部分的任務了。

這裡介紹幾種主流的模型，他們都是在機器學習領域有著深遠影響的模型，甚至以該演算法為核心形成了自己的派系。每種方法都經歷了浮浮沉沉，曾經獨立風騷，也曾經備受唾棄。現在回過頭來看的話，其實每種模型都有它的優缺點，有它適用的範圍。所謂「強扭的瓜不甜」，針對問題找到合適的演算法，才是正道。因此我們有必要弄清楚演算法的一些基本原理。

神經網路

這裡首先要介紹的就是神經網路，這個玩意兒現在可以說是火的一塌糊塗，有的朋友說貌似沒聽過，如果換個稱呼「深度學習」，那麼聽過的人就必定不在少數了。目前大部分的「深度學習」都是用深度很深的神經網路構建出來的（當然也有一些研究指出深度學習不一定要用神經網路，這裡就不做過多討論了）。其實神經網路是一個很簡單的模型，並且早就發明出來了。它主要由神經元和神經元之間的連接來定義。

上圖中虛線表示的神經元，接收用向量 $X$ 表示的輸入，並且對應於向量中的每一維 $x_i$ 都有一個參數 $w_i$ 與其進行關聯 $X*W$ ，一般還會額外再加上一個偏置參數 $b$ ，將輸入變為 $X*W+b$ 傳送給激活函數，得到相應的輸出 $g(X*W+b)$ 。通常我們需要從數據中尋找最優的 $W$ 和 $b$ 的組合，來訓練一個神經元。這裡的激活函數的選擇很多，比如 $g(x)=frac{1}{1+e^{-x}}$ 。但是都是非線性的函數，因為前面的操作為線性的，如果這裡還用線性函數，那麼神經元的表達能力就大大下降了。

而一般的神經網路其實就是一堆神經元的組合，最常見的就是通過層級關係組織的多層感知機，如下圖所示

每一層的神經元只會與前後的層里的神經元相連，但是不會與自己層里的神經元相連，具有這種形式的也被稱為前向神經網路。

那麼一個神經網路里，這麼多神經元，有那麼多參數要找，應該怎麼找呢？最常用的方法是Backpropagation，簡單的來說，當我們向網路輸入數據，根據設定的連邊和激活函數，我們可以一層一層的計算到最後，得到一個值，這個就是網路的輸出值，而這個值和標記可能有一定的誤差（沒有誤差就更好了，說明權值是對的），我們將這個誤差通過梯度更新的方式逐層更新回去，當在我們的訓練數據中，這個誤差總和最小了，說明我們這個網路能夠很好的表達出訓練數據了。（為了能夠讓這個過程正常進行，激活函數通常都會選擇那些求導比較簡單的函數，方便我們運用鏈式法則逐層求導）

從這樣的過程，我們可以看到，神經網路對於處理連續類型的數據更為自然一些。

目前的深度神經網路，主要也是通過不斷的加入神經單元層來增加輸入的非線性轉化能力，在一定程度上能夠自動完成初級特徵到高級特徵的轉換，用於處理諸如圖像這樣複雜的連續性數據具有非常顯著的效果。

具體到遊戲中，我們可以拿神經網路去模仿玩家的行為。我們可以收集玩家在遊戲中的行為數據。輸入上我們可以自己設計一些統計特徵（比如吃豆人和怪物的平均距離等），也可以利用神經網路的特徵抽取能力，直接使用一些初級的特徵（比如遊戲的圖像）。輸出標記就定為吃豆人每一幀採取的動作即可。

支持向量機

上面說到神經網路曾經也是大熱的話題，以至於支持向量機剛提出來時候，都強行套上神經網路的名字。但是歷史的車輪卻至此駛向了另外一條道路。支持向量機由於優雅的理論體系，快速的訓練速度，成功的取代神經網路成為新一代的演算法模型王者。

那麼支持向量機是什麼呢？我們先看一下下面這個例子

圖中有兩類數據，藍點和紅點，我們需要一個模型能夠很好的區分這兩種點，從我們已經看到的數據來看，似乎右邊的線也可以，左邊的線也可以，那麼我們實際使用的時候應該選哪個呢？直觀感覺似乎右邊的線更好一點，因為在我們沒有接觸到的數據里，在圖的下方的位置很可能會出現一個紅點，這時左圖的分界線顯然就分錯了。

而支持向量機要做得就是這樣的事，在數據中找一個最寬的線來分隔數據，因為這樣的線可以使得不同類別距離線最近的那個樣本（這樣的樣本就被稱為支持向量）也具有相當遠的距離，保證了模型的魯棒性。

如果用數學符號來表達一下，如果我們的數據用向量 $x$ 表示，那麼通常這個空間的一個超平面可以表示為 $omega x+b=0$ ，這裡參數 $omega$ 作為平面的法向量決定了平面的方向， $b$ 作為位移項，決定了超平面與原點之間的距離。樣本空間中的任意一點到平面上的距離可以由下面的式子計算（中學的計算公式）

$d=frac{|omega x + b|}{||omega||}$

如果能找到合適的 $omega$ 和 $b$ 使得這個超平面能夠有效的區分兩類數據，那麼它們一定滿足，如果 $y_i=1$ ，那 $omega x_i + b > 0$ ；如果 $y_i=-1$ ，那 $omega x_i + b < 0$ 。按照我們之前所確立的準則就是要找到距離最近的那個點，最遠的超平面，即

$arg max_{omega, b} {frac{1}{||omega||} min_n [y_i(omega x_i + b)]}$

整個演算法就是求解這個優化式子，求解方法有很多，也涉及到比較多的數學原理，限於篇幅，在此就不過多討論了。

如果還是有點不明白，這裡有個更為具體的圖形解釋，可以給大家一個直觀的感受。

支持向量機(SVM)是什麼意思？ - 簡之的回答 - 知乎
https://www.zhihu.com/question/21094489/answer/86273196

這裡的介紹是基於最基本的線性二分類問題的支持向量機，實際上支持向量機也能很好的去解決非線性問題，應用的主要技巧是核函數的技巧，簡單的來說，就是對數據空間進行升維，假如在原來的維度空間不能線性可分的數據，維度升高之後也許可以線性可分，依然按照求解超平面的方法就可以解決。如下面這個例子，原來在二維平面中的時候，我們沒有辦法用線性平面分開兩類點，但是當升維到三維的時候，兩類點就線性可分了！

支持向量機目前被廣泛應用在文本分類，手寫字識別這類應用中。在遊戲中，它其實和前面提到的神經網路類似，也可以用在模仿人類玩家行為的模型中，由於支持向量的關鍵性，因此對於我們的特徵設計和數據質量是有比較高的要求的。

決策樹

Stanford大學的一句標語

在這一部分我們介紹決策樹演算法，雖然好像決策樹現在好像沒有深度神經網路那麼火，但是實際上，在諸多應用中，決策樹都是數據挖掘者的首選演算法，比如知名的數據挖掘競賽Kaggle上，許多獲勝者都會將決策樹模型作為自己的關鍵武器。

決策樹模型其實理解起來非常直觀，我們可以看下面這就是個簡單的決策樹模型。樹的節點對應於我們輸入的特徵，節點又會有進一步的劃分形成的子節點。而樹的葉子就是我們希望區分的類別了。

通常我們通過一種由上至下的遞歸形式來構造決策樹（這裡需要假設輸入的特徵和輸出的類別都是有限的離散值，如果是連續值，就將它離散化）。我們按照某種指標從特徵中選取一個特徵作為劃分數據的指標，基於這個選擇出來的屬性，按照它可能的取值來生成子節點（如上圖第二層所示，我們可以按照歲數以20為分界點，將數據分成兩大類，後面的子節點以此類推）。隨著劃分的不斷進行，我們希望分支上包含的樣本盡量屬於同一類別（比如這類人就是買Prada的）。構建好決策樹之後，當我們遇到新的樣本的時候，按照決策樹的路徑去索取標記，就能得到預測了。

那麼如何選擇合適的特徵來進行劃分呢？考慮到上面的準則是每次劃分，希望分支上的樣本盡量往同類別去劃分，也就是每個分支的數據越「純」越好。那麼怎麼才能讓劃分達到提升純度最大的目的呢？這裡簡單介紹一種信息增益(Information Gain)演算法。

我們先通過信息熵來度量樣本集合的純度，假設當前樣本集合 $D$ 中第 $k$ 類樣本所佔的比例為 $p_k(k=1,2,ldots,|Y|)$ ， $D$ 的信息熵可以定義為 $Ent(D)=-sum_{k=1}^{|Y|}p_klog_2 p_k$ , $Ent(D)$ 值越小，則 $D$ 的純度越高。

如果候選的特徵 $x$ 有 $N$ 個可能的取值 ${x^1, x^2, ldots, x^N}$ ，用它來對數據集進行劃分，那麼會產生 $N$ 個分支節點，其中分支 $n$ 包含的數據集我們令為 $D^n$ 。那麼用特徵 $x$ 對數據集進行劃分所獲得的信息增益為

$Gain(D, x) = Ent(D) - sum_{v=1}^{V} frac{|D^n|}{|D|}Ent(D^n)$

其中 $frac{|D^n|}{|D|}$ 考慮到了不同分支樣本數不同，因此樣本多的占更大比重。我們簡單的選擇增益高的節點進行劃分即可。當然還有其他更好的劃分方式，在這裡就不做過多展開了。

由於決策樹這樣語義清晰的結構，這個模型天生具有非常好的解釋性。這是什麼意思呢，就是我們如果從數據中生成了一個決策樹模型，我們很容易將它其中的節點抽取出來，作為一種規則展示出來，這些規則可能是我們能夠預料到的，也有可能是我們之前沒有想過的，我們能夠對這些規則進行檢查，也能從這些規則中受到啟發。比如，如果用玩家玩吃豆人的遊戲數據訓練一個決策樹來控制吃豆人，給定最近怪獸的距離，能量球，與豆豆的距離，可以得到如下的決策樹。

如果一個怪獸靠近吃豆人，那麼如果附近有能量球的話，就去吃能量球（可以增加一條命），否則去盡量避開怪獸。如果怪獸不在吃豆人的視線內的話，就去看豆豆的距離，如果豆豆距離很近，或者不算遠，那就去吃豆豆。如果比較遠，則優先去吃水果（可以獲得額外加分）。可以看到我們演算法的決策過程具有非常清晰的語義，這一點是在神經網路和支持向量機里都比較難得到的。

總結

上面簡單介紹了三類常見的監督學習演算法，但是限於篇幅，這裡介紹的都是最基本的演算法形態，隨著研究的發展，這些演算法都已經發展出了非常強大的變種，比如卷積神經網路，遞歸神經網路，隨機森林，GBDT等等。

每類演算法都有自己擅長的問題類型，比如樹模型對於處理離散類型特徵更有優勢，神經網路模型對於處理連續類型特徵更有優勢，我們需要更具我們的問題去選擇合適的演算法。

而另外一方面，我們需要注意的是問題的難度本身是不會改變的。如果我們想要模型去學習一個複雜問題，而我們又不在特徵上下很多的功夫，那必然在訓練上會有很大的難度。反之，如果我們下功夫去處理特徵，那麼模型就可以很簡單。舉個例子，本來在二維平面無法用一個超平面劃開的數據，當我們多提取一維特徵值，使其空間成為一個三維空間的時候，就可以找到一個超平面去劃分了。（在SVM中通常使用Kernel函數達到這個效果，當然我們也可以靠我們的智慧去提取這樣的特徵）

You aim to cheat the devil. you owe him at least an offering.

簡單的來說就是「輕特徵->重模型」，「重模型->輕特徵」。所以其實談了這麼久的演算法，其實真正重要的是數據，數據決定了一個系統的上限，而演算法模型只是下限，好的演算法也只是能夠逼近上限。

誠然，在我們實際的應用中，很多時候很難設計出足夠好的，能夠使用簡單模型就能解決的特徵。這也是為什麼深度學習作為一種表示學習當前大行其道的原因。但是如果我們能夠花功夫去理解問題，去設計特徵，對於深度學習這種能夠自動進行特徵學習的演算法依然還是會有好處的。

監督學習的廣泛應用也已經延伸到了工業級的遊戲中，比如著名賽車遊戲Forza Motorsport（最近的E3展上又發布了新作，可以期待一下）。

他們設計的Drivatar可以根據玩家的遊戲數據，來生成具有和真實人類駕駛風格和駕駛水平非常相似的NPC來與玩家競速，極大的提升了玩家遊戲體驗。

相信隨著遊戲與人工智慧技術越來越精密的結合，在未來我們可以期待更多這樣利用人工之鞥技術為我們提升遊戲體驗的新型遊戲！

參考資料

以下推薦一些有足夠深度，但是初學者也能夠藉由入門的資料

- Andrew Ng教授主講的 Machine Learning公開課

- 台灣大學林軒田教授主講的機器學習技法

- 周志華教授撰寫的機器學習

實踐方面，

- 目前比較適合初學者，演算法比較全面而又使用方便的，當屬Python的scikit-learn庫

- 另外Waikato大學開發的Weka提供了圖形化的機器學習工作界面，可以方便不需要開發的使用者直接分析數據建立模型。

遊戲人工智慧 讀書筆記 （七） 遊戲與監督學習

監督學習是什麼

常用監督學習模型

神經網路

支持向量機

決策樹

總結

參考資料

遊戲人工智慧讀書筆記（七）遊戲與監督學習