AI 2011: Advances in Artificial Intelligence

XCS is a learning classifier system that combines a reinforcement learning scheme with evolutionary algorithms to evolve a population of classifiers in the form of condition-action rules. In this paper, we investigate the effectiveness of XCS in high-dimensional classification problems where the number of features greatly exceeds the number of data instances – common characteristics of microarray gene expression classification tasks. We introduce a new guided rule discovery mechanisms for XCS, inspired by feature selection techniques commonly used in machine learning. The extracted feature quality information is used to bias the evolutionary operators. The performance of the proposed model is compared with the standard XCS model and a number of well-known machine learning algorithms using benchmark binary classification tasks and gene expression data sets. Experimental results suggests that the guided rule discovery mechanism is computationally efficient, and promotes the evolution of more accurate solutions. The proposed model performs significantly better than comparative algorithms when tackling high-dimensional classification problems.

Time series clustering by

k

-Means algorithm still has to overcome the dilemma of choosing the initial cluster centers. In this paper, we present a new method for initializing the

k

-Means clustering algorithm of time series data. Our initialization method hinges on the use of time series motif information detected by a previous task in choosing

k

time series in the database to be the seeds. Experimental results show that our proposed clustering approach performs better than ordinary

k

-Means in terms of clustering quality, robustness and running time.

This paper presents a classifier which uses a tree-based Neural Network (NN), and uses both, unlabeled and labeled instances. First, we learn the structure of the data distribution in an unsupervised manner. After convergence, and once labeled data become available, our strategy tags each of the clusters according to the evidence provided by the instances. Unlike other neighborhood-based schemes, our classifier uses only a small set of representatives whose cardinality can be much smaller than that of the input set. Our experiments show that, on average, the accuracy of such classifier is reasonably comparable to those obtained by some of the state-of-the-art classification schemes that only use labeled instances during the training phase. The experiments also show that improved levels of accuracy can be obtained by imposing trees with a larger number of nodes.

Rule and tree based classifier learning systems can employ the idea of order on discrete attribute and class values to aid in classification. Much work has been done on using both orders on class values and monotonic relationships between class and attribute orders. In contrast to this, we examine the usefulness of order specifically on attribute values, and present and evaluate three new methods for recovering or discovering such orders, showing that under some circumstances they can significantly improve accuracy. In addition we introduce the use of classifier ensembles that use random value orders as a source of variation, and show that this can also lead to significant accuracy gains.

MITI is a simple and elegant decision tree learner designed for multi-instance classification problems, where examples for learning consist of bags of instances. MITI grows a tree in best-first manner by maintaining a priority queue containing the unexpanded nodes in the fringe of the tree. When the head node contains instances from positive examples only, it is made into a leaf, and any bag of data that is associated with this leaf is removed. In this paper we first revisit the basic algorithm and consider the effect of parameter settings on classification accuracy, using several benchmark datasets. We show that the chosen splitting criterion in particular can have a significant effect on accuracy. We identify a potential weakness of the algorithm—subtrees can contain structure that has been created using data that is subsequently removed—and show that a simple modification turns the algorithm into a rule learner that avoids this problem. This rule learner produces more compact classifiers with comparable accuracy on the benchmark datasets we consider. Finally, we present randomized algorithm variants that enable us to generate ensemble classifiers. We show that these can yield substantially improved classification accuracy.

The amount of user generated content on the Web is growing and identifying high quality content in a timely manner has become a problem. Many forums rely on its users to manually rate content quality but this often results in gathering insufficient rating. Automated quality assessment models have largely evaluated linguistic features but these techniques are less adaptive for the diverse writing styles and terminologies used by different forum communities. Therefore, we propose a novel model that evaluates content, usage, reputation, temporal and structural features of user generated content to address these limitations. We employed a rule learner, a fuzzy classifier and Support Vector Machines to validate our model on three operational forums. Our model outperformed the existing models in our experiments and we verified that our performance improvements were statistically significant.

Using gray-scale texture features has recently become a new trend in supervised machine learning crater detection algorithms. To provide better classification of craters in planetary images, feature subset selection is used to reduce irrelevant and redundant features. Feature selection is known to be NP-hard. To provide an efficient suboptimal solution, three genetic algorithms are proposed to use greedy selection, weighted random selection, and simulated annealing to distinguish discriminate features from indiscriminate features. A significant increase in the classification ability of a Bayesian classifier in crater detection using image texture features.

Modeling of financial time series data by methods of artificial intelligence is difficult because of the extremely noisy nature of the data. A common and simple form of filter to reduce the noise originated in signal processing, the finite impulse response (FIR) filter. There are several of these noise reduction methods used throughout the financial instrument trading community. The major issue with these filters is the delay between the filtered data and the noisy data. This delay only increases as more noise reduction is desired. In the present marketplace, where investors are competing for quality and timely information, this delay can be a hindrance. This paper proposes a new FIR filter derived with the aim of maximizing the level of noise reduction and minimizing the delay. The model is modified from the old problem of time series graduation by penalized least squares. Comparison between five different methods has been done and experiment results have shown that our method is significantly superior to the alternatives in both delay and smoothness over short and middle range delay periods.

Logistic regression is one of the most commonly applied statistical methods for binary classification problems. This paper considers the nonnegative garrote regularization penalty in logistic models and derives an optimization algorithm for minimizing the resultant penalty function. The search algorithm is computationally efficient and can be used even when the number of regressors is much larger than the number of samples. As the nonnegative garrote requires an initial estimate of the parameters, a number of possible estimators are compared and contrasted. Logistic regression with the nonnegative garrote is then compared with several popular regularization methods in a set of comprehensive numerical simulations. The proposed method attained excellent performance in terms of prediction rate and variable selection accuracy on both real and artificially generated data.

This work is motivated by the need for consensus clustering methods using multiple datasets, applicable to microarray data. It introduces a new method for clustering samples with similar genetic profiles, in an unsupervised fashion, using information from two or more datasets. The method was tested using two breast cancer gene expression microarray datasets, with 295 and 249 samples; and 12,325 common genes. Four subtypes with similar genetic profiles were identified in both datasets. Clinical information was analysed for the subtypes found and they confirmed different levels of tumour aggressiveness, measured by the time of metastasis, thus indicating a connection between different genetic profiles and prognosis. Finally, the subtypes identified were compared to already established subtypes of breast cancer. That indicates that the new approach managed to detect similar gene expression profile patterns across the two datasets without any

a priori

knowledge. The two datasets used in this work, as well as all the figures, are available for download from the website

http://www.cs.newcastle.edu.au/~mendes/BreastCancer.html.

Understanding the way how genes interact is one of the fundamental questions in systems biology. The modeling of gene regulations currently assumes that genes interact either instantaneously or with a certain amount of time delay. In this paper, we propose an information theory based novel two-phase gene regulatory network (GRN) inference algorithm using the Bayesian network formalism that can model both instantaneous and single-step time-delayed interactions between genes simultaneously. We show the effectiveness of our approach by applying it to the analysis of synthetic data as well as the

Saccharomyces cerevisiae

gene expression data.

Spectral graph theoretic methods such as Laplacian Eigenmaps are among the most popular algorithms for manifold learning and clustering. One drawback of these methods is, however, that they do not provide a natural out-of-sample extension. They only provide an embedding for the given training data. We propose to use sparse grid functions to approximate the eigenfunctions of the Laplace-Beltrami operator. We then have an explicit mapping between ambient and latent space. Thus, out-of-sample points can be mapped as well. We present results for synthetic and real-world examples to support the effectiveness of the sparse-grid-based explicit mapping.

Changes in the distribution of financial time series, particularly stock market prices, can happen at a very high frequency. Such changes make the prediction of future behavior very challenging. Application of traditional regression algorithms in this scenario is based on the assumption that all data samples are equally important for model building. Our work examines the use of an alternative data pre-processing approach, whereby knowledge of distribution changes is used to pre-filter the training dataset. Experimental results indicate that this simple and efficient technique can produce effective results and obtain improvements in prediction accuracy when used in conjunction with a range of forecasting techniques.

In most real-world information processing problems, data is not a free resource; its acquisition is rather time-consuming and/or expensive. We investigate how these two factors can be included in supervised classification tasks by deriving classification as a sequential decision process and making it accessible to Reinforcement Learning. Our method performs a sequential feature selection that learns which features are most informative at each timestep, choosing the next feature depending on the already selected features and the internal belief of the classifier. Experiments on a handwritten digits classification task show significant reduction in required data for correct classification, while a medical diabetes prediction task illustrates variable feature cost minimization as a further property of our algorithm.

We propose a collaborative filtering data processing method based on reflective vector-space retraining, referred to as Progressive Reflective Indexing (PRI). We evaluate the method’s ability to provide recommendations of items from a long tail. In order to reflect ‘real-world’ demands, in particular those regarding non-triviality of recommendations, our evaluation is novelty-oriented. We compare PRI with a few widely-referenced collaborative filtering methods based on SVD and with Reflective Random Indexing (RRI) - a reflective data processing method established in the area of Information Retrieval. To demonstrate the superiority of PRI over other methods in long tail recommendation scenarios, we use the probabilistically interpretable AUROC measure. To show the relation between the structural properties of the user-item matrix and the optimal number of reflections we model the analyzed data sets as bipartite graphs.

The ranking and clustering of publication databases are often used to discover useful information about research areas. NetClus is an iterative algorithm for clustering heterogenous star-schema information network that incorporates the ranking information of individual data types. The algorithm has been evaluated using the DBLP database. In this paper, we apply NetClus on PubMed, a free database of articles on life sciences and biomedical topics to discover key aspects of cancer research. The absence of unique identifiers for authors in PubMed introduces additional challenges. To address this, we introduce an improved author disambiguation technique using affiliation string normalisation based on vector space model together with co-author networks. Our technique for disambiguating authors, which offers a higher accuracy than existing techniques, significantly improves NetClus clustering results.

Chronic Disease Management (CDM) is an important area of health care where Health Knowledge Management can provide substantial benefits. A web-based chronic disease management service, called cdmNet, is accumulating detailed data on CDM as it is being rolled out across Australia. This paper presents the application of unsupervised neural networks to cdmNet data to: (1) identify interesting patterns in diabetes data; and (2) assist diabetes related policy-making at different levels. The work is distinct from existing research in: (1) the data; (2) the objectives; and (3) the techniques used. The data represents the diabetes population across the entire primary care sector. The objectives include diabetes related decision and policy making at different levels. The pattern recognition techniques combine a traditional approach to data mining, involving the Self-Organizing Map (SOM), with an extension to include the Growing Self-Organizing Map (GSOM).

We study the problem of classification on uncertain objects whose locations are uncertain and described by probability density functions (pdf). We propose a novel supervised UK-means algorithm for classifying uncertain objects to overcome the computation bottleneck of existing algorithms. Additionally, we consider to select features that can capture the relevant properties of uncertain data. We experimentally demonstrate that our proposed approaches are more efficient than existing algorithms and can attain comparatively accurate results on non-overlapping data sets.

We present results on closure spaces induced by isotone fuzzy Galois connections. Such spaces play a fundamental role in the analysis of relational data such as formal concept analysis or relational factor analysis. We provide a characterization of such closure spaces and study their morphisms. The results contribute to foundations of a matrix calculus over relational data.

Machine learning algorithms can suffer a performance bias when data sets are unbalanced. This paper develops a multi-objective genetic programming approach to evolving accurate and diverse ensembles of non-dominated solutions where members vote on class membership. We explore why the ensembles can also be vulnerable to the learning bias using a range of unbalanced data sets. Based on the notion that smaller ensembles can be better than larger ensembles, we develop a new evolutionary-based pruning method to find groups of highly-cooperative individuals that can improve accuracy on the important minority class.

Compiling Bayesian networks (BNs) is one of the most effective ways to exact inference because a logical approach enables the exploitation of local structures in BNs (i.e., determinism and context-specific independence). In this paper, a new parameter learning method based on compiling BNs is proposed. Firstly, a target BN with multiple evidence sets are compiled into a single

shared

binary

decision

diagram

(SBDD) which shares common sub-graphs in multiple BDDs. Secondly, all conditional expectations which are required for executing the EM algorithm are simultaneously computed on the SBDD while their common local probabilities and expectations are shared. Due to these two types of sharing, the computation efficiency of the proposed method is higher than that of an EMalgorithm which naively uses an existing BN compiler for exact inference.

Research into learning from imbalanced data has increasingly captured the attention of both academia and industry, especially when the class distribution is highly skewed. This paper compares the Area Under the Receiver Operating Characteristic Curve (

AUC

) performance of bagging in the context of learning from different imbalanced levels of class distribution. Despite the popularity of bagging in many real-world applications, some questions have not been clearly answered in the existing research, e.g., which bagging predictors may achieve the best performance for applications, and whether bagging is superior to single learners when the levels of class distribution change. We perform a comprehensive evaluation of the

AUC

performance of bagging predictors with 12 base learners at different imbalanced levels of class distribution by using a sampling technique on 14 imbalanced data-sets. Our experimental results indicate that Decision Table (DTable) and RepTree are the learning algorithms with the best bagging

AUC

performance. Most

AUC

performances of bagging predictors are statistically superior to single learners, except for Support Vector Machines (SVM) and Decision Stump (DStump).

Variable selection or feature ranking is a problem of fundamental importance in modern scientific research where data sets comprising hundreds of thousands of potential predictor features and only a few hundred samples are not uncommon. This paper introduces a novel Bayesian algorithm for feature ranking (BFR) which does not require any user specified parameters. The BFR algorithm is very general and can be applied to both parametric regression and classification problems. An empirical comparison of BFR against random forests and marginal covariate screening demonstrates promising performance in both real and artificial experiments.

We present and investigate ensembles of semi-random model trees as a novel regression method. Such ensembles combine the scalability of tree-based methods with predictive performance rivalling the state of the art in numeric prediction. An empirical investigation shows that Semi-Random Model Trees produce predictive performance which is competitive with state-of-the-art methods like Gaussian Processes Regression or Additive Groves of Regression Trees. The training and optimization of Random Model Trees scales better than Gaussian Processes Regression to larger datasets, and enjoys a constant advantage over Additive Groves of the order of one to two orders of magnitude.

Learning robust subspaces to maximize class discrimination is challenging, and most current works consider a weak connection between dimensionality reduction and classifier design. We propose an alternate framework wherein these two steps are combined in a joint formulation to exploit the direct connection between dimensionality reduction and classification. Specifically, we learn an optimal subspace on the Grassmann manifold jointly minimizing the classification error of an SVM classifier. We minimize the regularized empirical risk over both the hypothesis space of functions that underlies this new generalized multi-class Lagrangian SVM and the Grassmann manifold such that a linear projection is to be found. We propose an iterative algorithm to meet the dual goal of optimizing both the classifier and projection. Extensive numerical studies on challenging datasets show robust performance of the proposed scheme over other alternatives in contexts wherein limited training data is used, verifying the advantage of the joint formulation.

Ensemble selection has recently appeared as a popular ensemble learning method, not only because its implementation is fairly straightforward, but also due to its excellent predictive performance on practical problems. The method has been highlighted in winning solutions of many data mining competitions, such as the Netflix competition, the KDD Cup 2009 and 2010, the UCSD FICO contest 2010, and a number of data mining competitions on the Kaggle platform. In this paper we present a novel variant: bagging ensemble selection. Three variations of the proposed algorithm are compared to the original ensemble selection algorithm and other ensemble algorithms. Experiments with ten real world problems from diverse domains demonstrate the benefit of the bagging ensemble selection algorithm.

It is a widely held view in contemporary computational neuroscience that the brain responds to sensory input by producing sparse distributed representations. In this paper we investigate a brain-inspired spatial pooling algorithm that produces such sparse distributed representations by modelling the formation of proximal dendrites associated with neocortical minicolumns. In this approach, distributed representations are formed out of a competitive process of inter-column inhibition and subsequent learning. Specifically, we evaluate the performance of a recently proposed binary spatial pooling algorithm on a well-known benchmark of greyscale natural images. Our main contribution is to augment the algorithm to handle greyscale images, and to produce better quality encodings of binary images. We also show that the augmented algorithm produces superior population and lifetime kurtosis measures in comparison to a number of other well-known coding schemes.

Particle swarm optimization cannot guarantee convergence to the global optimum on multi-modal functions, so multiple swarms can be useful. One means to coordinate these swarms is to use a separate search mechanism to identify different regions of the solution space for each swarm to explore. The expectation is that these independent sub-swarms can each perform an effective search around the region where it is initialized. This regional focus means that sub-swarms will have different goals and features when compared to standard (single) swarms. A comprehensive study of these differences leads to a new set of general guidelines for the configuration of sub-swarms in multi-swarm systems.

Each particle in a swarm maintains its current position and its personal best position. It is useful to think of these personal best positions as a population of attractors – updates to current positions are based on attractions to these personal best positions. If the population of attractors has high diversity, it will encourage a broad exploration of the search space with particles being drawn in many different directions. However, the population of attractors can converge quickly – attractors can draw other particles towards them, and these particles can update their own personal bests to be near the first attractor. This convergence of attractors can be reduced by having a particle update the attractor it has approached rather than its own attractor/personal best. This simple change to the update procedure in particle swarm optimization incurs minimal computational cost, and it can lead to large performance improvements in multi-modal search spaces.

Evolutionary algorithms have been widely used to tackle multi-objective optimization problems. Incorporating preference information into the search of evolutionary algorithms for multi-objective optimization is of great importance as it allows one to focus on interesting regions in the objective space. Zitzler et al. have shown how to use a weight distribution function on the objective space to incorporate preference information into hypervolume-based algorithms. We show that this weighted information can easily be used in other popular EMO algorithms as well. Our results for NSGA-II and SPEA2 show that this yields similar results to the hypervolume approach and requires less computational effort.

This paper investigates fitness functions based on the detecting accuracy of each training image. In general, machine learning algorithms for edge detection only focus on the accuracy based on all training pixels treated equally, but the accuracy based on every training image is not investigated. We employ genetic programming to evolve detectors with fitness functions based on the accuracy of every training image. Here, average (arithmetic mean) and geometric mean are used as fitness functions for normal natural images. The experimental results show fitness functions based on the accuracy of each training image obtain better performance, compared with the Sobel detector, and there is no obvious difference between the fitness functions with average and geometric mean.

Object detection in images is inherently imbalanced and prone to overfitting on the training set. This work investigates the use of a validation set and sampling methods in Multi-Objective Genetic Programming (MOGP) to improve the effectiveness and robustness of object detection in images. Results show that sampling methods decrease runtimes substantially and increase robustness of detectors at higher detection rates, and that a combination of validation together with sampling improves upon a validation-only approach in effectiveness and efficiency.

This paper proposes a new variant of differential evolution for multimodal optimization termed DE/isolated/1. It generates new individuals close to an isolated individual in a current population as a niching scheme. This mechanism will evenly allocate search resources for each optimum. The proposed method was evaluated along with the existing methods through computational experiments using eight two-dimensional multimodal functions as benchmarks. Experimental results show that the proposed method shows better performance for several functions which are not effectively solved by existing algorithms.

In this paper, we investigate the effectiveness of several techniques commonly recommended for overcoming convergence problems with coevolutionary algorithms. In particular, we investigate effects of the Hall of Fame, and of several diversity maintenance methods, on a problem designed to test the ability of coevolutionary algorithms to deal with an intransitive superiority relation between solutions. We measure and analyse the effects of these methods on population diversity and on solution quality.

Object detection is the task of correctly identifying and locating objects of interest within a larger image. An ideal object detector would maximise the number of correctly located objects and minimise the number of false-alarms. Previous work, following the traditional multiple-objective paradigm of finding Pareto-optimal tradeoffs between these objectives, suffers from an abundance of useless detectors that either detect nothing (but with no false-alarms) or mark every pixel as an object (perfect detection performance with but a very large number of false-alarms); these are very often Pareto-optimal and hence inadvertently rewarded. We propose and compare a number of improvements to eliminate useless detectors during evolution. The most successful improvements are generally more inefficient than the benchmark MOGP approach due to the often vast numbers of additional crossover and mutation operations required, but as a result the archive populations generally include a much higher number of Pareto-fronts.

A core challenge of Multiobjective Evolutionary Algorithms (MOEAs) is to attain evenly distributed Pareto optimal solutions along the Pareto front. In this paper, we propose a novel asymmetric Pareto-adaptive (

apa

) scheme for the identification of well distributed Pareto optimal solutions based on the geometrical characteristics of the Pareto front. The

apa

scheme applies to problem with symmetric and asymmetric Pareto fronts. Evaluation on multiobjective problems with Pareto fronts of different forms confirms that

apa

improves both convergence and diversity of the classical decomposition-based (MOEA/D) and Pareto dominance-based MOEAs (

paε

-MyDE).

We present analysis of performance of an elitist Evolutionary algorithm using a recombination operator 1-Bit-Swap on the Royal Roads test function. We derive complete, approximate and asymptotic convergence rates. Both complete and approximate models show the benefit of the size of the population and recombination pool when they are small and leveling out of this effect when limit conditions are applied. Numerical results confirm our findings.

Most real-world problems involve objectives, constraints and parameters which constantly change with time. Treating such problems as static problems requires knowledge of the prior time but the computational cost is still high. In this paper, a simplex model based evolutionary algorithm is proposed for dynamic multi-objective optimization, which uses a modified simplex model to predict the optimal solutions (in variable space) of the next time step. Thereafter, a modified evolutionary algorithm which borrows ideas from particle swarm optimization is applied to solve multi-objective problems when the time step is fixed. This method is tested and compared on a set of benchmarks. The results show that the method can effectively track varying Pareto fronts over time.

Color quantization (CQ) is one of the most important techniques in image compression and processing. Most of quantization methods are based on clustering algorithms. Data clustering is an unsupervised classification technique and belongs to NP-hard problems. One of the methods for solving NP-hard problems is applying swarm intelligence algorithms. Artificial fish swarm algorithm (AFSA) fits in the swarm intelligence algorithms. In this paper, a modified AFSA is proposed for performing CQ. In the proposed algorithm, to improve the AFSA’s efficiency and remove its weaknesses, some modifications are done on behaviors, parameters and the algorithm procedure. The proposed algorithm along with other multiple known algorithms has been used on four well known images for doing CQ. Experimental results comparison shows that the proposed algorithm has acceptable efficiency.

Multiagent learning is a challenging problem in the area of multiagent systems because of the non-stationary environment caused by the interdependencies between agents. Learning for coordination becomes more difficult when agents do not know the structure of the environment and have only local observability. In this paper, an approach is proposed to enable autonomous agents to learn where and how to coordinate their behaviours in an environment where the interactions between agents are sparse. Our approach firstly adopts a statistical method to detect those states where coordination is most necessary. A Q-learning based coordination mechanism is then applied to coordinate agents’ behaviours based on their local observability of the environment. We test our approach in grid world domains to show its good performance.

Traders that operate in markets with multiple competing marketplaces can use learning to choose in which marketplace they will trade, and how much they will shout in that marketplace. If traders are able to share information with each other about their shout price and market choice over a social network, they can trend towards the market equilibrium more quickly, leading to higher profits for individual traders, and a more efficient market overall. However, if some traders share false information, profit and market efficiency can suffer as a result of traders acting on incorrect information. We present the

Trading Agent Trust Model

(TATM) that individual traders employ to detect deceptive traders and mitigate their influence on the individual’s actions. Using the JCAT double-auction simulator, we assess TATM by performing an experimental evaluation of traders sharing information about their actions over a social network in the presence of deceptive traders. Results indicate that TATM is effective at mitigating traders sharing false information, and can increase the profit of TATM traders relative to non-TATM traders.

Multi-robot task allocation research has focused on

sequential single-item auctions

and various extensions as quick methods for allocating tasks to robots with small overall team costs. In this paper we outline the benefits of grouping tasks with positive synergies together and auctioning clusters of tasks rather than individual tasks. We show that with task-clustering the winner determination costs remain the same as sequential single-item auctions and that auctioning task-clusters can result in overall smaller team costs.

Biologists are interested in studying the relation between the genetic diversity of a population and its fitness. We adopt the notion of entropy as a measure of genetic diversity and correlate it with fitness of an evolutionary ecosystem simulation. EcoSim is a predator-prey individual based simulation which models co-evolving sexual individuals evolving in a dynamic environment. The correlation values between entropy and fitness of all the species that ever existed during the whole simulation are presented. We show how entropy strongly correlates with fitness and investigate the factors behind this result using machine learning techniques. We build a classifier based on different species’ features and successfully predict the resulting correlation value between entropy and fitness. The best features affecting the quality of classification are also being investigated.

It is widely acknowledged that belief revision and belief update are two very different types of processes – one is appropriate to model belief change in a static environment, the other in a dynamic environment. Technically speaking, the former is constructed with the aid of a global preference ordering over possible worlds as the selection mechanism, and the latter with the aid of a family of such local orderings. It has been argued that update can be defined via revision. In this paper I argue that indeed revision can be defined via update in a restricted sense if a distance function is used as the selection mechanism.

Negotiating agents play a key role in e-markets and become more popular. However, in much existing work, the e-markets are assumed to be closed and static, which is unrealistic. To address the issue, this paper developed negotiating agents that can adapt their negotiation strategies, outcome expectations, offer evaluations, and counter-offers generations in dynamic, open e-markets. Also, the proposed agents can generate multiple counter-offers according to different preferences so as to further improve their negotiation outcomes. Finally, the experimental results show the improvements on agents’ profits by employing our negotiation model.

In this paper we are discussing which factors affect the scalability of the parallel Monte Carlo Tree Search algorithm. We have run the algorithm on CPUs and GPUs in Reversi game and SameGame puzzle on the TSUBAME supercomputer. We are showing that the most likely cause of the scaling bottleneck is the problem size. Therefore we are showing that the MCTS is a weak-scaling algorithm. We are not focusing on the relative scaling when compared to a single-threaded MCTS, but rather on the absolute scaling of the parallel MCTS algorithm.

We will be concerned with decisions that involve some sort of action. You have an apple and can exchange it for an orange. If you prefer the orange then you exchange; if not, you don’t. The concept of preference here is a practical one, which presupposes that it is within your capability to move from one thing to another only if it is at least as good. Yet it is also important to be aware of what your capabilities are, and this is where questions are useful.

A new non-monotonic logic called clausal defeasible logic (CDL) is defined and explained. CDL is the latest in the family of defeasible logics, which, it is argued, is important for knowledge representation and reasoning. CDL increases the expressive power of defeasible logic by allowing clauses where previous defeasible logics only allowed literals. This greater expressiveness allows the representation of the Lottery Paradox, for example. CDL is well-defined, consistent, and has other desirable properties.

A new expert systems methodology was developed, building on existing work on the Ripple Down Rules (RDR) method. RDR methods offer a solution to the maintenance problem which has otherwise plagued traditional rule-based expert systems. However, they are, in their classic form, unable to support rules which use existing classifications in their rule conditions. The new method outlined in this paper is suited to multiple classification tasks, and maintains all the significant advantages of previous RDR offerings, while also allowing the creation of rules which use classifications in their conditions. It improves on previous offerings in this field by having fewer restrictions regarding where and how these rules may be used. The method has undergone initial testing on a complex configuration task, which would be practically unsolvable with traditional multiple classification RDR methods, and has performed well, reaching an accuracy in the 90

th

percentile after being trained with 1073 rules over the course of classifying 1000 cases, taking ~12 expert hours.

Description logics are a well-established family of knowledge representation formalisms in Artificial Intelligence. Enriching description logics with non-monotonic reasoning capabilities, especially preferential reasoning as developed by Lehmann and colleagues in the 90’s, would therefore constitute a natural extension of such KR formalisms. Nevertheless, there is at present no generally accepted semantics, with corresponding syntactic characterization, for preferential consequence in description logics. In this paper we fill this gap by providing a natural and intuitive semantics for defeasible subsumption in the description logic

$\mathcal{ALC}$

. Our semantics replaces the propositional valuations used in the models of Lehmann et al.. with structures we refer to as

concept models

. We present representation results for the description logic

$\mathcal{ALC}$

for both preferential and rational consequence relations. We argue that our semantics paves the way for extending preferential and rational consequence, and therefore also rational closure, to a whole class of logics that have a semantics defined in terms of first-order relational structures.

Approximate propositional logics provide a response to the intractability of classical inference for the modelling and construction of resource-bounded agents. They allow the degree of logical soundness (or completeness) to be balanced against the agent’s resource limitations.

We develop a logical semantics, based on a restriction to Finger’s

logics of limited bivalence

[5], and establish the adequacy of a clausal tableau based proof theory with respect to this semantics. This system is shown to characterise DPLL with restricted branching, providing a clear path for the adaptation of DPLL-based satisfiability solvers to approximate reasoning. Furthermore it provides insights into the traditional notion of problem hardness, as we show that the parameter set of these logics correspond to the

strong backdoor

for an unsatisfiable problem.

In this paper, we develop a formal framework for analysing the flow of information and knowledge through social networks. Specifically, we propose a multi-agent epistemic logic in which we can represent and reason about communicative actions based on social networks and the resulting knowledge and ignorance of agents. We apply this logic to formally analyse the “Revolt or Stay-at-home” problem known from the literature, where social networks play an important role in agents’ knowledge acquisition and decision-making. We evaluate our work by proving some mathematical properties of our new logic, including the fact that it generalises the existing Logic of Public Announcement.

Efficient Subwindow Search(ESS) is an effective method for object detection and localization, which adopts a scheme of branch-and-bound to find the global optimum of a quality function from all the possible subimages. Since the number of possible subimage is

$\emph{O}(\emph{n}^{4})$

for an images with

$\emph{n}\times\emph{n}$

resolution, the time complexity of ESS ranges from

$\emph{O}(\emph{n}^{2})$

to

$\emph{O}(\emph{n}^{4})$

. In other words, ESS is equivalent to the exhaustive search in the worst case. In this paper, we propose a new method named Adimissible Region Search(ARS) for detecting and localizing the object with arbitrary shape in an image. Compared with the sliding window methods using ESS, ARS has two advantages: firstly, the time complexity is quadratic and stable so that it is more suitable to process large resolution images; secondly, the admissible region is adaptable to match the real shape of the target object and thus more suitable to represent the object. The experimental results on

PASCAL VOC 2006

demonstrate that the proposed method is much faster than the ESS method on average.

Recent progress in stereo matching algorithms performance especially belief propagation algorithm encourages us greatly. However, it is difficult to develop a stable, real time and low cost shape measurement system. In this paper, we propose a novel laser-scanning based 3D measurement system to obtain depth information in real time. Efficient Belief Propagation algorithm is adopted to match the correspondent points of laser stripe between calibration image and measurement image. When laser beam is projected onto scene, occlusion problem will occur and influence 3D reconstruction accuracy. Outliers are detected by the ratio of the second highest peak over the highest peak. Experimental results demonstrate the feasibility of proposed approach.

Research in this paper is focused to make a change on variety of Efficient Sub-window Search algorithms. A restriction is applied on the sub-window shape from rectangle into square in order to reduce the number of possible sub-windows with an expectation to improve the computation speed. However, this may come with a consequence of accuracy loss. The experiment results on the proposed algorithms were analysed and compared with the performance of the original algorithms to determine whether the speed improvement is significantly large to make the accuracy loss acceptable. It was found that some new algorithms show a good speed improvement while maintaining small accuracy loss. Furthermore, there is an algorithm designed from a combination of a new algorithm and an original algorithm which gains the benefit from both algorithms and produces the best performance among all new algorithms.

Binocular stereo vision technology shows a particular interesting for face recognition, in which the accurate stereo matching is the key issue for obtaining dense disparity map used for exploiting 3D shape information of object. This paper proposed a binocular structured light stereo matching approach to deal with the challenge of stereo matching to objects having large disparity and low texture, such as facial image. By introducing global system to coordinate the binocular camera and projector, a projector cast structured light pattern which added texture to the face scene. Binocular epipolar constraint and semi-global stereo matching algorithm were applied. The experiments showed that the accuracy had improved compared to that of purely binocular vision for getting dense facial disparity map.

This paper describes the use of foveated imaging and virtual saccades to identify visual objects using both colour and edge features. Vision processing is a resource hungry operation at the best of times. When the demands require robust, real time performance with a limited embedded processor, the challenge is significant. Our domain of application is the RoboCup Standard Platform League soccer competition using the Aldebaran Nao robot. We describe algorithms that use a combination of down-sampled colour images and high resolution edge detection to identify objects in varying lighting conditions. Optimised to run in real time on autonomous robots, these techniques can potentially be applied in other resource limited domains.

Object classification is an important problem in multimedia information retrieval. In order to better objects classification, we often employ a set of multi-view images to describe an object for classification. However, two issues remain unsolved: 1) exploiting the spatial relations of local features in the multi-view images for classification, and 2) accelerating the classification process. To solve them, Fast Multi-view Graph Kernel (FMGK), is proposed. Given a set of multi-view images for an object, we segment each view image into several regions. And inter- and intra- view linkage graphs are constructed to describe the spatial relations of the regions between and within each multi-view image respectively. Then, the inter- and intra- view graphs are integrated into a so-called multi-view region graph. Finally, the kernel between objects is computed by accumulating all matchings’ of walk structures between corresponding multi-view region graphs. And a SVM [11] classifier is trained based on the computed kernels for object classification. The experimental results on different datasets validate the effectiveness of our FMGK.

Image feature selection (FS) is an important task which can affect the performance of image classification and recognition. In this paper, we present a feature selection algorithm based on ant colony optimization (ACO). For

n

features, most ACO-based feature selection methods use a complete graph with O(

n

2

) edges. However, the artificial ants in the proposed algorithm traverse on a directed graph with only 2

n

arcs. The algorithm adopts classifier performance and the number of the selected features as heuristic information, and selects the optimal feature subset in terms of feature set size and classification performance. Experimental results on various images show that our algorithm can obtain better classification accuracy with a smaller feature set comparing to other algorithms.

A robust smile recognition system could be widely used for many real-world applications. In this paper, we introduce biologically inspired model (BIM) into the building of realistic smile classification system for solving challenging realistic tasks. To improve the performance of BIM, we develop a modified BIM (MBIM), which utilizes a more efficient pooling operation and boosting feature selection. Experiments demonstrate the effectiveness of themodifications and adjustments of BIM. By testing on the challenging realistic database, GENKI, our method is proved to be superior to some other state-of-the-art smile classification algorithms.

The capability of inferring colours from the texture (grayscale contents) of an image is useful in many application areas, when the imaging device/environment is limited. Traditional colour assignment involves intensive human effort. Automatic methods have been proposed to establish relations between image textures and the corresponding colours. Existing research mainly focuses on linear relations.

In this paper, we employ sparse constraints in the model of texture-colour relationship. The technique is developed on a locally linear model, which assumes manifold assumption of the distribution of the image data. Given the texture of an image patch, learning the model transfers colours to the texture patch by combining known colours of similar texture patches. The sparse constraint checks the contributing factors in the model and helps improve the stability of the colour transfer. Experiments show that our method gives superior results to those of the previous work.

This paper investigates the effects of applying different well-known static and dynamic neighbourhood topologies on the efficiency and effectiveness of a particle swarm optimisation-based edge detection algorithm. Our experiments show that the use of different topologies in a PSO-based edge detection algorithm does not have any significant effect on the accuracy of the algorithm for noisy images in most cases. That is in contrast to many reported results in the literature which claim that the selection of the neighbourhood topology affects the robustness of the algorithm to premature convergence and its accuracy. However, the fully connected topology in which all particles are connected to each other and exchange information performs more efficiently than other topologies in the PSO-based based edge detector.

In order to transform ancient Malay manuscript images to be cleaner and more readable, enhancement must be performed as the images have different qualities due to uneven background, ink bleed, or ink bleed and expansion of spots. The proposed method for image improvement in this experiment consists of several stages, which are Local Adaptive Equalization, Image Intensity Values, K-Means Clustering, Adaptive Thresholding, and Median Filtering. The proposed method produces an adaptive binarization image. We tested the proposed method on eleven ancient Malay manuscript images. The proposed method has the smallest average value of Relative Foreground Area Error compared to the other state of the art methods. At the same time, the proposed method have produced the better results and better readability compared to the other methods.

Semantic Relatedness Measurement (SRM) is one of the most important applications of reasoning by ontologies and different disciplines of AI, e.g. Information Retrieval, are firmly tied to it. The accuracy of SRM by lexical resources is largely determined by the quality of the knowledge modeling by the knowledge base. The limited types of relations modeled by ontologies have caused most of the SRM methods to be able to detect and measure only a few special types of semantic relationships that is very far from the concept of semantic relatedness in human brain. Concepts of lexical resources are usually accompanied with a plain text narratively defines the concept. The information included in the definition of concepts sound very promising for SRM. This paper intends to treat this information as formal relations to improve SRM by distance-base methods. In order to do so, concepts glosses are mined for the semantic relations that are not modeled by the ontology. Then, these relations are employed in combination with classic relations of the ontology for semantic relatedness measurement according to the shortest path between concepts. Our evaluation demonstrated qualitative and quantitative improvement in detection of previously unknown semantic relationships and also stronger correlation with human judgment in SRM.

We present and evaluate

MKBUILD

, a tool for creating domain-specific ontologies. These ontologies, which we call Modular Knowledge Bases (MKBs), contain concepts and associations imported from existing large-scale knowledge resources, in particular WordNet and Wikipedia. The combination of WordNet’s human-crafted taxonomy and Wikipedia’s semantic associations between articles produces a highly connected resource. Our MKBs are used by a

conversational agent

operating in a small computational environment. We constructed several domains with our technique, and then conducted an evaluation by asking human subjects to rate the domain-relevance of the concepts included in each MKB on a 3-point scale. The proposed methodology achieved precision values between 71% and 88% and recall between 37% and 95% in the evaluation, depending on how the middle-score judgements are interpreted. The results are encouraging considering the cross-domain nature of the construction process and the difficulty of representing concepts as opposed to terms.

In this paper we introduce three methods for automatic generality evaluation of commonsense statements candidates generated for Open Mind Common Sense (OMCS), which is the basis of ConceptNet, a commonsense knowledge base. By using sister terms from Japanese WordNet, our system generates new statements which are automatically evaluated by using WWW co-occurrences and hit number retrieved by a Web search engine. These values are used in three generality judgment methods we propose. Evaluation experiments show that the best of them was “exact match ratio” which achieved accuracy of 62.6% when evaluating general sentences and “co-occurrences in snippets” method scored highest with 48.6% when judging unnatural phrases. Compared to the data without noise elimination, the “exact match ratio” achieved 38.2 points increase in accuracy.

PENG Light is a controlled natural language designed to write unambiguous specifications that can be translated automatically via discourse representation structures into a formal target language. Instead of writing axioms in a formal language, an author writes a specification and the associated background axioms directly in controlled natural language. In this paper, we first review the controlled natural language PENG Light and show how a discourse representation structure is generated for sentences written in PENG Light. We then discuss two different solutions of how discourse representation structures can be implemented for coordinated structures. Finally, we show how an efficient implementation of coordinated structures combined with a suitable parsing strategy affects the parsing performance of the controlled natural language.

The Malay language may be written using either Roman or Jawi characters. Most Malay stemmers cover only Roman (

Rumi

) affixes. This paper proposes a stemmer for Jawi characters using two sets of rules in Jawi: one set of rules is used to stem various forms of derived words, and another set is used to replace the use of a dictionary by producing the root word for each derivative. This stemmer has been tested using 1185 derived words consisting of prefix, circumfix, suffix, and infix. The results show that 84.89% of Jawi root words have been successfully stemmed.

This paper establishes a formal relationship between theories of computation and certain types of reasoning about action theories expressed in the situation calculus. In particular it establishes a formal correspondence between Deterministic Finite-State Automata (DFAs) and the ‘literal-based’ class of basic action theory, and identifies the special case of DFAs equivalent to ‘context-free’ action theories. These results formally describe the relative expressivity of different action theories. We intend to exploit these results to drive more efficient implementations for planning, legality checking, and modelling in the situation calculus.

We describe a simulation model based on an avian ecosystem for determining what causes birdsong evolution. It is already known that songbirds communicate with a “birdsong.” This birdsong is used in territorial and courtship behaviors. Some previous researches have suggested that songs related to territorial behaviors should have simple structures while those related to courtship behaviors should have complex ones. We suspect that birdsongs are constantly evolving to achieve a suitable balance between the two behaviors while considering the surrounding environment. We consider avian habitat density to be one of the most important environmental factors influencing birdsong evolution and therefore created different densities in a simulation model. In this paper, we propose a birdsong acquisition model by sexual selection that contains both territorial and courtship behaviors. We conducted simulations with the proposed model and determined that the evolution of birdsongs differs depending on a bird’s habitat density.

We address the problem of visualizing structure of bipartite graphs such as relations between pairs of objects and their multi-labeled categories. For this task, the existing spherical embedding method, as well as the other standard graph embedding methods, can be used. However, these existing methods either produce poor visualization results or require extremely large computation time to obtain the final results. In order to overcome these shortcomings, we propose a new spherical embedding method based on a power iteration, which additionally performs two operations on the position vectors: double-centering and normalizing operations. Moreover, we theoretically prove that the proposed method always converges. In our experiments using bipartite graphs constructed from the Japanese sites of Yahoo!Movies and Yahoo!Answers, we show that the proposed method works much faster than these existing methods and still the visualization results are comparable to the best available so far.

This paper addresses the issue of content sequencing in computer-based learning (CBL). In doing so, it proposes a Skill-Challenge Balancing (SCB) approach as a way to enhance the CBL experience. The approach is based on the Flow Theory, allowing self-adjustment of the given levels of challenges in a given learning tasks so that the learner will consistently be adaptively able to engage in the CBL activity. An empirical study with 70 students suggested that the SCB-based learners were significantly better in their learning experience specifically in their focus of attention and intrinsic interests compared to the learners in the system without SCB. The results also revealed that SCB was fully utilised by the learners to regulate the levels of difficulty of the CBL tasks.

Online Test Paper Generation (Online-TPG) is a promising approach for Web-based testing and intelligent tutoring. It generates a test paper automatically online according to user specification based on multiple assessment criteria, and the generated test paper can then be attempted over the Web by user for self-assessment. Online-TPG is challenging as it is a multi-objective optimization problem on constraint satisfaction that is NP-hard, and it is also required to satisfy the online runtime requirement. The current techniques such as dynamic programming, tabu search, swarm intelligence and biologically inspired algorithms are ineffective for Online-TPG as these techniques generally require long runtime for generating good quality test papers. In this paper, we propose an efficient approach, called DAC-TS, which is based on the principle of constraint-based divide-and-conquer (DAC) and tabu search (TS) for constraint decomposition and multi-objective optimization for Online-TPG. Our empirical performance results have shown that the proposed DAC-TS approach has outperformed other techniques in terms of runtime and paper quality.

We examine the interactions of knowledge and awareness in dynamic epistemic logic. Implicit knowledge describes the things that an agent could infer from what is known, if the agent were aware of the necessary concepts. Reasoning techniques that are robust to incomplete awareness are important when considering interactions of automated agents in complex dynamic environments, such as the semantic web. Here we revisit Hector Levesque’s original motivation of implicit knowledge and consider several contemporary realizations of implicit knowledge. We present a framework to compare different interactions of knowledge and awareness in the context of public announcements, and introduce a new formalism for

tacit knowledge

.

A recent theory of perceptual mapping argues that humans do not integrate successive views using a mathematical transformation approach to form a perceptual map. Rather, it is formed from integrating views at limiting points in the environment. Each view affords an adequate description of the spatial layout of a local environment and its limiting point is detected via a process of recognizing significant features in it and tracking them across views. This paper discusses the implementation of this theory on a laser-ranging mobile robot. Two algorithms were implemented to produce two different kinds of maps; one which is sparse and fragmented, and the other which is dense and detailed. Both algorithms successfully generated maps that preserve well the layout of the environment. The implementation provides insights into the problem of loop closing, moving in featureless environments, seeing a stable world, and augmenting mapping with commonsense knowledge.

The principal goal of the LANdroids program (2007-2010) was to validate the concept that mobile tactical radio relay platforms can provide improved communications connectivity in non-line-of-sight communications environments such as urban terrain. The first phase of the program demonstrated that intelligent mobile relays can provide improved system performance in network configuration, optimization, and self-healing, and the second phase added additional capabilities including intruder detection and situational awareness, and included a real-world demonstration to potential users.

Our study shows that algorithms used to check the similarity of data records affect the efficiency of a wrapper. A closer examination indicates that the accuracy of a wrapper can be improved if the DOM Tree and visual properties of data records can be fully utilized. In this paper, we develop algorithms to check the similarity of data records based on the distinct tags and visual cue of the tree structure of data records and the voting algorithm which can detect the similarity of data records of a relevant data region which may contain irrelevant information such as search identifiers to distinguish the potential data regions more correctly and eliminate data region only when necessary. Experimental results show that our wrapper performs better than state of the art wrapper WISH and it is highly effective in data extraction. This wrapper will be useful for meta search engine application, which needs an accurate tool to locate its source of information.

Modern compilers have many optimization passes which help to get a better binary code for a given program. These optimizations are NP-hard. People use different heuristics to get a near optimal solution. These heuristics are designed by a compiler expert after examining sample programs. This is a challenging task. Recently, people have used machine learning techniques instead of heuristics for compiler optimizations. Machine learning techniques have not only eliminated the human efforts but have also out-performed human made huristics. However, the human efforts have now been moved from creating heuristics to selecting good features. Selecting right set of features is important for machine learning techniques since no machine learning tool will work well with poorly choosen features. This paper introduces a noval approach to generate features for machine learning for compiler optimization problems with out any human involvement.

This paper proposes a new multi-objective approach for the problem of power restoration in (n-1) contingency situations. It builds on a previous, mono-objective approach introduced in Mendes et al. (2010) [14]. Power restoration normally relies on network reconfiguration, and typically involves re-switching and adjustment of tap-changers and capacitor banks. In this work, we focus on re-switching strategies. The quality of the re-switching strategy is measured in terms of voltage deviations, number of consumers still affected after the reconfiguration, number of overloaded branches and number of switches changes. Due to the number of criteria and conflicting objectives, power restoration is a prime candidate for multi-objective optimisation. The method studied is based on a genetic algorithm and was tested using two real-world networks, with up to of 1,645 branches and 158 switches. We present a contingency example for each network and discuss the results obtained. Finally, we discuss the approach’s convergence by analysing the evolution of the solutions that compose the Pareto frontier.

As expressive schema languages, Web Ontology Language (OWL) and Semantic Web Rule Language (SWRL) have been widely introduced to many industrial applications. Most existing OWL reasoners hold Open World Assumption (OWA) and do not hold Unique Name Assumption (UNA). They lack efficiency when they are applied to industrial models which capture information under Closed World Assumption (CWA) and UNA. To overcome the problem, this paper proposes a novel backward chained ABox reasoner which efficiently reasons through OWL and SWRL under CWA and UNA.

Since a social network, by definition, is so diverse, the problem of estimating the preferences of its users is becoming increasingly essential for personalized applications which range from service recommender systems to the targeted advertising of services. However, unlike traditional estimation problems where the underlying target distribution is stationary, estimating a user’s interests, typically, involves non-stationary distributions. The consequent time varying nature of the distribution to be tracked imposes stringent constraints on the “

unlearning

” capabilities of the estimator used. Therefore, resorting to strong estimators that converge with probability 1 is inefficient since they rely on the assumption that the distribution of the user’s preferences is stationary. In this vein, we propose to use a family of stochastic-learning based

Weak

estimators for learning and tracking user’s time varying interests. Experimental results demonstrate that our proposed paradigm outperforms some of the traditional legacy approaches that represent the state-of-the-art.

In an auction market where the price of each selling item is restricted to an admissible interval (price rigidities), a Walrasian equilibrium usually fails to exist. Dreze (1975) introduced a variant concept of Walrasian equilibrium based on rationing systems, named constrained Walrasian equilibrium, for modelling an economy with price rigidities. Talman and Yang (2008) further refined the concept and proposed a dynamic auction procedure that converges to a constrained Walrasian equilibrium. However, a constrained Walrasian equilibrium does not guarantee market efficiency. In other words, a constrained Walrasian equilibrium allocation does not necessarily lead to the best market value. In this paper, we introduce a concept of competitive equilibrium by weakening the concept of constrained Walrasian equilibrium and devise an dynamic auction procedure that generates an efficient competitive equilibrium.