Extending Defeasible Reasoning Beyond Rational Closure

Overview

Artificial Intelligence (AI) faces a key challenge in effectively representing and reasoning about knowledge, especially when dealing with exceptions and uncertainties. Traditional reasoning methods based on classical logic often fall short, as they do not accommodate the complexities of real-world scenarios. Defeasible reasoning, particularly through the KLM framework, offers a solution by allowing conclusions to be retracted in light of new information, thereby providing a more flexible approach to AI decision-making.

Our project addresses the limited availability of defeasible knowledge base generators and practical implementations of rational closure, the most prominent defeasible reasoning framework. We aim to contribute to this research by developing reasoners that implement both rational closure and its extension, lexicographic closure, with step-by-step explanations to provide transparency in the reasoning process. Additionally, we focus on optimizing knowledge base generation and improving the practical implementations of rational closure to make them more scalable and efficient.

Background

Propositional Logic

Propositional logic is introduced as the formal system to reason about atomic propositions. Boolean operators like AND, OR, and NOT are used to combine propositions, with rules of precedence for evaluating logical expressions. The semantics of propositional logic are discussed through interpretations (truth assignments) and the concept of satisfaction and models of formulas. Entailment is the notion that using the relationship between two or more statements one can make deductions or conclusions . This is a fundamental concept in reasoning, it formally shows how certain states of the world are logical consequence of others.

Defeasible Reasoning

Defeasible reasoning is a type of reasoning where conclusions are drawn from incomplete or uncertain information and can be revised when new information arises. Unlike classical reasoning, where conclusions are fixed once drawn, defeasible reasoning allows conclusions to remain tentative and be overridden by exceptions or additional data. This makes it particularly useful for modeling real-world situations where certainty is often limited.

KLM Framework

The KLM framework formalizes defeasible reasoning using conditional assertions, allowing for typical implications rather than strict logical conclusions. For example, the assertion "birds typically fly" can accommodate exceptions like "penguins typically don’t fly." The framework outlines several rationality properties, such as reflexivity, left logical equivalence, and rational monotonicity, to ensure that entailments are rational. Preferential and ranked interpretations are used to model defeasible entailments, where more typical scenarios are ranked lower and are preferred.

Rational Closure

Rational closure is a method for making inferences from defeasible knowledge while ensuring logical consistency. It ranks knowledge based on typicality and ensures that conclusions drawn respect rationality. It is the most conservative form of defeasible entailment, ensuring that anything entailed by rational closure will also be entailed by other forms of defeasible reasoning. The Base Rank Algorithm separates knowledge into ranks, where the more exceptional statements are ranked higher. The Rational Closure Algorithm then checks for defeasible implications by evaluating the ranks.

Lexicographic Closure

Lexicographic closure builds on rational closure by refining it to consider both the cardinality and specificity of statements. It ensures that more specific rules are given priority, and less serious violations are preferred over more serious ones. This form of closure weakens specific formulas rather than discarding entire levels when inconsistencies are found, allowing for more nuanced reasoning.

Knowledge Base Generation

The main objectives of this knowledge base component of the project were to create a pseudo-random, multi-threaded defeasible knowledge base generator for testing the rational closure algorithm and its extensions. The project also focused on optimizing the generator through parallel programming improvements, reusing existing knowledge bases to leverage the space-time trade-off, and enhancing the overall architecture. Additionally, it aimed to increase the expressiveness of generated knowledge bases and analyze key parameters affecting the generation process. Overall, the goal was to bridge the gap in platforms available for testing and developing reasoners. The generator’s performance was shaped by a set of control parameters, detailed in the following section.

Control parameters:

Generator type
Number of Ranks
Knowledge base distribution
Minimum number of statements required in each rank
Number of statements
Ratio of classical to defeasible statements
Reusing consequents or not
Having transitive relations in ranks or not
Antecedent and Consequent Complexity
Boolean Connectives
Character set

The defeasible knowledge base above is an example with 2 ranks, 3 statements, and employs negation and material implication as Boolean connectives. It features a 0:1 ratio of classical to defeasible statements. Overall, it presents the information: 'birds fly','penguins are birds' and 'penguins do not fly'.

Optional operations:

Print the generated defeasible knowledge base to the terminal
Writing the generated knowledge base in a text file. In this format the knowledge base can be used on reasoners.
Saving the knowledge base in a database. This allows the use of the optimized generator.
Testing the generated knowledge base using a basebaserank algorithm

Results

The optimized knowledge base generator (KBG_Optimized) significantly reduced generation time compared to the original KBG under identical control parameters. Tests across 10 different defeasible knowledge bases, each with varying ranks and statements, confirmed that the generators consistently produced knowledge bases with the correct number of statements and ranks, as verified by the baserank algorithm. Additionally, the expressiveness of the pseudo-random defeasible knowledge base generator was enhanced by incorporating antecedent and consequent complexity, leading to more diverse and intricate knowledge bases. The space-time trade-off analysis revealed that while using existing knowledge bases reduced generation time, it increased storage requirements. Parameter analysis indicated weak correlations between most parameters and generation time, with complexity and the reuse of consequents having the strongest impact. Monte Carlo simulations demonstrated stronger correlations with specific distributions, such as linear decline and exponential growth, which significantly affected generation time, while flat and random distributions exhibited weaker effects.

Source Code

Future Work

In future work, I recommend developing non-deterministic knowledge bases based on specific contexts or languages, such as English. This would involve understanding language concepts and translating them into propositional statements and connectives. A defeasible knowledge base generator of this kind could create more realistic world representations, improving reasoners suited to specific environments. Additionally, implementing a propositional formula formatting feature in the generator would allow for more precise testing of reasoners, by specifying the desired formula format rather than just selecting connectives and complexity levels.

Optimization

Traditional reasoning methods based on classical logic often fall short, as they do not accommodate the complexities of real-world scenarios. Defeasible reasoning, particularly through the KLM framework, offers a solution by allowing conclusions to be retracted in light of new information, thereby providing a more flexible approach to AI decision-making.

Despite the theoretical advancements in rational closure, there have been few practical implementations, leaving a significant gap in research. Moreover, rational closure is inherently not well-suited for large knowledge bases due to its linear nature, which makes the process inefficient and unscalable. Given the increasing complexity of real-world AI applications, optimizing rational closure to handle large knowledge bases efficiently is crucial. This paper addresses these issues by exploring optimization techniques, such as caching and advanced search algorithms, to enhance the scalability of rational closure, making it applicable to larger, more complex systems.

Aims

The primary goal of this research is to optimize the Rational Closure algorithm for defeasible reasoning. We aim to evaluate the effects of caching and search algorithms (binary and ternary searches) on the algorithm’s performance. By improving the scalability and efficiency of Rational Closure, we hope to extend its practical applicability, particularly in systems that handle large knowledge bases and complex queries.

Implementation

We developed six different defeasible reasoners, including naive, binary, and ternary entailment checkers. These reasoners were built on the foundational work of previous researchers and employed the Sat4j solver for satisfiability checks. The binary and ternary reasoners utilize search algorithms to optimize the ranking process, while caching mechanisms were introduced to minimize redundant calculations. The research also introduced two caching strategies: antecedent-based caching, which stores and reuses ranks associated with queries, and full-query caching, which stores entire query results for repeated use.

Results

The experimental results showed that both binary and ternary search methods consistently outperformed the naive implementation in terms of execution time, regardless of the size of the knowledge base. Below is a graph illustrating the comparison of execution times.

Source Code

Future Work Recommendations

Future research could explore the conditions under which ternary search outperforms binary, particularly in complex knowledge bases with irregular rank distributions. Additionally, further investigation into optimizing cache management for larger and more dynamic query sets would be beneficial. Exploring advanced query patterns and scaling to even larger knowledge bases will be essential to improving the practical applicability of Rational Closure in real-world AI systems.

Web-Based Defeasible Reasoner

Live Demo Source Code

This project developed a web-based tool designed to showcase defeasible reasoning processes, specifically focusing on Rational Closure and Lexicographic Closure. The application allows users to input knowledge bases and queries, displaying the reasoning steps. The software, built with Java (back-end) and TypeScript/ReactJS (front-end), implements algorithms for defeasible entailment.

The back-end system employs the Javalin framework to create RESTful APIs, enabling interaction between the front-end and core reasoning algorithms, which leverage the TweetyProject library. The tool computes Base Rank, Rational Closure, and Lexicographic Closure algorithms and displays results in a structured manner, aiding in understanding how conclusions are derived.

Features

Query Inputs
Summary
Base Rank
Rational Closure
Lexicographic Closure

Query Forms

Edit query inputs

Upload Knowledge Base

Upload knowledge base

Query formula and knowledge base

Summary

Summary of entailment algorithms

Base Rank

Results from base rank algorithm

Rational Closure

Results from rational closure algorithm

Lexicographic Closure

Results from lexicographic closure algorithm

This tool allows users to edit defeasible implication, edit the knowledge base and upload the knowledge base from a text file. The user can compute defeasible entailment. The formulas in this tool are entered as plain text but displayed as Math formulas.

The Summary section shows the entailment results, initial ranking, final rankings and the time taken to compute algorithms. The Base Rank sections shows a step-by-step process on how to construct initial ranking from a given knowledge base. The Rational Closure section shows a step-by-step process starting with initial ranking, to removing ranks and getting the entailment results. The Lexicographic Closure section shows a step-by-step process starting with initial ranking, weaking ranks, removing ranks, and getting the entailment results.

This web tool demonstrates the defeasible reasoning process and serves as a debugger for identifying exceptional knowledge base statements. Future work could focus on extending the software to handle other forms of defeasible entailment, such as Relevant Closure, and on adding optimized entailment algorithms to the tool.

Team

Maqhobosheane Mohlerepe

Team member

mhlmaq001@myuct.ac.za

github.com/maqhobosheane/EXTRC.git

Thabo Vincent Moloi

Team member

mlxtha036@myuct.ac.za

github.com/thabomoloi/extrc.git

Mamodike Sadiki

Team member

sdkmam001@myuct.ac.za

github.com/Tryiphosa/extrc_kbg.git

Tommie Meyer

Supervisor