Multidimensional Particle Swarm Optimization for Machine Learning and Pattern Recognition

It is an undeniable fact that all of us are optimizers as we all make decisions for the sole purpose of maximizing our quality of life, productivity in time, as well as our welfare in some way or another. Since this is an ongoing struggle for creating the best possible among many inferior designs, optimization was, is, and will always be the core requirement of human life and this fact yields the development of a massive number of techniques in this area, starting from the early ages of civilization until now. The efforts and lives behind this aim dedicated by many brilliant philosophers, mathematicians, scientists, and engineers have brought the high level of civilization we enjoy today. Therefore, we find it imperative to get to know first those major optimization techniques along with the philosophy and long history behind them before going into the details of the method detailed in this book. This chapter begins with a detailed history of optimization, covering the major achievements in time along with the people behind them. The rest of the chapter then draws the focus on major optimization techniques, while briefly explaining the mathematical theory and foundations over some sample problems.

The behavior of a single organism in a swarm is often insignificant, but their collective and social behavior is of paramount importance. The particle swarm optimization (PSO) was introduced by Kennedy and Eberhart [1] in 1995 as a population-based stochastic search and optimization process. It is originated from the computer simulation of the individuals (particles or living organisms) in a bird flock or fish school [2], which basically show a natural behavior when they search for some target (e.g., food). The goal is, therefore, to converge to the global optima of some multidimensional and possibly nonlinear function or system. Henceforth, PSO follows the same path of other evolutionary algorithms (EAs), [3] such as genetic algorithm (GA) [4], genetic programming (GP) [5], evolution strategies (ES) [6], and evolutionary programming (EP) [7]. Recall that the common point of all is that EAs are in population-based nature and they can avoid being trapped in a local optimum. Thus they can find the optimum solutions; however, this is never guaranteed.

Imagine now that each PSO particle can also change its dimension, which means that they have the ability to jump to another (solution space) dimension as they see fit. In that dimension they simply do regular PSO moves but in any iteration they can still jump to any other dimension. In this chapter we shall show how the design of PSO particles is extended into Multi-dimensional PSO (MD PSO) particles so as to perform interdimensional jumps without altering or breaking the natural PSO concept.

As a natural extension of PSO, MD PSO may also have a serious drawback of premature convergence to a local optimum, due to the direct link of the information flow between particles and gbest, which “guides” the rest of the swarm resulting in possible loss of diversity. Hence, this phenomenon increases the probability of being trapped in local optima [1] and it is the main cause of the premature convergence problem especially when the search space is of high dimensions [2] and the problem to be optimized is multimodal [1]. Another reason for the premature convergence is that particles are flown through a single point which is (randomly) determined by gbest and pbest positions and this point is not even guaranteed to be a local optimum [3]. Various modifications and PSO variants have been proposed in order to address this problem such as [1, 3‐28]. As briefly discussed in Sect.​ 3.​3, such methods usually try to improve the diversity among the particles and the search mechanism either by changing the update equations toward a more diversified version, by adding more randomization to the system (to particle velocities, positions, etc.), or simply resetting some or all particles randomly when some conditions are met. On the one hand, most of these variants require additional parameters to accomplish the task and thus making the algorithms even more parameter dependent. On the other hand, the main problem is in fact the inability of the algorithm to use available diversity in one or more positional components of a particle. Note that one or more components of any particle may already be in a close vicinity of the global optimum. This potential is then wasted with the (velocity) update in the next iteration, which changes all the components at once. In this chapter, we shall address this drawback of global convergence by developing two efficient techniques. The first one, the so-called Fractional Global Best Formation (FGBF), collects all such promising (or simply the best) components from each particle and fractionally creates an artificial global best (GB) candidate, the aGB, which will be the swarm’s global best (GB) particle if it is better than the previous GB and the just-computed gbest. Note that whenever a better gbest particle or aGB particle emerges, it will replace the current GB particle. Without any additional change, we shall show that FGBF can avoid local optima and thus yield the optimum (or near optimum) solution efficiently even in high dimensional search spaces. Unfortunately FGBF is not an entirely generic technique, which should be specifically adapted to the problem at hand (we shall return to this issue later). In order to address this drawback efficiently, we shall further present two generic approaches, one of which moves gbest efficiently or simply put, “guides” it with respect to the function (or error surface) it resides on. The idea behind this is quite simple: since the velocity update equation of gbest is quite poor, we shall replace it with a simple yet powerful stochastic search technique to guide it instead. We shall henceforth show that due to the stochastic nature of the search technique, the likelihood of getting trapped into a local optimum can significantly be decreased.

Clustering in the most basic terms, is the collection of patterns, which are usually represented as vectors or points in a multi-dimensional data space, into groups (clusters) based on similarity or proximity. Such an organization is useful in pattern analysis, classification, machine learning, information retrieval, spatial segmentation, and many other application domains. Cluster validity analysis is the assessment of the clustering method’s output using a specific criterion for optimality, i.e., the so-called clustering validity index (CVI). Therefore, the optimality of any clustering method can only be assessed with respect to the CVI, which is defined over a specific data (feature) representation with a proper distance (similarity) metric. What characterizes a clustering method further depends on its scalability over the dimensions of the data and solution spaces, i.e., whether or not it can perform well enough on a large dataset; say with a million patterns and having large number of clusters (e.g., ≫10). In the former case, the complexity of the method may raise an infeasibility problem and the latter case shows the degree of its immunity against the well-known phenomenon, “the curse of dimensionality”. Even humans, who perform quite well in 2D and perhaps in 3D, have difficulties of interpreting data in higher dimensions. Nevertheless, most real problems involve clustering in high dimensions, in that; the data distribution can hardly be modeled by some ideal structures such as hyperspheres.

Artificial neural networks (ANNs) are known as “universal approximators” and “computational models” with particular characteristics such as the ability to learn or adapt, to organize or to generalize data. Because of their automatic (self-adaptive) process and capability to learn complex, nonlinear surfaces, ANN classifiers have become a popular choice for many machine intelligence and pattern recognition applications. In this chapter, we shall present a technique for automatic design of Artificial Neural Networks (ANNs) by evolving to the optimal network configuration(s) within an architecture space (AS), which is a family of ANNs. The AS can be formed according to the problem in hand encapsulating indefinite number of network configurations. The evolutionary search technique is entirely based on multidimensional Particle Swarm Optimization (MD PSO). With a proper encoding of the network configurations and parameters into particles, MD PSO can then seek positional optimum in the error space and dimensional optimum in the AS. The optimum dimension converged at the end of a MD PSO process corresponds to a unique ANN configuration where the network parameters (connections, weights, and biases) can then be resolved from the positional optimum reached on that dimension. In addition to this, the proposed technique generates a ranked list of network configurations, from the best to the worst. This is indeed a crucial piece of information, indicating what potential configurations can be alternatives to the best one, and which configurations should not be used at all for a particular problem. In this chapter, the architecture space is defined over feed-forward, fully connected ANNs so as to use the conventional techniques such as back-propagation and some other evolutionary methods in this field. We shall then apply the evolutionary ANNs over the most challenging synthetic problems to test its optimality on evolving networks and over the benchmark problems to test its generalization capability as well as to make comparative evaluations with the several competing techniques. We shall demonstrate that MD PSO evolves to optimum or near-optimum networks in general and has a superior generalization capability. In addition, MD PSO naturally favors a low-dimension solution when it exhibits a competitive performance with a high dimension counterpart and such a native tendency eventually steers the evolution process toward the compact network configurations in the architecture space instead of more complex ones, as long as optimality prevails.

Each individual heartbeat in the cardiac cycle of the recorded electrocardiogram (ECG) waveform shows the time evolution of the heart’s electrical activity, which is made of distinct electrical depolarization–repolarization patterns of the heart. Any disorder of heart rate or rhythm, or change in the morphological pattern is an indication of an arrhythmia, which could be detected by analysis of the recorded ECG waveform. Real-time automated ECG analysis in clinical settings is of great assistance to clinicians in detecting cardiac arrhythmias, which often arise as a consequence of a cardiac disease and may be life-threatening and require immediate therapy.

Multimedia content features (also called descriptors) play a central role in many computer vision and image processing applications. Features are various types of information extracted from the content and represent some of its characteristics or signatures. However, especially these low-level features, which can be extracted automatically usually lack the discrimination power needed for accurate content representation especially in the case of a large and varied media content data reserve. Therefore, a major objective in this chapter is to synthesize better discriminative features using an evolutionary feature synthesis (EFS) framework, which aims to enhance the discrimination power by synthesizing media content descriptors. The chapter presents an EFS framework, which applies a set of linear and nonlinear operators in an optimal way over the given features in order to synthesize highly discriminative features in an optimal dimensionality. The optimality therein is sought by the multidimensional particle swarm optimization (MD PSO) along with the fractional global best formation (FGBF) presented in Chaps.​ 4 and 5, respectively. We shall further demonstrate that the features synthesized by the EFS framework that is applied over only a minority of the original feature vectors exhibit a major increase in the discrimination power between different classes and a significant content-based image retrieval (CBIR) performance improvement can thus be achieved.