If you're new here, you may want to subscribe to my RSS feed. Thanks for visiting!

“give me a banana”

The first stage is to break this into its component parts and then categorise them. First instinct would be to apply common lexical forms noun, adverb, etc. But to simplify further and because it actually does not matter at this stage I will create my own lexical ‘tokens’ that I will apply to each word.

The tokens are as follows: TYPE, THING, WHO & RUBBISH

Now in my solution it is actually possible to categorise some words into multiple tokens. So banana could be assigned TYPE & THING. But again to keep things simple we will just assign one to one maps.

So for our example: “give me a banana” we have TYPE, WHO, RUBBISH, THING

Now at this point you are starting to think I have completely lost it. But please keep with it there is a reason for all this gibberish.

The next step in translating one form of language into something the computer understands is normally performed with some form of lexicon. This can be done with something like bison in which you produce rules like below.

term: term ASTERISK factor { $$ = * ; }
| term SLASH factor { $$ = / ; }
| factor

When I tried to get my head around writing rules to apply to the English I was trying to translate I kept finding combinations that just didn’t seem to fit. So to turn the problem around I made the computer teach itself. To do this I gave it correct examples of English and incorrect examples and each time I then gave it what was the correct answer to those examples.

To achieve this I let the computer build its own lexicon as it learnt from each of the examples. This translates into a branching tree where each token designates a branch in the tree. So to give an example we have the four following examples.

• give you a banana
• sell me an apple
• give the apple to me
• sell an apple to you

These translate to the following tokens.

• TYPE WHO RUBBISH THING
• TYPE WHO RUBBISH THING
• TYPE RUBBISH THING WHO
• TYPE RUBBISH THING WHO

This is extreme over simplification but the diagram below shows the tree that this would generate.

What we are also missing is the meaning of each of these statements. For the program to make use of the examples it must be assigned a meaning to understand if one statement is actually the same as another but written with different words.

• give you a banana - meaning “I lose a fruit”
• sell me an apple - meaning “I gain a fruit”
• give the apple to me - meaning “I gain a fruit”
• sell an apple to you - meaning “I lose a fruit”

We now rebuild the tree taking into account that the tree should now only have two end points. But in doing so discover that we cannot resolve the set of rules just by applying the tokens. This results in a tree that looks like.

What this means is that we need to break down the tree by one of its parts to make a distinction of one of the tokens. Obviously this is ‘give’ & ’sell’ as they are the only distinguishing differences between ‘I lose a fruit’ and ‘I gain a fruit’. The final result is that we have a tree that is reduced just checking ‘TYPE’ for it being ‘give’ or ’sell’. Although this is the first token in the chain it could have been any part of the string. Below is the final tree structure.

Although this tree is completely worthless for parsing anything other than “give you a banana” I hope it shows that given lots of extra examples the tree can build itself into something that can translate quite complex meanings. Plus on top it is something that can be easily extended when you find a string it does not understand by just teaching it the correct meaning.

Just a quick note on my previous entry about ‘Stratagem’ I have started investigating setting a site on sourceforge but the registration process for a new project is not short. I was also disappointed that ‘Stratagem’ has already been taken so it will have to be registered under another name. The real question will be is anyone be interested in working on it? But only time will tell. I did get a few people asking ‘do you own it’ and the answer is a definite yes.