International Journal on Artificial Intelligence Tools

In this paper, we present a bootstrapping algorithm for Word Sense Disambiguation which succeeds in disambiguating a subset of the words in the input text with very high precision. It uses WordNet and a semantic tagged corpus, for the purpose of identifying the correct sense of the words in a given text. The bootstrapping process initializes a set of ambiguous words with all the nouns and verbs in the text. It then applies various disambiguation procedures and builds a set of disambiguated words: new words are sense tagged based on their relation to the already disambiguated words, and then added to the set. This process allows us to identify, in the original text, a set of words which can be disambiguated with high precision; 55% of the verbs and nouns are disambiguated with an accuracy of 92%.

Discrete optimization problems are usually NP hard. The structural characteristics of these problems significantly dictate the solution landscape. In this paper, we explore a structure-based approach to solving these kinds of problems. We use a reinforcement learning system to adaptively learn the structural characteristics of the problem, hereby decomposing the problem into several subproblems. Based on these structural characteristics, we develop a Genetic Algorithm by using structural operations to recombine these subproblems together to solve the problem. The reinforcement learning system directs the GA. We test our algorithm on the Tactical Fixed Interval Scheduling Problem(TFISP) which is the problem of determining the minimum number of parallel non-identical machine such that a feasible schedule exists for a given set of jobs. This work continues our work in exploiting structure for optimization.

To reduce the complexity of studying a parallel mechanism for natural language learning and understanding which supports both utterance and discourse processing, we propose a computational model demonstrating the performance of a young language user just starting to construct one and two word utterances. This model is constructed using discoveries from both connectionism and symbolic research which guided the construction of our own cognitive modeling system. This system consists of 1) a cognitive theory, 2) a cognitive and a computational architecture, and 3) the support environment necessary to construct concurrent symbolic-based cognitive models using a multi-agent environment. After providing the discourse performance of the resulting model, we also address the pragmatic consideration of building and supporting the resulting modeling system and language model on a cluster of SMP computers.

It is widely accepted that more knowledge means more intelligence. In many knowledge intensive applications, it is necessary to have extensive domain-specific knowledge in addition to general-purpose knowledge bases. This paper presents a methodology for discovering domain-specific concepts and relationships in an attempt to extend WordNet. The method was tested on five seed concepts selected from the financial domain: interest rate, stock market, inflation, economic growth, and employment. Queries were formed with each of these concepts and a corpus of 5000 sentences was extracted automatically from the Internet and TREC-8 corpora. On this corpus, the system discovered a total of 264 new concepts not defined in WordNet, of which 221 contain the seeds and 43 are other related concepts. The system also discovered 64 relationships that link these concepts with either WordNet concepts or with each other. The relationships were extracted with the help of 22 distinct lexico-syntactic patterns representing four semantic relations. It takes the system approximately 40 minutes per seed working in interactive mode to discover the new concepts and relationships on the 5000 sentence corpus.

Neurules are a kind of hybrid rules integrating neurocomputing and production rules. Each neurule is represented as an adaline unit. Thus, the corresponding neurule base consists of a number of autonomous adaline units (neurules). Due to this fact, a modular and natural knowledge base is constructed, in contrast to existing connectionist knowledge bases. In this paper, we present a method for generating neurules from empirical data. To overcome the difficulty of the adaline unit to classify non-separable training examples, the notion of 'closeness' between training examples is introduced. In case of a training failure, two subsets of 'close' examples are produced from the initial training set and a copy of the neurule for each subset is trained. Failure of training any copy, leads to production of further subsets as far as success is achieved.

Hierarchical conceptual clustering has proven to be a useful, although greatly under-explored data mining technique. A graph-based representation of structural information combined with a substructure discovery technique has been shown to be successful in knowledge discovery. The SUBDUE substructure discovery system provides the advantages of both approaches. This work presents SUBDUE and the development of its clustering functionalities. Several examples are used to illustrate the validity of the approach both in structured and unstructured domains, as well as compare SUBDUE to earlier clustering algorithms. Results show that SUBDUE successfully discovers hierarchical clusterings in both structured and unstructured data.

The noise intolerance and the storage requirements of Nearest-Neighbor-based algorithms are the two main obstacles to their use for solving complex classification tasks. From the beginning of the 70's (with Hart and Gates), many methods have been proposed for dealing with these problems, by eliminating mislabeled instances, and selecting relevant prototypes. These models often have the distinctive feature of optimizing during the process the accuracy. In this paper, we present a new original approach which adapts the properties of boosting (which optimizes an other criterion) to the prototype selection field. While in a standard boosting algorithm the final classifier combines a set of weak hypotheses, where each one is a classifier built according to a given distribution over the training data, we defined in our approach each weak hypothesis as a single weighted prototype. The distribution update (a key step of boosting) and the criterion optimized during the process are slightly modified to allow an efficient adaptation of boosting to the prototype selection field.

In order to show the interest of our new algorithm, called PSBOOST, we achieved a wide experimental study, comparing our procedure with the state-of-the-art prototype selection algorithms. Taking into account many performance measures, such as storage reduction, noise tolerance, generalization accuracy and learning speed, we can claim that PSBOOST seems to be very efficient by providing a good balance between all these performance measures. A statistical analysis is presented to validate all the results.

The design of an optimal Bayesian classifier for multiple features is dependent on the estimation of multidimensional joint probability density functions and therefore requires a design sample size that increases exponentially with the number of dimensions. A method was developed that combines classification decisions from marginal density functions using an additional classifier. Unlike voting methods, this method can select a more appropriate class than the ones selected by the marginal classifiers, thus "overriding" their decisions. It is shown that this method always exhibits an asymptotic probability of error no worse than the probability of error of the best marginal classifier.

Automated theorem proving with connection tableau calculi imposes search problems in tremendous search spaces. In this paper, we present a new approach to search space reduction in connection tableau calculi. In our approach structurally similar parts of the search space are compressed by means of disjunctive constraints. We describe the necessary changes of the calculus, and we develop elaborate techniques for an efficient constraint processing. Moreover, we present an experimental evaluation of our approach.

This paper describes a knowledge-based methodology of mining textual answers from large collections of texts. We present an answer engine capable of providing answers to any question posed in natural language, regardless of the domain of interest. The answers are produced by combining semantic data from question taxonomies with information abductively inferred from texts. The high precision of the retrieved answers is due to novel, efficient knowledge processing techniques.

We first revisit a problem from the literature, that of partitioning a given set of numbers into subsets such that their sums are as nearly equal as possible. We devise a new genetic algorithm, Eager Breeder, for this problem. The algorithm is distinctive in its novel and aggressive way of extracting parental genetic material when forming a child partition, and its results are a substantial improvement upon prior results from the literature. Then we extend our algorithm to the more general setting, of partitioning a set in the case that the environment provides us a measure of the fitness of individual subsets in the partition. We apply the extension to two artificial problems, one with a targeted partition whose subsets are of very diverse sizes, and one whose subsets are the same size. Finally, we apply our approach to several map coloring problems, and obtain good results there as well. In our different stages of work, we exploit different heuristics, which are attuned to the particular partitioning problem under attack.

Identification of affine deformed and simultaneously blur degraded images is an important task in pattern analysis. In this paper, we introduce an image normalization approach to derive blur and affine combined moment invariants (BACIs). In our scheme, the lowest order blur invariant moments are used as the normalization constraints and an appropriate normalization procedure is designed to guarantee that the constraints used in each step should not be affected in the subsequent normalization steps. A neural network (NN) model is then employed to classify the degraded images using the proposed BACIs. Experimental results show that the system has high classification accuracy.

The paper presents a framework to induction of concept hierarchies based on consistent integration of metric and similarity-based approaches. The hierarchies used are subsumption lattices induced by the least general generalization operator (lgg) commonly used in inductive learning. Using some basic results from lattice theory the paper introduces a semantic distance measure between objects in concept hierarchies and discusses its applications for solving concept learning and conceptual clustering tasks. Experiments with well known ML datasets represented in three types of languages - propositional (attribute-value), atomic formulae and Horn clauses, are also presented.

Hard discrete optimization problems using randomized methods such as genetic algorithms require large numbers of samples from the solution space. Each candidate sample/solution must be evaluated using the target fitness/energy function being optimized. Such fitness computations are a bottleneck in sampling methods such as genetic algorithms. We observe that the caching of partial results from these fitness computations can reduce this bottleneck. We provide a rigorous analysis of the run-times of GAs with and without caching. By representing fitness functions as classic Divide and Conquer algorithms, we provide a formal model to predict the efficiency of caching GAs vs. non-caching GAs. Finally, we explore the domain of protein folding with GAs and demonstrate that caching can significantly reduce expected run-times through both theoretical and extensive empirical analyses.