基于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