贝叶斯学习

2024-10-29

贝叶斯学习（精选10篇）

贝叶斯学习篇1

1 引言

朴素贝叶斯算法是基于贝叶斯全概率公式的一种分类算法[1,2]。它以贝叶斯定理为理论基础,是一种在已知先验概率和条件概率的情况下计算后验概率的模式识别方法。朴素贝叶斯分类算法有一个基本限制:在给定特征条件下的属性值之间必须相互条件独立,即特征项独立性假设。尽管在现实世界中,这种独立性假设经常是不能满足的,但目前许多研究和应用都表明,即使违背这种假定,NB也表现出很强的健壮性[3],所以越来越受到机器学习研究人员的重视[4,5]。但是由于贝叶斯分类分类算法本身的特点,它不可避免地存在一些其他的限制和不足,如训练集永远没有变化或者更新训练集后需要重新学习分类器从而耗费大量时间等,增量学习方法能够弥补这些方面的不足。

增量学习(Incremental Learning)是一种得到广泛研究与应用的智能化数据挖掘与知识发现技术[1,6,7,8]。在这个信息不断增长的时代,一种机器学习方法是否具有良好的增量学习能力已经成为评价学习性能优劣的重要参考之一。但是传统的贝叶斯分类算法只是在分类时使用到先验概率与样本信息,很少涉及到对分类器进行增量学习,文章[6,8]中提到的增量学习都是基于文档型计算公式的朴素贝叶斯分类算法。这种使用文档型计算公式计算属性的类条件概率存在特征项对文本贡献不明显的弊端。Harry Zhang在文献[9]中提出了根据属性的重要性给不同属性赋不同权值的加权朴素贝叶斯(Weighted Naïve Bayes,简称WNB)模型并实验得出较理想的效果。但是Zhang的文章未涉及到增量学习修正分类器。

本文结合上述两种思想的优势,提出加权朴素贝叶斯分类增量学习算法。文章对加权贝叶斯分类增量学习算法思想以及实现过程进行了详细描述并对算法进行证明。通过算法分析,得到其相比无增量学习的贝叶斯分类,额外的空间复杂度与时间复杂度都在可接受范围。

2 朴素贝叶斯分类算法

2.1 朴素贝叶斯分类算法简述

朴素贝叶斯分类方法中,每个数据样本用一个m维向量:d=d(W1,…,Wi,…,Wm)表示,其中Wi表示文本特征项;训练集D={d1,d2,…,dN}中的每个文本属于类集C={c1,…,ck}中的一个类。利用贝叶斯公式通过类别ci的先验概率和文本的类条件概率P(d|ci)来计算未知文本d属于ci类的概率,并取后验概率最大的类为文本的类别。计算公式如下:

undefined

undefined

其中P(wj|ci)即特征项wj在类ci中出现的概率,也叫属性的类条件概率。

2.2 贝叶斯分类算法的缺陷

朴素贝叶斯分类算法具有简洁,高效和稳定等优势,但是也存在一定的弊端。其要求在给定特征条件下的属性值之间必须相互条件独立在现实文本中就难以满足。但目前许多研究和应用都表明,即使违背这种假定,朴素贝叶斯也能取得较好效果。除了这个独立性假设,目前研究的朴素贝叶斯分类算法还是存在一个比较明显的缺陷。

朴素贝叶斯分类算法就是根据训练样本的类先验概率和特征项的类条件概率(都从训练集D中得到)来预测后验概率,得出测试文档的类别标签。有限的训练文本集的文本分布很难完全代表总体文本的分布,所以计算得到的先验概率的可信度有待修正。如果训练集D没有良好的数据完备性,那么预测的测试文档类别标签就可能不准确。而真实的情况是,有限大小的训练集D不可能具有完备的数据,一些领域的分类文本也是一批一批得到。不学习新的文本的分类器的分类效果必然没有多学习新的文本的分类器的分类效果好。传统的贝叶斯分类要想学习新的文本所包含的信息,就需要重新学习全部文本,每这样学习一次,都需要耗费大量时间代价。

3 贝叶斯分类增量学习算法

3.1 增量学习思想

在原始条件下,训练集D是保持不变的。而有限的训练集要完全表示文本的分布情况是不现实的。为此需要通过一种方法来不断更新训练集,以期达到完备训练集从而使其分类效果更精确的目的。增量学习思想[3]就是将测试集Dt中没有类别标签的实例经过分类器分类后,经过一个严格判断过程,将判断确认正确分类的文本追加到训练集D中;以及将专家给出正确分类的文本和其他途径得到的批量已分类文本追加到训练文本集,使得训练文本信息能够得到扩充,信息量更加丰富。在分类器已有知识的基础上,结合新加入文本,再次训练分类器,利用新文本中含有的有用信息来修正当前的分类器,能够使得各类别的先验概率以及各特征项的类条件概率能够更加精确,从而使得分类器分类效果更好。

对于贝叶斯文本分类,增量学习的任务实质上是如何根据先验信息和新加入样本的信息来确定新的先验概率P(ci)和各个属性类条件概率P(wk|ci)。

对于属性类条件概率P(wk|ci),文献[6]与[8]中使用的是文档型计算公式:

undefined

其中P(Aj=aj|c=ci)为特征项aj属于类ci的概率,count(Aj=aj|c=ci)为在属于类ci的文本中出现了特征项aj的文本数, count(c=ci)为属于类ci为属于类的文本数。

此计算公式具体简洁易算的特点,能够使得分类方法在这个过程中计算速度很快。但是,依据此公式,多个对文本类别贡献不同的特征项,只要都同时在若干个文本中出现,其属性的类条件概率就相同。显然,这样的属性类条件概率公式完全不能凸显特征项在文本中的重要性。为克服此弊端,本文对属性的类概率P(wj|ci)计算采用能够体现特征项在文本中重要性的词频加权计算公式,公式如下:

undefined

式中|V|表示项表中总项数,TF(wj,ci)表示项wj在训练集中属于类ci的所有文本中出现的频次之和,即

undefined

式中fik为特征项wi在文本dk中的出现频率。为防止TF(wj,ci)为0从而引起P(wj|ci)为0的情况发生,可以在初始化时先给每个TF(wj,ci)赋初值0.01。赋小的初值能够解除前面的疑虑,同时又能避免淹没其他在类中少量出现但是分类能力强的特征项。

3.2 增量学习文本选择

并非所有测试文本都适合用来对系统进行增量学习,那些类别不太明确或者对类别表示贡献不大的文本,加入后可能反而使类别特征模糊化。所以对于哪些文本采取增量学习应有严格的限制。有两种情况的文本适合分类器增量学习,一种是有专家已经给予分类的文本,这在专题文本领域是很常见的;另一种是对未分类的文本,由分类系统自动判断其是否合适参与增量学习。本文主要论述第二种情况,第一种情况相比第二种情况少了判断过程,实际上是一个单纯的增量学习的过程。

对于没有类标签的文本dt,需要用现有的分类器为它分配类标签。为方便计算,本文定义给文本划分到某类的概率取一个名称为类置信度,用θ表示。依据上面的公式(4),文本dt属于类ci的类置信度为:

undefined

令θt=max{θi,1≤i≤k},则分类结果为,即dt属于类ct。

判断被分类文本dt是否满足加入训练集进行增量学习的条件是:如果θt满足:undefined,即θt不小于其他类置信度之和的某个系数倍,则系统相信文档dt属于类ci的划分确定可信。系数α设定越大,系统对于参与增量学习的文本要求越严格。根据经验得出α∈[1/2,1]系统都能得到比较好的效果。

3.3 算法描述

输入:训练集D={d1,d2,...,dN},测试集Dt={dN+1,dN+2,...,dK}

输出:分类器C,测试文档dt类别

Step1:利用训练集D,学习分类器C;

Step2:对于测试集Di中每个文本di,重复如下步骤:

Step3:利用分类器C,分类di,得到类标签〈di,ct〉;

Step4:依据式(6)判断类置信度θt,如果undefined,进行下一步,否则,转Step6;

Step5:undefined,修正分类器C,包括修正P(ci)、P(wk|ci)、D和|Dci|;

Step6:Dt=Dt-dt,判断Dt是否为空,为空,执行下一部,否则转Step2;

Step7:算法结束。

下面给出上述算法中的增量学习公式并在后文给出部分证明。

类先验概率修正公式:

undefined

属性的类条件概率修正公式:

undefined

文档数量修正公式:D=D+1;|Dci|=|Dci|+1,当ct=ci

其中:D表示文档总数;|Dct|表示属于ci类的文档数;|Wci|表示属于ci类的所有文本中的所有词频总和;fkt表示特征项wk在文dt中的频率;undefined表示文档dt中出现的所有词的词频总和。

对分类器进行修正的文本不仅仅限于系统判断保证准确分类的文本,还可以是专家分类结果文本和其他途径得到的批量带分类文本。对带分类的文本的增量学习,直接进行Step5。可以看出,依本算法得到的分类器除了拥有较好的自学习能力,还有良好的人机交互功能。其增量学习能力正是我们所期望的。

4 算法证明与分析

4.1 算法证明

下面对式(7)进行简单证明。为方便阅读,对新生成的变量P(ci),以P*(ci)表示以显示区别,其他变化变量同此。式(7)中ct=ci情况下对P(ci)增量学习公式证明如下:

undefined

证毕。

当ct≠ci时,P(ci)的增量学习公式undefined,可以看出它是ct=ci情况下对P(ci)增量学习公式的一部分,证明参照上式。

式(8)中当ct=ci并且wk∈dt情况下对P(wk|ci)增量学习公式证明如下:

undefined

证毕。

式(8)中当ct=ci并且wk∉dt情况下对P(wk|ci)增量公式证明如下:

undefined可以看出它是ct=ci并且wk∈dt情况下对P(wk|ci)增量学习公式的一部分,证明参照上式。

4.2 算法分析

对新加入一个文本到训练集,系统需要保存的内容包括:新文本的各特征项,各类的先验概率,各属性的类条件概率,为增量学习系统需额外保存与临时保存的内容有属于类ci的词频总和、|Wci|新加入文档dt中的词频总和undefined、新的类先验概率P(ci)以及新的属性的类条件概率P(wk|ci),不能分析得到,因增量学习而产生的额外空间开销为S(m),其中m为新文本中的特征项数;

在额外时间复杂度方面,对系统进行一个文本的增量学习,与不进行增量学习的差别主要在step4与step4,即需要对是否进行增量学习做判定以及需要重新计算被分类文档的词频总数、类先验概率、属性的类条件概率、文档总数与划入类的类文档总数。step4做判定的时间复杂度是O(k),计算总词频总数、文档总数与划入类的类文档总数是一个简单加法,复杂度为O(1),计算类先验概率的时间复杂度为O(k),计算属性的类条件概率的时间复杂度为O(km),不难得出额外时间开销为O(k)+O(1)+O(k)+O(km)=O(km),其中m为分类系统中所包含的总项数,k为文档类别总数。可以看出,贝叶斯分类增量学习算法在空间和时间复杂度上的额外开销都在可接受范围,所以该算法是可行的。

5 结束语

朴素贝叶斯分类方法以其高效率为广大研究人员接受,但是关于其增量学习方面得到的关注并不多,更多是关注到属性条件概率计算上面,以使特征项能更好的表现文本。本文研究属性类条件概率计算公式为TF加权法的加权朴素贝叶斯分类增量算法,对给出了算法思想,具体算法以及算法证明和分析。虽然采用TF加权比文档型计算公式对分类效果要好很多[9],但是采用的TF加权法,也存在如下弊端:一些在多种类型的文本中多次出现的词削弱了其他分类能力强的词的表现力。作者下一步目标是研究能够在时间复杂度可接受范围内进行的更理想的加权朴素贝叶斯分类增量学习算法。

参考文献

[1]史忠植.知识发现.北京:清华大学出版社,2002.169～220

[2]王玉玲.基于贝叶斯理论的分类模式挖掘方法研究.微计算机应用,2007,28(6):664～668

[3]Domingos P,Pazzani M.On the Optimality of the Simple Bayesian Classifier under Zero-One Loss.Machine Learning,1997,29(2-3):103～130

[4]Yager R.An extension of the naive Bayesian classifier.Information Sciences,2006,176:577～588

[5]Mc Callum A,Nigam K.A comparison of Event Models for Naive Bayes Text Classification.AAAI-98Workshop on Learning for Text Categorization,Madison,Wisconsim:AAAI Press,1998,509～5l6

[6]宫秀军,刘少辉,史忠植.一种增量贝叶斯分类模型.计算机学报,2002,25(6):645～650

[7]Nadeem Ahmed,Syed Huan.Incremental learning with support vector machines,IJCAI[c],Stockholm,Sweden,1999.

[8]姜卯生,王浩,姚宏亮.朴素贝叶斯分类器增量学习序列算法研究.计算机工程与应用,2004,14:57～59

[9]Harry Z,Sheng S.Learning Weighted Naive Bayes with Accurate Ranking.In:Fourth IEEE International Conference on Data Min-ing(ICDM'04),2004.567～570

贝叶斯学习篇2

【摘要】对于一道考研真题，比较分析了文献[1]和[2]中的方法，借助MATLAB将随机试验并不直观的样本空间以编程的方式呈现，利用MATLAB仿真随机试验的数值结果进行曲线拟合，拟合结果与文献[1]中的结果非常接近，误差不超过10-3，因此验证了文献[1]中方法是正确的。并通过理论分析指出了文献[2]中方法错误的原因，修正了文献[2]中方法的计算过程，给出了P（ 1|A2）正确的计算公式。理论分析方法能更深刻地理解贝叶斯公式，理论分析结果与文献[1]中方法相同。

【关键词】条件概率全概率公式贝叶斯公式 MATLAB仿真

【中图分类号】O211.5【文献标识码】A 【文章编号】2095-3089（2016）08-0128-02

文献[1]和[2]中对于同一道概率问题给出了两种解法，分析也是大相径庭，结果迥异。究竟哪种方法是正确的，本文将通过MATLAB数值模拟和理论分析两种方法进行讨论分析，两种方法的结果都与文献[1]相同。文献[1]和[2]中讨论的概率题如下：

例：设有来自三个地区的各10名，15名和25名考生的报名表，其中女生的报名表分别为3份，7份和5份，随机地取一个地区的报名表，从中先后抽出两份。已知后抽到的一份是男生表，求先抽到的一份是女生表的概率P。

文献[1]中方法：用事件Hj表示报名表是第j地区考生的，j=1，2，3，事件Ai表示第i次抽到的是男生表，i=1，2。显然A1，A2，A3构成完备事件组，且

P（H1）=P（H2）=P（H3）= ，P（A2|H1）= ，P（A2|H2）= ，P（A2|H3）= ，P（ 1A2|H1）= = ，P（ 1A2|H2）= = ，P（ 1A2|H3）= = 。

由全概率公式得

文献[2]中方法：当H1发生时，P（ 1|A2）= ，当H2发生时，P（ 1|A2）= ；当H3发生时，P（ 1|A2）= ，因此，

以下通过MATLAB数值模拟和理论分析论证文献[1]中方法是正确的。

1.利用MATLAB仿真随机试验

利用定义计算条件概率，通过缩减样本空间的方式也可以计算条件概率。本文借助MATLAB将并不直观的样本空间以编程的形式呈现出来，从而实现在缩减的样本空间中计算条件概率。

条件概率满足概率的三个公理化条件，因此条件概率也是概率。根据伯努利大数定律可以得到：在取法条件不变的情况下，相互独立地重复试验多次，在第二次抽取到的是男生表的条件下，第一次抽取到的是女生表的频率近似于其概率。

在MATLAB R2014a环境下进行仿真随机实验，利用40次得到的数值结果进行曲线拟合，拟合函数为y=-2.437×10-11x+0.3279，显然，此拟合曲线（如图1）几乎平行与x轴，y轴截距为0.3279，非常接近0.32787.

两次改变女生数据，通过MATLAB模拟出的概率值依然与文献[1]中结果非常接近（见表1），且误差不超过10-3。综上，本文认为文献[1]中方法正确，文献[2]中方法错误。

2.理论分析

文献[2]中方法忽略了“先抽到的一份是男生表的条件下”这个条件，错误地认为取自三个地区的概率仍为，违背了贝叶斯公式，人为地制造出P（A2|A1|H1）这样不存在的概率。

在先抽到的一份是男生表的条件下，经过计算发现报名表来自第一区的概率为

文献[2]中方法产生错误的另一主要原因是利用不存在的概率，错误地使用贝叶斯公式，“当H1发生时，P（ 1|A2）= ”的确切表述应该是“P（ 1H1|A2H1）= ”。

结合上面两种原因，将文献[2]中方法修正如下：

当H1发生时，P（H1|A2）= = = ，P（ 1H1|A2H1）= ；

同理，当H2发生时，P（H2|A2）= ，P（ 1H2|A2H2）= ；当H3发生时，P（H3|A2）= ，P（ 1H3|A2H3）= ；

3.结论

本文利用MATLAB仿真随机试验的方式验证了文献[1]中方法的正确性，通过理论分析指出了文献[2]中方法错误的原因，修正了文献[2]中方法，给出了P（ 1|A2）又一计算公式：

P（ 1|A2）= P（Hi|A2）P（ 1Hi|A2Hi）。

通过对此问题的研究，有助于加深对于条件概率问题的理解，尤其对于全概率公式和贝叶斯公式的掌握具有实际的指导意义。本文方法可以使学生今后避免犯同类错误，对于教师的教学也具有指导意义。

参考文献：

[1]张宇.概率与数理统计（9讲）[M].北京：北京理工大学出版社，2016.

[2] 李永乐，王式安，季文铎. 考研数学复习全书（数学三）[M]. 国家行政学院出版社，2016.

作者简介：

贝叶斯学习篇3

贝叶斯优化算法是利用贝叶斯网络匹配进化种群的优良解集而产生的染色体来体现种群的进化。贝叶斯网络图是一种有向无环图,它由两部分组成:模型结构和条件概率表。网络图中的n个节点X1,X2,…,Xn代表着种群中染色体的n个基因位置。在利用贝叶斯网络对种群进行匹配的过程中,贝叶斯网络结构越复杂,种群的进化信息描述就越完整,进化质量自然越高,但运算速度相对来说却会越慢;相反,贝叶斯网络越简单,算法描述的种群进化信息就越少,进化质量自然越差,但却能够提高算法的运算速度。因此本文给出了简单贝叶斯网络与复杂贝叶斯网络的概念:如果一个贝叶斯网络中,所有的节点至多有一个父节点,称这个贝叶斯网络为简单贝叶斯网络;如果这个贝叶斯网络中存在有多个父节点的节点,称这个网络为复杂贝叶斯网络。相对应的,利用简单贝叶斯网络来匹配进化种群的优化算法称为简单贝叶斯优化算法,利用复杂贝叶斯网络来匹配进化种群的优化算法称为复杂贝叶斯优化算法。

对于贝叶斯网络中的每个节点Xi,∏xi表示Xi的父节点集,在这里由于简单贝叶斯网络中的节点至多有一个父节点,所以∏xi只有一个元素。因此X1,X2,…,Xn的联合概率分布为:

$Ρ (X_{1} ‚ X_{2} ‚ \dots ‚ X_{n}) = \prod_{1}^{n} Ρ (X_{i} | \prod_{x_{i}}) (1)$

对于复杂贝叶斯网络的学习,方法有许多种,像搜索BN结构的贪婪算法[1],三步学习算法[2]等等,这些算法都比较复杂,运算量比较大。而在一些优化过程中利用简单贝叶斯网络进行优化就足够了,没有必要去求复杂的贝叶斯网络。因此本文提出了简单贝叶斯网络的学习算法,这种方法操作简单,运算量少,大大节约了计算机的运行时间。

1 基于BD度量的简单贝叶斯优化学习算法

贝叶斯网络的学习主要包含两个方面:结构学习和条件概率学习。对于进化算法而言,由于种群的优良解集在一定的选择机制确定后,所对应的数据就是学习的样本,所以变量的取值是确定的,即数据是完备的,因此网络图的条件概率学习是比较简单的。相反的,网络图结构学习非常困难,下面本文介绍基于BD度量的简单贝叶斯网络的结构学习算法。为了能够加深对算法的理解,首先介绍BD度量。

1.1 BD度量

贝叶斯度量是指利用贝叶斯规则和先验分布刻画网络结构和参数的不确定。即一个特定网络图的质量是由其匹配与给定数据的边际拟然进行度量。一般而言,计算边际拟然非常困难。为了简化计算,假设条件概率服从狄利克雷分布,以及数据样本具有可加性和完备性、参数具有独立性和模块性、网络结构的拟然等价性和具有结构可能性,于是可得贝叶斯狄利克雷度量,简记为BD度量[1]。

下面定义简单贝叶斯网络中有关节点的BD度量:

定义1:设 X1,X2,…, Xn是n个离散型变量,即对应于种群中的染色体的基因位置。i1,i2,…,ir,…,in是1,2,…,n的一个排列,φ是从整数1≤r≤n到整数ϕ(r)的映射,其中0≤ϕ(r)≤n。对于所有的1≤i≤n,定义:对于任意一个节点Xi,相对于其父节点Xϕ(i)的BD度量为:

$B D (X_{i} \to X_{j}) = \frac{Δ x_{i = 0}^{j = 0}! x_{i = 0}^{j = 1}! x_{i = 1}^{j = 1}! x_{i = 1}^{j = 1}!}{(1 + x_{i = 0})! (1 + x_{i = 1})!} (2)$

对于根节点Xi,定义根节点的父节点为X0

$B D (X_{i}) = B D (X_{0} - X_{i}) = \frac{Δ x_{i = 0}! x_{i = 1}!}{(1 + n)!} (3)$

其中,x $_{i = a}^{j = b}$ 表示在染色体的第i个位置基因取a,第j个位置基因取b的个体数量。

对于由节点X1,X2,…,Xn构成的简单贝叶斯网络,其BD度量定义为:

$B D = (Τ B_{X_{1} X_{2} \dots X_{n}}) = \prod_{r = 1}^{n} B D (X_{ϕ (i_{r})} \to X_{i_{r}}) (4)$

但是,当种群规模相当大时,对于计算机来说,对BD度量的计算会出现溢出现象,为此需要对其进行技术处理,在此本文利用底大于1的对数函数来解决这个问题。首先给出下面引理:

引理1:对于任意两个正数,同时取底大于1的对数后他们的先后顺序不变。

此引理由对数函数的单调性就能得到。

由上面式子可以看出BD度量是大于0小于1的数,去对数后小于0,为了计算方便本文取对数的负值。

以式(2)为例取以a(a>1)为底的对数变为:

$\begin{array}{l} B D (X_{i} \to X_{j}) = - ((\sum_{k = 1}^{x_{i = 0}^{j = 0}} \log_{a}^{k} + \sum_{k = 1}^{x_{i = 0}^{j = 1}} \log_{a}^{k} + \\ \sum_{k = 1}^{x_{i = 1}^{j = 0}} \log_{a}^{k} + \sum_{k = 1}^{x_{i = 1}^{j = 1}} \log_{a}^{k}) - (\sum_{k = 1}^{k = x_{i = 0}} \log_{a}^{k} + \sum_{k = 1}^{k = x_{i = 1}} \log_{a}^{k})) (5) \end{array}$

对于贝叶斯结构学习,结构学习的原则是使简单贝叶斯网络的BD度量值最大,即对于处理过的BD度量去最小值。下面给出了由种群到简单贝叶斯网络的三部结构学习算法:第一步,构造简单贝叶斯网络的初始结构;第二步,判断初始结构中是否存在有向环;第三步,去环得到最终的简单贝叶斯网络图。在下面的操作过程中可以看到,此方法保证了所构造的简单贝叶斯网络的BD度量值最大。

1.2 构造简单贝叶斯网络的初始结构

在构造贝叶斯网络的初始结构之前要做一些准备工作,首先,通过优良种群求出贝叶斯网络中与任意两个节点有关的值x $_{i = a}^{j = b}$ (a,b=0,1),然后由它们求出任意两个节点BD度量,构成一个BD度量矩阵g,其中g(i,j)表示BD(Xi→Xj)。然后开始构造初始结构。

先给出一个引理:

引理2:对于任意两个节点a、b,当|xa=1-xa=0|>|xb=1-xb=0|时,BD(X0→Xa)>BD(X0→Xb)[1]。

由此可以得出,当节点所对应的基因在染色体中取0、1的个数的差值最大时,他的BD度量最大,选取这个节点为简单贝叶斯网络的根节点。

下面确定其他的节点的初始顺序:首先把BD度量矩阵g对角线上的值设置为0,然后令矩阵f=g。在矩阵f中找一个最小的值,记录下它的位置(i,j),对于一个简单贝叶斯网络,任何一个节点至多有一个父节点,所以由网络结构产生的结构矩阵除根节点所在的列全为0外,其他每一列只有一个位置值为1其它为0,然后令矩阵f的这一列值为0。由于贝叶斯网络是有向的,同时令f(j,i)=0。然后再在矩阵f中搜寻最小值,记下它的位置,把这一列值设置为0,再把它的对称位置设置为0。如此续行,直到f=0,得到一组数对,这其中每一个数对(i,j)表示由节点i指向节点j的有向边。这样就得到了简单贝叶斯网络的初始结构。这个结构保证了简单贝叶斯网络的BD度量最大。

1.3 判断初始结构中是否有环

由于简单贝叶斯网络的初始结构是按照BD度量最大求出来的,不能保证这其中没有有向环。由于简单贝叶斯网络中每个节点至多有一个父节点,如果他不在有向环中,一旦把它所有的子节点去掉之后,他就是一个叶结点。因此采用下面方法来搜索有向环,称为层层剥离法。

首先,把初始结构中所有的叶结点删掉,同时记下与他们相关的有向边,这样得到一个新的网络图和一组有向边集A。然后再把新的网络图中的叶结点去掉,记下与他们相关的有向边,把它放在集合A中。如此下去,如果网络结构的初始结构中含有有向环,可以看到,剥离到最后剩下的就是有向环。如果一个简单贝叶斯网络中没有有向环。那么记下的有向边组合起来就是初始贝叶斯网络。

1.4 去环得到最终的简单贝叶斯网络结构

如果从1.1节得到的简单贝叶斯网络结构中含有有向环,在1.2节中已经把这个环给剥离了出来。比较这些有向环中所有有向边对应的BD度量,选择最小的一个边,不妨把它设为(a→b),去掉这个边,记下节点b。然后从根节点开始,依次记下其子节点,可以得到一个结点组成的列B。然后把在这个点列B中的节点和b之间建立有向边,选择BD度量最大的边所对应的节点作为b的父节点,把这条边放入集合A,把节点放入集合B,对剩下的边进行判断,如果剩下边的起点属于集合B,把它放入集合A,把这条边的另一个节点放入集合B,如此续行,可以把节点b所在的换去掉。如果最后还有节点在集合B之外,说明在网络结构中还有有向环存在,按照上面的方法去掉有向环,直到所有有向环去掉为止。

这样就从一个优良种群得到了一个简单贝叶斯网络结构。

2 实例分析

这里给出一个含有41个染色体的优良种群,每个染色体由10个基因组成。

这里求得BD度量矩阵g为:

$g = [\begin{matrix} 44 & 150845043 & 241352070 & 523816809 & 1571450428 & 448985836 & 1346957510 & 1654158345 & 1571450428 & 1346957510 \\ 30 & 636654817 & 210050517 & 1430344000 & 1430344000 & 2184525383 & 1716412800 & 2145516001 & 2184525383 & 1390152516 \\ 37 & 159638393 & 848873090 & 446987501 & 1185885207 & 1660239291 & 2697888848 & 228289025 & 2697888848 & 2697888848 \\ 80 & 1087061440 & 446987501 & 848873090 & 2697888848 & 1630592160 & 1962100980 & 1660239291 & 1630592160 & 968472919 \\ 184 & 1263225547 & 902303962 & 2052741514 & 1130341536 & 631612773 & 2736988686 & 2280823905 & 2736988686 & 676727971 \\ 91 & 1716412800 & 2184525383 & 2145516001 & 1092262691 & 636654817 & 2730656728 & 1092262691 & 546131345 & 2366569164 \\ 173 & 1358826800 & 2248240706 & 1635084150 & 2997654275 & 1729415928 & 102758214 & 1729415928 & 1498827137 & 2113730578 \\ 194 & 1263225547 & 1736935127 & 1263225547 & 2280823905 & 631612773 & 1579031934 & 1130341536 & 2509906295 & 2736988686 \\ 201 & 880429927 & 2248240706 & 1358826800 & 2997654275 & 34588185 & 1498827137 & 2747849752 & 1027583214 & 620815974 \\ 173 & 1729415928 & 2248240706 & 807060766 & 741178254 & 1498827137 & 2113730578 & 2997654275 & 620815974 & 1027583214 \end{matrix}]$

其中, $g (i, j) = \frac{1}{B D (X_{i} \to X_{j}) \times 1000}$

由以上BD度量矩阵可得到简单贝叶斯网络的初始结构为:(3 4),(1 7),(6 8),(2 3),(1 2),(9 6),(10 9),(5 10),(6 5),如图1所示。

由根节点开始,依次记下他们的子节点为{1,7,2,3,4}。当把所有叶结点去掉以后,剩下的就是(1 2)、(2 3)(6 5)、(5 10)、(10 9)、(9 6),然后再在剩下的结构图中去掉叶结点剩下的就是:(1 2)、(6 5)、(5 10)、(10 9)、(9 6),如此下去,最后只剩下(6 5)、(5 10)、(10 9)、(9 6)。

然后去环,通过比较,BD度量最小的有向边是(6 5),取消这个边,在点集{1,7,2,3,4}中,与节点5组成的有向边中,有向边(3 5)的BD度量最大,然后按照第1.3节的方法就得到了与优良种群相匹配的简单贝叶斯网络结构图如图2所示。

通过这个例子可以看到,此算法操作简单,通过简单的几步就可以求出所需的简单贝叶斯网络,与前面提到的几种普通贝叶斯网络结构学习方法相比大大减少了运算速度,具有较高的使用价值。

3 结束语

本文根据贝叶斯网络在解决问题中的一些需要,提出简单贝叶斯优化与复杂贝叶斯优化概念,并在此基础上给出了简单贝叶斯优化过程中由种群到贝叶斯网络结构学习的三步学习算法,该方法简单实用,既保证了优化质量,也提高了运算速度。同时也为研究复杂贝叶斯网络的学习提供了一个参考。

参考文献

[1]杨有龙.基于图形模型的智能优化[D].西安:西北工业大学博士论文,2003.

[2]胡仁兵.动态贝叶斯网络结构学习的研究[D].北京工业大学硕士学位论文,2009.

[3]何宗耀,王刚.一种隐式法的贝叶斯网络结构学习[J].河南师范大学学报:自然科学版,2011(11):150-153.

[4]林士敏,田凤占,陆玉昌.贝叶斯网络的建造及其在数据采掘中的应用[J].清华大学学报:自然科学版,2001,41(1):49-52.

贝叶斯学习篇4

决策者依据先验概率分布及期望值准则进行最优方案的选择。由于先验概率不能完全反映客观规律，所以就必须要补充新信息，修正先验概率，得到后验概率。后验概率是根据概率论中贝叶斯公式进行计算，这就是我们通常所讲的贝叶斯决策模型。

一、贝叶斯风险决策模型

（一）基本理论

贝叶斯决策模型是决策者在考虑成本或收益等经济指标时经常使用的方法。贝叶斯方法是一种广泛运用于系统工程，金融和保险等各个领域的投资决策方法，是一种现代风险型决策法，是统计决策理论的重要分支，贝叶斯决策的理论基础是贝叶斯概率公式。它被运用在对信息掌握不完备或者存在主观判断下的风险型决策方法，风险型决策方法是根据预测各种事件可能发生的先验概率，通过调查、统计分析等方法获得较为准确的情报信息，以修正先验概率，然后再采用期望值标准或最大可能性标准等来选择最佳决策方案。这样使决策逐渐完善，越来越符合实际情况，可以协助决策者做出正确的决策。由于由贝叶斯定理可以推出通过抽样增加信息量能够使概率更加准确，概率准确则意味着决策风险的降低，所以贝叶斯定理保证了该决策模型的科学性。

（二）决策模型的建立

风险决策贝叶斯模型的建立一般分为三个步骤，具体过程如下：

第一步，风险投资者在进行企业项目决策时，最终的目的都是要获得较高的投资收益，而每一个项目方案的收益都取決于诸多风险变量未来的状态，因而风险资本投资决策是一个风险型多指标决策问题。

第二步，构造判断矩阵。决策者以本层次上的因素为准则，两两比较因素Yi、Yj的相对重要程度，给出标度aij，构造一系列判断矩阵A＝（aij），其中，aij>0，aij＝1/aij，aii＝1。

第三步，建立投资决策模型。

二、风险收益函数的贝叶斯决策

决策者面临着几种可能的状态和相应的后果，依据过去的信息或经验去预测每种状态和后果可能出现的概率，在这种情况下，决策者根据确定的决策函数计算出项目在不同状态下的函数值，然后再结合概率求出相应的期望值，然后依此期望值做出决策行为。贝叶斯决策法是最常见的以期望为标准的分析方法。

贝叶斯决策模型是决策者在考虑收益指标时经常使用的方法，以收益型问题为例，其基本思想是在已知不确定性状态变量的概率密度函数f（）的情况下，按照收益的期望值大小对决策方案排序，则最优方案为使期望收益最大的方案。

接下来看一个具体决策实例。某百货商场过去200天关于商品B的日销售量纪录，商品B的进价为200元/件, 售价为600元/件，如果当天销售不完，余下全部报废，求该商品的最佳日订货量a*，及相应的期望收益金额EMV*和EVPI。该商场商品B的销售状态空间为，这些状态发生的概率也可以推测出来。根据此状态空间，决策者的决策空间为。当商场的销售量为，而进货量为时，商场的条件收益为：而相应的期望收益为。

从经济角度看当日订货量等于日销售量时，商场没有因为多定货或少定货而造成的机会损失，因此获得的收益最大，所以此例理论上的最大利润为EPC=2720元。但在实际工作中这个值很难得到，除非商场能够根据情况随时调整进货量，因此商场的经营者往往追求的是期望收益的最大值，在此例中当订货量为7时期望收益最大，EMV*和EVPI分别为2460元和260元。

EVPI的含义为由于情报不准确而造成的商场的赢利损失。为了追求更多的利润，决策者总是希望获取一些准确信高的信息，只要费用小于预期收入，决策者就可以考虑购买由信息公司提供的情报信息。这些信息主要是通过抽样调查或其他途径得到的概率，与凭借经验预测出来的概率不同它们的可靠性更高，这种概率称为后验概率。一般的用后验概率代替先验概率进行贝叶斯决策, 往往可以得到更准确的方案，这种用后验概率代替先验概率再进行贝叶斯决策，就成为后验分析法。需要指出的是有些情况下并非用后验分析法就一定比先验分析好，如果两者选择的方案相同，则意味着后者在增加成本的情况下收益并没有增加，显然此时先验比后验更加有效率。

三、结论

由于在生活中许多自然现象和生产问题难以完全准确预测，因此决策者在采取相应的决策时总会带一定的风险。贝叶斯决策法是将各因素发生某种变动引起结果变动的概率凭统计资料或凭经验主观地假设，再进一步对期望值进行分析，由于此概率并不能证实其客观性，故往往是主观的和人为的概率，本身带一定的风险性和不肯定性。

风险投资中，各风险因素概率分布的获得往往取决于风险决策者的经验和态度，投资风险的分析需要依据大量的信息，而信息的获取是一个渐进的过程。从决策者的主观概率与调查分析的结果取二者之一都是片面和不准确的。而贝叶斯方法正好能将这二者信息结合起来，在决策者及专家的定性判断基础上，根据新信息，对先验概率进行修正，能得出较为准确的结论。当风险投资决策者对先验阶段的估计把握不大时，决策者就可利用这方法决定是否要再做进一步的调查，并对先验概率进行修正，从而减少决策的风险程度。

参考文献：

[1]朱金玲.贝叶斯决策分析及改进.江苏统计应用研究.2000(6).

[2]肖芸茹.论不确定条件下的风险决策.南开经济研究.2003(1).

贝叶斯学习篇5

贝叶斯网络将先验知识与样本信息相结合、依赖关系与概率表示相结合数学模型, 其坚实的理论基础、知识结构的自然表述方式、强大的推理能力使其成为人工智能、数据挖掘等领域处理不确定性问题的主要方法[1]。

经典贝叶斯网络学习的方法都是基于批量数据集学习, 即要把所有的数据集全部读入内存后, 再调用学习算法来对之进行学习, 显然这只适合对内存存储空间要求不高的数据集。在某些数据量较大的应用场合, 就会遇到数据集太大而不能被完全读入内存的情况, 那么针对批量数据集的学习方法就不能应用在这些场合[2]。对于这种情况我们只能对数据分成若干批次来学习, 也就需要增量贝叶斯网络学习方法。

文献[3]提出的增量贝叶斯网络学习策略是:针对当前批次数据的学习产生了一系列候选网络作为下一批数据学习的初始网络, 并且引入了充分统计量对学过的数据集的信息进行存储保留, 每一批数据学习后都为下一批次的学习做了充分的准备。实验结果也表明, 无论是在存储空间的压缩还是在学出的网络质量的方面, 该方法是一种行之有效的方法。但该方法只是在完备数据集下进行增量学习, 在不完备数据集下却并没有展开深入的探讨。

由于诸多原因, 学习贝叶斯网络所用到的数据集存在着不同程度的数据缺失现象[1,4]。实际上对于大规模数据集来说, 数据缺失几乎是一种自然现象。目前, 关于数据缺失情况下学习贝叶斯网的研究主要基于打分—搜索方法。数据缺失导致了两方面问题的出现:一方面, 打分函数不可分解, 不能进行局部搜索;另一方面, 学习贝叶斯网络所需的统计因子不存在, 无法进行直接结构打分。围绕这两个问题, 本文提出了一种新的算法IBN-M, 主要用来解决数据缺失情况下贝叶斯网络的增量学习。

1 数据缺失下贝叶斯网络的增量学习

1.1 贝叶斯网络增量学习的一般策略

最常见的增量学习的一般策略是:将数据分为若干批次来学, 每一批次的学习都要找出一个后验概率最大的网络[3], 作为下一批次数据学习的初始网络。这种算法的优点是每一次的空间开销都比较稳定合理, 因为它只保存当前批的数据, 已经学过的数据完全抛弃。但它的缺点是经过若干次的迭代后, 网络会锁定在某个网络模型上, 丧失对新数据的适应能力。

所以文献[3]引入了用当前学出的最好的网络生成一批候选网络作为下一批数据学习的先验网络, 同时引入了充分统计量来保存学过的数据的信息, 使得网络能保存更多的先验知识, 也使以后学出的网络能与潜在的网络模型拟合得更好一些。每一批数据到来时, 都要用当前批次的数据对充分统计量进行更新。每一次的搜索都要从候选网络中找出一个打分值最高的网络, 依次进行迭代, 直到算法收敛为止。

1.2 数据缺失下贝叶斯网络学习的一般策略

一般情况下对于缺失数据下贝叶斯网络的学习, 通常是把结构化的EM算法 (SEM) [4]引入到贝叶斯网络的学习中, 用来补全数据集中缺失的数据, 该方法称之为SEM数据补全策略。但SEM算法往往由于峰值过多而陷入局部最优, 当数据量缺失较为严重时, 该情况尤为明显[5]。

为了避免学习过程中由于引入SEM算法导致陷入局部最优, 我们将元启发和并行的策略[6,7,8]引入到缺失数据的学习中去, 用并行的启发式搜索算法与SEM算法结合进行网络的求解。通过SEM将数据补充完整后, 我们利用并行的启发式搜索算法提供的较为广阔的搜索空间, 可以大范围地有启发地加大搜索力度, 更好地考察候选网络, 为基于打分—搜索机制等类似算法提供良好支持。刚好弥补了经典算法单一采用SEM+贪婪导致的局部最优的情况[9]。

1.3 增量学习下的打分函数

目前针对贝叶斯网络学习基本上都是建立在打分—搜索机制之上的, 并且对于贝叶斯网络学习的打分函数都是针对于批量数据学习的, 也就是对于不同网络结构的打分我们都是建立在同一个数据集上, 数据集是固定不变的, 但是对于本文的基于大规模数据集下的增量学习来说, 这一条件已经不成立了。因为我们面对的是变化的数据集, 每一批数据的到来我们都要更新数据集, 该情况也就是在不同的时刻、在不同的数据集上对不同的网络结构进行打分。为解决这一问题我们引入平均打分函数[3], 实际上就是用在批量学习上的打分函数除以记录该结点的充分统计量的结点的记录条数, 局部打分函数如下:

其中SK2 (Xi, pa (Xi) ) 是我们常见的批量学习算法中的K2[10]打分函数, ∑xi, pa (xi) N (xi, pa (xi) ) 是指参与对Xi结点K2打分的所有的记录的条数。针对变化的数据集, 该打分的含义实际上就是用平均到记录上的K2打分值来近似批量下数据集的局部分数。

1.4 IBN-M算法

综上, 结合SEM算法和并行化启发式搜索策略的特性, 我们给出数据缺失下贝叶斯网络增量学习算法IBN-M, 算法详细流程如下:

其中Suff (s) ={N^Xi, pa (Xi) :1≤i≤n}是充分统计量, 主要用来保存对数据集的一些统计信息, 此处的统计信息是指每一个结点Xi和它的父亲结点集pa (Xi) 取值的所有组合在原数据集中出现的频数。我们用记录频数的方式来代替存储数据集, 减小了存储空间的开销, 使我们用较少的内存空间就可以来描述整个数据集所反映的信息, 这对于我们在大规模数据集下贝叶斯网络的增量学习来说是至关重要的。F主要是由当前网络中任意两个结点之间添边、减边和逆转边等操作形成的一系列候选网络。算法功能说明如下:第1-3行构建初始网络和与候选网络集F, 以及候选网络的的充分统计量;第5行读入一批k条记录的数据集;第7-11行用SEM算法补全缺失数据, 并用并行化的启发式搜索找出候选网络中打分值较高的网络, 作为下一批数据学习的初始网络;第13-14行更新根据当前的最优网络更新当前的候选网络, 同时更新充分统计量;第16-17行输出最终的网络结构和相关的参数。

1.5 IBN-M算法时间和空间复杂度说明

IBN-M算法采用了SEM来对学习过程中出现的缺失的统计量进行修补。由于EM算法的时间消耗是很大的, SEM算法的时间复杂度为O (Nnqrn) [9], 其中q为数据缺失率, r为节点变量最大属性取值的数目。但是由于采用了并行的启发式搜索使得学习过程能够在更大的搜索空间里寻找最优网络, 避免了局部最优的情况。同时采用并行机制, 共享了打分函数所使用的统计量, 重叠了巨大的工作量, 进而加快了搜索进程, 所以IBN-M算法的时间复杂度得到了一定的控制。从空间消耗情况来看, 由于采用了存储充分统计量这一机制, 使得内存中只保存记录的统计值, 而不保存数据集。并且每一次新数据到来更新充分统计量时, 会添加一些充分统计量, 同时也会去除一部分充分统计量, 所以使得内存的空间消耗趋于一个较为合理稳定的值。不像批量数据学习所导致的空间消耗量随着数据量增长呈线性增加。

2 实验结果分析

本文实验采用的硬件环境是IBM-p550并行计算机, 程序的运行环境为Linux下的gcc。文中应用到的ALARM训练数据集和测试数据集是根据http://www.norsys.com提供的ALARM网概率分布图生成的, 包含了10组实验数据集, 每组实验数据集包含1个10000条记录的训练数据集和1个1000条记录的测试数据集, 所有训练数据集都随机产生了10%和20%的缺失数据。实验的结果是在10组数据集下测试的平均值。本文使用标准网络的logloss与学出网络的logloss的差值来衡量学出网络质量的好坏, 差值越小, 表明学出的网络越精确。本节通过实验对批量学习算法和IBN-M增量学习算法学出的网络进行比较和分析。

图1表示批量学习算法和IBN-M算法的内存消耗情况, 其中横坐标表示数据集的记录条数, 纵坐标表示学习过程中所消耗的内存空间, k=1000和2000分别表示IBN-M算法学习过程中每批次数据的记录条数。从图1中我们可以看出, 随着数据集记录条数的增加, IBN-M算法的空间开销趋于稳定, 而且内存的消耗量也比较合理, 这说明该算法有用绝对的存储空间优势, 这也解决了增量学习贝叶斯网络的瓶颈问题。IBN-M算法的存储空间开销实际上也就是刚开始构造的存储充分统计量的结构体所占用的空间开销, 每一批次数据集学习完成以后, 都要从内存中删除一部分充分统计量或者添加一部分充分统计量, 所以在后续的学习过程中存储开销基本上趋于稳定。然而批量学习由于要保存从开始到当前所有的数据集, 致使内存消耗量随着数据记录的增多而急剧增大。

图2描述了批量学习算法和IBN-M算法学出的网络对测试集的数据拟合情况, 其中的横坐标表示数据集的记录条数, 纵坐标表示学出网络的logloss与标准网络logloss的差值。从图2我们可以看出随着实验数据记录的增加, 两种算法学出的网络都越来越趋近于标准网络。相比之下批量学习算法收敛得更快一点, 主要是因为批量学习算法保存了迄今为止所有的观测数据, 能充分利用所有数据信息进行网络学习。但它致命的缺点就是内存消耗量太大, 随着实验数据记录条数的增多, 内存空间的消耗量呈线性增加的趋势, 这一点是大规模数据集下贝叶斯网络学习所不能忍受的。然而本文提出的算法却恰恰弥补了这一缺点, 与批量学习不同的是本文算法不是保存数据集, 而是只保存数据集充分统计量。这样虽然开始学出的网络质量不如批量学出的精确, 但是随着数据记录条数的增多, 学出网络的质量越来越趋近于批量, 这也验证了IBN-M算法的学习能力。

另外从图2中可以看出在数据缺失10%和20%情况下, 随着数据记录条数的增多, IBN-M学出网络的logloss与标准网络的logloss的差值在逐渐减小, 在程序运行结束时与标准网络的logloss差值相差很小 (只有0.2左右) , 这说明在数据缺失的情况下, IBN-M确实能够学出相对较好的网络。在图2中我们还可以看出在缺失数据分别为10%和20%两种情况下IBN-M算法最后学出网络的质量差不多, 只不过相比较而言10%的情况下收敛得更快一点, 20%的情况下较慢一点。主要是因为刚开始由于数据缺失较大的情况下统计信息缺失较大, 导致学出的网络质量不好, 随着数据记录条数的增多对缺失数据的修复逐渐准确起来, 网络的质量也逐渐变好。同时我们也可以看到, IBN-M算法中k值的大小也影响学出网络的精度。当k值较小时, 由于数据记录较少不能很好地反映统计规律[5], 所以学出的网络质量要逊色k值较大情况下学出网络的质量。这就告诉我们要在内存空间容许的范围之内, 尽可能大地设置k的值, 以便学出的网络能与实际的网络模型较好地拟合。

3 结束语

本文提出的IBN-M算法是对经典的增量学习算法在缺失数据上贝叶斯网络学习的一个重要的补充。该算法既能利用SEM算法进行缺失数据的修复, 又能利用并行的启发式算法扩大搜索空间, 避免陷入局部极值, 同时并行的策略也加快了搜索的速度, 弥补了引入EM算法导致的算法效率低下这一缺点。从实验的结果我们可以看到IBN-M算法确实能在数据缺失的情况下学出相对精确的网络模型来, 随着在增量学习过程中数据量的逐渐增多, IBN-M算法学出的网络越来越趋近于批量学习所学出的网络模型。能在存储空间消耗较少的情况下学出与批量学习算法相当的网络质量, 说明了IBN-M算法是处理缺失数据下贝叶斯网络学习的一种有效的算法。本文方法已经成功地应用于一个实际的大规模网络日志挖掘系统中[2]。

由于在存储历史数据统计信息方面, IBN-M算法仍然抛弃了一部分数据的信息, 这部分抛弃的信息也会对学出网络的质量造成影响。未来的工作之一就是选取一种好的存储结构来完整保存数据集的历史信息, 其实这样做也是为了解决增量学习的关键问题;另外也要对打分函数进行改造, 毕竟在基于打分—搜索机制的贝叶斯网络学习过程中, 充分地利用先验知识进行打分在我们增量学习的情形下, 显得更加自然。

参考文献

[1]张连文, 郭海鹏.贝叶斯网络引论[M].北京:科学出版社, 2007.

[2]Chen Jiamin, Lv Qiang.Network log mining by Bayesian network[C]//2008Proceedings of Information Technology and Environmental System Sciences, 2008:239242.

[3]Friedman N, Goldzmidt M, Wyner A.Sequential Update of Bayesian Network Structure[C]//Proc.UAI, 1997.

[4]Friedman N.Learning belief networks in the presence of missing values and hidden variables[C]//Proc.of the14th Int'l Conf.on Machine Learning.San Francisco:Morgan Kaufmann Publishers, 1997:125133.

[5]田凤占, 黄丽.包含隐变量的贝叶斯网络增量学习方法[J].电子学报, 2005 (11) :19251928.

[6]Campos L M de, Fernadez-Luna J M, Gamez J A, et al.Ant colony opti-mization for learning Bayesian networks.Int.J.Approx.Reasoning, 2002, 31 (3) :291311.

[7]潘吉斯, 吕强, 王红玲.一种并行蚁群Bayesian网络学习的算法[J].小型微型机计算机系统, 2007 (4) :651655.

[8]吕强, 高彦明, 钱培德.共享信息素矩阵:一种新的并行ACO方法[J].自动化学报, 2007 (33) :418421。

[9]廖学清, 吕强, 单冬冬.数据缺失下学习贝叶斯网的一种有效SEM算法[J].计算机工程, 2009 (8) .

贝叶斯学习篇6

Win32环境下,反病毒工程师借助逆向工程和调试技术,通过分析可疑程序API及参数调用情况,依据经验判断上报的可疑样本是否为病毒。随着商业利益的驱动和病毒制作技术的普及,病毒种类和数量都在迅速增加,这给传统的人工分析手段带来了巨大的压力。鉴于此,本文实现一个病毒上报分析系统用于可疑样本的自动化分析和检测。在上报分析检测中,样本数据通常是分批获取,随着新样本的出现,需对分类模型进行增量学习,以对模型参数进行调整。贝叶斯方法由于其充分利用先验知识的特性,使之成为增量学习的自然选择。文献[1,2]从当前分类损失的角度探讨了增量贝叶斯模型中学习序列算法的问题。本文从优先学习的样本被正确分类概率大小的角度对学习序列算法的问题进行了探讨,利用分类器对已知类别样本的检测结果的先验知识,提出了一种基于样本分类结果可信度的朴素贝叶斯增量学习序列算法。

1 病毒上报分析系统模型

系统模块结构如图1所示。系统由可疑样本上报模块、样本入库模块、自动化行为分析模块、增量学习模块和病毒检测模块组成。可疑样本上报模块为Internet用户提供可疑样本上传的Web服务,并将样本运行时的具体行为和检测结果通过邮件以Xml形式反馈给用户。样本入库模块用于大规模样本的集中入库。自动化行为分析模块为系统核心模块,用于分析样本进程运行时所加载的系统DLL,并根据事先定义的恶意行为来对特定API进行监控。增量学习模块用于新样本入库时,检测模型的学习和分类器参数的调整,其包括已知样本类型和未知样本类型的增量学习。病毒检测模块对上报样本进行检测并给出检测结果,用户也可以根据系统返回的样本具体行为,依据自身经验对样本性质进行判断。

2 病毒特征定义

API作为操作系统为应用程序提供的服务接口,完成对网络、文件系统和其它重要系统资源的访问。通过跟踪病毒程序的API调用,可以掌握其具体的操作行为。文献[3,4]通过API来描述病毒行为用于病毒的检测,但仅使用API并不能准确描述一个恶意行为。同一个API调用,其危险性随着其参数的不同而不同。拷贝一个可执行文件到系统敏感目录相对拷贝一个文本文件到用户目录的潜在危险性要高得多。因此本文采用API与参数相结合的方式来描述恶意行为,并依据专家经验定义了一个35维的特征向量,其每一维代表一种恶意行为事件,该事件由相应的API及其参数表示,仅当程序调用的API和参数均满足条件时,我们才认为发生了该行为事件。表1给出部分行为事件的定义。

3 朴素贝叶斯及其增量推理

朴素贝叶斯分类算法的基础是贝叶斯定理。在处理大规模数据时,贝叶斯分类算法表现出较高的分类准确性和运算性能,加之其充分利用先验信息的特性,使之成为增量学习中的最佳选择模型。

为便于表述,文中病毒统称为黑样本,正常程序统称为白样本。对于样本空间的每一个样本可以看作是n维空间的一个点X=(x1,x2,…,xn),其中x1,x2,…,xn分别为行为事件属性A1,A2,…,An的取值;xn∈{0,1},取值为1时表示该事件发生,0则表示未发生。D为样本类别属性,D={d0,d1}, d1表示黑样本,d0表示白样本。依据朴素贝叶斯定理,病毒检测判别式表示为:

$C (X) = \underset{d}{\arg} \max (\frac{p (d) p (x | d)}{p (x)})$

根据朴素贝叶斯理论各条件属性相互独立的基本假设和p(x)在判别式中对具体样本而言为常数,判别式可简化为:

$C (X) = \underset{d}{\arg} \max (p (d) \prod_{i = 1}^{n} p (x_{i} | d)) (1)$

在无信息Dirichlet共轭先验假设条件下[5],p(di)的计算公式方法为:

$p (d_{i}) = \frac{1 + c o u n t (d_{i})}{| D | + | Τ |} (2)$

$p (x_{i} | d_{i}) = \frac{1 + c o u n t (d_{i} \land x_{i})}{| A_{i} | + c o u n t (d_{i})} (3)$

其中,count(di)为训练样本中样本类别为di的样本数;|D|为样本类别个数;|T|为训练样本总数;count(di∧xi)表示样本类别为di且属性Ai取值为xi的样本数;|Ai|为属性Ai的取值个数。

增量学习的任务之一是:当新增学习样本集T′={X′1,X′2,…,X′n}时,分类器参数的调整。

对于已知类别的学习样本,根据共轭Dirichlet分布,得到参数的重新估计为:

$p^{'} (d_{i}) = \frac{1 + c o u n t (d_{i}) + c o u n t^{'} (d_{i})}{| D | + | Τ | + | Τ^{'} |} (4)$

$p^{'} (x_{i} | d_{i}) = \frac{1 + c o u n t (d_{i} \land x_{i}) + c o u n t^{'} (d_{i} \land x_{i})}{| A_{i} | + c o u n t (d_{i}) + c o u n t^{'} (d_{i})} (5)$

其中,count′(di)表示新增样本集中样本类别为di的样本数。

对于未知类别的学习样本,需用现有的分类器对其进行分类,同时按照一定的学习序列对这些样本进行学习,每加入一个样本X′=(x′1,x′2,…,x′n)时,其参数的重新估计为:

$p^{'} (d_{i}) = {\begin{cases} \frac{δ}{1 + δ} p^{'} (d_{i}) C (X^{'}) \neq d_{i} \\ \frac{δ}{1 + δ} p^{'} (d_{i}) + \frac{1}{1 + δ} C (X^{'}) = d_{i} \end{cases} (6)$

其中δ=|D|+|T|。

$p^{'} (x_{i} | d_{i}) = {\begin{cases} \frac{ζ}{ζ + 1} p^{'} (x_{i} | d_{i}) C (X^{'}) = d_{i} & x_{i} \neq x^{'}_{i} \\ \frac{ζ}{ζ + 1} p^{'} (x_{i} | d_{i}) + \frac{1}{ζ + 1} C (X^{'}) = d_{i} & x_{i} = x^{'}_{i} \\ p^{'} (x_{i} | d_{i}) C (X^{'}) \neq d_{i} \end{cases} (7)$

其中ζ=|Ai|+count(di)。

4基于分类结果可信度的未知类别样本增量学习

基于分类结果可信度的未知类别样本增量学习的基本思想为:充分利用分类器对已知类别样本检测结果的统计特性,将分类结果正确概率大的样本优先加入原样本集合,使得优先学习的样本尽可能为正确分类的样本。其实现过程主要分为两步。

1) 事件数排序

事件数为样本发生不同行为事件的次数。不同事件数下,样本分类结果与其实际类别一致的概率往往不同,即分类结果的可信度不同。事件数越大,样本恶意行为越明显,样本判定为黑样本且其实际为黑样本的概率也越大,即样本分类结果为黑的可信度越大。事件数排序就是根据不同事件数下分类结果可信度的大小,对事件数进行排序,将可信度大的事件数下的样本优先进行学习。文中分别使用PBi和PWi来衡量不同事件数下样本分类结果为黑和白的可信度:

$Ρ B_{i} = \frac{c o u n t (d_{1} \land E v n = i) \times Τ Ρ F_{i}}{c o u n t (d_{1} \land E v n = i) \times Τ Ρ F_{i} + c o u n t (d_{0} \land E v n = i) \times F Ρ F_{i}} (8)$

$Ρ W_{i} = \frac{c o u n t (d_{0} \land E v n = i) \times Τ Ν F_{i}}{c o u n t (d_{1} \land E v n = i) \times F Ν F_{i} + c o u n t (d_{0} \land E v n = i) \times Τ Ν F_{i}} (9)$

其中Evn表示样本发生行为事件的个数;count(d1∧Evn=i)为某已知类型样本集合中事件数为i的黑样本数;TPFi为模型对该集合中事件数为i的样本的检出率,表示为该集合事件数为i的黑样本中正确检测为黑样本的样本比例;FPFi为误报率,表示该集合事件数为i的白样本中误报为黑样本的样本比例;TNFi为真阴性率,表示该集合事件数为i的白样本中正确检测为白样本的样本比例,TNFi=1-FPFi;FNFi为假阴性率,表示该集合事件数为i的黑样本中检测为白样本的样本比例,FNFi=1-TPFi。PBi值越大,事件数Evn=i下的样本判定为黑的可信度越大;PWi值越大,事件数Evn=i下的样本判定为白的可信度越大。

以下举例说明如何根据分类器对已知类别样本集分类结果的统计特性对事件数进行排序。样本集L按事件数划分为L={L0,L1,…,Ln},n为事件数,Ln表示发生事件数为n的样本集合。分类器对该集合不同事件数下样本的检出率和误报率如表2所示,为便于计算,不同事件数下的黑白样本个数均取100。

事件数Evn=1时的可信度计算:

$\begin{array}{l} Ρ B_{1} = \frac{100 \times 100 %}{100 \times 100 % + 100 \times 30 %} \times 100 % = 76.92 % \\ Ρ W_{1} = \frac{100 \times (1 - 30 %)}{100 \times (1 - 100 %) + 100 \times (1 - 30 %)} \times 100 % = 100 % \end{array}$

同理可得到其它事件数下样本分类结果的可信度。由表2中的PBi,PWi分别得到分类结果为黑和白的事件数序列<L2,L3,L1>和<L1,L3,L2>。在未知类别样本的增量学习过程中,对于判定结果为黑的样本,按序列<L2,L3,L1>进行学习,即事件数为2的样本优先进行学习;对于判定结果为白的样本,按序列<L1,L3,L2>进行学习,即事件数为1的样本优先学习。

2) 同一事件数下的样本排序

同一事件数下的样本按照PD值降序排序,PD值大的样本将优先进行学习。

$Ρ D (X) = {\begin{cases} \frac{p (d_{0}) \prod_{i = 1}^{n} p (x_{i} | d_{0})}{p (d_{1}) \prod_{i = 1}^{n} p (x_{i} | d_{1})} C (X) = d_{0} \\ \frac{p (d_{1}) \prod_{i = 1}^{n} p (x_{i} | d_{1})}{p (d_{0}) \prod_{i = 1}^{n} p (x_{i} | d_{0})} C (X) = d_{1} \end{cases} (10)$

可信度增量学习算法描述如下:

输入:训练集T={<X1,C1>,<X2,C2>,…,<Xn,Cn>},其中Cn是Xn的类别;学习集L={X′1,X′2,…,X′n}。

输出:分类器C。

(1) 在训练集T的基础上生成分类器C;

(2) 对训练集T进行分类和统计,生成黑白样本事件数序列E_blist=<Evnp,Evng,…,Evnb>E_wlist=<Evns,Evnt,…,Evnw>;

(3) 若L=ϕ,返回,算法结束,否则继续;

(4) 利用公式(1)对测试集L进行分类,获取类别标签;

(5) 根据E_blist,E_wlist和PD(Xn)对(4)中分类结果进行排序,生成黑白样本加入序列:

blist=<X′p,X′g…,X′b>

wlist=<X′s,X′t…,X′w>;

6) 将学习样本blist[1]和wlist[1]加入训练集T,T=T+{<blist[1],C(blist[1])>,<wlist[1],C(wlist[1])>},L=L-{blist[1],wlist[1]},并依据公式(6)和(7)更新分类器参数,转向(2)。

5 实验设计及结果

5.1 数据集描述

文中所有实验样本均为PE结构的可执行程序。实验中黑白样本均由哈尔滨安天实验室提供。白样本选择上报可疑样本中最终判定为正常可执行程序的样本,这类样本大多因具有疑似病毒行为特征而被上报,但实际上仍然属于合法的正常程序。用这类白样本建模,更加符合上报分析的真实环境,使得检测模型更具实用性。

为保证数据建模的合理性,对原始黑白样本进行以下处理:

1) 依据病毒命名规则去掉黑样本中病毒的近似变种,以避免黑样本中存在过多来自同一病毒的变种,使得训练后的分类器带有倾向性。

2) 依据MD5值去掉白样本中的重复样本。

另从初步的实验结果来看,对于发生事件数1和2的黑白样本,由于样本事件数较少且发生的事件相似,模型对其区分效果不佳。因此本文仅对发生事件数大于2的样本进行实验。最终获取的试验数据集由1854个黑样本(恶意可执行程序)和1510个白样本(正常可执行程序)组成。

5.2 实验结果

黑白样本中分别随机选取1460和1189个样本作为初始训练集T,余下394和321个样本看作无标签的增量学习集L。表3为随机增量学习和可信度增量学习后的检测模型对初始测试集和初始训练集的检测效果。

从表3中可以看出,基于可信度增量学习后的检测模型对初始测试集和初始训练集的检测正确率均有所提高,虽检出率有所下降,但误报率有着较为明显的改善。

表4为基于两种方法学习样本选入正确率的比较。学习集整体选入正确率为原始学习集L中被正确标记选入的样本所占比例。从表中可以看出,基于可信度增量学习的黑白样本选入正确率和总体选入正确率较随机增量学习均有所提高。

6 结论

对于未知类别样本的增量学习,其主要工作是寻找样本加入原有样本集合的学习序列。本文从优先学习的样本被正确分类并选入的角度对学习序列算法进行了探讨,利用分类器对已知类别样本的检测结果的先验知识,提出了一种基于样本分类结果可信度的朴素贝叶斯增量学习序列算法,使得优先学习的样本尽可能为正确分类的样本。实验结果表明,经该算法增量学习后的分类器检测效果优于随机增量学习,另学习样本的选入正确率也优于随机增量学习。本文今后的工作将关注以下两个方面:增加特征向量维数,定义更多在病毒和正常程序中具有区分能力的行为特征,使得程序在理论上能被捕获到更多的事件,增加模型可检测样本范围;另一方面,未知样本增量学习中,如何控制原有分类器误差的累积和传递也是今后研究的方向。

参考文献

[1]宫秀军,刘少辉,史忠植.一种增量贝叶斯分类模型[J].计算机学报,2002,25(6):645-650.

[2]姜卯生,王浩,姚宏亮.朴素贝叶斯分类器增量学习序列算法研究[J].计算机工程与应用,2004(14):57-59.

[3]Xu J Y,Sung A H,Chavez P,et al.Polymorphic Malicious ExecutableScanner by API Sequence Analysis[C]//Proceedings of the Fourth In-ternational Conference on Hybrid Intelligent Systems.IEEE ComputerSociety,2004:378-383.

[4]张波云,殷建平,蒿敬波,等.基于多重朴素贝叶斯算法的未知病毒检测[J].计算机工程,2006,32(10):18-21.

贝叶斯学习篇7

贝叶斯网络是20世纪80年代在简单贝叶斯的基础上发展起来的一种新的信息推理方法。同时它也是一种有向无环图,适用于表达与分析不确定性和概率性的事物,因为它是基于概率分析、图论的一种不确定性知识的表达和推理的模型,且同时是一种将因果知识与概率知识相结合的信息表示的框架,故也被称为信念网络。

贝叶斯网络的学习包括两部分:结构学习与参数学习两部分,贝叶斯网络学习的核心问题是结构的学习[1]。目前,现有的贝叶斯网络的结构学习方法可以分成两大类[2]:一类是基于依赖分析的学习方法。它在一些假设下学习效率较高,且能获得全局最优结构,但是它的过程比较复杂。又因为冗余边的检验通常是在确定边的方向之前进行的,这样就导致了大量的高维条件概率的计算,由于这些问题的存在就导致了学习准确性与效率的降低。另一类就是基于打分-搜索的学习方法。它的过程简单规范,只适用于变量少或者在一定范围之内的结构学习。此方法由于搜索空间大,一般是结点有序等诸多的原因,从而导致了学习的效率的降低,且容易陷入局部最优解。

受文献[3]中提出的基于互信息贝叶斯网络结构学习算法的启发,文章提出了一个改进的贝叶斯网络结构学习分类模型,整个算法的核心仍然是相应的贝叶斯网络结构的确定。在该算法中,使用交叉熵这个概念作为判断弧的方向的依据,并且利用环路检验来保证图中不会出现回路,而后利用最小切割集来对已有的图进行相应调整,以此来构造一个与数据具有更好拟合性的贝叶斯网络结构。最后根据该结构和文献[4]中Judea Pearl给出的定理来最终确定一个分类模型。文章把整个算法应用到质量管理数据集中进行了实验,并与基于互信息的贝叶斯网络结构学习算法[3]进行了实验对比和性能分析,结构表明了该算法具有更高的精确性和时效性。

1 贝叶斯网络简述

贝叶斯网络是一个有向无环图(DAG),它可以表示为一个三元组G=(N,E,P)。其中N={x1,x2,…,xn}是一组结点的集合,每个结点代表一个变量(属性)。E={<xi,xj>|xi≠xj,xi,xj∈N}是一组有向边的集合,每条边<xi,xj>表示xi,xj具有依赖关系xi→xj。P={p(xi|πi)}是一组条件概率的集合,其中p(xi|πi)表示xi的父结点集πi对xi的影响。

设某系统的结点集合N={x1,x2,…,xn},由联合概率公式表示:

$p (x_{1}, x_{2}, \dots, x_{n}) = \prod_{i = 1}^{n} p (x_{i} | x_{1}, x_{2}, \dots, x_{i - 1}) (1)$

现在假如对每个结点xi,已知存在某个子集πi⊆{x1,x2,…,xi-1},在给出πi时,xi和{x1,x2,…,xi-1}-πi是条件独立的,即有:

p(xi|x1,x2,…,xi-1)=p(xi|πi) (2)

由式(2)、式(1)可等价为:

$p (x_{1}, x_{2}, \dots, x_{n}) = \prod_{i = 1}^{n} p (x_{i} | π_{i}) (3)$

由式(3)可知,贝叶斯网络实质上就是一个联合概率分布p(x1,x2,…,xn)所有条件独立性的图形化表示,其中πi为xi父亲结点集[5]。

贝叶斯网络结构的学习一般分为以下三个步骤:(1) 确定变量集和变量域;(2) 确定网络结构;(3) 确定局部概率分布。其中确定网络结构有如下三种方法:(1) 根据变量之间的条件独立性确定弧的存在性,根据变量之间条件相对预测能力(或条件相对互信息)确定弧的方向;(2) 用户根据变量之间的因果关系(根据用户的已有知识)来建立网络结构;(3) 结合前两种方法混合使用。

2 信息论基础

从信息论的角度来看,信息就是用来消除不确定性的事物。而对信息不确定性知识的一种度量的就是信息熵。消息被称为信息的载体,信源被称为含有信息的消息集合,信源提供的整个信息的总体度量被称为信源的信息熵。所以如果信源的信息熵越小,则消息消除的不确定性就将越大,则表明信息间的相互依赖性就会越大;反之信息间的相互独立性将会越大。关于“互信息”的定义及特性在文献[3]中给出了介绍。下面给出“交叉熵”[6]及“联合鉴别信息”的具体定义:

定义1 (交叉熵) 假设{a1,a2,…,an}为属性X的值,通常X的分布和假设H1与假设H2有关。当在假设H1下,

$(\begin{array}{l} X \\ Ρ_{1} (x) \end{array}) = [\begin{matrix} a_{1} & a_{2} & \dots & a_{k} \\ Ρ_{1} (a_{1}) & Ρ_{1} (a_{2}) & \dots & Ρ_{1} (a_{k}) \end{matrix}]$

为X的概率分布;然而当在假设H2下,

$(\begin{array}{l} X \\ Ρ_{2} (x) \end{array}) = [\begin{matrix} a_{1} & a_{2} & \dots & a_{k} \\ Ρ_{2} (a_{1}) & Ρ_{2} (a_{2}) & \dots & Ρ_{2} (a_{k}) \end{matrix}]$

为X的概率分布。设p(H2)为H2的概率,且p(H1)为H1的概率,则存在条件概论公式为:

$p (Η_{1} | a_{k}) = \frac{p (Η_{1}) p (a_{k} | Η_{1})}{p (Η_{1}) p (a_{k} | Η_{1}) + p (Η_{2}) p (a_{k} | Η_{2})} (4)$

$p (Η_{2} | a_{k}) = \frac{p (Η_{2}) p (a_{k} | Η_{2})}{p (Η_{1}) p (a_{k} | Η_{1}) + p (Η_{2}) p (a_{k} | Η_{2})} (5)$

通过式(4)与式(5)可以得出:

$\lg \frac{p (a_{k} | Η_{2})}{p (a_{k} | Η_{1})} = \lg \frac{p (Η_{2} | a_{k})}{p (Η_{1} | a_{k})} - \lg \frac{p (Η_{2})}{p (Η_{1})}$ ,当ak取X且存在着鉴别假设H2与H1时,则倾向H2的信息量为 $\lg \frac{p (a_{k} | Η_{2})}{p (a_{k} | Η_{1})}$ 。在假设H2下 $\lg \frac{p (a_{k} | Η_{2})}{p (a_{k} | Η_{1})}$ 的鉴别信息值或数学期望值为I(p1,p1; $X) = \sum_{k = 1}^{Κ} p_{2} (a_{k}) \lg \frac{p_{2} (a_{k})}{p_{1} (a_{k})}$ 。在信息论当中,鉴别信息又叫方向散度,故它是有方向的。

定义2 (联合鉴别信息) 假设存在Xi,Xj两个离散随机变量,它们的取值分别为:

Xi:{xi1,xi2…,xim}

Xj:{xj1,xj2…,xjm}

再假设H1与H2下,Xi的联合概率分布为p1(xim,xjn),且Xj的联合概率分布为p2(xim,xjn)。其中m=1,2,…,M,n=1,2,…,N。则公式:

I(p2,p1; $X_{i}, X_{j}) = \sum_{m = 1}^{Μ} \sum_{n = 1}^{Ν} p_{2} (x_{i m}, x_{j n}) \log \frac{p_{2} (x_{i m}, x_{j n})}{p_{1} (x_{i m}, x_{j n})} (6)$

为随机变量Xi与Xj的联合鉴别信息。

在上面提到过可以使用鉴别信息来定向,在这里将给出具体的定向过程,如下:

在网络中任意选择一对有弧连接的节点Xi,Xj,用式(6)计算联合鉴别信息。同时可把假设H1与H2分别看作是Xi→Xj与Xi←Xj这样两种情况。在这里箭头的方向就是表示两个节点之间弧的方向,则式(6)可相应地转化为:

I(p1,p2; $X_{i}, X_{j}) = \sum_{m = 1}^{Μ} \sum_{n = 1}^{Ν} p (X_{i}) p (X_{j} | X_{i}) \log \frac{p (X_{i}) p (X_{j} | X_{i})}{p (X_{j}) p (X_{i} | X_{j})}$

I(p2,p1; $X_{i}, X_{j}) = \sum_{m = 1}^{Μ} \sum_{n = 1}^{Ν} p (X_{j}) p (X_{i} | X_{j}) \log \frac{p (X_{j}) p (X_{i} | X_{j})}{p (X_{i}) p (X_{j} | X_{i})}$

定理1 如果I(p1,p2;Xi,Xj)>I(p2,p1;Xi,Xj),则定向为Xi→Xj,否则为Xi←Xj。

3 改进的贝叶斯网络结构学习算法

3.1 相关概念

概念1 (D分离) 在有向无环图G中,设U存在三个不相交的子集分别为X,Y与Z,如果从属于X中一个节点到属于Y中的一个节点的所有路径之间,存在节点M满足以下条件之一:

(1)M属于Z中,且M不是一个汇聚节点;

(2)M或任何M的子节点都不属于Z,且M是一个汇聚节点,则称X与Y对于Z为D分离,记为<X|Z|Y>G[7]。

概念2 (邻接路径) 指的是在不考虑边方向的情况下,连接两结点之间的路径。

概念3 (碰撞结点) 任意一个结点x,如果有两个结点都指向它,则称结点x为碰撞结点或者是汇聚结点。

概念4 (开放路径) 指的是在两结点之间,构成的无向路径上所有的结点都是活跃的,则称这样的路径为开放路径。

概念5 (闭路路径) 指的是在两结点之间,构成的无向路径上所有的结点都是不活跃的,则称这样的路径为闭路路径。

概念6 (割集) 在一个图G中,存在着一个结点集S能D分离X与Y,则称S为X与Y的割集[8]。

割集是一个很重要的概念,要通过它来确定最小切割集。而算法中有用到最小割集,下面是确定最小切割集的算法:

(1) 令D(xi,xj)为结点xi与结点xj 的切割集,并将结点xi到结点xj的路径放入集合Si,j中。

(2) 将从结点xi到结点xj且将经过x $_{i}^{j}$ ,j=1,…,r的非碰撞路径放入集合Si,j 中。

(3) 在Si,j中,设有路径都经过同一个结点x,将结点x放入D中,则从Si,j中删除经过结点x的所有路径。

(4) 重复(3),直到遍历整个Si,j中的路径。

(5) 设结点∏xi能阻塞最多的路径,则将结点∏xi放入D中,同时移除经过该结点的所有路径。

(6) 重复以上的步骤,直至Si,j为空。

改进的贝叶斯网络结构学习分类模型算法中引用了鉴别信息来确定弧的方向,因为鉴别信息的应用还不是很广泛,因此对扩大信息论理论知识的用途有很重要的意义。

为了更加准确地找出贝叶斯网络的分类模型,算法还使用了环路检验,最后算法用最小切割集作为条件来检测两结点的弧是否是多余的。算法大致分为三步:第一步是构建无向图,通过利用条件互信息来确定属性结点的顺序;第二步是构建有向图,其中利用鉴别信息来确定边的方向,并使用了环路检验来提高结构学习的准确性;第三步利用最小切割集来调整图的结构。

3.2 算法步骤描述

第一步:构建无向图

(1) 设一个数据集D有N个变量{X1,X2,…,Xn},所建立的无向图为P={<Xi,Xj>},其中i,j=1,2,…,n,且i≠j。

(2) 设N为属性全集,Xi,Xj∈U(i,j=1,2,…,n),Xi≠Xj,且Ck(i=1,2,…,n)∈C,其中Ck是类属性集。计算I(Xi,Yj|Ck)的值,并按条件互信息的值进行非递增进行排列,并依次放入集合S中。

(3) 在集合S中,依次计算属性对中的互信息。如果I(Xm,Xq)≤ε1(m,q=1,2,…,n),将属性对(Xm,Xq)从E中放入集合R中,否则在(Xm,Xq)中增加相应的弧。

(4) 返回(3),遍历集合E中的结点对。

第二步:构建有向图

(1) 对于在集合E中的每一对结点(xi,xj)∈E,假设(xi→xj)的概率是p1且(xi←xj)的概率是p2,则计算它们的交叉熵I(p1,p2;xi,xj)和I(p2,p1;xj,xi)。

(2) 如果I(p1,p2;xi,xj)> I(p2,p1;xj,xi),且两结点之间没有形成开放路径,则两结点的方向为(xi→xj)。否则为(xi←xj)。

(3) 重复上面的过程,直到遍历集合E中的每一对结点对。

第三步:调整图的结构(增加和删除)

增加:通过切割集来判断。

删除:冗余检验。删除不必要的边。

(1) 取E中的一条边(xe,xf),并找出两结点的割集D(xe,xf)。

(2) 计算条件互信息I(xe,xf|D(xe,xf))。如果I(xe,xf|D(xe,xf))<ε3,则将边(xe,xf)从E中删除。否则保留此边。

(3) 重复上面的步骤,直到遍历整个E。

3.3 算法主要伪代码

Input: 数据训练集D,非类属性集X,类属性C,阈值ε1,ε2。

Output: 贝叶斯网络图P*。

/*调用数据离散化方法*/

Discretize(D);

/* 构造无向图P */

FOR i FROM 1 To n /*其中n是非类属性的属性个数*/

FOR j FROM i+1 to n

Calculate I(Xi,Yj|C);

S=S∪{<Xi,Xj>};

Order by the value of I(Xi,Yj|C)

ASC in S;

If I(Xm,Xq)≤ε1(m,q=1,2,…,n)

S=S-{<Xi,Xj>};

R=R∪{<Xi,Xj>};

Else

S=S∪{<Xi-Xj>};

END IF

END FOR;

FOR k FROM 1 TOm /*其中m是类属性的属性个数*/

IF I(Xi,Ck)>ε1

S=S∪{<Cj-Xi>};

END IF;

END FOR;

/*将无向图转变为有向图P**/

E=E-{<C-X>}

E=E∪{<C→X>}

FOR i FROM 1 TO n-1

FOR j FROM i+1 TO n

P(xi→xj)=p1;

P(xi←xj)=p2;

vij=I(p1,p2;xi,xj);

vji=I(p2,p1;xj,xi);

If vij>vji and NOP(xi,xj)

/* NOP(xi,xj)确定两结点xi,xj之间没有开放路径*/

E=E-{<xi-xj>};

E=E∪{<xi→xj>};

Else

E=E-{<xi-xj>}

E=E∪{<xi←xj>}

END IF

END FOR

/* 对有向图进行调整 */

FOR i FROM 1 TO n-1

FOR j FROM i+1 TO n

D(xi,xj); /*D(xi,xj)确定两结点xi,xj的割集 */

vij=I(xi,xj|D(xi,xj));

If vij<ε2

E=E-{xi,xj};

END FOR;

4 应用实验与分析

改进的贝叶斯网络结构学习分类模型仍然采用质量管理中的“产品硬度”数据表作为训练数据集,把训练数据集D、类属性C和非类属性X作为整个算法的输入。

算法中对训练数据集D的类属性C “产品硬度”进行离散化操作后得到五个离散值,分别用C1,C2,C3,C4,C5来表示,结合领域知识,用C1,C2,C3,C4,C5来分别代表一等品,二等品,三等品,四等品和五等品,算法最终把测试数据集进行分类,指出每一个数据对象归属于某一类,也即是找出一个产品是属于几等品。

算法首先构建一个无向图,利用条件互信息来确定属性结点的顺序,设置阈值参数ε1=0.010,执行过程中得到的无向图如图1所示。

对建立的无向图1利用鉴别信息来确定边的方向,并利用环路检验来保证图中不会出现回路,最终确立的有向图如图2所示。

对有向图2利用最小切割集来调整其结构,也相当于对有向图进行剪枝,设置阈值参数ε2=0.020,得到调整后的有向图如图3所示。

经过调整,删除了“添加量”到“材料硬度”的有向边、“材料硬度”到“加工温度3”的有向边、“材料纯度”到“加工温度2”的有向边、“加工温度1”到“加工温度2”的有向边,同时结点“加工温度2”被孤立,因此也被删除。

最终得到的贝叶斯网络结构如图3所示,对比文献[3]中MIBNS算法得到的结果可以看出两算法得到的结果并不完全相同,本算法把“材料硬度”到“加工温度3”的有向边也删除了,实验结果及结合质量管理领域知识证明这样得到的结果会更加精确。

根据上面得到的有向图,使用Judea Pearl在文献[4]中给出的定理构建贝叶斯网络分类器的方法得到的贝叶斯网络分类器式子如下:

$\begin{array}{l} \underset{C (X_{1}, X_{2}, \dots, X_{6},)}{a r g m a x} {Ρ (C) Ρ (X_{1} | C) Ρ (X_{2} | X_{1}, C) \\ Ρ (X_{3} | X_{1}, C) Ρ (X_{4} | X_{2}, C) \\ Ρ (X_{5} | X_{1}, X_{4}, C) Ρ (X_{6} | X_{2}, X_{3}, C)} \end{array}$

其中,X1代表结点“产品硬度”,X2代表结点“材料硬度”,X3代表结点“添加量”,X4代表结点“材料纯度”,X5代表结点“加工温度3”,X6代表结点“加工温度1”。

由以上得到的贝叶斯网络分类器,抽取“产品硬度”数据表中20条数据作为测试数据集,最终得到的分类结果如表1所示。

由以上结果可以看出,经过算法输出把测试数据集中的第3、7、16、19个产品归属到类别C1(一等品)中,把第1、4、5、9、10、14、15、17、18个产品归属到类别C2(二等品)中,把第2、6、11、12、13、20个产品归属到类别C3(三等品)中,把第8个产品归属到类别C4(四等品)中,没有产品属于类别C5(五等品)。

为了和文献[3]中MIBNS算法进行比较,使用同样的数据集对MIBNS算法进行实验,结果如表2所示。

对比MIBNS算法的结果可以看出,两算法得到的结果只存在一个产品数据分类的差异,这也正是由于两算法确定的贝叶斯网络结构存在微小差异造成的。根据实际的数据值和领域知识可知把产品数据d1归属到类别C2中更符合实际情况。实验结果表明本算法在保证得到正确结果的条件下又提高了效率,是对MIBNS算法的一个较成功的改进。

5 性能分析

改进的贝叶斯网络结构学习算法分类模型仍然以训练数据集D、以及D的非类属性集X和类属性C作为输入,在给定阈值ε1,ε2时,输出相应的贝叶斯网络结构图P*。整个分类模型的构建就是结合这个贝叶斯网络结构和Judea Pearl在文献[4]中给出的定理来最终确定的。通过将本算法与文献[1]中的MIBNS算法相比较可知,MIBNS算法在最坏的情况下要进行n(m+n)+2mn2次的运算,而该算法的时间复杂度为n(m+n)+2n(n-1)次的运算,其中n是训练数据集非类属性的属性个数,m是类属性的属性个数。因此,该算法较MIBNS算法在时间复杂度方面有明显的提高。另外该算法只需要设置两个阈值参数ε1,ε2,提高了算法的易用性,减少了用户的参与。从以上分析中可见,影响整个算法性能的一个最重要的因素就是数据集中类属性和非类属性的个数,即数据集的维数。综上所述,该算法在提高了结构学习准确率的同时,时效性方面也优于MIBNS算法。

6 结语

改进的贝叶斯结构学习分类模型的核心仍然是相应的贝叶斯网络结构的确定,文章提出的改进的贝叶斯网络结构学习算法是受了文献[3]中提出的基于互信息贝叶斯网络的分类模型的启发。在该算法中,引用了交叉熵这个概念做依据来判断弧的方向,并且利用环路检验来保证图中不会出现回路。并合理地利用最小切割集的知识来对已有的图进行调整,以此来构造了一个与数据具有拟合性更好的一个贝叶斯网络结构。文章最后把改进的贝叶斯网络结果学习分类模型与基于互信息的贝叶斯网络的分类模型在算法的性能上作了对比,通过对比发现本文算法在面对数据量大且属性之间不具有确定性时具有较高的精确性。

参考文献

[1]Neil M,Fenton N,Nielsen L.Building large-scale Bayesian networks[J].The Knowledge Engineering Review,2000,15(3):257-284.

[2]Tsamardinos I,Brown E,Aleferis CF.The max-min hill-climbing Bayesian network structure learning algorithm[J].Machine Learning,2006,65(1):31-78.

[3]王越,谭暑秋,刘亚辉.基于互信息的贝叶斯网络结构学习算法及应用[J].计算机工程,2011,7(37):62-64.

[4]Pearl J.Probabilistic Reasoning in intelligent systems[M].Morgan Kaufann,San Francisco,Calif,1988.

[5]刘惟一,田雯.数据模型[M].北京:科学出版社,2001.

[6]Rao J R,Rohatgi P,Scherzer H.Partitioning Attacks:Or How to Rapidly Clone Some GSM Cards[C]//Proc of IEEE Symp on Securi-ty and Privacy,2002:31234.

[7]姜丹,钱玉美.信息论与编码[M].北京:科学出版社,1992.

贝叶斯学习篇8

本文尝试用一个一般化的行为调整模式来解释业主通过试误、受教和模仿来选择所谓“理性”和“非理性”的维权方式。本文的主要目的是基于个体学习来探究业主群体行为调整的认知根源[1]。这里将引入一种基于贝叶斯法则的行为调整模型(Bayesian Adaptive Rhythm)来进行现实模拟。第二部分界定业主维权时使用到的四种基本策略;第三部分简单介绍心理学和社会学对我们的研究方法所起的作用,并给出两个基本假设;第四部分给出BAR调整模式;第五部分用具体的案例来说明该模型的运行特点。

1住宅小区业主的维权策略界定

1.1四种维权策略

在维权过程中,业主有四种基本的维权途径。第一种途径是采用对争议方利益造成损害的方式,如业主悬挂维权条幅、堵路、拒交物业费、停止银行按揭、呼吁媒体介入等。第二种是通过业委会或业主代表与侵犯业主权益的当事人(开发商、物管公司、政府部门等)进行谈判,协商解决业主权益问题。第三种是向政府有关部门投诉,这一方式是业主维权的有效途径,也是我国各级政府“立党为公,执政为民”的具体体现。第四种是提起仲裁、诉讼等司法途径的方式。

我们将以上四种途径称为四种纯策略,分别定义为:“报复”、“谈判”、“行政”、“司法”,以这四种基本方式为基础也可以组合成不同的行动方式。

1.2决策环境的不确定性与由此引起的信念调整

业主对于这四种策略的预期结果是不一致的,预期结果与实际运行的结果也是不一致的。“报复”策略通常是业主最先采取的方式,因为这一方式作用对象直接,影响面大,但这一策略往往收效甚微,业主为此常常获得较强的“负收益”;“谈判”的交易成本较低,业主通常将其预期为既能有效解决问题又不伤和气的方式,但前提是争议双方对相关法律、法理比较明白、有相互尊重的意识,同时对业主的自我治理能力提出较高要求,并要求一个较好的依法办事的环境,如果业主的合法权益得不到行政部门和司法机关的保护,侵权当事人一般是不会通过协商放弃既得利益的;“行政”策略属政府依赖方式,是业主维权的主要有效途径,但业主对于政府的态度、应对方式无法获得明确的信息,某些部门的拖延、回避等不作为直接提高了业主维权的难度,增加了业主的时间成本;考虑到法律的公正性,“司法”是业主最重要的法律武器,然而目前这一策略的频繁使用本身说明了谈判和行政投诉途径的无效性,并且司法诉讼途径不通畅、法律诉讼周期长、程序复杂,判决结果往往倾向于鼓励侵权当事人拒绝协商继续侵权的意愿。

环境的不确定性带来了策略选择的问题,所以业主维权的过程是选择某个策略或策略组合的过程,观察其运行结果,并以此为据对自己的选择会带来多大收益的信念进行调整。

2相关学科的研究成果对个体行为所起的作用

贝叶斯定理用于推理时一般是条件概率推理问题,在心理学领域,Kahneman和Tversky等人探讨对揭示人们认知加工过程与规律,揭示习俗和制度选择行为模式的变迁过程具有十分重要的理论意义和实践意义。

贝叶斯定理作为处理不确定情形的分析方法的原理已经很多年,可用文字直观的描述为:当行为人无法准确掌握某件事物的本质时,可以依靠与事物特定本质相关的事件出现的多少来判断其本质属性的概率,或者说某件事情发生的概率大致可以由它过去发生的概率似然估计出来。用数学语言表述就是:支持某项属性的事件发生得越多,则该属性成立的可能性就越大[2,3,4]。

已有的研究认为个体进行推理时接受信息的方式的主要有两种:“文本”和“经验”。“文本”方式是指实验中的问题以文本的形式直接向被试个体提供各事件的先验概率、条件概率等信息,让被试对象对某一出现的事件做出概率大小的判断。然而,在实际生活中,人们进行概率判断需要从自己经历过的事件中搜集信息,而不是像文本方式那样被动得到这些信息。经验方式便克服了文本方式这一缺陷。经验方式就是在实验中让被试对象通过经历事件,主动搜集信息来获得各种先验概率和条件概率,然后做出概率判断。经验方式的优点在于实验操作过程非常接近人们在日常生活中获得概率信息做出判断的情况,较为真实的反映了人们实际的表征信息和做出判断的过程。所以许多研究者采用了这一范式。

总结以上所述,本文将采用两点基本假定:①业主群体的判断推理符合贝叶斯法则;②业主群体接受信息以经验方式为主。

3业主维权策略选择的贝叶斯调整模型

3.1三个基本要求

由于第三部分提出的两点假设是对于行为人最低要求,因此在业主难以控制且不能完全准确预测的维权过程中,还应加入三个基本要求:

业主通过不同策略组合取得的结果来学习,并对自己的行为有所记忆;业主利用基本假定①来获得信息,并采纳他认为最有可能达到既定目标的策略组合;业主相信存在某个策略均衡点,并对此均衡抱有一种相对不固定的先验信念,即这个先验信念对主体的行动影响是中性的。

3.2业主维权的BAR模型构成

贝叶斯调整模型(Bayesian Adaptive Rhythm)是一种递推的学习模型,是一个路径依赖的动态系统,即每次的响应概率是此前一系列响应概率和每次概率结果的函数。具体来讲,是指行为人的每一次尝试都选择使其目标预期最大化的行为策略集。根据这个思路,行为人根据每次行动的经验结果来更新自己关于各种可供选择的世界状态(如行动风险表)的先验概率,通过结果发生的概率(条件概率)来修正信念从而达到既定目标。

3.2.1现实简化

客观状态:假设某个业主要进行T期维权,其中第t期维权中(t=1,2,..,T)可选的行动策略有四个,这四个策略的成功概率分别用pB、pT、pX、pS来表示,那么可以用一个1×4向量undefined来表示业主面对的“客观世界状态”。元素pk∈[0,1],具体数值由业主通过以往的经历、观察经一定的计算得出。

策略组合:面对每一轮维权过程,业主每一期可能选择的策略组合用另一个1×4向量undefined(j=1,2…)来表示。向量中的元素ϕn用1和0来表示:当ϕk=1时,表示业主选择了该策略,ϕk =0时,表示业主未选择该策略。

3.2.2业主维权策略的选择调整过程

一个客观概率(用P表示)。P(A/t,j):条件概率,业主在第t期维权中,采用第j个策略组合导致维权成功的客观概率(事件A表示维权成功)。

三个主观概率(用p表示)。p(A/t):对第t期维权获得成功的先验主观概率。p(A/t+1)=p′(A/i):第t期维权获得成功的后验概率,也是第t+1期的先验概率。p(A/t,j)=[P(A/t,j)]·p(A/t):第t期维权中,第j个组合获得成功的主观概率。鉴于前述的第三条要求,业主对于初始值p(A/0)的选择依赖于他所面临的undefined。

行动决策规则。业主在每一期计算每个策略组合可获成功的期望值:

undefined

决策规则:undefined

信念调整规则。业主选择预期值最大的策略组合进行维权,并观察每期是否达到预期目标,然后根据贝叶斯公式得到第t期维权成功的后验概率,即第t+1期的先验概率:

undefined

经过若干样本观察或数值计算,可以总结出策略的不同选择、不同组合、策略实施的时间先后都能带来不同的维权结果。这种认知过程是由客观(随机)过程和运算法则共同作用的,决定的是行为人在某一特定场景下采取某种行动的可能结果[4,5]。

4案例分析

4.1两个小区的维权之路[6,7,8,9]

4.1.1 “城市印象”业主维权事件

“城市印象”小区位于深圳市南山区商业文化中心区,周边配套完善,片区优势明显及深圳市政府积极投资的西部通道和滨海走廓的前景吸引了大批年轻的白领阶层购买,然而距约定收楼尚有半年的时间起,业主就发现一连串与预售合同约定条目不符的事实,一场维权运动就此展开。下面简单记录业主的维权事件。

资料来源:文献[10]

4.1.2丰泽湖山庄维权案

深圳丰泽湖山庄业主维权案,是一起典型案例,尤其是就纠纷问题举行的听证会,是“决策程序民主化的一个重要标志”。本文将其作为案例分析出于以下三点考虑:首先,维权内容涉及的是政府部门对业主权益的漠视和侵害,使得习惯依赖于政府部门解决纠纷的业主面临前所未有的认知考验;其次,业主选择的维权途径非常广泛,几乎涵盖了上述所有四种策略,引起社会各界的广泛关注;第三,本案的业主内部相当团结,几乎每次维权行动都是以集体行动为形式的,因此可以着重考察业主的行动策略选择。

丰泽湖山庄住宅小区位于深圳市福田区和宝安区交界的梅林关旁,因小区中心有一总面积达9万平米的环型湖泊而得名。然而在业主刚刚入住不到一个月之时,业主在小区内的一个公示牌上得知政府规划的一条双向八车道重型集装箱货柜车专用通道高架桥将从小区内部横穿而过,小区已建好的幼儿园和会所将被拆除。由于这个规划事先开发商并没有向他们公示,业主除了感到困惑之外,也担心将降低小区今后的居住品质。业主认为,规划部门在确定道路规划前,应事先向业主公示方案,给个时间让业主参与意见,政府也应和业主协商赔偿事宜。于是一场维权运动在匆忙之中展开:

1)请愿与堵路:2003年11月10日早上,300多名业主抵达深圳市政府,要求与市领导见面,但结果不能令业主满意。失望的业主回到小区后选择在深港间最为繁忙的交通枢纽——皇岗路梅林检查站路段聚集起来,在皇岗路上堵了几个小时,造成长时间交通堵塞。之后部分业主与保安员发生冲突,3名业主和3名小区保安被警方带走,经调查取证,带头闹事者已触犯法律,被警方依法予以刑事拘留。事后,小区业主决定成立业委会筹备小组规范业主行为。

2)致歉:11月17日,筹备小组通过当地媒体向全体市民道歉,声明“维权活动应通过正常的途径和合法的方式进行,在维护自己权利的时候不能侵害他人利益和公众利益。”

3)学习:11月23日,筹备小组向社会各界以及深圳市政府、规则与国土资源局、住宅局等有关部门发出邀请,举办“法治公民意识的觉醒研讨会”,共同探讨合适的维权道路。

4)上访、协商:2003年12月-2004年3月,业主就快速路修改方案问题多次与相关部门进行协商,并等待规划部门的调整方案公示,期间多家媒体报道了该事件。

5)协商:2004年4月7日,调整方案公示,业主再次到市政府上访,提出细化的设计要求,以保证小区内现有湖水、空气等自然环境不受破坏。

6)听证会:2004年6月29日,方案听证会举行,八名业主作为代表进行陈述,最后结果是双方接受第4套修改方案,听证报告交市政府,作为决策时重要参考依据。

4.2案例小结

从以上案例不难发现,争议双方没有根本对立的维权内容基本得到了较好解决,集中在开发商方面的维权内容由于涉及土地权属、赔偿等关键问题则未能取得成功,而这些方面正是维权的难点所在。从维权方式来看,较早维权的丰泽湖山庄由于时间紧迫,并期望在短时间内得到满意答复,采取了极端的“报复”行为,并持续使用了这一策略,之后随着维权行动逐渐深入,业主意识到了维权所需的时间成本和信息成本,转而对“谈判”寄予了较高期望;而城市印象则一直采取“谈判”策略,但其预期结果仍与实际存在显著差距。

对照BAR的特点,由于没有足够的信息证明某个策略组合是一定有效的,业主首先会尝试其中某个组合。如果依此可以取得较显著的效果(政府愿意谈判等),业主会提高此方法有效性的概率,并在以后加强使用这种行为。丰泽湖山庄业主的先验认知是将仲裁、诉讼等手段的成功估计成小概率事件,而认为扩大纠纷的影响可引起媒体关注可能带来开发商的让步概率较大,进而导致较高行政级别(例如直至中央)的重视才能将久拖不决的困难解决的话,维权的行动选择依BAR必然“理性”地选择“报复”策略。

对于城市印象业主来说,丰泽湖山庄的维权事件曾经轰动深圳乃至全国,他们由于“报复”行为获得的负强化有目共睹。随着维权知识的扩散,他们采用了相对稳妥的“谈判”方法。从宏观层次上来看,深圳业主的维权成功率是有所上升的,并出现了由街道组织、多个业主委员会联合组建的片区维权工作站,这种示范作用将被其它同类情况的小区观察到,必然会有差别的选择使用有效的维权策略,并推动着维权运动向有效的方向发展。从众多案例中,小区业主通过维权斗争,积累了维权手段的经验,在处理纠纷的主要矛盾方面取得的认知进步也是符合BAR特点的。

4.3维权过程中的BAR路径

4.3.1行动策略的调整过程

丰泽湖山庄案例之所以典型,就是因为其包括了众多住宅小区业主维权的特征。将长达8个月之久的丰泽湖山庄业主维权过程用四个阶段的策略调整过程简化的表征出来:在t=1期,业主采取的请愿、堵路方式是很典型的“报复”策略,原因在于业主对侵权事件迅速做出反应,期望在较短时间内得到满意答复,然而现实情况与预期严重不符。接下来的t=2期,业主进行了登报致歉方式,从一方面看这是一种“谈判”策略,通过单方面的声明表达出业主渴望有关部门做出答复,但从一方面来看这也可以认为是另一种形式的“报复”策略,因为业主另一个目的是引起媒体及公众的关注,扩大影响,显然这一“报复”策略比t=1期的策略要“温和”得多,而实际效果也是让业主满意的。事实上,业主就维权事件举办的研讨会也应属于这一策略。t=3期,业主与相关部门进行若干次上访、方案论证等,多数时间都获得有关部门的承诺,如答应将展示修改方案等,通过多次往复,业主对各方面的信息掌握得越来越多,对未来的预期和对成本的把握也较为稳定准确起来。t=4期,听证会上业主代表进行了陈述,并博得现场阵阵掌声,虽然最后的听证结果仍让业主代表不是完全满意,但他们同意在以后的时间里继续就相关争议问题进行协商讨论。总的来说,“谈判”是一个持续使用的策略。

4.3.2调整模式的运行特点

1)初始值的重要性:

政府侵权带来的业主认知考验。BAR模型的一个特点就是初始值的重要性,即先验认知对于个体行为的影响。环境因素的不确定性和随机干扰的运行是个体面临的一种外生条件,但个体对这些条件的先验认知在一定程度上决定了其在个体学习过程中作为外生环境的适度准确性,这对BAR方法的应用是至关重要的,因为它先验的决定了个体在处理信息问题时如何确定各种客观状态,即确定undefined。

有限的计算能力使个体在面临较为陌生的外界信号时只能用一种简化的方法从有限数据中提取决策信息,如启发法。丰泽湖山庄的业主一开始并没有足够的信息证明哪一种维权途径是一定有效的,并先验的将谈判、诉讼等手段的成功估计成小概率事件,而认为直接与政府对话、扩大纠纷的影响可引起媒体关注可能带来政府的让步概率较大,维权的行动选择依BAR选择“报复”策略。

2)BAR的运行规则:

持续使用有效的“谈判”策略。使用BAR的个体通过一定途径拥有了较好的策略组合,并抓住不同策略之间某些显著特征,由此产生较为成熟的经验,因而能使其行动获得成功,掌握一条最基本的准则是“坚持最有效的行动”。这条准则并不是先验的选择某个可以成功的策略组合,而是多次试错学习后的事实结果,是对于正负反馈信号的反应。个体基于后验估计对策略组合的优化可以对导致成功的组合进行正强化,反之则排挤掉这一组合,最终受正强化的组合倾向于被锁定,个体的行为相对稳定。

对于丰泽湖山庄的业主来说,其行为趋势一定是对失败做出反应并转向相对稳妥的方法。图2表述的调整过程正是业主由迅速导致失败的“报复”策略转向收效较慢但有可能导致成功的“谈判”策略,最后在“谈判”策略上收敛。

3)个体认知进步和集体学习:

丰泽湖山庄维权事件的示范效应。个体在BAR的试错过程中可以提高自身的认知。这里将认知进步定义为:个体的先验概率收敛,以一定概率把其信念看作“真实”模式,这个概率是在特定条件下行动获得成功的客观概率。绝对主义认为只有个体在不断提高客观真实世界状态的可信度时,认知才真正得到发展演化。通过BAR获得认知进步的个体,其每个时点的调整都受其先前形态严格及时的限制,即个体有选择的保留某些信念,而信念限定的调整特征在下一次行动中表现得非常典型。

在宏观层次上,随着知识扩散,更多的业主使用某些具有较高成功概率的策略组合,使得维权的成功率持续上升,这种上升体现了维权业主的持续学习和行为的持续改变——BAR的运行规则在宏观层面产生了集体学习的效果。丰泽湖山庄维权案中的研讨会、听证会都为深圳其他小区的维权活动提供了示范作用,具有很典型的意义。事实上,城市印象小区的业主在进行维权之前,就通过向周边小区学习、聘请律师咨询等多种学习方式积累了维权手段的经验,从而进行“理性”的谈判,取得了在处理纠纷的主要矛盾方面的认知进步。

5结论与讨论

今年元月《物权法》已正式开始实施,这为保护“物的归属”化解物业纠纷提供了法律保障。然而,任何一部法律都不可能是绝对理想的,其执行过程也将受到各种现实条件的干扰,法律界定和实际情况的差异可能成为隐患,削弱法律的实际效力。BAR模型是一个研究个体认知进步与行为调整的一般性模型,希望下面四点可以为这部法律的贯彻和执行提供某种意义的借鉴和启示:

1)关于交易纠纷处理方式的制度选择并不是简单的设计、宣讲就可以推行实施的,交易纠纷处理制度变迁必定是当事人信念调整均衡的过程;

2)惯性的历史记忆对业主当事人贝叶斯推断及维权行动选择是重要的;

3)业主当事人对“谈判”策略是否能形成高收益预期的信念调整,必然需要经历足够的适当的后验概率事件。处理房产纠纷、物业纠纷的法律诉讼周期长、程序较复杂、过程烦琐,显然将强化“报复”策略;

4)适度相信经验策略,虽然经验可以减轻认知负荷,但也会导致错误的概率估计,在许多情况下误导人们的判断。所以业主在处理维权纠纷问题上,也有可能形成“错误”的概率估计致使遭受较大的损失。

由于时间及客观条件限制,至今尚未进行定量测试,后续研究可望基于以上思路展开实际的经验工作,给出样本观测的信念调整及物业交易纠纷处理方式的制度选择计量估计与检验。此外,BAR是一个研究个体学习的模型,应用在集体行动问题上应考虑更多的随机干扰问题,做出相应的简化假设。

参考文献

[1]CLARK A.认知理性:个人学习和外部结构的相互作用[G]//John N Drobak,John V C Nye ed.新制度经济学前沿.张宇燕,等,译.北京:经济科学出版社,2003:320-346.

[2]DAVID P A,SANDERSON W C,STEINMUELLER W E.Bounded Bayesian Learning and Performance Improvement inComplex Production Processes:A Stochastic Simulation Ap-proach[M].Research-IOIP Project Research Memorandum.Stanford University Center for Economic Policy,Stanford,CA,1988.

[3]KAHNEMAN D,SLOVIC P,TVERSKY A,et al.Judgmentunder Uncertainty:Heuristics and Biases[J].Cambridge U-niversity Press,Cambridge,UK:1982.

[4]KURNA T.Cognitive limitations and preference evolution[J].Journal of Institutional and Theoretical Economics,1994.

[5]ATKINSO R C,BOWER G,CROTHERS.Introduction toMathematical Learning[M].New York:1965.

[6]傅沙沙.业主委员会艰难维权路[EB/OL].(2006-01-18).http://zzhz.zjol.com.cn/05zzhz/system/2006/01/18/006447697.shtml.

[7]高祥阳,陈宇.购房置业、业主维权完全手册[M].北京:中国人民大学法律援助中心,2003.

[8]南方都市报.丰泽湖山庄业主维权之路[EB/OL].(2004-08-04).http://gz.house.sina.com.cn/news/2004-08-04/590823.html.

[9]沈莹茜.物业和业方双方都要理性维权[EB/OL].(2006-03-14).http://zzhz.zjol.com.cn/05zzhz/news/honest/ht-tp://zzhz.zjol.com.cn/05zzhz/system/2006/03/14/006515556.shtml.

贝叶斯学习篇9

摘要：采用聚类分析法将多专家的动态综合评价转换为静态综合评价；引入横向拉开档次法对各指标客观赋权，结合指标主观权重，运用数学规划法得到指标的集成权重；采用贝叶斯网络模型对24项科技成果进行分类评价，对每一项成果获得某一等级奖项的可能性给出测度，并对每一类内的项目排序。实证分析表明：我国科研成果大部分具有研究价值，且成果丰硕，但突破性、创造性的研究成果较少。

关键词：贝叶斯网络；集成权重；拉开档次法；聚类分析法

中图分类号：G311 文献标识码：A

与2013年、2012年相比，2014年度国家科学技术奖授奖项目明显减少。对此，国家科技部奖励办表示，优化奖励结构、减少奖励数量，是为了突出鼓励自主创新成果和重大的发明创造科技成果。科技成果的评价作为科技奖励的前期工作，对科技奖励的最终决策有着举足轻重的作用，也是保证真正的重大创新项目获得应有奖励、鼓励科研人员进一步有所突破的关键。

目前，学者们对科技奖励综合评价体系的研究做了大量工作，部分研究成果已经投入实际应用。张立军等构建了基于路径系数权重体系的科技奖励评价模型。王瑛等提出了基于模糊多属性投影法的科技奖励模型和E-BP神经网络的科技奖励评价模型。黄卫春等提出了一种基于云模型的科技奖励评审模型，利用云模型描述项目评分在各属性下的分布情况，通过计算云模型参数来确定云模型数字特征图或云滴分布情况，并以此确定评价等级。王瑛、蒋晓东等提出了改进CRITIC法和云模型的科技奖励评价模型，既考虑评价过程中专家评分的模糊性和随机性，又考虑了定性语言与定量语言之问的转换。王瑛、王娜等提出了基于随机森林赋权和改进的ELECTRE-Ⅲ方法的科技奖励评价方法，既提高了权重估计的精确度和可信度，又解决了难以给定门槛值和不能完全排序的问题。朱紫巍等针对国内外科技评价方法，进行比较分析，提出了改革我国科技评价方法的建议。

针对科技奖励评价涉及多专家、多项目、多指标的特点，此前，学界的研究主要集中在评价指标的客观赋权法与主观赋权法的单方面研究，没有将这两方面有机结合起来；在评价方法上主要集中在数理统计和人工智能等方面，但对于评价结果的可靠性没有给出科学的测度。对此，本文提出一种集成权重的方法对科技奖励的评价指标进行综合赋权；应用概率论中的贝叶斯网络模型进行科技奖励综合评价，该方法不仅可实现对科技成果的分类评价，而且可对每一项科技成果获得某一等级奖项的可能性给出概率测度，并在分类评价的基础上，对每一类内的项目进行排序。

1集成权重的理论

评价指标权重的确定可分为主观赋权法和客观赋权法，两者各有千秋。本文采用一種主、客观权重集成的方法，计算各评价指标的综合权重，该方法既能满足决策者的主观偏好，又能实现决策的客观性、真实性。

1.1基于聚类分析的专家权重理论

聚类分析方法是一种作为模式识别的分类方法，它常常被用来判断样品质量的好坏。把评审专家的个体排序向量看作是待识别的样品，对其进行聚类分析并判别其客观可信性，再根据聚类结果给专家赋权。

动态专家赋权坚持的是简单多数的基本原则，即一个评审结果体现的是整个专家群体的综合意见。因此，一个专家的个人评审意见和大多数专家的评审结果的吻合程度决定了该专家在整个综合评价中所占的分量。如果他的评价结果与大多数专家的结论基本一致，就可以给这一类专家赋以较大的权重；反之，其意见就值得怀疑，可以给这一类专家赋以较小的权重。

通过聚类分析，可以将个体排序向量划分成不同的类别，即将k个评审专家分成s类（s≤k），假设第l类（l≤s）内包含φ_l个个体排序向量，那么，第k位专家的权重η_k应该和他所在的类别中包含的专家人数φ_k成正比，其具体计算公式为：

（1）对η_k进行归一化处理，即可得到基于聚类分析的动态专家权重：

（2）

1.2拉开档次法的指标赋权理论

拉开档次法就是在使得各被评价对象之问的整体差异尽量拉大的条件下确定评价指标权重的方法。

对于静态综合评价问题，一般解决办法是取线性综合评价函数：

（3）式中：ω_i为评价指标权重。

（4）式中：

当指标权重矩阵W为对称矩阵H的最大特征值对应的特征向量时，σ²取最大值。此时权重系数W最大可能地体现了各评价对象问的差异。

1.3基于数学规划法的集成权重理论

本文应用数学规划法在非线性约束条件下，求解线性目标函数的极值问题。该方法在科技奖励综合评价中的具体应用如下。

（5）

解得：

（6）

（7）（8）

（9）

（10）

由式（10）即可求得评价指标的集成权重。

2贝叶斯网络模型的理论

（11）式中：P（A|B_i）为条件概率；P（B_i）为事件B_i的概率。

结合科技奖励评价的特点，B_i为科技奖励的等级集，元素y_ji表示第j个指标在第i等级时的标准值；A表示科技奖励的指标集，元素x_jk表示第k项科技成果的第j个指标的实际值；i为标准级别，i=1，2，…，s；j为指标，j=1，2，…，m；k为科技成果编号，k=1，2，…，n。据此式（11）可改写为：

（12）

算法步骤如下：

1）计算P（y_ji）。在没有任何信息的条件下，某项科技成果究竟属于哪一等级，这在许多应用中难以确定。结合科技奖励的特点，在没有获取科技成果相关信息的情况下，人们最能接受的是获得某等级奖励的概率相等，即取：P（y_j1）P=（y_j2）=…=P（y_js）=1/s。

2）计算P（x_jk|y_ji）。现有研究成果表明，P（x_jk|y_ji）的估计是贝叶斯网络模型的核心。本文从抽样误差角度估计P（x_jk|y_ji）。根据统计理论，当科技成果属于i类时，由于抽样缘故获得的样本指标值和总体指标值总是存在一定的抽样误差，其分布可用正态分布表示。基于以上考虑，将抽样误差正态分布原理用于估计P（x_jk|y_ji）。以科技成果评价指标j各等级标准值作为正态分布的均值a_j，基于a_j和标准差σ_j获得某一等级某一指标完整的正态分布。

（13）

（14）

（15）式中：a_j，σ_j和C_j分别为指标j各等级的均值、标准差和变异系数。

由式（13）～（15）计算变异系数C_j，C_j表示指标j在各类之间相对变化情况。而某类指标j抽样值的相对变化亦与之类似，因此采用C_ji=C_j，即以各类等级变异系数估计某一类指标抽样值的变异系数。

基于抽样误差正态分布原理估计P（x_jk|y_ji）的计算步骤归纳如下：

①由式（13）～（15）估计C_ji，并采用C_ji=C_j；

②将第i类指标j的标准值y_jk作为该类指标均值；

③计算第i类的标准差σ_ji=C_jiy_ji；

④将抽样值（检测值）x_jk标准化，

（16）

⑤以标准化正态分布计算

（17）

用标准正态分布函数求取，|t_jk|为t_jk坤的绝对值。

3）由式（12）计算P（y_ji|x_jk）。

4）多指标下（ω_j为指标权重）科技成果评价后验概率P_i的计算。

（18）

5）以最大概率原则决策最终的级别P_h。

（19）

6）以分类结果为基础，在每一类内根据概率大小进行排序。

3实证分析

以国家科学技术进步奖（技术开放项目）评选中25位专家对24项科技成果的评分数据（资料来源：科技部国家科技奖励办公室，原始数据略）为例，该奖项的5个评价指标是：技术创新程度、技术经济指标的先进程度、技术创新对提高市场竞争能力的作用、已获经济效益、推动科技进步的作用。国家科技奖励办赋予5个评价指标的权重为：ω'=（0.2，0.2，0.2，0.25，0.15），将该权重作为评价指标的主观权重。具体步骤如下。

步骤1基于聚类分析法的专家权重的计算。

运用SPSS19.0对原始数据进行聚类分析，将25位专家分为5类，即：

第一类包含10，16号2位专家；

第二类包含1，2，4，12，15号5位专家；

第三类包含3，6，8，9，14，25号6位专家；

第四类包含5，7，11，13，18，19，20，21，22，23，24号11位专家；

第五类：含17号1位专家。由式（1）（2）计算专家权重，结果见表1。

由表1求得的专家动态权重，采用简单线性加权法，计算25位专家对每个项目的5个评价指标评分的加权平均值，计算结果见表2。

表2的数据组成的矩阵，即为式（4）中的矩阵X，应用Matlab7.0计算X^TX的最大特征值及归一化的特征向量（即权重系数）分别为：

步骤3科技成果评价标准体系的构建。

根据国家科技奖励办公布的国家科技进步奖（技术开发项目）评价指标体系和奖励办法，建立国家科技进步奖（技术开发项目）评价标准。按照“从严把关，严肃评审，宁缺毋滥”的原则，在分类上设置5个等级，在各等级标准设定中采取5分制原则，采用随机生成数的办法，得到5个指标各等级的评价标准，见表3。

步骤4

基于贝叶斯网络模型的科技奖励评价。

3）由式（12）可知，求P（y_ji|x_jk）的过程就相当于P（x_ik|y_ji）的归一化过程，计算结果略。

4）由式（18）计算该项目分属各等级的概率。

同理，计算24个项目分属各等级的概率，结果见表5。

5）由式（19）确定项目1所属类别，属于三等，抽样误差标准正态分布以0.366的概率保证其获得三等奖。

6）同理，可以得到所有项目的所属类别，并根据同一类内概率的大小，进行排序，结果见表6。

从分类评价结果看，大部分科技成果都属于二等和三等，一等和四等的项目较少，五等的项目完全没有；从评价结果的可靠性看，获得一等奖的项目分别以0.408，0.426，0.469的概率给予保障，获得二等、三等项目的可靠性测度维持在0.382，获得四等奖的可靠性则以0.320的概率给予保障；每一个等级内的排序可以為决策部门在授奖指标一定的情况下提供参考。通过实证分析可以得出：高等级获奖项目较少，大部分属于二等和三等，低等级获奖项目极少，这表明我国科研成果绝大部分具有研究价值且成果丰硕，但突破性、创造性的研究成果较少。

4结论

采用集成权重和贝叶斯模型相结合的方法进行科技成果综合评价，方法的特点表现在：

1）聚类分析将多专家的动态评价转化为静态评价。从一般线性函数的评价结果出发，用拉开档次法对评价指标客观赋权，该赋权过程科学、客观、透明，可操作性强。

2）数学规划法将主、客观权重相结合，构成评价指标的集成权重，使科技奖励综合评价结果同时反映了主、客观因素，弥补了单纯采用主观赋权法或客观赋权法的不足。

贝叶斯学习篇10

关键词：电力线通信,脉冲噪声,稀疏贝叶斯学习,噪声消除,信噪比,误符号率

0 引言

电力线通信 (power line communication, PLC) 在电网自动化、自动抄表、家庭内部联网等领域得到了广泛应用。在PLC中干扰主要来自背景噪声和脉冲噪声, 脉冲噪声是突发性、高幅度、低概率的非高斯噪声, 会影响全部子载波上的信号判决, 对PLC的性能产生很大的影响[1,2]。无线通信中的多输入多输出 (multiple-input multiple-output, MIMO) 技术最近被引入PLC中, 用于提升系统的容量和覆盖率[3,4]。在MIMO-PLC系统中高幅度的脉冲噪声在电力线的每条线上产生串扰, 从而引入了相关性[5]。可以使用文献[6]中建立的Bivariate Middleton Class A模型, 来描述MIMO-PLC系统中脉冲噪声的特性。

脉冲噪声消除通常通过简单消波或限幅, 或使用更复杂的参数和迭代的抑制方案。由于脉冲噪声在时域上具有稀疏特性, 可以使用最近发展起来的压缩感知技术来消除脉冲噪声。文献[7]使用基于最小二乘的基追踪的压缩感知重构算法来消除脉冲噪声。文献[8]则使用稀疏贝叶斯学习 (sparse Bayesian learning, SBL) 来消除单输入单输出正交频分复用 (SISO-OFDM) 系统中的脉冲噪声影响。

SBL通过假定先验概率分布来推理总体分布, 由于其具有良好的性能被广泛应用于压缩感知重构中。SBL算法首先由Tipping[9]提出, Wipf和Rao将SBL应用于单观测向量 (single measurement vectors, SMV) 模型[10], 随后提出多观测向量稀疏贝叶斯学习 (MSBL) 算法将SBL算法扩展到多观测向量 (multiple measurement vectors, MMV) 模型[11]。Zhang和Rao利用多观测向量的行相关结构, 引入相关性矩阵B, 得到了利用时序结构的TSBL算法[12]。文献[11-12]显示SBL算法的性能优于同步正交匹配追踪 (simultaneous orthogonal matching pursuit, SOMP) 算法[13]、Basis Pursuit算法[14]和FOCUSS算法[15]。

为了提高MIMO-PLC系统对抗脉冲噪声的能力, 本文基于SBL的理论, 利用脉冲噪声在电力线上的相关性, 提出了一种消除MIMO电力线脉冲噪声的方案。本文脉冲噪声采用Bivariate Middleton Class A模型, 方案使用全部子载波来联合估计脉冲噪声和可用子载波上的信号, 无需训练脉冲噪声的统计信息。

1 系统模型

1.1 MIMO-PLC系统信道

使用火线 (L) 、零线 (N) 和地线 (PE) 的MIMO-PLC系统, 相对传统的只使用火线和零线的PLC有更高的传输速率和更广的覆盖率。文献[3-4]使用L-N和L-PE对来组成2×2 MIMO-PLC系统, 如图1所示。MIMO-PLC系统的发射机 (Tx) 和接收机 (Rx) 通过三线来传输数据。

2×2 MIMO-PLC系统信道模型如下:

式中:Y为接收端的信号;H为2×2的信道矩阵;X为发射端的信号;N为加性噪声, 包含加性高斯白噪声 (AWGN) 和脉冲噪声。

在每个子载波c上的信道矩阵如下:

式中:hij为第i个接收端口和第j个发射端口之间的信道系数。

当发射端和接收端都已知信道状态下, MIMO-PLC系统将信道进行奇异值分解 (SVD) , 通过发射端和接收端联合处理。信道矩阵H在每个子载波c上的奇异值分解如下:

式中:U和VH都为酉矩阵, U-1=UH, VH-1=VHH (上标H表示共轭转置操作) ;Σ为由信道矩阵H奇异值构成的对角矩阵。

1.2 脉冲噪声模型

根据文献[1-2], 电力线中包含工频异步、工频同步和强幅值3种脉冲噪声。通常使用Middleton Class A模型来描述脉冲噪声。对于MIMO-PLC系统来说, 由于脉冲噪声的高幅值导致PLC不同线上出现串扰, 文献[5]中的实验数据也体现了这种相关性。因此, 本文使用文献[6]中的Bivariate Middleton Class A模型来描述MIMO-PLC系统中的脉冲噪声和AWGN。

脉冲噪声的实部和虚部是时间独立同分布, Bivariate Middleton Class A噪声N的联合分布如下:

式中:A为脉冲指数, 是每秒钟接收到的脉冲噪声个数和宽度的乘积, 表示了脉冲噪声的强度, A越小噪声脉冲特性越强;nR (I) 为噪声N的实部或虚部矩阵;m=0, 1;κ为两路噪声的相关系数, κ∈[-1, 1];Γ1和Γ2分别为2×2 MIMO-PLC系统的接收机在两路上的高斯噪声分量和脉冲噪声分量的平均功率比。

1.3 系统架构

本文的MIMO-PLC脉冲噪声消除系统如图2所示。

噪声消除模块位于快速傅里叶变换 (FFT) 之后, 频率均衡 (frequency domain equalize, FEQ) 之前。其他模块和文献[3-4]中的一样, 这样可以尽量减少现有系统的改动。为简化, 本文仿真中没有加入前向纠错 (forward error correction, FEC) 模块, 通过误符号率 (symbol error rate, SER) 来体现系统抗噪声能力。在发射端, 二进制比特被映射为OFDM符号α, 其中M个空子载波没有填入数据, 剩下的Nc-M个子载波用于数据传输。接下来进行预编码和快速傅里叶逆变换 (IFFT) 将频率信号转变为时域信号。然后, 加入循环前缀 (cyclic prefix, CP) 用于消除符号间的干扰。当发射端和接收端都已知信道状态下, 没有脉冲噪声消除情况下, FEQ后接收到的信号为:

式中:F为Nc点的离散傅里叶变换 (DFT) 矩阵;e和n∈RN分别表示脉冲噪声和AWGN。

经过FFT以后的信号k为:

采用压缩感知的概念, e为待估计解向量, F为感知矩阵, k为观测向量, 系统的噪声为。v满足均值为UΣα、方差为λ的高斯分布:

由压缩感知重构算法可以得到e的估计值, 通过脉冲噪声消除模块后的信号为:

得到d后, 通过均衡模块后信号为:

将得到的送入后面的解映射模块。脉冲噪声消除模块中的估计算法由后面章节中的压缩感知重构算法构成。

2 SBL算法

2.1 SMV模型下的SBL算法

压缩感知的SMV基本模型如下 (其中, y的维数为M×1) :

式中:Φ为M×Nc的感知矩阵;x为Nc×1维待求的解向量。

SBL算法假定x向量中的每个元素是均值为0、方差为γi的高斯分布, 噪声v为均值为0、方差为λ的高斯白噪声向量。利用贝叶斯规则容易获得其后验分布为高斯分布:

式中:, 使用第二类最大似然估计来估计Γ和λ, 通常采用基于迭代的广义最大期望值算法来求解。

在接收信号y及超参数Γ和λ已知的情况下, x满足均值为μx、方差为Σx的正态分布:

x的最大后验估计由均值μx给出。算法收敛后, 大部分的γi会趋于0, 从而μx也会趋于0, 得到x的稀疏解。

2.2 MMV模型下的SBL算法

在一些应用中 (比如源定位、波到达方向估计) , 有一系列的观测数据可以使用, 从而压缩感知的基本SMV模型 (式 (12) ) 扩展成MMV模型 (其中, Y的维数为M×L, X的维数为Nc×L) :

式中:V为噪声矩阵。

和前面SMV模型的假定一样, X只有少数行为非零行, 而绝大多数行都为零行。MMV模型相对只使用一个观测向量的SMV模型能获得更好的最终解。

文献[12]的TSBL算法利用多观测向量的行相关结构, 将块稀疏贝叶斯学习 (block sparse Bayesian learning, BSBL) 框架应用于MMV模型中。令y=vec (YT) ∈RML×1 (vec为向量转换函数) , x=vec (XT) ∈RNcL×1, v=vec (VT) , D=ΦIL (是Kronecker积) , 这样MMV模型 (式 (15) ) 转变为块SMV模型:

假定噪声v为均值为0、方差为λ的高斯白噪声矩阵, x向量中的每个元素均为均值为0、方差为γiBi的高斯分布。

在接收信号y和超参数γi, Bi, λ已知的情况下, x满足均值为μx、方差为Σx的正态分布:

为了避免过拟合和减少参数量, 只使用一个B取代原来的Bi, 这样Σ0=ΓB。TSBL算法的参数更新公式见附录A。

x的最大后验估计由均值μx给出, 当TSBL算法收敛后得到x的稀疏解。

3 MIMO-PLC系统的脉冲噪声消除

假定MIMO-PLC系统中空子载波接收到的信号为z, z的数目为M, 定义, 则式 (8) 可以表示为:

3.1 使用全部子载波的TSBL-All算法

如果只使用空子载波来估计脉冲噪声, 系统性能将取决于空子载波数目M, 可以联合数据子载波来提高性能。这样原先的TSBL算法就需要引入这个均值, 从而联合估计信号Sx和噪声e, 将Sx送入后面的FEQ和解映射模块完成α的解调。TSBL算法中的μx和λ更新公式更改如下:

e的最大后验估计由均值μx给出, Sx在算法收敛后也由式 (21) 迭代出来。算法使用了全部Nc个子载波, MIMO-PLC脉冲噪声的相关性体现在B中。

3.2 使用全部子载波的FTSBL快速算法

虽然使用全部子载波的TSBL-All算法具有良好的消除噪声性能, 但是D为NcL×NcL维矩阵, 直接矩阵相乘复杂度较高。由于Φ=F为Nc点的DFT矩阵, 可以使用FFT来替代矩阵相乘, 同时利用DFT矩阵的特性来降低算法的复杂度。FTSBL快速算法的具体步骤如下 (公式的推导过程见附录B) 。

步骤1:初始化。各参数的初始值设置如附录B表B1所示。

步骤2:更新脉冲噪声X。K是输入脉冲噪声消除模块的信号, Sx是经过脉冲消除后得到的信号。Ξ供后面方差γi的更新使用。X的更新公式如式 (22) 所示。

步骤3:更新相关性矩阵B。为避免信号Sx在算法开始阶段时引入过多误差, 可以令B=IL, 当迭代次数Cnt超过Bcnt后更新B, 加入正则项ηIL以增强算法的鲁棒性。B的更新公式如下:W{i}=XiTXi, 若Cnt≤Bcnt, 则B=IL, ;否则

步骤4:更新脉冲噪声的方差γi, 如式 (23) 所示。

步骤5:更新高斯白噪声的方差λ, 如式 (24) 所示。

步骤6:更新消除脉冲噪声后的信号Sx=P, 更新Sx时需要将空子载波上的值清零。

步骤7:若信号Sx收敛或者迭代次数达到最大次数后, 则将经过脉冲消除后的信号Sx输出给后面的模块解调, 算法结束, 否则跳至步骤2。

3.3 FTSBL算法应用于传统的SISO-PLC系统

在实际应用中地线并不会完全存在, 比如线路老化, 而且已经有大量的SISO-PLC系统在使用, 因此应用于MIMO-PLC系统的FTSBL算法同样需要适合SISO-PLC系统。MIMO-PLC系统的FTSBL算法只在更新B和γi时需要多路数据联合计算, 其余均可并行处理, 所以SISO-PLC系统的FTSBL只需L=1, B=1, B^=1, γi=xi2+Ξi, 算法其他部分都改为向量运算。

4 算法复杂度分析

下面首先分析本文提出的使用全部子载波的FTSBL算法的计算复杂度, 并与TSBL-All算法、SOMP算法[13]、使用空子载波的SBL-Null算法[9]、使用全部子载波的SBL-All算法[9]、使用空子载波的TSBL-Null算法[12]、使用空子载波的MSBL算法[10]的计算复杂度进行比较。本文用实数加法 (RA) 、实数乘法 (RM) 、实数除法 (RD) 和矩阵求逆的操作次数来衡量算法的计算复杂度。一次复数乘法按4次RM和2次RA计算。一次基2的Nc点复数FFT/IFFT操作需要3 Nclog2Nc次RA和2 Nclog2Nc次RM。

应用于MIMO-PLC系统的FTSBL算法每次迭代需要12 Nclog2Nc+25 Nc+6次RA, 8 Nclog2Nc+13 Nc+4次RM, 4 Nc+4次RD和1次2×2的实数矩阵求逆。

在SISO-PLC系统中, FTSBL算法不再计算B, 其他操作和MIMO-PLC系统下的FTSBL类似, 需6 Nclog2Nc+11 Nc+1次RA, 4 Nclog2Nc+5 Nc+1次RM和Nc+1次RD。在MIMO-PLC和SISO-PLC系统中本文提出的FTSBL算法相比其他算法的低复杂度优势较为明显。MIMO-PLC和SISO-PLC系统下算法的计算复杂度分析见附录C。

5 实验结果及分析

仿真中使用正交相移键控 (QPSK) 调制, 全部子载波数目Nc=256, 其中空子载波数目M=100, 空子载波分布在频段两侧。MIMO-PLC系统仿真中脉冲噪声使用Bivariate Middleton Class A模型, 其参数为A=0.1, Γ1=Γ2=0.01, κ=0.5;SISO-PLC系统仿真中使用Middleton Class A模型, 其参数为A=0.1, Γ=0.01。信道模型使用平坦信道, 因为对于使用空子载波的算法, 估计噪声不受信道影响;对于使用数据子载波的算法, 由于存在预编码和均衡模块, 同时假定接收端和发射端都完全已知信道状态, 信道也不会对系统性能产生影响。

5.1 不同算法下系统的SER对比

图3和图4给出了使用脉冲噪声消除算法后MIMO-PLC和SISO-PLC系统的SER随信噪比 (SNR) 的变化情况。

图3中MIMO-PLC系统为达到4.8×10-3的SER, FTSBL和TSBL-All算法需要-5 dB的SNR, 而MSBL则需要6 dB的SNR, 因此在MIMO-PLC系统中本文提出的算法较MSBL算法有11dB的性能提升。使用FTSBL算法和TSBL-All算法时系统的SER差别不大, 当SER为3.2×10-5时两者所需SNR差别只有2dB。

图4中SISO-PLC系统的SER达到2.1×10-3, FTSBL算法需要0dB的SNR, 而SBL-All算法和SBL-Null算法分别需要5dB和10dB的SNR。由于在SISO-PLC系统中没有MIMO-PLC系统中的脉冲噪声相关性可利用, 随着SNR增加, FTSBL算法与SBL-All算法的SER差别逐渐缩小。

5.2 算法的收敛速度对比

图5和图6给出了SNR为0dB时, 使用脉冲噪声消除算法后MIMO-PLC和SISO-PLC系统的SER随迭代次数的变化情况。图5中MIMO-PLC系统TSBL-Null算法迭代30次后SER收敛到1.45×10-2, TSBL-All算法迭代60次后SER收敛到1.0×10-4, FTSBL算法迭代10次后SER收敛到4.6×10-4。FTSBL算法只在计算B和γ时引入相关性, 在迭代开始阶段不更新B, 从而提高了收敛速度。图6中SISO-PLC系统3种算法迭代10次后SER均收敛, FTSBL和另外两种算法相比, 系统的SER最小为2.1×10-3。

5.3 空子载波数目对系统性能的影响

图7和图8给出了SNR为0dB时空子载波数目对MIMO-PLC和SISO-PLC系统SER的影响情况, SER随空子载波数目M的减少呈近似指数增加。在MIMO-PLC系统中使用全部子载波的FTSBL算法和TSBL-All算法的系统SER小于TSBL-Null算法。在SISO-PLC系统中FTSBL算法的系统SER也小于其他两种算法。

5.4 脉冲噪声的相关性对MIMO-PLC性能的影响

图9显示了SNR为-10dB时MIMO-PLC系统的SER随相关系数κ的变化情况。由于TSBL和FTSBL算法引入了相关矩阵B, κ对系统的SER影响不大, 但是使用MSBL算法的系统的SER则随着κ的绝对值趋向1而显著增加。TSBL-All算法和其快速算法FTSBL在不同κ下系统的SER始终最小。

6 结语

本文基于SBL的理论, 利用脉冲噪声在电力线上的相关性, 使用全部子载波联合估计脉冲噪声和可用子载波上的信号, 较只使用空子载波的MSBL方案性能提升了11dB, 提高了MIMO-PLC系统对抗脉冲噪声的能力。

【贝叶斯学习】推荐阅读：

贝叶斯网络的在线学习05-15

学习感想-学习感想个人学习心得体会08-28

学习演讲稿2018：向雷锋学习与学习演讲稿：努力学习09-16