面向決策行為預測的多層策略網絡隨機游走模型

李曉寒,祁明澤,鄧宏鐘

(1.國防科技大學 系統工程學院， 長沙 410073； 2.國防科技大學 文理學院， 長沙 410073)

0 引言

決策者只需做出一次決策的決策過程稱為單階段決策過程。在現實世界中，特別是在雙方的交互對抗中，人們可能需要對同一決策過程反復決策，這樣的決策過程稱為多階段決策。多階段決策是很多問題的基礎，如在博弈對抗時，單方的決策過程可以看作是一個多階段決策過程[1-2]。很多時序過程，如股票漲跌[3]、天氣預測[4]也可以通過對時序數據進行序列分組的方法轉換為多階段決策過程。因此分析多階段決策問題對解決現實生活中的問題有重要意義。傳統的多階段決策過程常被建模為馬爾可夫鏈，即假設決策人以固定策略轉移概率進行依次決策，當前策略僅受上一階段的決策的影響[5]。但是決策人的決策行為實際上會受到階段結果的影響，例如本階段的策略獲利后，下一階段繼續采取該策略的可能性會增加，此時，傳統的馬爾科夫鏈不再適用。為了解決該問題，探究決策過程中人的決策行為規律，本文中引入了復雜網絡中隨機游走(random walks,RWs)的方法。

復雜網絡的隨機游走模型[6]能夠刻畫決策行為的隨機性，游走過程可以描繪決策人的決策過程，進而刻畫其行為規律，依據該規律可以對未來決策行為進行預測。網絡上隨機游走過程的算法及其應用研究受到廣泛關注，標準的隨機游走過程是指隨機游走子按照與邊權重成比例的概率移動到另一個鄰居。除此之外，人們還提出了其他類型的隨機游走，例如相關隨機游走、自避免隨機游走、乘法隨機游走過程和自適應隨機游走等[7]。這些不同類型的游走過程廣泛應用于不同的場景中，例如，乘法隨機游走過程是研究金融市場動態變化的有力工具[8]，自適應隨機游走通常會被用于研究生物系統中的動物遷徙過程[9]。此外，隨機游走還是很多網絡算法的基礎，在關鍵節點、邊或者其他關鍵網絡結構的識別過程中[10]，人們通常利用隨機游走的軌跡去搜尋重要節點、邊或網絡結構，例如經典的PageRank算法[11]和特征向量中心性[12]。近年來，在單層網絡上的隨機游走基礎上，人們還研究了時序網絡[13-14]和多層網絡[15]上的隨機游走過程。朱義鑫等[16]提出了時序網絡上基于隨機游走的免疫策略，解決了傳統免疫模型在時序網絡中所面臨的難以收集拓撲信息的困境。多層網絡上的隨機游走多被用來研究網絡擴散[17]和傳播過程[18]，Gómez等[17]通過研究多層網絡上的隨機游走過程，發現相比單層網絡，多層網絡的擴散速度更快。然而，利用多層網絡隨機游走研究決策過程的相關研究較少。本文中對多階段決策過程進行分析，首先，構建策略網絡模型，利用網絡上的隨機游走過程對多階段決策過程建模。隨后，將考慮決策階段結果的決策過程構建為多層策略網絡。同時，針對單層和多層策略網絡模型，提出了利用歷史決策信息的單步策略預測算法。最后，為了探尋模型與預測算法的有效性，采用多階段決策過程仿真數據和典型博弈場景決策數據進行實驗驗證。

1 基于單層網絡的多階段決策模型

研究的多階段決策過程是由若干個階段組成的重復決策過程，即相同結構的決策過程重復多次，其中每次決策稱為階段決策。雖然重復決策過程形式上是原決策過程的重復進行，但是對于決策者來說，并不是簡單的重復。決策者會依據上一階段的策略或結果選擇下一階段的策略。決策過程中出現的所有可能策略的集合組成策略空間。當前階段到下一階段采取的策略的變化稱為策略轉移。假設多階段決策過程有t個子階段，則各個子階段決策過程中依次采取的策略可以組成一個決策序列，稱該決策序列為決策鏈，用(s(1),s(2),…,s(t))表示，其中s(i)(i=1,2,…,t)為決策者在第i個子階段采取的策略。

1.1 策略網絡

策略網絡(strategy network)是以策略空間中的策略為節點，策略之間的轉移關系為有向邊，策略轉移概率為邊權重構建的有向加權網絡。記有限策略空間為S={s1,s2,…,sk}，k為策略空間中策略的數量，則策略網絡的鄰接矩陣可以表示為：

(1)

式中：wij為節點i與節點j之間有向邊的邊權重，表示決策過程中當前子階段采取策略si，下一子階段采取策略sj的概率，即wij=p(sj|si)。該矩陣需滿足式(2)：

(2)

即任意節點的出度之和為1。上述策略網絡的網絡結構與邊權不變，對應策略轉移概率不變的決策過程，將其定義為單層策略網絡(single-layer strategy network,SSN)。圖1為一個單層策略網絡的示意圖，它描述了一個策略空間為{A,B,C,D,E}的多階段決策過程，網絡中的有向邊表示決策者在決策過程中的策略轉移的方向，邊的權重表示對應的策略轉移概率。

假設決策人的決策行為是不固定的，決策人的每一步決策通常具有隨機性，因此多階段決策過程可以看作是一個策略網絡上的隨機游走過程。假設在網絡上有一個隨機游走子，該隨機游走子隨著網絡的邊以邊權表達的概率進行游走，每個子階段游走一步。隨機游走子在2個節點之間經過的概率就是2個策略之間的策略轉移概率。隨機游走子在網絡上的有限隨機游走過程可以表示一個有限階段的多階段決策過程，游走過的節點組成的序列構成多階段決策過程的決策鏈。圖1中藍色虛線表示一個隨機游走實例，代表了一個階段數為4的多階段決策過程，決策鏈為(A,C,D,E)。

圖1 單層策略網絡示意圖

1.2 基于單層策略網絡的單步預測算法

通常，決策者在決策過程中策略轉移的概率是未知的，因此網絡的邊權重及拓撲結構是未知的，若能根據歷史決策階段的決策策略得到策略轉移概率，便可對該決策者未來的決策策略進行預測。針對策略網絡為單層網絡的決策情形，筆者提出了一種單步策略預測算法。所謂單步預測是指在前t-1階段的決策策略已知的情形下，預測t階段最可能的決策策略。采取頻率近似概率的思想，利用歷史決策信息估計策略網絡的拓撲結構和邊權重，進而對決策行為進行單步預測。

歷史決策信息用決策鏈(s(1),s(2),…,s(N))表示，s(t)(t=1,2,…,N)表示階段t采取的策略，算法可預測下一階段N+1決策者最可能采取的策略s(N+1)，具體算法過程為：

輸入：多階段決策過程前N個階段的決策鏈(s(1),s(2),…,s(N))

輸出：下一階段的決策策略s(N+1)

1.初始化任意策略之間的轉移頻數，即c(sj|si)=0，i,j=1,2,…,k

2.fort=1 toN-1

3.c(s(t+1)|s(t))=c(s(t+1)|s(t))+1

4.end for

6.end for

7.得到下一階段的策略s(N+1)：

2 基于多層網絡的多階段決策模型

2.1 多層策略網絡

上文所描述的模型，決策策略僅受到上一階段的策略影響，但是決策者在多階段決策過程中難免會受到決策結果的影響，導致策略轉移概率發生改變。例如,在金融市場中，股民會有“追漲殺跌”的決策行為。考慮到階段結果對決策行為產生的影響，構建了多層策略網絡(multiplex strategy network,MSN)。

圖2 多層策略網絡示意圖

2.2 基于多層策略網絡的單步預測算法

相較單層策略網絡，多層策略網絡能夠刻畫結果對決策行為的影響，能夠捕捉決策者在不同階段結果下的決策行為習慣。對于階段結果已知的多階段決策過程，可以利用包含階段策略和階段結果的歷史決策信息估計多層策略網絡的拓撲結構和邊權重，進而估計不同階段結果下策略轉移矩陣概率，以預測單步策略。包含階段結果的歷史決策信息用決策鏈((s(1),r(1)),(s(2),r(2)),…,(s(N),r(N)))表示，其中，s(t)(t=1,2,…,N)表示階段t采取的策略，r(t)(t=1,2,…,N)表示階段t產生的階段結果，利用單步預測算法可預測N+1階段決策者最可能采取的策略s(N+1)，具體算法預測過程如下：

輸入：多階段決策過程前N個階段的決策鏈((s(1),r(1)),(s(2),r(2)),…,(s(N),r(N)))

輸出：下一階段的決策策略s(N+1)

1.令R=?，m=0，R表示階段結果集合，m表示集合中元素的個數

2.fort=1 toN-1

3.ifr(t) not inR

4.putr(t) inR

5.m=m+1

6.c(si|sj,r(t))=0,i,j=1,2,…,k

7.c(s(t+1)|s(t),r(t))=c(s(t+1)|s(t),r(t))+1

8. else

9.c(s(t+1)|s(t),r(t))=c(s(t+1)|s(t),r(t))+1

10.end for

15.end for

16.end for

17.得到下一階段的策略s(N+1)：

3 實驗驗證

為了驗證預測算法的有效性，針對仿真數據和一個重復猜拳博弈數據，設計了單步預測實驗。將隨機預測(RAND)作為對照組，比較和評估了基于單層策略網絡的預測算法(SSN)和基于多層策略網絡的預測算法(MSN)的預測效果。

3.1 仿真數據生成

假設一個多階段決策過程的策略矩陣的拓撲結構及邊權重是已知的，則可利用網絡上隨機游走過程生成仿真決策數據。在實驗中，利用圖2給出的邊權已知的多層策略網絡生成了任意階段數的決策鏈，從多個方面評估了預測算法的有效性，決策鏈的生成算法如下：

輸入：邊權已知的多層策略網絡，網絡層鄰接矩陣的集合為W={W[1],W[2],W[3]}，階段數N

輸出：階段數為N的決策鏈((s(1),r(1)),(s(2),r(2)),…,(s(N),r(N)))

1.隨機給定初始策略s(1)、階段結果r(1)

2.fort=1 toN-1

3.在多層策略網絡的當前結果層r(t)進行一次隨機游走，得到下一階段的決策策略s(t+1)

4.在階段結果層之間等概率隨機游走，得到下一階段的結果r(t+1)

5.將當前決策鏈更新為：{(s(1),r(1)),(s(2),r(2)),…,(s(N),r(N)),(s(N+1),r(N+1))}

6.end for

3.2 仿真過程行為預測

準確率是最普遍的評估指標，因此，首先將準確率作為評估指標，分析不同算法在多階段決策過程單步預測過程中的表現。準確率可以理解為對于隨機一條決策鏈進行單步預測，預測策略與真實策略相同的概率。在具體實驗過程中，通過改變初始策略，利用3.1節提出的算法生成了若干相同長度的決策鏈，并對每條決策鏈進行單步預測，對于n條長度相同的決策鏈，若預測正確的決策鏈數量為n1，則準確率定義為：

(3)

預測準確率除了會受到算法效果的影響，還會受到生成決策鏈數量n的影響，因此需要選擇合適的參數n。首先固定歷史決策階段數為100，考察不同決策鏈數量對準確率的影響，結果如圖3所示，首先可以初步看出基于多層策略網絡的預測算法有較高的預測準確率。此外，還可以看出當決策鏈數量較少時，準確率會呈現較大的波動幅度。隨著決策鏈數量的增加，預測的準確率趨于平穩，因此決策鏈數量越多，最后得到的準確率也最可靠。為了衡量隨著決策鏈數量變化，準確率波動幅度的大小，定義了準確率誤差：

(4)

式中：A(n)表示決策鏈數量為n時的預測準確率。為了考察在決策鏈數量為9 900～10 000準確率誤差的變化，繪制了如圖4所示的散點圖，可以看出，隨著決策鏈數量的變化，誤差會上下波動，但波動范圍不超過6×10-5。當決策鏈數量為10 000 時，準確率的誤差小于10-4，可忽略不計。因此，設定每次實驗生成決策鏈的數量為10 000。

圖3 準確率隨決策鏈數量變化圖

圖4 誤差隨決策鏈數量變化圖

準確率可以從整體上衡量預測的準確性，為了更全面地評估算法效果，還采用了精確率、召回率和F1-score等算法評估指標。精確率和召回率可以從局部衡量預測的準確性，對于每一個策略i，可以定義其預測精確率和召回率分別為：

(5)

(6)

式中：TPi為預測策略為i，真實策略為i的決策鏈數量；FPi為預測策略為i，真實策略不為i的決策鏈數量；FNi為預測策略不為i，真實策略為i的決策鏈數量。對于策略空間中k個策略的預測效果，可以用單個策略指標的平均值來衡量，具體為：

(7)

(8)

F1-score指標為精確率和準確率的調和平均數，定義為：

(9)

圖5給出了不同歷史決策鏈長度對預測效果的影響，(a)、(b)、(c)和(d)分別表示固定決策鏈數量為10 000時，不同算法在準確率、精確率、召回率和F1-score 4種評估指標下的表現。

圖5 不同評估指標隨決策鏈歷史階段數變化圖

從圖5(a)可以看出，隨機預測的準確率為0.2左右，是策略空間中的策略總數的倒數。基于單層策略網絡的預測算法的準確率會隨著決策鏈歷史階段數數量的增加而增加，當決策鏈歷史階段數增加到30時，準確率趨于平緩，穩定在0.3左右。這說明若當決策鏈中前30個階段的決策策略和階段結果信息已知，利用單層策略網絡可以對決策鏈的下一階段策略進行預測，但預測準確率僅比隨機預測高0.1。基于多層策略網絡的預測算法的預測效果要優于其他2種方法，其準確率也會隨著決策鏈階段數數量的增加而增加，當歷史決策階段數達到60時，準確率平緩，穩定在0.7左右。可以看出基于多層策略網絡的預測算法能夠得到較好的單步預測準確率，但需要更多的歷史決策信息。此外，從圖5(b)、(c)和(d)可以看出，對于在精確率、召回率和F1-score評估指標，基于多層策略網絡的預測算法的效果仍是最好的。4種評價指標的預測結果相似，因此在后文的實驗中，主要用準確率評估算法效果。

3.3 重復猜拳過程行為預測

為了進一步驗證提出的模型能夠有效捕捉決策人的決策行為習慣，在重復猜拳的決策數據集上進行單步策略預測實驗。

首先通過模擬雙方的重復猜拳過程得到決策數據，假定一方為隨機出招決策人，另一方為具有固定習慣的決策人。考慮了2種常見的猜拳習慣，第1種為“贏存輸平變”，即若己方贏了，則下一輪以較大概率繼續采取本輪策略；若己方輸了或雙方平局，則下一輪以較大概率采取能戰勝敵方本輪策略的策略。第2種為“贏輸變平存”規則，即若己方贏了，則下一輪采取敵方策略，若己方輸了，則下一輪采取能戰勝敵方本輪策略的策略，若雙方平手，則下一輪保持本輪策略不變。利用博弈過程中生成的決策數據，以及多層策略網絡對決策過程進行建模，并結合預測算法，可有效地捕捉到決策人的出招習慣。

圖6為對于決策習慣為“贏存輸平變”的決策者的決策行為預測的結果圖，圖7為對于出招習慣為“贏輸變平存”的決策人的決策行為預測的結果圖。在這2個預測中，基于多層策略網絡的預測均取得了較好的效果，預測累積準確率均能達到0.8左右。在每次預測過程中，都會估計多層策略網絡，圖8(a)和(b)分別給出了在歷史決策鏈長度為50和100時多層策略網絡鄰接矩陣的估計值。

圖6 預測準確率隨決策鏈歷史階段數變化圖

圖7 準確率隨決策鏈歷史階段數變化圖

圖8 多層策略網絡鄰接矩陣的估計

該鄰接矩陣可以反映出決策人的決策習慣，當決策鏈長度為50時，多層策略網絡鄰接矩陣反映的出招習慣還不準確，預測準確率僅能達到0.7左右，當決策鏈長度為100時，多層策略網絡已經能較為準確地反映用戶地決策習慣，且預測準確率能達到0.8左右。

4 結論

研究了單層策略網絡及網絡上的隨機游走過程，為多階段決策過程提供了一種網絡模型，同時在此基礎上提出了單步策略預測算法。此外，將單層策略網絡拓展為多層策略網絡，提供了考慮階段結果的決策過程的網絡模型，提出相應預測算法。通過實驗發現，考慮基于多層策略網絡的預測算法的預測準確率遠高于基準水平和基于單層策略網絡的預測算法。

本文中定義的決策網絡的預測場景可用于運動員行為習慣分析、多智能體系統行為預測和體系對抗博弈等領域，具體應用效果將結合實證數據進一步分析。同時，對于階段結果如何界定、歷史數據如何獲取等問題，也有待進一步研究。此外，對于決策過程中，決策空間隨時間變化的場景，可以結合時序網絡的隨機游走過程開展下一步研究。