Narrow Results

A new framework is introduced which allows the formulation of difficult structural classification tasks in terms of decision-theoretic-based pattern recognition. It is based on extending the classical formulation of generalized linear discriminant functions so as to permit each given object to have a different vector representation in each class. The proposed extension properly accounts for the corresponding extension of the classical learning techniques of linear discriminant functions in a way such that the convergence of the extended techniques can still be proved. The proposed framework can be considered as a hybrid methodology in which both structural and decision-theoretic pattern recognition are integrated. Furthermore, it can be considered as a means to achieve convenient tradeoffs between the inductive and deductive ways of knowledge acquisition, which can result in rendering tractable the possibly hard original inductive learning problem associated with the given task. The proposed framework and methods are illustrated through their use in two difficult structural classification tasks, showing both the appropriateness and the capability of these methods to obtain useful results.

Recently, a new methodology, referred to as “Morphic Generator Grammatical Inference” (MGGI), has been introduced as a step towards a general methodology for the inference of regular languages. In this paper we consider the application of this methodology to a real problem of automatic speech recognition, thus allowing (and also requiring) the proposed problem to be properly formulated within the canonical framework of syntactic pattern recognition. The results show both the viability and appropriateness of the application of MGGI to the problem considered.

This paper examines several line-drawing pattern recognition methods for handwritten character recognition. They are the picture descriptive language (PDL), Berthod and Maroy (BM), extended Freeman's chain code (EFC), error transformation (ET), tree grammar (TG), and array grammar (AG) methods. A new character recognition scheme that uses improved extended octal codes as primitives is introduced. This scheme offers the advantages of handling flexible sizes, orientations, and variations, the need for fewer learning samples, and lower degree of ambiguity. Finally, the simulation of off-line character recognition by the real-time on-line counterpart is investigated.

This paper presents a real-time constraint-free handprinted character recognition system based on a structural approach. After the preprocessing operation, a chain code is extracted to represent the character. The classification is based on the use of a processor dedicated to string comparison. The average computation time to recognize a character is about 0.07 seconds. During the learning step, the user can define any set of characters or symbols to be recognized by the system. Thus there are no constraints on the handprinting. The experimental tests show a high degree of accuracy (96%) for writer-dependent applications. Comparisons with other system and methods are discussed. We also present a comparison between the processor used in this system and the Wagner and Fischer algorithm. Finally, we describe some applications of the system.

A two-stage design method for artificial neural networks is presented. The first stage is an evolutionary RLS (recursive least squares) algorithm which determines the optimal configuration of the net based on the concept of optimal interpolation. During this stage, the members of a given sample set are processed sequentially and a small consistent subset, constituting what we call prototypes, is selected to form the building blocks of the net. The synaptic weights as well as the internal dimensions of the net are updated recursively as each new prototype is selected. The evolving net at each intermediate step is a modified version of the Optimal Interpolative (OI) net derived in a recent paper by one of the authors. The concept of an evolving network configuration is attractive since it does not require the prescription of a fixed configuration in order to learn the optimal synaptic weights. This can eventually lead to a network architecture which is only as complex as it needs to achieve a required interpolation function.

The second stage is for the fine adjustment of the synaptic weights of the network structure acquired during the first stage. This stage is a two-step iterative optimization procedure using the method of steepest descent. The initial values of the synaptic weights in the iterative search are obtained from the first stage. It is seen that they are indeed very close to the optimal values. Hence, fast convergence during the second stage is guaranteed.

We describe experiments with a versatile pictorial prototype-based learning scheme for 3-D object recognition. The Generalized Radial Basis Function (GRBF) scheme seems to be amenable to realization in biophysical hardware because the only kind of computation it involves can be effectively carried out by combining receptive fields. Furthermore, the scheme is computationally attractive because it brings together the old notion of a "grandmother" cell and the rigorous approximation methods of regularization and splines.

A method of learning pattern languages in time polynomial in the length of the pattern is introduced. The learning of certain picture languages can then be done by considering them as an interpretation of pattern languages. The learning of Tabled Regular k-Matrix languages describing arrays of symbols is also examined.

There has been much interest in increasing the computational power of neural networks. In addition there has been much interest in “designing” neural networks better suited to particular problems. Increasing the “order” of the connectivity of a neural network permits both. Though order has played a significant role in feedforward neural networks, its role in dynamically driven recurrent networks is still being understood. This work explores the effect of order in learning grammars. We present an experimental comparison of first order and second order recurrent neural networks, as applied to the task of grammatical inference. We show that for the small grammars studied these two neural net architectures have comparable learning and generalization power, and that both are reasonably capable of extracting the correct finite state automata for the language in question. However, for a larger randomly-generated ten-state grammar, second order networks significantly outperformed the first order networks, both in convergence time and generalization capability. We show that these networks learn faster the more neurons they have (our experiments used up to 10 hidden neurons), but that the solutions found by smaller networks are usually of better quality (in terms of generalization performance after training). Second order nets have the advantage that they converge more quickly to a solution and can find it more reliably than first order nets, but that the second order solutions tend to be of poorer quality than those of the first order if both architectures are trained to the same error tolerance. Despite this, second order nets can more successfully extract finite state machines using heuristic clustering techniques applied to the internal state representations. We speculate that this may be due to restrictions on the ability of first order architecture to fully make use of its internal state representation power and that this may have implications for the performance of the two architectures when scaled up to larger problems.

We report on progress in understanding how to build machines which adaptively acquire the language for their task. The generic mechanism in our research has been an information-theoretic connectionist network embedded in a feedback control system. In this paper, we investigate the capability of such a network to learn associations between messages and meaningful responses to them as a task increases in size and complexity. Specifically, we consider how one might reflect task structure in a network architecture in order to provide improved generalization capability in language acquisition. We propose a method for constructing networks from component subnetworks, namely a product network, which provides improved generalization by factoring the associations between words and actions through an intermediate layer of semantic primitives. A two-dimensional product network was evaluated in a 1000-action data retrieval system, the object of which is to answer questions about 20 attributes of the 50 states of the USA. The system was tested by 13 subjects over a two-week period, during which over 1000 natural language dialogues were recorded. The experiment was conducted using typed input with unconstrained vocabulary and syntax. During the course of performing its task, the system acquired over 500 words and retained 92% of what it learned. We provide a description of the system and details on the experimental results.

Learning of certain classes of two-dimensional picture languages is considered in this paper. Linear time algorithms that learn in the limit, from positive data the classes of local picture languages and locally testable picture languages are presented. A crucial step for obtaining the learning algorithm for local picture languages is an explicit construction of a two-dimensional on-line tessellation acceptor for a given local picture language. A polynomial time algorithm that learns the class of recognizable picture languages from positive data and restricted subset queries, is presented in contrast to the fact that this class is not learnable in the limit from positive data alone.

A robotic agent operating in an unknown and complex environment may employ a search strategy of some kind to perform a navigational task such as reaching a given goal. In the process of performing the task, the agent can attempt to discover characteristics of its environment that enable it to choose a more efficient search strategy for that environment. If the agent is able to do this, we can say that it has "learned to navigate" — i.e., to improve its navigational performance. This paper describes how an agent can learn to improve its goal-finding performance in a class of discrete spaces, represented by graphs embedded in the plane. We compare several basic search strategies on two different classes of "random" graphs and show how information collected during the traversal of a graph can be used to classify the graph, thus allowing the agent to choose the search strategy best suited for that graph.

The subject matter of computer vision and pattern recognition can play a useful role in the education of mathematics for students in middle school. New standards in education call for new content relevant to students' lives, and new pedagogical methods involving construction, group work, discovery, and the use of new technology. The project "Mathematics Experiences Through Image Processing" at the University of Washington has developed software and learning activities that enable middle school and high school students to use mathematical tools and concepts to explore some exciting ideas of image processing. This paper describes these materials and discusses how the ideas of computer vision and pattern recognition can be integrated into the curriculum. Not only do we use 2D topics such as digital geometry and edge detection, but also 3D topics such as surface construction and stereogram generation.

In this paper, we report our experiments on feature-based facial expression recognition within an architecture based on a two-layer perceptron. We investigate the use of two types of features extracted from face images: the geometric positions of a set of fiducial points on a face, and a set of multiscale and multiorientation Gabor wavelet coefficients at these points. They can be used either independently or jointly. The recognition performance with different types of features has been compared, which shows that Gabor wavelet coefficients are much more powerful than geometric positions. Furthermore, since the first layer of the perceptron actually performs a nonlinear reduction of the dimensionality of the feature space, we have also studied the desired number of hidden units, i.e. the appropriate dimension to represent a facial expression in order to achieve a good recognition rate. It turns out that five to seven hidden units are probably enough to represent the space of facial expressions. Then, we have investigated the importance of each individual fiducial point to facial expression recognition. Sensitivity analysis reveals that points on cheeks and on forehead carry little useful information. After discarding them, not only the computational efficiency increases, but also the generalization performance slightly improves. Finally, we have studied the significance of image scales. Experiments show that facial expression recognition is mainly a low frequency process, and a spatial resolution of 64 pixels × 64 pixels is probably enough.

This paper deals with computation over dynamical analog systems, exploring applications of chaos. The dynamical system used is an artificial neural network model that can code any symbolic algorithm. Herein, we propose the integration of chaotic dynamics onto this model, to implement computational tasks, namely, a blind search algorithm and a pseudo-random number generator.

The memristor has attracted phenomenal worldwide attention since its debut on 1 May 2008 issue of Nature in view of its many potential applications, e.g. super-dense nonvolatile computer memory and neural synapses. The Hewlett–Packard memristor is a passive nonlinear two-terminal circuit element that maintains a functional relationship between the time integrals of current and voltage, respectively, viz. charge and flux. In this paper, we derive several nonlinear oscillators from Chua's oscillators by replacing Chua's diodes with memristors.

Memristors are promising next-generation memory candidates that are nonvolatile, possess low power requirements and are capable of nanoscale fabrication. In this article, we physically realize and describe the use of organic memristors in designing stateful boolean logic gates for the AND OR and NOT operations. The output of these gates is analog and dependent on the length of time that suitable charge is applied to the inputs, displaying a learning property. Results may be also interpreted in a traditional binary manner through the use of a suitable thresholding function at the output. The memristive property of the gate allows for the production of analog outputs that vary based on the charge-dependent nonvolatile state of the memristor. We provide experimental results of physical fabrication of three types of logic gate. A simulation of a one-bit full adder comprised of memristive logic gates is also included, displaying varying response to two distinct input patterns.

Estimation by analogy (EBA) predicts effort for a new project by learning from the performance of former projects. This is done by aggregating effort information of similar projects from a given historical data set that contains projects, or objects in general, and attributes describing the objects. While this has been successful in general, existing research results have shown that a carefully selected subset, as well as weighting, of the attributes may improve the performance of the estimation methods.

In order to improve the estimation accuracy of our former proposed EBA method AQUA, which supports data sets that have non-quantitative and missing values, an attribute weighting method using rough set analysis is proposed in this paper. AQUA is thus extended to AQUA⁺ by incorporating the proposed attribute weighting and selection method. Better prediction accuracy was obtained by AQUA⁺ compared to AQUA for five data sets. The proposed method for attribute weighting and selection is effective in that (1) it supports data sets that have non-quantitative and missing values; (2) it supports attribute selection as well as weighting, which are not supported simultaneously by other attribute selection methods; and (3) it helps AQUA⁺ to produce better performance.

This work aims at giving an updated vision on the successful combination between Metaheuristics and Software Engineering (SE). Mostly during the 90s, varied groups of researchers dealing with search, optimization, and learning (SOL) met SE researchers, all of them looking for a quantified manner of modeling and solving problems in the software field. This paper will discuss on the construction, assessment, and exploitation tasks that help in making software programs a scientific object, subject to automatic study and control. We also want to show with several case studies how the quantification of software features and the automatic search for bugs can improve the software quality process, which eases compliance to ISO/IEEE standards. In short, we want to build intelligent automatic tools that will upgrade the quality of software products and services. Since we approach this new field as a cross-fertilization between two research domains, we then need to talk not only on metaheuristics for SE (well known by now), but also on SE for metaheuristics (not so well known nowadays). In summary, we will discuss here with three time horizons in mind: the old times [before the term search-based SE (SBSE) was used for this], the recent years on SBSE, and the many avenues for future research/development. A new body of knowledge in SOL and SE exists internationally, which is resulting in a new class of researchers able of building intelligent techniques for the benefit of software, that is, of modern societies.

This paper deals with the modeling and simulation of swarms viewed as a living, hence complex, system. The approach is based on methods of kinetic theory and statistical mechanics, where interactions at the microscopic scale are nonlinearly additive and modeled by stochastic games.

This paper presents a development of the so-called kinetic theory for active particles to the modeling of living, hence complex, systems localized in networks. The overall system is viewed as a network of interacting nodes, mathematical equations are required to describe the dynamics in each node and in the whole network. These interactions, which are nonlinearly additive, are modeled by evolutive stochastic games. The first conceptual part derives a general mathematical structure, to be regarded as a candidate towards the derivation of models, suitable to capture the main features of the said systems. An application on opinion formation follows to show how the theory can generate specific models.