Note: I wrote this blog to clarify some of my ideas on the subject and also in the hope that some of it may be of interest to others. Keep in mind that all of this is work-in-progress.

Let's first take a look at the parse tree of the sentence:

S
+-- S
    +-- WhNP
        +-- whword: how
        +-- NP
            +-- NBar
                +-- proper noun: old
    +-- aux: was
    +-- NP
         +-- proper noun: Lord Byron
+-- SBar
    +-- whword (?): when 
    +-- S
        +-- NP
             +-- proper noun: Lady Lovelace
        +-- aux: was
        +-- VP
            +-- verb: born

The sentence consist of a main clause ("how old was Lord Byron") and a dependent clause ("Lady Lovelace was born"). The dependent clause is an adverbial clause that modifies the time of the main clause. The word "when" is a complementizer. I got this information from [Brinton-2000, p.221], a very useful book.

To answer the question you can do two things: look it up or calculate it. In the sentences I handled before this one, I was able to look up the answer. Now it's different. Why? Because the knowledge base doesn't have a direct relation that tells me how old Lord Byron was when his talented daughter was born.

age_at_time(lord_byron, birthdate_lady_lovelace, x)

So, calculation then. But how does that work?

It is useful to set out what I'm trying to achieve. I want my agent to calculate the age of Lord Byron at a given moment and report it to a user. The algorithm for this calculation could go something like this:

input:

1. question: age?
2. object: Lord Byron
3. t-time: the time of birth of Lady Lovelace

One thing is asked: an age. And age is a function of a person (or animate object, in general) and a given time. The function is quite simply:

1. get the time of birth of object (o-time)
2. subtract o-time from t-time
3. convert the result to years (rounding off to the first integer below)

At this point we have a syntactic representation of the sentence and an algorithm to calculate the result. To do the actual math we also need to look up two birthdates in our knowledge base. What is missing is a framework that incorporates these parts.

Recently, I have read some books about computational semantics. In these books there are no completely worked out techniques of how to solve this kind of problem, but there are many ideas and examples.  I will name two.

1. Use a separate, semantic, representation based on relations.

The syntactic representation of a sentence is not used for reasoning. It is first transformed into a semantic representation. In this representation the meaning of the sentence is split up in its relations. These could be Predicate Calculus relations, but not necessarily so. Important is that there is a simple uniform representation of the way objects, things, entities are connected to each other and to their own properties.

In the example I use here, this would be

name(o1, "Lord Byron") 
age(o1, t1, a1)

but I am also thinking of labeling the arguments, like this:

name(subject: o1, object: "Lord Byron")
age(subject: o1, time: t1, object: a1)

With this representation it is easy to accomplish that certain arguments can be optional and others are required.

Predicate Calculus relations have a fixed number of arguments and may that be a handicap in natural language processing. However, since it is such an established paradigm, many tools exist for it that might help you. I doubt many tools are available in PHP, however ;) Reasoning with natural language is usually done in Lisp and Prolog, and more recently, Haskell. I chose to stear away from these languages however, because the built-in processor of the language fixes some of the things you may want to control yourself.

2. Relations are goals to be achieved and functions to be performed.

I am writing this title down easily now, but it took me a lot of time to find it out, and it is the most important insight I gained over the last month.

When a sentence is transformed into a set of relations, these might look something like this (I will probably use a different representation later):

age(object1, time1, q)             "How old was"
name(object1, "Lord Byron")        "Lord Byron"
time(time1, event1)                "when"
same(event1, event2)
name(object2, "Lady Lovelace")     "Lady Lovelace"
birth(event2, object2)             "was born"

Where q is the answer to be found.

There's a set of relations and a goal variable. But how do you find the value (or values) of this variable?

The key is to transform the sentence into a goal hierarchy. Here is a Prolog-like representation of the sentence to illustrate what I mean:

answer(q) :- name(object1, "Lord Byron"), name(object2, "Lady Lovelace"), 
                 time(time1, event1), same(event1, event2), birth(event2, object2), age(object1, time1, q).

The goal is answer(q) and it can be reached by performing the sub-goals that are named after the :- sign.

To reach the goal age(object1, time1, q), look for another one of these rules, which are called "Horn clauses", with age() in its head:

age(o1, t1, a) :- birth(o1, t2), diff_in_years(t2, t1, a).

Such a rule needs to be hardcoded in the agent. It is a form of procedural knowledge. So the original goal is now split up in sub-goals, or tasks. Some of these tasks are just built-in functions that are performed immediately, like "diff()", which computes the difference between t2 and t1 and places the result in d.

Let me give you some other examples of goal-hierarchy based representations of meaning from what I've read:

"Which customer ordered a five dollar shake?"

que(Y, 
    customer(Y), 
    some(X, 
        and(fdshake(X), order(Y, X))))

from [Blackburn and Bos-2005] (p. 294)        

It shows, interestingly, that determiners ("some") cause an extra level to be introduced in the sentence. A level in which a new variable is introduced.

"Which red block supports three pyramids but is not contained in a box?"

(THPROG (X1)
    (THGOAL(#IS $?X1 #BLOCK))
    (#EQDIM $?X1)
    (THGOAL(#COLOR $?X1 #RED))
    (THFIND 3 $?X2 (X2) (THGOAL (#IS ?$X2 #PYRAMID))
                        (THGOAL (#SUPPORT $?X1 $?X2)))
    (THNOT(THPROG(X3)
        (THGOAL(#IS $?X3 #BOX))
        (THGOAL(#CONTAIN $?X3 $?X1)))))

from [Winograd-1972] (p. 127)
This also shows the nested namespaces. It shows that the noun of an entity ("BLOCK") is not a predicate but a value. And it shows how to deal with determiners like "three".  

"Which European country exports no arms to countries in Africa?"

answer(C) <=
    european(C) &
    country(C) &
    \+exists(X, 
        arm(X) &
        exists(C1, 
            country(C1) & 
            in(C1, africa) &
            exports(C, X, C1)))

from [Warren and Pereira-1982] (p. 110) - this is an article
Again a query that shows how a negation can be implemented.

"Which flight is serving lunch?"

WHQ(x, ∃e, x, 
    Isa(e, Serving) & 
    Server(e, x) &
    Served(e, Lunch) &
    Isa(x, Flight))  

from [Jurafsky and Martin-2000] (p. 560)
The roles in the event are implemented as special predicates (Server, Served).


There are number of interesting properties of treating semantics this way:

The three types of sentences can be expressed in a natural way.

• Imperative sentences (= commands) are expressed as tasks to be performed.
• Interrogative sentences (= questions) are expressed as plans to find the answer.
• Declarative sentences (= statements) are expressed as the task to insert a description into the local memory store.

Functions/goals are devices that take several input values and return a single value. A function can be performed in different ways:

• A function can be a system function, like 'add(x, y)'. It is performed immediately by the agent
• A function can contain a plan that has a series of steps.
• A function can be considered a statement that is looked up in a third-party knowledge base
• A function can contain program logic, like AND, NOT, IF/THEN/ELSE

The execution of a function can be delayed. It may be placed on a todo list. Perhaps it can even be given a priority. These functions could then be performed later. This would give the agent a more human-like intelligence.  

The examples above show that Prolog is very suitable for this task. But it is perfectly possible to write a basic Prolog-like engine yourself. You will not and should need to full toolset of the language.

Problems

• How are relations modeled in a manner that facilitates reasoning and integration with other knowledge sources?
• How is the goal-hierarchy tree built from the syntax tree? In sequence or in parallel?

Conclusion

So, how old was he?

1. Find the entity by the name of "Lady Lovelace" in a Knowledge Base: o1
2. Find the date of birth of o1 in the same Knowledge Base (b1): 10 December 1815
3. Find the entity by the name of "Lord Byron" in a Knowledge Base: o2
4. The time of the age of o2 (t2) is set to be the same as the time of the birth of o1 (b1)
5. To calculate the age we need to know the birthdate of o2 (b2), calculate the difference between t2 and b2, and transform the difference into years
6. Find the date of birth of o2 in the same Knowledge Base (b2): 22 January 1788
7. The difference between 10 December 1815 and 22 January 1788 (in years) is 27 (check here)

He was 27.

I want to add something about the books I read.

The books [Blackburn and Bos-2005] and [Eijk and Unger-2010] treat the problem from the perspective of a logicist. This is important to know because unless you are a student of logic, their approach may be hard to follow. They stay firmly rooted in First Order Predicate Calculus with a preference for Lambda Calculus. I found them to be of little use for my application.

The books [Allen-1995] and [Jurafsky and Martin-2000] I can recommed to everyone. The latter one is the standard work in the field and it contains many priceless algorithms. That being said, these works offer a great many ways to treat semantics, but none of these are worked out to great extent. Expect to learn the concepts, but not the details.

[Charniak and Wilks-1976] has stolen my heart. It is a wonderful work that treats the subject with a child-like innocence and a puberal honesty. I may seem old but remember that a lot of the AI ideas were already formed at that time and this books reflects on many of them.

And I conclude with the book that is both the oldest and, surprisingly, the most practically useful to me: [Winograd-1972]. In this book Winograd describes the structure and workings of his masterpiece of natural language processing: SHRDLU. This is really the best book to read when learning how to deal with many of the problems you encounter when actually building a semantic NLP system. SHRDLU is often put away as being "procedural", but I believe this to be inessential. Many of Winograds ideas can be used in any approach to NLP and it is the extensive ground he covered that makes it so very interesting.

Books and articles

[Winograd-1972] Understanding Natural Language - Terry Winograd
[Charniak and Wilks-1976] Computational Semantics - Eugene Charniak and Yorick Wilks, eds.
[Warren and Pereira-1982] An Efficient Easily Adaptable System for Interpreting Natural Language Queries
[Allen-1995] Natural Language Understanding
[Brinton-2000] The structure of modern english - Laurel J. Brinton
[Jurafsky and Martin-2000] Speech and Language Processing - Daniel Jurafsky and James H. Martin
[Blackburn and Bos-2005] Representation and Inference for Natural Language
[Eijk and Unger-2010] Computational Semantics with Functional Programming