The computational cost and benefit of collective attacks in abstract argumentation

Abstract

Resolving conflicts and reasoning in an argumentative setting is a discipline that is essential for reliable and explainable artificial intelligence (AI). In the last decades, argumentation frameworks (AFs) by Dung have stood out in the research community as a well-investigated simple formalism for these tasks. The elegant structure of arguments as nodes and attacks as edges of a directed graph not only served well for modeling argumentation scenarios, but proved quite versatile with many connections to other non-monotonic reasoning formalisms. However, the seemingly basic notion of collective attacks, i.e., the scenario where a set of arguments rather than a single one is needed to defeat another, cannot natively be modeled in AFs without additional arguments. Hence, Nielsen and Parsons introduced a conservative generalization of AFs in 2006 incorporating this basic feature—the resulting frameworks are referred to as SETAFs.While it was shown that SETAFs are strictly more expressive than AFs, comparatively little research was performed on them. Oftentimes increased expressive power goes hand in hand with undesirable side effects—like high computational cost, the loss of essential properties, or the impossibility of applying popular algorithmic ideas to reason even more efficiently on non-random data. We will see in this thesis that these worries are mostly groundless in the context of SETAFs: remarkably, even facing all apparent advantages of SETAFs over AFs, most desirable properties generalize to SETAFs—as captured by a principle-based analysis. In this prominent approach, the semantics of the frameworks are investigated and categorized by the satisfaction or violation of principles—i.e., properties that succinctly capture key features and behaviors in common argumentative scenarios.Moreover, we show that when carefully generalized, advanced algorithmic ideas that are promising on AFs in general also work for SETAFs. In particular, we investigate the backdoor- and treewidth-approaches. In a nutshell, a backdoor is a part of a SETAF, such that its removal renders the remaining framework structurally simple. We apply this idea to the hypergraph structure of SETAFs by means of efficient propagation algorithms. The parameter treewidth describes how tree-like a graph is. Since many problems become efficiently solvable in tree-shaped SETAFs, we exploit a tree-like structure via dynamic programming algorithms. Interesting phenomena that can be exploited in several ways are hidden or trivialized by the simple structure of AFs—we utilize these phenomena for computational improvements. By means of our thorough analysis of the structure of SETAFs we not only deepen our understanding of collective attacks and their effects, but also shine a new light on AFs. This is because AFs can be seen as a special case of SETAFs, where for each attack the attacking set is of size 1. Our close look pays off measurably: our algorithms for backdoor- and treewidth-techniques not only establish for the first time that SETAFs can be efficiently treated in the aforementioned scenarios, but also show improvements in the AF case.

Sinnvolle Schlussfolgerungen aus möglicherweise widersprüchlichen Informationen zu ziehen ist von zentraler Bedeutung für verlässliche und nachvollziehbare Anwendungen von Künstliche-Intelligenz (KI). Formalismen für derartige Schlussfolgerungen werden in der formalen Argumentationstheorie erforscht; ein solcher Formalismus sind Argumentation Frameworks (AFs). AFs zeichnen sich—belegt durch laufend neue Forschungsergebnisse in den letzten Jahren—durch ihre Vielseitigkeit, einschließlich zahlreicher aufgezeigter Verbindungen zu anderen nicht-monotonen Formalismen, aus. Sie gelten daher ob ihrer einfachen Struktur als naheliegende Wahl, um Probleme in einem argumentativen Setting darzustellen und zu lösen. Die Eleganz dieses Formalismus liegt in der einfachen Struktur der AFs: Argumente werden als abstrakte Knoten eines Graphen modelliert, gerichtete Kanten stellen Attacken zwischen Argumenten dar. Eine weiterführende Idee ist, dass anstatt eines einzelnen Arguments eine Menge von Argumenten den Ursprung einer Attacke bilden—und keine kleinere Teilmenge davon stark genug ist, das Ziel-Argument anzugreifen. Diese Art der Attacke ist in AFs nicht ohne zusätzliche Argumente ohne klare Bedeutung möglich. In SETAFs können derartige “kollektive Attacken” zusätzlich zu den von AFs bekannten Attacken vorkommen; damit verallgemeinern SETAFs die einfachen AFs auf natürliche Weise. SETAFs wurden erstmals 2006 von Nielsen und Parsons formalisiert.Obwohl gezeigt werden konnte, dass SETAFs eine größere Ausdrucksstärke bieten als AFs, wurde die naheliegende Idee von kollektiven Attacken bisher verhältnismäßig wenig erforscht. Oft muss man bei großer Ausdrucksstärke negative Auswirkungen in anderen Aspekten in Kauf nehmen: etwa eine erhöhte Rechenkomplexität (und daher schlussendlich auch längere Laufzeit) von Algorithmen, den Verlust wichtiger Eigenschaften, oder, dass komplexere algorithmische Ansätze nicht anwendbar sind. In dieser Arbeit werden wir allerdings sehen, dass derartige Befürchtungen im Falle der SETAFs nicht zutreffend sind: bemerkenswerterweise gelten die wichtigsten Eigenschaften von AFs auch für SETAFs, wie wir durch eine sogenannte “principle-based analysis” zeigen. Dieses Werkzeug bedient sich vordefinierter Eigenschaften (der “principles”) um anhand ihrer Erfüllung oder Nichterfüllung zu zeigen, welche Merkmale die Argumentationssemantiken aufweisen.Darüber hinaus zeigen wir, dass auch komplexere algorithmische Ansätze, welche für AFs bereits vielversprechende Ergebnisse zeigen, ebenfalls auf SETAFs anwendbar sind— unter der Voraussetzung dass diese auf clevere Weise an das neue Setting angepasst werden. Wir untersuchen den backdoor-Ansatz und den treewidth-Ansatz. Eine backdoor (“Hintertür”) kann man sich als den Teil eines Problems vorstellen, welcher für den größten Berechnungsaufwand verantwortlich ist; wird dieser Teil entfernt, so ist die Struktur des übrigen Teils simpel. Das nutzen wir um Teillösungen des komplizierten Teils auf den simplen Teil auszuweiten, um dadurch schnellere Laufzeiten zu erzielen. Der Parameter treewidth (“Baumweite”) bestimmt wie ähnlich der Argumentationsgraph zu einem Baum ist. Da die von uns untersuchten Probleme auf baumförmigen SETAFs leicht lösbar sind, verspricht dieser Parameter ebenfalls verbesserte Laufzeiten. In der Tat zeigen wir durch auf dynamischer Programmierung basierenden Algorithmen, dass diese Ideen ebenfalls auf SETAFs anwendbar sind, und beweisen auch hier verbesserte Laufzeitschranken. In AFs sind durch ihre einfache Struktur viele interessante Phänomene nicht sichtbar, welche bei SETAFs einen deutlicheren Effekt zeigen. Wir können eben diese Phänomene oft ausnutzen, um bessere Ergebnisse zu erzielen—und diese sind sogar ebenfalls auf AFs anwendbar. Das kommt daher, dass ein AF als Spezialfall eines SETAF gesehen werden kann, wo jede Attacke von einer genau ein-elementigen Menge ausgeht. Wir beweisen also nicht nur, dass SETAFs mit den genannten strukturellen Eigenschaften effizienter verarbeitet werden können, sondern zeigen auch Verbesserungen für AFs auf.