Evaluation techniques for algebraic answer set counting over idempotent semirings

Abstract

Algebraic Answer Set Counting (AASC) eignet sich zum Lösen einer Vielzahl von Problemen wie z.B. probabilistisches Schließen, präferenzielles Schließen, und Optimisierungsprobleme. Dazu wird eine Erweiterung von Answer Set Programming (ASP) verwendet, in der über einem Semiring Gewichtungen für Answer Sets berechnet werden. Die Evaluierung von AASC erfordert einen hohen Rechenaufwand (Komplexitätsklasse #P/OptP/NP-schwer, je nach verwendetem Semiring). Daher besteht für AASC besonderes Interesse darin, effiziente Evaluierungsansätze zu finden. Ausgehend von einem Evaluierungsansatz, in dem AASC auf Algebraic Model Counting (AMC) reduziert wird, präsentieren wir mehrere Modifikationen dieses Ansatzes mit dem Ziel, die Effizienz zu verbessern. Wir fokussieren uns dabei insbesondere auf den Spezialfall von AASC über idempotenten Semiringen, für den wir beweisen, dass zusätzliche Cycle-Breaking-Algorithmen anwendbar sind, die im allgemeinen Fall von beliebigen Semiringen nicht verwendet werden können. Für den allgemeinen Fall beweisen wir weiters die Anwendbarkeit einer Preprocessing-Technik für AMC namens B+E, bei der Defined-Variables durch Variable-Forgetting eliminiert werden. Zusätzlich beschreiben wir ein abgeänderte Version für idempotente Semiringe, bei der neben Defined-Variables noch weitere Variablen eliminiert werden. Die theoretischen Resultate bezüglich des Preprocessings setzten wir in die Praxis um, indem wir den AASC-Solver aspmc um die beschriebenen Preprocessing-Techniken erweitern. Dafür adaptieren wir eine existierende Implementation von B+E. Unsere Experimente zur Evaluierung der Performance des Preprocessors zeigen, dass durch dieses Feature die benötigte Zeit für die nachfolgenden Evaluierungsschritte (Knowledge-Compilation und Counting) reduziert wird. Allerdings erhöht sich die Gesamtzeit für die Evaluierung, aufgrund der zusätzlichen Zeit, die für das Preprocessing selbst benötigt wird.

Algebraic Answer Set Counting (AASC) is a reasoning task that has recently gained interest. It is defined over an extension of Answer Set Programming (ASP) with weights over semirings, called ASP with algebraic measures. What makes AASC particularly interesting is that it can be used to model a variety of different problems, such as probabilistic reasoning, preferential reasoning, and optimization problems. At the same time, AASC is a computationally hard task (#P}/OptP/NP-hard, depending on the semiring). Therefore, one of the goals in current research is to find efficient evaluation techniques for this task. Starting with an evaluation approach that reduces AASC to Algebraic Model Counting (AMC), we propose modifications intended to improve efficiency. We focus in particular on the special case of AASC over idempotent semirings, for which we show the applicability of alternative cycle breaking algorithms that are not applicable in the general case. We establish further theoretical results regarding the preprocessing of AMC instances. Here, we first show, for the general case of arbitrary semirings, the applicability of the preprocessor B+E, which uses variable forgetting to eliminate defined variables. Then we modify the technique for idempotent semirings so that further variables, i.e. not just defined ones, are eliminated. We put our theoretical results regarding preprocessing to practical use by adding the proposed preprocessor to the AASC solver aspmc. For this we adapt an existing implementation of B+E. Our experiments for evaluating the performance of the preprocessor show that it reduces the time for the evaluation steps that follow, which are knowledge compilation and counting. However, the total time needed to solve instances may increase due to the additional time needed for the preprocessing itself.