稀疏贝叶斯论文

稀疏贝叶斯论文（精选7篇）

稀疏贝叶斯论文 篇1

0 引言

电力系统是一个超大规模的动态非线性系统，因此它存在着许多稳定性问题，暂态稳定是其中最基本和最重要的问题之一。数值积分法、直接法和人工智能法是当前暂态稳定评估的3种主要方法。随着基于全球卫星定位系统(GPS)的广域测量技术———相量测量单元(PMU)广泛应用于电力系统，利用现代通信技术，完全可以同步跟踪到电力系统设备的动态变化相量，因此，近几年人工智能法在暂态稳定评估中的应用有了较快发展[1,2,3]。与传统方法相比，人工智能方法具有在线计算速度快、容易生成决策用的启发规则等优点，可与传统暂态稳定评估方法构成良好的互补。各国学者对基于人工神经网络(ANN)的暂态稳定评估技术进行了大量的研究，并取得很大进展[4];文献[5]对基于神经网络的暂态稳定评估进行了总结并给出了仿真结果;文献[6]利用BP(Back Propagation)网进行暂态稳定评估并对原始特征进行非线性变换提高预测精度;文献[7]利用改进的模糊神经网络Fuzzy Hyper-rectangular Composite ANN提高了暂态稳定的预测精度;文献[8]复合了Kohonen网络和径向基网络，结合这2种网络的优点提高了稳定评估能力;文献[9]结合了遗传算法，改进了BP神经网络的易陷入局部最小的问题。尽管神经网络在暂态稳定评估中的研究已经取得了显著进展，但是由于神经网络本身存在的结构局限性，如结构复杂、收敛速度慢、过适应以及较差的学习结果推广能力等，其在暂态稳定评估中的应用还只停留在研究阶段。

1995年，Vapnik博士在统计学习理论的基础上，提出了基于结构风险最小化归纳原则(SRM)的实用模型———支持向量机(SVM)，由于其具有理论完备性、小样本学习、良好的学习结果推广能力、支持向量的相对稀疏性、计算速度快、预测精度高等优点，短短几年时间支持向量机的研究和应用有了飞速发展，各种算法层出不穷，成为当前最流行的模式识别技术。支持向量机在暂态稳定评估的应用也有了较大发展，文献[10]将支持向量机应用于大规模电力系统中，其仿真结果远优于神经网络;文献[11]将支持向量机分类的输出划分为稳定类、不稳定类和边界区3类，减少了误分类;文献[12]对训练样本集先进行聚类分析预处理，然后利用支持向量机回归分别建立各聚类的预测模型，对发电机相对功角的变化趋势进行快速预测;文献[13]利用信息融合的思想构造多重支持向量机进行分类预测，提高了预测精度。

然而，支持向量机在实际应用中也存在一些问题，如：

a.无法得到概率式的预测;

b.使用者必须给定一个误差参数C，该参数对结果有很大的影响，且必须通过大量的交叉验证或附加算法来进行确定，费时费力;

c.核函数必须满足Mercer条件;

d.支持向量个数与训练样本数相比虽然具备一定的稀疏性，但是依然会随着训练样本数的增加而成线性增加，这一方面可能会造成过适应，另一方面会造成预测计算时间的增加。

1 支持向量机

在一般人工智能模式识别过程中，给出训练样本集包括输入向量{xn}Nn=1和与之相对应的目标{tn}Nn=1，其中，tn可以是某一实数(回归)或分类号(分类)。通过这些训练样本集的“学习”，期望得到一个模型能够从一个新的输入向量x*，得到未知的目标t*[14]。

支持向量机的思路是通过使用非线性变换把输入向量映射到一个高维特征空间中，在线性决策规则集合上按照正规超平面权值的模构造一个结构，并选择结构中最好的元素以及这个元素中最好的函数，从而达到最小化错误率的界目标。

支持向量机是基于如下函数来进行预测的：

其中，K(x,xi)是核函数，它是支持向量机的关键要素，算法利用求解二次规划问题的方法和满足Mercer条件的核函数内积的回旋，找到“最好的”权值ω，其中只有在xi为支持向量时其预测模型函数的ωi才为非零值相对提高了计算稀疏性，其具体算法见文献[15]。

2 基于稀疏贝叶斯学习的分类

2001年Michael E.Tipping博士在支持向量机预测函数式(1)的基础上，以基于概率学习的贝叶斯学习理论提出了其实用的算法模型：相关向量机(RVM)。该模型结合了马尔科夫性质(Markov’s)、贝叶斯原理(Bayes’s)、自动相关决定先验(ARD)和最大似然等理论，由于算法的高稀疏性和基于概率的学习特点，相关向量机不仅得到了很高的预测精度，而且与支持向量机相比大幅减少了核函数参与预测计算的数量，缩短了预测计算时间，并且可以提供概率性预测，自动参数设置和任意使用核函数等。下面描述其分类模型原理。

在两分类中，目标值{tn}Nn=1只可能为分类号0或1，在此引用分类问题常用的sigmoid函数对y(x;ω)写出概率函数：

假设每次观测的样本为独立事件，根据伯努力(Bernoulli)分布可以得到观测结果t的概率为

其中，N为样本总数。

为避免过适应(over-fitting)现象，相关向量机对ω加上先决条件，根据贝叶斯理论观点，限制ω的概率分布是落在0周围的标准正态分布：

其中，α=[α0，α1，α2，…，αN]T，则

对每个权值限定先决条件的方法，是相关向量机的一个重要特征，其中超权值α符合伽马分布，由于自动相关决定先验理论，经过足够多的更新后，大部分αi会趋近于无限大，其对应的ωi为0，而其他的αi会稳定地趋近有限值，而与之对应的xi就被称为相关向量，这也是实现相关向量机高稀疏特性的重要原因。

由于式(2)不是正态分布函数，无法直接求解定积分，在此套用拉普拉斯方法(Laplace’s methods)。

设超权值α已知，目标是求权值ω的最大值ωMP，根据delta近似函数需要求出：

根据逻辑对数似然函数：

其中，A=diag(α0，α1，…，αN),yi=σ[y(xi;ω)]。

一般可以通过牛顿方法(Newton’s method)很快找到ωMP。

超权值的更新是通过高斯函数来近似而这个高斯函数的中心位于偏微分后求等于零的解可以得到：

其中，为协方差矩阵，由海森矩阵H而来，

这样不断重复计算式(8)，同时不断地更新∑和ωMP，直到满足收敛要求，而且在不断计算过程中，大部分αi会趋近于无穷大，而与之相对应的ωMPi为0，这使得核函数矩阵Φ的大部分项不会参与到预测计算中[16,17,18,19]。就可利用最终得到的权值进行分类预测，即y*(x*;ωMP)=Φ(x*)ωMP。

由于需要重复计算和逆运算矩阵H，这需要O(N2)的存储空间和O(N3)的计算时间，在使用较大的样本训练集时，其耗费的训练时间要超过支持向量机的训练时间。针对这个问题，算法可以采用最大化边际似然函数原理(Marginal Likelihood Maximisation)进行改进，其关键点在于，它在训练过程中从空集开始不断扩充核函数矩阵Φ项，从而增大边际似然函数，在相同原理的框架内，同时通过去掉冗余的Φ项函数来增大目标函数。在具体算法实现中，由于相关向量机是解决最大边际似然函数找到其先验超权值αi，它等价于最大化其对数目标函数，而这种计算方式更加直观，即最大化目标函数Γ：

其中，C=ΦA-1ΦT，并定义C-i为C去掉相对应项的矩阵，为矩阵Φ(x)中一向量。

下面描述相关向量机的快速边际似然最大化算法步骤[26]。

步骤1初始化仅一项的核函数矩阵Φ，并计算αi，其他所有超权值αm全部假设为无限大。

步骤2分别计算∑和ωMP，并计算所有m个核函数矩阵相对应的判断值si和qi，计算公式如下式所示：

步骤3从所有核函数矩阵中选择一个候选

步骤4计算θi=qi2-si。

步骤5如果θi>0并且αi<∞，按原算法更新αi。

步骤6如果θi>0并且αi=∞，加入，重新按式(11)计算αi。

步骤7如果θi≤0并且αi<∞，删除，设置

步骤8按原算法更新计算∑和ωMP，并重新计算si和qi。

步骤9如果达到收敛条件则结束，否则转至步骤4。

3 暂态稳定评估的应用

以EPRI36 8机36节点全交流电系统为例进行暂态稳定评估的仿真。仿真计算条件为：发电机采用经典模型;不计调速器和励磁系统的作用;负荷采用恒定阻抗模型。故障方式为三相接地短路，故障发生后0.2 s切除，故障切除后线路自动重合闸成功，即故障前、后网络拓扑没有发生变化。在满足潮流计算的前提下以60%、80%、100%、110%和112.2%等5种不同的发电出力和负荷分布方式，每条线路均任意选择不同的故障位置，在上述条件下使用电力系统综合分析程序PSASP7.0仿真得到843个有效样本，其中稳定样本469个，失稳样本374个，稳定用“0”标号表示，失稳用“1”标号表示。为了对比仿真计算的结果，分别选取4种训练集方式，在Matlab 7.0编程环境下进行训练和预测计算：

a.方式1：任意100个样本为训练样本，剩下743个样本为测试样本。

b.方式2：任意200个样本为训练样本，剩下643个样本为测试样本。

c.方式3：任意300个样本为训练样本，剩下543个样本为测试样本。

d.方式4：任意400个样本为训练样本，剩下443个样本为测试样本。

电力系统暂态稳定评估是一个超大规模的动态非线性问题，需要考虑的特征空间一般分为静态特征和动态特征，静态特征又包括电网部分和发电机部分，动态特征又包括故障初始时刻和故障切除时刻。在此综合了文献[6,8,9,11,20,21,22,23,24,25]的经验和笔者仿真总结，为具备普遍适用性，选取能具体表征整个系统的特征值，而剔除那些会随着系统规模的增大而输入特征向量维数也随之增大的特征值作为输入向量。如表1所示，共17维。

在训练开始之前需要对输入向量的各特征值进行规范，以防止大数“淹没”小数以及大数计算上的困难。在此，变换过程采用“零-均值规范化”对任意属性M的值d，基于M的平均值和标准差σM进行规范化，使得M的值被规范化为d′，见式(12):

在相关向量机模型训练中，采用高斯核函数，与此同时，在相同的输入向量和其他同等条件下，也训练了核函数同样为高斯核函数的支持向量机模型，其误差参数采用了5次交叉验证法来确定，其结果对比见表2(n1为支持向量个数，n2为相关向量个数)。

结果显示，支持向量机仅在训练集方式4下准确度略高于相关向量机，而相关向量机在小样本学习的情况下具有更高的预测精度，并且更重要的是，在各训练集方式下，相关向量的个数都远远少于支持向量的个数，并且随着训练集的增加相关向量个数的增加并不明显。相关向量机这种高稀疏度远远优于支持向量机，仅使用极少数的训练集相关向量就能得到非常好的预测精度，预测计算中所消耗的时间大幅减少，为实时预测打下了良好的基础。

除此之外，更加具有实用价值的是：由于相关向量机的概率预测特性，还可以从中得到支持向量机无法得到的概率性预测，而概率性预测往往是实际应用中最希望解决的问题之一。由式(2)可以得到结果的概率性预测，图1显示了训练集方式2下测试样本的概率预测结果(n为测试样本数)。

从图1中可以很清晰地看到预测结果的概率性预测，虽然无法通过图形对高达17维的空间进行表述，但通过概率性预测可以很直观地观察到结果的准确情况，从而形成不同级别的控制策略。还可以通过概率选取预测结果的不确定区域，如图中显示概率为0.25～0.75区间，可以作为分类的不确定区单独作为一类，这在实际应用中不仅提高了预测精度，而且更有利于系统工程的冗余控制。这种概率性的预测结果，是相关向量机在实际应用中的最大优势之一，它不仅可以给出了一个“硬”的分类，而且还能给出这个“硬”分类的趋势程度。这也是其他模式识别技术所欠缺的，而相关向量机这种基于概率学习的方式很好地解决了这个难题。

4 结论

从本文暂态稳定评估的例子中，可以发现，相关向量机的分类应用有着许多优势。

a.超高的稀疏性，使用极少的相关向量就能得到很高的预测精度，并且预测计算时间大幅减少;

b.概率特性的预测，对分类值的概率性结果进行预测;

c.不用事先定义误差参数，大幅节约了数据处理时间，提高了预测精度;

d.可任意使用不同的核函数，而支持向量机中核函数必须满足Mercer条件。

综上所述，相关向量机在电力系统预测控制中有着非常广阔的应用前景。特别是其概率性预测和超高的稀疏性所带来的快速计算特点，对电力系统在线计算和分级控制策略的形成有着非常大的实用价值。相关向量机的算法研究也必将掀起新一轮的模式识别技术的研究热潮。

摘要：介绍了基于稀疏贝叶斯学习理论的模式识别技术相关向量机及其分类器,在此基础上构建了电力系统暂态稳定评估模型。以EPRI36电力系统暂态稳定仿真数据为例,在相同的数据输入和相同的仿真环境下同时构建相关向量机和支持向量机2种暂态稳定评估模型。仿真预测计算显示,作为一种全新的概率学习模型,相关向量机不仅得到了比支持向量机更高的预测精确度,而且还能得到支持向量机无法完成的概率性预测和更高的稀疏性计算。

关键词：概率学习,贝叶斯理论,相关向量机,支持向量机,暂态稳定评估

稀疏贝叶斯论文 篇2

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

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系统对抗脉冲噪声的能力。

贝叶斯网络模型概述 篇3

1 贝叶斯网络模型的描述

贝叶斯网络(BN),又称为信度网,由一个有向无环图(Directed Acylic Graph,DAG)和条件概率表(Conditional Probability Table,CPT)组成[1]。

贝叶斯网络分类模型(BNC)的形式化的描述如下:

n元随机变量X={X1,X2,…Xn}的贝叶斯网络模型是一个二元组B=(Bs,Bp)。Bs=(X,E)是一有向无环图(directed acrylic graph,DAG),其中X={X1,X2,…Xn}为结点集,每个结点可看成取离散或连续值的变量(本文限定其只取离散值);E是有向边的集合,每条边表示两结点间依赖关系,依赖程度由条件概率参数决定。称Bs为BN模型网络结构。Bp={P(Xi/∏Xi),Xi∈X}是贝叶斯网络模型的一组条件概率分布的集合。在各结点取离散值的情况下,BP为一组条件概率表(conditional probability tables,CPTs)的集合。∏Xi是在Bs中Xi所有父结点的集合,表示结点Xi在其父结点某一取值组合状态下的条件概率分布。这说明,在贝叶斯网络模型中,结点的取值依赖于其父结点的取值状态。

这里,学习贝叶斯网络的问题描述为:给定Xi中的一组实例构成的训练集合D=X={X1,X2,…Xn},找到一个与D匹配最好的网络B。这样,学习贝叶斯网络的问题转化为优化问题。这时类变量和属性变量不加区别。

实际处理这个问题的方法是在可能的网络构成的空间中进行启发式搜索。搜索成功的关键是确定一个合理的评分函数,评价网络对训练数据的匹配程度,以指导搜索。

有两种主要的评分函数[2]:贝叶斯评分函数和最小描述长度原理(MDL:minimal description length)评分函数。它们是渐进正确的,即随着样本数目的增加,得分最高的网络将任意逼近样本的概率分布。

2 构造贝叶斯网络的方式

一般情况下,构造贝叶斯网有三种不同的方式:

(1)由领域专家确定贝叶斯网的变量(有时也称为影响因子)节点,然后通过专家的知识来确定贝叶斯网络的结构,并指定它的分布参数。这种方式构造的贝叶斯网完全在专家的指导下进行,由于人类获得知识的有限性,导致构建的网络与实践中积累下的数据具有很大的偏差。

(2)由领域专家确定贝叶斯网络的节点,通过大量的训练数据,来学习贝叶斯网的结构和参数。这种方式完全是一种数据驱动的方法,具有很强的适应性,而且随着人工智能、数据挖掘和机器学习的不断发展,使得这种方法成为可能。如何从数据中学习贝叶斯网的结构和参数,已经成为贝叶斯网络研究的热点。

(3)由领域专家确定贝叶斯网络的节点,通过专家的知识来指定网络的结构,而通过机器学习的方法从数据中学习网络的参数。这种方式实际上是前两种方式的折衷,当领域中变量之间的关系较明显的情况下,这种方法能大大提高学习的效率。

可以看出,在由领域专家确定贝叶斯网络的节点后,构造贝叶斯网的主要任务就是学习它的结构和参数。很显然,学习结构和参数不是完全独立的。一方面节点的条件概率很大程度上依赖于网络的拓朴结构;另一方面,网络的拓朴结构直接由联合概率分布的函数来决定。

然而,一般情况下,我们还是把这两个方面分开来进行。这是因为,带有太多连接的复杂网络结构所需观测的参数较多,而为使获得这些参数达到某种信任程度所需的数据量随着参数数目的增加而迅速增长,并且复杂的结构需要太大的存储空间及冗长繁琐的计算过程才能产生预测和解释。因此,为使贝叶斯网作为知识模型是可用的,在学习过程中致力于寻找一种最简单的网络结构是非常必要的,这种简单的结构模型称之为稀疏网络,它含有最少可能的参数及最少可能的依赖关系。

根据构成贝叶斯网络的结点变量是离散的变量且取有限个值或是连续的变量或是既有连续变量又有离散变量三种不同情况,贝叶斯网络的类型可以分为离散型、连续型、混合型三种[3]。

近年来,关于贝叶斯网络的理论研究重点集中于贝叶斯网络的结构学习和参数学习方面。结构学习是指对于每一特征节点找到除根节点之外的所有父节点,参数学习是指在己知结构的基础上获得上述参数的估计。

当我们在贝叶斯网络中把其中代表类别变量的节点作为根节点,其余所有变量都作为它的子节点时,贝叶斯网络就变成了分类器[4]。

3 贝叶斯网络模型的优点

通过提供图形化的方法来表示和运算概率知识,贝叶斯网络克服了基于规则的系统所具有的许多概念上和计算上的困难。贝叶斯网络与统计技术相结合,使得其在数据分析方面拥有了许多优点,与规划挖掘、决策树、人工神经网络、密度估计、分类、回归和聚类等方法相比,贝叶斯网络的优点主要体现在:

(1)贝叶斯网络使用图形的方法描述数据间的相互关系,语义清晰,易于理解。图形化的知识表示方法使得保持概率知识库的一致性和完整性变得容易,可以方便地针对条件的改变进行网络模块的重新配置。

(2)贝叶斯网络易于处理不完备数据集。对于传统标准的监督学习算法而言必须知道所有可能的数据输入,如果缺少其中的某一输入就会对建立的模型产生偏差,贝叶斯网络的方法反映的是整个数据库中数据间的概率关系模型,缺少某一数据变量仍然可以建立精确的模型。

(3)贝叶斯网络允许学习变量间的因果关系。在以往的数据分析中,一个问题的因果关系在干扰较多时,系统就无法做出精确的预测。而这种因果关系己经包含在贝叶斯网络模型中。贝叶斯方法具有因果和概率性语义,可以用来学习数据中的因果关系,并根据因果关系进行学习。

(4)贝叶斯网络与贝叶斯统计相结合能够充分利用领域知识和样本数据的信息。贝叶斯网络用弧表示变量间的依赖关系,用概率分布表来表示依赖关系的强弱,将先验信息与样本知识有机结合起来,促进了先验知识和数据的集成,这在样本数据稀疏或数据较难获得的时候特别有效。

4 小结

贝叶斯推断理论提供一种概率手段,为数据建模提供了一个统一的框架,而且它为算法的分析提供了理论基础。尽管关于贝叶斯网的理论研究还很不完善,应用研究还处于起步阶段,但在许多领域中已显现出令人瞩目的效果,可以预见随着技术的进步,贝叶斯网模型将发挥越来越重要的作用。

参考文献

[1]张少中,王秀坤,孙莹光.贝叶斯网络及其在决策支持系统中的应用[J].计算机工程,2004.30(10):1-3.

[2]胡玉胜,涂序彦,崔晓瑜,程乾生.基于贝叶斯网络的不确定性知识的推理方法[J].计算机集成制造系统.2001.7(12):65-68.

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

贝叶斯网络推理算法研究 篇4

现代大型复杂系统的贝叶斯网络结构也是庞大复杂的,对于诊断推理存在困难。因此在进行诊断推理前,应适当地对其网络结构进行简化。本文采用分簇优化联合树算法对贝叶斯网络结构进行简化处理及推理运算,下面介绍分簇优化联合树算法及其用于网络参数学习及诊断推理算法。

1 分簇搜索算法基本思想

用于故障诊断的贝叶斯网络的结构是非常复杂的,并且由于其结构的复杂性致使故障诊断推理也非常复杂,因此,通过贝叶斯网络结构学习,寻找一个与训练数据拟合度高且网络复杂性相对较低的网络结构成为一个非常有意义和研究价值的问题。由式可知,n个变量构成的贝叶斯网络结构的数目是指数级的,要从这些可能存在的网络结构空间中搜索出最优的网络结构也是很难的。当n=10时,需要搜索的模型个数就已经达到约为4.17*1018,可见搜索空间太大,为了缩小搜索空间,有效地找到最优解,一个较好的搜索算法就非常必要。

贝叶斯网络结构的学习实际就是优化搜索的问题。基于分簇的优化搜索方法就是将问题节点划分为团簇结构。团簇结构思想最早用于物理和化学领域中对分子和原子的处理,而在近代,团簇结构在许多领域得到了广泛的应用,包括模式识别,数据分析,图像处理等。许多学者都在这方面做出了研究,旨在发现能够用于更好聚类方法的簇结构,不同的网络拓扑结构对于分簇算法都是不同的。人工智能越来越多地研究这种方法,使之成为一种较为优秀的搜索算法。基于簇的搜索方法被证实较好地用于解决TSP问题。这种方法的主要优势在于不会陷入局部最优,并且搜索时间非常短。

分簇算法的基本思想是把网络结构中的节点划分为若干个簇,簇内依据某种事先约定的值进行连接,在簇与簇之间,也根据这种约定进行点与点之间的连接,这里设定一个阀值,节点间的关联程度大于这个阀值时就连接这两个节点,最终基于簇的这种搜索算法将形成一个团簇树状结构。

基于簇的结构学习算法是由初始的贝叶斯网络结构经过优化搜索构造出用于诊断的树形结构。设用于该算法的阀值为θ,由当前信息得到相关节点的关联程度为θij,表示第i个节点和第j个节点的关联程度,设两个数据结构D 1,D 2分别存放局部网络的起始参数节点表和目标节点表,首先把网络的所有节点都放入D 1表中。具体的步骤如下:

步骤1:随即选取一个起始节点V1,比较与V1相关的各个节点的θ1k值,若θ1k≥0,则将V1和Vk划分到一个簇S1内,把簇S1中的节点都从D1表中移出,放入表D2中。

步骤2:如果D1为空表,则转到步骤4。

步骤3:在D1表中随即选取一个节点Vn,比较与Vn相关的各个节点,分两种情况:

(1)若无关联节点,则将Vn单独划分到簇S2中,并将节点Vn从表D1中移出,放入表D2中,转入步骤2。

(2)若有关联的节点,且关联值为θnm,若θnm≥0,则将Vn和Vm划分到一个簇S2中,把簇S2中的节点从D1表中移出,放入表D2中,转入步骤2。

步骤4:在簇到S1之Sn间,观察是否簇间有相关联的节点,若相关联,且关联值θij≥θ,则将Vi与Vj相连接。

该算法的最终目的是搜索出一个较为简单的网络结构,减少网络推理的复杂度,使学习后的网络结构能够使用精确推理算法来实现推理,得出一个较为准确的结果。

搜索的过程如图1所示。

从图1可以看出,在经过分簇搜索之后,网络结构(d)比网络结构(a)有了一定程度的简化。

有效的贝叶斯网络推理算法是贝叶斯网络的重要内容,也是其应用的前提。大型复杂的故障诊断系统,所建立的贝叶斯网络模型也具有非常复杂的结构,为了降低贝叶斯网络的推理复杂度,使其更容易应用于解决实际问题,一般的推理算法都是在简化网络结构上进行研究的。下面来分析经过分簇结构优化算法后的网络推理。

2 联合树推理

分簇优化联合树算法实现对贝叶斯网络的诊断推理。分簇优化联合树算法是分簇优化算法与联合树算法的结合,其流程图如图2所示。分簇优化已在前文介绍,下面介绍流程图中其余步骤。

2.1 贝叶斯网络转化为联合树

将贝叶斯网络B转化为联合树,分为四步:建立B的Moral图;三角化Moral图;确定所有的团(Cliques);建立联合树。

(1)建立B的Moral图

简历Moral图的过程就是找出每个节点的父节点,并将他们用无相边两两相连,同时将所有有向边改为无向边。

(2)三角化Moral图

在Moral图中添加一些无向边,使图中每个大于或等于4的环中,都存在一条边连接两个非相邻节点。这就完成了对Moral图的三角化。

(3)确定所有的团(Cliques)

对Moral图三角化的目的就是找到构成联合树的所有团。团是Moral图三角化后最大的全连通子图,团中每对不同的节点都有边相连。

(4)建立联合树

利用得到的团,添加一些边和分隔节点就可构造一棵联合树T。联合树T要满足:树中任意两个团C,C′在连接它们的路径上的所有团节点必须包含变量C∩C′。

2.2 初始化

将贝叶斯网络转化为联合树后,就要对联合树的所有节点指定参数,即对联合树进行初始化。下面的算法实现了对满足条件的联合树参数的指定。

若联合树中的团Ci由X1,X2,…,Xr,r个节点组成,每一个节点有Sr个状态,则共有个状态组合。i代表Ci的分布函数,ij代表图Ci第j个状态组合的分布函数。具体步骤是:

for一个随机变量V

找到包含V的家庭的团Ci;

fori=1,…,n(n为团的数目)

orj=1,…,m(m为团C状态组合的个数)

初始化Φij,使Φij=1;

forj=1,…,m

Φij=Φij*P(Vj|Pa(Vj))

2.3 消息传递

对联合树进行初始化后,要在联合树上进行消息传递。通过个团节点之间的消息传递,可以是联合树达到全局一致,即达到稳态。如图3所示是团节点间一次消息传递的过程。

从节点Ci到Cj的一次消息传递过程包括以下几步:

(1)产生消息:

(2)吸收信息,更新团结点的分布函数:

(3)更新分隔节点的分布函数:

2.4 概率计算

当一个联合树通过消息传递满足全局一致性后,即可计算任意随机变量V的概率分布。找到任意一个包含变量V的团节点C,通过可计算出变量V的分布。

2.5 加入证据

若有新的证据加入,重复证据收集和证据扩散的过程,直到得到全局一致的联合树为止。当联合树再次满足全局一致性时,对任意的团C有:C=P(C,e),(e表示加入的证据)。要计算假设的变量V的概率分布,首先找到任意一个包含变量V团结点C,,再根据条件概率公式,求出变量V的概率分布

3 结束语

有效的贝叶斯网络推理算法是贝叶斯网络的重要内容,也是其应用的前提。大型复杂的故障诊断系统,所建立的贝叶斯网络模型也具有非常复杂的结构,为了降低贝叶斯网络的推理复杂度,使其更容易应用于解决实际问题,一般的推理算法都是在简化网络结构上进行研究的。而分簇简化联合树算法在对网络结构简化之后再进行网络推理,一定程度上简化了网络推理的难度。

摘要：大型复杂贝叶斯网络的诊断推理存在困难,在其推理诊断之前对网络结构进行适当的简化,可以有效地加快诊断推理速度。采用分簇联合树算法实现对网络结构的简化与推理。主要介绍了分簇搜索算法的基本思想、实现步骤及联合树推理算法,并将它们结合使用,使贝叶斯网络的简化推理更有效。

关键词：贝叶斯网络,概率推理,分簇理论,联合树

参考文献

[1]Wang Weidong,Zhu Qingxin.A Hierarchical Clustering Algorithmand Cooperation Analysis for Wireless Sensor Networks[J].Journalof Software,2006,17(5):1157-1167.

[2]Stephenson T.A.An Introduction to Bayesian Network Theory andUsage[Z].IDIAP-PR,Feb,2000.

[3]Gregory F Cooper,Edward Herskovits.A Bayesian method for theinduction of probabilistic networks from data[J].Machine Learning(S0885-6125),1992,9(4):309-347.

[4]衡星辰,覃征,邵利平,等.动态贝叶斯网络在复杂系统中建模方法的研究[J].系统仿真学报,2006,18(4):1002-1005.

[5]邢永康.信度网理论及应用研究:[D].重庆:重庆大学,2001.

贝叶斯网络诱导的内积空间 篇5

将贝叶斯网络与核函数结合起来,综合两者的优势,这一方法被广大研究者充分重视。如文献[4,5,6]提出了隐性马尔可夫模型的核函数,文献[7]提出了新的结合概率模型和核函数的方法。一个给定的贝叶斯网络诱导的概念类(即决策函数的类),在数据点集或者超平面中,线性分类器的误差边界多以欧几里德维数或几何边际的形式给出。应用随即投影技术,文献[8,9,10]给出了任意具有较大边际的线性排列可转化为维数较低的线性排列,文献[11]讨论了在允许一定误差的条件下,低维的线性排列;给出了维数较小的线性分类器存在较大边际的结论。文献[12]讨论了在欧几里德半空间里,VC维为常数的概念类的最大边际问题;文献[13]讨论了在布尔域上的贝叶斯网络的计算模型,给出了一般贝叶斯网络诱导的概念类维数的上下界。

文中讨论了将贝叶斯网络作为计算模型,变量在布尔域上取值的两类分类任务的问题。重点研究了几类常见贝叶斯网络,讨论了可以表示该贝叶斯网络诱导的概念类的最简单的内积空间,(这里“最简单”是指内积空间的维数尽可能低。)集中在具有标准点乘定义的欧几里德内积空间来讨论。文中通过分析概念类的VC维来确定贝叶斯网络维数的下界,同时VC维可用于估计贝叶斯网络诱导的概念类的复杂性,也可用于判断概念类的分类性能,VC维也被广泛的应用于其它领域,如模式识别、神经网络等。

1 预备知识

定义1 区域X中的一个概念类C是指一族函数f∈C,∀x∈X,有f(x)=1或f(x)=-1。

一个有限集合S={s1,…,sm}⊆X称作被概念类C可分是指对任意m维向量b∈{1,-1}m,存在概念类f∈S,使得f(si)=bi,(i=1,…,m)。

概念类C的Vapnik-Chervonenkis(VC)维指$\mathit{V}\mathit{C}\dim (\mathit{C})=\sup \{m|\mathit{S}\subseteq \mathit{X},\mathit{S}$被C可分,且$\left|\mathit{S}\right|=m\}$。

定义2 一个贝叶斯网络N满足

(1)有向无圈图G=(V,E),V表示有限点集,E⊆V×V表示边的集合;

(2) 参数(pi,α)i∈V,a∈{0,1}mi∈(0,1),其中mi表示节点i的父节点的个数,即$m{}_i=\left|\{j\in \mathit{V}|(j,i)\in \mathit{E}\}\right|$;

(3) 可以将(0,1)中的某些值赋给集合中的参数,这样的约束是被允许的。

Pi表示节点i的父节点的集合,则$m{}_i=\left|\mathit{{\rm P}}{}_i\right|$,且完全连接图N是指对每一个节点i有Pi={1,…,i-1}。

定义3 由n个节点构成的贝叶斯网络图,其分布诱导的类记作DN,当每个节点在布尔域上取值时,其分布为

${\rm P}(x)={\displaystyle \prod _{i=1}^n{\displaystyle \prod _{\alpha \in \{0,1\}{}^{m{}_i}}p}}{}_{i,\alpha }^{x{}_i{\rm M}{}_{i,\alpha }(x)}(1-p{}_{i,\alpha }){}^{(1-x{}_i){\rm M}{}_{i,\alpha }(x)}$ (1)

其中,${\rm M}{}_{i,\alpha }(x)={\displaystyle \prod _{j\in {\rm P}{}_i}x}{}_j^{\alpha {}_j}$,且x0 j=1-xj,x${}_j^1$=xj。

定义4 由n个节点构成的贝叶斯网络图N,DN为其导出的分布类,由网络N诱导的概念类CN是指形式为sign$\left(\log \frac{{\rm P}(x)}{Q(x)}\right)$的一族函数,其中x∈{0,1}n,P(x),Q(x)∈DN。

定义5 在X域上的概念类C的d维线性排列是指存在d维向量(uf)f∈C和(vx)x∈X使得∀f∈C,x∈X∶f(x)=sign(uTfvx),在概念类C的d维线性排列中,最小的d记作E dim(C)。

如果概念类CN是由贝叶斯网络N导出的,则可以用E dim(N)替代E dim(C)。

引理1[13] 任一个概念类C满足E dim(C)≥VC dim(C)。

引理2[13,14,15] 任一个由n个节点构成的,变量在布尔域上取值的贝叶斯网络N,满足

${\displaystyle \sum _{i=1}^{n}2}{}^{m{}_i}\le \mathit{E}\dim (\mathit{{\rm N}})\le \left|{\displaystyle \underset{i=1}{\overset{n}{\cup }}2}{}^{\mathit{{\rm P}}{}_i{\displaystyle \cup \{}i\}}\right|\le 2{\displaystyle \sum _{i=1}^{n}2}{}^{m{}_i}$ (2)

2 当变量在布尔域上取值时,几个常见贝叶斯网络的维数

定理1 在布尔域上取值的n个节点构成的贝叶斯网络图Nk,结构如图1所示,则E dim(Nk)=n+k+1。

证明:由引理2知贝叶斯网络图NkE dim的下界

${\displaystyle \sum _{i=1}^{n}2}{}^{m{}_i}=1+{\displaystyle \sum _{i=2}^{k+1}2}+{\displaystyle \sum _{i=k+2}^{n}1}=n+k$ (3)

上界${\displaystyle \underset{i=1}{\overset{n}{\cup }}2}{}^{{\rm P}{}_i{\displaystyle \cup \{}i\}}={\displaystyle \underset{i=2}{\overset{k+1}{\cup }}\{}J{}_i|\subseteq \{A{}_1,A{}_i\}\}{\displaystyle \underset{i=k+2}{\overset{n}{\cup }}\{}A{}_i\}$ (4)

所以$\left|{\displaystyle \underset{i=1}{\overset{n}{\cup }}2}{}^{{\rm P}{}_i{\displaystyle \cup \{}i\}}\right|=n+k+1,n+k\le \mathit{E}\dim (\mathit{{\rm N}}{}_k)\le n+k+1(5)$

集合S:当j=1,…,n,eoj表示第j个分量为1,其余分量为0的n维向量;e11表示所有分量为1的n维向量,当i-2,…,k+1时,e1j表示第1个和第j个分量为1,其余分量为0的n维向量。则$\left|\mathit{S}\right|=n+k+1$。

$\log \frac{{\rm P}(x)}{Q(x)}x{}_1\log \frac{p{}_1}{q{}_1}+(1-x{}_1)\log \frac{1-p{}_1}{1-q{}_1}+{\displaystyle \sum _{i=2}^n{\displaystyle \sum _{\alpha \in \{0,1\}}(}}x{}_i{\rm M}{}_{i\alpha }(x)\log \frac{p{}_{i\alpha }}{q{}_{i\alpha }}+(1-x{}_i){\rm M}{}_{i\alpha }(x)\log \frac{1-p{}_{i\alpha }}{1-q{}_{i\alpha }})(6)$

当i=0,1,j=1,2,…,n,eij∈S时,令eij=(aij1,aij2,…,aijn),S的二分集合为(S-,S+)

$\text{当}m=1,2,\cdots ,n\text{时}\{\begin{array}{l}p{}_{m\alpha }^{ij}=\frac{1}{2},a{}_{ij{}_m}=1,\text{当}\mathit{e}{}_{ij}\in \mathit{S}{}^{+}\\ p{}_{m\alpha }^{ij}=2{}^{-2{}^{m-1}n}/2,\text{其}\text{他}\end{array}$

$\{\begin{array}{l}q{}_{m\alpha }^{ij}=2{}^{-2{}^{m-1}n}/2,\text{当}a{}_{ij{}_m}=1,e{}_{ij}\in \mathit{S}{}^{+}\\ q{}_{m\alpha }^{ij}=\frac{1}{2},\text{其}\text{他}\end{array}$

则$\left|\log \frac{p{}_{m\alpha }^{ij}}{q{}_{m\alpha }^{ij}}\right|=2{}^{m-1}n,\left|\log \frac{1-p{}_{m\alpha }^{ij}}{1-q{}_{m\alpha }^{ij}}\right|＜1$。若i=0,且当e0 j∈S+,J∈{1,…,n}时

$\log \frac{p(\mathit{e}{}_{0j})}{q(\mathit{e}{}_{0j})}=\log \frac{p{}_{j\alpha }^{0j}}{q{}_{j\alpha }^{0j}}+{\displaystyle \sum _{\begin{array}{l}i=1\\ i\ne j\end{array}}^n}{\displaystyle \sum _{\alpha \in (0,1)}{\rm M}}{}_{i\alpha }(x)\log \frac{1-p{}_{i\alpha }^{0j}}{1-q{}_{i\alpha }^{0j}}$ (7)

$\log \frac{p{}_{j\alpha }^{0j}}{q{}_{i\alpha }^{0j}}=2{}^{j-1}n,\left|{\displaystyle \sum _{\begin{array}{l}i=1\\ i\ne j\end{array}}^n}{\displaystyle \sum _{\alpha \in (0,1)}{\rm M}}{}_{i\alpha }(x)\log \frac{1-p{}_{i\alpha }^{0j}}{1-q{}_{i\alpha }^{0j}}\right|＜n-1,2{}^{j-1}n-(n-1)＞0$,则sign$\left(\log \frac{{\rm P}(\mathit{e}{}_{0j})}{Q(\mathit{e}{}_{0j})}\right)=1$。若i=1,j=1即e11∈S+时,$\log \frac{{\rm P}(x)}{Q(x)}={\displaystyle \sum _{i=1}^{n}2}{}^{i-1}n=n(2{}^n-1)＞0$。若i=1,j∈{2,…,k+1},e1j∈S+时

$\log \frac{{\rm P}(x)}{Q(x)}=\log \frac{p{}_1^{1j}}{q{}_1^{1j}}+\log \frac{p{}_{j1}^{1j}}{q{}_{j1}^{1j}}+{\displaystyle \sum _{\begin{array}{l}i=2\\ i\ne j\end{array}}^n}{\displaystyle \sum _{\alpha \in \{0,1\}}{\rm M}}{}_{i\alpha }(x)\log \frac{1-p{}_{i\alpha }^{1j}}{1-q{}_{i\alpha }^{1j}}(8)$

$\begin{array}{l}\log \frac{p{}_1^{1j}}{q{}_1^{1j}}=n,\log \frac{p{}_{j1}^{1j}}{q{}_{j1}^{1j}}=2{}^{j-1}n,|{\displaystyle \sum _{\begin{array}{l}i=1\\ i\ne j\end{array}}^n}{\displaystyle \sum _{\alpha \in (0,1)}{\rm M}}{}_{i\alpha }(x)\log \\ \frac{1-p{}_{i\alpha }^{1j}}{1-q{}_{i\alpha }^{1j}}|＜n-1,\text{s}\text{i}\text{g}\text{n}\left(\log \frac{{\rm P}(x)}{Q(x)}\right)=1。\end{array}$

综上所述,对任意二分集合(S-,S+),存在P(x),Q(x)使得当eij∈S+时,f(eij)=1当eij∈S-时,f(eij)=-1。由引理1知E dim(Nk)=n+k+1。

定理2 在布尔域上取值的n个节点的构成完全连接的贝叶斯网络图NF,则 VC dim(NF)=2n-1。

证明:由文献[13]中的定理17知,

$\mathit{V}\mathit{C}\dim (\mathit{{\rm N}}{}_F)\ge {\displaystyle \sum _{i=1}^{n}2}{}^{i-1}=2{}^n-1$ (9)

先证VC dim(NF)≤2n-1:

当n=2时,$\log \frac{{\rm P}(x)}{Q(x)}=x{}_1\log \frac{p{}_1}{q{}_1}+(1-x{}_1)\log \frac{1-p{}_1}{1-q{}_1}+x{}_2(1-x{}_1)\log \frac{p{}_{20}}{q{}_{20}}+(1-x{}_2)(1-x{}_1)\log \frac{1-p{}_{20}}{1-q{}_{20}}+x{}_{2}x{}_1\log \frac{p{}_{21}}{q{}_{21}}+(1-x{}_2)x{}_1\log \frac{1-p{}_{21}}{1-q{}_{21}}(10)$

当b=(1,1,1,1)时,即

$\{\begin{array}{l}\log \frac{p{}_1}{q{}_1}+\log \frac{p{}_{21}}{q{}_{21}}＞0\\ \log \frac{p{}_1}{q{}_1}+\log \frac{1-q{}_{21}}{1-q{}_{21}}＞0\\ \log \frac{1-p{}_1}{1-q{}_1}+\log \frac{p{}_{20}}{q{}_{20}}＞0\\ \log \frac{1-p{}_1}{1-q{}_1}+\log \frac{1-p{}_{20}}{1-q{}_{20}}＞0\end{array}$

(11)

由于当$\log \frac{p{}_i}{q{}_i}＞0$时,$\log \frac{1-p{}_i}{1-q{}_i}＜0$,分析可知式(11)不能同时成立,所以当然n=2时,VC dim(N′F)=22-1=3。

假设当n=k时,不存在P(x),Q(x)使得$f(s{}_i)=b{}_i,\mathit{S}=\{s{}_i|s{}_i\in \{0,1\}{}^n,i=1,\cdots ,2{}^k\},\mathit{b}=(b{}_1,b{}_2,\cdots ,b{}_{2{}^k})=(1,1,\cdots ,1)\in \{-1,1\}{}^{2{}^k}$

当n=k+1时,若存在P′(x),Q′(x)使得$\mathbf{f}({\mathbf{s}}^{\prime }{}_{\mathbf{i}})={\mathbf{b}}^{\prime }{}_{\mathbf{i}},{\mathit{S}}^{\prime }=\{s^{\prime }{}_i|s^{\prime }{}_i\in \{0,1\}{}^n,i=1,\cdots ,2{}^{k+1}\},\mathit{b}=(b^{\prime }{}_1,b^{\prime }{}_2,\cdots ,b^{\prime }{}_{2{}^{k+1}})=(1,1,\cdots ,1)\in \{-1,1\}{}^{2{}^{k+1}}$

$\log \frac{{{\rm P}}^{\prime }(x)}{Q^{\prime }(x)}={\displaystyle \sum _{i=1}^k{\displaystyle \sum _{\alpha \in \{0,1\}{}^{i-1}}x}}{}_i{\rm M}{}_{i\alpha }(x){}_i{\rm M}{}_{i\alpha }(x)\log \frac{p{}_{i\alpha }}{q{}_{i\alpha }}{\rm M}{}_{i\alpha }(x)\log \frac{1-p{}_{i\alpha }}{1-q{}_{i\alpha }}(12)$

在式(12)中,若$\log \frac{p{}_{(k+1)\alpha }}{q{}_{(k+1)\alpha }}＞0$,则$\log \frac{1-p{}_{(k+1)\alpha }}{1-q{}_{(k+1)\alpha }}＜0$,由于α′∈{0,1}k,则对任意$s{}_i\in \mathit{S},{\displaystyle \sum _{i=1}^k{\displaystyle \sum _{\alpha \in \{0,1\}{}^{i-1}}x}}{}_i{\rm M}{}_{i\alpha }(x)\log \frac{p{}_{i\alpha }}{q{}_{i\alpha }}+(1-x{}_i){\rm M}{}_{i\alpha }(x)\log \frac{1-p{}_{i\alpha }}{1-q{}_{i\alpha }}＞0$,与前面n=k时,不存在P(x),Q(x)使得f(si)=bi矛盾。

所以当n=k+1时,也不存在P′(x),Q′(x),使得f(s′i)=b′i,s′i∈S′,bi=1,i=1,…,2k+1

同样,当b=(-1,-1,…,-1)∈{-1,1}2k+1时,也不存在P′(x),Q′(x),使得f(s′i)=b′i

定理3 在布尔域上取值的n个节点构成的完全连接的贝叶斯网络图NF,则E dim(NF)=2n-1

证明:由定理2和引理1知E dim(NF)的下界为2n-1,由文献[13]的结论18知E dim(NF)的上界

${\displaystyle \underset{i=1}{\overset{n}{\cup }}2}{}^{\mathit{{\rm P}}{}_i{\displaystyle \cup \{}i\}}={\displaystyle \underset{i=1}{\overset{n}{\cup }}\{}J{}_i|J{}_i\subseteq \{A{}_1,A{}_2,\cdots ,A{}_i\}\}=\{J|J\subseteq \{A{}_1,A{}_2,\cdots ,A{}_n\}\}(13)$

$\left|{\displaystyle \underset{i=1}{\overset{n}{\cup }}2}{}^{\mathit{{\rm P}}{}_i{\displaystyle \cup \{}i\}}\right|=2{}^n$,即2n-1≤E dim(NF)≤2n

现在证明存在uf,vx∈R2n-1,使得对任意f∈C,x∈X∶f(x)=sign$(u{}_{f}v{}_x),\mathit{S}=\{x{}_1,x{}_2,\cdots ,x{}_{2{}^n}\},\left|\mathit{S}\right|=2{}^n,x{}_i\in \{0,1\}{}^n,x{}_1\to \mathit{e}{}_1,x{}_2\to \mathit{e}{}_2,\cdots ,x{}_{2{}^n-1}\to \mathit{e}{}_{2{}^n-1},x{}_{2{}^n}\to \mathit{e}{}_{2{}^n}$令vx∈{e1,e2,…,e2n},

当i=1,…,2n-1时,ei表示第i个分量为1,其余分量为0的2n-1维向量,e2n表示所有分量均为-1的2n-1维向量,可令$\mathit{u}{}_f^{\text{Τ}}=\left\{\log \frac{{\rm P}(x{}_1)}{Q(x{}_1)},\log \frac{{\rm P}(x{}_2)}{Q(x{}_2)},\cdots ,\log \frac{{\rm P}(x{}_{2{}^n-1})}{Q(x{}_{2{}^n-1})}\right\}$,则对任意f∈C/{f2n},有f(x)=sign(uTfvx),由定理2的证明知,不存在P(x),Q(x)使得对所有xi∈S,i=1,…,2n,sign$\left(\log -\frac{{\rm P}(x{}_i)}{Q(x{}_i)}\right)=-1$或sign$\left(\log \frac{{\rm P}(x{}_i)}{Q(x{}_i)}\right)=1$,即若f(x2n)=1,则存在i∈{1,…,2n-1},使得$\log \frac{{\rm P}(x{}_i)}{Q(x{}_i)}＜0$,即sign$\left(\log \frac{{\rm P}(x{}_i)}{Q(x{}_i)}\right)=-1$则存在P(x),Q(x)使得uTfvx2n=uTfe2n>0,即f(x2n)=sign(uTfvx)

同理可证,f(x2n)=-1时结论成立。

由以上证明可知∃uTf,vx∈R2n-1,使得f(x)=sign(uTfvx),则E dim(NF)=2n-1。

3 结束语

基于利他的贝叶斯均衡研究 篇6

基于Marco G和Morgan J于2008年提出非合作博弈轻微利他理论[10],王能发[11]在企业成本信息完全公开且成本相同的条件下,引入利他因子0<ε<1,推广至n个企业的利他博弈,并且分析了随着利他因子的变化,总产量和总利润的变化规律,为实际竞争中打破垄断提供了最优策略。

本文推广张维迎[7]的结论,分析对手成本信息不完全公开下的古诺-纳什模型,比较成本信息完全公开与否对两个企业最优均衡产量的影响。并引入利他因子0<ε<1,讨论两个企业在成本信息不完全公开竞争中实现利他(期望)利润最优化的贝叶斯利他均衡产量,分析了利他因子对两个企业贝叶斯利他均衡产量的影响。

一、成本信息不完全公开的古诺模型

企业1的成本c1为公共信息,企业2的成本c2是两点分布的随机变量,c2以概率p21取到低成本c2L,以概率p22取到高成本c2H。其中p21+p22=1,p21cL2+p22c2H=Ec2。

企业1和企业2的利润函数:

假设1:π1(q1,q2),π2(q1,q2)分别为企业1和企业2的利润函数;

假设2:产品价格p=a-q1-q2,其中a为常数且a>c1,a>c2。

企业2的利润函数极值条件为:

企业2的反应函数:

由于企业1不知道企业2的使用成本,所以考虑企业1的期望利润函数:

企业1的期望利润函数的极值条件为:

企业1的反应函数:

联立(1)式,解得:

(q1*,q2*)即为两个企业在成本信息不完全公开下的贝叶斯均衡产量。

定理1设企业1在成本信息完全公开下的纳什均衡产量为q1*L和q1*H,有q1*L<q1*<q1*H,企业2在成本信息完全公开下的纳什均衡产量为q2*L和q2*H,有q2*H<q2*<q2*L。

证明:若企业2公开成本为c2=c2L,得到企业1的纳什均衡产量:

若企业2公开成本为c2=c2H,得到企业1的纳什均衡产量:

由于c2L<Ec2<c2H,所以

同理可证,对企业2有q2*H<q2*<q2*L。证毕。

结论:若企业2公开成本为c2=c2L,则企业1的纳什均衡产量低于贝叶斯均衡产量,企业2作出相应反应;若企业2公开成本为c2=c2H,则企业1的纳什均衡产量高于贝叶斯均衡产量,企业2作出相应反应。

定理2设企业1在成本信息完全公开下的最优期望利润为Eπ1*L(q1*L,q2*L)和Eπ1*H(q1*H,q2*H),在成本信息不完全公开下的最优期望利润为Eπ1*(q1*,q2*),有Eπ1*L(q1*L,q2*L)<Eπ1*(q1*,q2*)<Eπ1*H(q1*H,q2*H);企业2在成本信息完全公开下的最优利润为π2*L(q1*L,q2*L)和π2*H(q1*H,q2*H),在成本信息不完全公开下的最优利润为π2*(q1*,q2*),有π2*H(q1*H,q2*H)<π2*(q1*,q2*)<π2*L(q1*L,q2*L)。

证明:设企业1在成本信息不完全公开下的最优期望利润为Eπ1*(q1*,q2*),有Eπ1*(q1*,q2*)=(q1*)2

根据定理1,有q1*L<q1*<q1*H,则

同理可证,对企业2有π2*H(q1*H,q2*H)<π2*(q1*,q2*)<π2*L(q1*L,q2*L)。证毕。

结论:两个企业在成本信息不完全公开下的最优(期望)利润介于成本信息完全公开下的两个最优(期望)利润之间。

二、成本信息不完全公开下,考虑利他的古诺模型

在成本信息不完全公开的古诺模型里,引入利他因子0<ε<1。建立企业1和企业2的利他函数:

假设1:π1ε(q1,q2),π2ε(q1,q2)分别为企业1和企业2的利他函数;

假设2:产品价格p=a-q1-q2,其中a>0,a均为常数;

假设3:ε为利他因子,0<ε<1。

企业2的利他函数极值条件为:

企业2的反应函数:

由于企业1不知道企业2的使用成本,所以考虑企业1的利他函数期望:

企业1利他函数期望的极值条件为:

企业1的反应函数:

联立(2)式,解得:

(q*1ε,q*2ε)即为两个企业在成本信息不完全公开下考虑了利他的贝叶斯利他均衡产量。

定理3设企业1在成本信息完全公开下的纳什利他均衡产量为q1ε*L和q1ε*H,有q1ε*L<q*1ε<q1ε*H,企业2在成本信息完全公开下的纳什利他均衡产量为q2ε*L和q2ε*H,有q2ε*H<q*2ε<q2ε*L。

若企业2公开成本为c2=c2L,得到企业1纳什利他均衡产量:

若企业2公开成本为c2=c2H,得到企业1纳什利他均衡产量:

同理可证,对企业2有q2ε*H<q*2ε<q2ε*L。证毕。

结论:若企业2公开成本为c2=c2L,则企业1的纳什利他均衡产量低于贝叶斯利他均衡产量,企业2作出相应反应;若企业2公开成本为c2=c2H,则企业1的纳什利他均衡产量高于贝叶斯利他均衡产量,企业2作出相应反应。此结论与成本信息不完全公开的古诺模型结论一致。企业2成本信息不完全公开时,企业1采用的最优贝叶斯(利他)均衡产量介于企业2公开成本时的两个纳什(利他)均衡产量之间,企业2作出相应反应。

图2企业2的纳什利他均衡产量和贝叶斯均衡利他产量比较

考虑下列情形的数值模拟。

设a=2,c1=1,c2L=0.6,c2H=0.9,p21=0.5,p22=0.5,此时,Ec2=p21c2L+p22c2H<c1。取0<ε<0.7,做出企业1纳什利他均衡产量和贝叶斯利他均衡产量的比较图图1及企业2纳什利他均衡产量和贝叶斯利他均衡产量的比较图图2。由图1、图2观察到,无论企业2成本信息是否完全公开,企业1的均衡产量均随着利他因子的增大而减小。企业2的均衡利他产量随着利他因子的增大而增大,说明当企业2的成本具有明显优势时,企业2更倾向于利他。

定理4当0<ε<1时,两个企业的贝叶斯利他均衡总产量为Qε*(ε),满足Qε*(1)<Qε*(ε)<Qε*(0)。

证明:当0<ε<1时,两个企业的贝叶斯利他均衡总产量为Qε*(ε),有:

因为c1<a,c2<a,Ec2<a,所以:

因此Qε*单调递减。又

即Qε*(1)<Qε*(ε)<Qε*(0)。证毕。

结论:此结论具有一般性,无论企业2成本信息是否完全公开,两个企业的利他均衡总产量随着利他因子ε的增大而减少。

三、结束语

面对成本信息不完全公开的竞争,企业1的贝叶斯均衡产量介于成本信息完全公开时的两个纳什均衡产量之间,企业2相应作出反应,这一特征,在考虑了相同利他因子的情况下仍然成立。成本信息不完全公开下的最优期望利润,可能会比成本信息完全公开下的最优期望利润小,但是不失为化被动为主动的最优竞争策略。而两个企业总产量随着利他因子的增加而减少,这为企业在成本信息不完全公开下的反垄断提供决策参考。结论推广到n个企业成本信息不完全公开的竞争是否成立,或一般化为企业间的差异利他,结论会怎样改变,有待进一步论证。

摘要：本文比较了成本信息公开与否对两个企业均衡产量的影响,在成本信息不完全公开的情况下,引入利他因子0<ε<1,建立企业在成本信息不完全公开下的利他函数,讨论了两个企业在成本信息不完全公开下的贝叶斯利他均衡产量。

基于贝叶斯网络的信息检索模型 篇7

(一) 推理网络模型

推理网络模型采用的是信息检索认识论的观点[4]。该模型中文档节点用dj表示, 术语节点用ki表示, 查询节点用q表示。文档节点、术语节点、查询节点均与用相同符号表示的二进制随机变量相关。U={k 1, k 2, ..., k t}表示t维的向量空间, 变量k1, k 2, ..., kt为U定义了2t种状态, u表示其中一种状态。

根据查询q对文档dj进行排序, 其结果可以用来度量dj的观测值为查询q提供了多少证据支持。在推理网络中, 文献dj的排序可用P (q|d j) 来计算[2], 其计算方法如下:

其中α是一个常数因子, 因为没有对任何文档给出特定的先验概率, 所以一般采用一个统一的先验概率分布, 在有关推理网络的早期著作[1,5]中, 规定观测一篇文档dj的先验概率为, N为系统中的文献总数, 因而:

利用基本条件及贝叶斯定理, 公式 (1) 可变为下式:

具体定义方法参考文献[4]。

(二) 信念网络模型

信念网络模型也是基于概率认识论描述的, 但是这种模型采用的是一个明确定义的样本空间, 因而产生了一种不同于推理网络的网络拓扑, 即将网络中的文档和查询分离开来。

在信念网络中, 术语集合U={k 1, k 2, ..., k t}是一个论域 (discourse) , 同时为信念网络模型定义了样本空间。u⊂U是U的一个子集, 且g i (u) =1⇔ki∈u。每个索引术语被看作是一个基本概念, 因此U被看作是一个概念空间, 概念u是U的子集。文档和用户查询用概念空间U中的概念表示。

定义在样本空间U上的概率分布P如下所示, c是空间U中的一个概念, 表示一篇文档或一个用户查询:

公式 (5) 将p (c) 定义为空间U中c的覆盖度 (degree of coverage) , 公式 (5) 表示概念空间中的所有概念均是等概率发生的。

与给定查询q相关的文档dj的排序被理解为一种概念匹配关系, 它反映了概念q提供给概念dj的覆盖度。因此在信念网络中用p (dj|q) 计算文档dj关于查询q的排序。根据条件概率、公式 (5) 及贝叶斯定理可得:

其中η为规范化因子, 对概率P (d j|u) , P (q|u) 的不同定义可使信念网络检索模型包括由各种经典信息检索模型 (布尔模型、矢量模型、概率模型) 产生的排序策略。具体定义方法参考文献[2]。本文提出的扩展模型就是以基本信念网络模型为框架的。

(三) 简单贝叶斯网络检索模型

简单贝叶斯网络检索模型中的变量由两个不同的集合组成, V=T∪D:集合T={T1, T2, ..., TM}, 集合D={D1, ..., DN}, T和D中的变量均是二值的。变量Dj取值集合为, 其中和dj分别表示在给定查询下文档Dj不相关和相关。变量Ti取值集合为, 其中分别表示术语不相关和相关。

网络拓扑结构的建立基于以下三个假设:

1. 如果术语Ti属于文档Dj, 则术语节点Ti和文档节点Dj之间有弧。这反映了文档和其索引术语之间的依赖关系;

2. 文档节点之间没有弧, 也就是说文档节点之间的关系只是通过索引它们的术语表示出来;

3. 已知文档Dj中索引术语是否相关的情况下, 文档Dj和其它任何文档Dk是条件独立的, 也就是说文档Dj是否相关只受索引它的术语的影响, 而不受其它文档的影响。在网络中表现为弧的指向是由术语节点指向文档节点。

由这三个假设最终确定网络的拓扑结构。网络包括两个子网:术语子网和文档子网, 弧是由第一个子网中的节点指向第二个子网中的节点。该模型与推理网络模型和信念网络模型最大的区别是在网络中没有包含查询节点, 也就是说该模型是查询独立的, 查询只是作为证据在网络中传播。

BNR模型各类节点中存储的条件概率计算如下:

(2) 对于文档节点需要估计条件概率分布p (dj|π (Dj) ) , 其中π (Dj) 是Dj的父节点集Π (D j) 取值后的任意一种组合。因为文档节点可能有大量的父节点, 所以需要估计和存储的条件概率的数目是很巨大的。因此, 简单贝叶斯网络检索模型采用了专门的正则模型来表示条件概率:

其中R (π (Dj) ) 是π (Dj) 中相关术语的集合, 权重wij满足wij≥0且。这样在π (Dj) 中的相关术语越多, Dj的相关概率越大。

简单贝叶斯网络中节点的数目通常比较大, 节点之间的连接也是多路经的, 每个节点也可能包含大量的父节点, 所以考虑到检索的效率问题, 一般的推理算法是不能使用的。因此, 简单贝叶斯网络检索模型设计了特殊的推理过程可以非常有效地计算需要的概率, 并且证明了得到的结果和在整个网络中实施精确推理得到的结果是一样的:

根据术语子网的拓扑结构, 则当Ti∈Q时p (ti|Q) =1, 当Ti∉Q时p (ti|Q) =1/M, 这时公式 (8) 可改写为:

权重wij有多种计算方法, 可参考有关文献。

参考文献

[1]Howard Robert Turtle, W.Bruce Croft.Inference networks for document retrieval.Proceedings of the13th ACM-SIGIR Conference, 1990:1-24.

[2]Berthier Ribeiro-Neto, Richard Muntz.A belief network model for IR.Proceedings of the19th ACM-SIGIR Conference, 1996:253-260.

[3]Ricardo Baeza-Yates, Berthier Ribeiro-Neto.现代信息检索.北京:机械工业出版, 2005:24-42.

[4]Howard Robert Turtle, W.Bruce Croft.Evaluation of an inference network-based retrieval model.ACM Transactions on information systems, 1991, 9 (3) :187-222.