Integrating memetic search into the BioHEL evolutionary learning system for large-scale datasets

Local search methods are widely used to improve the performance of evolutionary computation algorithms in all kinds of domains. Employing advanced and efficient exploration mechanisms becomes crucial in complex and very large (in terms of search space) problems, such as when employing evolutionary algorithms to large-scale data mining tasks. Recently, the GAssist Pittsburgh evolutionary learning system was extended with memetic operators for discrete representations that use information from the supervised learning process to heuristically edit classification rules and rule sets. In this paper we first adapt some of these operators to BioHEL, a different evolutionary learning system applying the iterative learning approach, and afterwards propose versions of these operators designed for continuous attributes and for dealing with noise. The performance of all these operators and their combination is extensively evaluated on a broad range of synthetic large-scale datasets to identify the settings that present the best balance between efficiency and accuracy. Finally, the identified best configurations are compared with other classes of machine learning methods on both synthetic and real-world large-scale datasets and show very competent performance.     

HPBILc: A histogram-based EDA for continuous optimization

Designing different estimation of distribution algorithms for continuous optimization is a recent emerging focus in the evolutionary computation field. This paper proposes an improved population-based incremental learning algorithm using histogram probabilistic model for continuous optimization. Histogram models are advantageous in describing the solution distribution of complex and multimodal continuous problems. The algorithm utilizes the sub-dividing strategy to guarantee the accuracy of optimal solutions. Experimental results show that the proposed algorithm is effective and it obtains better performance than the fast evolutionary programming (FEP) and those newly published EDAs in most test functions.     

Ten years of genetic fuzzy systems: current framework and new trends

Fuzzy systems have demonstrated their ability to solve different kinds of problems in various application domains. Currently, there is an increasing interest to augment fuzzy systems with learning and adaptation capabilities. Two of the most successful approaches to hybridise fuzzy systems with learning and adaptation methods have been made in the realm of soft computing. Neural fuzzy systems and genetic fuzzy systems hybridise the approximate reasoning method of fuzzy systems with the learning capabilities of neural networks and evolutionary algorithms.The objective of this paper is to provide an account of genetic fuzzy systems, with special attention to genetic fuzzy rule-based systems. After a brief introduction to models and applications of genetic fuzzy systems, the field is overviewed, new trends are identified, a critical evaluation of genetic fuzzy systems for fuzzy knowledge extraction is elaborated, and open questions that remain to be addressed in the future are raised. The paper also includes some of the key references required to quickly access implementation details of genetic fuzzy systems.     

Some relationships between fuzzy and random set-based classifiers and models

When designing rule-based models and classifiers, some precision is sacrificed to obtain linguistic interpretability. Understandable models are not expected to outperform black boxes, but usually fuzzy learning algorithms are statistically validated by contrasting them with black-box models. Unless performance of both approaches is equivalent, it is difficult to judge whether the fuzzy one is doing its best, because the precision gap between the best understandable model and the best black-box model is not known.In this paper we discuss how to generate probabilistic rule-based models and classifiers with the same structure as fuzzy rule-based ones. Fuzzy models, in which features are partitioned into linguistic terms, will be compared to probabilistic rule-based models with the same number of terms in every linguistic partition. We propose to use these probabilistic models to estimate a lower precision limit which fuzzy rule learning algorithms should surpass.     

Distributing evolutionary computation in a networked multi-agent environment

It has become increasingly popular to employ evolutionary algorithms to solve problems in different domains, and parallel models have been widely used for performance enhancement. Instead of using parallel computing facilities or public computing systems to speed up the computation, we propose to implement parallel evolutionary computation models on networked personal computers (PCs) that are locally available and manageable. To realize the parallelism, a multi-agent system is presented in which mobile agents play the major roles to carry the code and move from machine to machine to complete the computation dynamically. To evaluate the proposed approach, we use our multi-agent system to solve two types of time-consuming applications. Different kinds of experiments were conducted to assess the developed system, and the preliminary results show its promise and efficiency.     

Marginal and simultaneous predictive classification using stratified graphical models

An inductive probabilistic classification rule must generally obey the principles of Bayesian predictive inference, such that all observed and unobserved stochastic quantities are jointly modeled and the parameter uncertainty is fully acknowledged through the posterior predictive distribution. Several such rules have been recently considered and their asymptotic behavior has been characterized under the assumption that the observed features or variables used for building a classifier are conditionally independent given a simultaneous labeling of both the training samples and those from an unknown origin. Here we extend the theoretical results to predictive classifiers acknowledging feature dependencies either through graphical models or sparser alternatives defined as stratified graphical models. We show through experimentation with both synthetic and real data that the predictive classifiers encoding dependencies have the potential to substantially improve classification accuracy compared with both standard discriminative classifiers and the predictive classifiers based on solely conditionally independent features. In most of our experiments stratified graphical models show an advantage over ordinary graphical models.     

Divide-and-Conquer With Sequential Monte Carlo

We propose a novel class of Sequential Monte Carlo (SMC) algorithms, appropriate for inference in probabilistic graphical models. This class of algorithms adopts a divide-and-conquer approach based upon an auxiliary tree-structured decomposition of the model of interest, turning the overall inferential task into a collection of recursively solved subproblems. The proposed method is applicable to a broad class of probabilistic graphical models, including models with loops. Unlike a standard SMC sampler, the proposed divide-and-conquer SMC employs multiple independent populations of weighted particles, which are resampled, merged, and propagated as the method progresses. We illustrate empirically that this approach can outperform standard methods in terms of the accuracy of the posterior expectation and marginal likelihood approximations. Divide-and-conquer SMC also opens up novel parallel implementation options and the possibility of concentrating the computational effort on the most challenging subproblems. We demonstrate its performance on a Markov random field and on a hierarchical logistic regression problem. Supplementary materials including proofs and additional numerical results are available online.     

Computing lower and upper expectations under epistemic independence

This paper investigates the computation of lower/upper expectations that must cohere with a collection of probabilistic assessments and a collection of judgements of epistemic independence. New algorithms, based on multilinear programming, are presented, both for independence among events and among random variables. Separation properties of graphical models are also investigated.     

Improvements to Variable Elimination and Symbolic Probabilistic Inference for evaluating Influence Diagrams

An Influence Diagram is a probabilistic graphical model used to represent and solve decision problems under uncertainty. Its evaluation requires performing several combinations and marginalizations on the potentials attached to the Influence Diagram. Finding an optimal order for these operations, which is NP-hard, is an element of crucial importance for the efficiency of the evaluation. In this paper, two methods for optimizing this order are proposed. The first one is an improvement of the Variable Elimination algorithm while the second is the adaptation of the Symbolic Probabilistic Inference for evaluating Influence Diagrams. Both algorithms can be used for the direct evaluation of IDs but also for the computation of clique-to-clique messages in Lazy Evaluation of Influence Diagrams. In the experimental work, the efficiency of these algorithms is tested with several Influence Diagrams from the literature.     

Asymptotic Bayesian structure learning using graph supports for Gaussian graphical models

The theory of Gaussian graphical models is a powerful tool for independence analysis between continuous variables. In this framework, various methods have been conceived to infer independence relations from data samples. However, most of them result in stepwise, deterministic, descent algorithms that are inadequate for solving this issue. More recent developments have focused on stochastic procedures, yet they all base their research on strong a priori knowledge and are unable to perform model selection among the set of all possible models. Moreover, convergence of the corresponding algorithms is slow, precluding applications on a large scale. In this paper, we propose a novel Bayesian strategy to deal with structure learning. Relating graphs to their supports, we convert the problem of model selection into that of parameter estimation. Use of non-informative priors and asymptotic results yield a posterior probability for independence graph supports in closed form. Gibbs sampling is then applied to approximate the full joint posterior density. We finally give three examples of structure learning, one from synthetic data, and the two others from real data.     

A Survey of Optimization by Building and Using Probabilistic Models

This paper summarizes the research on population-based probabilistic search algorithms based on modeling promising solutions by estimating their probability distribution and using the constructed model to guide the exploration of the search space. It settles the algorithms in the field of genetic and evolutionary computation where they have been originated, and classifies them into a few classes according to the complexity of models they use. Algorithms within each class are briefly described and their strengths and weaknesses are discussed.     

Data association based on optimization in graphical models with application to sensor networks

We propose techniques based on graphical models for efficiently solving data association problems arising in multiple target tracking with distributed sensor networks. Graphical models provide a powerful framework for representing the statistical dependencies among a collection of random variables, and are widely used in many applications (e.g., computer vision, error-correcting codes). We consider two different types of data association problems, corresponding to whether or not it is known a priori which targets are within the surveillance range of each sensor. We first demonstrate how to transform these two problems to inference problems on graphical models. With this transformation, both problems can be solved efficiently by local message-passing algorithms for graphical models, which solve optimization problems in a distributed manner by exchange of information among neighboring nodes on the graph. Moreover, a suitably reweighted version of the max–product algorithm yields provably optimal data associations. These approaches scale well with the number of sensors in the network, and moreover are well suited to being realized in a distributed fashion. So as to address trade-offs between performance and communication costs, we propose a communication-sensitive form of message-passing that is capable of achieving near-optimal performance using far less communication. We demonstrate the effectiveness of our approach with experiments on simulated data.     

A novel multi-objective memetic algorithm based on opposition-based self-adaptive differential evolution

Under the framework of evolutionary paradigms, many evolutionary algorithms have been designed for handling multi-objective optimization problems. Each of the different algorithms may display exceptionally good performance in certain optimization problems, but none of them can be completely superior over one another. As such, different evolutionary algorithms are being synthesized to complement each other in view of their strengths and the limitations inherent in them. In this study, the novel memetic algorithm known as the Opposition-based Self-adaptive Hybridized Differential Evolution algorithm (OSADE) is being comprehensively investigated through a comparative study with some state-of-the-art algorithms, such as NSGA-II, non-dominated sorting Differential Evolution (NSDE), MOEA/D-SBX, MOEA/D-DE and the Multi-objective Evolutionary Gradient Search (MO-EGS) by using a suite of different benchmark problems. Through the experimental results that are presented by employing the Inverted Generational Distance (IGD) and the Hausdorff Distance performance indicators, it is seen that OSADE is able to achieve competitive, if not better, performance when compared to the other algorithms in this study.     

Learning temporal nodes Bayesian networks

Temporal Nodes Bayesian Networks (TNBNs) are an alternative to Dynamic Bayesian Networks for temporal reasoning with much simpler and efficient models in some domains. TNBNs are composed of temporal nodes, temporal intervals, and probabilistic dependencies. However, methods for learning this type of models from data have not yet been developed. In this paper, we propose a learning algorithm to obtain the structure and temporal intervals for TNBNs from data. The method consists of three phases: (i) obtain an initial approximation of the intervals, (ii) obtain a structure using a standard algorithm and (iii) refine the intervals for each temporal node based on a clustering algorithm. We evaluated the method with synthetic data from three different TNBNs of different sizes. Our method obtains the best score using a combined measure of interval quality and prediction accuracy, and a competitive structural quality with lower running times, compared to other related algorithms. We also present a real world application of the algorithm with data obtained from a combined cycle power plant in order to diagnose temporal faults.     

网络路径问题及其多目标扩展形式的混合进化算法

本文就几类困难的网络路径问题及其多目标扩展形式给出相应的混合型进化算法,并在微机上予以实现,为复杂的组合优化问题提供了新的求解手段．     

Structural-EM for learning PDG models from incomplete data

Probabilistic Decision Graphs (PDGs) are a class of graphical models that can naturally encode some context specific independencies that cannot always be efficiently captured by other popular models, such as Bayesian Networks. Furthermore, inference can be carried out efficiently over a PDG, in time linear in the size of the model. The problem of learning PDGs from data has been studied in the literature, but only for the case of complete data. We propose an algorithm for learning PDGs in the presence of missing data. The proposed method is based on the Expectation-Maximisation principle for estimating the structure of the model as well as the parameters. We test our proposal on both artificially generated data with different rates of missing cells and real incomplete data. We also compare the PDG models learnt by our approach to the commonly used Bayesian Network (BN) model. The results indicate that the PDG model is less sensitive to the rate of missing data than BN model. Also, though the BN models usually attain higher likelihood, the PDGs are close to them also in size, which makes the learnt PDGs preferable for probabilistic inference purposes.     

Word problems in mathematics education: a survey

Word problems are among the most difficult kinds of problems that mathematics learners encounter. Perhaps as a result, they have been the object of a tremendous amount research over the past 50 years. This opening article gives an overview of the research literature on word problem solving, by pointing to a number of major topics, questions, and debates that have dominated the field. After a short introduction, we begin with research that has conceived word problems primarily as problems of comprehension, and we describe the various ways in which this complex comprehension process has been conceived theoretically as well as the empirical evidence supporting different theoretical models. Next we review research that has focused on strategies for actually solving the word problem. Strengths and weaknesses of informal and formal solution strategies—at various levels of learners’ mathematical development (i.e., arithmetic, algebra)—are discussed. Fourth, we address research that thinks of word problems as exercises in complex problem solving, requiring the use of cognitive strategies (heuristics) as well as metacognitive (or self-regulatory) strategies. The fifth section concerns the role of graphical representations in word problem solving. The complex and sometimes surprising results of research on representations—both self-made and externally provided ones—are summarized and discussed. As in many other domains of mathematics learning, word problem solving performance has been shown to be significantly associated with a number of general cognitive resources such as working memory capacity and inhibitory skills. Research focusing on the role of these general cognitive resources is reviewed afterwards. The seventh section discusses research that analyzes the complex relationship between (traditional) word problems and (genuine) mathematical modeling tasks. Generally, this research points to the gap between the artificial word problems learners encounter in their mathematics lessons, on the one hand, and the authentic mathematical modeling situations with which they are confronted in real life, on the other hand. Finally, we review research on the impact of three important elements of the teaching/learning environment on the development of learners’ word problem solving competence: textbooks, software, and teachers. It is shown how each of these three environmental elements may support or hinder the development of learners’ word problem solving competence. With this general overview of international research on the various perspectives on this complex and fascinating kind of mathematical problem, we set the scene for the empirical contributions on word problems that appear in this special issue.

     

Comparison of strategy learning methods in Farmer–Pest problem for various complexity environments without delays

In this paper effectiveness of several agent strategy learning algorithms is compared in a new multi-agent Farmer–Pest learning environment. Learning is often utilized by multi-agent systems which can deal with complex problems by means of their decentralized approach. With a number of learning methods available, a need for their comparison arises. This is why we designed and implemented new multi-dimensional Farmer–Pest problem domain, which is suitable for benchmarking learning algorithms. This paper presents comparison results for reinforcement learning (SARSA) and supervised learning (Naïve Bayes, C4.5 and Ripper). These algorithms are tested on configurations with various complexity with not delayed rewards. The results show that algorithm performances depend highly on the environment configuration and various conditions favor different learning algorithms.     

Multi-dimensional classification with Bayesian networks

Multi-dimensional classification aims at finding a function that assigns a vector of class values to a given vector of features. In this paper, this problem is tackled by a general family of models, called multi-dimensional Bayesian network classifiers (MBCs). This probabilistic graphical model organizes class and feature variables as three different subgraphs: class subgraph, feature subgraph, and bridge (from class to features) subgraph. Under the standard 0-1 loss function, the most probable explanation (MPE) must be computed, for which we provide theoretical results in both general MBCs and in MBCs decomposable into maximal connected components. Moreover, when computing the MPE, the vector of class values is covered by following a special ordering (gray code). Under other loss functions defined in accordance with a decomposable structure, we derive theoretical results on how to minimize the expected loss. Besides these inference issues, the paper presents flexible algorithms for learning MBC structures from data based on filter, wrapper and hybrid approaches. The cardinality of the search space is also given. New performance evaluation metrics adapted from the single-class setting are introduced. Experimental results with three benchmark data sets are encouraging, and they outperform state-of-the-art algorithms for multi-label classification.     

Reference classes and relational learning

This paper studies the connections between relational probabilistic models and reference classes, with specific focus on the ability of these models to generate the correct answers to probabilistic queries. We distinguish between relational models that represent only observed relations and those which additionally represent latent properties of individuals. We show how both types of relational models can be understood in terms of reference classes, and that learning such models correspond to different ways of identifying reference classes. Rather than examining the impact of philosophical issues associated with reference classes on relational learning, we directly assess whether relational models can represent the correct probabilities of a simple generative process for relational data. We show that models with only observed properties and relations can only represent the correct probabilities under restrictive conditions, whilst models that also represent latent properties avoids such restrictions. As such, methods for acquiring latent-property models are an attractive alternatives to traditional ways of identifying reference classes. Our experiments on synthetic as well as real-world domains support the analysis, demonstrating that models with latent relations are significantly more accurate than those without latent relations.