基于f-散度的復(fù)雜系統(tǒng)涌現(xiàn)度量方法

屈 強， 何新華， 陸皖麟

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

?

基于f-散度的復(fù)雜系統(tǒng)涌現(xiàn)度量方法

屈 強， 何新華， 陸皖麟

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

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

涌現(xiàn)度量； 涌現(xiàn)性； 復(fù)雜系統(tǒng)；f-散度； Hel散度

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

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

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

1 基本概念

1.1f-散度

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

(1)

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

(2)

在實際應(yīng)用中，f-散度定義式常轉(zhuǎn)變?yōu)殡x散形式。如果f(x)為[0,∞)區(qū)間上的凸函數(shù)，且概率分布集合P={p1，p2，…，pN}和Q={q1，q2，…，qN}滿足

(3)

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

(4)

1.2 涌現(xiàn)和涌現(xiàn)強度

涌現(xiàn)是指系統(tǒng)單元在環(huán)境刺激下相互作用，從無序(或準(zhǔn)無序)狀態(tài)向有序狀態(tài)轉(zhuǎn)變的過程。無序和有序是系統(tǒng)單元狀態(tài)的統(tǒng)計學(xué)特征，其無序來自于系統(tǒng)單元行為的隨機(jī)性，而有序是涌現(xiàn)的結(jié)果。環(huán)境刺激是涌現(xiàn)的外因，單元間的相互作用是涌現(xiàn)的內(nèi)動力。系統(tǒng)單元在環(huán)境作用下定向改變狀態(tài)，并向內(nèi)傳導(dǎo)，使得狀態(tài)呈現(xiàn)統(tǒng)計意義上的有序。系統(tǒng)涌現(xiàn)出的有序狀態(tài)定義為涌現(xiàn)特征。

假設(shè)系統(tǒng)S從t1到t2時刻產(chǎn)生涌現(xiàn)，某項系統(tǒng)特征x的取值分布從無序變?yōu)橛行颍瑒t有序性增量E(x)為

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

(5)

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

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

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

(6)

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

2 f-散度的種類與選取

2.1f-散度的種類

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

表1 常見的f-散度

2.2f-散度的選取

根據(jù)可度量性、收斂性和靈敏度來比較選擇適用于度量系統(tǒng)涌現(xiàn)特征的f-散度。

1)可度量性

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

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

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

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

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

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

2)收斂性

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

3)靈敏度

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

(7)

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

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

3 基于Hel散度的涌現(xiàn)度量

3.1 Hel散度的近似計算

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

(8)

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

Parzen窗法的基本形式為

(9)

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

(10)

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

(11)

根據(jù)式(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 涌現(xiàn)度量流程

假設(shè)系統(tǒng)S由m個單元組成，t1時刻開始觀察，t2時刻出現(xiàn)L種系統(tǒng)宏觀特征，進(jìn)行涌現(xiàn)度量，其流程如下：

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

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

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

4)設(shè)定判據(jù)門限e，若Ek>e，說明系統(tǒng)涌現(xiàn)出了特征xk，可納入系統(tǒng)S的涌現(xiàn)特征集(系統(tǒng)涌現(xiàn)特征構(gòu)成的全集M,M?X)；

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

6)根據(jù)涌現(xiàn)強度大小對涌現(xiàn)特征集中的涌現(xiàn)特征進(jìn)行排序，供后續(xù)分析使用。

4 仿真實例

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

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

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

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

圖3 觀察空間劃分與編號

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

圖4 Hel散度變化圖

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

上述分析表明：Hel散度能夠有效度量復(fù)雜系統(tǒng)的涌現(xiàn)特征。當(dāng)然，坐標(biāo)空間上的螞蟻位置斑圖只是蟻群系統(tǒng)的涌現(xiàn)特征之一，若選擇不同的屬性進(jìn)行觀測，則可能還有其他的涌現(xiàn)特征，這里不再逐一度量。

5 結(jié)論

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

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

[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] 苗東升.論涌現(xiàn)[J].河池學(xué)院學(xué)報,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-散度的一致風(fēng)險度量[J].大連理工大學(xué)學(xué)報,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] 李慶，胡捍英.支持向量預(yù)選取的K邊界鄰近法[J].電路與系統(tǒng)學(xué)報,2013(2):91-96.

(責(zé)任編輯: 尚菲菲)

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