To give an example of the flavour of ATN programming, we will now look at the outline of part of a hypothetical question-answering program using an ATN. To start with, we will deal with simple English declarative sentences; later, we will deal with questions as well. For simplicity, we will ignore tense in this example. The output of the network will be a simple proposition, qualified with the word add or search, according to whether the information is to be added to the system's database (is new information) or is to be searched for in the system's database (has been asked about in a question). We will see later how such a system might actually be implemented.
For this example, we will assume that a proposition can be represented by a sequence consisting of a verb followed by a sequence of names of objects qualified by their syntactic relation to the verb. In a programming language like Pop11, it would be natural to represent these by lists. In this context, we will say that an object can be related to a verb
by acting as its subject (arg0) or object (arg1), or by appearing as the object of some preposition. Thus, for declarative sentences, we wish to produce results such as the following:
Mayumi will see Maria: <add, <see, <arg0,Mayumi>, <arg1,Maria> > > Mayumi will see Maria with Hans: <add, <see, <arg0,Mayumi>, <arg1,Maria>, <with,Hans> > >
Here is a network that will do this.
Name S: Registers PPS, AUXS, MOOD, MAINVERB, ARG0, ARG1 Initial 0 set PPS to the empty sequence, set AUXS to the empty sequence Final 3 return <MOOD,<MAINVERB, <"arg0", ARG0>, <"arg1", ARG1> > ++ PPS> From 0 to 1 by NP set ARG0 to *, set MOOD to "add" From 1 to 2 by V set MAINVERB to * From 2 to 2 by V add MAINVERB to AUXS, set MAINVERB to * From 2 to 3 by NP set ARG1 to * From 2 to 3 by # set ARG1 to the empty sequence From 3 to 3 by PP add * to PPS.
Name NP: Registers RES Initial 0 Final 1 return RES From 0 to 1 by PN set RES to *.
Name PP: Registers PREP, ARG Initial 0 Final 2 return <PREP, ARG> From 0 to 1 by P set PREP to * From 1 to 2 by NP set ARG to *.
PN abbreviates: John, Mary, Susan, Peter, ... . P abbreviates: with, behind, ... . V abbreviates: will, see, ... .
(The operation '++' is concatenation of sequences.)
There are a number of things to note about this network. First of all, to reuse bits of network (with different register assignments), ATN programmers tend to have large networks, rather than lots of small ones. So, there is no VP network here. This has been turned to advantage in the present context, because the translation of the predicate does not come out as a simple constituent of the translation of its sentence. Instead, components of the predicate appear at different points in the analysis of the whole sentence.
Secondly, note how the recognition of verb sequences is done, by the following arcs:
From 1 to 2 by V set MAINVERB to * From 2 to 2 by V add MAINVERB to AUXS set MAINVERB to *
In this application, only the main verb (the last word in the sequence) is used, all the (preceding) auxiliary verbs being ignored (stored in a register AUXS whose value is not subsequently used). Until the last verb is reached, however, it is not known which is the main verb. So, it is arranged that at each moment MAINVERB is the last verb that has been encountered so far. In general, the value of this register will change several times when an input like the following is analyzed:
Mayumi will have seen the play.
and so at times the traversal will be on a correct analysis path but the register will have an incorrect value. One of the techniques used in ATN programming is to put into a register a value that is probably (but not necessarily) correct, and then to change it if it turns out to be wrong. This is effectively a way of postponing a decision on the value - a form of least commitment. An alternative strategy, that of making a blind choice and leaving the search mechanism to rule out all but the correct possibilities, would be encoded as the following non-deterministic fragment:
From 1 to 1 by V add * to AUXS From 1 to 2 by V set MAINVERB to *
The least commitment strategy is often more efficient than making a blind choice, as maintaining alternative hypotheses tends to be expensive in ATN implementations. It relies, however, on the network explicitly noticing when the initial register assignment is wrong (here, when a verb follows a previous sequence of verbs) and there always being enough information in the registers to reconstruct the correct values when this happens.
We can elaborate this network further to deal with simple yes-no questions and to generate outputs such as the following:
Will Mayumi see Maria: <search, <see, <arg0, Mayumi>, <arg1, Maria>>>
In this context, the form of a yes-no question is the same as that of the corresponding statement, except that the first of the sequence of verbs appears at the start of the sentence. It is fairly straightforward to make the network incorporate this generalization, by adding extra arcs:
From 0 to 4 by V set MAINVERB to * From 4 to 2 by NP set ARG0 to *, MOOD to "search"
Note how little of the network has had to change for this. The use of the MOOD register allows large parts of the networks to be shared between statements and yes-no questions, in the same kind of way that the FGENDER register was useful before.
Finally, it would be nice to deal with simple WH questions, like 'Who will Mayumi see?' We will translate them into the same basic form, but with a special symbol, '?', indicating an element that is being asked about, thus:
Who will see Maria: <search, <see, <arg0, ?>, <arg1, Maria>>> Who will Mayumi see: <search, <see, <arg0, Mayumi>, <arg1, ?>>> Who will Mayumi see Maria with: <search, <see, <arg0, Mayumi>, <arg1, Maria>, <with,?>>>
Now these WH questions are identical in form to the word 'who' followed by an ordinary yes-no question, except that somewhere in the yes-no question there is a gap where we would normally expect a noun phrase. This gap corresponds to the position of the item whose identity is being questioned:
Who [? will see Maria] Who [will Mayumi see ?] Who [will Mayumi see Maria with ?]
The first thing we need to do is recognize words like 'who' as forming simple noun phrases. We shall say that 'who' belongs to a category WH of question pronouns. In the event that a noun phrase takes the form of a question pronoun, we shall produce the special value "?" from the NP network:
From 0 to 1 by WH set RES to "?"
Now we need to deal with such a noun phrase appearing at the start of a sentence. We can indicate that such a noun phrase has appeared by assigning a value to a register HOLD. Apart from setting this register, we want to continue as if this was a normal yes-no question:
From 1 to 4 by V ARG0 must be "?" set MAINVERB to *, set HOLD to TRUE
Now we need to cater for the fact that somewhere later in the sentence an expected noun phrase will not appear and that the value "?" is to be used instead of the value returned by the NP network. We could add alternative arcs to this effect wherever a noun phrase is expected, but this would result in many messy changes. It would be much better to add to the NP network, so that if HOLD is TRUE a "?" noun phrase can be appropriately 'hallucinated':
From 0 to 1 by # HOLD must be TRUE set RES to "?", set HOLD to FALSE
The only thing that now needs to be done is to ensure that HOLD is given an appropriate value at the start of a sentence:
Initial 0 ... set HOLD to FALSE
and finally to ensure that we do not allow ourselves to leave the sentence with any unused NPs:
Final 3 ... HOLD must be FALSE
The diagrammatic form of the complete network (with the annotations associated with registers removed) is shown in Figure 3.3.
Something like our HOLD register is a traditional device in ATN programming for dealing with what linguists call 'unbounded dependencies', 'left extraposition', 'leftwards extraction' or 'wh-movement' - where a phrase appears to have been moved leftwards out of its normal position. We should note that, whereas all other registers used so far (apart from '*') have only been used locally within individual networks, HOLD needs to be globally available to all networks. Hence, in ATN systems it is usually implemented by a special mechanism (as is '*').
Send us a comment.