Sunday, November 6, 2016

Logic Expression evaluation with open-world assumption


So, we have looked at how to store knowledge and the basics of open/closed world assumptions in previous posts.

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

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.
Good luck :)

No comments:

Post a Comment