Expression evaluation over time

Tweet

We have looked at different aspects of knowledge representation during this series and this time its time to look at time itself. How to model logical expressions that incorporate time? I.e. how to store knowledge and query it with time based queries?

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?

Introduction

To be able to model logic expressions that incorporate time we first have to ask ourselves, what do we mean by time? Is it abstract ideas like before, after, now and then? Or is it exact number of ticks since we began to measure? Or is it a combination of both?

This part will be quite heavy on ideas rather then code..
Turns out that I provided code for the examples as well. Enjoy : )

Discrete Time

Lets first look at some definitions of discrete time.

Discrete time views values of variables as occurring at distinct, separate "points in time", or equivalently as being unchanged throughout each non-zero region of time ("time period")—that is, time is viewed as a discrete variable -wikipedia

So basically what we say is that even though time is continuous, we will look at it in a discrete way just to simplify our models.

Events

Lets say that we receive knowledge in the form of events, all data recorded in the event will be added to our Context as one frame. For example:

Time Frame	Name	Occupation	Eye-color	Hair-color
1	Kate	Student	Blue	Brown
2	Kate			Pearlescent
3	Kate			Pink
4	Kate	Student	Blue
5	Kate	Intern		Blonde
6	Kate			Pearlescent
7	Kate	Lawyer		Brown

Time frame can be incremental number if we don't care about actual time passed or a time stamp of when the even occurred.
So lets store all our data in this form.

Full frame from incomplete frames

How to query something like the above example?
One idea is to see each event as its own frame of context. I.e. all expressions written in previous posts would now be transferred to refer only to one frame at a time. But that would be kind of incomplete as all events do not record data on all possible parameters. One way to work around this would be to always start from the latest frame and search backwards in the frame-stack until that parameter gets hit. For example in the example above, a full 'latest' frame of information would be the blue highlighted information as seen in the following table:

Time Frame	Name	Occupation	Eye-color	Hair-color
4	Kate	Student	Blue
5	Kate	Intern		Blonde
6	Kate			Pearlescent
7	Kate	Lawyer		Brown

Occupation(Lawyer) AND Eye-color(Blue) AND Hair-color(Brown)
Would return True

Occupation(Intern) AND Eye-color(Blue) AND Hair-color(Brown)
Would evaluate to False, as it is not the last full aggregate frame. See Occupation column has newer entries then Intern.

Occupation(Lawyer) AND Eye-color(Blue) AND Drives(Volvo XC90)
Would evaluate to Not Sure as there is no event recording any knowledge about what car Kate drives.

Lets look at some C# code to do just that. Lets convert our Evaluate method in the Context class to the following instead:

public EvaluationResult Evaluate(AExpression expression, int frameStart = -1)
{
    if (frameStart == -1)
        frameStart = _frames.Count - 1;
    var facts = new Dictionary<ExpressionLeaf, EvaluationResult>();
    var leafNodes = expression.GetLeafNodes();
    foreach (var node in leafNodes)
    {
        var leaf = node.Leaf;
        var attr = leaf as KnowledgeAttribute;
        var rel = leaf as KnowledgeRelation;
        if (!(attr != null | rel != null))
            continue;
        for (int i = frameStart; i >= 0; i--)
        {
            var frame = _frames[i];
            var result = attr != null ? frame.Evaluate(attr) : frame.Evaluate(rel);

            if (result == EvaluationResult.NotSure)
                continue;
            facts.Add(node, result);
            break;
        }
    }
    if (!facts.Any())
        return EvaluationResult.NotSure;
    if (facts.Values.Any(x => x == EvaluationResult.NotSure))
        return EvaluationResult.NotSure;
    return expression.TransformEvaluation(facts);
}

And the frame/event store looks something like this (still in the Context class):

private readonly List<KnowledgeStore> _frames;
public IReadOnlyCollection<KnowledgeStore> Frames => new ReadOnlyCollection<KnowledgeStore>(_frames);
public KnowledgeStore CurrentFrame => _frames.Last();
public void AddFrame(KnowledgeStore frame)
{
    _frames.Add(frame);
}

Relative queries

So now we have covered how to determine the current state from this event based knowledge store. Next step is to start determining how knowledge relates to each other based on relative time queries.

For this we will need to add an Evaluate method in the Context class for just relative queries:

public EvaluationResult Evaluate(IRelative expression)
{
    return expression.Evaluate(this);
}

All keyword

Time Frame	Name	Occupation	Eye-color	Hair-color
1	Kate	Student	Blue	Brown
2	Kate			Pearlescent
3	Kate			Pink
4	Kate	Student	Blue
5	Kate	Intern		Blonde
6	Kate			Pearlescent
7	Kate	Lawyer		Brown

This one is pretty simple, it just states that All knowledge frames in the store should evaluate the expression to true.
I.e. ALL Name(Kate) AND Eye-color(Blue)
would be True.
But ALL Occupation(Lawyer) would evaluate to False as there exists frames where this statement is false.
And as before, including a fact from a column that has no recorded data in the query would result in Not Sure.

public class RelativeAll : IRelative
{
    private readonly AExpression _expression;

    public RelativeAll(AExpression expression)
    {
        _expression = expression;
    }

    public EvaluationResult Evaluate(Context context)
    {
        var result = EvaluationResult.NotSure;
        for (int frameIndex = context.Frames.Count - 1; frameIndex >= 0; frameIndex--)
        {
            result = context.Evaluate(_expression, frameIndex);
            if(result == EvaluationResult.False)
                return EvaluationResult.False;
        }
        return result;
    }
}

Some unit tests to see how it behaves:

[TestMethod]
public void RelativeAllTest_AddFrame_CurrentUpdated()
{
    Context target;
    var obj = CreateTarget(out target);

    var expr = new ExpressionIs(new KnowledgeRelation { Subject = "Lawyer", Relation = "Occupation of", Target = obj.ToString() });
    var actual = target.Evaluate(expr);
    Assert.AreEqual(EvaluationResult.True, actual);
}

[TestMethod]
public void RelativeAllTest_All_True()
{
    Context target;
    var obj = CreateTarget(out target);

    var expr = new ExpressionIs(new KnowledgeRelation
    {
        Subject = "Alice",
        Relation = "Name of",
        Target = obj.ToString()
    });
    var rel = new RelativeAll(expr);
    var actual = target.Evaluate(rel);
    Assert.AreEqual(EvaluationResult.True, actual);
}

[TestMethod]
public void RelativeAllTest_All_False()
{
    Context target;
    var obj = CreateTarget(out target);

    var expr = new ExpressionIs(new KnowledgeRelation
    {
        Subject = "Lawyer",
        Relation = "Occupation of",
        Target = obj.ToString()
    });
    var rel = new RelativeAll(expr);
    var actual = target.Evaluate(rel);
    Assert.AreEqual(EvaluationResult.False, actual);
}

[TestMethod]
public void RelativeAllTest_All_NotSure()
{
    Context target;
    var obj = CreateTarget(out target);

    var expr = new ExpressionIs(new KnowledgeRelation
    {
        Subject = "Undercut",
        Relation = "Hair style of",
        Target = obj.ToString()
    });
    var rel = new RelativeAll(expr);
    var actual = target.Evaluate(rel);
    Assert.AreEqual(EvaluationResult.NotSure, actual);
}

private static Person CreateTarget(out Context target)
{
    var obj = new Person("Alice");
    obj.Occupation = "Student";
    target = new Context(obj.ToString());
    target.AddFrame(FrameFactory.Create(obj));
    obj.Occupation = "Lawyer";
    target.AddFrame(FrameFactory.Create(obj));
    return obj;
}

Before keyword

Time Frame	Name	Occupation	Eye-color	Hair-color
4	Kate	Student	Blue
5	Kate	Intern		Blonde
6	Kate			Pearlescent
7	Kate	Lawyer		Brown

Syntax: Expression1 Before Expression2
A little harder, trying to determine if Expression1 evaluates true in a full frame before Expression2 evaluates true.
For example:
(Name(Kate) AND Occupation(Intern) AND Hair-color(Blonde)) Before (Name(Kate) AND Occupation(Intern) AND Hair-color(Pearlescent))
Would evaluate to True.

(Name(Kate) AND Occupation(Intern) AND Hair-color(Pearlescent)) Before (Name(Kate) AND Occupation(Intern) AND Hair-color(Blonde))
Would evaluate to False.

And as before, including a fact from a column that has no recorded data in the query would result in Not Sure.

Tricky one is if only one of the expressions evaluate but the other comes back Not Sure, I think for sake of consistency we should evaluate that as Not Sure also.

public class RelativeBefore : IRelative
{
    private readonly AExpression _left;
    private readonly AExpression _right;

    public RelativeBefore(AExpression left, AExpression right)
    {
        _left = left;
        _right = right;
    }

    public EvaluationResult Evaluate(Context context)
    {
        int rightFrameIndex;
        var rightResult = EvaluateExpression(context, _right, out rightFrameIndex);
        int leftFrameIndex;
        var leftResult = EvaluateExpression(context, _left, out leftFrameIndex);

        if (leftResult == EvaluationResult.NotSure || rightResult == EvaluationResult.NotSure)
            return EvaluationResult.NotSure;

        if (leftResult == EvaluationResult.True && rightResult == EvaluationResult.True)
        {
            return leftFrameIndex < rightFrameIndex ? EvaluationResult.True : EvaluationResult.False;
        }
        return EvaluationResult.False;
    }

    private EvaluationResult EvaluateExpression(Context context, AExpression expression, out int frameIndex)
    {
        var result = EvaluationResult.NotSure;
        for (frameIndex = context.Frames.Count - 1; frameIndex >= 0; frameIndex--)
        {
            result = context.Evaluate(expression, frameIndex);
            if (result == EvaluationResult.True)
            {
                return EvaluationResult.True;
            }
        }
        return result;
    }
}

Some tests to clarify things:

[TestMethod]
public void RelativeBeforeTest_True()
{
    Context target;
    var obj = CreateTarget(out target);

    var expr1 = new ExpressionIs(new KnowledgeRelation { Subject = "Student", Relation = "Occupation of", Target = obj.ToString() });
    var expr2 = new ExpressionIs(new KnowledgeRelation { Subject = "Lawyer", Relation = "Occupation of", Target = obj.ToString() });
    var relative = new RelativeBefore(expr1, expr2);
    var actual = target.Evaluate(relative);
    Assert.AreEqual(EvaluationResult.True, actual);
}
[TestMethod]
public void RelativeBeforeTest_False()
{
    Context target;
    var obj = CreateTarget(out target);

    var expr1 = new ExpressionIs(new KnowledgeRelation { Subject = "Student", Relation = "Occupation of", Target = obj.ToString() });
    var expr2 = new ExpressionIs(new KnowledgeRelation { Subject = "Lawyer", Relation = "Occupation of", Target = obj.ToString() });
    var relative = new RelativeBefore(expr2, expr1);
    var actual = target.Evaluate(relative);
    Assert.AreEqual(EvaluationResult.False, actual);
}
[TestMethod]
public void RelativeBeforeTest_LeftNotSure_NotSure()
{
    Context target;
    var obj = CreateTarget(out target);

    var expr1 = new ExpressionIs(new KnowledgeRelation { Subject = "Undercut", Relation = "Hair style of", Target = obj.ToString() });
    var expr2 = new ExpressionIs(new KnowledgeRelation { Subject = "Lawyer", Relation = "Occupation of", Target = obj.ToString() });
    var relative = new RelativeBefore(expr1, expr2);
    var actual = target.Evaluate(relative);
    Assert.AreEqual(EvaluationResult.NotSure, actual);
}
[TestMethod]
public void RelativeBeforeTest_RightNotSure_NotSure()
{
    Context target;
    var obj = CreateTarget(out target);

    var expr1 = new ExpressionIs(new KnowledgeRelation { Subject = "Undercut", Relation = "Hair style of", Target = obj.ToString() });
    var expr2 = new ExpressionIs(new KnowledgeRelation { Subject = "Lawyer", Relation = "Occupation of", Target = obj.ToString() });
    var relative = new RelativeBefore(expr2, expr1);
    var actual = target.Evaluate(relative);
    Assert.AreEqual(EvaluationResult.NotSure, actual);
}
private static Person CreateTarget(out Context target)
{
    var obj = new Person("Alice");
    obj.Occupation = "Student";
    target = new Context(obj.ToString());
    target.AddFrame(FrameFactory.Create(obj));
    obj.Occupation = "Lawyer";
    target.AddFrame(FrameFactory.Create(obj));
    return obj;
}

Conclusions and future work

The method to determine a 'full' frame by aggregating each column backwards gives room for uncertainty as we don't really consider the time between two events that are aggregated together into one frame, if we only have a few records of knowledge and the time between those events is years, then maybe we should be a little bit more uncertain.. a little bit more fuzzy in our determination. Or perhaps return a probability value together with the result. I.e.
True: 0.95
False: 0.1
NotSure: 0.4

And that way be able to build a little more smooth evaluations. But for now this suites my needs.
Another improvement could be to add variance per knowledge column. I.e. if the name is always Kate, then variance should be 0, but for the hair color in the example above it should be way higher as it changes for each event..
Addition of more types of relative expressions could be useful. Exists, Followed by, X years ago etc. But here I think the requirements for each type of project needs to guide the way.

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

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