Skip links
Main content

"How old was Lord Byron when Lady Lovelace was born?"

maandag 22 oktober 2012 20:16

What does it take to answer this question through computation?


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

Labels
books
nlp

« Terug

Reacties op '"How old was Lord Byron when Lady Lovelace was born?"'

1 2 Laatste pagina
Pim
Geplaatst op: 22-10-2012 22:42 Quote
Leuk stuk weer Patrick, ik vind het gaaf dat je deze met de wereld deelt!

Ik heb zelf nog het een en ander gedaan op school dat raakt aan dit onderwerp: automatische resolutie. Horn clauses zijn daarbij een essentieel concept. Later hebben we dit gebruikt om te programmeren in Prolog, maar eerst kregen we er een uitgebreid tentamen over ;-)
toms outlet
Geplaatst op: 26-06-2013 15:42 Quote
Hello there, I found your web site by the use of Google at the same time as searching for a comparable topic, your site came up, it seems good. I've bookmarked it in my google bookmarks. toms outlet http://www.ideavelopers.com/tomsshoes.php
oakley sunglasses
Geplaatst op: 02-07-2013 06:31 Quote
I am extremely inspired with your writing abilities as well as with the structure on your weblog. Is that this a paid topic or did you customize it your self? Anyway keep up the excellent quality writing, it is uncommon to see a nice blog like this one nowadays..<a href="http://www.razzlewood.com/oakleysunglasses.html">www.razzlewood.com/oakleysunglasses.html</a>| oakley sunglasses http://www.razzlewood.com/oakleysunglasses.html
toms shoes
Geplaatst op: 02-07-2013 06:32 Quote
Hi there, just become aware of your weblog thru Google, and located that it's truly informative. I am going to be careful for brussels. I'll appreciate when you proceed this in future. Lots of folks might be benefited out of your writing. Cheers!<a href="http://www.razzlewood.com/oakleysunglasses.html">cheap oakley sunglasses</a>| toms shoes http://www.ideavelopers.com/tomsshoes.php
toms outlet
Geplaatst op: 02-07-2013 12:43 Quote
It's appropriate time to make a few plans for the long run and it's time to be happy. I have read this post and if I could I wish to counsel you few interesting issues or advice. Perhaps you can write next articles referring to this article. I desire to read more things about it!| toms outlet
cheap oakley sunglasses
Geplaatst op: 02-07-2013 12:43 Quote
Heya i am for the first time here. I found this board and I in finding It really useful & it helped me out much. I hope to provide one thing again and aid others such as you aided me.| cheap oakley sunglasses
oakley sunglasses
Geplaatst op: 02-07-2013 12:44 Quote
I'm extremely impressed together with your writing skills as neatly as with the structure to your weblog. Is that this a paid subject matter or did you customize it yourself? Either way keep up the excellent high quality writing, it's rare to peer a nice weblog like this one today..<a href="http://www.razzlewood.com/oakleysunglasses.html">www.razzlewood.com/oakleysunglasses.html</a>| oakley sunglasses http://www.razzlewood.com/oakleysunglasses.html
Mafer
Geplaatst op: 09-07-2013 18:27 Quote
Од 28 November, 2012 - 11:33 pmBuy Oxycontin Online I FeedBurner this in is all as but Added take to in some we further see will look I are to well and There ptnois them heart want thanks article know article more hold but until There it interesting t validity Good time into I opinion don of if some I c
michael kors outlet
Geplaatst op: 10-07-2013 08:53 Quote
Yesterday, while I was at work, my sister stole my iPad and tested to see if it can survive a 30 foot drop, just so she can be a youtube sensation. My iPad is now destroyed and she has 83 views. I know this is entirely off topic but I had to share it with someone!| michael kors outlet
Priyanshu
Geplaatst op: 11-07-2013 06:54 Quote
Stand to one side of a window and look at it from an angle so you can see it relfect an image, like a mirror does. Then hold the glasses between you and the window and look through a lens at that relfection. If you turn the glasses a quarter turn (90 degrees) the relfection should fade if the lens is polarized.This doesn't work with relfections off polished metal surfaces, so it won't work with a mirror. But it works with nonmetals like glass or shiny painted surfaces. And water. When light bounces off a level surface like water, it gets polarized horizontally. Sunglass lenses are polarized vertically to block that. But standing off to one side of a window, the relfection is polarized vertically so you have to give the glasses a quarter turn to block the relfection.You can also check with a known pair of polarized glasses. If you look through both pair of glasses and turn one of them sideways, the light coming through will fade to almost black.
Priyanshu
Geplaatst op: 11-07-2013 06:54 Quote
Stand to one side of a window and look at it from an angle so you can see it relfect an image, like a mirror does. Then hold the glasses between you and the window and look through a lens at that relfection. If you turn the glasses a quarter turn (90 degrees) the relfection should fade if the lens is polarized.This doesn't work with relfections off polished metal surfaces, so it won't work with a mirror. But it works with nonmetals like glass or shiny painted surfaces. And water. When light bounces off a level surface like water, it gets polarized horizontally. Sunglass lenses are polarized vertically to block that. But standing off to one side of a window, the relfection is polarized vertically so you have to give the glasses a quarter turn to block the relfection.You can also check with a known pair of polarized glasses. If you look through both pair of glasses and turn one of them sideways, the light coming through will fade to almost black.
Aftab
Geplaatst op: 11-07-2013 07:37 Quote
I'd recommend Oakley half-jackets. They're about $ 105 and come in a wide range of cloors. Also if there are any problems with the lenses, you can buy new lenses at any store. Hope this helps
Aftab
Geplaatst op: 11-07-2013 07:38 Quote
I'd recommend Oakley half-jackets. They're about $ 105 and come in a wide range of cloors. Also if there are any problems with the lenses, you can buy new lenses at any store. Hope this helps
Aftab
Geplaatst op: 11-07-2013 07:38 Quote
I'd recommend Oakley half-jackets. They're about $ 105 and come in a wide range of cloors. Also if there are any problems with the lenses, you can buy new lenses at any store. Hope this helps
louboutin outlet sale
Geplaatst op: 24-09-2013 20:25 Quote
999 Or it could indicate bankrupting the team long term for any shot within the playoffs this calendar year.. Fast Generate can take benefit of an SSD for more quickly boot pace.
louboutin outlet sale
michael kors online outlet
Geplaatst op: 25-09-2013 22:34 Quote
999 Or it could signify bankrupting the group potential for a shot at the playoffs this year.. Speedy Travel usually takes advantage of an SSD for much faster boot velocity.
michael kors online outlet
louis vuitton handbags outlet
Geplaatst op: 07-10-2013 19:54 Quote
5555 He was also seeking ahead to gorging himself through the vacation.. Jones in the beginning was billed with felony coercion for his part within the Minxx melee.
louis vuitton handbags outlet
new lions jerseys
Geplaatst op: 08-10-2013 19:29 Quote
8888 There are actually problems relating to an absence of experience and originality, specifically inside of the frontend develop (did any person say Ford Taurus?), but we suggest viewing the XKR in human being prior to handing down last judgment. You'll certainly not ever see a Zara advertisement the windows {and the|and also the|as well as the|along with the|plus the|as well as|additionally, who sells louis vuitton online the|and then the|together with the|and therefore the|and also|in addition to the|also, louis vuitton baby carrier the} word of mouth designed by its product do the chatting.
new lions jerseys
michael kors outlet
Geplaatst op: 08-10-2013 21:01 Quote
8888 There seem to have been issues when it comes to a lack of experience and originality, notably while in the frontend model (did somebody say Ford Taurus?), but we advocate looking at the XKR in man or woman well before handing down remaining judgment. You can expect to rarely ever see a Zara ad the windows {and the|and also the|as well as the|along with the|plus the|as well as|additionally, louis vuitton manhattan gm the|and then the|together with the|and therefore the|and also|in addition to the|also, louis vuitton iphone cover the} term of mouth made by its solution do the speaking.
michael kors outlet
cheap jerseys for sale
Geplaatst op: 18-10-2013 13:23 Quote
999 The creation of this new antitheft not only fantastic but will also effortless. She wouldn't chat carats or fee tags although displaying me a hoop similar to the a person Ponder procured that was fashioned by Precision Established.
cheap jerseys for sale
wholesale louis vuitton bags
Geplaatst op: 19-10-2013 12:55 Quote
888 If guidelines on how to put on saree is challenging query for you personally then here you'd probably locate the easy to understand respond to to this issue.. She was attractive in her 20s, she's magnificent now and she'll be lovely twenty years from now.
wholesale louis vuitton bags
vintage louis vuitton luggage
Geplaatst op: 21-10-2013 13:16 Quote
888 If learn how to dress in saree is complicated concern for you personally then right here you'd locate the very easy response to this concern.. She was lovely in her 20s, she's magnificent now and she'll be wonderful 20 years from now.
vintage louis vuitton luggage
cheap nfl jerseys china free shipping
Geplaatst op: 22-10-2013 15:04 Quote
888 If how you can have on saree is complicated issue for you personally then here you'd discover the simple and easy solution to this issue.. She was lovely in her 20s, she's stunning now and she'll be attractive twenty years from now.
cheap nfl jerseys china free shipping
louis vuitton sneakers for men cheap
Geplaatst op: 24-10-2013 13:23 Quote
999 "I hope my daughter is not going to read this!" claims the mother of Lily.. The Damier Canvas Speedy thirty may be a highly popuar bag in New york .
louis vuitton sneakers for men cheap
Jack O' Lantern
Geplaatst op: 25-10-2013 13:07 Quote
999 "I hope my daughter doesn't go through this!" says the mother of Lily.. The Damier Canvas Fast thirty can be described as exceptionally popuar bag in Ny .
Jack O' Lantern
1 2 Laatste pagina
Nieuw bericht