Introduction

It is well known that a classifier's effectiveness depends strongly on the distribution of the (training and testing) datasets. Consequently, we will not know in advance the best possible classifiers for data analysis. This prompts the need to develop a versatile classifier endowed with an adequate set of adjustable parameters to cope with various real-world application scenarios. Two common ways to enhance the robustness of the classifiers are by means of (1) using a proper ridge factor to mitigate over-fitting problems (as adopted by KRR) and/or (2) selecting an appropriate number of support vectors to participate in the decision making (as adopted by SVM). Both regularization mechanisms are meant to enhance the robustness of the learned models and, ultimately, improve the generalization performance.

This chapter introduces the notion of a weight–error curve (WEC) for characterization of kernelized supervised learning models, including KDA, KRR, SVM, and Ridge-SVM. Under the LSP condition, the decision vector can be “voted” as a weighted sum of training vectors in the intrinsic space – each vector is assigned a weight in voting. The weights can be obtained by solving the kernelized learning model. In addition, each vector is also associated with an error, which is dictated by its distance from the decision boundary. In short, given a learned model, each training vector is endowed with two parameters: weight and error. These parameters collectively form the so-called WEC. The analysis of the WEC leads us to a new type of classifier named Ridge-SVM.

Introduction

Since the invention of integrated circuits in the 1950s, processing gates and memory storages on a chip have grown at an exponential rate. Major breakthroughs in wireless and internet technologies have further promoted novel information technologies (IT). New applications, such as cloud computing and green computing, will undoubtedly have profound impacts on everyone's daily life.

Machine learning will play a vital part in modern information technology, especially in the era of big data analysis. For the design of kernel-based machine learning systems, it is important to find suitable kernel functions that lead to an optimal tradeoff between design freedom and computational complexity, which involves very often a choice between the intrinsic-space and empirical-space learning models.

A successful deployment of a machine learning system hinges upon a well-coordinated co-design of algorithm and hardware. This chapter addresses practical design issues related to cost-effective learning or low-power prediction that are vital for green IT applications.

This chapter addresses the following topics concerning cost-effective system implementations both in the learning phase and in the prediction phase.

This part contains three chapters with the focus placed on support vector machines (SVM). The SVM learning model lies right at the heart of kernel methods. It has been a major driving force of modern machine learning technologies.

Chapter 10 is focused on the basic SVM learning theory, which relies on the identification of a set of “support vectors” via the well-known Karush–Kuhn–Tucker (KKT) condition. The “support vectors” are solely responsible for the formation of the decision boundary. The LSP is obviously valid for SVM learning models and the kernelized SVM learning models have exactly the same form for linear and nonlinear problems. This is evidenced by Algorithm 10.1.

Chapter 11 covers support-vector-based learning models aiming at outlier detection. The support vector regression (SVR), see Algorithm 11.1, aims at finding an approximating function to fit the training data under the guidance of teacher values. The chapter explores, in addition, several SVM-based learning models for outlier detection, including hyperplane OCSVM (Algorithm 11.2), hypersphere OCSVM (Algorithm 11.3), and SVC. For all these learning models, the fraction of outliers can be analytically estimated – a sharp contrast to the other SVM learning models. In fact, for Gaussian kernels, it can be shown that all three algorithms coincide with each other. However, when polynomial kernels are adopted, the translation-invariance property is a legitimate concern for the hyperplane-OCSVM learning models.

Chapter 12 introduces the notion of a weight–error curve (WEC) for characterization of kernelized supervised learning models, including KDA, KRR, SVM, and Ridge-SVM.

This part contains three chapters, covering learning models closely related to the kernel ridge regressor (KRR).

1. (i) Chapter 7 discusses applications of the kernel ridge regressor (KRR) to regularization and approximation problems.

2. (ii) Chapter 8 covers a broad spectrum of conventional linear classification techniques, all related to ridge regression.

3. (iii) Chapter 9 extends the linear classification to kernel methods for nonlinear classifiers that are closely related to the kernel ridge regressor (KRR).

Chapter 7 discusses the role of ridge regression analysis in regularization problems. The optimization formulation for the kernel ridge regressor (KRR), in the intrinsic space, obviously satisfies the LSP condition in Theorem 1.1, implying the existence of a kernelized KRR learning model, see Algorithm 7.1.

If a Gaussian RBF kernel is adopted, the KRR learning model is intimately related to several prominent regularization models:

1. (i) the RBF approximation networks devised by Poggio and Girosi [207];

2. (ii) Nadaraya–Watson regression estimators [191, 293]; and

3. (iii) RBF-based back-propagation neural networks [198, 226, 294].

The chapter also addresses the role of the multi-kernel formulation in regression/classification problems. It shows that, if the LSP condition is satisfied, then some multi-kernel problems effectively warant a mono-kernel solution.

Chapter 8 covers a family of linear classifiers. The basic linear regression analysis leads to the classical least-squares-error (LSE) classifiers, see Algorithm 8.1.The derivation of Fisher's conventional linear discriminant analysis is based on finding the best projection direction which can maximize the so-called signal-to-noise ratio; see Algorithm 8.2.

Introduction

The notion of kernel-induced vector spaces is the cornerstone of kernel-based machine learning. Generalization of the traditional definition of a similarity metric plays a vital role in facilitating the analysis of complex and big data. It is often necessary to generalize the traditional Euclidean inner product to the more flexible and nonlinear inner products characterized by properly chosen kernel functions. The new inner product leads to a new distance metric, allowing the data analysis to be effectively performed in a higher-dimensional vector space. The topics addressed in this chapter are as follows.

• Section 2.2 introduces Mercer's fundamental theorem stating the necessary and sufficient condition for a function be a Mercer kernel. It will examine several prominent kernel functions, including the polynomial and Gaussian kernel functions.

• Section 2.3 introduces the notion of intrinsic space associated with a kernel function. The intrinsic space is so named because it is independent of the training dataset. The dimension of the space is denoted by J and will be referred to as the intrinsic degree. This degree, whether finite or infinite, dictates the training efficiency and computational cost.

• Section 2.4 introduces a finite-dimensional kernel-induced vector space, known as empirical space, which is jointly determined by the kernel function and the training dataset. The dimension of the empirical space is equal to the data size N. With the LSP condition, both the intrinsic-space and the kernelized learning model will be at our disposal.

Introduction

Two primary techniques for dimension-reducing feature extraction are subspace projection and feature selection. Compared with subspace projection, feature selection has the following advantages.

• Owing to its simplicity, feature selection can quickly and effectively weed out a large fraction of the insignificant features and yield a manageable vector dimension for subsequent data analysis.

• Feature selection is appealing from the perspective of online processing. Processing speed and power consumption are usually the major concerns for online processing. Feature selection results in a reduced number of selected features. This means that fewer features will need to be acquired in the input acquisition phase, thus saving processing power in the raw-data acquisition phase. This saving does not apply to the subspace projection approach, for which all of the original features must be acquired first before proper linear combinations can be computed to generate principal components.

• There are application-specific roles of feature selection, which simply could not be replaced by subspace projection. For example, gene selection is vital to genomic study. It is known that a few genes are often responsible for the cause or cure of tumors while most of the remaining genes are just “housekeeping” genes that have no functional roles and should be discarded for the sake of performance. Moreover, if a specific subset of genes is specially effective for accurate prediction of certain tumors, those genes are also most likely to be the biomarkers for the design of effective drugs to cure the tumors.

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.