Thursday, September 15, 2016

Knowledge based reasoning in .net c#


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.

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

No comments:

Post a Comment