基于事件的贝叶斯信任模型

理论计算机科学电子笔记172（2007）499-521www.elsevier.com/locate/entcs基于事件的贝叶斯信任模型莫恩斯尼尔森1Karl Krukow2金砖丹麦奥胡斯大学3弗拉迪米罗·萨索内南安普敦大学ECS摘要为“全球无处不在的计算”设想的应用场景 一个替代 目前正在调查 是通过主体信任关系的显式表示来支持安全决策，即， 通过计算信任的系统。在这里，我们专注于系统中的计算实体的信任被解释为基于过去的行为模式的某些未来行为的预期，并关注自己与这种概率系统的基础。特别是，我们的目标是建立正式的概率模型计算信任和他们的基本属性。 在本文中，我们定义了一个数学度量，用于定量比较各种环境中概率计算信任系统的有效性。使用它，我们比较了一些系统的计算信任的文献，比较是正式的，而不是通过实验模拟传统上做的。有了这个基础，我们正式形成了一个关于过去行为的信息的一般概念，基于事件结构。这就产生了一个灵活的信任模型，其中可以评估复杂协议结果的概率。保留字：贝叶斯模型，信任模型，概率系统，事件结构1介绍全球普适计算（GUC）科学的大挑战的一部分[5]是找到现有访问控制方法的替代方案，更广泛地说，是安全敏感决策。GUC的许多新特性（虚拟匿名性，可扩展性，移动性，自治性，普遍性，不完全信息，全球连接性，。. .）将改变我们对安全需求的概念。例如，流动性1电子邮件：mn@brics.dk2电子邮件：krukow@brics.dk3金砖国家：计算机科学基础研究（www.brics.dk），由丹麦国家研究基金会资助1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2007.02.017500M. Nielsen等人理论计算机科学电子笔记172（2007）499这意味着GUC实体可能会发现自己处于敌对环境中，与其首选的安全基础设施断开连接，例如，其通常的认证机构。此外，自治要求意味着即使在这种情况下，它也必须能够向其他GUC实体分配特权;特权是基于分配实体具有的关于所分配的实体的通常不完整的信息而有意义的GUC的这些属性意味着传统的安全机制不再适用（参见例如，Blaze，Feigenbaum等人 [1]）。目前正在研究的替代方案之一是基于信任概念的方法，在某些方面，类似于人类之间存在的信任概念我们将这一研究方向称为计算信任。事实上，计算信任不仅涉及访问控制，而且更普遍地涉及在存在未知、不可控和可能有害的实体的情况下计算代理例如，自主选择（显然类似的）特定服务的提供者就是这种情况。在计算信任领域，很难确定一个（甚至几个）被社区广泛接受的模型。不完全信息的GUC特征自然会导致概率决策;因此，一种常见的分类区分了非概率系统可以进一步分为不同类型（例如，社交网络或认知的）;相反，概率系统通常具有共同的目标和结构：它们（i）假设主体行为的特定（概率）模型;以及（ii）提出用于近似主体行为的算法（即，在模型中进行预测）。在这样的模型中，关于主体的信任信息是关于其过去行为的信息。这样的历史不会立即将主体分类为Sabater和Sierra [ 21 ]称之为“博弈理论”的概率系统基于Gambetta的信任观[ 9 ]：. .信任（或对称地，不信任）是主体评估另一个主体或一组主体将执行特定动作的主观概率的特定水平，无论是在他能够监控这种动作之前（或独立于他能够监控它的能力）还是在它影响他自己的动作的上下文中。本文的贡献就是受到这种预测性的信任观的启发任何概率模型都基于计算实体之间交互的底层模型，为此，我们使用Plotkin等人 [18]的事件结构，如之前在[17]和[14]中所讨论的我们在Varacca等人 [23]中为事件结构配备了概率，并且我们遵循贝叶斯方法来处理概率论，例如[10]中所提倡的。事实上，我们开发了我们以前在SECURE项目[4]中使用的事件结构框架的概率扩展，我们用它来建模交互的结果，并使用贝叶斯学习对其配置进行预测。从这个意义上说，我们的框架概括了以前的概率模型，只有其中每一个相互作用被认为是M. Nielsen等人理论计算机科学电子笔记172（2007）499501pp在简单的情况下，这些结果可能代表不同程度的满意度的贝叶斯分析包括对一些真实世界的现象提出假设，运行实验来测试这种假设，然后更新假设（如果必要），以更好地解释实验观察结果，更好地拟合假设观察到的通过用感兴趣的空间上的条件概率来表达它，这个过程可以用贝叶斯概率（Θ|X）可编程逻辑器件（X|·Prob（Θ）。从左到右阅读，该公式被解释为：实验X的结果之后的假设的概率Θ与在假设下的这种结果的可能性乘以实验之前的假设的概率成比例[4]在本上下文中，先验θ将是我们与主体p的下一次交互中每个潜在结果的概率估计，而后验将是我们与结果X发生一次这样的交互后的修正估计。在这里重要的是观察到，|X）在某种意义上是一个二阶概念，我们对计算θ的任何特定值不感兴趣。事实上，由于Θ是我们问题中的未知数，我们有兴趣导出整个分布，以计算其期望值，并将其用作我们对Θ的下一个估计。为了使这个讨论更具体，让我们首先关注二元结果模型。这里，Θ可以由单个概率Θp表示，即主体p将表现为恶意的概率，即，与p的交互将是成功的。在这种情况下，n个实验的序列X =X1···Xn是二项（伯努利）试验的序列，并且由二项分布建模概率（X由k次成功组成）= Θ k（1 − Θ p）n−k。事实证明，如果先验θ服从β分布，比如参数α和β的B（α，β）<$Θα−1（1−Θp）β−1，那么后验也是如此：即， 如果X是k个成功的n序列，则概率（Θ|X）是B（α + k，β + n-k），参数α + k和β + n-k的β分布。这是一个特别令人高兴的情况下，应用贝叶斯如上所述，我们的选择模型偏离了将交互视为具有二元（成功/失败）结果的事件序列从技术上讲，我们看到4我们通常会省略比例因子，因为比例因子是唯一确定的常数，它使右侧项成为概率分布。事实上，它等于Prob（X）-1。502M. Nielsen等人理论计算机科学电子笔记172（2007）4991K由独立的、多重概率选择序列产生的有限的、无混淆的事件结构的配置。 从数学上讲，这需要传递从二项试验的典型二项分布到多项分布，tions Θ n1. Θnk（其中θn = 1）是n次试验序列（n=<$n）的典型，k1ki i不同的结果。在这个新框架中，我们的贝叶斯分析依赖于观察事件结构配置的序列一次一个事件以“学习”（即，估计）每种配置作为下一个复杂（基本序列）相互作用的结果出现的概率当然这里Θi表示我们目前对k路选择中第i个相应地，我们需要在多项试验之前确定一个合适的共轭，以代替贝叶斯定理应用中的β 正如我们在§4，我们将其定义在Dirichlet分布族中D（α1，.，αk）<$Θ α1−1···θ αk −1。与二元情况完全类似，从而确定理论的光滑和统一提升，如果先验服从Dirichlet分布D（α1，.，αk），则后验概率（Θ|D.符合Dirichlet分布D（α1 + #1（X），.，αk+#k（X）），其中#i（X）计数事件i在序列X中的出现次数。我们注意到，类似的观察是独立的[11，20]。我们在本文中的第二个贡献是定义了一种形式化的度量，它表达了各种应用环境中概率计算信任系统的质量。该度量基于所谓的Kullback-Leibler散度[15]，也称为信息散度或相对熵，在信息论文献中用于测量从近似到已知目标概率分布的在这里，我们将调整它来衡量计算信任算法如何近似计算实体的作为理论的适用性的一个例子，我们提出了理论结果领域内，关于整个类现有的概率信任算法。据我们所知，以前没有提出过这样的方法（但参见。[6]对于匿名性的类似概念的应用事实上，我们认为这是本文的主要结果，因为它以比较计算信任算法的方式论文的结构 本文的组织结构如下。在§2中，我们精确地描述了在引言中以某种非正式的方式描述的场景，并证明了我们的计算信任算法的形式结果为了简单起见，我们提出了我们的在实验是非结构化结果的序列的情况下，我们希望所有这些参数都经过必要的修改，以达到结果是事件结构配置的情况。本文的其余部分致力于将二元模型提升为结构化，分布式，复杂的结果，M. Nielsen等人理论计算机科学电子笔记172（2007）499503事件结构。在§ 3中，我们介绍了概率事件结构模型;熟悉[ 23 ]的读者可以安全地省略这一节。在§ 4中，我们用Dirichlet分布来装备事件结构，并说明我们基于事件的贝叶斯分析框架。最后，§ 5对本文中所阐述的概率模型的一些基本假设进行了评论，并指出了未来的研究方向旨在让他们放松。2贝叶斯信任模型从一开始，贝叶斯信任模型就基于这样的假设，即委托人的行为方式可以通过固定的概率来近似相应地，在与主要的p互动时，一个人将不断地体验到结果，遵循不变的概率分布Θp。当然，这种假设在现实世界的几种情况下可能是不现实的，我们将在第5节中讨论一个旨在解除它的研究计划;然而，目前，我们继续探索在哪里这种假设引导我们。我们的总体目标是获得Θp的估计值，以便为我们未来与p的相互作用策略提供信息。计算信任算法试图使用贝叶斯分析来实现这一点。让我们确定一个主体行为的概率模型，即一组关于主体行为方式的基本假设，比如λ，然后考虑单个固定主体p的行为。我们将专注于以下问题的算法：让X是一个在-交互历史x1，x2，. ...，yk}的可能结果。概率计算信任算法，比如A，在输入X上输出结果{y1，.，yk}。也就是说，A满足：克A（yi|X）∈ [0，1] （i=1，.，k）的i=1A（yi|X）= 1。这种分布意味着在假设λ下近似θp。为了使这一点更精确，让我们假设概率模型λ，定义了以下概率：概率（yi|Xλ）：“在给定过去历史X的情况下，在下一次相互作用中观察到yi”的概率;概率（X|λ）：“在模型λ中观察X”的先验概率。现在，Prob（·|X λ）定义下一次交互结果的“真实”分布（根据模型）;相反，A（·|我们现在将提出一个通用的衡量标准来“ 评 分 ” 特 定 的 算 法 A ，概率分布分数基于所谓的Kullback-Leibler发散，是算法近似主体的“真实”概率行为的程度的度量504M. Nielsen等人理论计算机科学电子笔记172（2007）499A.A.KLKLKLKL2.1基于概率信任的系统比较与香农的熵概念密切相关对于p =（p1，.，p，k）和q =（q1，q2，.，qm）分布，从p到q的Kullback-Leibler散度定义为：克DKL（pq）=i=1pilog2（pi/qi），其中使用的对数基数是无关紧要的。信息发散类似于数学意义上的距离：可以证明DKL满足DKL（p<$q）≥0，并且当且仅当p=q时获得相等;然而，它不是对称的。我们调整DKL，通过在可能的输入序列上取其平均值来对算法之间的距离进行评分，如下所示。对于每个n∈N，设On表示长度为n的相互作用历史的集合.德费恩n，从λ到A的第n个预期Kullback-Leibler散度为：Σn（λ）=X∈On概率（X|λ）·DKL.Prob（·|X λ）<$A（·|ΣX），也就是说，nKL（λA）= ΣX∈On概率（X|λ）·克i=1概率（yi.| Xλ）log 2ΣP（yi|X λ）。A（yi|X）注意，对于每个可能的输入序列X∈On，我们将算法的性能评估为D KL（Prob（·|Xλ）<$A（·|X）），即我们接受一些算法可能在非常不可能的训练序列X上表现不佳，同时提供excel-结果经常投入。因此，我们通过序列X的固有概率来衡量每个输入X的性能。换句话说，我们计算大小为n的输入的期望信息发散。虽然Kullback和Leibler是新的由于与香农的信息论的关系n（λA）定量地作为预期的信息比特数，通过了解“真实”分布概率（·|Xλ）的所有训练序列长度n，而不是它的近似值A（·|X）。2.1.1举个例子为了验证我们的测量，我们将Mui等人 [16]的基于β的算法与Aberer和Despotovic[7]的最大似然算法进行了比较。比较是可能的，因为算法共享相同的基本假设：DDDDM. Nielsen等人理论计算机科学电子笔记172（2007）499505一|nKLKLKLєKL一|n每个主体我们把这些称为β模型λB。s和f分别代表X∈{s，f}n的似然性由下式给出：概率（X |Θ λB）= Θ #s（X）（1-Θ）#f（X），其中#x（X）表示X中出现x的次数。 使用A和B分别表示Mui等人的算法，以及Aberer和Despotovic的算法，我们有：A（s）|X）=B（s）|X）=#s（X）+1和（fX）=n+2的#s（X）和B（f|X）=f（X）=0、n+2的#f（X）.n对于θ∈ [0，1]的每个选择和训练序列长度n的每个选择，我们可以通过计算和比较Dn（ΘλB<$A）和n （Θ λB<$B）。定理2.1如果Θ = 0或Θ = 1，则来自[ 7 ]的Aberer和Despotovic的算法B比来自[ 16 ]的Mui等人的算法A计算出更好的委托人行为的近似。事实上，在这些假设下，B总是计算任何可能的训练序列的准确成功概率。证据 假设Θ = 0，并且令n> 0。 唯一具有非零概率的n序列是fn，并且我们有B（f |f n）= 1;相反，A（f |f n）=（n +1）/（n +2），而A（s|fn）= 1/（n +2 ） ） 。 由 于 概 率 |fnΘ λB） = Θ = 0 = B （ s|f n） 和 P rob （f|fnΘλB ）=1−Θ=1=B（f|fn），我们可以将其KL（Θ λB<$B）= 0。自Dn（ΘλB<$A）>0我们就完成了。（对于Θ = 1的论证类似）。Q现在让我们比较0 Θ 1下的A和B<<观察B分配概率0到s在输入f k上，对于所有k ≥ 1;这导致Dn（Θ λB<$B）= ∞。它遵循在这种情况下，A提供了更好的近似。为了进一步探索基于β的算法的空间，我们定义了一个参数算法A，对于≥0，它包含A和B：A（s|h）=#s（h）+s和（sX）=|+2|+ 2 ϵ#f（h）+f。|+2|+ 2 ϵ观察A0=B和A1=A。DD506M. Nielsen等人理论计算机科学电子笔记172（2007）499KLKLKLKLDKLKLnnn−n−n我n我现在让我们研究表达式Dn（ΘλB<$A<$）作为θ的函数。 我们将对于cθ/=1/2的情况下，预处理的结果是一致的，并且如果cθ/=1/ 2，则预处理的结果是一致的。最小化距离Dn（ΘλB <$A<$）。 此外，Dn（ΘλB<$A<$）在减小在区间（0，）上，并在区间[，∞]上增加。（注意：n（Θ λB <$A<$）→∞（当<$A→ 0时）根据定义，我们有：卢恩D（ΘλB <$A）=.ΣΘi（1−Θ）n−iΣ ΣΘlog Θ（n +2 θ）+（1-Θ）log（1-Θ）（n +2 θ）。吉隆坡我i=0时i+n−i+n分离出包含k的项，我们得到卢恩i=0时.ΣΘi（1Θ）n−i我ΣΣΘ log Θ+（1−Θ）log（1 −Θ）+ log（n+2）n.Σ niΣ Σn−i−i=0时iΘ（1−Θ）Θlog（i+）+（1 − Θ）log（n − i+）。通过区分Dn（ΘλB<$A<$）关于θ，我们得到DndKL（ΘλB<$A<$）=2αn+2π卢恩−i=0时.ΣΘi（1Θ）n−i我ΣΘα+i+Σ（1− Θ）α，n−i+n其中，α= loge是对函数log进行微分时得到的正常数。 为了找到信息分歧的最小点，让我们检查其中，h_i_i_n_u_i（Θ λ B_i_a_i）/_i（ΘλB_i_i_a_i_i_i）是唯一的。d. 这是一个复杂的问题，如图1所示。 注意，由于i=0inΘi（1− Θ）n−i是期望的在长度为n的伯努利试验中成功的次数，它等于Θn。同样，一能证明卢恩i=0时.Σi2Θ i（1 − Θ）n−i= n（n − 1）Θ 2+ Θ n。这些等式使我们可以用更简单的形式写出等式（1n（2 Θ −1）（nΘ−n/2）=n（n−1）Θ2+Θn−Θn（n/2 +Θn） +Θn2/2。因此，我们有<$（2Θ− 1）（nΘ−n/ 2）=<$（2Θ− 1）n（Θ− 1）=<$（2Θ− 1）2n/2，n（n−1）Θ2+Θn−Θn（n/2 +Θn） +Θn2/2 =DΣM. Nielsen等人理论计算机科学电子笔记172（2007）499507KLn2（Θ2-Θ/2-Θ2+Θ/2）+n（Θ-Θ2）=nΘ（1-Θ）。由于当Θ = 1/ 2时（2Θ− 1）2不为零，我们得到dDn（ΘλB<$A <$）/d <$是如果Θ/=1/2，θ = 2Θ（1-Θ）。（2Θ −1）2508M. Nielsen等人理论计算机科学电子笔记172（2007）499KLDdDnKL卢恩.Σn我Σ（ΘλB<$A<$）Ⓘ=零ΣΘi（1− Θ）n−i卢恩 .Σn/2+Ⓘ1Θ-i+− （1−Θ）n−i+n=零i=0时i=0时n我ΣΘi（1− Θ）n−i（i+）（n−i+）−Θ（n/2+）（n−i+）卢恩Σ-（1- Θ）（n/2+θ）（i+θ）Ⓘ=零.Σn我Σϵ2Θi（1− Θ）n−i1− Θ−（1−Θ）+i=0时卢恩ϵ.ΣnΣΣΘi（1− Θ）n−ii+n−i− Θ（3n/ 2−i）−（1− Θ）（n/2+i）+i=0时卢恩i=0时我.Σn我ΣΣΘi（1−Θ）n−ii（n−i）−θ（n2/2−ni/2）−ni（1−Θ）/2=零卢恩ϵ.Σn我ⒾΘi（1− Θ）n−i[（2Θ− 1）（i−n/2）]+i=0时卢恩.Σn我Θi（1− Θ）n−i[（Θn−i）（i−n/2）]=0i=0时卢恩ϵi=0时.Σn我ΣⒾΣθi（1−θ）n−i（2θ− 1）（i− ）=n卢恩2i=0时.Σn我ΣΣθi（1−θ）n−i（i−θn）（i−）n2（一）Fig. 1.求解方程d D n（ΘλB<$Ac）/d <$= 0。值得注意的是，这与n无关。此外，从同一推导中，我们立即得出，dDn （ΘλBA）02Θ（1− Θ）<<和d KL（2Θ −1）2dDn （ΘλBA）>0λ λB>2Θ（1− Θ）d KL（2Θ−1）2因此，我们证明了以下内容。M. Nielsen等人理论计算机科学电子笔记172（2007）499509KLKL对于2.2阶的nyΘ∈[0，1/2）<$（1/2，1]，存在n∈[0，∞）使得min imisen（Θ λB<$A<$）同时对所有n;即，θ = 2Θ（1-Θ）/（2Θ-1）2。此外，Dn（ΘλB<$A<$）是λ在区间（0，λ），并在（∞，∞）中增加。这意味着，除非主体 如果Θ = 1/ 2，则θ越大，算法越好。关于A和B，一个新的应用程序的第二个。2.告诉我们，我们的时间表是最佳的Θ =1/2±1/12，其中该值由θ或2表示。1-这是一个很好的选择，Θ = 0和Θ = 1。在结束本节时，有必要指出，我们感兴趣的并不是算法A和B的可比性;相反，信息是使用正式的概率模型可以进行这种数学比较，更多的是，一般，研究模型和算法的属性3概率事件结构分布式系统中的代理通过观察行为观察来获取信息，通常通过交换消息来触发这种消息交换的结构通过行为观察，我们指的是各方可以对此类协议的具体运行进行的观察。这些包括有关消息内容的信息、从协议转移、在特定时间范围内接收消息失败在这里，如在以前的工作（cf。[17，14，13]）我们使用事件结构来形式化协议，观察和结果的概念事件结构非常适合我们目前的目的，因为它们为事件提供了一个通用模型（即，基本的可观测量）和因果关系，独立于任何特定的编程语言和更高级别的模型。在我们的模型中，一个代理持有的关于另一个代理行为的信息或配置，x1x2···xn。配置xi代表方案的第i次运行(e.g.、按开始时间按时间顺序排序），并收集在该协议实例中直到该点发生的所有事件;xi可以表示完成的协议运行，在这种情况下，它记录交互的完整结果，或者可以表示运行的协议运行，在这种情况下，随着计算的进行，更多的事件将被添加到它。请注意，与许多现有系统相反，这里我们不是对主体的行为进行评级;而是记录他们的实际行为，即，确切的事件发生在相互作用中。我们稍后将为模型配备概率度量，以便对交互结果进行评级，从而评估未来交互的可能性。虽然在SECURE项目中，事件结构是计算分布式交互的“信任值”的首选模型D510M. Nielsen等人理论计算机科学电子笔记172（2007）499上下文是主体行为的正式概率模型。在接下来的两节中，我们对此进行了修改：我们用概率模型来扩展事件结构框架，该模型概括了基于β分布[12，16，2，22]的系统中使用的概率模型，并且我们展示了如何计算给定观测历史的结果概率。虽然这本身可能是有价值的，我们注意到，我们的主要原因是说明一个正式的概率模型，使正式的问题被问（和回答）的例子。拟议的系统尚不实用：事实上，它无法处理许多问题，例如，主要行为的变化、说谎的声誉来源和多个执行上下文。我们认为，在我们能够成功地处理这些问题之前，必须更好地理解基本的概率模型。3.1事件结构我们简要概括了基本定义，同时请读者参考[17，14，13]以获得更多细节和示例。一个事件结构是一个三元组ES=（E，≤，#），它由一个事件集合E组成，这些事件集合E部分地被必然性（或因果性）关系≤排序;联系关系#是一个二元的、对称的、不相关的事件关系。对于所有的e，EJ，EJJ∈E，它们满足下列性质.defJ J[e]={e∈E|e≤e}是有限的;如果e#eJ且eJ≤eJJ，则e#eJJ这一切背后的意图应该是直观的。一个事件可以排除其他事件发生的可能性;这就是冲突关系模型。必然性关系代表了这样一种思想，即事件只有在其他事件（它们的原因）已经发生时才是最后，如果两个事件在任何一个关系中，它们被称为独立的。因此，上面的两个条件是事件结构对在特定事件中可能发生的事件集进行tocol;控制流程由≤和#提供，保证不是所有的事件可以在特定的运行中发生。配置的概念将其形式化如下。一组事件x∈E是ES的配置，如果它是无约束：对于任何e，eJ∈x：不是e#eJ;并且因果闭：对任意e ∈ x，EJ∈ E：EJ≤ e蕴涵EJ∈ x。我们将ES的配置集写成CES。所有最大配置的集合，即，不能扩展的配置详尽地定义了交互的集合结果。当然，这些配置是相互排斥的。3.2历史有限配置对关于单个交互的信息进行建模，即，一个协议的单次运行一般来说，一个主体所拥有的关于M. Nielsen等人理论计算机科学电子笔记172（2007）499511ES伊什另一个由关于几个协议运行的信息组成;关于每个单独运行的信息由相应事件结构中的配置表示 （局部）交互历史的概念对此进行了建模。 的交互ES中的历史是一个有限的有序构形序列，h = x1x2···xn∈Cn。条目xi被称为h的会话。备注。 虽然记录了会话的顺序（即，历史是序列），但相比之下，单个会话中独立事件的顺序却没有。事件的独立性实际上是在设计事件-结构模型时可能做出的抽象选择（因为人们对事件的特定顺序不感兴趣，或者因为事件顺序的精确记录是不可行的）。这当然是事件结构的一个特征，而不是限制：在事件排序既相关又可观察的情况下，人们总是可以使用适当的3.3无混淆事件结构在下文中，我们考虑一种特殊类型的事件结构，即所谓的无混淆，将概率与之相连特别简单[23]。正如我们将看到的，关键是要确保所有的这相当于要求一个事件的发生不影响单元格内的相对概率，即使它当然可能排除整个单元格。这将通过保证每个事件最多属于一个单元并且冲突在单元上的行为一致考虑下面的事件结构，作为对以下定义中的固定概念的帮助（代表冲突，→代表因果关系）。c、......你好，，，，，，，，我的天啊a，，，ss，b，事件c和e是独立的，下面的事件对也是独立的：c和f; d和e; d和f。 在事件结构中，这仅仅意味着独立对中的两个事件可以在相同的配置中以任何顺序发生。我们旨在定义一个概率模型，其中独立性也意味着概率独立性。为此，我们提出了细胞和直接接触的概念[23]。设ES=（E，≤，#）是一个固定的事件结构。对于[e]z{e}，写[e），并说事件e，eJ∈E在符号e#μeJ中是立即连接的，如果e#eJ和[e][eJ]和[e][eJ]都是配置。显然，当且仅当存在一个e和eJ都被使能的配置x时，一个冲突e#eJ是立即的这意味着它们可以在x中同时发生。例如，连接a # b是立即的，而a # c不是。部分单元是事件c∈E的非空集合，使得e，eJ∈c意味着e#μeJ和[e）=[eJ）。一个最大的部分单元称为一个单元。这意味着，在512M. Nielsen等人理论计算机科学电子笔记172（2007）499Σ为了从[e）完成，计算必须细胞代表选择。上述事件结构中有三个单元格：{a，b}、{c，d}和{e，f}。无混淆事件结构是其中直接联系是传递关系并且在单元格内的事件结构e#μeJ意味着[e）= [eJ）。在无混淆事件结构中，如果单元格c的事件在配置x下启用，则C的所有事件在X处被启用。 这是因为如果e与某个eJ∈c相容，则e与所有eJ∈c相容。如果事件结构也是有限的，则最大配置（即，交互的结果）通过开始然后重复以下操作。 设C为当前配置中启用的单元集。如果C为空，则停止，因为当前配置是最大的;否则，非确定性地选择一个单元格c∈C，然后非确定性地选择（或概率采样）一个事件e∈c。 通过添加e更新当前配置。单元赋值的概念形式化了单元中的概率抽样在这里和下面，对于f：X→[0，+∞]一个函数和Y<$X一个集合，我们使用f[Y]来设y∈Yf（y）.定义3.1（Cell valuation，Varaccaet al [23]）无混淆事件结构ES=（E，≤，#）上的Cell valuation是一个函数p：E→[0， 1]，使得对于每个Cellc，我们有p[c] =1。如果我们假设细胞中事件之间的（概率）独立性，那么我们可以计算任何配置x发生的概率，简单地作为构成事件的概率支持3.2（[23]）Letp是一个等价的，且对于e∈xp（e），可写成p（x）;则• p（n）=1;• p（x）≥p（XJ），若x<$XJ;• p（x）=p[C]，如果C是覆盖x的极大配置集;• p是最大配置上的概率分布。在上面的公式中，我们说y覆盖x意味着对于某个e，y=x<${e}。注意命题3.2的含义是p（x）必须被解释为（部分）配置x包含在计算结果中的概率。在最大配置上，p产生一个概率分布。参考我们运行的示例的事件结构{a›→1/4 b›→3/4; c›→4/5; d<$→1/5; e›→3/5; f›→2/5}很容易看出它代表了一个单元格的估值。图2给出了配置的整个结构及其概率。M. Nielsen等人理论计算机科学电子笔记172（2007）499513--------............--k=1e9/ 25 b、c、e......b、d、e9/100，，6/ 25 b、c、f，，b、d、f6/ 100、、9/ 20 {b，e}，，，，，，，，，、、{b，c}，{b，d}，，，，，，，，，{b，f}、、，，3/53/ 20 、、、、3/ 10四分之一，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，一，，，，，，，，，，，，，，，，{b}，，，，，，第1页三分之四图二. 一个细胞估值和配置概率4基于事件模型如前一节所述，找到一个单元赋值p：E→[0， 1]是为一个有限的、无混淆的事件结构ES的配置分配概率的关键步骤。注意，给出一个这样的p是给每个单元c是函数pc：c→[0，1]，其中pc[c] = 1，即，概率分布。我们的假设是，典型的贝叶斯方法，分布pc独立且不变地存在;我们的意图是，同样典型的，它们是‘learned’ via experiments, that in our case means derived from the past history ofinteractions 在下面的标题下，我们明确地陈述了关于我们模型中实体行为的假设。 然后我们继续（i）找到在模型下保留足够信息的抽象;以及（ii）导出预测概率的方程，即，公式来回答诸如“在与实体q的下一次交互中结果x的概率是多少”之类的问题4.1模型设ES是一个有限的、无混淆的事件结构ES，C（ES）={c1，c2，. ，cM}其单元的集合，其中，ci={ei，.，ei}。我们写λDES为以下我们模型的假设1Ki每个委托人 在每个交互中，如果c1被使能，则存在小区c1的事件发生的概率分布Θc1，而与我们所知道的关于其它交互的任何情况无关这样的基本数据相当于对ES的每个事件e给出概率Θe，因此这是一个Θi= 1。 集合Θ =（Θ c1K，... ，Θ cM）确定单元格估值在ES上。从我们的假设可以得出，对于每个配置x∈ CES，在具有由Θ参数化的主要参数的ES的任何运行中获得x的概率是概率（x|ΘλDES）=e∈x、514M. Nielsen等人理论计算机科学电子笔记172（2007）499Θ e。（二）M. Nielsen等人理论计算机科学电子笔记172（2007）499515ESK与§2中描述的模型λB相比，λDES将概率分配给（最大）配置，以获得与λB对二元结果所{s，f}。然而，在这种情况下，分配不是“原子的”，而是通过单元评估获得的，即，将概率分布分配给细胞，并最终分配给基本事件。虽然从{s，f}中x的发生是一个二项式（伯努利）试验，但从ci中事件的发生是一个具有Ki结果的随机过程。也就是说，关于Θci的多项式试验。为了利用这个类比，我们只需要在多项式实验的基础上，将§2的框架提升为1特别是我们需要确定一个分布族，它在这里可以起到与β分布在那里同样的作用。首先，我们观察到，为了估计给定先验分布的参数Θ，我们只需要简单的事件计数，即，函数X：E→N。事实上，在Eq。在等式（2）中，估计每个小区c的参数Θc是足够的。然后，从λDES的假设得出，事件发生的计数X对于任何观测到的数据序列h∈ C，固定的本金。其次，为了应用贝叶斯分析，我们需要先验分布。由于我们打算使用我们的估计来确定整个分布的期望值，因此我们能够以符号形式计算它们是至关重要这是共轭先验的作用之一我们用引言中的术语来说明贝叶斯定义4.1概率分布族F是似然函数L的共轭先验，如果无论何时先验分布属于F，则后验分布也属于F。事实上，共轭先验的使用通常会在贝叶斯分析中带来显著的正如我们将在下面看到的，事实证明狄利克雷分布族是多项式试验的共轭先验分布族。使用Dirichlet分布作为先验完成了我们将贝叶斯定理应用于事件结构的图景。具体地说，先验狄利克雷分布被分配给ES的每个单元格c。然后，事件计数X用于更新每个单元格处的狄利克雷。 因此，在任何时候，我们对每个单元格c都有一个狄利克雷该单元格的参数Θc我们将证明，结果x∈E的概率是这些分布的某些期望的乘积4.2Dirichlet分布K阶Dirichlet族D，当2≤K∈N时，是一个参数集定义在[0，1]上的连续概率密度函数（pdf）;正实数的K个参数，α =（α1，.，αK），从下式中选择一个特定的Dirichlet分布：516M. Nielsen等人理论计算机科学电子笔记172（2007）499|0Σ||家人 对于变量Θ =（Θ 1，.，Θ K）∈ [0，1] K，pdf由下式给出：ΣΓ（ iαi）α1−1αK−1D（Θα）=我 Γ（αi）·Θ1···ΘK，其中Gamma函数，对于z > 0，Γ（z）=∞tz−1e−tdt，用于定义归一化常数幸运的是，我们不会明确地关注这样一个常数。在我们的应用程序中的主要利益值是期望值和方差的变量分布根据D（·|a）重要的是，只依赖于α。 也就是说，使用[α]作为jαj的简写，我们有：E（Θ）=αiσ2（Θ）=αi（[α]−αi）（三）D（Θ |α）i[α]D（Θ |α）i[α]2（[α]+1）4.3共轭先验考虑一系列具有K元结果的独立实验，每个实验都以某个固定的概率Θi产生结果i;这样的实验是多项试验（在我们的框架中对应于在一个细胞中概率选择一个事件令λD表示收集这种假设的模型，并且令Xi表示第i次试验（i = 1，.，n）。换句话说，Zi≠（Xi=ji）是第i次试验具有结果ji∈ {1，2，. ，K}。 令Z =（Z1，. ，Zn）是n的合取，报表然后，通过多项试验的定义，独立实验的序列具有以下可能性：概率（Z|Θ λD）=ni=1K概率（Zi|Θ λD）=i=1#i（Z）Θi，其中#i（Z）是i在Z中出现的次数。狄利克雷分布构成了这个可能性的共轭先验分布族。为了说明这一事实，让我们回顾一下，贝叶斯定理可以从Θ上的先验分布导出，比如f（Θ |λD），以及实验Z，后验分布f（Θ |ZλD）为：f（Θ Z λD）= f（ΘλD）Prob（Z|Θ λD）。概率（Z|λD）事实上，不难证明，当f（Θ）|λD）是一个Dirichlet分布，比如说D（Θ |α1，... ，αK），则f（Θ |Z λD）也是狄利克雷分布;即，f（Θ |Z λD）=D.ΣΘ |α1 + #1（Z），.，αK+ #K（Z），这正是我们想要的注意，通过对所有i选择αi= 1，狄利克雷分布退化为[0，1]K上的均匀分布。这是非常有用的，因为它为那些在我们的应用程序域中相对频繁的情况M. Nielsen等人理论计算机科学电子笔记172（2007）499517提供了一个方便的无偏见的初始先验，在这些情况下，我们没有关于主体的先验信息。518M. Nielsen等人理论计算机科学电子笔记172（2007）499ΣeeKD我[α]+n4.4Dirichlet模型λD现在让我们考虑语句Zn+1<$（Xn+1=i），然后执行n+ 1实验。我们可以解释Prob（Zn+1|ZλD）作为预测概率：假设没有关于Θ的直接知识，而只有过去的证据（即，Z）和模型（即，λD），则Prob（Zn+1|Z λD）是下一次试验结果i的概率。很容易证明：概率（Z| Zλ ）=E（Θ）=αi+#i（Z）事实上，第n+1个结果是i的预测概率显然是在实验Z之后计算的后验的第i个参数的期望。 然后，给定f（Θ）的上述狄利克雷表达式，|ZλD）和以下事实i#i（Z）=n，结果由期望公式（3）得出。 我们注意到方差公式可以在任何时候用来评估我们预测的准确性：方差越小，预测的可能性越大4.5胞腔上的Dirichlet分布回到我们的事件结构模型，我们将每个单元格c∈C（ES）与一个关于参数Θc的狄利克雷先验分布相关联，该分布决定了c的事件的固定主体的行为。当我们与委托人交互时，我们使用贝叶斯每个单元格c∈C（ES）表示在相互排斥之间的选择c的选择和穷举事件，并且根据λDES的假设，这样的选择是多项试验在任何时候，我们通过乘以配置中每个事件的参数期望值来获得导致特定配置的下一次交互的预测概率。让我们精确地说。设fc（Θ c|λDES）表示c∈ C（ES）的先验分布，设每个e ∈ E对应一个正实数αe. 我们使用αci作为与C1相关联的参数向量的简写，即，（αei，.，αei ）. 我们1Ki然后只剩下调整§4.3的公式的任务。 我们拥有：Γ（[α]）Kiαi−1fc（Θc | λDES) = D (Θc| αc)=e·Θ ik。我我我Kik=1 Γ（αi）K杨永k=1设X：E→N是一个事件计数，它用一个特定的主体对过去运行的观察进行建模。后验pdf如下所示，其中+表示标量和矢量和，并且X（ci）=（X（ei），.，X（ei））.1Ki.ΣKiαi+X（ei）−1fc（Θc| X λDES) = D Θc| αc+ X (ci)=Γ（[αci+X（ci）]）·杨永Θik.我我我Kik=1 Γ（αiK +X（ei））Cin+1个f（Θ|ZλD）