International Journal on Artificial Intelligence Tools

This paper presents a system based on new operators for handling sets of propositional clauses compactly represented by means of ZBDDs. The high compression power of such data structures allows efficient encodings of structured instances. A specialized operator for the distribution of sets of clauses is introduced and used for performing multiresolution on clause sets. Cut eliminations between sets of clauses of exponential size may then be performed using polynomial size data structures. The ZRES system, a new implementation of the Davis-Putnam procedure of 1960, solves two hard problems for resolution, that are currently out of the scope of the best SAT provers.

For many years, the non-montonic reasoning community has focussed on highly expressive logics. Such logics have turned out to be computationally expensive, and have given little support to the practical use of non-monotonic reasoning. In this work we discuss defeasible logic, a less-expressive but more efficient non-monotonic logic. We report on two new implemented systems for defeasible logic: a query answering system employing a backward-chaining approach, and a forward-chaining implementation that computes all conclusions. Our experimental evaluation demonstrates that the systems can deal with large theories (up to hundreds of thousands of rules). We show that defeasible logic has linear complexity, which contrasts markedly with most other non-monotonic logics and helps to explain the impressive experimental results. We believe that defeasible logic, with its efficiency and simplicity, is a good candidate to be used as a modeling language for practical applications, including modelling of regulations and business rules.

In Artificial Intelligence, Default Logic is recognized as a powerful framework for knowledge representation when one has to deal with incomplete information. Its expressive power is suitable for non monotonic reasoning, but the counterpart is its very high level of theoretical complexity. Today, some operational systems are able to deal with real world applications. However, finding a default logic extension in a practical way is not yet possible in whole generality. This paper which is an extended version of¹⁸ shows how heuristics such as Genetic Algorithms and Local Search techniques can be used and combined to build an automated default reasoning system. We give a general description of the required basic components and we exhibit experimental results.

The selection of an appropriate inducer is crucial for performing effective classification. In previous work we presented a system called NOEMON which relied on a mapping between dataset characteristics and inducer performance to propose inducers for specific datasets. Instance-based learning was used to create that mapping. Here we explore the use of decision trees inducers as the inducers on the meta-learning level. We believe that they posses a set of properties that match the properties of the meta-learning problem that we are trying to solve. The results show that the performance of the system is indeed improved with the use of the decision tree learners.

Multiple approaches have been developed for improving predictive performance of a system by creating and combining various learned models. There are two main approaches to creating model ensembles. This first is to create a set of learned models by applying an algorithm repeatedly to different training sample data, the second applies various learning algorithms to the same sample data. The predictions of the models are then combined accordings to a voting scheme. This paper presents a method for combining models that were developed using numerous samples, modeling algorithms, and modelers and compares it with the alternate approaches. The presented results are based on findings from an ongoing operational data mining initiative with respect to selecting a model set that is best able to meet defined goals from among trained models. The operational goals to be attained in this initiative are to deploy data mining model(s) that maximizes specificity with minimal negative impact to sensitivity. The results of the model combination methods are evaluated with respect to sensitivity and false alarm rates and are then compared against other approaches.

We show how two novel tools in logic programming for AI (namely, continuation-based linear and timeless assumptions, and Datalog grammars) can assist us in producing terse treatments of difficult language processing phenomena. As a proof of concept, we present a concise parser for Datalog grammars (logic grammars where strings are represented with numbered word boundaries rather than as lists of words) that uses assumptions and a combination of left-corner parsing and charting. We then study two test cases of this parser's application: complete constituent coordination, and error diagnosis and correction.

The question addressed in this paper is which types of spatial reference human users employ in the interaction with a robot and how a cognitively adequate model of these strategies can be implemented. In experiments we explored how human users approach an artificial communication partner, which was designed to mimic spatial reference among humans. Our findings show that spatial reference in human-robot interaction differs from natural situations in human-human interaction in seveal respects. For instance, many users unexpectedly employed fine-grained, path-based, instructions rather than specifying the intended goal object of the action directly. If instructions were not successful, participants created less and less complex descriptions. Those users who did specify the goal object were found to employ those kinds of spatial reference strategies implemented in our computational model. In particular, they exploited the presence of several similar objects by perceiving and referring to them linguistically as a group.

In this paper we describe a project (IMPRESS) in which machine learning (ML) tools were created and utilised for the validation of an Air Traffic Control domain theory written in first order logic. During the project, novel techniques were devised for the automated revision of general clause form theories using training examples. These techniques were combined in an algorithm which focused in on the parts of a theory which involve ordinal sorts, and applied geometrical revision operators to repair faulty component parts. While we illustrate the feasibility of applying ML to this area, we conclude that to be effective it must be focused to the application at hand, and used in mixed-initiative mode within a tools environment. The method is illustrated with experimental results obtained during the project.

Efficient algorithms for checking consistency of a set of spatial constraints among spatiotemporal objects are crucial for many practical application systems needing real-time response. This paper is focused on the consistency for directional spatial constraints in a two-dimensional Euclidean space, which is critical in application domains such as geographic information systems, battlefield visualization, transportation, etc. We propose a dimension graph representation to maintain the Euclidean spatial constraints among 2D objects (points, intervals, regions). The basic idea is to project the spatial constraints on both X and Y dimensions, and then to construct a dimension graph on each dimension. The dimension graph representation transforms the problem of consistency checking into the problem of graph cycle detection. Consistency checking for conjunctive constraints can then be achieved in linear time complexity. This approach is much more efficient than competing approaches when there are few disjunctions in the spatial constraints, which are often true in above applications. We also demonstrate that the proposed algorithm can guarantee global consistency.

Supervised feature extraction is used in data dassification and, unlike unsupervised feature extraction, uses class labels to evaluate the quality of the extracted features. It can be computationally inefficient to perform exhaustive searches to find optimal subsets of features. This article proposes an algorithm of supervised linear feature extraction based on the use of multivariate decision trees. The main motivation in proposing this new approach to feature extraction is to decrease computation time required to induce new classifiers required to evaluate every new subset of features. The new feature extraction algorithm proposed here uses an approach similar to the wrapper model method used in feature selection. In order to evaluate the performance of proposed algorithm, several tests with real world data have been performed. The fundamental importance of this new feature extraction method is found in its ability to significantly reduce computational time required to extract features from large database.

This article addresses the issue of acquiring translation rules for machine translation (MT) systems that adopt a transfer approach. These rules aer semantic pattern pairs (SPPs) of the source and target languages. Practical MT systems must additionally contain a huge number of SPPs corresponding to rarely-used predicates and predicate usages. Such SPPs are difficult to automatically acquire with corpus-based methods. To solve this difficulty, this article proposes a method to acquire SPPs by using queries based on a semantic hierarchy. The proposed method asks a lexicographer for the necessary information in order to generalize the conditions of SPPs and then gradually generalizes these conditions. Experimental results show that the proposed method allows the acquisition of more plausible conditions within almost the same time spent for manual generalization.

The problem of model selection in knowledge discovery and data mining—the selection of appropriate discovered patterns/models or algorithms to achieve such patterns/models—is generally a difficult task for the user as it requires meta-knowledge on algorithms/models and model performance metrics. Viewing knowledge discovery as a human-centered process that requires an effective collaboration between the user and the discovery system, our work aims to make model selection in knowledge discovery easier and more effective. For such a collaboration, our solution is to give the user the ability to try easily various alternatives and to compare competing models quantitatively and qualitatively. The basic idea of our solution is to integrate data and knowledge visualization with the knowledge discovery process in order to the support the participation of the user. We introduce the knowledge discovery system D2MS in which several visualization techniques of data and knowledge are developed and integrated into the steps of the knowledge discovery process. The visualizers in D2MS greatly help the user gain better insight in each step of the knowledge discovery process as well the relationship between data and discovered knowledge in the whole process.

The identification of the overlapped objects is a great challenge in object tracking and video data indexing. For this purpose, a backtrack-chain-updation split algorithm is proposed to assist an unsupervised video segmentation method called the "simultaneous partition and class parameter estimation" (SPCPE) algorithm to identify the overlapped objects in the video sequence. The backtrack-chain-updation split algorithm can identify the split segment (object) and use the information in the current frame to update the previous frames in a backtrack-chain manner. The split algorithm provides more accurate temporal and spatial information of the semantic objects so that the semantic objects can be indexed and modeled by multimedia input strings and the multimedia augmented transition network (MATN) model. The MATN model is based on the ATN model that has been used in artificial intelligence (AI) areas for natural language understanding systems, and its inputs are modeled by the multimedia input strings. In this paper, we will show that the SPCPE algorithm together with the backtrack-chain-updation split algorithm can significantly enhance the efficiency of spatio-temporal video indexing by improving the accuracy of multimedia database queries related to semantic objects.