Although introducing named subnetworks seems conceptually like a small change to make to FSTNs, it does introduce significant complexity in the procedure for traversing a network. The basic problem is that, to traverse one arc, it may be necessary to traverse a whole subnetwork. While that subnetwork is being traversed, the position of the original arc must be remembered, so that the traversal can resume there afterwards. Our kangaroo model of network traversal, introduced in Chapter 2, needs to be embellished somewhat to account for this.
In a recursive network, a kangaroo may come across a subnetwork name on an arc, instead of a word. In this case, we can think of it as recruiting another kangaroo (from a large labour pool) to traverse the subnetwork for it. As this second kangaroo jumps through the subnetwork, it is allowed to move the pointing device along the input string. It is also allowed to recruit other kangaroos to traverse sub-sub-networks for it (and the levels of delegation may go arbitrarily deep). When any kangaroo has finished, it reports success to the kangaroo that recruited it, who waits patiently until this happens. So, when the second kangaroo has finished jumping through its subnetwork it reports back to the first kangaroo. The first kangaroo wakes up again, noticing that the pointer has been moved on, finishes jumping along the arc mentioning the subnetwork and continues from the new node as before.
In the kangaroo model, at any time, there is one kangaroo jumping through a network and a line of other kangaroos, each remembering a place in a network and waiting to resume work once its subordinate has finished, as illustrated in Figure 3.2. The first of the waiting kangaroos (the one who joined the line last) is waiting for the currently active kangaroo, the second waiting kangaroo is waiting for the first, the third waiting kangaroo is waiting for the second, and so on. If the active kangaroo gets to the end of its network, it wakes up the first waiting kangaroo and then rejoins the labour pool. This first waiting kangaroo leaves the line and resumes work. When it finishes, it wakes up the first kangaroo in the line (who was previously the second) and itself goes back to the labour pool. On the other hand, if the active kangaroo finds a subnetwork that needs traversing, it recruits a new kangaroo from the labour pool (not the waiting line), sets this kangaroo off on the subnetwork and itself joins the waiting line, at the front, waiting for the subcontracted work to be complete.
The main innovation here is the line of waiting kangaroos. How are we to represent this computationally? In fact, the line of waiting kangaroos corresponds to the computational device of a pushdown stack. A pushdown stack is a device for storing information that can be manipulated by two basic operations.
(1) A piece of information can be PUSHed (added) on to the stack. This corresponds to a kangaroo joining the line at the front.
(2) The most recently added piece of information can be POPped (removed) from the stack. This corresponds to the first kangaroo in the line being woken up, leaving the line and resuming work.
When we need to indicate the contents of a pushdown stack, we will simply separate the items with colons, the first (most recently added) item being on the left. We will denote the empty stack by empty space. So here is how we would denote the stack that results from 'pushing' the symbols a, b and c on to the empty stack in that order:
c : b : a :
While a kangaroo is waiting in the line, it only needs to remember its place in a network, so that it can resume there afterwards. All other information can be picked up when it starts work again - the networks themselves will not have changed, and the pointer will have changed in ways completely outside its control. Thus, the pieces of information to be stored in the pushdown stack are simply positions in the networks. We can represent a position in a network by the name of the node where the kangaroo will resume work (the destination of the arc that requires the traversal of the subnetwork). In general, if we allow the same node name to be used in different networks, we require the name of the network containing the node as well. Where it is necessary to distinguish which network a node belongs to, we will qualify the name in the following fashion:
S/3
which denotes the node named 3 in the network S.
If we wish to extend our previous account of network traversal to RTNs, the notion of 'state' will have to be extended now to include a third component:
R3. a pushdown stack of positions (node names).
Here, then, is a fully specified example state describing a point in an RTN traversal (recognition, not generation):
<NP/0, the men, VP/2:S/2: > ^ ^ ^ | | | | | R3. stack of node names | | | R2. remaining symbols | R1. current node
This state represents the intermediate state of a traversal where the remaining words to be considered are 'the men', the active kangaroo is sitting on node 0 in the network NP. The line of waiting kangaroos contains kangaroos waiting to continue moving from node 2 in network VP (at the front of the line) and node 2 in network S (at the back of the line).
Given this modified notion of 'state', the basic search algorithm for network traversal does not need to be different from the finite-state case. This time each of the initial set of states needs to have an empty stack. Thus, since 0 is the only initial node in the top-level network for English sentences, the only initial state for traversing this network would be:
<S/0, ..., >
where '...' is the input string. What are the valid final states that indicate successful traversal? To be successful, we must have reached a final node in the top-level network, we must have an empty line of waiting kangaroos and we must have used all the symbols in the input. Thus, if we were using our networks for English sentences, the only possible final state would be:
<S/2, , >
How do we calculate the valid next states that follow from a given state <NODE, INPUT, STACK>. For each arc (with label L and destination D) leaving node NODE, we must include states in the set according to the following rules. We illustrate these with examples from the foregoing example networks:
(POP) if NODE is a final node, the top of STACK is H and the rest of STACK is T, include <H, INPUT, T>
e.g. from <NP/2, sings, S/1: > we can get <S/1, sings, >
(SYM') if L is a symbol and the first symbol of INPUT is the same, include <D, ...rest of INPUT..., STACK>
e.g. from <VP/1,that John, S/2: > we can get <VP/3,John, S/2: >
(ABB') if L is an abbreviation which covers the first symbol of INPUT, include <D, ...rest of INPUT..., STACK>
e.g. from <NP/1,man sings, S/1: > we can get <NP/2,sings,S/1: >, since 'man' is a N
(PUSH) if L is a network name, for each initial node INIT of that network include <INIT, INPUT, D:STACK>
e.g. from <VP/1, the man, S/2: > we can get <NP/0, the man, VP/2:S/2: >
(JMP') if L is #, include <D, INPUT, STACK>
Of these principles, two are new and correspond to entering and leaving subnetworks (PUSH and POP). The others are essentially the same as in the finite-state network case.
Here is an example of recognition using our initial English networks and the sentence 'Mary sees that man.' We will show the stages of the recognition by a sequence of 'snapshots', each time showing the set of alternative states under consideration. Initially, we just have one state:
<S/0, Mary sees that man, >
Removing this from the set, only the PUSH rule is applicable and so we get:
<NP/0, Mary sees that man, S/1: >
Selecting this, only the ABB' rule applies (the first word is an NP):
<NP/2, sees that man, S/1: >
From NP/2, the only arc requires a WH word, and 'sees' is not of this category. Since NP/2 is a final node, the only option is then to POP to:
<S/1, sees that man, >
From S/1, there is no choice but to PUSH, looking for a VP:
<VP/0, sees that man,S/2: >
Once again, there is no choice but to recognize the V and proceed (by ABB') to VP/1:
<VP/1, that man, S/2: >
From VP/1, there are now three possibilities. Since VP/1 is a final node, we can POP back to the S network. Alternatively, we can proceed to VP/3 by consuming the word 'that' (SYM'). Finally, we can try to PUSH for an NP. Thus, we have three possible next states:
<S/2, that man, > <VP/3, man,S/2: > <NP/0, that man, VP/2:S/2: >
We now have to choose between these, removing one from the set and leaving the other two behind, to be reconsidered later if other possibilities do not work out. Let us say that we choose the first of them. Since there are no arcs leaving S/2, only the POP rule could be appropriate. This does not apply, however, as the stack is empty. So we cannot progress further from this state. Since the state is not a final state, we simply remove it from the list, leaving:
<VP/3, man, S/2: > <NP/0, that man, VP/2:S/2: >
Again, we have to choose which state to investigate next. Let us again choose the first one. From VP/3, we have no option but to PUSH for an S:
<S/0, man, VP/2:S/2: > <NP/0, that man, VP/2:S/2: >
Again, selecting the first state in the list, we are forced to PUSH and get:
<NP/0, man, S/1:VP/2:S/2: > <NP/0, that man, VP/2:S/2: >
If we this time select the second state to investigate, we can proceed to:
<NP/0, man, S/1:VP/2:S/2: > <NP/1, man, VP/2:S/2: >
(because 'that' is a DET). Similarly, we can progress from this state to a similar state at NP/2:
<NP/0, man, S/1:VP/2:S/2: > <NP/2, , VP/2:S/2: >
If we continue selecting the second state in the set, we can POP to:
<NP/0, man, S/1:VP/2:S/2: > <VP/2, , S/2: >
and then POP again to:
<NP/0, man, S/1:VP/2:S/2: > <S/2, , >
The second state in our list is now a successful final state, and so we can halt, having successfully recognized the string.
Here is an example of random generation from the networks, giving the intermediate states and the rule used at each stage. As in the FSTN case, for generation, we keep the list of words output so far, rather than the list of words to be processed in a state. The rules for generating next states have to be altered slightly to cater for this change. Since the generation is random, we only need to consider one alternative at each point and can discard the others.
<S/0, , > PUSH <NP/0, , S/1: > ABB' (NP) <NP/2, John, S/1: > POP <S/1, John, > PUSH <VP/0, John, S/2: > ABB' (V) <VP/1, John saw, S/2: > PUSH <NP/0, John saw, VP/2:S/2: > ABB' (DET) <NP/1, John saw the, VP/2:S/2: > ABB' (N) <NP/2, John saw the mouse, VP/2:S/2: > POP <VP/2, John saw the mouse, S/2: > POP <S/2, John saw the mouse, > SUCCESS!
Send us a comment.