Augmented Transition Network (ATN)
An Augmented Transition Network (ATN) is an Artificial Neural Network that is an extension of a Recursive Transition Network.
- Context:
- …
- Example(s):
- Counter-Example(s):
- See: Ambiguity, Graph Theory, Operational Definition, Formal Language, Parsing, Natural Language, Artificial Intelligence, Sentence Structure, Recursive Transition Network, Finite State Machine, Markov Model, Recursive.
References
2020
- (Wikipedia, 2020) ⇒ https://en.wikipedia.org/wiki/Augmented_transition_network Retrieved:2020-9-11.
- An augmented transition network or ATN is a type of graph theoretic structure used in the operational definition of formal languages, used especially in parsing relatively complex natural languages, and having wide application in artificial intelligence. An ATN can, theoretically, analyze the structure of any sentence, however complicated. ATN are modified transition networks and an extension of RTNs.
ATNs build on the idea of using finite state machines (Markov model) to parse sentences. W. A. Woods in "Transition Network Grammars for Natural Language Analysis" claims that by adding a recursive mechanism to a finite state model, parsing can be achieved much more efficiently. Instead of building an automaton for a particular sentence, a collection of transition graphs are built. A grammatically correct sentence is parsed by reaching a final state in any state graph. Transitions between these graphs are simply subroutine calls from one state to any initial state on any graph in the network. A sentence is determined to be grammatically correct if a final state is reached by the last word in the sentence.
This model meets many of the goals set forth by the nature of language in that it captures the regularities of the language. That is, if there is a process that operates in a number of environments, the grammar should encapsulate the process in a single structure. Such encapsulation not only simplifies the grammar, but has the added bonus of efficiency of operation. Another advantage of such a model is the ability to postpone decisions. Many grammars use guessing when an ambiguity comes up. This means that not enough is yet known about the sentence. By the use of recursion, ATNs solve this inefficiency by postponing decisions until more is known about a sentence.
- An augmented transition network or ATN is a type of graph theoretic structure used in the operational definition of formal languages, used especially in parsing relatively complex natural languages, and having wide application in artificial intelligence. An ATN can, theoretically, analyze the structure of any sentence, however complicated. ATN are modified transition networks and an extension of RTNs.
2002
- (Chen et al., 2002) ⇒ Shu-Ching Chen, R. L. Kashyap, and Arif Ghafoor (2002) "Case Study 1 — Augmented Transition Network (ATN) Model". In: Semantic Models for Multimedia Database Searching and Browsing. Advances in Database Systems, vol 21. Springer, Boston, MA. DOI:10.1007/0-306-47029-2_5.
- QUOTE: An augmented transition network $\psi$ is a 6-tuple $\left(S, I, T, S_0, F, \psi\right)$ where
1. $S = \{S_0, S_1, \cdots , S_{n-1}\}$ is a finite set of states of the control. Each state represents all the events before this state have been accomplished so that it does not need to know the history of the past to continue the presentation.
2. $I$ is a set from which input symbols are chosen. The input string consists of one or more $m_i$ and $cm_i$ where $m_i$ and $cm_i$ are separated by “+” and $m_i$ and $cm_i$ denote a media stream and compressed version of that media stream, respectively.
3. $T$ is a condition and action table by permitting a sequence of actions and conditions to be specified on each arc. A presentation can be divided into several time durations based on different media stream combinations.
- QUOTE: An augmented transition network $\psi$ is a 6-tuple $\left(S, I, T, S_0, F, \psi\right)$ where
1978
- (Bates, 1978) ⇒ Madeleine Bates (1978). "The Theory And Practice Of Augmented Transition Network Grammars". In: Natural language communication with computers (pp. 191-254). Springer, Berlin, Heidelberg.
- QUOTE: A basic transition network (BTN) grammar looks like a collection of finite state transition diagrams; each is a directed graph with labelled states and labelled arcs, a distinguished start state, and a set of distinguished final states. The label on an arc indicates the type (usually the syntactic category, i.e., part of speech) of input which will allow the transition to be made to the next state. An input sequence is said to be accepted by the network if, beginning in the start state, some path (sequence of arcs) can be followed which terminates on a final state.
The network differs from a finite state automaton in that it permits recursion by allowing the label on some arcs to be a nonterminal rather than a terminal symbol (...)
But it is well known that context free grammars are not adequate for English. In addition, the basic grammar we have described is capable only of accepting or rejecting input strings; it cannot produce a structure which shows something about the relationships among the words.
To make a more powerful model, each arc is provided with a test and a sequence of actions, thus producing an augmented transition network. The test associated with an arc must be satisfied (in addition to the label) for the arc to be taken, and the actions are executed as the arc is traversed. The actions construct pieces of structure (tree structures, case structures, etc.) and keep them in registers, which may be thought of in programming terms as variables local to the level of the grammar where they are set. Registers and their contents are available on subsequent arcs and can be combined, copied, changed, or added to as more of the input is processed.
- QUOTE: A basic transition network (BTN) grammar looks like a collection of finite state transition diagrams; each is a directed graph with labelled states and labelled arcs, a distinguished start state, and a set of distinguished final states. The label on an arc indicates the type (usually the syntactic category, i.e., part of speech) of input which will allow the transition to be made to the next state. An input sequence is said to be accepted by the network if, beginning in the start state, some path (sequence of arcs) can be followed which terminates on a final state.
1970
- (Woods, 1970) ⇒ William A. Woods. (1970). “Transition Network Grammars For Natural Language Analysis.” In: Communications of the ACM, 13(10). DOI:10.1145/355598.362773
- QUOTE: In addition to many advantages for efficient context free recognition and improved strong generative power, the transition network model also provides a convenient means for incorporating syntactic and semantic conditions for guiding the parsing and for performing transformations and relocations of constituents. This is done by associating arbitrary conditions and structure building actions with the arcs of the network. This augmented network is a kind of “transducer", whose effects are to make changes in the contents of a set of registers associated with the network and whose transitions can be conditional on the contents of those registers. Registers can be used to hold pieces of syntactic structure whose position and function in the syntactic structure being built might not yet have been determined.
Experience with the parsing system has shown it to be an extremely powerful system- capable of performing the equivalent of transformational analysis in little more time than that customarily required for context free analysis alone. In addition, the system is convenient for the designer of the grammar and facilitates experiments with various types of structural representations and various parsing strategies.
- QUOTE: In addition to many advantages for efficient context free recognition and improved strong generative power, the transition network model also provides a convenient means for incorporating syntactic and semantic conditions for guiding the parsing and for performing transformations and relocations of constituents. This is done by associating arbitrary conditions and structure building actions with the arcs of the network. This augmented network is a kind of “transducer", whose effects are to make changes in the contents of a set of registers associated with the network and whose transitions can be conditional on the contents of those registers. Registers can be used to hold pieces of syntactic structure whose position and function in the syntactic structure being built might not yet have been determined.