In feature selection, a measure that captures nonlinear relationships between features and class is the mutual information (MI), which is based on how information in the features reduces the uncertainty in the output. In this paper, we propose a new measure that is related to MI, called neighborhood entropy, and a novel filter method based on its minimization in a greedy procedure. Our algorithm integrates sequential forward selection with approximated nearest-neighbors techniques and locality-sensitive hashing. Experiments show that the classification accuracy is usually higher than that of other state-of-the-art algorithms, with the best results obtained with problems that are highly unbalanced and nonlinearly separable. The order by which the features are selected is also better, leading to a higher accuracy for fewer features. The experimental results indicate that our technique can be employed effectively in offline scenarios when one can dedicate more CPU time to achieve superior results and more robustness to noise and to class imbalance.

This paper proposes a new algorithm based on multiscale stochastic local search with binary representation for training neural networks [binary learning machine (BLM)]. We study the effects of neighborhood evaluation strategies, the effect of the number of bits per weight and that of the maximum weight range used for mapping binary strings to real values. Following this preliminary investigation, we propose a telescopic multiscale version of local search, where the number of bits is increased in an adaptive manner, leading to a faster search and to local minima of better quality. An analysis related to adapting the number of bits in a dynamic way is presented. The control on the number of bits, which happens in a natural manner in the proposed method, is effective to increase the generalization performance. The learning dynamics are discussed and validated on a highly nonlinear artificial problem and on real-world tasks in many application domains; BLM is finally applied to a problem requiring either feedforward or recurrent architectures for feedback control.

In machine learning, an information-theory optimal way to filter the best input features, without reference to any specific machine learning models, consists of maximizing the mutual information between the selected features and the model output, a choice which will minimize the uncertainty in the output to be predicted, given the feature values. Although this criterion is optimal in the context of information theory, a practical difficulty in using it lies in the need to estimate the mutual information from a limited set of input-output examples, in possibly very-high-dimensional input spaces. Estimating probability densities from some data points in these conditions is far from trivial. Starting from the seminal proposals in [1], different approaches focus on approximating the mutual information by considering a limited set of variable dependencies (like dependencies among couples or triplets), or by assuming specific forms for the probability densities (like Gaussian forms). In this paper we study the effect of considering the exact mutual information between selected features and output, without resorting to any approximation (apart from that implicit and unavoidable in estimating it from experimental data). The objectives of this investigation are: to assess how far one can go by adopting the exact mutual information in terms of CPU time and number of features, and to measure what is lost by adopting some popular approximations which consider only relationships among small subsets of features, assumptions about the distribution of feature values (e.g. Gaussian) or upper bounds on the mutual information as proxies to maximize instead of the exact value. The experimental results show a significant performance advantage when the feature sets identified by exact mutual information are used in both binary and multi-valued classification tasks, with longer CPU times.

This paper investigates Stochastic Local Search (SLS) algorithms for training neural networks with threshold activation functions. and proposes a novel technique, called Binary Learning Machine (BLM). BLM acts by changing individual bits in the binary representation of each weight and picking improving moves.

Combining ideas from evolutionary algorithms, decomposition approaches, and Pareto local search, this paper suggests a simple yet efficient memetic algorithm for combinatorial multiobjective optimization problems: memetic algorithm based on decomposition (MOMAD). It decomposes a combinatorial multiobjective problem into a number of single objective optimization problems using an aggregation method. MOMAD evolves three populations: 1) population P(L) for recording the current solution to each subproblem; 2) population P(P) for storing starting solutions for Pareto local search; and 3) an external population P(E) for maintaining all the nondominated solutions found so far during the search. A problem-specific single objective heuristic can be applied to these subproblems to initialize the three populations. At each generation, a Pareto local search method is first applied to search a neighborhood of each solution in P(P) to update P(L) and P(E). Then a single objective local search is applied to each perturbed solution in P(L) for improving P(L) and P(E), and reinitializing P(P). The procedure is repeated until a stopping condition is met. MOMAD provides a generic hybrid multiobjective algorithmic framework in which problem specific knowledge, well developed single objective local search and heuristics and Pareto local search methods can be hybridized. It is a population based iterative method and thus an anytime algorithm. Extensive experiments have been conducted in this paper to study MOMAD and compare it with some other state-of-the-art algorithms on the multiobjective traveling salesman problem and the multiobjective knapsack problem. The experimental results show that our proposed algorithm outperforms or performs similarly to the best so far heuristics on these two problems.

This paper introduces the active learning of Pareto fronts (ALP) algorithm, a novel approach to recover the Pareto front of a multiobjective optimization problem. ALP casts the identification of the Pareto front into a supervised machine learning task. This approach enables an analytical model of the Pareto front to be built. The computational effort in generating the supervised information is reduced by an active learning strategy. In particular, the model is learned from a set of informative training objective vectors. The training objective vectors are approximated Pareto-optimal vectors obtained by solving different scalarized problem instances. The experimental results show that ALP achieves an accurate Pareto front approximation with a lower computational effort than state-of-the-art estimation of distribution algorithms and widely known genetic techniques.

Given a gene expression data matrix where each cell is the expression level of a gene under a certain condition, biclustering is the problem of searching for a subset of genes that co regulate and co express only under a subset of conditions. As some genes can belong to different functional categories, searching for non-redundant overlapping biclusters is an important problem in biclustering. However, most recent algorithms can only either produce disjoint biclusters or redundant biclusters with significant overlap. In other words, these algorithms do not allow users to specify the maximum overlap between the biclusters. In this paper, we propose a novel algorithm which can generate K overlapping biclusters where the maximum overlap between them is below a predefined threshold. Unlike the other approaches which often generate all biclusters at once, our algorithm produces the biclusters sequentially, where each newly generated bicluster is guaranteed to be different from the previous ones but can still overlap with them. The experiments on real datasets confirm that different meaningful overlapping biclusters are successfully discovered. Besides, under the same constraints, our algorithm returns much larger and higher-quality biclusters compared to those of the other state-of-the art algorithms.

Almost by definition, optimization is a source of a tremendous power for automatically improving processes, decisions, products and services. But its potential is still largely unexploited in most real-world contexts. One of the main reasons blocking its widespread adoption is that standard optimization assumes the existence of a function f(x) to be minimized, while in most real-world business contexts this function does not exist or is extremely difficult and costly to build by hand. Machine learning (ML) comes to the rescue: the function (the model) can be built by machine learning starting from abundant data. By Learning and Intelligent Optimization (LION) we mean this combination of learning from data and optimization which can be applied to complex, dynamic, stochastic contexts. This combination dramatically increases the automation level and puts more power directly in the hands of decision makers without resorting to intermediate layers of data scientists (LION has a huge potential for a self-service usage). Reaching this goal is a huge challenge and it will require research at the boundary between two areas, machine learning and optimization, which have been traditionally separated.

Combining ant colony optimization (ACO) and the multiobjective evolutionary algorithm (EA) based on decomposition (MOEA/D), this paper proposes a multiobjective EA, i.e., MOEA/D-ACO. Following other MOEA/D-like algorithms, MOEA/D-ACO decomposes a multiobjective optimization problem into a number of single-objective optimization problems. Each ant (i.e., agent) is responsible for solving one subproblem. All the ants are divided into a few groups, and each ant has several neighboring ants. An ant group maintains a pheromone matrix, and an individual ant has a heuristic information matrix. During the search, each ant also records the best solution found so far for its subproblem. To construct a new solution, an ant combines information from its group's pheromone matrix, its own heuristic information matrix, and its current solution. An ant checks the new solutions constructed by itself and its neighbors, and updates its current solution if it has found a better one in terms of its own objective. Extensive experiments have been conducted in this paper to study and compare MOEA/D-ACO with other algorithms on two sets of test problems. On the multiobjective 0-1 knapsack problem,MOEA/D-ACO outperforms the MOEA/D with conventional genetic operators and local search on all the nine test instances. We also demonstrate that the heuristic information matrices in MOEA/D-ACO are crucial to the good performance of MOEA/D-ACO for the knapsack problem. On the biobjective traveling salesman problem, MOEA/D-ACO performs much better than the BicriterionAnt on all the 12 test instances. We also evaluate the effects of grouping, neighborhood, and the location information of current solutions on the performance of MOEA/D-ACO. The work in this paper shows that reactive search optimization scheme, i.e., the "learning while optimizing" principle, is effective in improving multiobjective optimization algorithms.

Supervised alternative clusterings is the problem of finding a set of clusterings which are of high quality and different from a given negative clustering. The task is therefore a clear multi-objective optimization problem. Optimizing two conflicting objectives requires dealing with trade-offs. Most approaches in the literature optimize these objectives sequentially or indirectly, resulting in solutions which are dominated. We develop a multi-objective algorithm, called COGNAC, able to optimize the objectives directly and simultaneously and producing solutions approximating the Pareto front. COGNAC performs the recombination operator at the cluster level instead of the object level as in traditional genetic algorithms. It can accept arbitrary clustering quality and dissimilarity objectives and provide solutions dominating those of other state-of-the-art algorithms. COGNAC can also be used to generate a sequence of alternative clusterings, each of which is guaranteed to be different from all previous ones.

An evolutionary algorithm with guided mutation (EA/G) has been proposed recently for solving the maximum clique problem. In the framework of estimation-of-distribution algorithms, guided mutation uses a model distribution to generate offspring by combining the local information of solutions found so far with global statistical information. Each individual is then subjected to a Marchiori's repair heuristic, based on randomized extraction and greedy expansion, to ensure that it represents a legal clique. A novel reactive and evolutionary algorithm (R-EVO) proposed in this paper starts from the same evolutionary framework but considers more complex individuals, which modify tentative solutions by local search with memory, according to the reactive search optimization (RSO) principles. In particular, the estimated distribution is used to periodically initialize the state of each individual based on the previous statistical knowledge extracted from the population. We demonstrate that the combination of the estimation-of-distribution concept with RSO produces significantly better results than EA/G for many test instances and it is remarkably robust with respect to the setting of the algorithm parameters. R-EVO adopts a drastically simplified low-knowledge version of reactive local search (RLS), with a simple internal diversification mechanism based on tabu-search, with a prohibition parameter proportional to the estimated best clique size. R-EVO is competitive with the more complex full-knowledge RLS-EVO that adopts the original RLS algorithm. For most of the benchmark instances, the hybrid scheme version produces significantly better results than EA/G for comparable or a smaller central processing unit time.

The centrality of the decision maker (DM) is widely recognized in the multiple criteria decision-making community. This translates into emphasis on seamless human-computer interaction, and adaptation of the solution technique to the knowledge which is progressively acquired from the DM. This paper adopts the methodology of reactive search optimization (RSO) for evolutionary interactive multiobjective optimization. RSO follows to the paradigm of “learning while optimizing,” through the use of online machine learning techniques as an integral part of a self-tuning optimization scheme. User judgments of couples of solutions are used to build robust incremental models of the user utility function, with the objective to reduce the cognitive burden required from the DM to identify a satisficing solution. The technique of support vector ranking is used together with a k-fold cross-validation procedure to select the best kernel for the problem at hand, during the utility function training procedure. Experimental results are presented for a series of benchmark problems.

This paper investigates Reinforcement Learning (RL) applied to online parameter tuning in Stochastic Local Search (SLS) methods. In particular, a novel application of RL is proposed in the Reactive Tabu Search (RTS) scheme, where the appropriate amount of diversification in prohibition-based local search is adapted in a fast online manner to the characteristics of a task and of the local configuration. The experimental tests demonstrate promising results on Maximum Satisfiability (MAX-SAT) instances when compared with state-of-the-art SLS SAT solvers, such us AdaptNovelty, rSAPS and gNovelty.

Vehicular networks create a new communication paradigm that enables to exploit the movement of cars to disseminate content. If network coding is used, vehicles have much more flexibility in content sharing and the system stability and scalability are promoted also in presence of mobility. Along this line, we propose an efficient mechanism to provide secrecy of the information. Traditional approaches based on encryption decrease the cooperation willingness of intermediate nodes, which have no expectation of recovering the file. Our scheme is based on obfuscation by processing and polluting the original file so that only the intended recipients, informed of corrupted blocks, can recover the information timely. We present several alternatives to efficiently provide weak secrecy and to foster cooperation. We simulate the file distribution in a vehicular network and show that the proposed scheme enhances content distribution in term of downloading speed and it is much more efficient than the ones that use encryption.

Most current anomaly intrusion detection systems (IDSs) detect computer network behavior as normal or abnormal but cannot identify the type of attacks. Moreover, most current intrusion detection methods cannot process large amounts of audit data for real-time operation. In this paper, we propose a novel method for intrusion identification in computer networks based on principal component analysis (PCA). Each network connection is transformed into an input data vector. PCA is employed to reduce the dimensionality of the data vectors and identification is handled in a low dimensional space with high efficiency and low use of system resources. The normal behavior is profiled based on normal data for anomaly detection and models of each type of attack are built based on attack data for intrusion identification. The distance between a vector and its reconstruction onto those reduced subspaces representing the different types of attacks and normal activities is used for identification. The method is tested with network data from MIT Lincoln labs for the 1998 DARPA intrusion detection evaluation program and testing results show that the model is promising in terms of identification accuracy and computational efficiency for real-time intrusion identification.

Leveraging social networks in computer systems can be effective in dealing with a number of trust and security issues. Spam is one such issue where the "wisdom of crowds" can be harnessed by mining the collective knowledge of ordinary individuals. In this paper, we present a mechanism through which members of a virtual community can exchange information to combat spam. Previous attempts at collaborative spam filtering have concentrated on digest-based indexing techniques to share digests or fingerprints of emails that are known to be spam. We take a different approach and allow users to share their spam filters instead, thus dramatically reducing the amount of traffic generated in the network. The resultant diversity in the filters and cooperation in a community allows it to respond to spam in an autonomic fashion. As a test case for exchanging filters we use the popular SpamAssassin spam filtering software and show that exchanging spam filters provides an alternative method to improve spam filtering performance.

This paper presents a gregarious particle swarm optimization algorithm (G-PSO) in which the particles explore the search space by aggressively scouting the local minima with the help of only social knowledge. To avoid premature convergence of the swarm, the particles are re-initialized with a random velocity when stuck at a local minimum. Furthermore, G-PSO adopts a "reactive" determination of the step size, based on feedback from the last iterations. This is in contrast to the basic particle swarm algorithm, in which the particles explore the search space by using both the individual "cognitive" component and the "social" knowledge and no feedback is used for the self-tuning of algorithm parameters. The novel scheme presented, besides generally improving the average optimal values found, reduces the computation effort.

In order for autonomic systems to function, the individual components must co-operate and not indulge in malicious behavior. However, it is almost certain that autonomous systems in. Next generation networks will inadvertently include less than trustworthy components. Identifying such entities is critical to the smooth and effective functioning. We present new experiments conducted with the ROCQ scheme, a reputation-based trust management system that computes the trustworthiness of peers on the basis of transaction-based feedback. The ROCQ model combines four parameters: reputation (R) or a peer's global trust rating, opinion (O) formed by a peer's first-hand interactions, credibility (C) of a reporting peer and quality (Q) or the confidence a reporting peer puts on the feedback it provides. In this paper, we demonstrate that ROCQ is robust against churn and also examine the effect of credibility and quality on the performance of the scheme.

In this work we present an approach for maintaining the topology of a Bluetooth scatternet at an optimal configuration despite the dynamic behavior of the nodes in time. Our goal is to keep the ratio of the average scatternet throughput and node power consumption as high as possible while nodes unpredictably change their communication peers and migrate across the network. The approach consists in keeping the total number of hops between communicating nodes relatively low by periodically reconfiguring the scatternet topology based on the actual traffic pattern of the network

In this paper, we propose a swarm intelligence strategy for constructing a mobile backbone multicasting network which leads to improved scalability and connectivity compared to conventional flat networks. The strategy combines a simple clustering technique and on demand multicast protocol (ODMRP). Also we show benefits of the mobile backbone network through a simulation study.

IP over WDM networks are a promising candidate for the next generation optical Internet networks. A new traffic-engineering (TE) scheme is proposed in this paper with the objective to route subwavelength connection requests with QoS constraints. In particular, we consider the routing of high-priority connections characterized by stringent requirements in term of delay and packet-loss ratio, by translating them into constraints at the physical layer. Furthermore, in order to provide efficient service differentiation, the impact of a suboptimal preemption algorithm is analyzed through extensive simulation experiments considering both the blocking probability and the network disruption, while comparing it with an optimal mechanism proposed in literature.

Mobility, and the fact that nodes may change their communication peers in time, generates a permanently changing traffic flows in the Bluetooth scatternet. Thus, forming an optimal scatternet for a given traffic pattern may not be enough, rather a scatternet that best supports the traffic flows as they vary in time is required. In this article we propose an algorithm suite that enables us to modify the nodes' links and roles. Periodically executing these algorithms helps in maintaining the distance (measured in hops weighted with the corresponding traffic intensity) between every source-destination pair at a minimum. This allows for a higher network throughput, lower packet delivery delay, nodes' energy consumption, and reduced communication overhead.

In this paper we develop a load balancing scheme for networks based on the MPLS framework. The proposed algorithm (DYLBA - dynamic load balancing algorithm) implements a local search technique where the basic move is the modification of the route for a single label switched path. Experiments under a dynamic traffic scenario show a reduced rejection probability especially with long-lived connection requests, thus providing a better use of resources when compared to existing constraint-based routing schemes for traffic engineering in MPLS networks.

Mobile computing adds a mostly unexplored dimension to data mining: user's position is a relevant piece of information, and recommendation systems, selecting and ranking links of interest to the user, have the opportunity to take location into account. In this paper a mobility-aware recommendation system that considers the location of the user to filter recommended links is proposed. To avoid the potential problems and costs of insertion by hand, a new middleware layer, the location broker, maintains a historic database of locations and corresponding links used in the past and develops models relating resources to their spatial usage pattern. These models are used to calculate a preference metric when the current user is asking for resources of interest. Mobility scenarios are described and analyzed in terms of possible user requirements. The features of the PILGRIM mobile recommendation system are outlined together with a preliminary experimental evaluation of different metrics.

New heuristic algorithms are proposed for the Graph Partitioning problem. A greedy construction scheme with an appropriate tie-breaking rule (MIN-MAX-GREEDY) produces initial assignments in a very fast time. For some classes of graphs, independent repetitions of MIN-MAX-GREEDY are sufficient to reproduce solutions found by more complex techniques. When the method is not competitive, the initial assignments are used as starting points for a prohibition-based scheme, where the prohibition is chosen in a randomized and reactive way, with a bias towards more successful choices in the previous part of the run. The relationship between prohibition-based diversification (Tabu Search) and the variable-depth Kernighan-Lin algorithm is discussed, Detailed experimental results are presented on benchmark suites used in the previous literature, consisting of graphs derived from parametric models (random graphs, geometric graphs, etc.) and of "real-world" graphs of large size. On the first series of graphs, a better performance for equivalent or smaller computing times is obtained, while, on the large "real-world" instances, significantly better results than those of multilevel algorithms are obtained, but for a much larger computational effort.

In this paper the task of training subsymbolic systems is considered as a combinatorial optimization problem and solved with the heuristic scheme of the reactive tabu search (RTS). An iterative optimization process based on a "modified local search" component is complemented with a meta-strategy to realize a discrete dynamical system that discourages limit cycles and the confinement of the search trajectory in a limited portion of the search space. The possible cycles are discouraged by prohibiting (i.e., making tabu) the execution of moves that reverse the ones applied in the most recent part of the search. The prohibition period is adapted in an automated way. The confinement is avoided and a proper exploration is obtained by activating a diversification strategy when too many configurations are repeated excessively often. The RTS method is applicable to nondifferentiable functions, is robust with respect to the random initialization, and effective in continuing the search after local minima. Three tests of the technique on feedforward and feedback systems are presented.

We propose an algorithm for combinatorial optimization where an explicit check for the repetition of configurations is added to the basic scheme of Tabu search. In our Tabu scheme the appropriate size of the list is learned in an automated way by reacting to the occurrence of cycles. In addition, if the search appears to be repeating an excessive number of solutions excessively often, then the search is diversified by making a number of random moves proportional to a moving average of the cycle length. The reactive scheme is compared to a “strict” Tabu scheme that forbids the repetition of configurations and to schemes with a fixed or randomly varying list size. From the implementation point of view we show that the Hashing or Digital Tree techniques can be used in order to search for repetitions in a time that is approximately constant. We present the results obtained for a series of computational tests on a benchmark function, on the 0-1 Knapsack Problem, and on the Quadratic Assignment Problem. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

This paper investigates the application of the mutual information criterion to evaluate a set of candidate features and to select an informative subset to be used as input data for a neural network classifier. Because the mutual information measures arbitrary dependencies between random variables, it is suitable for assessing the "information content" of features in complex classification tasks, where methods bases on linear relations (like the correlation) are prone to mistakes. The fact that the mutual information is independent of the coordinates chosen permits a robust estimation. Nonetheless, the use of the mutual information for tasks characterized by high input dimensionality requires suitable approximations because of the prohibitive demands on computation and samples. An algorithm is proposed that is based on a "greedy" selection of the features and that takes both the mutual information with respect to the output class and with respect to the already-selected features into account. Finally the results of a series of experiments are discussed.

On-line first-order backpropagation is sufficiently fast and effective for many large-scale classification problems but for very high precision mappings, batch processing may be the method of choice. This paper reviews first- and second-order optimization methods for learning in feedforward neural networks. The viewpoint is that of optimization: many methods can be cast in the language of optimization techniques, allowing the transfer to neural nets of detailed results about computational complexity and safety procedures to ensure convergence and to avoid numerical problems. The review is not intended to deliver detailed prescriptions for the most appropriate methods in specific applications, but to illustrate the main characteristics of the different methods and their mutual relations.

Abstract This paper investigates the use of large grain size multi‐computers for solving low‐ and intermediate‐level computer vision problems. The realization of a general multi‐resolution framework requiring a two‐dimensional grid of communicating processors is analysed, and the resulting speed‐up and total solution time as a function of software and hardware parameters is presented. The scheme is then specialized for two significant problems: surface reconstruction and optical flow. While the first can be solved with the standard full multigrid approach, the second requires an adaptive grid determined by a local decision: the appropriate resolution for different parts of the image is tuned in order to minimize the error in the coefficients of the differential equations.