Inference engine

Run a knowledge base

Quick start: Download knowledge-base-example.xml (run it, view it) and read the comments to get familiar with the knowledge base format. Modify the file, upload it here and select Run to run it.

If you have a question or are stuck, you should ask your Teaching Assistant. If you notice a bug or have an idea to improve this system, please file an issue on Github.

How it works

After uploading your knowledge base, the program uses it to ask questions and come to a conclusion. It works like a simple QA-system. At anytime you can open the debug panel to view the current state of facts, questions, rules etc.

A knowledge base used by this program consists of rules, questions and one or multiple goals. Both rules and questions can yield knowledge which is stored in facts.

The program will try to infer the value of goals by looking for rules it can apply using the knowledge it already has. If it doesn't find any rules for which all the facts in the <if>-clause are known, it will add the unknown facts to the goal stack. It will also look for questions that could yield the facts looked for and will ask the one that has the most impact on the state of the knowledge base.

Note that this program uses a closed world assumption: if it cannot decide the value of a fact based on rules or questions, it will assign it the value undefined. You should never use that litteraly in your knowledge base, but you can make use of the fact that undefined is not equal to yes or some other value.

Tools

This website has a few tools available to help you with understanding what is happening.

When a question is asked, click the Debug button in the top bar to open the debug sidebar. This shows you the current known facts, the goal stack, the rules that are not yet applied and a step by step log of what has already happened.

Another option is the Analyse button. Here you can see the program try to infer all possible values of facts in your knowledge base and whether they are inferred or tested by rules. A rule infers a fact if it occurs in the <then>-clause, and tested if it occurs in the <if>-clause.

Order of execution

The solver uses a simple loop to infer stuff:

  1. The solver starts when solveAll() is called:
    1. While there are still goals on the goal stack:
      1. Try to solve the top most goal (see the solve function):
        1. First apply forward chaining to infer any new facts
        2. Check the current value of the goal
        3. If it is already a Yes or No, (i.e. it was already inferred during the forward chaining step) continue to to the next goal in the stack.
        4. If there are rules that can infer this fact, add those to the goal stack if they are not already in there. (These rules cannot yet infer this fact because otherwise they would already have done so during the forward chaining step.)
        5. If there are no rules but there are questions that can be asked to infer the fact, ask one of those.
        6. Otherwise, set the fact to $unknown.
    2. If a question was asked, show that on the screen and stop.
    3. As soon as it is answered, add the answer to the set of facts and start again with solveAll().

Writing a knowledge base

The knowledge base is written using simple XML. Globally, your file will look something like this:

<knowledge>
	<title>My test kb</title>
	<description>Decide whether to take a course.</description>

	<!-- Here follow multiple rules, questions and goals -->

	<!-- And yes, you can use this syntax to add
	     comments to your knowledge base :) -->
</knowledge>

You can download and run knowledge-base-example.xml (run it, view it) as a start and modify it to fit your needs. It contains comments explaining all the rules and clauses.

Facts

The most atomic part of this reasoning engine are little <fact> elements. They are what it tries to derive and they are the fundamental elements of all the rules, as you will see in the next sections.

<fact name="follow-course">yes</fact>

A fact always has a name specified using the attribute name and a value. A name could be follow-course and the value could be yes, no, whatever-you-like or undefined. The last value is a bit special, as this is the value the inference engine gives a fact when there are no more rules nor questions which can give the fact a value. I like to treat undefined as an implicit no, because it is not yes as far as I know.

Goals

Goals are the facts that your knowledge base is trying to answer and are the initial elements on the goal stack. At the end, the conclusion for each goal is shown. For example, if your knowledge base is written for answering whether you should follow a course it will show you what it recommends.

<goal name="follow-course">
	<description>Should you follow the course?</description>
	<answer value="yes">Yes, you should</answer>
	<answer value="no">No, you should not</answer>
	<answer>You should decide for yourself</answer>
</goal>

The last cause does not explicitly test for a value, which will make it test for the undefined value. See the closed world assumption.

Rules

The inference engine tries to gain new knowledge by applying rules. The rules, however, are very straightforward if-then rules. They also have a description but that is just there to help you remember what the rules encode. The most basic example of a rule:

<rule>
	<description>If the course is mandatory,
	  you should follow this course.</description>
	<if>
		<fact name="course-is-mandatory">yes</fact>
	</if>
	<then>
		<fact name="follow-course">yes</fact>
	</then>
</rule>

Furthermore, you can use <and>, <or> and <not> clauses to form more complex rules:

<rule>
	<description>If the course is mandatory or fun,
	  you should follow this course.</description>
	<if>
		<or>
			<fact name="course-is-mandatory">yes</fact>
			<fact name="course-is-fun">yes</fact>
		</or>
	</if>
	<then>
		<fact name="follow-course">yes</fact>
	</then>
</rule>

You can nest those as deep as you want. However, most of the time it is easier to chain a few rules. For example, writing two rules: if (teacher-is-interesting = yes and material-is-interesting = yes) then course-is-fun = yes and if (course-is-fun = yes or course-is-mandatory = yes) then follow-course = yes instead of if (teacher-is-interesting = yes and material-is-interesting = yes) or (course-is-mandatory = yes) then follow-course = yes. As for all programming challenges, less complex rules are almost always better.

Questions

You cannot test your knowledge base without data from the outside. So as some facts can be derived from rules inside the knowledge base, such as follow-course, others like material-is-interesting need to be asked to the user of the system. This can be done by defining questions for such facts:

<question>
	<description>If the material of the course interesting?</description>
	<option>
		<description>The material is very interesting</description>
		<then>
			<fact name="material-is-interesting">yes</fact>
		</then>
	</option>
	<option>
		<description>It is utterly boring</description>
		<then>
			<fact name="material-is-interesting">no</fact>
		</then>
	</option>
</question>