AUGMENTED TRANSITION NETWORKS

             AUGMENTED TRANSITION NETWORKS
                   =============================

Introduction
------------
Augmented Transition Networks (ATNs) were originally used for
syntactic parsing of Natural Language (NL), but they have the power
of a Universal Turing Machine, and so can be used for other purposes
too.   An example of their use is in the expert system ATTENDING
developed by P.L. Miller for critiquing an anaesthetist's patient
management plan.   Here, the use of ATNs in parsing English is
examined.   ATNs stand out somewhat from the rest of the course,
and this topic could be omitted entirely were it not for the fact
that ATNs are so often used as an AI technique.   It should be
noted, however, that there are other techniques for parsing NL.




prasenraj.blogspot.in

An ATN is a directed graph, consisting of nodes and arcs.   The
nodes represent states in the parse; each arc contains a test which
must succeed for the arc to be traversed.   If the arc is traversed,
an action is performed.   The parse proceeds by means of a depth-
first search of the ATN; it succeeds if a dead end (an arc which
leads to nowhere) is traversed.   During this process, a parse tree
is constructed by the actions performed during arc traversal.   The
tests on the arcs can involve traversal of other, independent graphs
called subnets.

                            ----------

An Example
----------
The ATN shown below parses simple noun phrases such as

  Marvin
  a bug in a rug
  a block in that box on the table
  this robot of Zaphod

                                     return
                                    +--->---
                                    |
     scan(det)        scan(noun)    |    parse(PP)         return
  NP ---->---- NP-DET ----->---- NP-NOUN ---->---- NP-DONE --->---
    |                                                 |
    +------->-------------------->--------------------+
        scan(pn)

     scan(prep)         parse(NP)         return
  PP ----->---- PP-PREP ---->---- PP-DONE --->---

  det  = (the, a, an, this, that)
  noun = (bug, rug, box, block, table, robot)
  pn   = (Marvin, Arthur, Ford, Zaphod)
  prep = (in, on, with, of)

The transition network shown above can be augmented, by attaching
actions to the arcs.   When this is done, we get the following:

  Node            Test            Dest.         Action
  ----            ----            -----         ------
  NP:      if     scan(det)  goto NP-DET  after DET  := det(*)
           elseif scan(pn)   goto NP-DONE after NP   := np(pn(*));
  NP-DET:  if     scan(noun) goto NP-NOUN after NOUN := noun(*);
  NP-NOUN: if     parse(PP)  goto NP-DONE after NP   := np(DET, NOUN, *)
           else   return NP;
  NP-DONE: return NP;

  PP:      if     scan(prep) goto PP-PREP after PREP := prep(*);
  PP-PREP: if     parse(NP)  goto PP-DONE after NP   := *;
  PP-DONE: return pp(PREP, NP);

* is always bound to the result of an arc test.   Actions can
either be assignments to registers (such as PREP and NP), or the
retrieval of values from registers.   Because the same register may
be used on more than one subnet of the ATN, it is necessary to save
the values of registers whenever a new subnet is entered.   The old
values are restored when the subnet is exited.

We shall consider the parsing of "this robot of Zaphod", with
NP as our start node.

   Trace of parse.                Result after action is executed.
   ---------------                --------------------------------
   (1) parse(NP)
   (2) enter NP
   (3) scan(det)                  * = this, DET = det(this)
   (4) enter NP-DET
   (5) scan(noun)                 * = robot, NOUN = noun(robot)
   (6) enter NP-NOUN
   (7) parse(PP)
   (8)   enter PP
   (9)   scan(prep)               * = of, PREP = prep(of)
  (10)   enter PP-PREP
  (11)   parse(NP)
  (12)     scan(det) -> failure
  (13)     scan(pn)               * = Zaphod, NP = np(pn(Zaphod))
  (14)     enter NP-DONE
  (15)     return from NP         * = np(pn(Zaphod))
  (16)   enter PP-DONE
  (17)   return from PP           * = pp(prep(of), np(pn(Zaphod)))
  (18) enter NP-DONE
  (19) return from NP             * = np(det(this),
                                         noun(robot),
                                         pp(prep(of), np(pn(Zaphod))))

                            ----------

The Basic ATN Parsing Algorithm
-------------------------------
The algorithm followed is very simple.   Here it is:

  To parse a node:
    Search through the arcs leaving the node until one is
      found whose test succeeds;
    IF none is found THEN
      Return with failure
    ELSE
      (A test on one of the arcs succeeded.)
      IF there are any arcs which have not yet been tried THEN
        Put them on an agenda, together with the current state of the
          computation.   (This will enable the ATN to backtrack if a
          parse fails.)
      END IF;
      IF the test which succeeded was "return" THEN
        (* is now bound to the result of the arc test.)
        Return with success -- the value returned is the value of the
          action on the arc.
      ELSE
        Perform the action on the arc;
        Parse the node reached by following the arc
          whose test succeeded.
      END IF
    END IF

                            ----------



prasenraj.blogspot.in



Backtracking and "Garden Path Sentences"
----------------------------------------
Many sentences are locally ambiguous.

He saw John and Mary last week.
He saw John and Mary saw Fred.
                    |
                   HERE

At the place marked HERE, there are two possibilities.   One is
that [John and Mary] is the object of [saw] (as in the first
sentence); the other is that [Mary] is the subject in a second
clause ([Mary saw Fred] in the second sentence).   Suppose we
choose the first possibility.   Then the first sentence will
parse correctly with [last week] being an extension of the verb,
but the second sentence will fail, as a verb would not be
expected after completing the parse of a clause.   If the second
possibility is chosen instead, the second sentence parses
correctly, but in the first sentence, a verb is expected and none
follows [Mary].   Either way, there are a number of words which
dangle at the end of a well-formed clause.

There are a number of ways round this problem:

  (1) Chronological backtracking.
  (2) Look ahead in the sentence far enough to make backtracking
      unnecessary.
  (3) Patch up the sentence, by undoing only as much of the parse
      tree as is necessary.   This can be done either by using
      dependency-directed backtracking, or by making the best use
      of information available when the parse is found to fail.

ATNs use chronological backtracking.   If a parse fails, it then
makes use of any decision points which were stored on the agenda.
These decision points contain

  (1) the current state of the computation, which was effectively
      spawned as a process -- this will contain, among other
      things, a copy of the stack contents;
  (2) the remainder of the sentence which was parsed;
  (3) the arcs which had not been tried when it reached the
      decision points.

The algorithm is now extended to handle the case of a failed parse:

  Parse the start node;
  IF the parse fails THEN
    WHILE the agenda is not empty
      Take the top item off the agenda and resume its computation;
      EXIT WHEN a parse succeeds
    END WHILE;
    IF the agenda is empty and no parse has succeeded THEN
      There is no valid parse
    ELSE
      A successful parse has been found
    END IF
  ELSE
    A successful parse has been found
  END IF

                            ----------