試作歷程序列資料的動態生成模型：結合多層次感知機與增強學習的應用 / Developing a Dynamic Path Generator base on Users’ Activity Logs: a MLP and Reinforcement Learning Approach

6月 19, 2017 Data Mining , Programming/JavaScript , Work/Widget 2 Comments Edit Copy Download

繼前一篇談完歷程資料的分析方式之後，本篇則是從機器學習的角度切入，藉由分析不同背景使用者的操作歷程序列資料，並將對歷程結果的評價作為輸入資料，以此訓練一套懂得不同特質使用者會如何操作的多層次感知機(MLP)預測模型。接著再以任意一位使用者為背景，用此模型來生成一套評價較好的操作序列路徑。為了避免模形產生的路徑陷入無限迴圈，本篇以增強學習(Reinforcement learning)來懲罰會走到迴圈的序列路徑。

結果最後產生的序列路徑過度受到增強學習的影響，使得使用者的背景因素與歷程評價的影響變得微乎其微。這篇是為了記錄這一連串開發的過程、思維，以及未來的改進方向。這整套系統皆以JavaScript網頁開發，全部原始碼與資料都放在GitHub上，線上展示網址為： https://pulipulichen.github.io/dynamic-generative-path/ 。

歷程序列資料 / Activity Sequence Dataset

我取得實際使用者的操作資料，將使用者匿名，並將資料分成歷程序列資料sequence.csv、評價資料target.csv跟背景資料profile.csv三個檔案。為了方便處理，這些檔案都是以CSV格式儲存，第一列(第一行)是欄位名稱，後面才是資料。

以下各別介紹這三個檔案：

sequence.csv：這是使用者的歷程序列資料記錄。主要使用三個欄位：

• 第一個欄位是使用者的ID代號，串聯其他資料表之用；
• 第二個欄位是時間序列，資料並非實際上的時間，只是為了表示先後順序而使用。
• 第三個欄位之後的「verb」跟「uri」是辨識現在使用者所做的動作，「verb」是在網頁上的操作，「uri」是在哪一個網頁上進行。但其實第三個欄位之後可以替換或增加任意的資料，像是獲得的評分、停留的時間等等皆可。

target.csv：這是每一位使用者的評價記錄。這個評價的用途是建議分類模型儘量選擇評價較好的路徑。評價資料不一定是針對歷程序列資料的評價。

profile.csv：這是每一位使用者的背景資料記錄。可以是連續資料，像是年齡；也可以是類別資料，像是性別。但是請不要把類別資料性別編碼成0、1這種連續資料，這樣會造成程式的誤判。

瞭解了我們手邊擁有的資料之後，接下來就要來發展動態生成模型囉。

演算法架構 / Architecture

接下來我要說明我是如何建制動態生成模型。這個做法並非單純的一個演算法就做完，而是結合了許多步驟來產生。就結論來說，這個做法並不完美。但我的目的是提供一種思路，供有興趣的人思考看看怎麼作可以做得更好。

整個流程大致上分成以下步驟：

1. 資料前處理
2. 建立路徑規則
3. 建制先驗知識的訓練資料
4. 建立路徑評估器
5. 產生路徑
6. 修正路徑評估器

以下各別介紹每個步驟的內容。

1. 資料前處理 / Preprocess

首先，我們要先把三份CSV格式的檔案轉換成avaScript程式可以處理的JSON物件。從CSV轉換成JSON只是單純的字串處理，並不特別。只是有些資料是連續形態，像是age，有些則是類別形態，像是性別。我們使用JavaScript的isNaN()函式來識別資料是否為連續形態，如果是連續形態，則用eval()將之轉換成JavaScript的number數值類型，否則維持string字串類型。這只是一個小技巧，供大家參考。CSV轉換成JSON的工具請參考「fpf-csv.js」這個檔案。

資料前處理的重點在與整理歷程序列資料。除了將歷程序列資料以使用者順序排列之外，比較重要的動作在於將歷程序列資料中相同時間的事件進行合併。

以上圖為例，使用者User1在統一時間內執行了4次相同的事件，我們需要把它合併成一個事件。

此外，也會有相同時間發生不同事件的情況。這時候我們要將同維度的資料合併，轉換成 {user: "User1", time: 132505, verb: "GL5_5,GL5_6", uri: "/zh_tw"} 的JSON格式。

最後是將這些資料進行正規化，在同一維度中，最大值縮放為1，最小值縮放為0，中間值按比例縮放。

2. 建立路徑規則 / Building Path Rule

再來是要建立兩種路徑規則。

第一種是「下一步規則」。我們分析歷程序列資料中的每一個事件，記錄該事件的下一個事件為何，作為生成模型產生路徑的主要依據。其中有一個事件是null，下一步記錄的是每一位使用者行為序列開始的第一個事件，以此作為產生路徑的起點。

第二種是「結束規則」，裡面是每一位使用者行為序列的最後一個事件。當生成模型產生出符合結束規則中的事件時，表示這個行為序列已經完成，結束任務。

3. 準備先驗知識的訓練資料 / Preparing a Priori Knowledge Training Set

接下來是準備要提供給機器學習分類器所使用的資料。訓練資料分成三個部分：事件資料、背景資料及作為訓練目標的評價資料。

事件資料 / Activity

在這裡我們要選擇所使用的時間片段長度，也就是lag數。一般來說我們選擇的lag數是2，意思是用2個事件作為訓練分類器的依據。這個lag也會用於生成模型，也就是用2個事件來評估生成模型所選擇的路徑是不是好的路徑。

如果是lag數=2，那麼就以2為單位，從每位使用者的歷程序列資料中0-(lag數=2)+1=-1的位置作為開頭，依序向後取lag數=2個事件資料，依序加入「lag0_verb」、「lag0_uri」、「lag1_verb」、「lag1_uri」的訓練資料中。lag0_開頭的特徵是表示位於lag數=2中的第一個事件，而lag1_開頭的特徵就是第二個事件了。如果使用者在該位置並沒有事件，則給予null作為空事件來表示。

背景資料 / Profile

接著我們要把事件資料跟使用者的背景資料作結合，以表示這是什麼樣背景的人會作這樣的選擇。舉例來說，User1先做GL2_14，再做GL2_6，而User1是16歲女性，則我們將此筆訓練資料彙整成為16歲女性進行了GL2_14與GL2_6這兩個動作。

評價資料 / Target

最後我們來建構評價資料，這個評價資料是指引生成模型的主要方向。

首先第一個資料是事件資料中最後一個事件的位置。如果該使用者的歷程序列資料有5個動作，陣列指標為0,1,2,3,4，第一次取得事件資料的位置就是0，最後一次則是4。再來將其正規化為0到1之間。生成模型應該往數字較大的方向選擇路徑。這裡可以注意到，位置的計算是以使用者個人為單位，而非考慮到所有使用者整體的位置。這是因為我在規劃時比較在意的是個人適性化的因素，而非從整體角度來生成模型。

第二個是該事件資料是否是來自於成功完成的歷程序列資料。這邊的資料都是來自於真實完成序列的使用者，所以這裡的數值都會是1。後面若生成模型產生了不能成功完成的序列，那麼是否完成就會標示為0。

第三個之後的資料取自於target.csv評價資料。若User1的評價資料中有個欄位是class=1，那麼這裡就加上class=1。

最後我們將事件資料與背景資料組合成訓練集(train, x)，而評價資料就是訓練目標(target, label, y)。然後將這些資料中的類別資料轉換成虛擬變數，連續資料則繼續維持原本的連續資料形態。以此作為建立路徑評估器的依據。

路徑評估器應該根據事件資料與背景資料，來預測位置、是否完成、使用者個人評價，以此作為評估路徑的依據。

4. 建立路徑評估器 / Building Path Evaluator

有了訓練集跟訓練目標之後，我們接下來就要來建立路徑評估器。

由於我們要用多個維度的訓練資料來預測多維度的訓練目標，這邊我選擇的是類神經網路中前饋結構全聯結的多層次感知機(MLP)作為分類模型，使用的工具是machine_learning中的MLP分類模型。

這個MLP模型需要額外指定的參數有：

• 隱藏層數量 hidden_layer_sizes：我預設使用兩層，各別是訓練集特徵個數-1個神經元、以及訓練目標特徵個數-1個神經元。隱藏層數量越多，建立模型所需要時間越長。
• 學習速度 lr：使用預設值0.6。
• 訓練次數 epochs：使用訓練集數量。訓練次數越多，建立模型所需要時間越長。

最後就可以得到一個模型model。這個模型可以輸入test資料，用model.predict(test)來預測結果。

5. 產生路徑 / Generating Path

有了路徑評估器之後，我們就可以跟路徑規則結合在一起建構出基本的生成模型。這個生成模型進行的步驟大致上如下：

1. 產生一個隨機的背景資料，例如是16歲女性。
2. 建立一個結果路徑的空陣列。
3. 以null事件作為當前的事件。
4. 從「下一步規則」中挑出當前事件接下來可能的下一步事件列表。
5. 挑出下一步事件列表中的其中一個下一步事件，將結果路徑中最後的事件跟下一步事件整合成事件資料，結合背景資料，交給路徑評估器來產生多維度的預測結果，再將預測結果單純地相加，得到選擇這個下一步事件的評價。
6. 選擇評價最好的下一步事件，加入結果路徑中。
7. 將下一步事件設為當前事件。
8. 如果下一步事件符合結束規則中的其中一種，則結束這個生成模型，回傳結果路徑。否則回到第4步。

乍看這之下這個流程還算合理，但實際上生成模型會為了選擇評價最佳的下一步事件，最後會一直陷入無限迴圈之中打轉。

6. 修正路徑評估器 / Correcting Path Evaluator

為了避免生成模型落入無限迴圈之後，我們必須要限制結果路徑的最大長度，並且加入生成模型是否陷入迴圈的偵測機制。如果結果路徑超過了最大長度卻還沒結束，或是生成模型產生的路徑已經有高達3次連續重複的情況，我們就判定這次生成模型產生的路徑為失敗。

為了修正路徑評估器使其不再落入同樣的迴圈之中，我們有必要從失敗的例子作為負面教材，再加入訓練資料中來修正路徑評估器。我們從生成模型產生的失敗路徑中最後的lag數兩倍的長度作為失敗案例，以前述產生事件資料、背景資料的方式產生訓練集。而訓練目標則全部設為0，表示不建議路徑評估器往這個方向來走。

將失敗的訓練集和訓練目標也加入原本的訓練集和訓練目標後，我們再重新建立訓練模型。然後又回到前面第5步來產生路徑。若它又選擇了一個走到迴圈的路徑，則繼續用這一部的方法來修正評估路徑。這樣的流程會進行數次，直到生成模型真的能夠產生出符合結束規則的下一步事件為止。

結果 / Result

這樣的做法每次都會產生不一樣的結果。其中一次的結果如下：

生成步數平均數,8
生成步數標準差,0
生成路徑成功率,1
對抗生成模型次數：33

最後一個生成路徑:
{"GL":"GL2_14","URL":"/en/"}
{"GL":"GL2_6","URL":"/en/"}
{"GL":"GL2_6","URL":"/zh_tw"}
{"GL":"GL1_5","URL":"/zh_tw/information/mrt"}
{"GL":"GL1_4,GL2_13,GL5_5,GL5_6,GL6_2","URL":"/zh_tw/information/mrt"}
{"GL":"GL2_13,GL5_5,GL5_6,GL6_2","URL":"/zh_tw/information/trafficlist"}
{"GL":"GL1_5","URL":"/zh_tw/information/tipslist"}
{"GL":"GL1_4,GL2_13,GL5_5,GL5_6,GL6_2","URL":"/zh_tw/information/tipslist"}

雖然沒有仔細的記錄，但每次產生的路徑大概是7到13步之間。而所有使用者的最短路徑為11步，平均是25步，看得出來它的選擇會比使用者走的路更短。

然而，我設定了產生10次路徑，每次都隨機產生不同背景的使用者來產生路徑，但由於修正路徑評估器的影響太大，使得背景資料的影響程度降到非常低的程度，最後不論是誰產生出來的路徑都是一樣。

線上展示 / Online Demo

這整個系統我都是用JavaScript來實作。不是在伺服器運作的Node.js，而是可以在瀏覽器運作的JavaScript網頁，因此我們可以直接用Google Chrome瀏覽器的網頁來執行，甚至是自行輸入profile.csv、sequence.csv與target.csv資料。

所有的程式碼都放在GitHub中：

• https://github.com/pulipulichen/dynamic-generative-path
• 全部檔案下載：https://github.com/pulipulichen/dynamic-generative-path/archive/master.zip

你也可以用以下網址來開啟線上展示頁面，按F12打開console看它的運作細節。不過因為一開啟就會執行生成模型，會導致網頁速度變慢，請小心點選：

• https://pulipulichen.github.io/dynamic-generative-path/

討論 / Discussion

姑且不論這個「生成模型」跟現在機器學習所謂的「生成」這個概念並不相同，只是我借鏡這個想法而自己兜出來的一個作法。就結果來說，這是一個失敗的生成模型。

失敗的地方在於修正路徑評估器的做法影響太大，導致最後profile的背景資料跟target的評價資料的影響都變得微乎其微，甚至可以說，路徑評估器只是為了評估一條可以走到結束的路徑而已。雖然跟隨機選擇路徑的隨機路徑評估器相比，用MLP實作的路徑評估器走得路的確比較短，但這仍不是我想要的結果。

理想上，我希望這個生成模型產生出來的結果應該因人而異。即使大部分的路徑都一樣，但對不同人來說，少部分的路徑應該有所差異。但最後的結果並不是如此。這有可能是目前的資料量過少、無法體現出較大的差異，又或著是這套生成模型在建構時就有根本上的錯誤。

是建構路徑評估器的問題嗎？的確，在建構路徑評估器時我所準備的訓練集跟訓練目標都跟傳統的動態貝氏網路和RNN有所不同，這是因為我的做法是為了評估這條路徑是好或是壞，而不是預測下一個可能的路徑。雖然有人會問，這看起來只像是描述做法上的差異，評估路徑是好是壞、選出最好的下一個事件，不就是預測下一個最可能的事件嗎？但因為後者的做法會簡略地總合位置、是否完成跟評價資料，我還是比較偏好產生各別的預測結果，以便進一步用自己的方式來選擇需要的下一步路徑。雖然是這樣想，但在校正之後，MLP路徑評估器產生出來的預測結果中，是否完成的影響變得非常地大，變成了只是產生一條可以走到結束的路徑的生成模型。因此我這種想法可能並不適合這個情況，需要再檢討。

另一種可能是對模型訓練的改進，可以借鏡RNN的各種訓練方法。例如不僅是從歷程序列資料的開頭產生訓練集中的事件資料，也可以從歷程序列資料的結尾往回產生事件資料。或是採用混合學習的方式，隨機建構多個不同的模型，挑選不同分類模型中較佳的評估結果之類的做法，但一般論文中比較不傾向這種帶有太多隨機性的方式。再要不然就是用深度學習RNN來建構模型。現在JavaScript有CNN模型的ConvNetJS，也有RNN：

• RecurrentJS：它也跟我一樣用類似的方式在動態產生句子，很有意思。
  GitHub：https://github.com/karpathy/recurrentjs
• Neataptic：更簡單建立深度學習的框架，好容易使用。
  LTSM的例子：https://jsfiddle.net/9t2787k5/4/

不過個人私心推測，用這種方式仍然無法克服走不到終點的這一關。

一種簡單的做法是單純地調整時間片段的長度lag、隱藏層、學習速度lr與訓練次數epochs，找尋最佳化的參數。我有試著設定不同參數的組合，但最終無法克服最基本的難關：走不到終點。如果一個生成模型產生的序列一直走不到終點而陷入迴圈，那做什麼都沒用。最後只有應用增強學習的概念來修正路徑評估器，生成模型才能走到終點。因此調整參數這條路我也不覺得可走。

相反地，如果用增強學習的概念可以讓生成模型走到終點，那麼用增強學習應該也可以讓生成模型產生出適性化的差異。換句話說，目前的增強學習用途只有讓生成模型產生出可以走到終點的路徑，接下來應該加上增大不同背景使用者之間的路徑差異的做法。但這要怎麼作？我還沒有一個很好的想法。而這種做法也可能會導致最後路徑無法收斂，陷入更糟糕的局面。這都很難說。

結論 / Conclusion

這篇記錄了我做動態生成模型的大概過程。雖然有很多程式寫作的細節並沒能很詳細地說明，但應該大概能夠記錄做到現在的一些想法。這個生成模型搭配增強學習可以產生出一條路徑，但這個路徑卻無法達到我原本適性化的目的。接下來是要用RNN與LTSM改善模型呢？還是加入更多的增強學習來修正模型呢？這個問題就先留到之後再慢慢想吧。

總之，這個專案目前就做到這裡先終止了，未來若有機會再來想想要怎麼改進。有興趣的人歡迎在下面留言來討論。

圖 / pimberly

對了，有人可能會問說，現在深度學習的主流是用Python，為什麼我不要用Python來開發呢？一來是這個專案我只有一個晚上的時間開發，用JavaScript我比較有把握能夠實作我整個想法。二來是，我喜歡在網頁上就可以直接執行運作的程式。不需要伺服器、不需要特別的環境、更不需要編譯，用JavaScript開發的專案只要瀏覽器打開就能運作，下載下來簡單地修改程式碼就能看到結果，什麼套件都不用裝，這樣不是很令人開心嗎？