抽象论证中扩展的多样性

# 抽象论证中扩展的多样性
来源：https://arxiv.org/html/2605.13332
Department of Computer and Information Science \(IDA\), Linköping University, Swedenjohannes\.fichte@liu\.sehttps://orcid\.org/0000\-0002\-8681\-7470 University of Potsdam, Germany & University of Artois, CNRS, UMR8188 \(CRIL\), France hecher@cril\.frhttps://orcid\.org/0000\-0003\-0131\-6771 Data Science Group, Heinz Nixdorf Institute, Paderborn University, Germanyyasir\.mahmood@uni\-paderborn\.dehttps://orcid\.org/0000\-0002\-5651\-5391 Data Science Group, Heinz Nixdorf Institute, Paderborn University, Germanyzwang@mail\.uni\-paderborn\.de\\CopyrightYasir Mahmood, Markus Hecher, Johannes K\. Fichte and Zhengjun Wang\\ccsdesc\[100\]Computing methodologies Knowledge representation and reasoning\\hideLIPIcs

###### 摘要

论证是人工智能中用于建模和推理论证的重要主题。在抽象论证中，我们考虑有向图，即所谓的*论证框架（AF）*，它表示论证之间的冲突。语义通过*扩展*的概念来定义，这些扩展是满足AF中特定关系条件的论证集合。通常，论证中的标准推理并不揭示扩展之间的*差异程度*。

我们引入了一种基于对称差的扩展*多样性*的量化概念，并提供了系统的复杂性分类。直观上，多样性捕捉的是框架的扩展（即被接受的观点）是仅存在细微差别，还是代表根本不相容的论证集合。我们研究了AF是否具有k-多样扩展，是否具有k-多样扩展且覆盖特定论证，以及计算AF具有k-多样扩展的最大k值。我们展示了一个原型实现，并提供了计算多样性水平的评估。

###### 关键词：

抽象论证，多样性，计算复杂性

## 1 引言

抽象论证 [Dung95a,Rahwan07a,BaroniCaminadaGiacomin11] 是人工智能中一个众所周知的概念，用于对论证进行建模、关联和分组 [AmgoudPrade09a,RagoCocarascuToni18a]。为了表达对立立场，论证以有向图的形式相互关联，即所谓的*论证框架（AF）*。满足特定关系条件（语义）的论证集合（*扩展*）构成了AF的解。通常，一个AF具有多个扩展，换句话说，它们是相互不相容但内部一致的共同可接受论证集合，可以被理解为同一论证情境下不同的“观点”。

抽象论证研究引入了一些概念，以便深入了解不同的扩展，例如，解释和选择最具代表性的观点集合 [BernreiterMalyNardi24]，在多个扩展之间进行决策 [DauphinCramerVan\-der\-Torre18]，探索大型解空间 [DachseltGagglKrotzsch22]，确定单个论证的重要性 [MahmoodEtAl25]，一个或多个论证出现在扩展中的条件概率 [FichteH0M23]，扩展计数 [FichteHecherMeier24]，以及引入对论证的预排序（扩展排序语义）[SkibaRienstraThimm21]。

然而，现有概念并不揭示整个扩展之间的*相距程度*和*多样性*，也不揭示*AF的多样性程度*。这在我们需要协商立场的环境中尤为有趣。不同的观点可能合理地支持不同的扩展。如果我们只考虑任意选择的一个扩展、一个代表性扩展或部分扩展，我们很容易掩盖真正的权衡并阻碍达成一致。为此，我们研究多样扩展，并引入一种基于对称差的扩展多样性量化概念。两个集合AA和BB的*对称差* A△BA\\triangle B 取那些恰好属于其中一个集合而不属于两者的元素，即 A△B:=\(A∪B\)∖\(A∩B\)A\\triangle B\\,\\mathrel\{\\mathop\{:\}=}\(A\\cup B\)\\setminus\(A\\cap B\)。 例1.1（https://arxiv.org/html/2605.13332#S1.Thmtheorem1）说明了一种我们感兴趣于理解扩展多样性的情况。

参见图注

图1：一个模拟医疗决策的示例AF。

###### 例 1.1.

考虑一个 AF F=\(A,R\)F=\(A,R\)，模拟时间压力下的医疗决策，如图1（https://arxiv.org/html/2605.13332#S1.F1）所示。FF中的论证具有以下直观含义：

- •sx (StartX)：立即开始治疗X。
- •sy (StartY)：立即开始治疗Y。
- •rx (RiskX)：由于没有立即决策，必须首先仔细评估X的长期风险。
- •ey (EffectiveY)：由于没有立即决策，Y的有效性需要进一步测试。
- •bx (BenefitsX)：X具有显著的短期效益。
- •lry (LowRiskY)：Y的副作用较小。
- •w (Wait)：在决策前收集更多数据。

在稳定语义下，其直观含义是表达一个自我一致且击败所有替代方案的观点，FF恰好有三个扩展。具体来说，EX=\{sx,bx,ey\},EY=\{sy,lry,rx\}E\_\{X\}=\\\{sx,bx,ey\\\},E\_\{Y\}=\\\{sy,lry,rx\\\}, 和 EW=\{w,rx,ey\}E\_\{W\}=\\\{w,rx,ey\\\}，每个扩展分别突出了一种治疗类型或等待更多数据的论点。

这里，关于最终决策最重要的三个论证是sx,sysx,sy和ww，它们分别选择一种治疗类型或主张等待。这些论证中的每一个都出现在某个扩展中（即轻信接受）。因此，我们无法对这三种选择中的任意一种得出太多信息。但从所有可用选项（稳定扩展）的全局视角来看，我们观察到，两种治疗的扩展之间完全不共享任何论证，而它们与迫使等待的扩展（EWE\_\{W\}）至少共享一个论证。具体来说，EX△EY=\{sx,bx,ey,sy,lry,rx\}E\_\{X\}\\triangle E\_\{Y\}=\\\{sx,bx,ey,sy,lry,rx\\\}，这表示我们视选项“StartX”和“StartY”为6-多样。然而，我们有EX△EW=\{sx,bx,rx,w\}E\_\{X\}\\triangle E\_\{W\}=\\\{sx,bx,rx,w\\\}，和EY△EW=\{sy,lry,ey,w\}E\_\{Y\}\\triangle E\_\{W\}=\\\{sy,lry,ey,w\\\}。因此，我们观察到选项“StartX”（或“StartY”）与“Wait”仅为4-多样。直观上，这意味着两种治疗类型的理由使用非常“不同”的推理路线，而两种治疗选项都至少与第三种选项（在决策前稍等）共享一些推理。或者说，“StartX”的理由与“Wait”的理由相比“StartY”有些*相似*。⊲\\triangleleft

贡献。我们的主要贡献如下：

1. 1. 我们将基于对称差的多样性概念引入抽象论证，并研究其性质。我们展示了多样性如何与现有概念不同，并提供了比基于轻信和怀疑推理的概念更细粒度的视角。
2. 2. 我们研究了核心问题（最多、至少、恰好k-多样，最大多样性）的计算复杂性，并提供了复杂性全景的完整图景，见表1（https://arxiv.org/html/2605.13332#S1.T1）。
3. 3. 我们提供了原型实现和初步实验评估，通过逻辑编程（ASP）计算多样性范围。

表1：语义 σ1∈\{conf,naiv\}\\sigma\_\{1\}\\in\\\{\\mathsf\{conf\},\\mathsf\{naiv\}\\\}, σ2∈\{adm,stab,comp\}\\sigma\_\{2\}\\in\\\{\\mathsf\{adm\},\\mathsf\{stab\},\\mathsf\{comp\}\\\}, 和 σ3∈\{semiSt,\\sigma\_\{3\}\\in\\\{\\mathsf\{semiSt\},stag\}\\mathsf\{stag\}\\\} 的复杂性结果概览。问题“Arg”询问两个论证是否k-多样，“Ext”询问AF是否具有两个k-多样σ\\sigma扩展。对于k≤\-Div\-Argσ\\,\{\}^\{\leq\}\\mathsf\{k\\text\{\-\}Div\\text{\-\}Arg\}\_\{\\sigma\}的结果也适用于每个σ\\sigma的k\-Div\-Argσ\\mathsf\{k\\text{\-\}Div\\text{\-\}Arg\}\_\{\\sigma\}。我们陈述的证明可在本pdf末尾的技术附录中找到。实现代码可在我们的GitHub仓库111https://github.com/Yahahasir/argu\_diversity/在线获取。

##### 相关工作。

[CyrasRagoAlbini21] 从可解释人工智能（XAI）的角度调查了基于论证的解释。[LiaoTorre20] 引入并研究了解释语义，该语义为每个被接受的论证关联一组这样的解释论证。[NiskanenJarvisalo20a] 和 [SaribaturWallnerWoltran20] 研究了论证被拒绝的相反情况，并分析了拒绝的原因。尽管已经研究了论证的计数复杂性 [FichteHecherMeier24]，但结果并不适用于此处，因为我们的重点是扩展空间中元素之间的距离。有许多用于决策和推理任务的实用求解器 [EglyGagglWoltran08,NiskanenJarvisalo20,ThimmCeruttiVallati21,Alviano18,Alviano21]，它们参与两年一度的ICCMA竞赛 [ThimmEtAl24]。

[MahmoodEtAl25] 为抽象论证提出了方面（ facets），能够量化决策的重要性并研究计算复杂性。方面不捕捉包含它们的扩展的信息，而多样性衡量AF中接受的论证集合的（不）相似性。[bohl2023representative] 考虑了答案集编程中的多样性和代表性集合。[UlbrichtWallner21] 考虑了强解释，确保目标论证集合在包含解释集合的每个子框架中都是可接受的。[BesnardDoutreDuchatelle22] 研究了关于解释的对比性和非对比性问题。在约束编程 [HebrardHnichOSullivan05] 和答案集编程 [EiterErdemErdogan13] 中已经考虑过寻找相似和多样化解的问题。[Rodrigues19] 比较了用于系统枚举扩展的不同替代表示。[Coste\-MarquisKoniecznyMailly15] 使用汉明距离来定义强制算子，这与之前最小变化上下文中的工作类似 [Baumann12]。[DachseltGagglKrotzsch22] 开发了一个使用ASP方面导航论证框架的工具，更细粒度的推理模式也已在ASP中得到研究 [FichteHecherNadeem22]。注意，ASP导航基于通过完整性约束禁止或强制程序中的原子。

## 2 预备知识

我们假设读者熟悉计算复杂性 [DBLP:books/daglib/0092426]、图论 [DBLP:books/sp/BondyM08] 和布尔逻辑 [DBLP:series/faia/336]。

##### 复杂性类。

我们使用基本复杂性类的标准表示法，例如，P（NP）表示可在（非确定性）多项式时间内求解的决策问题类。此外，coNP表示其补问题属于NP的决策问题类，DP表示可表示为NP中问题与coNP中问题交集的决策问题类。在此基础上，我们使用多项式层次 [StockmeyerMeyer73,Stockmeyer76,Wrathall76] 中的更多类：Δ0P:=Π0P:=Σ0P:=P\\bm\{\\Delta\}^\{\{\\textbf{P}\}\}\_\{0\}\\mathrel\{\\mathop\{:\}\}=\\bm\{\\mathrm\{\\Pi\}\}^\{\{\\textbf{P}\}\}\_\{0\}\\mathrel\{\\mathop\{:\}\}=\\bm\{\\mathrm\{\\Sigma\}\}^\{\{\\textbf{P}\}\}\_\{0\}\\mathrel\{\\mathop\{:\}\}=\{\\textbf\{P\}\}，对于 i\>0i\>0，ΔiP:=PΣi−1P\\bm\{\\Delta\}^\{\{\\textbf{P}\}\}\_\{i\}\\mathrel\{\\mathop\{:\}\}=\{\\textbf\{P\}\}^\{\\bm\{\\mathrm\{\\Sigma\}\}^\{\{\\textbf{P}\}\}\_\{i\-1\}\}，ΣiP:=NPΣi−1P\\bm\{\\mathrm\{\\Sigma\}\}^\{\{\\textbf{P}\}\}\_\{i\}\\mathrel\{\\mathop\{:\}\}=\\textbf\{NP\}^\{\\bm\{\\mathrm\{\\Sigma\}\}^\{\{\\textbf{P}\}\}\_\{i\-1\}\}，ΠiP:=coNPΣi−1P\\bm\{\\mathrm\{\\Pi\}\}^\{\{\\textbf{P}\}\}\_\{i\}\\mathrel\{\\mathop\{:\}\}=\\text\{co\}\\textbf\{NP\}^\{\\bm\{\\mathrm\{\\Sigma\}\}^\{\{\\textbf{P}\}\}\_\{i\-1\}\}，其中 CDC^\{D\} 是决策问题类CC通过D类中某个完全问题的预言机增强后的类。复杂性类DPk\\textbf\{DP\}\_\{k\} 定义为 DPk:=\{L1∩L2∣L1∈ΣkP,L2∈ΠkP\}\\textbf\{DP\}\_\{k\}\\mathrel\{\\mathop\{:\}\}=\\\{L\_\{1\}\\cap L\_\{2\}\\mid L\_\{1\}\\in\\bm\{\\mathrm\{\\Sigma\}\}^\{\{\\textbf\{P\}\}\}\_\{k\},L\_\{2\}\\in\\bm\{\\mathrm\{\\Pi\}\}^\{\{\\textbf\{P\}\}\}\_\{k\}\\\}，DP=DP1\\textbf\{DP\}\{=\}\\textbf\{DP\}\_\{1\} [LohreyRosowski23]。

合取范式（CNF）公式的布尔可满足性问题（SAT）询问：给定 φ=⋀i=1mCi\\varphi=\\bigwedge\_\{i=1\}^\{m\}C\_\{i\}，其中每个 CiC\_\{i\} 是一个子句，判定 φ\\varphi 是否至少有一个满足赋值。SAT是最著名的NP完全问题之一，而其互补问题（检查不可满足性）是coNP完全的。此外，对于给定的一对公式 (φ,ψ)(\\varphi,\\psi)，检查 φ\\varphi 是否可满足且 ψ\\psi 不可满足（即SAT-UNSAT问题）是DP完全的。对于 Π2P\\bm\{\\mathrm\{\\Pi\}\}^\{\{\\textbf\{P\}\}\}\_\{2\}，通常考虑形如 ∀X∃Y\.φ\\forall X\\exists Y\.\\varphi 的量词布尔公式的求值问题，其中XX和YY是两个不相交的变量集合，φ\\varphi是关于XX和YY的CNF公式。最后，Σ2P\\bm\{\\Sigma\}^\{\{\\textbf\{P\}\}\}\_\{2\} 的问题是检查 ∀X∃Y\.φ\\forall X\\exists Y\.\\varphi 是否为假。

##### 抽象论证。

我们使用Dung的论证框架 [Dung95a]，并仅考虑非空有限的论证集合AA。一个*（论证）框架（AF）* 是一个有向图 F=\(A,R\)F=\(A,R\)，其中AA是论证集合，R⊆A×AR\\subseteq A\\times A 包含表示论证之间直接攻击的序对。令 E⊆AE\\subseteq A 且 a∈Aa\\in A 为一个论证。那么我们说 aa 在FF中被EE*辩护*，如果对于每个 (a′,a)∈R(a^\{\\prime\},a)\\in R，都存在 a′′∈Ea^\{\\prime\\prime\}\\in E 使得 (a′′,a′)∈R(a^\{\\prime\\prime\},a^\{\\prime\}) \\in R。家族 defF⁡\(E\)\\operatorname\{def\}\_\{F\}\(E\) 定义为 defF\(E\):=\{a∣a∈A,ais defended byEinF\}\\operatorname\{def\}\_\{F\}\(E\)\\,\\mathrel\{\\mathop\{:\}\}=\\\{\\;a\\mid a\\in A,a\\text\{ is defended by $E$ in $F$\}\\;\\\}。在抽象论证中，目标是计算所谓的*扩展*，即具有某些性质的论证子集E⊆AE\\subseteq A。论证集合EE称为在FF中*无冲突的*，如果 (E×E)∩R=∅\(E\\times E\)\\cap R=\\emptyset；EE在FF中是*可接受的*，如果 (1) EE在FF中*无冲突*，且 (2) 每个 a∈Ea\\in E 在FF中被EE*辩护*。令 ER\+:=E∪\{a∣\(b,a\)∈R,b∈E\}E^\{\+\}\_\{R\}\\mathrel\{\\mathop\{:\}\}=E\\cup\\\{\\,a\\mid\(b,a\)\\in R,b\\in E\\,\\\} 且EE无冲突。那么，EE (1) 在FF中是*naive*的，如果不存在 E′⊃EE^\{\\prime\}\\supset E 在FF中无冲突；且 (2) 在FF中是*stage*的，如果不存在无冲突集 E′⊆AE^\{\\prime\}\\subseteq A 在FF中使得 ER\+⊊\(E′\)R\+E^\{\+\}\_\{R\}\\subsetneq\(E^\{\\prime\}\)^\{\+\}\_\{R\}。一个可接受集EE (1) 在FF中是*complete*的，如果 defF⁡\(E\)=E\\operatorname\{def\}\_\{F\}\(E\)=E；(2) 在FF中是*preferred*的，如果不存在 E′⊃EE^\{\\prime\}\\supset E 是FF中*可接受*的；(3) 在FF中是*semi\-stable*的，如果不存在可接受集 E′⊆AE^\{\\prime\}\\subseteq A 在FF中使得 ER\+⊊\(E′\)R\+E^\{\+\}\_\{R\}\\subsetneq\(E^\{\\prime\}\)^\{\+\}\_\{R\}；且 (4) 在FF中是*stable*的，如果每个 a∈A∖Ea\\in A\\setminus E 都被某个 a′∈Ea^\{\\prime\}\\in E*攻击*。对于语义 σ∈\{conf,naiv,adm,comp,stab,pref,semiSt,stag\}\\sigma\\in\\\{\\mathsf\{conf\},\\mathsf\{naiv\},\\mathsf\{adm\},\\mathsf\{comp\},\\mathsf\{stab\},\\mathsf\{pref\},\\mathsf\{semiSt\},\\mathsf\{stag\}\\\}，我们记 σ\(F\)\\sigma\(F\) 为FF中所有σ\\sigma语义下的*扩展*的集合。令 F=\(A,R\)F=\(A,R\) 为一个AF。那么，问题 Existσ\\textsc