Answer Set Networks: Casting Answer Set Programming into Deep Learning
Authors: Arseny Skryagin, Daniel Ochs, Philipp Deibert, Simon Kohaut, Devendra Singh Dhami, Kristian Kersting
Organizations: AI & Machine Learning Group, CS Dept., TU Darmstadt · Uncertainty in AI Group, Dept. of Mathematics and CS, TU Eindhoven · Hessian Center for AI (hessian.AI) · German Research Center for AI (DFKI)
Although Answer Set Programming (ASP) allows constraining neural-symbolic (NeSy) systems, its employment is hindered by the prohibitive costs of computing stable models and the CPU-bound nature of state-of-the-art solvers. To this end, we propose Answer Set Networks (ASN), a NeSy solver. Based on Graph Neural Networks (GNN), ASNs are a scalable approach to ASP-based Deep Probabilistic Logic Programming (DPPL). Specifically, we show how to translate ASPs into ASNs and demonstrate how ASNs can efficiently solve the encoded problem by leveraging GPU's batching and parallelization capabilities. Our experimental evaluations demonstrate that ASNs outperform state-of-the-art CPU-bound NeSy systems on multiple tasks. Simultaneously, we make the following two contributions based on the strengths of ASNs. Namely, we are the first to show the finetuning of Large Language Models (LLM) with DPPLs, employing ASNs to guide the training with logic. Further, we show the "constitutional navigation" of drones, i.e., encoding public aviation laws in an ASN for routing Unmanned Aerial Vehicles in uncertain environments.
Figures & tables
Figure 1 : ASN from Answer Set Program to NeSy-AI Applications: (left) ASN takes a grounded ASP program as input and translates it into an equivalent Reasoning Graph via neural compilation. The RG instances representing all possible choice selections are constructed in the definitization stage, to be iteratively solved in parallel using message passing. Finally, the resulting models are reduced to yield the ASP’s stable models. (right) Once stable models are in place, we can employ the Weighted Model Counting (WMC) to pursue the end-to-end learning for NeSy-AI applications in Natural Language Processing, Vision, and Navigation.
Figure 2 : Buildings bocks of Reasoning Graphs and the RGs for the selection of ASP’s syntax.
Figure 3 : The complete RG for the picking cake example
Figure 4 : Example of Neural-Probabilistic Predicate : ASN encodes NPPs with a choice rule. The choice atoms correspond to the outputs of a neural network, here a MNIST classifier with 3 digits.
Figure 6 : ASN for LLM Fine-Tuning and ProMis over Paris during the Olympics.
Accuracy after last Epoch
Average Time per Epoch
Method
T1
T2
T3
T1
T2
T3
DeepProbLog
98.50
98.75
98.23
8m:3s
15m:36s
34m:54s
SLASH
98.80
98.85
98.75
24s
1m:42s
51m:49s
SAME
98.56
98.82
98.71
17s
17s
1m:35s
ASN
98.83
98.73
98.47
5s
9s
35s
Table 1 : ASN scales well with growing task complexity: Test accuracy in % and runtime comparison for MNIST-Addition task. The runtime is averaged over ten epochs and five seeds for all methods. Light green indicates high accuracy or low time, while blue represents the opposite.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Experiment
Nodes
Edges
LLM Fine-Tuning
162
106
ProMis
122
56
MNIST-Add T1
495
354
MNIST-Add T2
3277
4076
MNIST-Add T3
30367
50102
Appendix
Table 2 : Nodes and Edges in the RG
BS
25
50
250
500
2.5k
5k
25k
50k
250k
Time
7m:21s
3m:41s
1m:2s
42s
27s
24s
22s
22s
21s
Appendix
Table 3 : Batching ProMis with ASN: Runtime comparison to compute a 500 2 grid with different batch sizes in ASN. Increasing the batch steadily reduces the computation time.
Total Time (#Epochs)
T1
T2
T3
Batch Size
time
e
time
e
time
e
64
1m:20s
(2)
6m:51s
(2)
1h:1m:13s
(2)
128
0m:45s
(2)
3m:36s
(2)
47m:5s
(3)
256
0m:26s
(2)
2m:46s
(3)
24m:10s
(3)
512
0m:24s
(3)
1m:59s
(4)
21m:10s
(5)
Appendix
Table 4 : Batch size trade-off for MNIST-addition: Models were trained for a maximum of fifty epochs to achieve a competitive accuracy of ≥98% . Results for 30k are not shown as they did not converge in 50 epochs, and the dataset size for T2 and T3 is 20k and 15k, respectively.
Figure 7 : Visualization ProMis Paris in full size
Figure 8 : Reasoning Graph for LLM Fine-Tuning with ASN: We query for all four possible relationship types among two persons and pick the one with the highest probability.
Figure 9 : Reasoning Graph for ProMis on Paris: Only one grid point is listed as query for the RG to become easily displayable.
Figure 10 : Reasoning Graph for MNIST-Addition: The number of classes was restricted to [0,1,2] for the RG to become easily displayable.
1Vienna University of Technology (TU Wien), Austria · 2National Institute of Informatics, Japan · 3The Graduate University for Advanced Studies, SOKENDAI, Japan