This paper presents the Min-Cut Bayesian Network Consensus (MCBNC) algorithm, a greedy method for structural consensus of Bayesian Networks (BNs), with applications in federated learning and model aggregation. MCBNC prunes weak edges from an initial unrestricted fusion using a structural score based on min-cut analysis, integrated into a modified Backward Equivalence Search (BES) phase of the Greedy Equivalence Search (GES) algorithm. The score quantifies edge support across input networks and is computed using max-flow. Unlike methods with fixed treewidth bounds, MCBNC introduces a pruning threshold θ that can be selected post hoc using only structural information. Experiments on real-world BNs show that MCBNC yields sparser, more accurate consensus structures than both canonical fusion and the input networks. The method is scalable, data-agnostic, and well-suited for distributed or federated structural learning of BNs or causal discovery.

Abstract The increasing complexity of software development has prompted a shift in project management practices toward agile methodologies, often supported by specialized software tools for planning and reporting. However, many widely adopted tools offer only limited decision support capabilities. This work introduces ProjectION, an intelligent software tool designed to enhance decision-making in agile project management through techniques relative to the Search-Based Software Engineering field. Based on an in-depth analysis of the challenges faced in agile environments, ProjectION assists decision makers in monitoring project status, forecasting progress, and automating software release planning. A comprehensive usability study was conducted with a small sample of experienced IT professionals, following the ISO/IEC 25062:2006 Common Industry Format. Key usability metrics of effectiveness, efficiency, and user satisfaction were assessed. Despite minor usability issues, results indicate that ProjectION effectively supports agile release planning. A second experiment further demonstrates the tool’s utility in generating optimal release plans, outperforming manual solutions proposed by decision makers. To foster collaboration and future development, the core algorithms and execution service have been made publicly available, enabling integration of novel approaches to the Next Release Problem.

Agile methodologies are widely adopted in the industry, with iterative development being a common practice. However, this approach introduces certain risks in controlling and managing the planned scope for delivery at the end of each iteration. Previous studies have proposed machine learning methods to predict the likelihood of meeting this committed scope, using models trained on features extracted from prior iterations and their associated tasks. A crucial aspect of any predictive model is user trust, which depends on the model’s explainability. However, an excessive number of features can complicate interpretation. In this work, we propose feature subset selection methods to reduce the number of features without compromising model performance.To ensure interpretability, we leverage state-of-the-art explainability techniques to analyze the key features driving model predictions. Our evaluation, conducted on five large open-source projects from prior studies, demonstrates successful feature subset selection, reducing the feature set to 10% of its original size without any loss in predictive performance. Using explainability tools, we provide a synthesis of the features with the most significant impact on iteration performance predictions across agile projects.

Bayesian Network (BN) fusion combines multiple input networks into a single structure, balancing dependency preservation with computational tractability. While unrestricted fusion retains all dependencies, it often results in overly complex networks with high treewidth, which affects inference scalability. Limited fusion mitigates this by pruning edges to control treewidth but risks overfitting to input-specific noise and omitting dependencies from the original BNs. This paper introduces a consensus framework that prioritizes shared structures among input networks while enforcing treewidth constraints, ensuring a good consensus. We propose genetic algorithms with advanced initialization, specialized operators, and a tailored fitness function. Additionally, we adapt existing methods to this problem and implement greedy baselines for benchmarking and further optimization. Experiments on synthetic and real-world BNs show the superiority of the proposed genetic algorithms over the adapted methods and greedy baselines.

We propose ODTE , a new ensemble that uses oblique decision trees as base classifiers. Additionally, we introduce STree, the base algorithm for growing oblique decision trees, which leverages support vector machines to define hyperplanes within the decision nodes. We embed a multiclass strategy (one-vs-one or one-vs-rest) at the decision nodes, allowing the model to directly handle non-binary classification tasks without the need to cluster instances into two groups, as is common in other approaches from the literature. In each decision node, only the best-performing model (SVM)—the one that minimizes an impurity measure for the n-ary classification—is retained, even if the learned SVM addresses a binary classification subtask. An extensive experimental study involving 49 datasets and various state-of-the-art algorithms for oblique decision tree ensembles has been conducted. Our results show that ODTE ranks consistently above its competitors, achieving significant performance gains when hyperparameters are carefully tuned. Moreover, the oblique decision trees learned through STree are more compact than those produced by other algorithms evaluated in our experiments.

This paper introduces an evolutionary computation approach for consensus in structural Bayesian Network (BN) fusion under the constraint of limited treewidth. The consensus BN aims to reconcile multiple input BNs into a single one that retains key structural features present in the original networks. Treewidth, a graph-based parameter associated with computationally tractable inference, is utilized to restrict the complexity of the resulting network. A genetic algorithm is proposed to look for a BN that codifies as much information about the unrestricted fusion as possible while ensuring the treewidth restriction. Experimental evaluation demonstrates the genetic algorithm's ability to obtain consensus BNs with limited treewidth, providing a valuable tool for aggregating information from diverse sources while returning a computationally actionable model.

Abstract Ensemble of label ranking trees (LRTs) are currently the state‐of‐the‐art approaches to the label ranking problem. Recently, bagging, boosting, and random forest methods have been proposed, all based on the LRT algorithm, which adapts regression/classification trees to the label classification problem. The LRT algorithm uses theoretically grounded Mallows probability distribution to select the best split when growing the tree, and an EM‐type process to complete the rankings on the training data when they are incomplete. These two steps have proven to be accurate, but require a large computational effort. This article proposes two alternative methods that replace the use of the Mallows distribution with distance‐based criteria to select the best split at each inner node of the tree. Moreover, these distance‐based criteria allow dealing with incomplete rankings natively, so avoiding the completion process. We have carried out an extensive experimental evaluation, which shows that (1) the integration of the two proposed modifications to the LRT algorithm into ensemble methods (bagging and random forest) are an order of magnitude faster than using the original Mallows‐based LRT algorithm; (2) ensembles using the proposed LRT methods are significantly more accurate in the presence of incomplete rankings, while they are at least as accurate in the complete case; and (3) the two modified LRT algorithms are also an order of magnitude faster than the Mallows‐based LRT, while they are at least as accurate as the Mallows‐based LRT on both complete and incomplete rankings.

Learning Bayesian Networks (BNs) from high-dimensional data is a complex and time-consuming task. Although the literature includes approaches based on horizontal (instances) or vertical (variables) partitioning, none can guarantee the same theoretical properties as the Greedy Equivalence Search (GES) algorithm, except those based on the GES algorithm itself. This paper proposes a distributed BN learning algorithm that uses GES as the local learning algorithm, ensuring the same theoretical properties as GES but requiring less CPU time. The two main novelties in our proposed method are (1) the distribution of the set of possible edges among local learning processes, which are constrained to only use its local edge set; and (2) the use of BN fusion to aggregate the networks learned constrained to local edge sets. The algorithm is iterative, and at each step, the last aggregated network is used as the starting point by each local BN process. After a comprehensive experimental evaluation, the results show that the proposed algorithm (pGES) obtains networks of equal or better quality than GES in less computational time. This improvement is especially noticeable in high-dimensional BNs.

Label ranking studies the problem of learning a preference model that maps instances to rankings over a finite set of predefined class labels. The training data used to solve this problem consists of instances labeled with rankings. Since these rankings are often incomplete, models need to be able to deal with missing information in the class labels to be more useful in practice. Several decision tree models have been proposed to learn from incomplete rankings, mainly using axis-parallel decision nodes, which is the standard approach for decision tree induction. In contrast to this strategy, this present work introduces a method for learning oblique decision trees for the label ranking problem, as they have been shown to improve performance in the standard classification scenario. Our experimentation shows that this method offers several advantages over the current decision tree model. Not only does it generate more compact tree structures, but it is also shown to achieve outstandingly better results for complete rankings and in cases with a low percentage of missing labels. Moreover, the proposed method is faster in the largest datasets than the current decision tree model.

Release planning is a critical step in the development of a software product, and it involves many factors. Deciding what to build for the next software release requires taking into account not only the cost of building a subset of software features, but also the expected satisfaction of the clients, as well as the dependencies that the features might have among them. This problem, called Next Release Problem, can be difficult to tackle by expert judge, or even intractable if the number of requirements, dependencies and clients to consider is very large. In the literature, this problem has been approached from the so-called search-based software engineering field, introducing a variety of metaheuristic algorithms to obtain a subset of release proposals that simultaneously optimise both cost and satisfaction. In this work, we present a GRASP-based advanced method, and evaluate it against other families of algorithms commonly applied to this problem, using two public and four synthetic datasets for the evaluation. Results show that solutions obtained by our proposal are superior to those of other algorithms in terms of quality indicators and speed of execution. Algorithms, datasets and evaluation framework have been made available to the research community.

In the development of a software product, the Next Release Problem is the selection of the most appropriate subset of requirements (tasks) to include in the next release of the product, such that the selected subset maximises the overall satisfaction of the stakeholders and minimises the total cost. Furthermore, in most cases, requirements or tasks cannot be developed independently, as there are dependencies between them, which must be respected in the selection for the next release. In this paper, we approach the Next Release Problem as a constrained bi-objective optimisation problem. The main contribution is the design of an Estimation of Distribution Algorithm that exploits domain knowledge, i.e. the dependencies between the requirements, to define the structure of a Bayesian network that models the relationships between the binary variables (requirements) to be optimised. The use of a Bayesian network with a fixed structure reduces the complexity of the search process, since it is unnecessary to learn the structure at each iteration of the algorithm. Moreover, it ensures that the sampled individuals are always valid with respect to the required dependencies. The second main contribution is the generation of a corpus of synthetic datasets with cost estimations derived from agile and classic management methodologies. Standard multi-objective metrics are computed in order to assess our proposal and compare it with other evolutionary multi-criterion optimisation algorithms, determining that it is the optimal choice when dealing with complex datasets.

The label ranking problem consists in learning preference models from training datasets labeled with (possibly incomplete) rankings of the class labels. The goal is then to predict a ranking for a given unlabeled instance. This work focuses on a more general interpretation where both the training dataset and the prediction given as output allow tied class labels, i.e., there is no particular preference between them. This problem is known as the partial label ranking problem. This paper tackles the partial label ranking problem by transforming the ranking with ties into a set of discrete variables representing the preference relations (ranked ahead, tied with, and ranked behind) between each pair of class labels. The posterior probabilities for each pair are then used to fill the values of a preference matrix. This preference matrix is the basis for solving the rank aggregation problem required to obtain the output ranking with ties. This paper aims to exploit the resemblance of this problem with multi-label and multi-dimensional classification by studying the use of Bayesian network classifiers to compute the posterior probabilities for the new class structure, i.e., pairs of class labels. In particular, binary relevance with naive Bayes and averaged one-dependence estimators between the new class structure are used to solve the partial label ranking problem. Furthermore, bivariate relationships between all the pairs of class labels are considered. However, the complexity of the model grows significantly, which makes it necessary to reduce the number of allowed bivariate relationships between pairs. Thus, a feature selection method is included to select the more relevant subset of bivariate relationships. The experimental evaluation shows that our proposals are competitive in accuracy with the current instance-based and decision tree induction algorithms. Moreover, they outperform the existing mixture-based probabilistic graphical models, while the algorithms proposed are much faster.

The partial label ranking problem is a particular preference learning scenario that focuses on learning preference models from data, such that they predict a complete ranking with ties defined over the values of the class variable for a given input instance. This work proposes to transform the rankings into preference relations among pairs of class labels and to learn a standard classifier for each of them. This classifier is then used to estimate the probability of each event from the preference relation between the two compared class labels. Finally, the probabilities obtained for each preference comparison are used to compute a preference matrix utilized to solve the corresponding rank aggregation problem and so obtain the ranking among all the class labels. The experimental evaluation shows that the proposed method is ranked ahead of competing algorithms in accuracy while obtaining similar CPU time results.

Classification algorithms have recently acquired great popularity due to their efficiency to generate models capable of solving high complexity problems. Specifically, black box models are the ones that offer the best results, since they greatly benefit from the enormous amount of data available to learn models in an increasingly accurate way. However, their main disadvantage compared to other simpler algorithms, e.g., decision trees, is the loss of interpretability for both the model and the individual classifications, which may become a major drawback because of the increasing number of applications where it is advisable and even compulsory to provide an explanation. A well-accepted practice is to build anexplainablemodel that can mimic the behavior of the (more complex) classifier in the neighborhood of the instance to be explained. Nonetheless, the generation of explanations in such white box models is not trivial either, which has generated intense research. It is common to generate two types of explanations, factual explanations and counterfactual explanations, which complement each other to justify why the instance has been classified into a certain class or category. In this work, we propose the definition of factual and counterfactual explanations in the frame of fuzzy decision trees, where multiple branches can be fired at once. Our proposal is centered around the definition of factual explanations that can contain more than a single rule, in contrast to the current standard that is limited to considering a single rule as a factual explanation. Moreover, we introduce the idea ofrobustfactual explanation. Finally, we provide procedures to obtain counterfactual explanations from the instance and also from a factual explanation.

The Label Ranking (LR) problem is a well-known nonstandard supervised classification problem, the goal of which is to learn preference classifiers from data, mapping instances to rankings of the labels of the class variable. In the literature, the particular setting where the output of the LR problem is a complete ranking without ties (a.k.a. permutation) has been profusely studied, and many algorithms have been designed to solve these particular instances based on the use of specific probability distributions and aggregation methods for permutations. However, also partial orders (a.k.a. bucket orders) can be considered as output in LR problems (i.e., some labels of the class variable may be tied), but the algorithms available do not tackle this kind of ranking. We refer to this particular case of LR as the Partial Label Ranking (PLR) problem. Thus, motivated by the lack of current methods to deal with the PLR problem, we design machine learning algorithms based on instance-based and decision tree approaches to tackle the PLR problem. We evaluate our proposals on a benchmark of 15 data sets obtained by transforming multiclass instances, and analyze their performance by carrying out a standard machine learning statistical analysis procedure.

The Optimal Bucket Order Problem (OBOP) is a rank aggregation problem which consists in finding a consensus ranking (with ties) that generalizes a set of input rankings. In this paper, with the aim of solving the OBOP in an efficient and scalable way, we propose several greedy algorithms based on different sort-first and cluster-second strategies. More specifically, the sorting step is based on the Borda method, whereas in the cluster step, pairs of adjacent buckets are suitably joined. The proposed methods are experimentally compared with the state-of-the-art greedy algorithms for solving the OBOP by using a large benchmark of real-world databases. Furthermore, we provide a complete statistical analysis of the experimental study, which shows that several of the proposed algorithms outperform the current state-of-the-art greedy algorithms. We also analyze the trade-off between accuracy and execution time of the algorithms to guide the users regarding the selection of the best option for each particular case. The study carried out shows that our proposal is not only competitive in terms of accuracy with the state-of-the-art evolutionary strategy for dealing with the OBOP, but is also fast and scalable.

As the data sets increase in size, the process of manually labeling data becomes unfeasible by small groups of experts. Thus, it is common to rely on crowdsourcing platforms which provide inexpensive, but noisy, labels. Although implementations of algorithms to tackle this problem exist, none of them focus on scalability, limiting the area of application to relatively small data sets. In this paper, we present spark-crowd, an Apache Spark package for learning from crowdsourced data with scalability in mind.

There is a wide variety of studies that propose different classifiers to solve a large amount of problems in distinct classification scenarios. The no free lunch theorem states that if we use a big enough set of varied problems, all classifiers would be equivalent in performance. From another point of view, the performance of the classifiers is dependant of the scope and properties of the datasets. In this sense, new proposals on the topic often focus on a given context, aiming at improving the related state-of-the-art approaches. Data complexity metrics have been traditionally used to determine the inner characteristics of datasets. This way, researchers are able to categorize the problems in different scenarios. Then, this taxonomy can be applied to determine inner characteristics of the datasets in order to determine intervals of good and bad behavior for a given classifier. In this paper, we will take advantage of the data complexity metrics in order to design a fuzzy metaclassifier. The final goal is to create decision rules based on the inner characteristics of the data to apply a different version of the fuzzy classifier for a given problem. To do so, we will make use of the FARC-HD classifier, an evolutionary fuzzy system that has led to different extensions in the specialized literature. Experimental results show the goodness of this novel approach as it is able to outperform all versions of FARC-HD on a wide set of problems, and obtain competitive results (in terms of performance and interpretability) versus two selected state-of-the-art rule-based classification system, C4.5 and FURIA.

Abstract The multilabel paradigm has recently attracted the attention of the machine learning community, multilabel problems being those which do not have only one class but several binomial classes instead. Although intensive research has been carried on lately into the multilabel classification paradigm, this is not the case of feature subset selection methods. In this work, we propose an adaptation of the well‐known CMIM feature selection algorithm, which is capable of approximating the conditional multivariate mutual information of each candidate attribute with respect to the whole set of labels. This capacity to search any degree of interaction among labels is the reason why our proposal performs better than other state‐of‐the‐art algorithms when the dataset on which it is run contains correlated labels.

Annual journal rankings are usually considered a tool for the evaluation of research and researchers. Although they are an objective resource for such evaluation, they also present drawbacks: (a) the uncertainty about the definite position of a target journal in the corresponding annual ranking when selecting a journal, and (b) in spite of the nonsignificant difference in score (for instance, impact factor) between consecutive journals in the ranking, the journals are strictly ranked and eventually placed in different terciles/quartiles, which may have a significant influence in the subsequent evaluation. In this article we present several proposals to obtain an aggregated consensus ranking as an alternative/complementary tool to standardize annual rankings. To illustrate the proposed methodology we use as a case study the Journal Citation Reports, and in particular the category of Computer Science: Artificial Intelligence (CS:AI). In the context of the consensus rankings obtained by the different methods, we discuss the convenience of using one or the other procedure according to the corresponding framework. In particular, our proposals allow us to obtain consensus rankings that avoid crisp frontiers between similarly ranked journals and consider the longitudinal/temporal evolution of the journals.

In this work, we propose several algorithms for learning first-order TSK fuzzy rules. These methods, consist of two stages: first, they generate a set of candidate rules with an adaptation of the apriori algorithm for frequent itemset detection. Then, they select a subset of such rules, generally by means of a search algorithm. In this work we have tested a genetic and two different local search algorithms. The results obtained show that, genetic algorithms tends to converge to systems with a higher number of rules, which minimize the training error, but also overfit. On the other hand, local search gets stuck in configurations with fewer rules which, despite producing a higher training error, avoid overfitting and lead to best results in terms of error.

High Efficiency Video Coding (HEVC) was developed by the Joint Collaborative Team on Video Coding to replace the current H.264/Advanced Video Coding (AVC) standard, which has dominated digital video services in all segments of the domestic and professional markets for over ten years. Therefore, there is a lot of legacy content encoded with H.264/AVC, and an efficient video transcoding from H.264/AVC to HEVC will be needed to enable gradual migration to HEVC. In terms of rate-distortion (RD) performance, HEVC roughly doubles the RD compression performance of H.264/AVC at the expense of a high computational cost. HEVC adopts a quadtree-based coding unit (CU) block partitioning structure that is flexible in adapting various texture characteristics of images. However, this causes a dramatic increase in computational complexity due to the necessity of finding the best CU partitions. This paper presents an adaptive fast quadtree level decision algorithm that is designed to exploit the information gathered at the H.264/AVC decoder in order to make faster decisions on CU splitting in HEVC using a Naïve-Bayes probabilistic classifier that is determined by a supervised data mining process. The experimental results show that the proposed algorithm can achieve a good tradeoff between coding efficiency and complexity compared with the anchor transcoder; moreover, it outperforms other related works available in the literature.

High Efficiency Video Coding was developed by the JCT-VC to replace the current H.264/AVC standard, which has dominated digital video services in all segments of the domestic and professional markets for over ten years. Therefore, there is a lot of legacy content encoded with H.264/AVC, and an efficient video transcoding from H.264 to HEVC will be needed to enable gradual migration to HEVC. HEVC adopts a quad tree-based Coding Unit block partitioning structure that is flexible in adapting various texture characteristics at the expense of a high computational cost. This paper presents a data-driven probabilistic CTU splitting algorithm that is designed to exploit the information gathered at the H.264/AVC decoder in order to make faster decisions on CU splitting in HEVC. Experimental results show that the proposed algorithm can achieve a good tradeoff between coding efficiency and complexity compared with the anchor transcoder, and, moreover, it outperforms other related works available in the literature.

Structural learning of Bayesian networks is a very expensive task even when sacrifying the optimality of the result. Because of that, there are some proposals aimed at obtaining relative-quality solutions in short times. One of them, namely Chain-ACO, searches an ordering among all variables with Ant Colony Optimization and a chain-structured surrogate model, and then uses this ordering to build a Bayesian network by means of the well-known K2 algorithm.

Learning Bayesian networks is known to be an NP-hard problem, and this, combined with the growing interest in learning models from high-dimensional domains, leads to the necessity of finding more efficient learning algorithms. Recent papers have proposed constrained approaches of successfully and widely used local search algorithms, such as Hill Climbing. One of these algorithms families, called constrained Hill Climbing (CHC), greatly improves upon the efficiency of the original approach, obtaining models with slightly lower quality but maintaining their theoretical properties. In this paper, we propose three different modifications to the most scalable version of these algorithms, fast constrained Hill Climbing, to improve the quality of its output by relaxing the constraints imposed to include some diversification in the search process. The aim of these new approaches is to adjust the trade-off between efficiency and accuracy of the algorithm, as they do not modify its complexity and only imply a few more search iterations. We perform an intensive experimental evaluation of the modifications proposed with an extensive comparison between the original algorithms and the new modifications covering several scenarios with quite large data sets. Available code and data for further use of the algorithms presented in this paper and experiment replication can be available at http://simd.albacete.org/supplements/FastCHC.html.

The High Efficiency Video Coding (HEVC) was developed by the Joint Collaborative Team on Video Coding (JCT-VC) to replace the current H.264/AVC standard which has been widely adopted in the last years. Therefore, there is a lot of legacy content encoded with H.264/AVC and an efficient conversion to HEVC is needed. This paper, presents a Fast Quadtree Level Decision (FQLD) algorithm that greatly reduces the complexity of the transcoding process between H.264/AVC and HEVC. The proposal tries to exploit the information gathered at the H.264/AVC decoder to make decisions on Coding Units (CU) splitting in HEVC using a Naïve-Bayes (NB) probabilistic classifier. Experimental results show that the proposed transcoder can achieve a good tradeoff between coding efficiency and complexity.

There exist a wide number of works in the literature related to new systems devoted to manage thermal control in buildings. Commonly, their evaluation is performed by using simulation of users and environmental conditions. Thus, in this work we choose a successful thermal-comfort system, formerly evaluated with simulations, and evaluate it by using data from project ASHRAE RP-884, which provides logs of real data coming from different buildings, in a wide variety of climates, and occupied by people with different thermal preferences. From these logs, we propose a pre-processing and evaluation methodology in order to achieve more realistic evaluations.

In this paper we present an extension to the classical k-dependence Bayesian network classifier algorithm. The original method intends to work for the whole continuum of Bayesian classifiers, from naïve Bayes to unrestricted networks. In our experience, it performs well for low values of k. However, the algorithm tends to degrade in more complex spaces, as it greedily tries to add k dependencies to all feature nodes of the resulting net.

Feature subset selection has become an expensive process due to the relatively recent appearance of high-dimensional databases. Thus, not only the need has arisen for reducing the dimensionality of these datasets, but also for doing it in an efficient way. We propose a new backward search, where attributes are removed given several smart criteria found in the literature and, besides, it is guided using a heuristic which reduces the cost and needed number of evaluations commonly expected from a backward search. Besides, we do not only propose the design of a new forward-backward algorithm but we also provide an experimental study of different criteria to decide the removal of attributes. The result is a very competitive algorithm which does not exceed the in-practice linear complexity while obtaining selected subsets of features with lower cardinality than other state-of-the-art algorithms.

The COR methodology allows the learning of Linguistic Fuzzy Rule-Based Systems by considering cooperation among rules. In order to do that, COR firstly finds the set of candidate fuzzy rules that can be fired by the examples in the training set, and then uses a search algorithm to find the final set of rules. In the algorithms proposed so far, all candidate rules have the same number of antecedents, which is the number of input variables. However, these rules could be too specific, and rules more generic are not considered. In this paper we study the effect of considering all possible rules, regardless of their number of antecedents. Experiments show that the rule bases obtained use simpler rules, and the results for the error of prediction improve upon those obtained by using classical COR methods.

The Averaged One-Dependence Estimators (AODE) classifier is one of the most attractive semi-naive Bayesian classifiers and hence a good alternative to Naive Bayes (NB), as it obtains fairly low error rates maintaining under control the computational complexity. Unfortunately, as most of the methods designed within the framework of Bayesian networks, AODE is exclusively defined to deal with discrete variables. Several approaches to avoid the use of discretization pre-processing techniques have already been presented, all of them involving in lower or greater degree the assumption of (conditional) Gaussian distributions. In this paper, we propose the use of Mixture of Truncated Exponentials (MTEs), whose expressive power to accurately approximate the most commonly used distributions for hybrid networks has already been demonstrated. We perform experiments on the use of MTEs over a large group of datasets for the first time, and we analyze the importance of selecting a proper number of points when learning MTEs for NB and AODE, as we believe, it is decisive to provide accurate results.

This paper deals with the problem of feature subset selection in classification-oriented datasets with a (very) large number of attributes. In such datasets complex classical wrapper approaches become intractable due to the high number of wrapper evaluations to be carried out. One way to alleviate this problem is to use the so-called filter-wrapper approach or Incremental Wrapper-based Subset Selection (IWSS), which consists of the construction of a ranking among the predictive attributes by using a filter measure, and then a wrapper approach is used by following the rank. In this way the number of wrapper evaluations is linear on the number of predictive attributes. In this paper we present two contributions to the IWSS approach. The first one is related with obtaining more compact subsets, and enables not only the addition of new attributes but also their interchange with some of those already included in the selected subset. Our second contribution, termed early stopping, sets an adaptive threshold on the number of attributes in the ranking to be considered. The advantages of these new approaches are analyzed both theoretically and experimentally. The results over a set of 12 high-dimensional datasets corroborate the success of our proposals.

When a Bayesian network (BN) is modified, for example adding or deleting a node, or changing the probability distributions, we usually will need a total recompilation of the model, despite feeling that a partial (re)compilation could have been enough. Especially when considering dynamic models, in which variables are added and removed very frequently, these recompilations are quite resource consuming. But even further, for the task of building a model, which is in many occasions an iterative process, there is a clear lack of flexibility. When we use the term Incremental Compilation or IC we refer to the possibility of modifying a network and avoiding a complete recompilation to obtain the new (and different) join tree (JT). The main point we intend to study in this work is JT-based inference in Bayesian networks. Apart from undertaking the triangulation problem itself, we have achieved a great improvement for the compilation in BNs. We do not develop a new architecture for BNs inference, but taking some already existing framework JT-based for probability propagation such as Hugin or Shenoy and Shafer, we have designed a method that can be successfully applied to get better performance, as the experimental evaluation will show.

The COR methodology allows the learning of Linguistic Fuzzy Rule-Based Systems by considering cooperation among rules. In order to do this, it uses search techniques, such as Genetic Algorithms, to find the set of candidate rules which will be used to build the final rule base. The performance of COR algorithms, in terms of the quality of the solutions and cost of the search, decreases as the problem size grows. In this paper, several local search algorithms for learning the rule base are tested, as an alternative to population-based methods. Experiments show that, in most cases, the results for the error of prediction improve upon those obtained with Genetic Algorithms. Moreover, this proposal allows a drastic reduction in the computational effort required to find the solutions.

This work studies the problem of premature convergence due to the lack of diversity in Estimation of Distributions Algorithms. This problem is quite important for these kind of algorithms since, even when using very complex probabilistic models, they can not solve certain optimization problems such as some deceptive, hierarchical or multimodal ones.

This paper deals with the problem of wrapper-based feature subset selection in classification oriented datasets with a (very) large number of attributes. In such datasets sophisticated search algorithms like beam search, branch and bound, best first, genetic algorithms, etc., become intractable in the wrapper approach due to the high number of wrapper evaluations to be carried out. One way to alleviate this problem is to use the so-called filter-wrapper approach or Incremental Wrapper-based Subset Selection (IWSS), which consists in the construction of a ranking among the predictive attributes by using a filter measure, and then a wrapper approach is used guided by the rank. In this way the number of wrapper evaluations is linear with the number of predictive attributes. In this paper we present a contribution to the IWSS approach which helps it to obtain more compact subsets, and consists into allow not only the addition of new attributes but also the interchange with some of the already included in the selected subset. The disadvantage of this novelty is that it grows up the worst-case complexity of IWSS up to O(n2), however, as in the case of the well known sequential forward selection (SFS) the actual number of wrapper evaluations is considerably smaller. Empirical tests over 7 (biological) datasets with a large number of attributes demonstrate the success of the proposed approach when comparing with both IWSS and SFS.

AODE (Aggregating One-Dependence Estimators) is considered one of the most interesting representatives of the Bayesian classifiers, taking into account not only the low error rate it provides but also its efficiency. Until now, all the attributes in a dataset have had to be nominal to build an AODE classifier or they have had to be previously discretized. In this paper, we propose two different approaches in order to deal directly with numeric attributes. One of them uses conditional Gaussian networks to model a dataset exclusively with numeric attributes; and the other one keeps the superparent on each model discrete and uses univariate Gaussians to estimate the probabilities for the numeric attributes and multinomial distributions for the categorical ones, it also being able to model hybrid datasets. Both of them obtain competitive results compared to AODE, the latter in particular being a very attractive alternative to AODE in numeric datasets.

One of the key points in Estimation of Distribution Algorithms (EDAs) is the learning of the probabilistic graphical model used to guide the search: the richer the model the more complex the learning task. Dependency networks-based EDAs have been recently introduced. On the contrary of Bayesian networks, dependency networks allow the presence of directed cycles in their structure. In a previous work the authors proposed EDNA, an EDA algorithm in which a multivariate dependency network is used but approximating its structure learning by considering only bivariate statistics. EDNA was compared with other models from the literature with the same computational complexity (e.g., univariate and bivariate models). In this work we propose a modified version of EDNA in which not only the structural learning phase is limited to bivariate statistics, but also the simulation and the parameter learning task. Now, we extend the comparison employing multivariate models based on Bayesian networks (EBNA and hBOA). Our experiments show that the modified EDNA is more accurate than the original one, being its accuracy comparable to EBNA and hBOA, but with the advantage of being faster specially in the more complex cases.

In this paper we deal with the problem of automatically optimizing the gait of a robot for forward walking speed. Each different walking surface and/or the wear and tear of the robots determines the speed of the robot. This means that a specific gait for one surface may not be valid on another surface or even on the same surface some time later. Given a parametrized walk designed for the robot and one specific robot, we approach the problem of searching over the space of gaits for this robot by using an estimation of distribution algorithm and our knowledge of the problem, which allows us to considerably reduce the space of gaits over which the algorithm searches. We have implemented and tested our method using the Sony AIBO ERS-7 robot, significantly improving on our previous gait in a short period of training time.

This paper presents a new approach for the classical Markov localization method for mobile robots by using image quality evaluation. Machine learning techniques have been used to obtain the quality of the images. This quality value is used to select the best information source, between odometry and sensor information. Real experiments in different scenarios of the Robocup standard platform league are also presented.

Recent developments have given birth to H.264/AVC: a video coding standard offering better bandwidth to video quality ratios than previous standards (such as H.263, MPEG-2, MPEG-4, etc.), due to its improved inter- and intraprediction modes at the expense of higher computation complexity. It is expected that H.264/AVC will take over the digital video market, replacing the use of previous standards in most digital video applications. This creates an important need for heterogeneous video transcoding technologies from older standards to H.264. In this paper, we focus our attention on the interframe prediction, the most computationally intensive task involved in the heterogeneous video transcoding process. This paper presents a novel macroblock (MB) mode decision algorithm for interframe prediction based on data mining techniques to be used as part of a very low complexity heterogeneous video transcoder. The proposed approach is based on the hypothesis that MB coding mode decisions in H.264 video have a correlation with the distribution of the motion compensated residual in the decoded video. We use data mining tools to exploit the correlation and derive decision trees to classify the incoming decoded MBs into one of the several coding modes in H.264. The proposed approach reduces the H.264 MB mode computation process into a decision tree lookup with very low complexity. For general validation purposes, we apply our algorithm to two of the most important heterogeneous video transcoders: MPEG-2 to H.264 and H.263 to H.264. Our results show that the our data-mining based transcoding algorithm is able to maintain a good video quality while considerably reducing the computational complexity by 72% on average when applied in MPEG-2 to H.264 transcoders, and by 62% on average when applied in H.263 to H.264 transcoders. Finally, we conduct a comparative study with some of the most prominent fast interprediction methods for H.264 presented in the literature. Our results show that the proposed data mining-based approach achieves the best results for video transcoding applications.

The main feature of Estimation of Distribution Algorithms is the way they evolve by gathering the information about the best elements of each population into a probability distribution. This work studies the application of these algorithms to the learning of weighted linguistic fuzzy-rule-based systems with the wCOR method. For this purpose, we propose the use of two different probabilistic models: One which does not assume any dependence between the rule consequents and their weights, and other whose structure is fixed from these dependences.

Migration of probabilistic models instead of individuals has been shown beneficial in islands-based models of parallel univariate estimation of distribution algorithms (EDAs). One of the key points when using this type of migration is how to incorporate the incoming probabilistic model to the inner one in a given island. When dealing with combinatorial optimization problems and univariate EDAs, models can be combined successfully by using a convex combination of the two probabilistic models (delaOssa et al., 2004). In this paper, we present an alternative way of combining probabilistic models. The new proposal for model combination is based on local search methods, and has its motivation in trying to identify what parts of the incoming model can help to improve the inner one, and to use only these parts to update the incoming model, instead of updating the whole one. Several algorithms are proposed and evaluated by using different test problems. The experiments show that the new proposals perform better than those based on convex combination, especially in the most difficult test problems.

Triangulation of Bayesian networks (BNs) is an NP-hard problem and of great importance for the efficiency of propagation algorithms. Several approaches, most of them basically heuristic, have been proposed to search optimal solutions for this problem. Recently, Olesen and Madsen1 launched the possibility of applying the maximal prime subgraph decomposition (MPSD) to the problem of triangulation. The idea is to retriangulate separately each MPS, so that we can work on smaller graphs. In this article, we exploit this idea by using both greedy heuristic algorithms and stochastic ones [genetic algorithms (GAs)]. From an experimentation performed over 10 real complex networks, we study empirically the usefulness of applying this MPSD-based retriangulation. © 2003 Wiley Periodicals, Inc.

Abductive inference in Bayesian belief networks (BBNs) is intended as the process of generating the K most probable configurations given observed evidence. When we are interested only in a subset of the network's variables, this problem is called partial abductive inference. Both problems are NP-hard, and so exact computation is not always possible. In this paper, a genetic algorithm is used to perform partial abductive inference in BBNs. The main contribution is the introduction of new genetic operators designed specifically for this problem. By using these genetic operators, we try to take advantage of the calculations previously carried out, when a new individual is evaluated. The algorithm is tested using a widely-used Bayesian network and a randomly generated one, and then compared with a previous genetic algorithm based on classical genetic operators. From the experimental results, we conclude that the new genetic operators preserve the accuracy of the previous algorithm and also reduce the number of operations performed during the evaluation of individuals. The performance of the genetic algorithm is thus improved.

Abductive inference in Bayesian belief networks is intended as the process of generating the K most probable configurations given an observed evidence. These configurations are called explanations and in most of the approaches found in the literature, all the explanations have the same number of literals. In this paper we propose some criteria to simplify the explanations in such a way that the resulting configurations are still accounting for the observed facts. Computational methods to perform the simplification task are also presented. Finally the algorithms are experimentally tested using a set of experiments which involves three different Bayesian belief networks.