看書也會靈肉分離嗎？

黃心健在<科技蜃樓>這本書說到「靈肉分離」，他提到電玩界的「雷神派對」(Quake party)或「區網派對」(LAN party)中，有一群人(20~30位)會24小時不間斷地玩「雷神之槌」(Quake)或是「絕對武力(Counter Strike)遊戲，他們看著驚險充滿血腥畫面，聽著爆炸音效，大腦會覺得處於危險的環境中，便持續分泌腎上線素，但事實上，他們只有手在動，身體是休眠狀態。長時間下來，身體和思考出現斷層，就是大腦極度興奮，身體卻像是在睡眠。

當遊戲結束後，大腦和身體重新連線時，高速思考的大腦和休眠身體連接的瞬間，產生一種無可言喻的違和感，他稱為「靈肉分離」現象。

難道只有電玩產生這樣感覺，看書也會嗎？

QUnit方便去單元測試

寫在前頭

看完這篇文章後，也許會得到這樣的想法：

• 使用QUnit強大工具完成單元測試。 
• 如何根據Location的hash屬性所指的頁面，執行對應Test Case。

自訂類別

• BaseTestCase
  只有兩個功能，新增測試函式及依序執行，預設是使用QUnit執行test。   
• BaseTestCaseSuite
  同樣也是負責新增及執行BaseTestCase實體，執行時會先抓現在Location的hash屬性，在依照hash值找出對應BaseTestCase執行。
• TestView&TestRouter
  硬是要用Backbone來助陣XD

加入一些測試

先假設有3個頁面，然後分別加入測試函式。
GO TO DEMO

結論
這篇算是自己的筆記，其用意是作單元測試時，可以把全部測試內容寫在一起，在切換不同頁面情況下，能自動找出對應測試函式並執行，預計後續不會只有局限抓取hash值，還能抓整個URL去解析，使整個測試流程會比較順。

完整程式碼

參考資料

• QUnit
• Backbone.js

PCA for Reduce Dimensions

寫在前頭
你會從這篇文章看到：

• 使用R軟體執行主成份分析(Principal Components Analysis, PCA)減少資料維度。

但無法從這裡得到：

• 嚴謹又完整的PCA教學內容。

單刀直入砍維度
情境：假設有一個m╳n的資料集，因n個屬性太多，該如何縮減？(為快速說明，就使用100╳2的資料集，縮減為100╳1)

總結
PCA的優點是將用k維的向量來代表n維空間的資料點，可以節省儲存空間，加速演算法計算，但值得注意的地方，該如何降低維度才能保留資料特性，這又是另一個討論議題，就先擱著囉！

參考資料

1. Tan, Steinbach, Kumar, ”Introduction to Data Mining”,2005

倒傳遞神經網路(BACKPROPAGATION NETWORK, BPN)

寫在前頭

2017/08/03 編輯：

1. 修正計算錯誤。
2. 備註加入新連結。

你可以從這篇文章得到：

1.          BPN基本概念。

2.          如何實作BPN，並應用在遊戲裡。

3.          提供一個使用BPN決策的DEMO NPC。

BPN簡介

BPN的網路架構為多層感知器(multilayer perceptron, MLP)，就是輸入層與輸出層之間多一層隱藏層(hidden layer)，使用誤差倒傳遞演算法(Error Back Propagation, EBP)為學習演算法，屬於多層前饋式網路，以監督式學習方式，處理輸入輸出之間非線性映射關係。

圖 1 BP網路圖

簡單說，BPN是由向前傳遞(forward pass)及向後傳遞(backward pass)兩個部份組成，向前傳遞(如圖1 由左至右黑線)是先將訓練資料丟進網路去跑，在計算出輸出結果與對應目標之間誤差，而向後傳遞(如圖1 由右至左紅線)是依誤差值去調整網路權重，經過這樣多次訓練後，就會將網路修正到誤差極小範圍內的輸出結果。其主要特性如下：

1.      學習精確度高

2.      回想速度快

3.      可處理非線性問題

提一下BPN會用到的數學公式。

l   向前傳遞

1.使用sigmoid為激活函數：

$$\mathit{f}\left(\mathit{x}\right)=\frac{1}{1+{\mathit{e}}^{-\mathit{x}}}$$

2.以均平方誤差(mean squared error,MSE)為計算誤差值方法：

$$\mathit{M}\mathit{S}\mathit{E}=\frac{{\left({\mathit{O}}_{\mathit{d}}\mathit{e}\mathit{s}\mathit{i}\mathit{r}\mathit{e}\mathit{d}-{\mathit{O}}_{\mathit{a}}\mathit{c}\mathit{t}\mathit{u}\mathit{a}\mathit{l}\right)}^2}{2}$$

l   向後傳遞

1.計算輸出層及隱藏層誤差值：

$${\mathit{\delta }}_{\mathit{o}}=\left({\mathit{C}}_{\mathit{i}}-{\mathit{u}}_{\mathit{i}}\right){\mathit{u}}_{\mathit{i}}\left(1-{\mathit{u}}_{\mathit{i}}\right)$$
$${\mathit{\delta }}_{\mathit{i}}=\left(\sum _{\mathit{m}:\mathit{m}>\mathit{i}}{\mathit{w}}_{\mathit{m},\mathit{j}}{\mathit{\delta }}_{\mathit{o}}\right){\mathit{u}}_{\mathit{i}}\left(1-{\mathit{u}}_{\mathit{j}}\right)$$

2.調整隱藏到輸出層和隱藏層到輸入層的權重：

$$\mathit{w}{*}_{\mathit{i},\mathit{j}}={\mathit{w}}_{\mathit{i},\mathit{j}}+\mathit{\rho }{\mathit{\delta }}_{\mathit{o}}{\mathit{u}}_{\mathit{i}}$$
$$\mathit{w}{*}_{\mathit{i},\mathit{j}}={\mathit{w}}_{\mathit{i},\mathit{j}}+\mathit{\rho }{\mathit{\delta }}_{\mathit{i}}{\mathit{u}}_{\mathit{i}}$$

看了一大推數學算式，也不知道該怎麼實作。最後，可以參考AI Application Programming, 2ed這本書提供的倒傳遞演算法例子。

圖 2 BP實例

l   The Feed-Forward Pass

計算各隱藏層的值和MSE。

$$\begin{array}{ccc}{\mathit{u}}_3& =& \mathit{f}\left({\mathit{w}}_{3,1}{\mathit{u}}_1+{\mathit{w}}_{3,2}{\mathit{u}}_2+{\mathit{w}}_{3,\mathit{b}}*\mathit{b}\mathit{i}\mathit{a}{\mathit{s}}_3\right)\\ & =& \mathit{f}\left(1*0+0.5*1+1*-1\right)\\ & =& \mathit{f}\left(-0.5\right)\\ & =& 0.377541\end{array}$$

$$\begin{array}{ccc}{\mathit{u}}_4& =& \mathit{f}\left({\mathit{w}}_{4,1}{\mathit{u}}_1+{\mathit{w}}_{4,2}{\mathit{u}}_2+{\mathit{w}}_{4,\mathit{b}}*\mathit{b}\mathit{i}\mathit{a}{\mathit{s}}_4\right)\\ & =& \mathit{f}\left(-1*0+2*1+1*1\right)\\ & =& \mathit{f}\left(3\right)\\ & =& 0.952574\end{array}$$
$$\begin{array}{ccc}{\mathit{u}}_5& =& \mathit{f}\left({\mathit{w}}_{5,3}{\mathit{u}}_3+{\mathit{w}}_{5,4}{\mathit{u}}_4+{\mathit{w}}_{5,\mathit{b}}*\mathit{b}\mathit{i}\mathit{a}{\mathit{s}}_5\right)\\ & =& \mathit{f}\left(1.5*0.377541+-1.0*0.952574+1*1\right)\\ & =& \mathit{f}\left(0.613738\right)\\ & =& 0.648793\end{array}$$

$$\begin{array}{ccc}\mathit{M}\mathit{S}\mathit{E}& =& 0.5*{\left(1.0-0.648793\right)}^2\\ & =& 0.0616733\end{array}$$

l   The Error Backward-Propagation Pass

計算出輸出層和隱藏層誤差值，在調整輸出層和隱藏各權重值及偏差值。(學習率為 ρ=0.5 )

$$\begin{array}{ccc}{\mathit{\delta }}_{\mathit{o}}& =& \left(1.0-0.648793\right)*0.648793*\left(1.0-0.648793\right)\\ & =& 0.080026\end{array}$$

$$\begin{array}{ccc}{\mathit{\delta }}_{\mathit{u}4}& =& \left({\mathit{\delta }}_{\mathit{o}}*{\mathit{w}}_{5,4}\right)*{\mathit{u}}_4*\left(1.0-{\mathit{u}}_4\right)\\ & =& \left(0.080026*-1.0\right)*0.952574*\left(1.0-0.952574\right)\\ & =& -0.00361531\end{array}$$

$$\begin{array}{ccc}{\mathit{\delta }}_{\mathit{u}3}& =& \left({\mathit{\delta }}_{\mathit{o}}*{\mathit{w}}_{5,3}\right)*{\mathit{u}}_3*\left(1.0-{\mathit{u}}_3\right)\\ & =& \left(0.080026*1.5\right)*0.377541*\left(1.0-0.377541\right)\\ & =& 0.0282096\end{array}$$

$$\begin{array}{ccc}{\mathit{w}}_{5,4}& =& {\mathit{w}}_{5,4}+\left(\mathit{\rho }*{\mathit{\delta }}_{\mathit{o}}*{\mathit{u}}_4\right)\\ & =& -1+\left(0.5*0.080026*0.952574\right)\\ & =& -0.961885\end{array}$$

$$\begin{array}{ccc}{\mathit{w}}_{5,3}& =& {\mathit{w}}_{5,3}+\left(\mathit{\rho }*{\mathit{\delta }}_{\mathit{o}}*{\mathit{u}}_3\right)\\ & =& 1.5+\left(0.5*0.080026*0.377541\right)\\ & =& 1.51511\end{array}$$

$$\begin{array}{ccc}{\mathit{w}}_{5,\mathit{b}}& =& {\mathit{w}}_{5,\mathit{b}}+\left(\mathit{\rho }*{\mathit{\delta }}_{\mathit{o}}*\mathit{b}\mathit{i}\mathit{a}{\mathit{s}}_5\right)\\ & =& 1+\left(0.5*0.080026*1\right)\\ & =& 1.04001\end{array}$$

$$\begin{array}{ccc}{\mathit{w}}_{4,2}& =& {\mathit{w}}_{4,2}+\left(\mathit{\rho }*{\mathit{\delta }}_{\mathit{u}4}*{\mathit{u}}_2\right)\\ & =& 2+\left(0.5*-0.00361531*1\right)\\ & =& 1.99819\end{array}$$

$$\begin{array}{ccc}{\mathit{w}}_{4,1}& =& {\mathit{w}}_{4,1}+\left(\mathit{\rho }*{\mathit{\delta }}_{\mathit{u}4}*{\mathit{u}}_1\right)\\ & =& -1+\left(0.5*-0.00361531*0\right)\\ & =& -1.0\end{array}$$

$$\begin{array}{ccc}{\mathit{w}}_{4,\mathit{b}}& =& {\mathit{w}}_{4,\mathit{b}}+\left(\mathit{\rho }*{\mathit{\delta }}_{\mathit{u}4}*\mathit{b}\mathit{i}\mathit{a}{\mathit{s}}_4\right)\\ & =& 1.0+\left(0.5*-0.00361531*1\right)\\ & =& 0.998192\end{array}$$

$$\begin{array}{ccc}{\mathit{w}}_{3,2}& =& {\mathit{w}}_{3,2}+\left(\mathit{\rho }*{\mathit{\delta }}_{\mathit{u}3}*{\mathit{u}}_2\right)\\ & =& 0.5+\left(0.5*0.0282096*1\right)\\ & =& 0.514105\end{array}$$

$$\begin{array}{ccc}{\mathit{w}}_{3,1}& =& {\mathit{w}}_{3,1}+\left(\mathit{\rho }*{\mathit{\delta }}_{\mathit{u}3}*{\mathit{u}}_1\right)\\ & =& 1.0+\left(0.5*0.0282096*0\right)\\ & =& 1.0\end{array}$$

$$\begin{array}{ccc}{\mathit{w}}_{3,\mathit{b}}& =& {\mathit{w}}_{3,\mathit{b}}+\left(\mathit{\rho }*{\mathit{\delta }}_{\mathit{u}3}*\mathit{b}\mathit{i}\mathit{a}{\mathit{s}}_3\right)\\ & =& 1.0+\left(0.5*0.0282096*-1\right)\\ & =& 0.985895\end{array}$$

經過調整後，再跑一次向前傳遞，重新計算MSE有明顯變低。

$$\begin{array}{ccc}{\mathit{u}}_3& =& \mathit{f}\left({\mathit{w}}_{3,1}{\mathit{u}}_1+{\mathit{w}}_{3,2}{\mathit{u}}_2+{\mathit{w}}_{3,\mathit{b}}*\mathit{b}\mathit{i}\mathit{a}{\mathit{s}}_3\right)\\ & =& \mathit{f}\left(1*0+0.514105*1+0.985895*-1\right)\\ & =& \mathit{f}\left(-0.47179\right)\\ & =& 0.384193\end{array}$$

$$\begin{array}{ccc}{\mathit{u}}_4& =& \mathit{f}\left({\mathit{w}}_{4,1}{\mathit{u}}_1+{\mathit{w}}_{4,2}{\mathit{u}}_2+{\mathit{w}}_{4,\mathit{b}}*\mathit{b}\mathit{i}\mathit{a}{\mathit{s}}_4\right)\\ & =& \mathit{f}\left(-1.0*0+1.99819*1+0.998192*1\right)\\ & =& \mathit{f}\left(2.99638\right)\\ & =& 0.952411\end{array}$$

$$\begin{array}{ccc}{\mathit{u}}_5& =& \mathit{f}\left({\mathit{w}}_{5,3}{\mathit{u}}_3+{\mathit{w}}_{5,4}{\mathit{u}}_4+{\mathit{w}}_{5,\mathit{b}}*\mathit{b}\mathit{i}\mathit{a}{\mathit{s}}_5\right)\\ & =& \mathit{f}\left(1.51511*0.384193+-0.961885*0.952411+1.04001*1\right)\\ & =& \mathit{f}\left(0.705995\right)\\ & =& 0.669516\end{array}$$

$$\begin{array}{ccc}\mathit{M}\mathit{S}\mathit{E}& =& 0.5*{\left(1.0-0.669516\right)}^2\\ & =& 0.0546099\end{array}$$

BPN如何應用在NPC決策行為

首先，容許我說明一下遊戲設定，在遊戲中會有一位NPC和玩家對抗，基本上，NPC會有下列屬性：

1.      生命值：範圍會介於0~2之間，如果~生命值=0時，NPC就會消失不見。

2.      小刀：NPC必須要擁有小刀，才能與玩家進行近距離攻擊，其數值為0或1。

3.      手槍：除了要佩帶手槍外，NPC還要有足夠的子彈數，就可以射擊玩家，其數值為0或1。

4.      子彈數：範圍會介於0~2之間，每發射一次，就會耗損一枚子彈，若子彈數為0時，就不能發射，必須要填充子彈後，才可以繼續射擊。

當賦予NPC這些屬性後，會在遊戲中與玩家的互動過程中，會產生一連串決策行為，其下列是NPC設定之行為：

1.      射擊：當NPC有佩帶手槍且子彈數夠(大於0)，就會發動射擊玩家，若玩家被射中，就會損失一點生命值。

2.      小力攻擊：當沒有手槍可以攻擊，若NPC身上還有小刀時，NPC會選擇用小刀來攻擊玩家，直到NPC生命值很低，就會選擇逃跑模式。

3.      裝彈：當NPC身上佩帶手槍的子彈用盡時，就會到裝彈的地方補充彈藥，繼續攻擊玩家。

4.      逃跑：如果NPC無計可施，就會採最壞打算「逃跑模式」，直到自己被消滅為止。

將上述邏輯轉成M╳N的數值矩陣(如表1所示)，前四欄為輸入屬性，而後四欄是輸出目標，即為NPC對應的行為，當輸出目標的其中之一欄為1時，NPC就會去執行該動作。

表 1 訓練資料

生命值	小刀	手槍	子彈數	射擊	小刀攻擊	裝彈	逃跑
2.0	0.0	1.0	0.0	0.0	0.0	1.0	0.0
2.0	0.0	1.0	1.0	1.0	0.0	0.0	0.0
2.0	0.0	1.0	2.0	1.0	0.0	0.0	0.0
2.0	1.0	0.0	0.0	0.0	1.0	0.0	0.0
2.0	1.0	0.0	1.0	0.0	1.0	0.0	0.0
2.0	1.0	0.0	2.0	0.0	1.0	0.0	0.0
2.0	1.0	1.0	1.0	1.0	0.0	0.0	0.0
2.0	0.0	0.0	0.0	0.0	0.0	0.0	1.0
2.0	1.0	1.0	2.0	1.0	0.0	0.0	0.0
1.0	0.0	1.0	0.0	0.0	0.0	1.0	0.0
1.0	0.0	1.0	1.0	1.0	0.0	0.0	0.0
1.0	0.0	1.0	2.0	1.0	0.0	0.0	0.0
1.0	1.0	0.0	0.0	0.0	1.0	0.0	0.0
1.0	1.0	1.0	0.0	0.0	0.0	1.0	0.0
1.0	0.0	0.0	0.0	0.0	0.0	0.0	1.0
1.0	1.0	1.0	1.0	0.0	0.0	0.0	1.0

從這些NPC訓練資料中， BPN會去找出它們之間的Pattern，在利用這些訓練好的Pattern去完成決策。

略談遊戲程式碼

這個DEMO中所用的程式碼，如下列所示：

名稱	說明
Backpropagation.cs	為BPN運作核心，先將訓練資料讀入，並把網路權重訓練好，傳入參數至action方法，得到對應指令。
BulletCollision.cs	當子彈碰撞時，會產生爆炸效果，若子彈是和Player或NPC發生碰撞，並計算扣血值。
Detection.cs	當NPC跑到補充點，就會補充NPC手槍彈藥。
FireBullet.cs	Player或NPC發射子彈時，會丟出剛建立的子彈物件。
KnifeCollision.cs	NPC拿小刀攻擊時，如果發生碰撞，就會傷害Player。
MainGUI.cs	顯示Player的生命值。
NPC.cs	定義NPC所有屬性和對應行為。
PlayerScript.cs	定義Player所有屬性和對應行為。

總結

這一篇主要核心是利用BPN作分類器，由訓練資料集去劃分四個對應動作類別，在有限訓練資料筆數中，其分類準確度極高，但缺點是若輸入參數超出訓練資料集的數值範圍，就會造成誤判的問題，故必須要時時擴充訓練資料集，若能將所有發生的可能都放進去，就可避免此情形發生。

參考資料

1.          M. Tim Jones, “AI Application Programming”, Second Edition, 2005

2.          Brian Schwab, “AI Game Engine Programming”, Second Edition, 2009

3.          Neural Networks - An Introduction

備註

Unity3D Package下載
GitHub
Gist - 範例程式碼