Natural Language Semantics
By ai-depot | April 29, 2003
Dealing with natural language and parsing sentences to extract meaning can be tricky. This tutorial explains one way of dealing with the problem using lambda calculus. There are many possible applications of such techniques, including bots that can understand orders.
Written by Max Dennis Luesebrink.
Natural Language Semantics
Introduction
The idea of the article is to introduce you roughly into the world of lingusitics or more precise phrase structures (PS), and then go on with some further assumptions about implementation and their use for bots in tactical shooters.
Every sentence consists of an internal structure which you could model with the phrase structure. It is very similar to a production system; you have rules you apply on an axiom (like L-Systems for example). The base axiom would look like this: S (the root, or in our, case the sentence). The first production rule would be.
(NP = noun phrase, VP = verb phrase)
S -> (NP, VP)
Then you’d have rules for the ‘branches’ like.
NP -> NOUN
VP -> VERB, NP
VERB and NOUN have terminal nodes which could be any word in the lexicon for the apropiate category. In the end you get a tree with the words as terminal nodes, which then are referred as the sentence. For my purposes I need the reverse of that technique, that is I get a given sentence and want to extract its PS. This might be ambigious in some cases but this doesn’t matter in this implementation (or at least that is the general idea :). With the extracted PS and the sentence itself im going to build a function which I call the sense of the sentence.
Figure 1: example for a phrase structure.
Implementation
So the basic idea is that any word is a lambda function - even the terminal nodes [Editor: see this reference]. Each lambda function has in the inner function an empty parameter list. These functions are then composed together to one single lambda function. The composition order depends on the kind of phrase were looking at. A VP for example would apply the verb function on the right NP first. Depending on the type of verb (transitive or intransitive) the aryty may vary.
Example:
Take this as an example sentence ‘llama pick_up ball’. The corresponding PS would look like this (S (NP (NOUN llama)) (VP (VERB pick_up) (NP (NOUN ball)))). Starting with the VP the two involved lambda functions would look like this.
pick_up (VERB)
(lambda (object)
#’(lambda (agent)
#’(lambda () (list (funcall agent)
‘pick_up (funcall object))
)
)
)ball (NOUN)
(lambda () ‘my_beloved_toyball)The composed lambda function would look like this
(lambda (agent) #’(lambda ()
(list (funcall agent) ‘pick_up
(funcall #’(lambda () ‘my_beloved_toy_ball)))
)
)
By applying this technique recursivlely on all the words in the sentence you retrieve the lambda functions which could to be said to be the sense of the sentence. Adjectives are quite similar they are functions over lambda functions yielding the objects which have certain features.
Example:
red ball ball would return all functions which are stored in relation to ball. red then would test whether these functions return symbols which have a property red and return these.
But there may occour more then one adjective for a word and then you might end up in an ambigious or hard to compute construct. Because these adjectives may or may not be commutative.
Example:
light coloured material != coloured light material
Or you might not know which ‘part’ of the object an adjective is referring to.
Example:
good doctor
is this a person whos good at being a doctor?
is this a good person which is a doctor?
Some ideas to deal with this will occur in the end of this text. Since i havent been able to implement that yet. Determiners like ‘a’ or ‘the’ can be used for specifing selection.
Example:
the ball versus a ball
‘the ball’ is refering to a specifinc ball while ‘a ball’ is referring to any ball.
Preprositions are another thing to deal with like ‘up’, ‘on’ ‘in’ and so on. Because I can’t deal with these at the moment in my implementation i chose ‘pick_up’ instead of ‘pick up’. Though that might besolved in a way that some verbs use prepositions as another lambda function.
In the end you have a set of functions. These functions are all executable and thus are able to express what the sentence was about.
Application
As an application for that kind of thing i thought about FPS like Counter Strike were communication is crucial for the team. One thing that bots don’t do really at the moment. And this is one point a lot of people are annoyed about because the bots act dumb and dont do what they are expected to do. The player wants the bots to perform certain actions and develop new strategies or new vocabulary to ‘talk’ to with the bots. This also would help a lot when you use something like the SOMs i presented in the last contest to name the objects a bot has categorized and make him able to connect these things with what i talk about.
Conclusion
My implementation is far from being finished and there will be a lot more problems i haven’t thought of yet and thus not stated here. But i think that the bot game ai is in need of that kind of thing. It bemore fun if you can interact with the bot in that way.
Some thoughts about some problems, solutions and related things:
Adjective problem:
By using semantic nets one might be able to find related categories where an objects falls in or consists of which would give you more functions which might contain the one the user meant.
Ambiguity:
Ambigous sentences should be differable in the element of the sentence in which they are ambigious. If there are more then one ball for example the bot could in return ask which ball you meant if you didn’t specified that with a determiner.
Planning the action and represent facts:
Just execting the function wouldn’t be very helpfull so the idea is to combine it with a planner anda database. The sentences would be seperated in functions which represent facts which then add orchange facts in the database and functions which are actions which then use the planner to executethe action. For more complex actions it might be usefull to combine the planner with a blackboardarchetecture such that a bot who can’t execture an action in the planner himself would ‘ask’for help and keep the plan as is is replaceing the action with a query of that action.
Bot-Bot communication:
Bot to bot communication is something else which would make sense to provide a somewhat morerealistic feeling of a tactical unit. An example for that would be a bot calling additionalfirepower or a medic.
There is a lot of more stuff you could think of related to that and i defenetly think that this would make games like this more fun.
Since my code is not finished yet it isnt commented and very unstructured patchy work form the PAIP NLP source and my own. But for the braves of you i attached it to the article.
References
books:
- Semantics in gernerative grammar by Irene Heim & Angelika Kratzer
- Paradigms of artificial intelligence programming by Peter Norvig
links:
realated:
- case frames
- theta theory
Written by Max Dennis Luesebrink.
Tags: none
Category: tutorial |
