International Journal on Artificial Intelligence Tools

Enterprise corpora contain evidence of what employees work on and therefore can be used to automatically find experts on a given topic. We present a general approach for representing the knowledge of a potential expert as a mixture of language models from associated documents. First we retrieve documents given the expert's name using a generative probabilistic technique and weight the retrieved documents according to expert-specific posterior distribution. Then we model the expert indirectly through the set of associated documents, which allows us to exploit their underlying structure and complex language features. Experiments show that our method has excellent performance on the expert search task of the TREC Enterprise track and that it effectively collects and combines evidence for expertise in a heterogeneous collection.

This paper introduces a stochastic graph-based algorithm, called OutRank, for detecting outliers in data. We consider two approaches for constructing a graph representation of the data, based on the object similarity and number of shared neighbors between objects. The heart of this approach is the Markov chain model that is built upon this graph, which assigns an outlier score to each object. Using this framework, we show that our algorithm is more robust than the existing outlier detection schemes and can effectively address the inherent problems of such schemes. Empirical studies conducted on both real and synthetic data sets show that significant improvements in detection rate and false alarm rate are achieved using the proposed framework.

Instruction scheduling is one of the most important steps for improving the performance of object code produced by a compiler. A fundamental problem that arises in instruction scheduling is to find a minimum length schedule for a basic block — a straight-line sequence of code with a single entry point and a single exit point — subject to precedence, latency, and resource constraints. Solving the problem exactly is NP-complete, and heuristic approaches are currently used in most compilers. In contrast, we present a scheduler that finds provably optimal schedules for basic blocks using techniques from constraint programming. In developing our optimal scheduler, the key to scaling up to large, real problems was in the development of preprocessing techniques for improving the constraint model. We experimentally evaluated our optimal scheduler on the SPEC 2000 integer and floating point benchmarks. On this benchmark suite, the optimal scheduler was very robust — all but a handful of the hundreds of thousands of basic blocks in our benchmark suite were solved optimally within a reasonable time limit — and scaled to the largest basic blocks, including basic blocks with up to 2600 instructions. This compares favorably to the best previous exact approaches.

The goal of spatial co-location pattern mining is to find subsets of spatial features frequently located together in spatial proximity. Example co-location patterns include services requested frequently and located together from mobile devices (e.g., PDAs and cellular phones) and symbiotic species in ecology (e.g., Nile crocodile and Egyptian plover). Spatial clustering groups similar spatial objects together. Reusing research results in clustering, e.g. algorithms and visualization techniques, by mapping co-location mining problem into a clustering problem would be very useful. However, directly clustering spatial objects from various spatial features may not yield well-defined co-location patterns. Clustering spatial objects in each layer followed by overlaying the layers of clusters may not applicable to many application domains where the spatial objects in some layers are not clustered.

In this paper, we propose a new approach to the problem of mining co-location patterns using clustering techniques. First, we propose a novel framework for co-location mining using clustering techniques. We show that the proximity of two spatial features can be captured by summarizing their spatial objects embedded in a continuous space via various techniques. We define the desired properties of proximity functions compared to similarity functions in clustering. Furthermore, we summarize the properties of a list of popular spatial statistical measures as the proximity functions. Finally, we show that clustering techniques can be applied to reveal the rich structure formed by co-located spatial features. A case study on real datasets shows that our method is effective for mining co-locations from large spatial datasets.

As one of the most successful recommender systems, collaborative filtering (CF) algorithms are required to deal with high sparsity and high requirement of scalability amongst other challenges. Bayesian networks (BNs), one of the most frequently used classifiers, can be used for CF tasks. Previous works on applying BNs to CF tasks were mainly focused on binary-class data, and used simple or basic Bayesian classifiers.^1,2 In this work, we apply advanced BNs models to CF tasks instead of simple ones, and work on real-world multi-class CF data instead of synthetic binary-class data. Empirical results show that with their ability to deal with incomplete data, the extended logistic regression on tree augmented naïve Bayes (TAN-ELR)³ CF model consistently performs better than the traditional Pearson correlation-based CF algorithm for the rating data that have few items or high missing rates. In addition, the ELR-optimized BNs CF models are robust in terms of the ability to make predictions, while the robustness of the Pearson correlation-based CF algorithm degrades as the sparseness of the data increases.

The duality between document and word clustering naturally leads to the consideration of storing the document dataset in a bipartite. With documents and words modeled as vertices on two sides respectively, partitioning such a graph yields a co-clustering of words and documents. The topic of each cluster can then be represented by the top words and documents that have highest within-cluster degrees. However, such claims may fail if top words and documents are selected simply because they are very general and frequent. In addition, for those words and documents across several topics, it may not be proper to assign them to a single cluster. In other words, to precisely capture the cluster topic, we need to identify those micro-sets of words/documents that are similar among themselves and as a whole, representative of their respective topics. Along this line, in this paper, we use hyperclique patterns, strongly affiliated words/documents, to define such micro-sets. We introduce a new bipartite formulation that incorporates both word hypercliques and document hypercliques as super vertices. By co-preserving hyperclique patterns during the clustering process, our experiments on real-world data sets show that better clustering results can be obtained in terms of various external clustering validation measures and the cluster topic can be more precisely identified. Also, the partitioned bipartite with co-preserved patterns naturally lends itself to different clustering-related functions in search engines. To that end, we illustrate such an application, returning clustered search results for keyword queries. We show that the topic of each cluster with respect to the current query can be identified more accurately with the words and documents from the patterns than with those top ones from the standard bipartite formulation.

We propose a specification-driven approach to Web service composition. Our framework allows the users (or service developers) to start with a high-level, possibly incomplete specification of a desired (goal) service that is to be realized using a subset of the available component services. These services are represented using labeled transition systems augmented with guards over variables with infinite domains and are used to determine a strategy for their composition that would realize the goal service functionality. However, in the event the goal service cannot be realized using the available services, our approach identifies the cause(s) for such failure which can then be used by the developer to reformulate the goal specification. Thus, the technique supports Web service composition through iterative reformulation of the functional specification. We present a prototype implementation in a tabled-logic programming environment that illustrates the key features of the proposed approach.

This paper aims to improve probability-based ranking (e.g. AUC) under decision-tree paradigm. We observe the fact that probability-based ranking is to sort samples in terms of their class probabilities. Therefore, ranking is a relative evaluation metric among those samples. This motivates us to use a lazy learner to explicitly yield a set of unique class probabilities for a testing sample based on its similarities to the training samples within its neighborhood. We embed lazy learners at the leaves of a decision tree to give class probability assignments. This results in the first model, named Lazy Distance-based Tree (LDTree). Then we further improve this model by continuing to grow the tree for the second time, and call the resulting model Eager Distance-based Tree (EDTree). In addition to the benefits of lazy learning, EDTree also takes advantage of the finer resolution of a large tree structure. We compare our models with C4.5, C4.4 and their variants in AUC on a large suite of UCI sample sets. The improvement shows that our method follows a new path that leads to better ranking performance.

In order for an autonomous agent to behave robustly in a variety of environments, it must have the ability to learn approximations to many different functions. The function approximator used by such an agent is subject to a number of constraints that may not apply in a traditional supervised learning setting. Many different function approximators exist and are appropriate for different problems. This paper proposes a set of criteria for function approximators for autonomous agents. Additionally, for those problems on which polynomial regression is a candidate technique, the paper presents an enhancement that meets these criteria. In particular, using polynomial regression typically requires a manual choice of the polynomial's degree, trading off between function accuracy and computational and memory efficiency. Polynomial Regression with Automated Degree (PRAD) is a novel function approximation method that uses training data to automatically identify an appropriate degree for the polynomial. PRAD is fully implemented. Empirical tests demonstrate its ability to efficiently and accurately approximate both a wide variety of synthetic functions and real-world data gathered by a mobile robot.

In this paper, we present an adaptive appearance based face recognition framework that combines the efficiency of global approaches and the robustness of local approaches together. The framework uses a novel eye locator to select an appropriate scheme for appearance based recognition. The eye locator first locates eye candidates via a new strength assignment, determined by the dissimilarity between the local appearance of an image point and the appearance of its neighboring points. Then the eye locator applies a simple but flexible model (half-circle snake) to the local context of the eye candidates in order to either refine the location of an eye candidate or discard non-eye candidates. We show the performance of our framework by testing on challenging face datasets containing extreme expressions, severe occlusions, and varied lighting conditions.

Standard tabu search methods are based on the complete exploration of current solution neighborhood. However, for some problems due to the neighborhood size or to the fitness evaluation complexity, the total exploration of the neighborhood is impractical. The main purpose of this paper is to propose a local search method with no enumeration procedure. In other words, a single solution is examined at each iteration and retained for the future iterations. The idea is to randomly select one solution among a sub-set of the neighborhood of the current one. An adaptive exploration of neighborhood, using extension and restriction mechanisms represented by loop detection and tabu list structure, determines this sub-set. This approach is applied to the K-coloring problem and evaluated on standard benchmarks like DIMACS. The objective is to show how a generic method, without full neighborhood exploration, degradation control and problem-oriented operators, provides a very competitive results comparing to the best dedicated algorithms for graph coloring problems published in the literature.

Precedence constraints specify that an activity must finish before another activity starts and hence such constraints play a crucial role in planning and scheduling problems. Many real-life problems also include dependency constraints expressing logical relations between the activities – for example, an activity requires presence of another activity in the plan. For such problems a typical objective is a maximization of the number of activities satisfying the precedence and dependency constraints. In the paper we propose new incremental filtering rules integrating propagation through both precedence and dependency constraints. We also propose a new filtering rule using the information about the requested number of activities in the plan. We demonstrate efficiency of the proposed rules on log-based reconciliation problems and min-cutset problems.

Course Timetabling is a complex problem that cannot be dealt with by using only a few general principles. The various actors (the administrator, the chairman, the instructor and the student) have their own objectives, and these objectives usually conflict. The complexity of the relationships among time slots, classes, classrooms, and instructors makes it difficult to achieve a feasible solution. In this article, we propose an artificial intelligence approach that integrates expert systems and constraint programming to implement a course timetabling system. Expert systems are utilized to incorporate knowledge into the timetabling system and to provide a reasoning capability for knowledge deduction. Separating out the knowledge base, the facts, and the inference engine in expert systems provides greater flexibility in supporting changes. The constraint hierarchy and the constraint network are utilized to capture hard and soft constraints and to reason about constraints by using constraint satisfaction and relaxation techniques. In addition, object-oriented software engineering is applied to improve the development and maintenance of the course timetabling system. A course timetabling system in the Department of Computer Science and Information Engineering at the National Changhua University of Education (NCUE) is used as an illustrative example of the proposed approach.