Breadth-first search strategies for trie-based syntactic pattern recognition

Dictionary-based syntactic pattern recognition of strings attempts to recognize a transmitted string X ^*, by processing its noisy version, Y, without sequentially comparing Y with every element X in the finite, (but possibly, large) dictionary, H. The best estimate X ⁺ of X ^*, is defined as that element of H which minimizes the generalized Levenshtein distance (GLD) D(X, Y) between X and Y, for all X ∈H. The non-sequential PR computation of X ⁺ involves a compact trie-based representation of H. In this paper, we show how we can optimize this computation by incorporating breadth first search schemes on the underlying graph structure. This heuristic emerges from the trie-based dynamic programming recursive equations, which can be effectively implemented using a new data structure called the linked list of prefixes that can be built separately or “on top of” the trie representation of H. The new scheme does not restrict the number of errors in Y to be merely a small constant, as is done in most of the available methods. The main contribution is that our new approach can be used for generalized GLDs and not merely for 0/1 costs. It is also applicable when all possible correct candidates need to be known, and not just the best match. These constitute the cases when the “cutoffs” cannot be used in the DFS trie-based technique (Shang and Merrettal in IEEE Trans Knowl Data Eng 8(4):540–547, 1996). The new technique is compared with the DFS trie-based technique (Risvik in United Patent 6377945 B1, 23 April 2002; Shang and Merrettal in IEEE Trans Knowl Data Eng 8(4):540–547, 1996) using three large and small benchmark dictionaries with different errors. In each case, we demonstrate marked improvements with regard to the operations needed up to 21%, while at the same time maintaining the same accuracy. Additionally, some further improvements can be obtained by introducing the knowledge of the maximum number or percentage of errors in Y.

Bi-directional graph search strategies for speech recognition

We describe a new search algorithm for speech recognition which applies the monotone graph search procedure to the problem of building a word graph. A first backward pass provides a method for estimating the word boundary times and phone segment boundary times needed to build the word graph using either the 1-phone or 2-phone lookahead assumptions. It also provides a heuristic for the search which satisfies the monotonicity condition. A second backward pass applies forward–backward pruning to the word graph. We show how the search can be made to run very quickly if the 1-phone lookahead assumption holds. We present the results of experiments performed on the 5000-word speaker-independentWall Street Journaltask under both the 1-phone and 2-phone lookahead assumptions. These results show that the 1-phone lookahead assumption leads to unacceptably large error rates for speaker-independent recognition using current acoustic phonetic modelling techniques. Finally, we give an account of the methods we have developed to process speech data in successive blocks so as to address the real-time issue and to control the memory requirements of the search.     

Visible models for interactive pattern recognition

The exchange of information between human and machine has been a bottleneck in interactive visual classification. The visible model of an object to be recognized is an abstraction of the object superimposed on its picture. It is constructed by the machine but it can be modified by the operator. The model guides the extraction of features from the picture. The classes are rank ordered according to the similarities (in the hidden high-dimensional feature space) between the unknown picture and a set of labeled reference pictures. The operator can either accept one of the top three candidates by clicking on a displayed reference picture, or modify the model. Model adjustment results in the extraction of new features, and a new rank ordering. The model and feature extraction parameters are re-estimated after each classified object, with its model and label, is added to the reference database. Pilot experiments show that interactive recognition of flowers and faces is more accurate than automated classification, faster than unaided human classification, and that both machine and human performance improve with use.     

Problem-solving strategies for DSS design

For a successful design and implementation of DSS, competent understanding of decision-making processes in organizational settings and sensitivity to the interpersonal and organizational dimensions of the relationship between decision-makers and DSS designers are essential. Towards this end, a three-faceted strategy is broadly outlined and proposed. The strategy encompasses (a) a diagnostic attitude to the empirical tasks and contextual properties of decision-making, (b) emphasis on decision-makers rather than on decisions, and (c) the concept of DSS design as a joint undertaking for organizational problem-solving.     

Language models and search algorithms for real-time speech recognition

In this paper, “continuous speech recognition” problem is given a clear mathematical formulation as the search for that sequence of basic speech units that best fits the input acoustic pattern. For this purpose spoken language models in the form of hierarchical transition networks are introduced, where lower level subnetworks describe the basic units as possible sequences of spectral states. The units adopted in this paper are either whole words or smaller subword elements, called diphones. The recognition problem thus becomes that of finding the best path through the network, a task carried out by the linguistic decoder. By using this approach, knowledge sources at different levels are strongly integrated. In this way, early decision making based on partial information (in particular any segmentation operation or the speech/silence distinction) is avoided; usually this is a significant source or errors. Instead, decisions are deferred to the linguistic decoder, which possesses all the necessary pieces of information. The properties that a linguistic decoder must possess in order to operate in real-time are listed, and then a best-few algorithm with partial traceback of explored paths, satisfying the above requisites, is described. In particular, the amount of storage needed is almost constant for any sentence length, the computation is approximately linear with sentence length, and the interpretation of early words in a sentence may be possible long before the speaker has finished talking. Experimental results with two systems, one with words and the other with diphones as basic speech units, are reported. Finally, relative merits of words and diphones are discussed, taking into account aspects such as the storage and computing time requirements, their relative ability to deal with phonological variations and to discriminate between similar words, their speaker adaptation capability, and the ease with which it is possible to change the vocabulary and the language dependencies.     

On deformable models for visual pattern recognition

This paper reviews model-based methods for non-rigid shape recognition. These methods model, match and classify non-rigid shapes, which are generally problematic for conventational algorithms using rigid models. Issues including model representation, optimization criteria formulation, model matching, and classification are examined in detail with the objective to provide interested researchers a roadmap for exploring the field. This paper emphasizes on 2D deformable models. Their potential applications and future research directions, particularly on deformable pattern classification, are discussed.     

A search technique for pattern recognition using relative distances

A technique for creating and searching a tree of patterns using relative distances is presented. The search is conducted to find patterns which are nearest neighbors of a given test pattern. The structure of the tree is such that the search time is proportional to the distance between the test pattern and its nearest neighbor, which suggests the anomalous possibility that a larger tree, which can be expected on average to contain closer neighbors, can be searched faster than a smaller tree. The technique has been used to recognize OCR digit samples derived from NIST data at an accuracy rate of 97% using a tree of 7,000 patterns     

Robust and efficient multiclass SVM models for phrase pattern recognition

Phrase pattern recognition (phrase chunking) refers to automatic approaches for identifying predefined phrase structures in a stream of text. Support vector machines (SVMs)-based methods had shown excellent performance in many sequential text pattern recognition tasks such as protein name finding, and noun phrase (NP)-chunking. Even though they yield very accurate results, they are not efficient for online applications, which need to handle hundreds of thousand words in a limited time. In this paper, we firstly re-examine five typical multiclass SVM methods and the adaptation to phrase chunking. However, most of them were inefficient when the number of phrase types scales. We thus introduce the proposed two new multiclass SVM models that make the system substantially faster in terms of training and testing while keeps the SVM accurate. The two methods can also be applied to similar tasks such as named entity recognition and Chinese word segmentation. Experiments on CoNLL-2000 chunking and Chinese base-chunking tasks showed that our method can achieve very competitive accuracy and at least 100 times faster than the state-of-the-art SVM-based phrase chunking method. Besides, the computational time complexity and the time cost analysis of our methods were also given in this paper.     

Growing subspace pattern recognition methods and theirneural-network models

In statistical pattern recognition, the decision of which features to use is usually left to human judgment. If possible, automatic methods are desirable. Like multilayer perceptrons, learning subspace methods (LSMs) have the potential to integrate feature extraction and classification. In this paper, we propose two new algorithms, along with their neural-network implementations, to overcome certain limitations of the earlier LSMs. By introducing one cluster at a time and adapting it if necessary, we eliminate one limitation of deciding how many clusters to have in each class by trial-and-error. By using the principal component analysis neural networks along with this strategy, we propose neural-network models which are better in overcoming another limitation, scalability. Our results indicate that the proposed classifiers are comparable to classifiers like the multilayer perceptrons and the nearest-neighbor classifier in terms of classification accuracy. In terms of classification speed and scalability in design, they appear to be better for large-dimensional problems.     

Natural strategies for search

In recent years a considerable amount of natural computing research has been undertaken to exploit the analogy between, say, searching a given problem space for an optimal solution and the natural process of foraging for food. Such analogies have led to useful solutions in areas such as optimisation, prominent examples being ant colony systems and particle swarm optimisation. However, these solutions often rely on well defined fitness landscapes that are not always be available in more general search scenarios. This paper surveys a wide variety of behaviours observed within the natural world, and aims to highlight general cooperative group behaviours, search strategies and communication methods that might be useful within a wider computing context, beyond optimisation, where information from the fitness landscape may be sparse, but new search paradigms could be developed that capitalise on research into biological systems that have developed over millennia within the natural world.     

Improving multiclass pattern recognition by the combination of two strategies

We present a new method of multiclass classification based on the combination of one-vs-all method and a modification of one-vs-one method. This combination of one-vs-all and one-vs-one methods proposed enforces the strength of both methods. A study of the behavior of the two methods identifies some of the sources of their failure. The performance of a classifier can be improved if the two methods are combined in one, in such a way that the main sources of their failure are partially avoided.     

Combined pattern search optimization of feature extraction and classification parameters in facial recognition

Constantly, the assumption is made that there is an independent contribution of the individual feature extraction and classifier parameters to the recognition performance. In our approach, the problems of feature extraction and classifier design are viewed together as a single matter of estimating the optimal parameters from limited data. We propose, for the problem of facial recognition, a combination between an Interest Operator based feature extraction technique and a k-NN statistical classifier having the parameters determined using a pattern search based optimization technique. This approach enables us to achieve both higher classification accuracy and faster processing time.     

On optimizing syntactic pattern recognition using tries and AI-based heuristic-search strategies.

This paper deals with the problem of estimating, using enhanced artificial-intelligence (AI) techniques, a transmitted string X* by processing the corresponding string Y, which is a noisy version of X*. It is assumed that Y contains substitution, insertion, and deletion (SID) errors. The best estimate X+ of X* is defined as that element of a dictionary H that minimizes the generalized Levenshtein distance (GLD) D (X, Y) between X and Y, for all X epsilon H. In this paper, it is shown how to evaluate D (X, Y) for every X epsilon H simultaneously, when the edit distances are general and the maximum number of errors is not given a priori, and when H is stored as a trie. A new scheme called clustered beam search (CBS) is first introduced, which is a heuristic-based search approach that enhances the well-known beam-search (BS) techniques used in AI. The new scheme is then applied to the approximate string-matching problem when the dictionary is stored as a trie. The new technique is compared with the benchmark depth-first search (DFS) trie-based technique (with respect to time and accuracy) using large and small dictionaries. The results demonstrate a marked improvement of up to 75% with respect to the total number of operations needed on three benchmark dictionaries, while yielding an accuracy comparable to the optimal. Experiments are also done to show the benefits of the CBS over the BS when the search is done on the trie. The results also demonstrate a marked improvement (more than 91%) for large dictionaries.     

Optimal linear feature selection for a general class of statistical pattern recognition models

A dimension reduction method proposed by Odell (1979) and Decell, Odell, and Coberly (1981) for Gaussian models is extended to a general class of density functions known as θ-generalized normal densities. Necessary and sufficient conditions for the existence of a dimension reduction matrix which preserves the original Bayes classification regions is derived. Moreover, an explicit expression for the compression matrix is given.     

XML strategies for legacy database search

Over the past few years, XML (Extensible Markup Language) has become the standard for data and document interchange between distributed systems. With the continuing proliferation of the Internet, XML has also become a key technology for transactional e-business. A large percentage of Internet interactions, however, involves searching through documents, Web pages, databases, and other information resources. This article explores some of the ways XML can improve these types of searches. It focuses particularly on searches through legacy databases and on the changes you can make to your legacy systems to effectively exploit XML.     

Some methods for pattern recognition

The present study is dedicated to pattern recognition of alphabetical and numerical symbols. A recognition method based on modification of Hausdorff metrics is presented; then, another method named the method of radial neighborhoods is described. A series of experiments on test patterns are conducted.     

MicroARTMAP for pattern recognition problems

Pattern recognition is an important aspect of a dominant technology such as machine intelligence. Domain specific fuzzy-neuro models particularly for the ‘black box’ implementation of pattern recognition applications have recently been investigated. In this paper, Sanchez’s MicroARTMAP has been discussed as a pattern recognizer/classifier for the image processing problems. The model inherently recognizes only noise free patterns and in case of noise perturbations (rotations/scaling/translation) misclassifies the images. To tackle this problem, a conventional Hu’s moment based rotation/scaling/translation invariant feature extractor has been employed. The potential of this model has been demonstrated on two problems, namely, recognition of alphabets and words and prediction of load from yield pattern of elasto-plastic analysis. The second example concerns with color images dealing with colored patterns. MicroARTMAP is also applied to other two civil engineering problems, namely (a) Indian Standard (IS) classification of soil and (b) prediction of earthquake parameters from the response spectrum in which no feature extractor step is necessary.