Inference engine
This article needs to be updated.(October 2019) |
In the field of
Additionally, the concept of 'inference' has expanded to include the process through which trained
Architecture
The logic that an inference engine uses is typically represented as IF-THEN rules. The general format of such rules is IF <logical expression> THEN <logical expression>. Prior to the development of expert systems and inference engines, artificial intelligence researchers focused on more powerful
A simple example of modus ponens often used in introductory logic books is "If you are human then you are mortal". This can be represented in pseudocode as:
Rule1: Human(x) => Mortal(x)
A trivial example of how this rule would be used in an inference engine is as follows. In forward chaining, the inference engine would find any facts in the knowledge base that matched Human(x) and for each fact it found would add the new information Mortal(x) to the knowledge base. So if it found an object called Socrates that was human it would deduce that Socrates was mortal. In backward chaining, the system would be given a goal, e.g. answer the question is Socrates mortal? It would search through the knowledge base and determine if Socrates was human and, if so, would assert he is also mortal. However, in backward chaining a common technique was to integrate the inference engine with a user interface. In that way, rather than simply being automated the system could now be interactive. In this trivial example, if the system was given the goal to answer the question if Socrates was mortal and it didn't yet know if he was human, it would generate a window to ask the user the question "Is Socrates human?" and would then use that information accordingly.
This innovation of integrating the inference engine with a user interface led to the second early advancement of expert systems: explanation capabilities. The explicit representation of knowledge as rules rather than code made it possible to generate explanations to users: both explanations in real time and after the fact. So if the system asked the user "Is Socrates human?", the user may wonder why she was being asked that question and the system would use the chain of rules to explain why it was currently trying to ascertain that bit of knowledge: that is, it needs to determine if Socrates is mortal and to do that needs to determine if he is human. At first these explanations were not much different than the standard debugging information that developers deal with when debugging any system. However, an active area of research was utilizing natural language technology to ask, understand, and generate questions and explanations using natural languages rather than computer formalisms.[3]
An inference engine cycles through three sequential steps: match rules, select rules, and execute rules. The execution of the rules will often result in new facts or goals being added to the knowledge base, which will trigger the cycle to repeat. This cycle continues until no new rules can be matched.
In the first step, match rules, the inference engine finds all of the rules that are triggered by the current contents of the knowledge base. In forward chaining, the engine looks for rules where the antecedent (left hand side) matches some fact in the knowledge base. In backward chaining, the engine looks for antecedents that can satisfy one of the current goals.
In the second step, select rules, the inference engine prioritizes the various rules that were matched to determine the order to execute them. In the final step, execute rules, the engine executes each matched rule in the order determined in step two and then iterates back to step one again. The cycle continues until no new rules are matched.[4]
Implementations
Early inference engines focused primarily on forward chaining. These systems were usually implemented in the
As expert systems moved from research prototypes to deployed systems there was more focus on issues such as speed and robustness. One of the first and most popular forward chaining engines was OPS5, which used the Rete algorithm to optimize the efficiency of rule firing. Another very popular technology that was developed was the Prolog logic programming language. Prolog focused primarily on backward chaining and also featured various commercial versions and optimizations for efficiency and robustness.[5]
As expert systems prompted significant interest from the business world, various companies, many of them started or guided by prominent AI researchers created productized versions of inference engines. For example, Intellicorp was initially guided by Edward Feigenbaum. These inference engine products were also often developed in Lisp at first. However, demands for more affordable and commercially viable platforms eventually made personal computer platforms very popular.
Open source implementations
ClipsRules and RefPerSys (inspired by CAIA [6] and the work of Jacques Pitrat). The Frama-C static source code analyzer also uses some inference engine techniques.
See also
- Geometric and Topological Inference
- Action selection
- Backward chaining
- Expert system
- Forward chaining
- Inductive inference
References
- ^ ISBN 0-201-10686-8.
- ISBN 0201118114.
- ^ Barzilayt, Regina; Daryl McCullough; Owen Rambow; Jonathan DeCristofaro; Tanya Korelsky; Benoit Lavoie. "A New Approach to Expert System Explanations" (PDF). USAF Rome Laboratory Report. Archived from the original on July 5, 2016.
- ^ Griffin, N.L., A Rule-Based Inference Engine which is Optimal and VLSI Implementable, University of Kentucky.
- ISBN 0-262-19250-0.
- ISBN 978-1848211018.