Nieuwskanaal voor: Garfixia

The problem with proper nouns

Sat, 19 May 2012 09:37:54 +0200

Before a sentence is passed to the parser, it is first run through the lexer. The lexer divides the sentence into words or word groups. These are called lexical items and they are the smallest parts of the sentence that have a single part-of-speech. Most lexical items can be looked up in the lexicon. But what about proper nouns?

Proper nouns (or more exactly: proper names), lexical items like "Sandra", "Peter R. de Vries" and "Ramachandra" are not part of the lexicon (dictionary). Therefore they will not be recognized simply by doing a lexicon lookup.

Still, you may be able to recognize some of them by looking them up in a knowledge base.

When was Lord Byron born?

The name "Lord Byron" may be looked up and form a single lexical item with the part-of-speech "proper noun".

[when, was, Lord Byron, born]

But this sentence is different:

My name is Jan de Vries.

The name of the conversation partner cannot be looked up. And this is only logical, because the purpose of the sentence is introduction. And I mean that in two ways: the person introduces himself. And at the same time a new lexical item, "Jan de Vries", is introduced in the mental lexicon of the agent.

How can a lexer recognize a new proper noun when it encounters one? I can think of two ways:

1. The words in the sentence that are not part of the lexicon form the new proper noun.
2. Proper nouns may be recognized because they follow certain patterns.

The first method is simple and applies to all names. However, it runs into several problems.

For example:

My name is Jan de Vries.

[my, name, is, Jan, de, Vries]

Since "de" is a word in the lexicon, are "Jan" and "Vries" to be separated into two separate proper nouns? No, because we want to end up with single lexical item. So we may want to take all words in between the unknown words as well. However, which words should we include and which words should we not?

My name is Jan and I like Sandra.

[my, name, is, Jan and I like Sandra]

Why can "Jan and I like Sandra" not be a proper noun? Because it is too long? What about

My Name is Johannes Hubertus van der Laak.

It contains just as many words.

That brings us to the second option: patterns.

The pattern for "Jan de Vries" is

"Ul+ de Ul+" (Ul+ = upper case letter followed by one or more lower case letters)

and the pattern for "Johannes Hubertus van der Laak" is

"Ul+ Ul+ van der Ul+"

Why require the capitals? People often leave them out, don't they? Yes they do. However, if the restriction on capital letters is dropped, the following sentence

john mills the grain.

would be lexed as

[john mills, the, grain]

and this cannot be parsed.

Remember, the lexer has no knowledge of the syntactic structure of the sentence. If the lexer was integrated in the parser, it might be more flexible and offer different possible interpretations. However, this makes the parsing process more complicated and computationally expensive.

References

Wikipedia: proper noun

Answering questions by means of Natural Language Processing

Mon, 30 Apr 2012 10:07:06 +0200

In the past year I have been working on a framework to allow users to interact with a knowledge base through written natural language. The goal is to provide a simple library that allows you to ask a question in plain english (or some other language) and receive a complete sentence for an answer. I do this in the sparse hours of free time that I have, so the project is a long way from being finished. However, I have now reached the point where the program can make a full round-trip from question to answer for a single question. This is a good moment to write about the choices I made and to explain the process.

There are many ways to process a sentence. I am going to describe the one I chose. I am still in the middle of all this, so don't expect a finished product. I wrote it to explain the big picture.

In this article I will take the following question as an example.

How many children had Lord Byron?

Follow the article to find out the answer :)

Understanding

Extract words

In the first step the words of the sentence are extracted. I have not found any use for punctuation marks at present so we can discard them. Whether a sentence is a question or a statement will be deduced from the structure of the sentence.

The product of this step is this:

[How, many, children, had, Lord, Byron]

Group lexical items

In the next step words that go together are aggregated into lexical items. The goal of this step is to find the smallest possible groups of words that still have a single part-of-speech (noun, verb, determiner, preposition, etc.). This way, compounds like "barbed wire" are now considered to be a single item. I also use this step to find proper nouns (i.e. the names of people, like "Lord Byron"). The words that are found in the lexicon are lowercased, the words that are suspected to be proper nouns are left unchanged (since there is no use to lowercase them, and I would need to uppercase them again in the production phase). This step produces this array of words:

[how, many, children, had, Lord Byron]

Parse the words to form a phrase specification

This is a big step. It is based on section 11.5 of the book "Speech and language processing" (Jurafsky & Martin) which describes parsing with unification constraints. In this step a syntax tree is created based on the array of words we just found, and a set of production rules like these:

S => WhNP VP NP             (how many children had Lord Byron)
WhNP => whwordNP NP         (how many children)
NP => determiner noun       (many children)
VP => verb                  (had)
NP => propernoun            (Lord Byron)

The parsing grammar has more rules, but these are the ones needed to parse our sentence.

Four choices were made at this point. I decided to go for Phrase Structure Grammar, not some other grammar, mainly because the books I happened to read treated this type of grammar much more extensively. Other grammars may work equally well, or even better, though. I chose the Earley parser, because it was said to have the best time efficiency. I have not compared it to other parsers, and those might be better in some instances.

This tree represents the syntactic aspect of the parse. It does not show the features that are attached to each of the syntax tree nodes. These features provide both extra syntactic and semantic information. At the same time the sentence is parsed into a parse tree, the feature structures that are bound to each of the words in the sentence are propagated up the tree via unification with the feature structures of the production rules.

The third choice I made was to integrate semantic parsing with syntactic parsing. I did this because I figured that producing multiple resulting parse trees was not really very useful. It is a neat feat, but it is not important for my project. One would still need to chose one tree over the other in order to answer the question in the best possible way. So why not try to find the best tree immediately, and leave it at that? Adding semantic constraints to the parse process helps eliminate ambiguous trees, and I needed semantics anyway. So my strategy is to add as many constraints to the parse as I can, and consequently pick the first parse tree that comes out.

I would like to explain to you the incredible power of feature structures in a single paragraph, but I'm afraid that's impossible. See chapter 11 of Jurafsky & Martin for an extensive explanation. I added feature structures to each of the production rules, like this one:

array(
    array('cat' => 'S',
             'features' => array('head-1' => array('sentenceType' => 'wh-non-subject-question', 'voice' => 'active'))),
    array('cat' => 'WhNP',
             'features' => array('head' => array('sem-1' => null))),
    array('cat' => 'VP',
             'features' => array('head-1' => array('agreement-1' => null, 'sem-1' => array('arg1{sem-2}' => null)))),
array('cat' => 'NP',
            'features' => array('head' => array('agreement-1' => null, 'sem-2' => null))),
),

You will recognize the production rule (S => WhNP VP NP) when you look at the 'cat' attributes. The array above can be represented like this:

It really is as complicated as it looks. Feature structures are not simple. They form a different programming paradigm and require some time to learn. In the feature structure above, S shares all features of VP, via the head node. This means that the VP is the base node of the structure and the S inherits all of it, including its sem (semantics). You can also see that NP and VP (via S) share agreement. That is, NP and VP should have the same person and number. This makes it impossible that the sentence "How many children has we?" will pass. Finally, you can see that NP forms the first argument (arg1) of the predicate expressed by VP.

Now the feature structrures of the constituents WhNP, VP, and NP, are unified with the feature structure of the top level production rule above, and at the same time the sentence's semantics bubbles up from bottom to top.

Semantics starts at the lowest level, where each word in the language has a feature structure attached to it. Here's an example for the verb 'had' that is used in our example sentence:

'had' => array(
    'verb' => array(
        'features' => array(
            'head' => array(
                'tense' => 'past',
                'sem' => array('predicate' => '*have'),
            ),
        ),
    ),
)

Parsing the sentence creates the following unified feature structure which we will call a phrase specification.

Array
(
    [head] => Array
        (
            [sem] => Array
                (
                    [predicate] => *have
                    [arg1] => Array
                        (
                            [name] => Lord Byron
                        )
                    [arg2] => Array
                        (
                            [category] => *child
                            [determiner] => *many
                            [question] => *extent
                        )
                )

            [tense] => past
            [sentenceType] => wh-non-subject-question
            [voice] => active
            [agreement] => Array
                (
                    [number] => s
                    [person] => 3
                )
        )
)

In this specification you see the sem (semantics) part that describes the predicate and its arguments. All three of them are objects that have attributes. The arg2 object contains an unknown, a variable, that is the root of the fact that this sentence is, in fact, a question. Next to these semantic aspects there are syntactic aspects, like tense and voice.

This allows me to explain the fourth choice I made: I don't create a logical representation of the sentence, but a syntactic-semantic representation, which is called a phrase specification. And this type of structure is used moreoften in language generation than in language understanding. I found the best descriptions of it in the book "Building natural language generation systems" (Reiter & Dale). This structure, which is a combination of syntactic and semantic features, keeps intact the structure of the sentence(!) and saves information about tense, voice, etc. This is all done to make it easier to create the answer, as we will see later on. But first we need to find the actual answer.

Finding the answer

Turn the phrase specification into a knowledge base representation

Now that we have the question, we need to find the answer. Luckily, these days you can find many Open Data knowledge bases on the internet that have publicly, and even free, accessible interfaces! I used one of them which I will not disclose at this point. It has a SPARQL interface. So I wrote a function that turns the phrase specification above into a SPARQL query:

SELECT COUNT(?id151) WHERE {
    ?id193 <http://some_enormous_database.net/object/child> ?id151 .
    ?id193 rdfs:label 'Lord Byron'@en
}

This knowledge base returns a data structure that tells me that the answer is:

The children were called Ada and Allegra [1].

Would it have been easier to turn our question into a SPARQL query if the representation had been a set of logical propositions? Probably not. You see, there are many ways to represent semantic information. For a simple example, the relation child(x, y) could have been represented as father(y, x). Other representations are even more different. So there will always be a conversion step between our way of representing relations and the way the knowledge base represents relations, except in the case that you write your parser uniquely for this specific knowledge base. I wanted to write a more generic framework that allowed the use different knowledge bases.

Generation

Integrate the answer into the phrase specification of the question

I would like to have the language processor give me the answer in a full sentence. We start by filling in the the answer that the knowledge base gave us into the phrase specification:

Array
(
    [head] => Array
        (
            [sem] => Array
                (
                    [predicate] => *have
                    [arg1] => Array
                        (
                            [name] => Lord Byron
                        )
                    [arg2] => Array
                        (
                            [category] => *child
                            [determiner] => 2
                        )
                )

            [tense] => past
            [sentenceType] => declarative
            [voice] => active
        )
)

We modify the existing phrase specification, and fill the variable. Then we change the sentenceType from question to declarative and we're done. This is important. We don't need to think of a sentence structure to express the knowledge we have. It's already there. It's like performing Jiu jitsu on the question: use its own strength against it.

Generate a sequence of lexical items from this phrase specification

Now we need to go the opposite way. We need to create a string of words from a tree structure. That seems easy. Just use the same production rules in the reverse order. Unfortunately it is not that simple. The production rules can be used, but the feature structures need to change. I found two reasons for this:

Generation is not a search process. If you don't specify which rules to use for generation, the processor will try many possible paths that will fail. This is a big waste of time!
Many feature structures used for understanding just pass meaning up to the node above. If this process is reversed the meaning stays the same, and this will cause an infinite loop for recursive rules like NP => NP PP.

The essential difference between understanding and generation is:

"Understanding is about hypotheses management, while generation is about choice."

(free, after Speech and Language processing, p. 766)

Generation is a process of hierarchical choices: each choice is based on a part of the phrase specification. Let's start at the top. I will show you the top-level production rule I use to generate the answer to the question:

array(
    'condition' => array('head' => array('sentenceType' => 'declarative', 'voice' => 'active')),
    'rule' => array(
        array('cat' => 'S', 'features' => array('head' => array('tense-1' => null,
            'sem' => array('predicate-1' => null, 'arg1-1' => null, 'arg2-1' => null)))),
        array('cat' => 'NP', 'features' => array('head' => array('agreement-2' => null, 'tense-1' => null,
            'sem{arg1-1}' => null))),
        array('cat' => 'VP', 'features' => array('head' => array('agreement-2' => null, 'tense-1' => null,
            'sem' => array('predicate-1' => null)))),
        array('cat' => 'NP', 'features' => array('head' => array('sem{arg2-1}' => null))),
    ),
),

The structure has two parts: a condition, and a rule. Only if the condition matches, when it is unified with the partial phrase specification, the rule is used to generate part of the syntax tree. The feature structure is different from the rule we saw earlier: it makes sure that meaning is distributed over the consequents. Generation is a recursive process, like understanding. First the S node is matched to the rule I just mentioned and the top-level phrase specification is unified with the feature structure of the rule. Then the process is repeated for the NP, VP and NP. And so on, until the lexical items are found.

While the understanding rules are ordered by frequency of occurrance, generation rules are ordered by decreasing specificity. The top ones have more conditions.

The result of this process is an array of lexical items:

[Lord Byron, had, 2, children]

Punctuation and capitalization

To form a proper sentence, it should start with a capital letter (which it already had in our example) and end with a period:

Lord Byron had 2 children.

That's what we wanted to hear :)

Books

The material above I found in these books. The books allow many alternative routes to follow, none of which are worked out to a great extent. After you read them, you will have some idea where to go, however.

Speech and language processing, Daniel Jurafsky & James H. Martin (2000)
Building natural language generation systems, Ehud Reiter and Robert Dale (2000)

Change syntax rules to facilitate semantics?

Sat, 31 Mar 2012 23:20:30 +0200

It may be useful to change the way phrase structure rules are built when dealing with semantics analysis and production.

The sentence

Lord Byron was influenced by the author of Paradise Lost

is usually parsed like this:

(thanks to phpSyntaxTree for the image)

But when analyzing the semantics of the sentence, it is somewhat awkward.

predicate: influenced
first argument: the author of Paradise Lost
second argument: Lord Byron

(It is a passive sentence, subject and object are reversed.) The related semantic parts are distributed over the sentence.

When generating the sentence from the semantic specification, this becomes even more complicated.

Things can be made easier by just changing the phrase structure rules:

This may make Chomsky frown, but it works perfectly well for both parsing and generating. The predicate and its two arguments can be rewritten using the same rule. In passive sentences, the word "by" is not just another preposition, it is a structural part of the passivization of the sentence. All passive sentences (that name the agent of the action) have it.

Auxiliaries

Sat, 31 Mar 2012 23:20:38 +0200

When I add production rules I only create the ones I really need for the moment. However, I want to create them in such a way that future extensions will be easy to make. So I decided to make a little study of the structure of auxiliaries. The table below is the result of that.

A typical natural language production rule looks like this:

S => NP VP

for a declarative language, or

S => aux NP VP

for a question.

S = sentence, NP = noun phrase, VP = verb phrase, aux = auxiliary.

In this case aux is rewritten by a single word: did, can, or will. When I tried to parse more complicated sentences I stumbled over the fact that the aux part was not a simple part-of-speech, but rather a phrase on its own; it can consist of multiple words.

Be careful when using this table: I am not a language specialist. Just a programmer. Although I tried very hard not to make mistakes, some combinations of grammatical categories seemed far fetched (i.e. "John used to be being bitten by a dog") and I had to use Google to find out if such a combination is being used at all. And even though I didn't add sentences I could not find via Google, some of them were very rare and may have been errors by the users of the language.

Auxiliaries
Mood	Voice	Aspect	Nonmodal	Modal
declarative	active	simple simple, progressive perfect perfect, progressive habitual habitual, progressive prospective prospective, progressive	A dog bites John. A dog is biting John. A dog has bitten John. A dog has been biting John. A dog used to bite John. A dog used to be biting John. A dog is going to bite John. A dog is going to be biting John.	A dog may bite John. A dog may be biting John. A dog may have bitten John. A dog may have been biting John. A dog may have used to bite John. A dog may have used to be biting John. A dog may be going to bite John. A dog may be going to be biting John.
declarative	passive	simple simple, progressive perfect perfect, progressive habitual habitual, progressive prospective prospective, progressive	John is bitten by a dog. John is being bitten by a dog. John has been bitten by a dog. John has been being bitten by a dog. John used to be bitten by a dog. John used to be being bitten by a dog. John is going to have been bitten by a dog. John is going to have been being bitten by a dog.	John may be bitten by a dog. John may be being bitten by a dog. John may have been bitten by a dog. John may have been being bitten by a dog. John may used to be bitten by a dog. John may used to be being bitten by a dog. John may be going to have been bitten by a dog. John may be going to have been being bitten by a dog.
interrogative	active	simple simple, progressive perfect perfect, progressive habitual habitual, progressive prospective prospective, progressive	Does a dog bite John? Is a dog biting John? Has a dog bitten John? Has a dog been biting John? Did a dog used to bite John? Did a dog used to be biting John? Is a dog going to bite John? Is a dog going to be biting John?	Can a dog bite John? Can a dog be biting John? Can a dog have bitten John? Can a dog have been biting John? Can a dog have used to bite John? Can a dog have used to be biting John? Can a dog be going to bite John? Can a dog be going to be biting John?
interrogative	passive	simple simple, progressive perfect perfect, progressive habitual habitual, progressive prospective prospective, progressive	Is John bitten by a dog? Is John being bitten by a dog? Has John been bitten by a dog? Has John been being bitten by a dog? Did John used to be bitten by a dog? Did John used to be being bitten by a dog? Is John going to have been bitten by a dog? Is John going to have been being bitten by a dog?	Can John be bitten by a dog? Can John be being bitten by a dog? Can John have been bitten by a dog? Can John have been being bitten by a dog? Can John have used to be bitten by a dog? Can John have used to be being bitten by a dog? Can John be going to have been bitten by a dog? Can John be going to have been being bitten by a dog?

Legend

For each color used, I give an example and the meaning of the word group.

bites = simple present (verb form)
biting = present participle (verb form)
bitten = past participle (verb form)
bite = infinitive (verb form)
could = modal auxilliary
is going to = primary auxiliary (italic = modify for tense, person, number)

Verb forms

A verb has different forms, and these are important with respect to these sentences.
Possible values: simple present, simple past, present participle, past participle, infinitive
Reference: Participle - Chomp chomp, Word forms (simple, participle, infinitive) - English Club

Grammatical categories

The auxiliaries in the table have been grouped by grammatical category combination. Some of these categories were new to me too, so it is probably a good idea that I explain them. And while I'm at it, I may as well name the link with their semantic counterparts.

Mood

The mood of a sentence is the main structure, and is represented by a production rule with S at the left hand.
Typical values: declarative (statement), interrogative (question), imperative (demand)
Meaning: the mood determines the speakers attitude toward that what they are saying.
Reference: Grammatical mood - Wikipedia

Voice

In which position do we find the agent of the sentence? In the subject position (active) or in the direct object position (passive)
Typical values: passive, active
Meaning: the subject position determines the focus of the sentence
Reference: Grammatical voice - Wikipedia, Examples of active and passive voice - Helping hands

Tense

When did the event or state in the sentence occur? Or: temporally when.
Typical values: past, present and future
Meaning: tense determines the time of the event, relative to the present moment
Reference: Grammatical tense - Wikipedia, Perfect tense - Wikipedia

Aspect

The the internal temporal constituency of a situation. Or: temporally how.
Typical values: simple (happens now, "a dog bites john"), progressive (ongoing: "a dog is biting John"), perfect (completed event, "a dog has bitten John"), habitual (customary, "a dog used to bit John"), prospective (future, "a dog is going to bite")
Meaning: aspect is a specification of the tense aspect, and determines the period of time within the range specified by tense
Reference: Grammatical aspect - Wikipedia

Modality

The proposition the speaker wishes to make with respect to the
Typical values: can, will, must
Meaning: will specifies that the event takes place in the future, can specifies that the event is possible, not certain, must specifies that the event is required.
Reference: Linguistic modality - Wikipedia

Conclusive remarks

When creating production rules, remember that these sentences may need to be negated as well ("John may not have been bitten by a dog"). Further, in the examples I have only used the present tense, using the third person, in the singular. An example of a first person, plural (a dog => we), past tense (bites => bit) sentence would be:

We bit John

I formatted all words that need to change to account for these three grammatical categories in italic.

Implementation of an Earley parser with unification

Sat, 31 Mar 2012 23:20:46 +0200

I just completed a PHP implementation of the Earley parser, extended with unification, that is described in the book "Speech and Language Processing" by Jurafsky and Martin. I thought it might be a good idea to share my code since it took me quite some time and effort to create it and, what's more important, I could not find any other implementation of it on the internet.

The Earley algorithm is a top-down chart parser that parses natural language and does this very efficiently. Given a grammar that contains syntax rules and the words of a language, it parses a sentence into all possible syntax trees. The unification extension adds further restrictions to the syntax rules. An example of such a restriction is that the rule S => NP VP only applies if the number and person of the NP agrees with that of the VP. When NP is "The children", then the VP may be "are playing", but cannot be "is playing" (a restriction on number) or "am playing" (a restriction on person). The grammar should provide extra feature structures for the syntax rules. The unification extension of the Earley parser applies these structures and ensures that a sentence with a feature error will not be parsed.

I just provide the code to give you some idea and hints on to implement it. The code has not been tested very much since I just finished it. I place it under MIT license.

Earley parser source code

The algorithm may be found in the book "Speech and language Processing" (first edition), chapter 11, page 431. In the second edition of the book the algorithm may be found in chapter 15. The rest of this article presumes you have read it, since I cannot quickly repeat all the information given in chapter 11.

The book first describes the basic Earley algorithm, which can be found on Wikipedia. Some implementations are available there as well. It is described in chapter 10 of the book but can be hard to really understand it, because of the undescriptive use of variable names like A and B, and that it uses two functions that are not specified, NEXT-CAT and PARTS-OF-SPEECH.

Syntax rules and feature structures

For the basic algorithm I use syntax rules like the following S => NP VP

array(
    array('cat' => 'S'),
    array('cat' => 'NP'),
    array('cat' => 'VP'),
),

The same rule, extended with feature structures looks like this:

array(
    array('cat' => 'S', 'features' => array('head-1' => null)),
    array('cat' => 'NP', 'features' => array('head' => array('agreement-2' => null))),
    array('cat' => 'VP', 'features' => array('head-1' => array('agreement-2' => null))),
),

This implements the feature structure that is described on page 428 of the book:

Features of the implementation

The implementation of the algorithm handles unification for syntax rules like this,

VP => NP NP

as described on the bottom of page 406. The rule as two identical consequents. If the grammatical categories of the rule are implemented as keys in a hashtable (as they are in my code) then they need to be discerned. I do that by adding the position of the category in the rule.

The book says: VP => NP(1) NP(2)

in the implementation it looks like this: VP@0 => NP@1 NP@2 (but you don't need to think about this when you write the syntax rules)

It also deals with rules like this NP => NP PP where one consequent is identical to the antecedent.

Remarks on the algorithm

The meaning of the function "FOLLOW-PATH" is not described in the book, but I presume that it means that it returns a subset of its argument. It starts out with the label "cat" and follows it to the end.

The function "UNIFY-STATES" of the original algorithm performed a "FOLLOW-PATH" of "dag2". I think this is an error in the algorithm, because it would corrupt the feature set of the charted state.

My version of unifyStates is also somewhat different since I take into account that a rule may have the same category at different positions (as in the VP => NP NP example).

Labeled DAGs

Unifying DAGs is a very elegant to implement unification. I could not follow the explanation of the unification process as described on page 423, unfortunately. That's why I decided to create a different implementation of this function. I introduced a class to separate the logic of the datastructure: LabeledDAG, a labeled directed acyclic graph (or DAG). Which reminds me to thank my employer at Procurios, Bert Slagter, for inadvertently providing me with a perfect datastructure for this task.

Finally

I also added the possibility to stop parsing when the first complete sentence is found. For some applications you are only interested in a single interpretation; it might as well be the first one, especially if you succeed to order your syntax rules in such a way that the best interpretation is found first.

Geld naar Wikipedia

Wed, 23 Nov 2011 20:49:36 +0100

Ik heb maar eens wat geld overgemaakt naar Wikipedia. Waarom niet? Het is een briljant concept met een geweldige uitwerking en ik hoop dat het nog lang mag bestaan.

Sense and reference in an NLP parser

Sun, 18 Sep 2011 21:15:12 +0200

Consider this short story.

George Bush was lazy. When I called him he just ignored me. But when I was sad he always comforted me. Gosh, I loved that cat.

It is tempting to resolve an obvious reference directly. So when the name "George Bush" comes along you look up entity by that name in the knowledge base and directly attach the new statement to it.

But when we continue the story, the former president of the US of A will have an even stranger predicate attached:

This is obviously a bad idea. So what we need to do is create a temporary object within our context of discourse to which we add the predicates and to which we add the most likely external reference:

This implementation reminds me of the distinction between sense and reference. The reference of a word is the object it denotes in the world. The sense of a word is the cognitive representation of the object in an agent. In our case both sense and reference are representations. But one of them, reference, is more absolute. The sense of a word is here an object in working memory whereas the reference of a word is an object in long term memory.

Now when the last sentence is parsed, we will drop the external reference when we find out we are in error (how we do this is another story). The temporary object can later be added as a new entry to our knowledge base. A second entry with the name George Bush.

Naming a cat after George Bush is not as unlikely as it may seem. George Bush loves cats. And no, we don't call George Bush a cat. We're not hippies.

I am reading "Linguistic Semantics" by William Frawley. A wonderful book full of new ideas.

Semantic analysis: predicates and arguments

Tue, 06 Sep 2011 21:16:53 +0200

One of the things that is needed for the semantic analysis of a sentence is the extraction of its predicates and their arguments. When I was trying to find out how to do this, I came by several linguistic techniques that are involved in this task. I thought it might be interesting for you to see what's available in this field. It was certainly interesting to me and it even made me understand some of the stuff that always troubled me in high school :)

Introduction

Let's start with an example. Take this simple sentence:

John Milton wrote Paradise Lost.

Using predicate logic we can write this sentence as follows:

write(john-milton, paradise-lost)

This representation of the sentence has the advantage that it can be stored easily in a relational database. Note that the paste tense has been lost in this representation. Also note that the token 'john-milton' is a constant that represents that which is named "John Milton" in the english sentence. And finally notice that 'write' has two arguments (or variables): the first one is assigned to john-milton, the second to paradise-lost. At this point it is not clear why there are two arguments and not three or four. Also it is not clear why john-milton needs to be in the first position and paradise-lost in the second.

But the actual sentence I want to be able to parse is:

John Milton wrote Paradise Lost in the sixteen fifties.

The sentence is true. Many scholars guess the epic poem is written in London around 1650-1660.

Syntactically, this sentence looks like this:

S
+-- NP
|   +-- noun: John Milton
|
+-- VP
    +-- verb: wrote
    +-- NP
        +-- NP
        |   +-- noun: Paradise Lost
        |
        +-- PP
            +-- preposition: in
            +-- NP
                +-- determiner: the
                +-- noun: sixteen fifties

This sentence doesn't fit predicate logic well, because we cannot simply add extra first-order sentences to represent the extra information ("in the sixteen fifties").

But let's try anyway:

write(john-milton, paradise-lost, decade-1650)

This looks good, but what would the following sentence look like?

John Milton wrote Paradise Lost in London.

write(john-milton, paradise-lost, london)

No that can't be right because that is the position where time used to be.

Predicate logic

A representation that solves this problem is like this:

isa(e, writing)
writer(e, john-milton)
writee(e, paradise-lost)
time(e, decade-1650)

As you can see an extra constant 'e' (for event) is introduced to link the different sentences together. But that's not all: along with e comes the constant 'writing', and the predicates 'isa', 'writer', 'writing', and 'time'.

What happens here is that the single predicate 'write' is split up and the concept of role is introduced. Each of the arguments of the predicate gets its own role and each of these roles is given a predicate. For example, argument 1 in the original predicate of 'write' now has the role of 'writer' and argument 2 has the role of 'writee'. By naming the roles explicitly rather than implictly it is possible to extend them arbitrarily. We can now add both 'time' and 'place' as extra roles.

However, calling these roles 'writer' and 'writee' is suboptimal. These roles can only be used in relation to the predicate 'write'. Whereas the role 'time' can be used to compare very different types of events, the role of 'writer' can only be used in the context of writing. Changing this role to 'agent' would generalize it and allows it to be used in a survey of all events in which a given person was the agent, for example. And the fact that the person is a writer can still be deducted from the fact that he or she is the agent in the event of 'writing'.

If we follow this reasoning, we end up with:

isa(e, writing)
agent(e, john-milton)
patient(e, paradise-lost)
time(e, decade-1650)

The question arises what this finite set of roles can be.

Scholastic semantic analysis

In school we are taught that a sentence can be analysed in two ways: syntactically (in Dutch: taalkundige analyse) and semantically (redekundige analyse). Semantic analysis labels the parts of the sentence as 'subject', 'predicate', 'object', 'complement', and 'adjunct'.

Our sentence is analysed as:

subject: john-milton
predicate: write
object: paradise-lost
adjunct: decade-1650

This analysis produces general roles for the arguments in the sentence (subject, predicate, etc.). Several refinements of the roles are discerned, like 'infinitive' and 'indirect object' These roles keep very close to the surface form, however. This is especially true for passive sentences like:

Paradise Lost was written by John Milton in the sixteen fifties.

That produces paradise-lost as the subject and john-milton as the object.

subject: paradise-lost
predicate: write
object: john-milton
adjunct: decade-1650

This is not very useful for our purpose. We want the roles to say something about the objects in the sentence, not about their form or their place in the sentence.

Grammatical case

Using grammatical case (in Dutch: naamvallen), the roles of arguments are expressed in a sentence through various forms. To express the fact that the book was written in London, we use the preposition 'in'. This is the locative case. The English language also uses word position to mark case. The subject of a sentence is placed first and denotes the nominative case. The direct object is placed second and denotes the accusative case.

nominative: john-milton
accusative: paradise-lost
locative: london

I wanted to add the right case of 'decade-1650', and what I found was 'accusative of duration of time'. This result is a little meagre if you ask me.

Theta roles

Theta roles are syntactic in nature. They describe the number and type of the arguments of a verb. The number of theta roles of a verb is fixed. So this formalism stays quite close to the orginal predicate logic expression, except that it 'names' the arguments. An example will make this clear:

write(agent: john-milton, theme: paradise-lost)

Only 'required' arguments are used as theta roles. So the adjunct 'in the sixteen fifties' cannot be represented. It is not considered to be part of the argument structure of the verb.

Thematic relations

Thematic relations are similar to theta roles, but their intention is semantic rather than syntactic. They assign roles to adjuncts ('in the sixteen fifties').

A list of the most important thematic relations is:

Agent
Experiencer
Theme
Patient
Instrument
Force
Location
Direction
Recipient
Source
Time
Beneficiary
Manner
Purpose
Cause

In our example this would make:

predicate: write
agent: john-milton
patient: paradise-lost
time: decade-1650

Summary and conclusion

Some things to take away:

A simple sentence has a single predicate and some arguments
There are required and optional arguments. The optional ones are not always considered 'real'
There are restrictions to the contents of an argument in a given role
The role of the arguments with respect to the predicate
How do you recognize different roles in a sentence?
There are different predicates with the same name, i.e., write(a, b), write(a, b, c)

I really like thematic relations. They give me the feeling of being 'right', so I will go with them.

Review: Les enfants de la salamandre

Sat, 20 Aug 2011 20:22:14 +0200

I read these three comic book albums some 20 years ago. They are absolutely fantastic. They contain very passionate and violent images, combined with some scenes of kindness and affection that stand out by comparison. Esotheric and biblical elements are located in the roughness of southwesternern USA.

The story is based very strongly on a poem by Rainer Maria Rilke and gives it a completely new dimension. The same is done with a song of Laurie Anderson. These techniques are woven into the story so naturally that it awakens a strong sense of fascination.

What I will do here is analyze the work as much as my limited mind can handle and add some links to informational places on the internet.

Editions

The series contains three books: Angie, Arkadin and Alicia. The first two albums I read were published as part of the series "Collectie Pilote", by Dargaud, in 1988 and 1989, in Dutch. The series was called "De kinderen van de salamander". "Alicia" was never added to this collection and I found a copy of an edition published by Novedi (in 1990). Glénat published the series in French as a single volume in 1997. At Amazon. Blitz published it in Dutch.

Story

The story is very intense. It describes the lives of three young adults, the "children of the salamander", that are the living actors in the eschatology (ideas about the end of the world) of an obscure book. Their goal is to meet each other. The storyline is highly complex and braids the lives of the main characters both chronologically and in flashbacks.

Scene from Angie

Main characters

The children of the salamander

Angie, Arkadin and Alicia are the children of the salamander. When they are aroused too much, they produce some kind of electric current that destroys things and people around them (the "sign of the salamander"). They fear the sound of nails pounding in wood since it "reminds them of the suffering of their lord" (Alicia, p18). They have a special connection with old car wrecks and can see the "lost legends" in the form of a conquistador skeleton riding a horse (Francisco Vásquez de Coronado, conqueror of the indians of the southwestern United States).

Angie

(The name means angel) Angie enters the world as he breaks out of a stone angel in a room in hotel Angel Heart. He explains the goal of the children of the salamander like this: "We all come from the same community.Everyone was part of the other, dependent on the other... all coming from the same dream and oblivion. We must fight this oblivion. We must rebuild the images of that dream. So that no sacrifice is in vain." The role of Angie is less explicit. Angie p3 says "Angie and Arkadin. Two sides of the same medal. Their glance filled with the same eternity, The hope of the one against the hatred of the other."

Arkadin

(A rare name, mostly used as surname, is probably chosen after Orson Welles' 1956 movie "Mr. Arkadin", that has in German the subtitle "Der Satan persönlich") He is the evil one of the children of the salamander. He calls Satan his father (Alicia, p27) He is "the beast of the apocalypse, marked by the seal" (Arkadin, p41). He is found by the faceless in hotel SkyRoad. (Alicia p.37) He is able to shift form. He wants Alicia to be destroyed. At the end of Arkadin he grabs Myrvold (of the sect) and continues to live inside his body.

Alicia (Ali)

(The name means 'of noble birth') She enters the world as she rises from the flames of a temple (church), according to the Asgarod. She is raised by brother Leon and sister Clara. Alicia escapes in a process that kills her foster parents (Alicia p21) She then lives with Paddy and works as a librarian. In the library she reads from the Asgarod. She knows the contents of every book in the library, even though she has no recollection of when she has read them. After Angie and Alicia have had sex in an old diner their energies combine (Alicia p26) and parts of their mutual memories return. They remember the gateway they must return to: hotel Skyroad (Alicia, p34)

The community of the salamander

This community consists of people that have come into contact with the children of the salamander: the sect, the "faceless" and the people in the old factory. They are "a people that waits for its saviour and until then is robbed of its strengths." (Alicia, p36)

The sect

A group of people that live by the Asgorad. They wear dark glasses to avoid polluting their sight with the corruption of the world. (Alicia, p12) They worship in temples and these temples contain a statue of a "guide" who has a white complexion and black hair, combed sideways. These statues are destroyed at the beginning of Arkadin, probably as a token to introduce the coming of Arkadin. The people of the sect meet with the faceless to find out where they found Arkadin, because this is the place where children of the salamander need to return to (hotel Skyroad). As soon as they find out out, they kill all the faceless (Alicia, p41)

The "faceless"

This 'special security' team of the "police" always wears motor helmets since their faces are being burned away. It is doubtful wether they are really part of the police force because of their brutal methods. They tortured first Arkadin and later Angie to find out the meaning of their own life (Alicia, p41)

People in the old factory

These people, who only occur in Arkadin, live in an old factory. Their health deteriorates. Their role is to help Alicia and Angie to find their way back to where they belong.

Scene from Arkadin

Asgarod

(The name may be related to the country of the Norse Gods, Asgard) A key element in the story is the fictive book of Asgarod. It is the "holy book that God left Lucifer after his fall" (Alicia, p12). Brother Achab (of the sect) spends his life decyphering (and probably translating) the book and found that it prophesies the coming of the children of the salamander, that they will meet, and that this will cause their mutual destruction. Only after that event, a Messiah will stand up and will save the community of the salamander (Alicia, p.17) The Asgarod is written in a logogrammatic language (in which several people at least have their own character) and it is probably Achab's translation of this work that everyone is reading.

The Asgarod says that the messiah will be sent after the three angels (the children of the salamander) have met and have been destroyed. Yet after this event has taken place, in hotel Skyroad, no messiah has appeared and so brother Achab resumes his studies. After many years he finds the answer to this enigma in a dream. The messiah is here already. (Alicia, p47)

Scene from Alicia

Powerful references

The books mention several explicit references at the end of Angie and Alicia:

Gravity's angel - a song by Laurie Anderson (see below)
"The poem about the children of the salamander is by Rilke" - Actually it is called "Nächtens will ich mit dem Engel reden" (see below)
South West USA (Gerd Kittel, 1986)
Written in the west (Wim Wenders, 1987)
Usines (Jacques Ferrier, 1987)

Gravity's angel - Laurie Anderson:

Nächtens will ich mit dem Engel reden - Rainer Maria Rilke (source) (I hope you will read it, Astrid :)

Nächtens will ich mit dem Engel reden,
ob er meine Augen anerkennt.
Wenn er plötzlich fragte: Schaust du Eden?
Und ich müsste sagen: Eden brennt

Meinen Mund will ich zu ihm erheben,
hart wie einer, welcher nicht begehrt.
Und der Engel spräche: Ahnst du Leben?
Und ich müsste sagen: Leben zehrt

Wenn er jene Freude in mir fände,
die in seinem Geiste ewig wird, -
und er hübe sie in seine Hände,
und ich müsste sagen: Freude irrt

Parsing "Was Ada Lovelace a daughter of Lord Byron?"

Fri, 22 Jul 2011 22:30:55 +0200

For the parser I am trying to write I need a fresh sentence to parse every week or so. This week the sentence is

"Was Ada Lovelace a daughter of Lord Byron?" (I'm using Byron related sentences)

This is a so-called "Yes-No question" and its phrase structure is something like this:

S
+--- aux (was)
+--- NP (proper noun: Ada Lovelace)
+--- NP
+--- NP (determiner: a, noun: daughter)
+--- PP (preposition: of, proper noun: Lord Byron)

Simple, but there is a problem: the books I read on the subjects tell me that a yes-no-question has the structure:

S
+--- aux
+--- NP
+--- VP

So I thought i'd get me an authorative reference on the subject. There is one. It's called "A Comprehensive Grammar of the English Language". But it's expensive ($110.-) So I thought I'd see if I could find a second-hand copy. There weren't any cheap ones. But then I did find a xeroxed version of the book here. Great, now I could lookup if S -> aux NP NP was also allowed.

The reference doesn't say. But it does say that "Again as with negation, main verb BE functions as operator". Where operator equals aux(iliary). But if the word was is the auxilliary then there has to be a main verb as well. Except there isn't! So I guess that the main verb is implicit, and I though what word it could be. First I landed on identified which is close, but does make the sentence flow a little bit awkwardly.

And then it came to me, and that's why I wrote this piece, that the word is being:

"Was Ada Lovelace being a daughter of Lord Byron?"

Which yields:

S
+--- aux (was)
+--- NP (proper noun: Ada Lovelace)
+--- VP
       +--- verb (being)
       +--- NP
              +--- NP (determiner: a, noun: daughter)
              +--- PP (preposition: of, proper noun: Lord Byron)

This is all swell, but my parser doesn't read implicit words. So I will allow the S -> aux NP NP in my parser, and I will let it generate the verb being.

PS: If you are reading this and you know it is nonsense, please let me know (kindly), but you will have to provide a better alternative!