Machine learning is a research field involving the study of theories and technologies to adapt a system model using a training dataset, so that the learned model will be able to generalize and provide a correct classification or useful guidance even when the inputs to the system are previously unknown. Machine learning builds its foundation on linear algebra, statistical learning theory, pattern recognition, and artificial intelligence. The development of practical machine learning tools requires multi-disciplinary knowledge including matrix theory, signal processing, regression analysis, discrete mathematics, and optimization theory. It covers a broad spectrum of application domains in multimedia processing, network optimization, biomedical analysis, etc.

Since the publication of Vapnik's book entitled The Nature of Statistical Learning Theory (Springer-Verlag, 1995) and the introduction of the celebrated support vector machine (SVM), research on kernel-based machine learning has flourished steadily for nearly two decades. The enormous amount of research findings on unsupervised and supervised learning models, both theory and applications, should already warrant a new textbook, even without considering the fact that this fundamental field will undoubtedly continue to grow for a good while.

The book first establishes algebraic and statistical foundations for kernel-based learning methods. It then systematically develops kernel-based learning models both for unsupervised and for supervised scenarios.

• The secret of success of a machine learning system lies in finding an effective representation for the objects of interest. In a basic representation, an object is represented as a feature vector in a finite-dimensional vector space.

Chapter 1 provides an overview of the broad spectrum of applications and problem formulations for kernel-based unsupervised and supervised learning methods. The dimension of the original vector space, along with its Euclidean inner product, often proves to be highly inadequate for complex data analysis. In order to provide more effective similarity metrics of any pairs of objects, in the kernel approach one replaces the traditional Euclidean inner product by more sophisticated and kernel-induced inner products associated with the corresponding kernel-induced vector spaces. Among the most useful such spaces are the (primal) intrinsic and (dual) empirical spaces.

The interplay between the formulations of learning models in the primal/dual spaces plays a key role both in the theoretical analysis and in the practical implementation of kernel methods. Chapter 1 shows that a vital condition for kernelization of a learning model is the LSP condition, which is often verifiable via Theorem 1.1. In fact, the optimization formulation prescribed in Theorem 1.1 covers most, if not all, of the ℓ2-based learning models treated in this book – both unsupervised and supervised.

Chapter 2 starts with the vital Theorem 2.1, which states that Mercer's condition of the kernel function used will be imperative for the existence of the kernel-induced vector spaces. For vectorial data analysis, in the first stage, the original vector space can be mapped to the kernel-induced intrinsic vector space. Here, every individual object is represented by a (possibly high-dimensional) feature vector in intrinsic space.

Introduction

The various types of raw data encountered in real-world applications fall into two main categories, vectorial and nonvectorial types. For vectorial data, the Euclidean distance or inner product is often used as the similarity measure of the training vectors: (xi, i = 1,…, N}. This leads to the conventional K-means or SOM clustering methods. This chapter extends these methods to kernel-based cluster discovery and then to nonvectorial clustering applications, such as sequence analysis (e.g. protein sequences and signal motifs) and graph partition problems (e.g. molecular interactions, social networks). The fundamental unsupervised learning theory will be systematically extended to nonvectorial data analysis.

This chapter will cover the following kernel-based unsupervised learning models for cluster discovery.

• Section 6.2 explores kernel K-means in intrinsic space. In this basic kernel K-means learning model, the original vectors are first mapped to the basis functions for the intrinsic vector space H, and the mapped vectors will then be partitioned into clusters by the conventional K-means. Because the intrinsic-space approach will not be implementable for some vectorial and all nonvectorial applications, alternative representations need to be pursued. According to Theorem 1.1, the LSP condition holds for K-means. According to Eq. (1.20), this means that the problem formulation may be fully and uniquely characterized by the kernel matrix K associated with the training vector, i.e. without a specific vector space being explicitly defined. In short, the original vector-based clustering criterion is converted to a vector-free clustering criterion.

There are two main learning strategies, namely inductive learning and transductive learning. These strategies are differentiated by their different ways of treating the (distribution of) testing data. The former adopts off-line learning models, see Figure B.1(a), but the latter usually adopts online learning models, see Figure B.1(b).

• Inductive learning strategies. The decision rule, trained under an inductive setting, must cover all the possible data in the entire vector space. More explicitly, the discriminant function f(w, x) can be trained by inductive learning. This approach can effectively distill the information inherent in the training dataset off-line into a simple set of decision parameters w, thus enjoying the advantage of having a low classification complexity. As shown in Figure B.1(a), this approach contains two stages: (1) an off-line learning phase and (2) an on-field prediction phase. During the learning phase, the training dataset is used to learn the decision parameter w, which dictates the decision boundary: f(w, x) = 0. In the prediction phase, no more learning is required, so the decision making can be made on-the-fly with minimum latency.

• Transductive learning strategies. In this case, the learner may explicitly make use of the structure and/or location of the putative test dataset in the decision process [281]. Hence, the discriminant function can be tailored to the specific test sample after it has been made known, presumably improving the prediction accuracy.

Linear prediction and system identification has become a well-established field in information sciences. On the other hand, kernel methods have acquired their popularity only during the past two decades, so they have a relatively short history. It is vital to establish a theoretical foundation linking kernel methods and the rich theory in estimation, prediction, and system identfication. This part contains two chapters addressing this important issue. Chapter 14 focuses on statistical analysis employing knowledge of the (joint) density functions of all the input and output variables and their respective noises. Chapter 15 focuses on estimation, prediction, and system identification using observed samples and prior knowledge of the irst- and second-order statistics of the system parameters.

In Chapter 14, the classical formulation for (linear) ridge regression will be extended to (nonlinear) kernel ridge regression (KRR). Using the notion of orthogonal polynomials (Theorem 14.1), closed-form results for the error analysis can be derived for KRR, see Theorem 14.2. The regression analysis can be further generalized to the errors-in-variables models, where the measurements of the input variable are no longer perfect. This leads to the development of perturbation-regulated regressors (PRRs), regarding which two major theoretical fronts will be explored:

• Under the Gaussian distribution assumption, the analysis on PRR benefits greatly from the exact knowledge of the joint statistical property of the ideal and perturbed input variables. The property of conventional orthogonal polynomials (Theorem 14.1) is extended to harness the cross-orthogonality between the original and perturbed input variables.

Appendix A reviews useful validation techniques and test schemes for learning models.

Appendix B covers supervised classifiers without an explicit learning process and the popular and fundamental Bayes classifiers.

Introduction

Regression analysis has been a major theoretical pillar for supervised machine learning since it is applicable to a broad range of identification, prediction and classification problems. There are two major approaches to the design of robust regressors. The first category involves a variety of regularization techniques whose principle lies in incorporating both the error and the penalty terms into the cost function. It is represented by the ridge regressor. The second category is based on the premise that the robustness of the regressor could be enhanced by accounting for potential measurement errors in the learning phase. These techniques are known as errors-in-variables models in statistics and are relatively new to the machine learning community. In our discussion, such errors in variables are viewed as additive input perturbation.

This chapter aims at enhancing the robustness of estimators by incorporating input perturbation into the conventional regression analysis. It develops a kernel perturbation-regulated regressor (PRR) that is based on the errors-in-variables models. The PRR offers a strong smoothing capability that is critical to the robustness of regression or classification results. For Gaussian cases, the notion of orthogonal polynomials is instrumental to optimal estimation and its error analysis. More exactly, the regressor may be expressed as a linear combination of many simple Hermite regressors, each focusing on one (and only one) orthogonal polynomial.

This chapter will cover the fundamental theory of linear regression and regularization analysis. The analysis leads to a closed-form error formula that is critical for order-error tradeoff.

Introduction

In Chapter 8, it is shown that the kernel ridge regressor (KRR) offers a unified treatment for over-determined and under-determined systems. Another way of achieving unification of these two linear systems approaches is by means of the support vector machine (SVM) learning model proposed by Vapnik [41, 280, 281].

• Just like FDA, the objective of SVM aims at the separation of two classes. FDA is focused on the separation of the positive and negative centroids with the total data distribution taken into account. In contrast, SVM aims at the separation of only the so-called support vectors, i.e. only those which are deemed critical for class separation.

• Just like ridge regression, the objective of the SVM classifier also involves minimization of the two-norm of the decision vector.

The key component in SVM learning is to identify a set of representative training vectors deemed to be most useful for shaping the (linear or nonlinear) decision boundary. These training vectors are called “support vectors.” The rest of the training vectors are called non-support vectors. Note that only support vectors can directly take part in the characterization of the decision boundary of the SVM.

SVM has successfully been applied to an enormously broad spectrum of application domains, including signal processing and classification, image retrieval, multimedia, fault detection, communication, computer vision, security/authentication, time-series prediction, biomedical prediction, and bioinformatics.

Introduction

Two primary techniques for dimension-reducing feature extraction are subspace projection and feature selection. This chapter will explore the key subspace projection approaches, i.e. PCA and KPCA.

Why dimension reduction?

In many real-world applications, the feature dimension (i.e. the number of features or attributes in an input vector) could easily be as high as tens of thousands. Such an extreme dimensionality could be very detrimental to data analysis and processing.

This part contains two chapters concerning reduction of the dimension of the feature space, which plays a vital role in improving learning efficiency as well as prediction performance.

Chapter 3 covers the most prominent subspace projection approach, namely the classical principal component analysis (PCA), cf. Algorithm 3.1. Theorems 3.1 and 3.2 establish the optimality of PCA for both the minimum reconstruction error and maximum entropy criteria. The optimal error and entropy attainable by PCA are given in closed form. Algorithms 3.2, 3.3, and 3.4 describe the numerical procedures for the computation of PCA via the data matrix, scatter matrix, and kernel matrix, respectively.

Given a finite training dataset, the PCA learning model meets the LSP condition, thus the conventional PCA model can be kernelized. When a nonlinear kernel is adopted, it further extends to the kernel-PCA (KPCA) learning model. The KPCA algorithms can be presented in intrinsic space or empirical space (see Algorithms 3.5 and 3.6). For several real-life datasets, visualization via KPCA shows more visible data separability than that via PCA. Moreover, KPCA is closely related to the kernel-induced spectral space, which proves instrumental for error analysis in unsupervised and supervised applications.

Chapter 4 explores various aspects of feature selection methods for supervised and unsupervised learning scenarios. It presents several filtering-based and wrapper-based methods for feature selection, a popular method for dimension reduction.

AND SO WE HAVE come to the end of our journey through the ‘making sense of data’ landscape. We have seen how machine learning can build models from features for solving tasks involving data. We have seen how models can be predictive or descriptive; learning can be supervised or unsupervised; and models can be logical, geometric, probabilistic or ensembles of such models. Now that I have equipped you with the basic concepts to understand the literature, there is a whole world out there for you to explore. So it is only natural for me to leave you with a few pointers to areas you may want to learn about next.

One thing that we have often assumed in the book is that the data comes in a form suitable for the task at hand. For example, if the task is to label e-mails we conveniently learn a classifier from data in the form of labelled e-mails. For tasks such as class probability estimation I introduced the output space (for the model) as separate from the label space (for the data) because the model outputs (class probability estimates) are not directly observable in the data and have to be reconstructed. An area where the distinction between data and model output is much more pronounced is reinforcement learning. Imagine you want to learn how to be a good chess player. This could be viewed as a classification task, but then you require a teacher to score every move.

TWO HEADS ARE BETTER THAN ONE – a well-known proverb suggesting that two minds working together can often achieve better results. If we read ‘features’ for ‘heads’ then this is certainly true in machine learning, as we have seen in the preceding chapters. But we can often further improve things by combining not just features but whole models, as will be demonstrated in this chapter. Combinations of models are generally known as model ensembles. They are among the most powerful techniques in machine learning, often outperforming other methods. This comes at the cost of increased algorithmic and model complexity.

The topic of model combination has a rich and diverse history, to which we can only partly do justice in this short chapter. The main motivations came from computational learning theory on the one hand, and statistics on the other. It is a well-known statistical intuition that averaging measurements can lead to a more stable and reliable estimate because we reduce the influence of random fluctuations in single measurements. So if we were to build an ensemble of slightly different models from the same training data, we might be able to similarly reduce the influence of random fluctuations in single models. The key question here is how to achieve diversity between these different models. As we shall see, this can often be achieved by training models on random subsets of the data, and even by constructing them from random subsets of the available features.