基于迭代分解的特征化概率論辯語(yǔ)義求解方法

陳東恒 廖備水

1 引言

近年來(lái)，抽象論辯是人工智能與邏輯學(xué)領(lǐng)域的重要研究方向，可用于建模不完備、不確定、不一致信息的推理。（[11]）抽象論辯理論的核心概念是論辯框架及其語(yǔ)義。一個(gè)論辯框架由一組論證集合和該集合上的攻擊關(guān)系組成。依據(jù)一定的評(píng)價(jià)標(biāo)準(zhǔn)（稱(chēng)為論辯語(yǔ)義），可以從一個(gè)論辯框架中得到一組論證集合，稱(chēng)之為外延。通過(guò)抽象論辯理論，可以建模不完備或不一致信息推理。

然而，在一些情況下，用于推理的信息不僅具有不完備性，而且具有不確定性。設(shè)有兩個(gè)論證“明天要下雨”和“如果不下雨，那么出門(mén)不要帶雨傘”，前者攻擊后者。這時(shí)，第二個(gè)論證的可接受性，不僅取決于來(lái)自第一個(gè)論證的攻擊，還取決于第一個(gè)論證存在的概率?；谏鲜鰡?wèn)題，在論辯框架中引入概率，使得論證和/或攻擊關(guān)系同特定概率關(guān)聯(lián)，由此得到的論辯框架稱(chēng)為概率論辯框架。

給定一個(gè)概率論辯框架，評(píng)價(jià)一個(gè)論證或一組論證集合的可接受性的方法，是計(jì)算它們可接受的概率。依據(jù)群組方法，把定義在一個(gè)論證上的概率解釋為該論證出現(xiàn)在論辯框架中的概率。對(duì)于一個(gè)包含n個(gè)論證的概率論辯框架，可以構(gòu)造2n個(gè)子框架，每個(gè)子框架表示一個(gè)可能世界；因此，為了評(píng)估一個(gè)論證或一組論證集合的可接受性，需要評(píng)估2n個(gè)子框架，導(dǎo)致計(jì)算效率低。加之多數(shù)情況下，論辯語(yǔ)義的求解均不存在易解的算法（[8]）,計(jì)算難度進(jìn)一步加劇。為了解決該問(wèn)題，我們?cè)谇捌诠ぷ髦刑岢隽艘环N基于特征化子圖的方法，極大提高了計(jì)算效率。

經(jīng)進(jìn)一步研究發(fā)現(xiàn)，在基于特征化子圖的方法中，對(duì)特征子圖的枚舉仍存在有一定盲目性（詳見(jiàn)3.1 節(jié)的分析）。對(duì)此，我們?cè)诒疚闹刑岢隽艘环N基于迭代分解的改進(jìn)方法。

本文剩余部分的結(jié)構(gòu)是這樣安排的：第2 節(jié)回顧本文要涉及的主要概念;第3 節(jié)分析現(xiàn)有特征化概率論辯語(yǔ)義求解方法，為提出進(jìn)一步的優(yōu)化方法奠定基礎(chǔ)；第4 節(jié)提出一種基于迭代分解的外延概率求解方法；最后一節(jié)是結(jié)論和未來(lái)工作。

2 抽象概率論辯理論

抽象概率論辯理論以抽象論辯理論為基礎(chǔ)。后者的核心概念之一是抽象論辯框架。抽象論辯框架（下簡(jiǎn)稱(chēng)AF）可以被看作是一個(gè)有向圖，因此也稱(chēng)為論證圖。

定義2.1(抽象論辯框架，[1]).抽象論辯框架是一個(gè)二元組AF=(Ar,att)。Ar的元素是有向圖的節(jié)點(diǎn)，稱(chēng)為“論證”。att的元素是有向邊，稱(chēng)為“攻擊”。我們用(α,β)∈att表示α攻擊β。

為了書(shū)寫(xiě)方便，有如下的常用縮寫(xiě)規(guī)則。設(shè)α ∈Ar,E ?Ar。

設(shè)Args ?Ar,則論辯框架AF在Args上的投影為(Args,att ∩(Args×Args))，記作AF ↓Args。AF ↓Args稱(chēng)為AF在Args上的關(guān)于Args的一個(gè)限制，或稱(chēng)為AF的一個(gè)子框架。

給定一個(gè)論證圖，把在特定評(píng)價(jià)標(biāo)準(zhǔn)（論辯語(yǔ)義）下集體可接受的論證集合稱(chēng)為一個(gè)外延。在現(xiàn)有文獻(xiàn)[1]中，定義了各種論辯語(yǔ)義下的外延。與本文相關(guān)的部分外延定義如下。

定義2.2(外延).設(shè)AF=(Ar,att)是一個(gè)抽象論辯框架，α ∈E是一個(gè)論證，E ?Ar是一組論證集合。

·E是無(wú)沖突的，當(dāng)且僅當(dāng)不存在α,β ∈E,使得(α,β)∈att。

·E可以防御α，當(dāng)且僅當(dāng)對(duì)任意的β ∈Ar,如果(β,α)∈att,那么存在γ ∈E，使得(γ,β)∈att。

·E是可相容的，當(dāng)且僅當(dāng)E是無(wú)沖突的，且E可以防御其中的每個(gè)論證。

·E是一個(gè)完全外延，當(dāng)且僅當(dāng)E是可相容的，且對(duì)于任意β ∈Ar,如果E可以防御β，那么β ∈E。

·E是一個(gè)優(yōu)先外延，當(dāng)且僅當(dāng)E是一個(gè)極大完全外延。

在下文中，分別用pr和co表示優(yōu)先語(yǔ)義和完全語(yǔ)義,用σ ∈{pr,co}表示其中任何一種語(yǔ)義。依據(jù)上述定義，顯然有pr(AF)?co(AF)。

在抽象論辯的基礎(chǔ)上，當(dāng)考慮論證和/或攻擊關(guān)系的不確定性時(shí)，可以給論證和/或攻擊關(guān)系指派概率，意指它們出現(xiàn)在論證圖中的概率。在本文中，我們僅考慮論證上的不確定性。依據(jù)文獻(xiàn)[2]，我們有如下3 個(gè)定義：

定義2.3(概率論辯框架).概率論辯框架（下簡(jiǎn)稱(chēng)PAF）是一個(gè)三元組(Ar,att,p)。其中(Ar,att)與抽象論辯框架（AF）相同，是一個(gè)論證圖。p:Ar →[0,1]是一個(gè)概率函數(shù)，將Ar中的每個(gè)論證映射為一個(gè)[0,1]上的概率。這個(gè)概率代表該論證在該框架中出現(xiàn)的概率。

定義2.4(子框架概率).對(duì)于論證集Ar的一個(gè)子集Args，PAF ↓Args是PAF的一個(gè)子框架，而p(Args)代表這個(gè)子框架（可能世界）的出現(xiàn)概率。

本文采取獨(dú)立性假設(shè)，即各論證是否出現(xiàn)互相獨(dú)立。因此，子框架概率的定義式為：

該定義式由兩個(gè)累乘式相乘得到。第一個(gè)累乘式代表集合Args中的論證都出現(xiàn)在圖中的概率，第二個(gè)累乘式代表其他論證，即集合Ar/Args的論證都不出現(xiàn)在圖中的概率。兩概率相乘即為子框架概率。

定義2.5(外延概率).對(duì)于屬于某個(gè)語(yǔ)義σ(PAF)的外延E，其外延概率Pσ(E)定義為：

本文擬研究的問(wèn)題是：給定概率論辯框架PAF與外延E，如何高效求解完全外延概率Pco(E)與優(yōu)先外延概率Ppr(E)？以下是一個(gè)求解樣例。

例1.已知PAF結(jié)構(gòu)如圖1 所示，E={a}，求解Pco(E)與Ppr(E)。

E僅在子框架2 和4 中是一個(gè)完全外延，僅在子框架2 和4 中是一個(gè)優(yōu)先外延。因此，Pco(E)=Ppr(E)=p({a,b})+p({a})=0.224+0.096=0.32。

圖1: PAF 的結(jié)構(gòu)圖

3 特征化概率論辯語(yǔ)義求解方法分析

依據(jù)例1 可知，為了求解一個(gè)概率論辯框架的完全外延或優(yōu)先外延的概率，需要構(gòu)造并檢驗(yàn)2n個(gè)子框架，計(jì)算效率低。在文獻(xiàn)[7]和[9]中，我們構(gòu)造了一種基于特征化子圖的高效求解方法。該方法之所以高效的原理分析如下。

依據(jù)定義5，Pco(E)的計(jì)算公式是：

這個(gè)公式要求我們，對(duì)所有的Args ?Ar，都先判斷E是否是子框架AF ↓Args的一個(gè)完全外延。如果是，就求解出其子框架概率p(Args)。然而，Ar的子集有2|Ar|個(gè)，其中包含了許多無(wú)效的子集（指E∈/co(AF ↓Args)）。如果能排除掉這些無(wú)效的子集，計(jì)算的效率會(huì)高許多。下面分析滿(mǎn)足什么條件的子集是無(wú)效的。在下面的敘述中，我們總假定Args是Ar的子集。

第一種最簡(jiǎn)單的情況是，如果Args不包含某個(gè)元素α，則必然失效，也就是E∈/co(AF ↓Args)。如果這樣的元素α存在，那么我們?cè)谟?jì)算外延概率時(shí)，只需要考慮包含α的子集Args就可以了。我們把α所具有的這種性質(zhì)為“必然包含性”。

我們斷言，外延E中的每一個(gè)元素都滿(mǎn)足“必然包含性”。因?yàn)橹挥蠩完整存在于子集Args中，E才有可能是一個(gè)外延。因此，我們發(fā)現(xiàn)，在公式1 中，Args實(shí)際滿(mǎn)足了一個(gè)隱含條件E ?Args。接下來(lái)，我們考慮如何利用這個(gè)隱含條件減少需要枚舉的子集個(gè)數(shù)。

根據(jù)獨(dú)立性假設(shè)。如果集合Args可以分解為兩個(gè)集合的無(wú)交并A1∪A2=Args，則有類(lèi)似的，我們可以將Args分解成E與Args/E。因此，對(duì)公式1 使用這個(gè)分解，得到：

由于P(E)與求和項(xiàng)無(wú)關(guān)，我們將其提到前面。

由于Args總包含E,因此我們不妨將Args ∈2Ar改寫(xiě)成Args=E ∪Args*,Args*∈2Ar/E。代入上式，有：

此時(shí)我們?cè)儆^察求和條件，枚舉域成功從Ar縮小到了Ar/E。從這個(gè)示例中，我們發(fā)現(xiàn)，枚舉域成功縮小的關(guān)鍵在于，我們要對(duì)論證集Ar進(jìn)行分解，變成具有如下性質(zhì)的無(wú)交并。

1.肯定包含于Ar的有效子集的部分，即滿(mǎn)足必然包含性的部分，文獻(xiàn)[9]中指出它就是E。

2.肯定不屬于Ar的有效子集的部分，即滿(mǎn)足必然不包含的部分。文獻(xiàn)[9]中指出，集合E-/E+具有這種性質(zhì)。

3.是否屬于子集Args都不會(huì)影響有效性的部分，文獻(xiàn)[9]中指出就是E+。4.剩余部分，我們記為I。

分成這四個(gè)部分后，外延概率的計(jì)算流程也發(fā)生了改變。我們不再需要考慮Ar所有的子集。對(duì)于滿(mǎn)足必然包含性的集合E，我們直接將其在Args中包含。而對(duì)于必然不能包含的集合E-/E+，我們直接將其在Args中去除。對(duì)于是否包含對(duì)有效性沒(méi)有影響的元素，因?yàn)槠淙怕适?，對(duì)結(jié)果沒(méi)有影響。因此我們也可以不考慮這部分元素。這一步的詳細(xì)過(guò)程，請(qǐng)參考文獻(xiàn)[9]，本文不再贅述。

對(duì)于E與E-/E+,因?yàn)槠涫欠癯霈F(xiàn)在有效Args子集中已經(jīng)完全確定：前者肯定出現(xiàn)，后者肯定不出現(xiàn)。因此我們?cè)O(shè)一個(gè)概率常數(shù)PE,令

其中，第一個(gè)累乘是因?yàn)檫@些元素肯定出現(xiàn)，所以乘它們都出現(xiàn)的概率。第二個(gè)累乘是因?yàn)樗鼈兛隙ú怀霈F(xiàn)，所以乘它們都不出現(xiàn)的概率。而對(duì)于E+中，對(duì)Args有效性沒(méi)有影響的部分，則乘以了全概率1，因此在公式中沒(méi)有體現(xiàn)。因此，對(duì)于E ∪E+∪E-這些元素，其概率已經(jīng)被完全考慮。我們只需要考慮剩余元素即可。

剩余元素的集合是I。此處的B′代指I的子集。公式2 處的求和條件依然考慮了I的所有子集，只是第二個(gè)條件換成了? ∈co(AF ↓B′)。實(shí)際上，這個(gè)條件與E ∈co(AF ↓Args*∪E)是完全等價(jià)的。這個(gè)等價(jià)的具體證明在文獻(xiàn)[9]有詳細(xì)介紹，受篇幅限制本文不再贅述。為了書(shū)寫(xiě)方便，我們對(duì)出現(xiàn)過(guò)的表達(dá)式稍加整理。由于優(yōu)先外延的情況與完全外延完全一致，這里略去推導(dǎo)過(guò)程。我們?cè)O(shè)：

則外延概率的計(jì)算公式可寫(xiě)成如下形式：

相比起根據(jù)外延概率的定義式求解外延概率，公式3 與公式4 取得了一定的進(jìn)步。下面我們以公式3 來(lái)具體分析其進(jìn)步與不足。定義式中的求和條件為：Args ∈2Ar,E ∈co(AF ↓Args)。在定義式中，枚舉域是Ar，共有2|Ar|個(gè)元素。也就意味著，根據(jù)定義式求解外延概率，需要進(jìn)行2|Ar|次外延判斷。而在公式3 中，求和條件為：Args ∈2I,?α ∈Args:α-∩Args/=?，枚舉域?yàn)镮，共有2|I|個(gè)元素。根據(jù)公式3 進(jìn)行外延計(jì)算，只需要做2|I|次外延判斷?？梢?jiàn)，枚舉域縮小k個(gè)元素意味著外延判斷的計(jì)算量縮小為原本的

但是，公式3 使用的枚舉域I是否還有進(jìn)一步縮小的空間呢？這是肯定的。該方法的不足之處在于，它提出了E-/E+確實(shí)具有性質(zhì)E∈co(PAF↓B′)??E-/E+∩B′=?，但并沒(méi)有指出具有這種性質(zhì)的集合就是E-/E+。換言之，可能存在比E-/E+更大的集合滿(mǎn)足該性質(zhì)。

因此,如果我們反其道而行之，這樣定義集合Aout：

定義3.1(Aout).Aout={α|E ∈co(PAF ↓B′)??α∈/B′}

這樣，Aout就成為了滿(mǎn)足“必然不包含性”的全體元素構(gòu)成的集合?？梢钥隙ǖ氖?，E-/E+肯定是Aout的一個(gè)子集。如果我們能設(shè)計(jì)一種算法，找出Aout中，除了E-/E+外的其他元素，那么需要枚舉的集合的元素會(huì)更少。本文將會(huì)在下一小節(jié)詳細(xì)介紹如何找出Aout。

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

在上述公式3 與公式4 中，都有一個(gè)相同的條件被提及：?α ∈B′:α-∩B′/=?。迭代分解的核心是，根據(jù)這個(gè)條件，反復(fù)迭代計(jì)算以擴(kuò)大集合Aout，從而縮小I，以達(dá)到縮小枚舉域的目的。作為迭代初值，我們令A(yù)out ←E-/E+。

4.1 Aout 迭代擴(kuò)展

由于B′是I的一個(gè)子集，因此α-與I無(wú)交集就意味著α-與B′無(wú)交集。而I不會(huì)隨著B(niǎo)′的改變而改變。如果有一個(gè)論證β，滿(mǎn)足β-與I無(wú)交集，那只要β ∈B′，條件?α ∈B′:α-∩B′/=?便不會(huì)被滿(mǎn)足。因此，我們?cè)诳紤]子框架B′時(shí)，可以直接不考慮這樣的論證β，也就是有β ∈Aout。與此同時(shí)，I也失去了元素β。

我們使用賦值表達(dá)式來(lái)描述這一過(guò)程：

在進(jìn)行第一次計(jì)算后，I發(fā)生了變化。因此，滿(mǎn)足條件α-∩I=?的論證α可能又會(huì)出現(xiàn)。因此這個(gè)賦值表達(dá)式的迭代計(jì)算是有意義的。我們反復(fù)計(jì)算迭代式5，直到I不再變化。因?yàn)锳out每一步都在擴(kuò)大，而Aout有有限上界Ar，由單調(diào)有界定理知，Aout必然在有限步內(nèi)停止擴(kuò)大，因此I在有限步內(nèi)達(dá)到迭代的不動(dòng)點(diǎn)。

實(shí)際上，這個(gè)迭代過(guò)程可以看作是從子論證圖PAF ↓I中連續(xù)除去入度為0 的節(jié)點(diǎn)的過(guò)程。接下來(lái)我們簡(jiǎn)要分析這種迭代的性質(zhì)。當(dāng)I是一個(gè)有向無(wú)環(huán)圖時(shí)，存在一個(gè)拓?fù)渑判?。如果我們按照這個(gè)拓?fù)渑判蛉コ?jié)點(diǎn)，每一步都滿(mǎn)足“去除入度為0”的點(diǎn)。因此，對(duì)于I是有向無(wú)環(huán)圖的情況，到達(dá)迭代終點(diǎn)后，I=?。所以，如果迭代終點(diǎn)時(shí)I非空，則I中必然有環(huán)。

迭代分解的另一個(gè)性質(zhì)是，對(duì)于任意的α ∈I，如果α不在環(huán)上，必然存在一條路徑γ1,...,γn，其中γn=α，γ1在環(huán)上。若不然，我們不斷向前延伸γ1。由于I是有限的，這種延伸必然會(huì)在某一節(jié)點(diǎn)處停止，否則便延伸到了環(huán)上，與假設(shè)矛盾。我們記這個(gè)停止的節(jié)點(diǎn)為Γ。這說(shuō)明存在?！蔍，滿(mǎn)足Γ-∩I=?，這說(shuō)明I并沒(méi)有到迭代終點(diǎn)，矛盾。因此，如果α不在環(huán)上，必然存在一條路徑γ1,...,γn，其中γn=α，γ1在環(huán)上。

證明.迭代擴(kuò)展對(duì)于完全語(yǔ)義的極大性。反證：若不是極大的，則存在α ∈I，使得α ∈B′ ??β ∈B′,β-∩B′=?。此時(shí)，我們斷言,必然存在I中的環(huán)R，環(huán)R上存在一條到α的路徑γ1,...,γn。此時(shí)當(dāng)B′=R ∪{γ1,...,γn}，即環(huán)R與路徑的并集作為B′時(shí)，滿(mǎn)足?β ∈B′,β-∩B′/=?，與前文存在β矛盾。因此，迭代擴(kuò)展對(duì)于完全語(yǔ)義是極大的。

4.2 弱聯(lián)通分支分解

定義4.1(弱聯(lián)通分解).對(duì)于論證圖(Ar,att)，弱聯(lián)通分解是將論證圖分為數(shù)個(gè)部分Ar1,Ar2,...,Arn，使得對(duì)于任意α ∈Ari,β ∈Arj，當(dāng)i=j時(shí)，論證圖中存在從α到β或從β到α的路徑。而當(dāng)i/=j時(shí)，既不存在從α到β的路徑，也不存在β到α的路徑。

在經(jīng)過(guò)迭代后，子論證圖PAF ↓I可能產(chǎn)生數(shù)個(gè)互不相連的分支，即數(shù)個(gè)弱聯(lián)通分支。這些聯(lián)通分支彼此獨(dú)立，因此我們可以分而治之。假設(shè)I有n個(gè)弱聯(lián)通分支，分別為I1,I2,...,In，則公式3 與公式4 可寫(xiě)成：

我們可以注意到，經(jīng)過(guò)了這兩步化簡(jiǎn)后，枚舉域的尺寸從最初的單個(gè)Ar/(E ∪E+∪E-)縮小到了Ii。枚舉域的大大減少了程序的儲(chǔ)存占用，加快了運(yùn)行速度。

5 偽代碼與實(shí)驗(yàn)結(jié)果

為了探究新方法是否能有效提高外延概率的計(jì)算速度，我們編寫(xiě)了代碼進(jìn)行模擬實(shí)驗(yàn)。為了盡可能覆蓋所有可能情況，實(shí)驗(yàn)中使用的概率論辯框架為隨機(jī)生成。一個(gè)隨機(jī)生成的概率論辯框架有以下兩個(gè)生成參數(shù)：論證數(shù)和攻擊密度（對(duì)應(yīng)節(jié)點(diǎn)數(shù)和邊密度（邊：節(jié)點(diǎn)））。我們?cè)诓煌蓞?shù)下做了多組實(shí)驗(yàn)。運(yùn)行環(huán)境上，計(jì)算機(jī)使用Intel i7 7700HQ 處理器，主頻2.8Ghz。內(nèi)存采用DDR4 內(nèi)存，主頻2400Mhz,容量32GB。1詳細(xì)配置參數(shù)見(jiàn)代碼鏈接：https://github.com/Sixlain/ProbabilityArgumentation2021.

我們分別使用舊算法和新算法，對(duì)于不同生成參數(shù)的概率論辯框架，求解某個(gè)外延E的優(yōu)先語(yǔ)義，并計(jì)算其平均時(shí)間（單位：s）。外延E的大小為3，滿(mǎn)足無(wú)沖突條件。表1 顯示了新算法與舊算法的平均求解時(shí)間。

表1：不同條件下算法的平均計(jì)算時(shí)間

我們可以看到，新算法的求解速度較舊算法快約2 個(gè)數(shù)量級(jí)。我們分別繪制邊密度為2 時(shí)，舊方法用時(shí)曲線和新方法用時(shí)曲線對(duì)比圖（圖2）。

我們可以確認(rèn)，新算法確實(shí)顯著較舊算法有所提高。這種提高的本質(zhì)在于新算法較舊算法進(jìn)一步縮小了需要枚舉計(jì)算的枚舉域I。我們繪制枚舉域I的平均大小的對(duì)比圖（圖3）。

圖2:對(duì)數(shù)坐標(biāo)下求解時(shí)間比較

圖3:枚舉域I 平均大小比較

表2：大網(wǎng)絡(luò)（n ＞25）中求解率的區(qū)別

我們可以看到，在節(jié)點(diǎn)個(gè)數(shù)較多時(shí)，舊算法的求解率不太穩(wěn)定，在75%上下波動(dòng)。而新算法可以穩(wěn)定在100%。讀取程序錯(cuò)誤信息，我們發(fā)現(xiàn)舊算法求解失敗是因?yàn)閮?nèi)存不足。在實(shí)驗(yàn)過(guò)程中，計(jì)算機(jī)的可用內(nèi)存一直保證在16G 以上，而新算法的總內(nèi)存占用不到1G。由此我們可以發(fā)現(xiàn)，枚舉域的縮小對(duì)減少內(nèi)存占用也大有裨益。

綜上所述，新算法較舊算法，在求解速度，空間占用上都有所提高。在邊密度為2 時(shí)，求解速度平均提高124 倍?？臻g占用上，在節(jié)點(diǎn)數(shù)小于等于30 時(shí)，基本上不存在內(nèi)存溢出的問(wèn)題，求解率從舊算法的75%提升到了100%。

6 結(jié)論與未來(lái)工作

作為邏輯學(xué)與人工智能的交叉研究，形式論辯領(lǐng)域的研究既要考慮系統(tǒng)的表達(dá)能力，又要改善系統(tǒng)的可實(shí)現(xiàn)性。本文不僅從概念上進(jìn)一步澄清了概率論辯語(yǔ)義高效求解的有效途徑，而且在此基礎(chǔ)上提出了一種新方法。經(jīng)過(guò)實(shí)驗(yàn)測(cè)試，該方法通過(guò)對(duì)Aout進(jìn)行極大擴(kuò)展，縮小了枚舉域，提高了問(wèn)題的求解速度，降低了求解的內(nèi)存占用，因此在求解速度上取得了明顯的進(jìn)步，并且求解的成功率也有顯著改善。因此，我們可以認(rèn)定該改進(jìn)是有效的。

作為形式論辯領(lǐng)域的一個(gè)熱點(diǎn)研究方向，關(guān)于概率論辯語(yǔ)義的求解國(guó)內(nèi)外學(xué)者近年來(lái)進(jìn)行了不少探索。在文獻(xiàn)[10]中，作者使用了PrAAF 框架。這種框架在給論證賦予概率的同時(shí)，也給攻擊賦予了概率。然而，文獻(xiàn)中提及的外延概率計(jì)算方法，使用了蒙特卡洛方法，并使用了判別式來(lái)計(jì)算保證模擬的精度。但蒙特卡洛方法的問(wèn)題在于，隨著概率論辯框架的擴(kuò)大，計(jì)算出的外延概率P會(huì)相當(dāng)小。在論證達(dá)到30 個(gè)時(shí)，往往外延概率P只有10-5量級(jí)。為了控制相對(duì)誤差，此處的N，也就是模擬次數(shù)，會(huì)相當(dāng)大，導(dǎo)致蒙特卡洛方法最后的運(yùn)算時(shí)間接近枚舉法甚至超過(guò)枚舉法。這是不可接受的。文獻(xiàn)[6] 也有類(lèi)似的問(wèn)題。在文獻(xiàn)[5]中，作者使用了包含概率的雙極論證框架，并且定義了幾種概率雙極論證到普通概率論辯框架的同態(tài)。這種同態(tài)的核心是支持攻擊，也就是利用支持的可傳遞性，將支持的間接攻擊映射為攻擊。然而，在支持求解的語(yǔ)義方面，作者只考慮了穩(wěn)定語(yǔ)義和可相容語(yǔ)義。而在求解算法上，本質(zhì)上也只是使用了基于無(wú)沖突原則，或是可防御原則的一階分解，其分解程度類(lèi)似于早期工作[7]。在文獻(xiàn)[3,4]中，作者分析了外延概率求解的計(jì)算復(fù)雜度。我們可以從中看到，本文提到的幾個(gè)求解問(wèn)題，都是NP 困難問(wèn)題。

綜上所述，本文在前期的研究工作和其他相關(guān)研究的基礎(chǔ)上進(jìn)行了創(chuàng)新，在一定程度上取得了算法效率的提升。創(chuàng)新點(diǎn)在相關(guān)研究中沒(méi)有提及。

但是，新算法并不能根本上解決這個(gè)NP 困難的問(wèn)題。從對(duì)數(shù)坐標(biāo)來(lái)看，其計(jì)算時(shí)間依然呈現(xiàn)指數(shù)上升的趨勢(shì)。我們認(rèn)為，未來(lái)對(duì)求解算法的優(yōu)化，應(yīng)該同樣著眼于枚舉域的縮小上。一個(gè)很好的思路就是對(duì)網(wǎng)絡(luò)進(jìn)行強(qiáng)連通分解。強(qiáng)連通分解后，網(wǎng)絡(luò)會(huì)呈現(xiàn)出有向無(wú)環(huán)圖的部分性質(zhì)。而定義在有向無(wú)環(huán)圖的貝葉斯網(wǎng)絡(luò)，其求解過(guò)程與外延概率PI_CO的求解有一定的相關(guān)性。如果能善用這種相關(guān)性，或許能極大縮小枚舉域I。另一方面，未來(lái)可以探討如何優(yōu)化PrAAF（[10]）框架下的外延概率求解問(wèn)題。目前相關(guān)的求解算法都以蒙特卡洛和枚舉法為主，算法效率還有較大的提升空間。