Hopfield Models as Nondeterministic Finite-State Machines

Hopfield Models as Nondeterministic Finite-State Machines Marc F.J. Drossacrs Computer Science Department, University of Twente, P.O Box 217, 7500 AE Enschede, The Netherlands, email: mdrssrs@cs.utwente.nl. Abstract Tbe use of neural networks for integrated linguistic analysis may be profitable. This paper presents the first results of our research on that subject: a Hop- field model for syntactical analysis. We construct a neural network as an implementation of a bounded push-down automaton, which can accept context-free languages with limited center-embedding. The net- work's behavior can be predicted a priori, so the pre- sented theory can be tested. The operation of the network as an implementation of the acceptor is prov- ably correct. Furthermore we found a solution to the problem of spurious states in Hopfield models: we use them as dynamically constructed representations of sets of states of the implemented acceptor. The so-called neural-network aceeptor we propose, is fast but large. 1 Introduction Neural networks may be well suited for integrated lin- guistic analysis, as Waltz and Pollack [10] indicate. An integrated linguistic analysis is a parallel compo- sition of several analyses, such as syntactical, seman- tical, and pragmatic analysis. When integrated, these analyses constrain each other interactively, and may thus suppress a combinatoric explosion of sentence structure and meaning representations. This paper presents the first results of our research into the use of neural networks for integrated linguis- tic analysis: a Hopfield model for syntactical analysis. Syntactical analysis in the context of integration with other analyses boils down to the decision whether a sentence is an element of a language. A parse tree is superfluous here as an intermediary representation, since it will not be finished before the complete in- tegrated analysis is. This fact allows us to deal with the problem of a restricted length of the sentences a neural par .... n handle, see e.g. [51,[7], a problem that could not be elegantly solved, see e.g. [6],[3]. In this paper we propose a formal model that rec- ognizes syntactically correct sentences (section 2), a tlopfield model onto which we want to map this for- mar model (section 3), the parameters that makes the network operate as intended (section 4), and a way to map the formal model onto the Hopfield model, including a correctness result for the latter (section 5). The theoretically predicted behavior of the so~ obtained network has been verified, and a simple ex- ample provides the taste of it (section 6). We alas consider complexity aspects of the model (section 7). Section 8 consists of concluding remarks. 2 A Bounded Push-Down Au- tomaton Although it is not an t.~tablished fact, it is as- stoned here that natural languages are context-free, and consequently that sentences in a natural lan- guage can be recognized, by a push-down atttoma- ton (PDA). ilowever, we are not interested in mod- eling the competence of natural language users, but in modeling their performance. The human perfor- mance in natural language use is also characterized by a very limited degree of center-embedding. In …

Content truncated to 500 words