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

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

來自專欄第九藝術魅影6 人贊了文章

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

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

Chapter 2 AI Methods

Chapter 2.7 Unsupervised Learning

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

在機器學習中，除了監督學習和強化學習，還有一類重要的演算法，就是無監督學習（Unsupervised Learning）。這類演算法不像監督學習，需要大量的標記信息，也不像強化學習，需要反饋信息。它們能夠在數據中自動總結出數據的規律，發現潛在有用的模式。這種「無師自通」的技術雖然已經在數據挖掘領域被廣泛應用，但是在遊戲中，依然可以為我們提供更多的想像空間。

什麼是無監督學習

無監督學習（unsupervised learning）與監督學習（supervised learning）正好是兩個對立面，監督學習需要老師的悉心指導，需要老師不斷不斷的灌輸知識，離開了老師就啥也做不了。而無監督學習則不同，它靠著自己去梳理數據之間的關係，從而總結出一些有用的模式，如何總結出來呢？通常都是需要大量數據的支持，只要數據量足夠大，規律一定會是統計性顯著的，所謂「書讀百遍其義自見」也是類似的道理。

這裡個人覺得值得一提的是1980年美國哲學家提出來的中文房間實驗（The Chinese Room Argument）。這個思想實驗本來是用來反駁通過圖靈測試的機器並不一定具備了思考的能力。這個實驗假設一個完全不懂中文的英國人坐在一個封閉的房間中，房間中充滿了各種中文的符號，以及一本中文的使用手冊，當從房間外遞進來中文的問題時，房間內的人可以通過字元和手冊，完成問題的回答。但是房間內的人完全不理解這其中的含義，更談不上思考了。

這裡我覺得就和無監督學習有一些類似（其實好像現在的機器學習基本上都是這樣），機器可能並不會像人一樣去理解數據，但是能夠按照一定的準則找到一些規律，雖然這樣可能算不上真正的智能，但是從圖靈的角度來看，這也是一項非常重要的智能表現。因此無監督學習對於構建一個「類智能」體還是非常重要的。

常用的無監督學習方法

無監督學習的目標在於發現數據中的內在結構或者模式，這些結構或者模式，往往被總結為簇類，頻繁項，或者嵌入(embedding)表示的形式。下面就以此為分類大體介紹一下一些重要演算法的基本思想。

聚類

中國古語有云「物以類聚，人以群分」，說的就是聚類這個事情。聚類演算法就是要找到這樣的劃分，使得在一個簇里的數據相互直接都比較相似，不在一個簇里的數據都不相似。雖然聚類的目標都是相同的，但是聚類的手段卻是各種各樣的。目前可能都有上百種聚類的方法。聚類不僅能夠將數據劃分開，還能夠用來做數據壓縮（比如以簇中心作為特徵），異常點檢測（比如遠離其他簇所有簇的小簇）。而在遊戲中，聚類可以用來對玩家進行建模，甚至是內容生成。

這裡介紹一種非常常用的聚類演算法，K-Means聚類。

在K-Means中，簇由簇中心決定，每一個數據都被分配給最近的簇。簇的中心點就是這個簇所有數據的平均值。演算法總共分下面幾步：

1. 設定一個期望的聚類種類數目

2. 將數據隨機分配到各個簇中

3. 計算每個簇的簇中心

4. 再將每個數據分配到距離最近的那個簇中心的簇中

5. 再重新計算簇中心

6. 一直重複4-5直到簇中心不再發生變化

儘管K-Means非常流行，但是它也有很多局限，比如

- 它只能處理連續空間中的數據

- 就是k需要事先指定，這一點幾乎很難知道，就只能去試

- 無法處理非凸的聚類問題

- 對於異常點異常敏感，如果有一個偏離很遠的離群點，很有可能使得整個聚類結果錯誤。

除了K-Means之外，聚類演算法還有很多，不同簇的定義，不同相似度的定義都會帶來不同的聚類效果。甚至還有基於樣本密度來聚類的方法（比如DBSCAN），而不需要我們指定需要聚類的類別數目如果還想了解其他的聚類演算法，可以參見有關聚類的綜述類文章A Tutorial on Clustering Algorithms，The 5 Clustering Algorithms Data Scientists Need to Know。

頻繁項挖掘

這類演算法也被稱為關聯規則挖掘（Association rule mining），通常認為是數據挖掘中非機器學習類的演算法。其中比較重要的一個演算法是Apriori，與諸多機器學習演算法並稱為數據挖掘十大演算法。

演算法依照這樣的原理：

1. 頻繁項集的所有非空子集都必須也是頻繁的

2. 非頻繁項集的所有父集都是非頻繁的

依照這個原理，演算法過程其實比較簡單，給定一個實現定義好的閾值 ，

1. 通過掃描數據生成候選集合C1（每個候選僅1個元素）

2. 在通過閾值 過濾C1，生成頻繁項集合L1

3. 由L1中的數據兩兩拼接成為C2（每個候選有2個元素）

4. 在C2中通過 再次過濾生成L2

5. 由L2中的數據拼接成為C3...

6. 重複以上過程，直到Lk中僅有一個數據或者沒有數據

舉個遊戲中的例子來看，假如我們的資料庫中有以下這些記錄

A：完成超過10關；B：解鎖大多數成就；C：購買魔法護盾道具；D：找到巫師的紫色帽子；

• <A, B, C>
• <A, C>
• <B, C, D>
• <B, D, A, C>

如果我們設 ，頻繁項的挖掘就可以用下圖這個過程來表示

首先，先找大小為1的候選集，滿足 的就只有A：完成超過10關，B：解鎖大多數成就，C購買魔法護盾道具。由此為基礎擴展找大小為2的候選集，則只有{A,C}和{B,C}符合，大小再大一些的就無法找到滿足條件的了。

實際應用中，這樣的演算法還是不夠高效，有很多改良的演算法，當然其中影響最大的應該就是韓家煒教授提出的FP-Growth的演算法，只需要掃描兩次數據集，並且不使用候選集，通過生成一棵樹來生成關聯規則，實驗表明它要比Apriori快一個數量級。

當然除了上述這類挖掘，也還有時間序列數據的挖掘，比如我們可以在吃豆人中，挖掘用戶的行為規律，諸如<玩家 先去了左上方的角落，玩家隨後去了右下方吃了能量藥丸>，這樣的規律，可以幫助我們分析玩家，以便於設計更好的遊戲AI。時間序列的挖掘在數據挖掘中也是一個大課題，方法很多，篇幅原因，在此不贅述了。數據挖掘屆的大牛Christos Faloutsos在2015年的KDD上分享了關於時序數據的挖掘的專題報告Mining and Forecasting of Big Time-series Data，大家可以按圖索驥。

對抗生成式網路（GAN）

這裡書中並未涉及，但值得一提的是最近在深度學習界風風火火的對抗生成式網路（GAN）實際上也是一種無監督模型。

它的工作方式並不複雜（但是訓練卻比較困難，由於原始的目標函數存在著自我矛盾，又有改進版的W-GAN會更容易訓練出來）。它主要分為兩大塊，生成部分和判別部分。

- 生成部分通過接收一些隨機數字作為種子來生成圖片

- 這個生成的圖片則交給判別部分，判別部分同時也能從真實的圖片集中獲取圖片

- 判別部分會判斷這兩張圖片的真偽

這樣，我們就可以得到兩個反饋的閉環

- 判別部分能夠從真實數據直道判斷的正確性，從而提高自己的判別精度

- 生成部分能夠從判別器反饋的答案來提升自己生成的精度

這樣不斷的迭代下去，生成器就能夠生成足以讓判別器混淆，媲美真實數據的假數據。這裡神經網路實際上就起到了嵌入表示的作用，通過將真實數據的模式嵌入到一個新的空間中，來協助生成器依此進行生成。（當然其實這類嵌入表示的演算法也還有很多，比如ISOMAP，PCA這些都可以算）

GAN為我們提供了很大的想像空間，它可以在遊戲中有著非常廣闊的應用空間，目前就已經有人它來自動生成超級瑪麗的遊戲關卡了。

GAN甚至還能應用到給線稿自動上色，目前已經有一些開源的軟體可供大家使用了，比如PAINTSCHAINER。同樣的技術同樣能夠應用到為遊戲中的組件自動上色上。

從這兩個例子中，我們能夠感受到自動遊戲內容的生成將會為遊戲的研髮帶來巨大的革命，特別是自動生成內容如果質量足夠高的話，那遊戲開發的方式也許也會因此而改變！

總結

無監督學習作為一種比較特殊的技術，可以在遊戲研發領域有著十分有趣而又別樣的應用，他們不僅能夠輔助監督學習完成一些監督學習的任務，還能在一些監督學習無法涉足的領域大展拳腳。不過無監督學習也有自己的缺陷，它們往往效率比較低，比較難以訓練，而且需要一些先驗知識的引入。這些使得很多無監督學習演算法還很難大規模的應用。學術界也有通過藉助少量的監督學習信息來提高無監督學習效率的半監督學習（Semi-supervised Learning）的研究。相信隨著技術的進一步發展，這類「無師自通」的技術能夠為我們的遊戲研發翻開新的一頁！

推薦閱讀：