Send us a comment. The foregoing examples show that certain kinds of outputs, such as sentences in other languages, can be computed from natural language sentences using transducers (PTs) built from RTNs. All the examples do, however, have a kind of family resemblance, in that the order in which items appear in the output echoes the order in which corresponding items appear in the input.
Now, it is possible to write PTs that produce outputs in a different order from the corresponding inputs, but for such a situation we have to essentially include a different set of arcs for each possible input-output pair. When the input and output languages have large vocabularies, this leads to large networks, which cannot be expressed concisely even using our abbreviation mechanism. One solution to this problem would be to have a way of specifying how a sequence of outputs relates to a sequence of inputs, rather than having to specify input-output relations at the level of single arcs. Grammars, as presented in Chapters 4 and 7, provide a basis for describing sequences of phrases, and in Chapter 8 we will see how we can compute outputs from such grammars. Alternatively, we can keep to the network metaphor and enhance our networks with extra facilities to overcome the PT limitations. This is the approach taken with augmented transition networks (ATNs).
Consider, for instance, what is required to enhance our translator to deal with more interesting noun phrases. In French, adjectives standardly follow the noun they modify, whereas in English they precede it For instance, we would want 'a short name' to be translated to 'un nom court' (literally, 'a name short').
In fact, there are good reasons why we left out adjectives in our previous translators. If we try to extend the PT to include adjectives on the English side, we find that we have to write networks like the following:
Name NP: Initial 0 Final 2 From 0 to 1 by DET-MASC From 1 to 1a by short_# From 1 to 1c by green_# ... From 1a to 2a by N-MASC From 1b to 2b by N-MASC From 1c to 2c by N-MASC ... From 2a to 2 by #_court From 2c to 2 by #_vert ... .
where there are three arcs for each possible English adjective (and yet this network only deals with single adjectives!). The problem is that the French adjectives, which are known before the English noun is encountered, have somehow to be remembered and then produced on the second tape after the noun is translated. ATNs allow values to be remembered in this way during a network traversal by providing registers (variables) for storing information. Registers are rather like (local) variables in a procedural programming
language like Lisp.
Thus, in our notation for ATNs, we will include a line declaring the registers used at the beginning of each network. Each arc of the network may then be annotated with instructions for how to shuffle information between these registers when it is traversed. Instructions can also be associated with the initial and final nodes of a network, specifying things to do when the network is entered or exited. In the latter case, the instructions will concern the single value that the network is allowed to return to the network that calls it, summarizing the result of its computations.
To make things more concrete, here is how we might tackle our noun phrase translation problem in an ATN. We will use the register FNP to keep track of the value (French phrase) to be returned by the NP network. In the French translation of a proper noun, this is simply whatever single French name corresponds to that English name, if there is one. In the French translation of a simple noun phrase, we need to have a French determiner, a collection of French adjectives and a French noun. We can introduce registers called FDET, FADJS and FNOUN to keep track of this information used in the translation of a noun phrase, and annotate the NP network informally as follows (for now, read '*' as meaning the current word):
Name NP: Registers FADJS, FNOUN, FDET, FNP Initial 0 set FADJS to the empty string Final 2 return FNP From 0 to 1 by DET set FDET to French(*) From 1 to 1 by ADJ set FADJS to FADJS + French(*) From 1 to 2 by N set FNOUN to French(*) set FNP to FDET + FNOUN + FADJS.
where '+' is a form of string concatenation that inserts spaces between words and 'French' is a function that takes English words to their French translations, which we naively assume to be unique. The register FADJS is used here to hold a string that will translate a whole sequence of adjectives. As more English adjectives are discovered, their French translations are added to the end of the current value of this register.
Registers allow us to separate the times when parts of the output are computed from the position they occupy in the output. The idea is to recognize one structure but to be able to build as output a structure that may be only indirectly related to it.
We have assumed here that the French translation of any English word - that is, French(*) - can be easily computed. In general, ATN systems allow us to call arbitrary procedures defined in a standard programming language (often LISP) from the arcs of a network, and in an actual system this would probably be how this would be implemented.
Note that the network could actually specify the category of the word to be translated, which would help when a given English word was ambiguous; for example, 'slight' could be a noun or an adjective, and would translate into 'manque d'egards' or 'leger' accordingly. Nevertheless, it is still very simplistic to assume that a word can be translated without any regard to the context, and no sensible machine translation system would be designed this way.
Usually in ATNs there is one special register, called '*', which automatically holds the value we are currently considering. When '*' is mentioned on an arc that is looking for a single word (either a specific word or a word covered by an abbreviation), it will always refer to the current word that the arc is looking at (as in the preceding network). On the other hand, when '*' is mentioned on an arc that introduces a PUSH to a subnetwork, it will always refer to the result returned by that subnetwork. This enables higher networks to deal with the result of lower networks. For instance, in our translation example, the S network needs to put together the French translations of the noun phrase and the verb phrase to make the translation of the whole sentence. Here is one way it could be done, using registers FSUBJECT and FPREDICATE to hold these values:
Name S: Registers FSUBJECT, FPREDICATE Initial 0 Final 2 return FSUBJECT + FPREDICATE From 0 to 1 by NP set FSUBJECT to * From 1 to 2 by VP set FPREDICATE to *.
Our translation rules for English noun phrases are inadequate in a number of ways, but one of the limitations provides grounds for introducing another feature of ATNs - extra tests on the arcs. The precise form of a determiner or adjective in French depends on the gender of the noun it qualifies, this being either masculine or feminine. Thus, we have
a green tree -> un arbre vert (a tree green) a green table -> une table verte (a table green)
Unfortunately, in our ATN we will not find out the gender of the noun phrase until the English noun is encountered, and by then we will have already generated the translation of the adjectives. One solution would be to actually keep the English determiner and adjectives in registers, and then translate them at the end of the phrase. A simpler solution, however, makes use of the trick used for French determiners in the ENG_FRE-2 FST, which relies on the fact that network traversal is organized as a search process, so that all possible traversals of the network will be found. We can outline two routes through the NP network, one corresponding to a masculine NP and the other corresponding to a feminine one. Each of these routes will produce adjectives with endings appropriate to the gender chosen and will then require there to be a noun of the appropriate gender at the end of the phrase. In any actual traversal, only one of them will lead to a successful solution, because the noun in the input string will have only one gender. As long as our implementation correctly searches through all possibilities, however, it will not matter whether it finds the correct path first or whether it starts off trying the possibility that fails. Because we have an ATN, rather than an FSTN, we can introduce a further twist and avoid duplicating all the NP arcs for the two different routes. Instead, we can use a register FGENDER to record the gender that we have chosen. So, the two different routes start with different arcs, setting the register to the two different values, but share exactly the same arcs after that. The arcs that the two routes have in common will then translate the determiner and adjectives on the basis of whatever value FGENDER has. To force the analysis to succeed only when the choice of FGENDER is the same as the gender of the French noun, we add a special test to the arc from "1" to "2":
Name NP: Registers FADJS, FDET, FNP, FNOUN, FGENDER Initial 0 set FADJS to the empty string Final 2 return FNP From 0 to 1 by DET set FGENDER to "masculine" set FDET to French(*,"masculine") From 0 to 1 by DET set FGENDER to "feminine" set FDET to French(*,"feminine") From 1 to 1 by ADJ set FADJS to FADJS + French(*,FGENDER) From 1 to 2 by N set FNOUN to French(*) the gender of FNOUN must be the same as FGENDER set FNP to FDET + FNOUN + FADJS.
where we now assume that the function French is provided with a gender as well as an English word, where this is required. Notice that, although we needed two arcs corresponding to the original choice of the gender, we did not need to duplicate the arcs for the adjectives and noun in the same way. The use of the register FGENDER enabled us to use each arc for both of the two alternatives. For this sort of approach to work, we obviously need a search mechanism that allows a register to have different values in different possible paths through the network. This has direct implications for the way one implements ATNs.
In our simple English-French translation example, we have seen how ATN registers can be used locally to reorder material to be output. The same idea can be used globally to keep track of phrases that appear extraposed from their canonical position. For instance, each of the following questions is identical in form to the word 'who' followed by an ordinary statement, except that somewhere in the statement there is a gap (indicated by '?') where we would normally expect a noun phrase. This gap corresponds to the position of the item whose identity is being questioned:
Which employer [? will see Maria tomorrow] Who [will Mayumi see ?] Who [does Mayumi have a contract with ?]
In an ATN, it is relatively straightforward to remember (left) extraposed material (here, the questioned noun phrases) by assigning a value to a global register HOLD and to retrieve the relevant information again when an apparent gap is found.
Send us a comment.