基于動態規劃的優先語義擴充求解算法

摘 要： 抽象辯論框架中的優先語義是判斷爭議可接受程度的最重要語義。現有優先擴充求解方法多用標記映射求解，依賴于標記的定義、轉換規則、相鄰爭議的標記。算法每次迭代會產生一個新的抽象辯論框架導致時間、空間復雜度較高。提出一種基于動態規劃的優先擴充算法，在動態規劃中加入爭議可接受性判斷，求出辯論框架中極大可容許集得到優先擴充。在基于隨機抽象辯論框架與ICCMA提供的數據集進行實驗，同Heureka、ArgSemSAT等算法進行對比。結果表明，求解相同數量的優先擴充，算法耗時較少，時間、空間復雜度有所降低。

關鍵詞： 抽象辯論框架； 語義擴充； 可容許集； 優先擴充

中圖分類號： TP312"" 文獻標志碼： A

文章編號： 1001-3695（2022）05-010-1343-06

doi：10.19734/j.issn.1001-3695.2021.10.0459

Preferred semantics extension algorithm based on dynamic programming

Xiong Caiquan， Zong Zehua， Wu Xinyun

（School of Computer Science， Hubei University of Technology， Wuhan 430068， China）

Abstract： The preferred semantics in the abstract argumentation framework is the most important semantics for judging the acceptability of arguments.The existing preferred expansion solving methods mostly use marker mapping to solve，which depends on the definition of markers，conversion rules，and the markers of adjacent arguments.Each iteration of the algorithm will gene-rate a new abstract argumentation framework，resulting in high time and space complexity.This paper proposed preferred expansion algorithm based on dynamic programming，and added the judgment of the acceptability of arguments to the dynamic pro-gramming，and

obtained the maximum admissible set in the argumentation framework by preferred expansion.

This paper conducted experiments based on the random abstract argumentation framework and the data set provided by ICCMA，and compared the proposed algorithm with algorithms such as Heureka and ArgSemSAT.The results show that，to solve the same number of preferred expansions，the algorithm consumes less time and reduces the time and space complexity.

Key words： abstract argumentation framework； semantics extension； admissible set； preferred extension

0 引言

辯論（argumentation）是智能主體（agent）間為了消除信念不一致性的一種基于言語的交互行為。在辯論過程中，一條有明確主張和相應根據的發言稱為爭議（argument）。辯論模型是對辯論過程的形式化描述，它包括辯論空間構造和爭議評價算法［1，2］。近年來辯論模型在被廣泛應用于人工智能中［3］，并在法律、醫療、電子政務和軍事等領域中得到廣泛應用［4］，辯論模型與算法也成為人工智能的一個重要研究方向［5］。在用辯論對形式系統建模的研究中，文獻[6]提出了一種抽象辯論框架（abstract argumentation framework，AFS），其將爭議視為抽象實體，僅關注爭議之間的攻擊關系，并用有向圖來表示爭議及爭議之間的攻擊關系。文獻[6]提出優先擴充、基礎擴充、穩定擴充和完全擴充等四個基本語義擴充。每一種語義擴充都是基于某種可接受標準的可接受爭議集。可接受標準稱為擴充語義，在指定可接受標準下的可授受爭議集稱為語義擴充。

抽象辯論框架的語義擴充求解是辯論模型研究中的一個熱門問題［7］。2015年開始舉行第一屆辯論模型求解算法的比賽（ICCMA），在這屆比賽中提出了18種算法［8］。辯論模型求解有決策問題和枚舉問題兩種，前者判斷一個集合是不是某種語義擴充，或判斷某種爭議在不在某個語義擴充中；后者是求出某種語義的所有擴充。如果一個爭議在一個語義擴充中，則稱該爭議基于該語義是輕信可接受的，如果一個爭議存在于所有的擴充中，則稱該爭議基于語義是謹慎可接受的［9］。

優先語義是判斷爭議可接受性的最重要語義，根據優先語義求解的優先擴充在很多領域中都得到應用，如決策支持系統［10］、思辨支持系統［11］等，因為在一個抽象辯論框架中，優先擴充總是存在的，可能存在多個優先擴充，且一個優先擴充不會是另一個優先擴充的真子集。所以，優先擴充求解在語義擴充求解占有十分重要的地位。 自文獻[6]提出抽象辯論框架以來，不少學者都對優先擴充求解算法進行了研究，但仍沒有提出好的算法，因而對優先擴充的求解一直都是抽象辯論框架研究的主要內容［12］。本文提出一種基于改進動態規劃的優先擴充方法（dynamic programming preferred extension algorithm，DpPR），將爭議可接受性作為狀態轉移方程求解出最大可容許集作為優先擴充。

1 相關工作

枚舉出一個抽象辯論框架中的所有優先擴充是一個NP-complete問題，枚舉優先擴充的算法時間復雜度都在指數級別［7］。求解優先擴充的算法大體上可以分為基于約簡的方法和直接方法求解兩大類［12］。

基于約簡的方法實現是利用現有的高效求解器（其他目的開發的），將抽象辯論框架與優先擴充語義歸結為求解器所需的目標形式，再將輸出進行解釋后得到最終結果，可分為ArgSemSAT［13］、Cegartix［14］和ASPARTIX-D［15］三種算法，其均依賴對SAT求解器的迭代調用即將求解任務變為多次查詢SAT求解器算法的迭代結果。算法策略是選擇更簡單的語義搜索空間如迭代搜索可容許爭議集，當搜索結果擴展至最大的集合時形成優先擴充、可以將完全擴充作為候選集合，從完全擴充中約簡得到優先擴充。此類算法要對SAT解算器進行指數次調用，是一個∏p2-complete問題。LabSATSolver［16］和QADF［17］使用基于標記的SAT求解器，根據量化運算公式（QBF），將優先擴充語義轉換為命題邏輯公式，通過邏輯公式進行編碼尋找優先擴充，公式將優先擴充語義表示為prfAr，att：=admAr，att∧AR′v（（Arlt;Ar′）∧admAr′，att′），即優先擴充語義公式當且僅當它滿足最大可容許集的公式（子集最大化）。

直接方法求解優先擴充的優點在于直接方法可以直接對抽象辯論框架上的爭議進行相應求解，不需要轉換為求解器需要的目標形式。故直接求解一定程度上效率要比約簡方法求解高。直接方法求解大都為基于標記的算法，優點是一個爭議的標記僅對相鄰爭議有直接的影響。標記首先由Caminada等人［18］ 提出的三值標記Λ→{in，out，undec}，分別代表被接受、被拒絕和未決定的爭議。算法將帶有undec標記的爭議變為in，更改相鄰標記直到辯論框架中不存在標記為undec的爭議，此時輸出所有帶有標記in的爭議即為一個優先擴充，算法繼續回溯直至輸出所有的優先擴充。此類算法通常以二叉樹的方式進行搜索，樹的每一個節點都是一個辯論框架，空間復雜度為O（n×（2n-1））。文獻［19］在此基礎上增加了兩個標記{must_out，blank}并修改了轉換規則，一定程度上對二叉樹進行剪枝處理改善了空間復雜度高的問題。文獻［20］在此前基礎上繼續添加了兩個標記{must_in，must_undec}，優點是避免不必要的掃描所有爭議，每次改動時僅修改相鄰的若干個爭議同時引入新的爭議選擇策略，依賴于每次迭代后的爭議標記。每輪迭代優先選取攻擊標記為must_out且爭議本身為blank的爭議。該策略優點是運行過程中避免了對某個爭議標記的確定而全局搜索整個辯論框架。類似還有Heureka求解器［21］，采用啟發式選擇策略以及回溯算法，取決于當前辯論框架的標記以及辯論圖的結構屬性（二部圖、非自反—對稱圖、對稱圖、無偶數圈圖）。

AFDivider［22］ 是將標記運用聚類算法求解，將辯論框架切割成若干簇的子辯論框架并轉為鄰接矩陣，計算兩個子辯論框架鄰接矩陣的相似度，通過一個爭議與一組爭議的相似程度以及每個爭議對其鄰域的全局相似性的貢獻程度進行K-means聚類后得出結果。類似還有文獻［23］提出的分布式算法，但其僅分析了爭議數量巨大的抽象辯論框架而沒有將其中的相關爭議切分成簇進行聚類。此外還有基于深度學習方法提出的辯論圖神經網絡（AGNN）［24］ 來預測一個爭議被接受的可能性來求解優先擴充。此類方法僅適用于爭議數量巨大的、集群的辯論框架（如agent系統），在爭議數量較少的辯論框架中會導致聚類結果準確率降低。

上述方法均在標記映射的基礎上進行優化或約簡，故求解的結果會受到抽象辯論框架的爭議攻擊密集度等影響。針對上述問題，本文提出一種利用辯論語義的關系推導進而采用動態規劃求解優先擴充的算法，算法不會受爭議間相互關系或攻擊密集程度的影響，適用性較好，與現有方法相比有更好全局搜索能力和局部搜索能力。

5 結束語

本文在抽象辯論框架下針對語義擴充定義的可接受標準，求解可接受的爭議集合，深入研究了優先擴充語義并提出了一種基于動態規劃的優先擴充求解算法。對無沖突爭議求解的策略進行改變，使得爭議僅判斷與相鄰的無沖突爭議的無沖突爭議集是否沖突，優化了算法時間復雜度，同時保證了算法求得結果的完整性。與相關算法進行比較時本文算法得到的最好結果個數最多，表明本文算法所得解的質量較高。同時，下一步可以針對爭議攻擊機制提出相關修剪機制，可以解決算法運行過程中對爭議與被攻擊爭議的重復判斷問題，使得算法時間空間、復雜度得到進一步改善，運行效率得到提高。

參考文獻：

［1］熊才權，李德華.一種研討模型［J］.軟件學報，2009，20（8）：2181-2190. （Xiong Caiquan，Li Dehua.Model of argumentation［J］.Journal of Software，2009，20（8）：2181-2190.）

［2］熊才權，歐陽勇，梅清.基于可信度的辯論模型及爭議評價算法［J］.軟件學報，2014，25（6）：1225-1238. （Xiong Caiquan，Ouyang Yong，Mei Qing.Argumentation model based on certainty-factor and algorithms of argument evaluation［J］.Journal of Software，2014，25（6）：1225-1238.）

［3］Cerutti F，Giacomin M，Vallati M.How we designed winning algorithms for abstract argumentation and which insight we attained［J］.Artificial Intelligence，2019，276：1-40.

［4］Vallati M，Cerutti F，Giacomin M.Predictive models and abstract argumentation：the case of high-complexity semantics［J］.The Knowledge Engineering Review，2019，34：1-23.

［5］Baumeister D，Jarvisalo M，Neugebauer D，et al.Acceptance in incomplete argumentation frameworks［J］.Artificial Intelligence，2021，295：103470.

［6］Dung P M.On the acceptability of arguments and its fundamental role in nonmonotonic reasoning，logic programming and n-person games［J］.Artificial Intelligence，1995，77（2）：321-357.

［7］Kroll M，Pichler R，Woltran S.On the complexity of enumerating the extensions of abstract argumentation frameworks［C］//Proc of the 20th International Joint Conference on Artificial Intelligence.Melbourne，Australia：International Joint Conferences on Artificial Intelligence Organization.2017：1145-1152.

［8］Thimm M，Villata S.The first international competition on computational models of argumentation：results and analysis［J］.Artificial Intelligence，2017，252：267-294.

［9］Dung P M.Fundamental properties of attack relations in structured argumentation with priorities［J］.Artificial Intelligence，2018，255：1-42.

［10］Xiong Caiquan，Li Xuan，Li Yuan.Multi-documents summarization based on the TextRank and its application in argumentation system［J］.International Journal of Data Warehousing and Mining，2018，14（3）：69-89.

［11］Black E，Modgil S，Oren N.Theory and applications of formal argumentation［M］//Nugent R.Lecture Notes in Computer Science.Cham：Springer International Publishing.2018.

［12］Cerutti F，Gaggl S A，Thimm M，et al.Foundations of implementations for formal argumentation［J］.IfCoLog Journal of Logics and Their Applications，2017，4（8）：2623-2705.

［13］Giacomin M，Cerutti F，Vallati M.ArgSemSAT：solving argumentation problems using SAT［M］//Computational Models of Argument：Proceedings of COMMA2014.[S.l.]：IOS Press，2014：455-456.

［14］Dvorak W，Jarvisalo M，Wallner J P，et al.Complexity-sensitive decision procedures for abstract argumentation［J］.Artificial Intelligence，2014，206：53-78.

［15］Gaggl S A，Manthey N.ASPARTIX-D：ASP argumentation reasoning tool-dresden［EB/OL］.（2015）.https：//iccl.inf.tu-dresden.de/w/images/ b/b1/System_description_aspartix-d-2015.pdf.

［16］Beierle C，Brons F，Potyka N.A software system using a sat solver for reasoning under complete，stable，preferred，and grounded argumentation semantics［C］//Proc of Joint German/Austrian Conference on Artificial Intelligence（Künstliche Intelligenz）.Berlin：Springer，2015：241-248.

［17］Diller M，Wallner J P，Woltran S.Reasoning in abstract dialectical frameworks using quantified Boolean formulas［J］.Argument amp; Computation，2015，6（2）：149-177.

［18］Caminada M W A，Gabbay D M.A logical account of formal argumentation［J］.Studia Logica，2009，93（2-3）：109-145.

［19］Nofal S.Algorithms for decision problems in argument systems under preferred semantics［J］.Artificial Intelligence，2014，207：23-51.

［20］Nofal S，Atkinson K，Dunne P，et al.A new labelling algorithm for generating preferred extensions of abstract argumentation frameworks［C］//Proc of the 21st International Conference on Enterprise Information Systems.2019：340-348.

［21］Geilen N，Thimm M.Heureka：a general heuristic backtracking solver for abstract argumentation［C］//Proc of International Workshop on Theorie and Applications of Formal Argumentation.Berlin：Springer，2017：143-149.

［22］Doutre S，Lafages M，Lagasquie-Schiex M C.A distributed and clustering-based algorithm for the enumeration problem in abstract argumentation［C］//Proc of International Conference on Principles and Practice of Multi-Agent Systems.Berlin：Springer，2019：87-105.

［23］Xu Yuming，Cayrol C.Initial sets in abstract argumentation frameworks［J］.Journal of Applied Non-Classical Logics，2018，28（2-3）：260-279.

［24］Craandijk D，Bex F.Deep learning for abstract argumentation semantics［C］//Proc of the 29th International Joint Conference on Artificial Intelligence.2020：1667-1673.

［25］Lagniez J M，Lonca E，Mailly J G.Coquiaas：a constraint-based quick abstract argumentation solver［C］//Proc of the 27th International Conference on Tools with Artificial Intelligence.Piscataway，NJ：IEEE Press，2015：928-935.

［26］Dvorak W，Rapberger A，Wallner J P，et al.Aspartix-v19-an answer-set programming based system for abstract argumentation［C］//Proc of International Symposium on Foundations of Information and Knowledge Systems.Berlin：Springer，2020：79-89.

［27］Nielsen S H，Parsons S.Computing preferred extensions for argumentation systems with sets of attacking arguments［C］//Proc of Conference on Computational Models of Argument：Proceedings of COMMA2006.2006：97-108.