A Parsing Architecture Based on Distributed Memory Machines

A PARSING ARCHITECTURE BASED ON DISTRIBUTED MEMORY MACHINES Jon M. Slack Department of Psychology Open University Milton Keynes MK7 6AA ENGLAND ABSTRACT The paper begins by defining a class of distributed memory machines which have useful properties as retrieval and filtering devices. These memory mechanisms store large numbers of associations on a single composite vector. They provide a natural format for encoding the syntactic and semantic constraints associated with linguistic elements. A computational architecture for parsing natural language is proposed which utillses the retrieval and associative features of these devices. The parsing mechanism is based on the principles of Lexlcal Functional Grammar and the paper demonstrates how these principles can be derived from the properties of the memory mechanisms. I INTRODUCTION Recently, interest has focussed on computational architectures employing massively parallel processing lip2]. Some of these systems have used a distributed form of knowledge representation [3]. This type of representation encodes an item of knowledge in terms of the relationships among a collection of elementary processing units, and such assemblages can encode large numbers of items. Representational similarity and the ability to generalize are the principal features of such memory systems. The next section defines a distributed memory machine which incorporates some of the computational advantages of distributed representations within a traditional yon Neumann architecture. The rest of the paper explores the properties of such machines as the basis for natural language parsing. II DISTRIBUTED MEMORY MACHINES Distributed memory machines (DMM) can be represented formally by the septuple DMM=(V,X,Y,Q,qo,p,A) , where V is a finite set denoting the total vocabulary; X is a finite set of inputs, and XGV; Y is a finite set of acceptable outputs and Y~V; Q is a set of internal states; q0 is a distinguished initial state; ~.QxX-->Q, the retrieval function; A:Q-->Qxy, the output function. Further, where Y" denotes the set of all finite concatenations of the elements of the set Y, Q~Y', and therefore QgV'. This statement represents the notion that internal states of DMMs can encode multiple outputs or hypotheses. The vocabulary, V, can be represented by the space I k, where I is some interval range defined within a chosen number system, N; IoN. The elements of X, Y and Q are encoded as k-element vectors, referred to as memory vectozs. A. Holographic Associative Memory One form of DMM is the holographic associative memory [4,5,6] which encodes large numbers of associations on a single composite vector. Items of information are encoded as k-element zero-centred vectors over an interval such as [-I,+I]; <X>=(...x.t,x0,x~t,...). Two items, <A> and <B> (angular brackets denote memory vectors), are associated in memory through the operation of convolution. This method of association formation is fundamental to the concept of holographic memory and the resulting associative trace is denoted <A>*<B>. The operation of convolution is define by the equation (<A>*<B>~=.~AIB~. i and has the following propertles*[7]: Commutative: <A>*<B> = <B>*<A>, Associative: <A>*(<B>*<C>) = (<A>*<B>)*<C>. Further, where a delta vector, denoted ~, is defined as a vector that has values of …

Content truncated to 500 words