基于動(dòng)態(tài)規(guī)劃的優(yōu)先語義擴(kuò)充求解算法

摘 要： 抽象辯論框架中的優(yōu)先語義是判斷爭議可接受程度的最重要語義。現(xiàn)有優(yōu)先擴(kuò)充求解方法多用標(biāo)記映射求解，依賴于標(biāo)記的定義、轉(zhuǎn)換規(guī)則、相鄰爭議的標(biāo)記。算法每次迭代會(huì)產(chǎn)生一個(gè)新的抽象辯論框架導(dǎo)致時(shí)間、空間復(fù)雜度較高。提出一種基于動(dòng)態(tài)規(guī)劃的優(yōu)先擴(kuò)充算法，在動(dòng)態(tài)規(guī)劃中加入爭議可接受性判斷，求出辯論框架中極大可容許集得到優(yōu)先擴(kuò)充。在基于隨機(jī)抽象辯論框架與ICCMA提供的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，同Heureka、ArgSemSAT等算法進(jìn)行對(duì)比。結(jié)果表明，求解相同數(shù)量的優(yōu)先擴(kuò)充，算法耗時(shí)較少，時(shí)間、空間復(fù)雜度有所降低。

關(guān)鍵詞： 抽象辯論框架； 語義擴(kuò)充； 可容許集； 優(yōu)先擴(kuò)充

中圖分類號(hào)： TP312"" 文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 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）間為了消除信念不一致性的一種基于言語的交互行為。在辯論過程中，一條有明確主張和相應(yīng)根據(jù)的發(fā)言稱為爭議（argument）。辯論模型是對(duì)辯論過程的形式化描述，它包括辯論空間構(gòu)造和爭議評(píng)價(jià)算法［1，2］。近年來辯論模型在被廣泛應(yīng)用于人工智能中［3］，并在法律、醫(yī)療、電子政務(wù)和軍事等領(lǐng)域中得到廣泛應(yīng)用［4］，辯論模型與算法也成為人工智能的一個(gè)重要研究方向［5］。在用辯論對(duì)形式系統(tǒng)建模的研究中，文獻(xiàn)[6]提出了一種抽象辯論框架（abstract argumentation framework，AFS），其將爭議視為抽象實(shí)體，僅關(guān)注爭議之間的攻擊關(guān)系，并用有向圖來表示爭議及爭議之間的攻擊關(guān)系。文獻(xiàn)[6]提出優(yōu)先擴(kuò)充、基礎(chǔ)擴(kuò)充、穩(wěn)定擴(kuò)充和完全擴(kuò)充等四個(gè)基本語義擴(kuò)充。每一種語義擴(kuò)充都是基于某種可接受標(biāo)準(zhǔn)的可接受爭議集。可接受標(biāo)準(zhǔn)稱為擴(kuò)充語義，在指定可接受標(biāo)準(zhǔn)下的可授受爭議集稱為語義擴(kuò)充。

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

優(yōu)先語義是判斷爭議可接受性的最重要語義，根據(jù)優(yōu)先語義求解的優(yōu)先擴(kuò)充在很多領(lǐng)域中都得到應(yīng)用，如決策支持系統(tǒng)［10］、思辨支持系統(tǒng)［11］等，因?yàn)樵谝粋€(gè)抽象辯論框架中，優(yōu)先擴(kuò)充總是存在的，可能存在多個(gè)優(yōu)先擴(kuò)充，且一個(gè)優(yōu)先擴(kuò)充不會(huì)是另一個(gè)優(yōu)先擴(kuò)充的真子集。所以，優(yōu)先擴(kuò)充求解在語義擴(kuò)充求解占有十分重要的地位。 自文獻(xiàn)[6]提出抽象辯論框架以來，不少學(xué)者都對(duì)優(yōu)先擴(kuò)充求解算法進(jìn)行了研究，但仍沒有提出好的算法，因而對(duì)優(yōu)先擴(kuò)充的求解一直都是抽象辯論框架研究的主要內(nèi)容［12］。本文提出一種基于改進(jìn)動(dòng)態(tài)規(guī)劃的優(yōu)先擴(kuò)充方法（dynamic programming preferred extension algorithm，DpPR），將爭議可接受性作為狀態(tài)轉(zhuǎn)移方程求解出最大可容許集作為優(yōu)先擴(kuò)充。

1 相關(guān)工作

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

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

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

AFDivider［22］ 是將標(biāo)記運(yùn)用聚類算法求解，將辯論框架切割成若干簇的子辯論框架并轉(zhuǎn)為鄰接矩陣，計(jì)算兩個(gè)子辯論框架鄰接矩陣的相似度，通過一個(gè)爭議與一組爭議的相似程度以及每個(gè)爭議對(duì)其鄰域的全局相似性的貢獻(xiàn)程度進(jìn)行K-means聚類后得出結(jié)果。類似還有文獻(xiàn)［23］提出的分布式算法，但其僅分析了爭議數(shù)量巨大的抽象辯論框架而沒有將其中的相關(guān)爭議切分成簇進(jìn)行聚類。此外還有基于深度學(xué)習(xí)方法提出的辯論圖神經(jīng)網(wǎng)絡(luò)（AGNN）［24］ 來預(yù)測一個(gè)爭議被接受的可能性來求解優(yōu)先擴(kuò)充。此類方法僅適用于爭議數(shù)量巨大的、集群的辯論框架（如agent系統(tǒng)），在爭議數(shù)量較少的辯論框架中會(huì)導(dǎo)致聚類結(jié)果準(zhǔn)確率降低。

上述方法均在標(biāo)記映射的基礎(chǔ)上進(jìn)行優(yōu)化或約簡，故求解的結(jié)果會(huì)受到抽象辯論框架的爭議攻擊密集度等影響。針對(duì)上述問題，本文提出一種利用辯論語義的關(guān)系推導(dǎo)進(jìn)而采用動(dòng)態(tài)規(guī)劃求解優(yōu)先擴(kuò)充的算法，算法不會(huì)受爭議間相互關(guān)系或攻擊密集程度的影響，適用性較好，與現(xiàn)有方法相比有更好全局搜索能力和局部搜索能力。

5 結(jié)束語

本文在抽象辯論框架下針對(duì)語義擴(kuò)充定義的可接受標(biāo)準(zhǔn)，求解可接受的爭議集合，深入研究了優(yōu)先擴(kuò)充語義并提出了一種基于動(dòng)態(tài)規(guī)劃的優(yōu)先擴(kuò)充求解算法。對(duì)無沖突爭議求解的策略進(jìn)行改變，使得爭議僅判斷與相鄰的無沖突爭議的無沖突爭議集是否沖突，優(yōu)化了算法時(shí)間復(fù)雜度，同時(shí)保證了算法求得結(jié)果的完整性。與相關(guān)算法進(jìn)行比較時(shí)本文算法得到的最好結(jié)果個(gè)數(shù)最多，表明本文算法所得解的質(zhì)量較高。同時(shí)，下一步可以針對(duì)爭議攻擊機(jī)制提出相關(guān)修剪機(jī)制，可以解決算法運(yùn)行過程中對(duì)爭議與被攻擊爭議的重復(fù)判斷問題，使得算法時(shí)間空間、復(fù)雜度得到進(jìn)一步改善，運(yùn)行效率得到提高。

參考文獻(xiàn)：

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

［2］熊才權(quán)，歐陽勇，梅清.基于可信度的辯論模型及爭議評(píng)價(jià)算法［J］.軟件學(xué)報(bào)，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.