基于迭代分解的特征化概率论辩语义求解方法

陈东恒 廖备水

1 引言

近年来，抽象论辩是人工智能与逻辑学领域的重要研究方向，可用于建模不完备、不确定、不一致信息的推理。（[11]）抽象论辩理论的核心概念是论辩框架及其语义。一个论辩框架由一组论证集合和该集合上的攻击关系组成。依据一定的评价标准（称为论辩语义），可以从一个论辩框架中得到一组论证集合，称之为外延。通过抽象论辩理论，可以建模不完备或不一致信息推理。

然而，在一些情况下，用于推理的信息不仅具有不完备性，而且具有不确定性。设有两个论证“明天要下雨”和“如果不下雨，那么出门不要带雨伞”，前者攻击后者。这时，第二个论证的可接受性，不仅取决于来自第一个论证的攻击，还取决于第一个论证存在的概率。基于上述问题，在论辩框架中引入概率，使得论证和/或攻击关系同特定概率关联，由此得到的论辩框架称为概率论辩框架。

给定一个概率论辩框架，评价一个论证或一组论证集合的可接受性的方法，是计算它们可接受的概率。依据群组方法，把定义在一个论证上的概率解释为该论证出现在论辩框架中的概率。对于一个包含n个论证的概率论辩框架，可以构造2n个子框架，每个子框架表示一个可能世界；因此，为了评估一个论证或一组论证集合的可接受性，需要评估2n个子框架，导致计算效率低。加之多数情况下，论辩语义的求解均不存在易解的算法（[8]）,计算难度进一步加剧。为了解决该问题，我们在前期工作中提出了一种基于特征化子图的方法，极大提高了计算效率。

经进一步研究发现，在基于特征化子图的方法中，对特征子图的枚举仍存在有一定盲目性（详见3.1 节的分析）。对此，我们在本文中提出了一种基于迭代分解的改进方法。

本文剩余部分的结构是这样安排的：第2 节回顾本文要涉及的主要概念;第3 节分析现有特征化概率论辩语义求解方法，为提出进一步的优化方法奠定基础；第4 节提出一种基于迭代分解的外延概率求解方法；最后一节是结论和未来工作。

2 抽象概率论辩理论

抽象概率论辩理论以抽象论辩理论为基础。后者的核心概念之一是抽象论辩框架。抽象论辩框架（下简称AF）可以被看作是一个有向图，因此也称为论证图。

定义2.1(抽象论辩框架，[1]).抽象论辩框架是一个二元组AF=(Ar,att)。Ar的元素是有向图的节点，称为“论证”。att的元素是有向边，称为“攻击”。我们用(α,β)∈att表示α攻击β。

为了书写方便，有如下的常用缩写规则。设α ∈Ar,E ⊆Ar。

设Args ⊆Ar,则论辩框架AF在Args上的投影为(Args,att ∩(Args×Args))，记作AF ↓Args。AF ↓Args称为AF在Args上的关于Args的一个限制，或称为AF的一个子框架。

给定一个论证图，把在特定评价标准（论辩语义）下集体可接受的论证集合称为一个外延。在现有文献[1]中，定义了各种论辩语义下的外延。与本文相关的部分外延定义如下。

定义2.2(外延).设AF=(Ar,att)是一个抽象论辩框架，α ∈E是一个论证，E ⊆Ar是一组论证集合。

·E是无冲突的，当且仅当不存在α,β ∈E,使得(α,β)∈att。

·E可以防御α，当且仅当对任意的β ∈Ar,如果(β,α)∈att,那么存在γ ∈E，使得(γ,β)∈att。

·E是可相容的，当且仅当E是无冲突的，且E可以防御其中的每个论证。

·E是一个完全外延，当且仅当E是可相容的，且对于任意β ∈Ar,如果E可以防御β，那么β ∈E。

·E是一个优先外延，当且仅当E是一个极大完全外延。

在下文中，分别用pr和co表示优先语义和完全语义,用σ ∈{pr,co}表示其中任何一种语义。依据上述定义，显然有pr(AF)⊆co(AF)。

在抽象论辩的基础上，当考虑论证和/或攻击关系的不确定性时，可以给论证和/或攻击关系指派概率，意指它们出现在论证图中的概率。在本文中，我们仅考虑论证上的不确定性。依据文献[2]，我们有如下3 个定义：

定义2.3(概率论辩框架).概率论辩框架（下简称PAF）是一个三元组(Ar,att,p)。其中(Ar,att)与抽象论辩框架（AF）相同，是一个论证图。p:Ar →[0,1]是一个概率函数，将Ar中的每个论证映射为一个[0,1]上的概率。这个概率代表该论证在该框架中出现的概率。

定义2.4(子框架概率).对于论证集Ar的一个子集Args，PAF ↓Args是PAF的一个子框架，而p(Args)代表这个子框架（可能世界）的出现概率。

本文采取独立性假设，即各论证是否出现互相独立。因此，子框架概率的定义式为：

该定义式由两个累乘式相乘得到。第一个累乘式代表集合Args中的论证都出现在图中的概率，第二个累乘式代表其他论证，即集合Ar/Args的论证都不出现在图中的概率。两概率相乘即为子框架概率。

定义2.5(外延概率).对于属于某个语义σ(PAF)的外延E，其外延概率Pσ(E)定义为：

本文拟研究的问题是：给定概率论辩框架PAF与外延E，如何高效求解完全外延概率Pco(E)与优先外延概率Ppr(E)？以下是一个求解样例。

例1.已知PAF结构如图1 所示，E={a}，求解Pco(E)与Ppr(E)。

E仅在子框架2 和4 中是一个完全外延，仅在子框架2 和4 中是一个优先外延。因此，Pco(E)=Ppr(E)=p({a,b})+p({a})=0.224+0.096=0.32。

图1: PAF 的结构图

3 特征化概率论辩语义求解方法分析

依据例1 可知，为了求解一个概率论辩框架的完全外延或优先外延的概率，需要构造并检验2n个子框架，计算效率低。在文献[7]和[9]中，我们构造了一种基于特征化子图的高效求解方法。该方法之所以高效的原理分析如下。

依据定义5，Pco(E)的计算公式是：

这个公式要求我们，对所有的Args ⊆Ar，都先判断E是否是子框架AF ↓Args的一个完全外延。如果是，就求解出其子框架概率p(Args)。然而，Ar的子集有2|Ar|个，其中包含了许多无效的子集（指E∈/co(AF ↓Args)）。如果能排除掉这些无效的子集，计算的效率会高许多。下面分析满足什么条件的子集是无效的。在下面的叙述中，我们总假定Args是Ar的子集。

第一种最简单的情况是，如果Args不包含某个元素α，则必然失效，也就是E∈/co(AF ↓Args)。如果这样的元素α存在，那么我们在计算外延概率时，只需要考虑包含α的子集Args就可以了。我们把α所具有的这种性质为“必然包含性”。

我们断言，外延E中的每一个元素都满足“必然包含性”。因为只有E完整存在于子集Args中，E才有可能是一个外延。因此，我们发现，在公式1 中，Args实际满足了一个隐含条件E ⊆Args。接下来，我们考虑如何利用这个隐含条件减少需要枚举的子集个数。

根据独立性假设。如果集合Args可以分解为两个集合的无交并A1∪A2=Args，则有类似的，我们可以将Args分解成E与Args/E。因此，对公式1 使用这个分解，得到：

由于P(E)与求和项无关，我们将其提到前面。

由于Args总包含E,因此我们不妨将Args ∈2Ar改写成Args=E ∪Args*,Args*∈2Ar/E。代入上式，有：

此时我们再观察求和条件，枚举域成功从Ar缩小到了Ar/E。从这个示例中，我们发现，枚举域成功缩小的关键在于，我们要对论证集Ar进行分解，变成具有如下性质的无交并。

1.肯定包含于Ar的有效子集的部分，即满足必然包含性的部分，文献[9]中指出它就是E。

2.肯定不属于Ar的有效子集的部分，即满足必然不包含的部分。文献[9]中指出，集合E-/E+具有这种性质。

3.是否属于子集Args都不会影响有效性的部分，文献[9]中指出就是E+。4.剩余部分，我们记为I。

分成这四个部分后，外延概率的计算流程也发生了改变。我们不再需要考虑Ar所有的子集。对于满足必然包含性的集合E，我们直接将其在Args中包含。而对于必然不能包含的集合E-/E+，我们直接将其在Args中去除。对于是否包含对有效性没有影响的元素，因为其全概率是1，对结果没有影响。因此我们也可以不考虑这部分元素。这一步的详细过程，请参考文献[9]，本文不再赘述。

对于E与E-/E+,因为其是否出现在有效Args子集中已经完全确定：前者肯定出现，后者肯定不出现。因此我们设一个概率常数PE,令

其中，第一个累乘是因为这些元素肯定出现，所以乘它们都出现的概率。第二个累乘是因为它们肯定不出现，所以乘它们都不出现的概率。而对于E+中，对Args有效性没有影响的部分，则乘以了全概率1，因此在公式中没有体现。因此，对于E ∪E+∪E-这些元素，其概率已经被完全考虑。我们只需要考虑剩余元素即可。

剩余元素的集合是I。此处的B′代指I的子集。公式2 处的求和条件依然考虑了I的所有子集，只是第二个条件换成了Ø ∈co(AF ↓B′)。实际上，这个条件与E ∈co(AF ↓Args*∪E)是完全等价的。这个等价的具体证明在文献[9]有详细介绍，受篇幅限制本文不再赘述。为了书写方便，我们对出现过的表达式稍加整理。由于优先外延的情况与完全外延完全一致，这里略去推导过程。我们设：

则外延概率的计算公式可写成如下形式：

相比起根据外延概率的定义式求解外延概率，公式3 与公式4 取得了一定的进步。下面我们以公式3 来具体分析其进步与不足。定义式中的求和条件为：Args ∈2Ar,E ∈co(AF ↓Args)。在定义式中，枚举域是Ar，共有2|Ar|个元素。也就意味着，根据定义式求解外延概率，需要进行2|Ar|次外延判断。而在公式3 中，求和条件为：Args ∈2I,∀α ∈Args:α-∩Args/=Ø，枚举域为I，共有2|I|个元素。根据公式3 进行外延计算，只需要做2|I|次外延判断。可见，枚举域缩小k个元素意味着外延判断的计算量缩小为原本的

但是，公式3 使用的枚举域I是否还有进一步缩小的空间呢？这是肯定的。该方法的不足之处在于，它提出了E-/E+确实具有性质E∈co(PAF↓B′)⇐⇒E-/E+∩B′=Ø，但并没有指出具有这种性质的集合就是E-/E+。换言之，可能存在比E-/E+更大的集合满足该性质。

因此,如果我们反其道而行之，这样定义集合Aout：

定义3.1(Aout).Aout={α|E ∈co(PAF ↓B′)⇐⇒α∈/B′}

这样，Aout就成为了满足“必然不包含性”的全体元素构成的集合。可以肯定的是，E-/E+肯定是Aout的一个子集。如果我们能设计一种算法，找出Aout中，除了E-/E+外的其他元素，那么需要枚举的集合的元素会更少。本文将会在下一小节详细介绍如何找出Aout。

4 基于迭代分解的外延概率求解方法

在上述公式3 与公式4 中，都有一个相同的条件被提及：∀α ∈B′:α-∩B′/=Ø。迭代分解的核心是，根据这个条件，反复迭代计算以扩大集合Aout，从而缩小I，以达到缩小枚举域的目的。作为迭代初值，我们令Aout ←E-/E+。

4.1 Aout 迭代扩展

由于B′是I的一个子集，因此α-与I无交集就意味着α-与B′无交集。而I不会随着B′的改变而改变。如果有一个论证β，满足β-与I无交集，那只要β ∈B′，条件∀α ∈B′:α-∩B′/=Ø便不会被满足。因此，我们在考虑子框架B′时，可以直接不考虑这样的论证β，也就是有β ∈Aout。与此同时，I也失去了元素β。

我们使用赋值表达式来描述这一过程：

在进行第一次计算后，I发生了变化。因此，满足条件α-∩I=Ø的论证α可能又会出现。因此这个赋值表达式的迭代计算是有意义的。我们反复计算迭代式5，直到I不再变化。因为Aout每一步都在扩大，而Aout有有限上界Ar，由单调有界定理知，Aout必然在有限步内停止扩大，因此I在有限步内达到迭代的不动点。

实际上，这个迭代过程可以看作是从子论证图PAF ↓I中连续除去入度为0 的节点的过程。接下来我们简要分析这种迭代的性质。当I是一个有向无环图时，存在一个拓扑排序。如果我们按照这个拓扑排序去除节点，每一步都满足“去除入度为0”的点。因此，对于I是有向无环图的情况，到达迭代终点后，I=Ø。所以，如果迭代终点时I非空，则I中必然有环。

迭代分解的另一个性质是，对于任意的α ∈I，如果α不在环上，必然存在一条路径γ1,...,γn，其中γn=α，γ1在环上。若不然，我们不断向前延伸γ1。由于I是有限的，这种延伸必然会在某一节点处停止，否则便延伸到了环上，与假设矛盾。我们记这个停止的节点为Γ。这说明存在Γ∈I，满足Γ-∩I=Ø，这说明I并没有到迭代终点，矛盾。因此，如果α不在环上，必然存在一条路径γ1,...,γn，其中γn=α，γ1在环上。

证明.迭代扩展对于完全语义的极大性。反证：若不是极大的，则存在α ∈I，使得α ∈B′ ⇒∃β ∈B′,β-∩B′=Ø。此时，我们断言,必然存在I中的环R，环R上存在一条到α的路径γ1,...,γn。此时当B′=R ∪{γ1,...,γn}，即环R与路径的并集作为B′时，满足∀β ∈B′,β-∩B′/=Ø，与前文存在β矛盾。因此，迭代扩展对于完全语义是极大的。

4.2 弱联通分支分解

定义4.1(弱联通分解).对于论证图(Ar,att)，弱联通分解是将论证图分为数个部分Ar1,Ar2,...,Arn，使得对于任意α ∈Ari,β ∈Arj，当i=j时，论证图中存在从α到β或从β到α的路径。而当i/=j时，既不存在从α到β的路径，也不存在β到α的路径。

在经过迭代后，子论证图PAF ↓I可能产生数个互不相连的分支，即数个弱联通分支。这些联通分支彼此独立，因此我们可以分而治之。假设I有n个弱联通分支，分别为I1,I2,...,In，则公式3 与公式4 可写成：

我们可以注意到，经过了这两步化简后，枚举域的尺寸从最初的单个Ar/(E ∪E+∪E-)缩小到了Ii。枚举域的大大减少了程序的储存占用，加快了运行速度。

5 伪代码与实验结果

为了探究新方法是否能有效提高外延概率的计算速度，我们编写了代码进行模拟实验。为了尽可能覆盖所有可能情况，实验中使用的概率论辩框架为随机生成。一个随机生成的概率论辩框架有以下两个生成参数：论证数和攻击密度（对应节点数和边密度（边：节点））。我们在不同生成参数下做了多组实验。运行环境上，计算机使用Intel i7 7700HQ 处理器，主频2.8Ghz。内存采用DDR4 内存，主频2400Mhz,容量32GB。1详细配置参数见代码链接：https://github.com/Sixlain/ProbabilityArgumentation2021.

我们分别使用旧算法和新算法，对于不同生成参数的概率论辩框架，求解某个外延E的优先语义，并计算其平均时间（单位：s）。外延E的大小为3，满足无冲突条件。表1 显示了新算法与旧算法的平均求解时间。

表1：不同条件下算法的平均计算时间

我们可以看到，新算法的求解速度较旧算法快约2 个数量级。我们分别绘制边密度为2 时，旧方法用时曲线和新方法用时曲线对比图（图2）。

我们可以确认，新算法确实显著较旧算法有所提高。这种提高的本质在于新算法较旧算法进一步缩小了需要枚举计算的枚举域I。我们绘制枚举域I的平均大小的对比图（图3）。

图2:对数坐标下求解时间比较

图3:枚举域I 平均大小比较

表2：大网络（n ＞25）中求解率的区别

我们可以看到，在节点个数较多时，旧算法的求解率不太稳定，在75%上下波动。而新算法可以稳定在100%。读取程序错误信息，我们发现旧算法求解失败是因为内存不足。在实验过程中，计算机的可用内存一直保证在16G 以上，而新算法的总内存占用不到1G。由此我们可以发现，枚举域的缩小对减少内存占用也大有裨益。

综上所述，新算法较旧算法，在求解速度，空间占用上都有所提高。在边密度为2 时，求解速度平均提高124 倍。空间占用上，在节点数小于等于30 时，基本上不存在内存溢出的问题，求解率从旧算法的75%提升到了100%。

6 结论与未来工作

作为逻辑学与人工智能的交叉研究，形式论辩领域的研究既要考虑系统的表达能力，又要改善系统的可实现性。本文不仅从概念上进一步澄清了概率论辩语义高效求解的有效途径，而且在此基础上提出了一种新方法。经过实验测试，该方法通过对Aout进行极大扩展，缩小了枚举域，提高了问题的求解速度，降低了求解的内存占用，因此在求解速度上取得了明显的进步，并且求解的成功率也有显著改善。因此，我们可以认定该改进是有效的。

作为形式论辩领域的一个热点研究方向，关于概率论辩语义的求解国内外学者近年来进行了不少探索。在文献[10]中，作者使用了PrAAF 框架。这种框架在给论证赋予概率的同时，也给攻击赋予了概率。然而，文献中提及的外延概率计算方法，使用了蒙特卡洛方法，并使用了判别式来计算保证模拟的精度。但蒙特卡洛方法的问题在于，随着概率论辩框架的扩大，计算出的外延概率P会相当小。在论证达到30 个时，往往外延概率P只有10-5量级。为了控制相对误差，此处的N，也就是模拟次数，会相当大，导致蒙特卡洛方法最后的运算时间接近枚举法甚至超过枚举法。这是不可接受的。文献[6] 也有类似的问题。在文献[5]中，作者使用了包含概率的双极论证框架，并且定义了几种概率双极论证到普通概率论辩框架的同态。这种同态的核心是支持攻击，也就是利用支持的可传递性，将支持的间接攻击映射为攻击。然而，在支持求解的语义方面，作者只考虑了稳定语义和可相容语义。而在求解算法上，本质上也只是使用了基于无冲突原则，或是可防御原则的一阶分解，其分解程度类似于早期工作[7]。在文献[3,4]中，作者分析了外延概率求解的计算复杂度。我们可以从中看到，本文提到的几个求解问题，都是NP 困难问题。

综上所述，本文在前期的研究工作和其他相关研究的基础上进行了创新，在一定程度上取得了算法效率的提升。创新点在相关研究中没有提及。

但是，新算法并不能根本上解决这个NP 困难的问题。从对数坐标来看，其计算时间依然呈现指数上升的趋势。我们认为，未来对求解算法的优化，应该同样着眼于枚举域的缩小上。一个很好的思路就是对网络进行强连通分解。强连通分解后，网络会呈现出有向无环图的部分性质。而定义在有向无环图的贝叶斯网络，其求解过程与外延概率PI_CO的求解有一定的相关性。如果能善用这种相关性，或许能极大缩小枚举域I。另一方面，未来可以探讨如何优化PrAAF（[10]）框架下的外延概率求解问题。目前相关的求解算法都以蒙特卡洛和枚举法为主，算法效率还有较大的提升空间。