Discrete recurrent neural networks for grammatical inference

Describes a novel neural architecture for learning deterministic context-free grammars, or equivalently, deterministic pushdown automata. The unique feature of the proposed network is that it forms stable state representations during learning-previous work has shown that conventional analog recurrent networks can be inherently unstable in that they cannot retain their state memory for long input strings. The authors have previously introduced the discrete recurrent network architecture for learning finite-state automata. Here they extend this model to include a discrete external stack with discrete symbols. A composite error function is described to handle the different situations encountered in learning. The pseudo-gradient learning method (introduced in previous work) is in turn extended for the minimization of these error functions. Empirical trials validating the effectiveness of the pseudo-gradient learning method are presented, for networks both with and without an external stack. Experimental results show that the new networks are successful in learning some simple pushdown automata, though overfitting and non-convergent learning can also occur. Once learned, the internal representation of the network is provably stable; i.e., it classifies unseen strings of arbitrary length with 100% accuracy.     

A survey of grammatical inference methods for natural language learning

The high complexity of natural language and the huge amount of human and temporal resources necessary for producing the grammars lead several researchers in the area of Natural Language Processing to investigate various solutions for automating grammar generation and updating processes. Many algorithms for Context-Free Grammar inference have been developed in the literature. This paper provides a survey of the methodologies for inferring context-free grammars from examples, developed by researchers in the last decade. After introducing some preliminary definitions and notations concerning learning and inductive inference, some of the most relevant existing grammatical inference methods for Natural Language are described and classified according to the kind of presentation (if text or informant) and the type of information (if supervised, unsupervised, or semi-supervised). Moreover, the state of the art of the strategies for evaluation and comparison of different grammar inference methods is presented. The goal of the paper is to provide a reader with introduction to major concepts and current approaches in Natural Language Learning research.     

Content-based unsupervised segmentation of recurrent TV programs using grammatical inference

Multimedia Tools and Applications - TV program segmentation raised as a major topic in the last decade for the task of high quality indexing of multimedia content. Earlier studies of TV program...     

Data mining for grammatical inference with bioinformatics criteria

In this work a novel data mining process is described that combines hybrid techniques of association analysis and classical sequentiation algorithms of genomics, to generate grammatical structures of a specific language. Subsequently, these structures are converted to Context-Free Grammars. Initially the method applies to context-free languages with the possibility of being applied to other languages: structured programming, the language of the book of life expressed in the genome and proteome and even the natural languages. We used an application of a compilers generator system that allows the development of a practical application within the area of grammarware, where the concepts of the language analysis are applied to other disciplines, like bioinformatic. The tool allows measuring the complexity of the obtained grammar automatically from textual data.     

First-order versus second-order single-layer recurrent neuralnetworks

We examine the representational capabilities of first-order and second-order single-layer recurrent neural networks (SLRNN's) with hard-limiting neurons. We show that a second-order SLRNN is strictly more powerful than a first-order SLRNN. However, if the first-order SLRNN is augmented with output layers of feedforward neurons, it can implement any finite-state recognizer, but only if state-splitting is employed. When a state is split, it is divided into two equivalent states. The judicious use of state-splitting allows for efficient implementation of finite-state recognizers using augmented first-order SLRNN's.     

Some experiments in two-dimensional grammatical inference

This paper presents results of experiments conducted on a scheme for inferring two-dimensional, probabilistic Siromoney array grammars incorporating Markov random field distortion of binary images.     

A bibliographical study of grammatical inference

The field of grammatical inference (also known as grammar induction) is transversal to a number of research areas including machine learning, formal language theory, syntactic and structural pattern recognition, computational linguistics, computational biology and speech recognition. There is no uniform literature on the subject and one can find many papers with original definitions or points of view. This makes research in this subject very hard, mainly for a beginner or someone who does not wish to become a specialist but just to find the most suitable ideas for his own research activity. The goal of this paper is to introduce a certain number of papers related with grammatical inference. Some of these papers are essential and should constitute a common background to research in the area, whereas others are specialized on particular problems or techniques, but can be of great help on specific tasks.     

Derivatives of tree sets with applications to grammatical inference

Tree automata generalize the notion of a finite automaton working on strings to that of a finite automaton operating on trees. Most results for finite automata have been extended to tree automata. In this paper we introduce tree derivatives which extend the concept of Brzozowski's string derivatives. We use tree derivatives for minimizing and characterizing tree automata. Tree derivatives are used as a basis of inference of tree automata from finite samples of trees. Our method compares tree derivative sets and infers a tree automaton based on the amount of overlap between the derivative sets. Several of the limitations present in the tree inference techniques by Brayer and Fu and Edwards, Gonzalez, and Thomason are not imposed by our algorithm.     

A grammatical inference for harmonic linear languages

We propose an effective algorithm to infer linear grammars from given finite sample sets. It is shown that the algorithm is complete for harmonic linear languages being a superclass of regular languages. A necessary and sufficient condition under which the algorithm converges to an expected grammar is given.     

Stable dynamic backpropagation learning in recurrent neuralnetworks

To avoid unstable phenomenon during the learning process, two new learning schemes, called the multiplier and constrained learning rate algorithms, are proposed in this paper to provide stable adaptive updating processes for both the synaptic and somatic parameters of the network. Based on the explicit stability conditions, in the multiplier method these conditions are introduced into the iterative error index, and the new updating formulations contain a set of inequality constraints. In the constrained learning rate algorithm, the learning rate is updated at each iterative instant by an equation derived using the stability conditions. With these stable dynamic backpropagation algorithms, any analog target pattern may be implemented by a steady output vector which is a nonlinear vector function of the stable equilibrium point. The applicability of the approaches presented is illustrated through both analog and binary pattern storage examples.     

Efficient regular grammatical inference for pattern recognition

A new and simple method for the inference of regular grammars or finite automata is presented. It is based on the analysis of the successive appearances of the terminal symbols in the learning strings. It is shown that for syntactic pattern recognition applications, this method is more efficient than other algorithms already proposed.     

Absolute stability conditions for discrete-time recurrent neuralnetworks

An analysis of the absolute stability for a general class of discrete-time recurrent neural networks (RNN's) is presented. A discrete-time model of RNN's is represented by a set of nonlinear difference equations. Some sufficient conditions for the absolute stability are derived using Ostrowski's theorem and the similarity transformation approach. For a given RNN model, these conditions are determined by the synaptic weight matrix of the network. The results reported in this paper need fewer constraints on the weight matrix and the model than in previously published studies.     

A multiobjective genetic algorithm for obtaining the optimal size of a recurrent neural network for grammatical inference

Grammatical inference has been extensively studied in recent years as a result of its wide field of application, and in turn, recurrent neural networks have proved themselves to be a good tool for grammatical inference. The learning algorithms for these neural networks, however, have been far less studied than those for feed-forward neural networks. Classical training methods for recurrent neural networks suffer from being trapped in local minimal and having a high computational time. In addition, selecting the optimal size of a neural network for a particular application is a difficult task. This suggests that the problems of developing methods to determine optimal topologies and new training algorithms should be studied.In this paper, we present a multi-objective evolutionary algorithm which is able to determine the optimal size of recurrent neural networks in any particular application. This is specially analyzed in the case of grammatical inference: in particular, we study how to establish the optimal size of a recurrent neural network in order to learn positive and negative examples in a certain language, and how to determine the corresponding automaton using a self-organizing map once the training has been completed.     

A survey of grammatical inference in software engineering

Grammatical inference – used successfully in a variety of fields such as pattern recognition, computational biology and natural language processing – is the process of automatically inferring a grammar by examining the sentences of an unknown language. Software engineering can also benefit from grammatical inference. Unlike these other fields, which use grammars as a convenient tool to model naturally occurring patterns, software engineering treats grammars as first-class objects typically created and maintained for a specific purpose by human designers. We introduce the theory of grammatical inference and review the state of the art as it relates to software engineering.     

Lur'e systems with multilayer perceptron and recurrent neuralnetworks: absolute stability and dissipativity

Sufficient conditions for absolute stability and dissipativity of continuous-time recurrent neural networks with two hidden layers are presented. In the autonomous case this is related to a Lur'e system with multilayer perceptron nonlinearity. Such models are obtained after parametrizing general nonlinear models and controllers by a multilayer perceptron with one hidden layer and representing the control scheme in standard plant form. The conditions are expressed as matrix inequalities and can be employed for nonlinear H_∞ control and imposing closed-loop stability in dynamic backpropagation     

Extracting finite-state representations from recurrent neuralnetworks trained on chaotic symbolic sequences

Concerns neural-based modeling of symbolic chaotic time series. We investigate the knowledge induction process associated with training recurrent mural nets (RNN) on single long chaotic symbolic sequences. Even though training RNN to predict the next symbol leaves the standard performance measures such as the mean square error on the network output virtually unchanged, the nets extract a lot of knowledge. We monitor the knowledge extraction process by considering the nets stochastic sources and letting them generate sequences which are then confronted with the training sequence via information theoretic entropy and cross-entropy measures. We also study the possibility of reformulating the knowledge gained by RNN in a compact easy-to-analyze form of finite-state stochastic machines. The experiments are performed on two sequences with different complexities measured by the size and state transition structure of the induced Crutchfield's epsilon-machines (1991, 1994). The extracted machines can achieve comparable or even better entropy and cross-entropy performance. They reflect the training sequence complexity in their dynamical state representations that can be reformulated using finite-state means. The findings are confirmed by a much more detailed analysis of model generated sequences. We also introduce a visual representation of allowed block structure in the studied sequences that allows for an illustrative insight into both RNN training and finite-state stochastic machine extraction processes.