Logic Expression evaluation with open-world assumption

Tweet

Now it is time to look at how to evaluate expressions against that stored knowledge.

Knowledge based reasoning in .net c#
Reasoning in Open or Closed models
Logic Expression evaluation with open-world assumption
Expression evaluation on object based models
Expression evaluation over time
Expression evaluation over time - Was?

Logic operators

Logical AND

The AND operator evaluates true, if both the right and the left side expression evaluate as true.
Leading to the following truth table:

AND	TRUE	FALSE
TRUE	TRUE	FALSE
FALSE	FALSE	FALSE

In code:

public override EvaluationResult TransformEvaluation(Dictionary<ExpressionLeaf, EvaluationResult> facts)
{
 var leftResult = Left.TransformEvaluation(facts);
 if (leftResult != EvaluationResult.True)
  return EvaluationResult.False;

 var rightResult = Right.TransformEvaluation(facts);
 if(rightResult != EvaluationResult.True)
  return EvaluationResult.False;

 return EvaluationResult.True;
}

Logical OR

The OR operator evaluates true, if any of the left or right side expressions evaluate as true.
This gives the following truth table:

OR	TRUE	FALSE
TRUE	TRUE	TRUE
FALSE	TRUE	FALSE

In code:

public override EvaluationResult TransformEvaluation(Dictionary<ExpressionLeaf, EvaluationResult> facts)
{
 var leftResult = Left.TransformEvaluation(facts);
 if (leftResult == EvaluationResult.True)
  return EvaluationResult.True;

 var rightResult = Right.TransformEvaluation(facts);
 if (rightResult == EvaluationResult.True)
  return EvaluationResult.True;

 return EvaluationResult.False;
}

Logical XOR

The XOR, i.e. the exclusive OR operator evaluates true, if either the left or the right hand side is true. But false if both are equal.
Truth table:

XOR	TRUE	FALSE
TRUE	FALSE	TRUE
FALSE	TRUE	FALSE

In code:

public override EvaluationResult TransformEvaluation(Dictionary<ExpressionLeaf, EvaluationResult> facts)
{
 var leftResult = Left.TransformEvaluation(facts);
 var rightResult = Right.TransformEvaluation(facts);

 if ((leftResult == EvaluationResult.True && rightResult == EvaluationResult.False)
  || (leftResult == EvaluationResult.False && rightResult == EvaluationResult.True))
  return EvaluationResult.True;
 
 return EvaluationResult.False;
}

Logical NOT

The NOT operator only has a right side value and evaluates true if it is false.
Truth table

NOT	TRUE	FALSE
-	FALSE	TRUE
-	-	-

In code:

public override EvaluationResult TransformEvaluation(Dictionary<ExpressionLeaf, EvaluationResult> facts)
{
 var result = Right.TransformEvaluation(facts);
 switch (result)
 {
  case EvaluationResult.False:
   return EvaluationResult.True;
  case EvaluationResult.True:
   return EvaluationResult.False;
  case EvaluationResult.NotSure:
   return EvaluationResult.NotSure;
  default:
   throw new ArgumentOutOfRangeException();
 }
}

Expression evaluation

Now that we have the basic logical operators to use to form our expressions. Lets look at how to evaluate:

In my code base I have a number of expression types, that include AND, OR, XOR, NOT and LEAF.

The leaf is a special case that contains one single KnowledgeItem and can be evaluated against the expression.

The leaf node evaluation is as follows:

public override EvaluationResult TransformEvaluation(Dictionary<ExpressionLeaf, EvaluationResult> facts)
{
 return facts[this];
}

So. The expression tree contains AND, OR, XOR and NOT operations but only the leaf nodes contains actual information that can be evaluated.
Also, you may have noted that the most of these operators above just Transform an result, and they only take into account True and False values, whereas in the open-world assumption we should also have the Unknown/NotSure value.
In my implementation I decided to evaluate each and every Leaf node at the start of the evaluation method. If any NotSure values were found, the result was not transformed. Meaning the logical operators were not hit. The evaluation method just returned NotSure directly.

public EvaluationResult Evaluate(AExpression expression)
{
 var facts = new Dictionary<ExpressionLeaf, EvaluationResult>();
 var leafNodes = expression.GetLeafNodes();
 foreach (var node in leafNodes)
 {
  var attr = node.Leaf as KnowledgeAttribute;
  if (attr != null)
  {
   facts.Add(node, KnowledgeStore.Evaluate(attr));
  }
  var rel = leaf as KnowledgeRelation;
  if (rel != null)
  {
   facts.Add(node, KnowledgeStore.Evaluate(rel));
  }
 }
 if (facts.Values.Any(x => x == EvaluationResult.NotSure))
  return EvaluationResult.NotSure;
 return expression.TransformEvaluation(facts);
}

All code provided as-is. This is copied from my own code-base, May need some additional programming to work.CodeProject
Good luck :)

Reasoning in Open or Closed models

Tweet

I've been thinking a lot on how to model knowledge and how to let a system work with it in a programmatic way.


Other articles in the AI Knowledge Based Reasoning series on this site:
Knowledge based reasoning in .net c#
Reasoning in Open or Closed models
Logic Expression evaluation with open-world assumption
Expression evaluation on object based models
Expression evaluation over time
Expression evaluation over time - Was?

Closed-world model

This is where I am at the moment in my thinking and in the coding of my current project. Mostly because it is quite stand forward to implement in code.

public bool Evaluate(expression);

In the closed-world model, everything that you do not find an answer for in your model is assumed to be false.
At first, this seems like a OK thing to do. Assuming that your model covers everything. For example in games, where the AI-engine has access to all information this is the way to go. But in an situation where the model does not cover everything I find it lacking. My current project tries to interface with the real world and when its reasoning returns False on everything that it does not know the end results are quite off the board.

Open-world assumption

So instead of just the boolean result of true or false. In the open-world assumption we introduce a third option, the NotSure result of an evaluation.

public EvaluationResult Evaluate(expression);
public enum EvaluationResult
{
 True,
 False,
 NotSure
}

So far quite easy, just convert your Evaluation method to return NotSure when its not sure.
But the question is, what to do when the system is not sure about something?
Options are:

• Nothing, just wait until it is sure. Could be OK for systems that receive a lot of information. Just assume that the information missing will arrive at a later date.
• Formulate a question regarding the missing piece of information. Break the evaluated expression into pieces and find out what was missing and ask a user or two to provide that input.
• Figure out how much of an expression is unsure. Is it OK to still act on a result with 75% knowledge and 25% gaps? Maybe the AI should figure out the accepted level of certainty by trial and error. 

Conclusions

As I wrote in the beginning. I'm not sure how to implement this kind of reasoning myself. First step in converting the closed-world system that I have now to an open world one is to go by the Nothing approach. Basically just returning NotSure and then not acting on it for starters. Could not be worse than assuming a false falsehood that the system does now.

Sources

https://en.wikipedia.org/wiki/Closed-world_assumption
https://en.wikipedia.org/wiki/Open-world_assumption