Abschlussarbeit

Beschreibung:

Eine große Herausforderung im Gebiet der künstlichen Intelligenz liegt im Umgang mit widersprüchlichen Informationen. Wenn beispielsweise Daten aus verschiedenen Quellen zusammengetragen werden, sind Konflikte (Inkonsistenzen) kaum vermeidbar. Wie stark eine Wissensbasis von Widersprüchen betroffen ist, lässt sich mit Hilfe von Inkonsistenzmaßen quantitativ bewerten.

Bislang lag der Fokus im Bereich der Inkonsistenzmessung [2,3] eher darauf, diverse Maße auf Basis verschiedener Herangehensweisen zu entwerfen. Die Praktikabilität der entwickelten Maße fand dabei weniger Beachtung. Die Entwicklung von Algorithmen, die eine praktische, anwendungsbezogene Verwendung von Inkonsistenzmaßen ermöglichen, ist daher ein ergiebiges Themengebiet. Es wurden bereits Arbeiten veröffentlicht, in denen Algorithmen zur Berechnung von insgesamt drei Inkonsistenzmaßen auf Basis von Antwortmengenprogrammierung und Satisfiability Solving vorgestellt wurden [4,5,6].

Weitere Problemlösungsansätze, die zur Berechnung von Inkonsistenzwerten herangezogen werden könnten, sind einerseits die Repräsentation als quantifizierte boolesche Formel (engl. quantified Boolean formula (QBF)) [1] und andererseits die Modellierung als ganzzahliges lineares Optimierungsproblem [7]. Für beide Ansätze existieren Solver, die für die eigentliche Lösungsberechnung herangezogen werden können.

Das Ziel der Masterarbeit liegt darin, mit den beiden genannten Ansätzen Algorithmen für mindestens ein Inkonsistenzmaß zu entwickeln und in einer Evaluation die Laufzeiten miteinander zu vergleichen.
Weiterhin sollen die Algorithmen mit bereits existierenden Ansätzen (etwa auf Basis von Antwortmengenprogrammierung und/oder SAT-Solving) verglichen werden.

[1] Enrico Giunchiglia, Paolo Marin, and Massimo Narizzano. Reasoning with Quantified Boolean Formulas. Handbook of Satisfiability (pp. 761-780). IOS Press, 2009.
[2] John Grant and Maria Vanina Martinez, editors. Measuring Inconsistency in Information. Volume 73 of Studies in Logic. College Publications, 2018.
[3] John Grant. Classifications for inconsistent theories. Notre Dame Journal of Formal Logic, 19(3):435–444, 1978.
[4] Isabelle Kuhlmann and Matthias Thimm. An Algorithm for the Contension Inconsistency Measure using Reductions to Answer Set Programming. International Conference on Scalable Uncertainty Management. Springer, Cham, 2020.
[5] Isabelle Kuhlmann and Matthias Thimm. Algorithms for Inconsistency Measurement using Answer Set Programming. 19th International Workshop on Non-Monotonic Reasoning. 2021.
[6] Isabelle Kuhlmann, Anna Gessler, Vivien Laszlo and Matthias Thimm. A Comparison of ASP-Based and SAT-Based Algorithms for the Contension Inconsistency Measure. International Conference on Scalable Uncertainty Management (pp. 139-153). Springer, Cham, 2022.
[7] Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1998.