基于f-散度的復雜系統涌現度量方法

屈 強， 何新華， 陸皖麟

(裝甲兵工程學院信息工程系， 北京 100072)

?

基于f-散度的復雜系統涌現度量方法

屈 強， 何新華， 陸皖麟

(裝甲兵工程學院信息工程系， 北京 100072)

針對目前復雜系統涌現研究領域缺少量化手段的問題，提出了一種基于f-散度的復雜系統涌現度量方法。首先，從有序性角度重新定義了涌現，提出了涌現強度的概念；然后，從可度量性、收斂性和靈敏度角度，分析比較了常見的5種f-散度，認為Hellinger(Hel)散度最適合涌現度量；最后，給出了Hel散度的近似計算方法和涌現度量流程，并通過螞蟻尋食實例仿真驗證了該涌現度量方法的有效性。

涌現度量； 涌現性； 復雜系統；f-散度； Hel散度

系統是由具有相同目標的單元相互作用構成的整體[1]，可分為簡單系統、無組織系統和復雜系統。復雜系統具有非線性、自組織性、自適應性和涌現性等特性，而涌現性是認識復雜系統的重點。涌現性是系統整體具有，分解到局部就不存在的屬性、特征、行為和現象等[2]。目前，涌現還主要停留在定性研究階段，而定量研究是涌現判斷、預測和控制的前提。

GABBAI等[3]最早提出用熵來度量涌現，DE WOLF等[4]提出用離散熵來分析無中心系統的自組織涌現行為，然而有序性并不等同于涌現性，因此采用有序性指標(熵)來直接度量涌現還有待商榷。MNIF等[5]提出采用不同時間點的熵差來度量自組織系統的涌現，HOLZER等[6]提出用熵值的商度量涌現，兩者的研究本質是用有序性增量作為涌現的度量，是對文獻[3-4]研究的改進，具有很強的借鑒意義。

有序性增量既可用熵差、熵值的商來度量，也可用f-散度來度量。如：FISCH等[7]引入f-散度來度量涌現，提出采用Hellinger(Hel)散度度量涌現，并比較了Hel散度與熵差度量涌現的優缺點，但未詳細說明選用Hel散度的原因。針對上述問題，筆者系統論述了基于f-散度度量復雜系統涌現的理論依據，通過分析比較證明了Hel散度最適合涌現度量，給出了Hel散度近似計算方法和涌現度量流程，并進行了有效性驗證。

1 基本概念

1.1f-散度

f-散度首先由CSISZAR等[8]和ALI等[9]在概率論中提出，用以度量概率分布之間的差異。假設概率分布P(x)和Q(x)定義在概率空間Ω上，且P(x)對Q(x)連續，則對于滿足f(1)=0的凸函數f(x)，Q(x)到P(x)的f-散度定義為

(1)

對于式(1)，如果概率空間Ω上存在一個參考概率分布μ，使得P(x)和Q(x)均相對于μ連續，則其對應的概率密度函數p(x)、q(x)可分別寫為dP(x)=p(x)dμ和dQ(x)=q(x)dμ。于是，f-散度定義可改寫為[10]

(2)

在實際應用中，f-散度定義式常轉變為離散形式。如果f(x)為[0,∞)區間上的凸函數，且概率分布集合P={p1，p2，…，pN}和Q={q1，q2，…，qN}滿足

(3)

則Q(x)到P(x)的f-散度可定義為

(4)

1.2 涌現和涌現強度

涌現是指系統單元在環境刺激下相互作用，從無序(或準無序)狀態向有序狀態轉變的過程。無序和有序是系統單元狀態的統計學特征，其無序來自于系統單元行為的隨機性，而有序是涌現的結果。環境刺激是涌現的外因，單元間的相互作用是涌現的內動力。系統單元在環境作用下定向改變狀態，并向內傳導，使得狀態呈現統計意義上的有序。系統涌現出的有序狀態定義為涌現特征。

假設系統S從t1到t2時刻產生涌現，某項系統特征x的取值分布從無序變為有序，則有序性增量E(x)為

E(x)=Rt2(x)-Rt1(x)，

(5)

式中：Rt1(x)和Rt2(x)分別表示t1和t2時刻系統特征x取值分布的有序性。

顯然，有序性增量越大，涌現特征越明顯，越容易被觀察分析。因此，可將系統特征有序性增量定義為涌現強度(用E表示)，以表征涌現特征的明顯程度。系統單元之間的不同作用將產生不同的涌現特征，作用范圍不同，涌現強度相差較大，為了化繁為簡，設定涌現強度門限，重點抓住強涌現特征，忽略弱涌現特征。

系統特征取值完全無序時，近似服從正態分布。涌現發生時，系統特征的概率分布將發生變化，涌現強度越大，概率分布變化量越大。概率分布變化量可用f-散度來表征，因此涌現強度又可用f-散度來表示，即

(6)

式中：Pt1(x)、Qt2(x)分別為t1和t2時刻系統特征x取值的概率分布。

2 f-散度的種類與選取

2.1f-散度的種類

由于凸函數f(x)有很多函數形式，根據式(4)可知f-散度也有多種類型，其中5種常見的f-散度，如表1所示[11-14]。

表1 常見的f-散度

2.2f-散度的選取

根據可度量性、收斂性和靈敏度來比較選擇適用于度量系統涌現特征的f-散度。

1)可度量性

設X為一個集合，R為實數集，函數d(·)滿足映射關系：X×X→R。若對于集合X中的任意元素x、y、z，函數d(·)滿足：

(1) 非負性：d(x,y)≥ 0，當且僅當x=y時d(x,y)=0。

(2) 對稱性：d(x,y)=d(y,x)。

(3) 三角不等式：d(x,y)≤d(x,z)+d(z,y)。

則稱函數d(·)為集合X上的完全可度量函數。不完全滿足以上3個條件的函數稱為廣義可度量函數或廣義距離(Generalized-Metrics)[15-16]。

5種f-散度中，全變差散度、Jensen-Shannon(JS)散度和Hel散度完全滿足上述3個條件，為完全可度量函數，具有完全可度量性；Kullback-Leibler(KL)散度和χ2散度則不滿足對稱性和三角不等式，屬于廣義距離，不具備完全可度量性。

2)收斂性

Hel散度的取值范圍為[0,1]，用于后續數據處理時程序收斂速度更快。而全變差散度和JS散度的取值范圍為[0,∞)，需要進行歸一化處理才能確保程序收斂。

3)靈敏度

靈敏度是指函數變量取值微小變化時函數值的相對變化量。它是函數值相對于變量值的靈敏程度，具體表達式為

(7)

將5種f-散度對應的f(x)函數歸一化處理后代入式(7)進行比較，可知：全變差散度靈敏度最高，KL散度靈敏度最低，Hel散度、JS散度和χ2散度靈敏度居中。

綜上分析可知：5種f-散度中，Hel散度具有完全可度量性、較好的收斂性和較高的靈敏度，是涌現度量的最佳選擇。

3 基于Hel散度的涌現度量

3.1 Hel散度的近似計算

對于離散分布的Hel散度，其定義式為

(8)

Hel散度計算的關鍵是進行概率分布的估計。概率分布估計的方法分為參數法和非參數法，其中：參數法包括最大似然估計法和貝葉斯估計法等；非參數法包括Parzen窗法和K近鄰法[17]等。本文采用Parzen窗法進行概率分布估計，其流程為：首先，建立系統實例，從初始時刻t1開始，連續以等間隔d采集v個樣本(v>>hN，其中hN為窗體長度)；然后，采用滑動數據窗估計p和q。

Parzen窗法的基本形式為

(9)

式中：X={x1,x2,…,xN},為樣本空間，其中N為樣本總數；D為數據維數；φ(·) 為窗函數，通常選取正態窗函數，即

(10)

將式(10)代入式(9)可得

(11)

根據式(8)、(11)可近似計算Hel散度。

Parzen窗估計的滑動加窗方法分為2種：1)采用一窗固定、一窗滑動的方法，將第1個窗體q固定在時間軸的t1時刻，以t2時刻為中心滑動第2個窗體p，如圖1(a)所示；2)第1個窗體q加在t1時刻，第2窗體p加在t2時刻，然后以等間距d同時滑動q和p兩窗，如圖1(b)所示。

圖1 Parzen窗估計的2種滑動加窗方法

3.2 涌現度量流程

假設系統S由m個單元組成，t1時刻開始觀察，t2時刻出現L種系統宏觀特征，進行涌現度量，其流程如下：

1) 構建系統S的特征值集X={x1,x2,…,xL}，選取其中一個特征xk(k=1，2，…，L)；

2) 分別對t1、t2時刻特征xk的取值進行統計，估計其概率分布p(xk)、q(xk)；

3) 根據式(8)計算t1至t2時刻特征xk的涌現強度Ek；

4)設定判據門限e，若Ek>e，說明系統涌現出了特征xk，可納入系統S的涌現特征集(系統涌現特征構成的全集M,M?X)；

5)重復上述步驟，直至所有特征度量完畢；

6)根據涌現強度大小對涌現特征集中的涌現特征進行排序，供后續分析使用。

4 仿真實例

在空間全局信息未知的情況下，蟻群能夠共同找到食物和最短路徑，將食物搬運回巢穴。蟻群尋食過程并不是所有螞蟻個體行為的簡單總和，而是螞蟻相互作用后產生的涌現，采用NetLogo仿真軟件對此過程進行建模仿真。

以蟻群分布為系統特征，假設蟻群由100只螞蟻組成，在初始時刻t1，蟻群無組織地隨機搜索，螞蟻位置坐標在觀察空間呈隨機分布，如圖2(a)所示；經過信息素作用，蟻群出現自組織和協同，t2時刻涌現出如圖2(b)所示的螞蟻位置斑圖。

圖2 不同時刻螞蟻位置分布圖

由于螞蟻位置坐標為二維數據，為計算方便，將其轉化換為一維樣本數據，具體方法為：將觀測空間劃分為9塊區域，相當于分辨率設置為3×3；假設落在同一塊區域的螞蟻位置坐標相同，依次對觀察區域進行編號(如圖3所示)，則落在第j(j=1,2,…,9)塊區域中螞蟻的個數為xj，此時樣本空間為X={x1,x2,…,x9},數據維數D=1,N=9。

圖3 觀察空間劃分與編號

采用式(11)中的Parzen窗法估計t1、t2時刻螞蟻在觀察空間上的概率分布Pt1(x)和Qt2(x)，選取窗體長度hN=5；然后，將Pt1(x)和Qt2(x)代入式(8)計算得出t2時刻的Hel散度值。同理，在[t1,t2]內等間隔劃分15個仿真步長(共計17個步數)，分別計算出相應時間點的Hel散度值，如圖4所示。

圖4 Hel散度變化圖

由圖4可知：1)開始未放置食物，因而螞蟻的分布坐標較為隨機，系統為無序；2)從步數7開始放置食物，Hel散度值明顯增大，這是因為螞蟻在尋找、搬運食物的過程中釋放信息素，系統因信息素的作用而趨向于有序；3)根據經驗，選取判斷門限e=0.1，則從步數9時刻開始涌現強度可被分辨；4)從步數11時刻開始，Hel散度達到最大并趨于穩定，即最大涌現強度為0.16。

上述分析表明：Hel散度能夠有效度量復雜系統的涌現特征。當然，坐標空間上的螞蟻位置斑圖只是蟻群系統的涌現特征之一，若選擇不同的屬性進行觀測，則可能還有其他的涌現特征，這里不再逐一度量。

5 結論

從可度量性、收斂性和靈敏度角度分析比較了5種常見的f-散度，認為Hel散度最適合涌現度量。給出了基于Hel散度的涌現度量方法流程和近似計算方法，并通過蟻群仿真實驗驗證了有效性。

基于f-散度的度量方法也存在很多問題，例如：使用Parzen窗估計散度時，需要用戶根據經驗設定窗體長度；在不同的觀察分辨率下對同一涌現過程進行度量，將得到不同的涌現強度。因此，如何選取窗體長度和觀察分辨率等是今后需要重點研究的問題。

[1] KONSTANTINOS P T,PAUL D C.A comprehensive basis for systems engineering theory[C]∥Proceedings of 2014 IEEE International Systems Conference.Ottawa，ON，Canada:IEEE,2014:139-143.

[2] 苗東升.論涌現[J].河池學院學報,2008,28(1):6-12.

[3] GABBAI J M E,YIN H,WRIGHT W A,et al.Self organization,emergence and multi-agent systems[C]∥Proceedings of 2005 International Conference on Neural Networks and Brain.Beijing,China:IEEE,2005:1858-1863.

[4] DE WOLF T,SAMAEY G,HOLVOET T,et al.Decentralised autonomic computing:analysing self organising emergent behaviour using advanced numerical methods[C]∥Proceedings of Second International Conference on Autonomic Computing.Seattle,Wa-shington,D.C.,U.S.:IEEE Computer Society,2005:52-63.

[5] MNIF M,MULLER-SCHLOER C.Quantitative emergence[J].IEEE mountain workshop on adaptive and learning systems,2011(1):39-52.

[6] HOLZER R,DE MEER H,BETTSTETTER C.On autonomy and emergence in self organizing systems[J].Lecture notes in computer science,2008,5343(1):157-169.

[7] FISCH D,JANICKE M,SICK B,et al.Quantitative emergence:a refined approach based on divergence measures[C]∥Proceedings of 2010 4th IEEE International Conference on self adaptive and self organizing Systems.San Francisco,California,America:IEEE,2010:94-103.

[8] CSISZAR I.Information-type measures of difference of probability distributions and indirect observations[J].Studia scientiarum mathematicarum hungarica,1967,2(3):229-318.

[9] ALI S M,SILVEY S D.A general class of coefficients of divergence of one distribution from another[J].Journal of the royal statistical society,1966,28(1):131-142.

[10] 任鳳英，李興斯.基于f-散度的一致風險度量[J].大連理工大學學報,2013,53(5):772-776.

[11] JOHN J,JOHNSON IV,ANDREAS T,et al.A theory of emergence and entropy in systems of systems[J].Procedia computer science,2013,20:283-289.

[12] ZENG J S,KRUGER U,GELUK J,et al.Detecting abnormal situations using the Kullback-Leibler divergence[J].Automatica,2014,50(11):2777-2786.

[13] VICTOR G C,ROCIO R,ENRIQUE A.Class distribution estimation based on the Hellinger distance[J].Information sciences,2013,218:146-164.

[14] BRIESCH D M,JAJA C E,MOORE T J,et al.Divergence measures tool:an introduction with brief tutorial[R].Adelphi:Army Research Lab,2014.

[15] KOPPERMAN R,PAJOOHESH H.Intrinsic generalized metrics[J].Algebra universalis,2012,67(1):1-18.

[16] GIANNOPOULOS P,VELTKAMP R C.A Pseudo-metric for weighted point sets[J].Lecture notes in computer science,2002,2352(1):89-114.

[17] 李慶，胡捍英.支持向量預選取的K邊界鄰近法[J].電路與系統學報,2013(2):91-96.

(責任編輯: 尚菲菲)

A New Approach to Measure the Emergence of Complex System Based onf-divergence

QU Qiang, HE Xin-hua, LU Wan-lin

(Department of Information Engineering, Academy of Armored Force Engineering, Beijing 100072, China)

In complex system research, there is still no mature means of quantitative description of emergence till now. To solve this problem, an emergence quantitative measurement method based onf-divergence is proposed. Firstly, the concept of emergence is re-defined in the view of system order, and the concept of emergence power is given for the first time. Secondly, analysis and comparison for the five kinds of commonf-divergence from the perspective of measurability, convergence and sensibility, Hel-divergence is considered as the best measure for quantitative emergence. Lastly, the process of emergence measurement based on Hel-divergence and approximate calculation method of Hel-divergence are given. The effectiveness of thef-divergence method is verified by simulation example of ant colony.

quantitative emergence; emergent property; complex system;f-divergence; Hel-divergence

1672-1497(2017)03-0106-05

2016-12-23

軍隊科研計劃項目

屈 強(1982-)，男，博士研究生。

N941.4

A

10.3969/j.issn.1672-1497.2017.03.020