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

Knowledge based reasoning in .net c#

Tweet

I've lately been working on a side project in AI. One of the key parts of it is to figure out how to include a knowledge base and let the program reason about things itself. So how to model knowledge?


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?

Prolog

Somewhere in the back of my head I have a class that I took back in university that scratched the surface of the Prolog language.
In a very simplified way the Prolog language uses facts and rules.

Facts in Prolog are in the form:

cat(pixel)

In other words, it is a known fact that pixel is a cat.
You can then go ahead and as for all the cats and get back pixel.
The fun things start when you define the rule that cat is an animal

animal(X) :- cat(X)

and start asking about animals and get back pixel.
A special case of rule you add a tuple and thus basically gain a relation

brotherOf(prime, pixel)
brotherOf(tiger, pixel)

meaning that prime and tiger and brothers to pixel.

As said, this is a very vague memory from the back of my head. If you are looking for a Prolog tutorial, then this is not the post for you.

Modelling knowledge

So, my approach to model knowledge is influenced by Prolog but that's about it. As I want the application to create the knowledge by itself there is no need to write a complicated textual representation, just a model that can be added to a queried. The textual representation used in this article are just there to make it easier to write about it
The model will be

attribute(variable)
relation(variable1, variable2)
variable1 => variable2

In this first version it is also assumed that all variables are strings. The attribute, relation and implication names are also treated as strings.

Some code for the knowledge model:

public class KnowledgeAttribute
{
 public string Attribute { get; set; }
 public string Subject { get; set; }
 public override string ToString()
 {
  return $"'{Attribute}'('{Subject}')";
 }
}
public class KnowledgeImplication
{
 public string Implicator { get; set; }
 public string Implied { get; set; }
 public override string ToString()
 {
  return $"'{Implicator}' => '{Implied}'";
 }
}
public class KnowledgeRelation
{
 public string Relation { get; set; }
 public string Subject { get; set; }
 public string Target { get; set; }
 public override string ToString()
 {
  return $"'{Relation}'('{Subject}', '{Target}')";
 }
}

So nothing too complicated there. Lets for simplicity store them in a holding object

public class KnowledgeModel
{
 public Dictionary<string, KnowledgeAttribute> Attributes { get; set; }
 public Dictionary<string, KnowledgeRelation> Relations { get; set; }

 public Dictionary<string, KnowledgeImplication> Implications { get; set; }

 public KnowledgeModel()
 {
  Attributes = new Dictionary<string, KnowledgeAttribute>();
  Relations = new Dictionary<string, KnowledgeRelation>();
  Implications = new Dictionary<string, KnowledgeImplication>();
 }
}

Querying

Now we can start querying the model. To get all variables with the same attribute:

public HashSet<string> ListAllWith(string attribute)
{
 return new HashSet<string>(from x in _model.Attributes.Values
  where
   x.Attribute.Equals(attribute, StringComparison.OrdinalIgnoreCase)
  select x.Subject
  );
}

Get variables matching a list of attributes

public HashSet<string> ListAllWith(IEnumerable attributes)
{
 HashSet<string> result = null;
 foreach (var attribute in attributes)
 {
  var found = ListAllWith(attribute);
  if (found.Count == 0)
   break; // nothing matches all attributes

  if (result == null)
   result = found;
  else
   result.IntersectWith(found);

  if (result.Count == 0)
   break; // nothing matches all attributes
 }
 return result;
}

Get all implications

private HashSet<string> GetAllImplications(string implied)
{
 var result = new HashSet<string>();
 result.UnionWith(from x in _model.Implications.Values
  where x.Implied.Equals(implied, StringComparison.OrdinalIgnoreCase)
  select x.Implicator);
 var chained = new HashSet<string>();
 foreach (var item in result)
 {
  chained.UnionWith(GetAllImplications(item));
 }
 result.UnionWith(chained);
 result.Add(implied);
 return result;
}

Or all related

public HashSet<string> ListAllRelated(string relationType, string variable)
{
 var relationTypes = GetAllImplications(relationType);
 return new HashSet<string>(from x in _model.Relations.Values
  where
  relationTypes.Contains(x.Relation)
  && x.Target.Equals(variable, StringComparison.OrdinalIgnoreCase)
  select x.Subject
  );
}

So. now just fill it with data and start querying.
Hope this helps someone out there

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

For example source code, head over to my github repository and play around for yourself:

Good luck :)

This is part of a series of posts regarding Knowledge modelling and expression evaluation.
The next part is
Logic Expression evaluation with open-world assumption