6.2.3.1 Feature Representations

The main task of kernel methods is to find a good feature representation that is adapted to the training data, which can be used as an input for the subsequent training model that, for example, tries to find a $f^{⁎}$ that minimizes Eq. (6.1).

From Eq. (6.2), we know that the solution $f^{⁎}$ can be found by projecting data onto ${\mathcal{F}}_{\mathcal{D}}$. In practice, for a given training set $\{({\mathbf{x}}_1,y_1),\cdots ,({\mathbf{x}}_N,y_N)\}$, a kernel function $k:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$, the projection ${\mathcal{T}}_{\mathcal{D}}:\mathcal{H}\to {\mathcal{F}}_{\mathcal{D}}$ and an empirical risk ${\mathcal{R}}_e$, there are mainly two ways of representing the features: (i) by the kernel matrix or (ii) by constructing an explicit feature vector.

6.2.3.2 Kernelization of Linear Models

Given a linear model, kernelization refers to introducing nonlinearity to the linear model by using the aforementioned feature representations. This transformation can be implemented using Eq. (6.3) or Eq. (6.4). These two alternative representations are essentially equivalent, in the sense that, for any $\mathbf{x},\mathbf{z}\in \mathcal{X}$,

$\varphi {(\mathbf{x})}^T\varphi (\mathbf{z})=<{\mathcal{T}}_{\mathcal{D}}\phi (\mathbf{x}),{\mathcal{T}}_{\mathcal{D}}\phi (\mathbf{z})>.$

It is more common to use Eq. (6.3), where the learning model is formulated using the kernel matrix, such as SVMs, Kernel Ridge Regression (KRR), Kernel Principal Component Analysis (KPCA) and GPs. This alternative requires the follow-up learning algorithm to be formulated using only inner-products to represent input data. However, compared with Eq. (6.3), the explicit feature vector (cf. Eq. (6.4)) provides a more flexible representation. One can simply apply the nonlinear transformation in Eq. (6.4) and use $\varphi (\mathbf{x})\in {\mathbb{R}}^N$ as the new feature vector to input the next learning module. The advantages are:

6.2.4.1 Computational Complexity and Memory Usage

One of the major challenges of kernel methods is the computational complexity and memory usage. As shown in Eq. (6.3), to project the features onto the subspace ${\mathcal{F}}_{\mathcal{D}}$ (cf. Eq. (6.2)), one has to store and invert an $N\times N$ kernel matrix which has a computational complexity of $\mathcal{O}(N^3)$ and $\mathcal{O}(N^2)$ memory. It is usually not possible to run on a single node machine with limited RAM when N is very large.

6.2.4.2 Robustness and Overfitting

Another issue related to the model complexity is overfitting. Since the feature space is essentially the subspace spanned by $\{\phi ({\mathbf{x}}_1),\cdots ,\phi ({\mathbf{x}}_N)\}$, the “quality” of the training dataset is crucial to construct a robust feature space. That is, noisy training data might result in a relatively arbitrary feature representation. Besides trying to increase the Signal-to-Noise Ratio (SNR) of the measurement, which has limitations on its own, one commonly adopted solution is to find a more robust and invariant subspace of the feature space.

6.2.5.1 Random Fourier Features

Random Fourier feature [1] techniques construct an explicit feature map such that the inner-product of the explicit feature vectors can be used to approximate the kernel function. The kernel functions are required to be shift-invariant, i.e., $k(\mathbf{x},\mathbf{z})=k(\mathbf{x}-\mathbf{z})$ for any $\mathbf{x},\mathbf{z}\in \mathcal{X}$. The construction is carried out by drawing independent and identically distributed samples in the frequency domain of the kernel function. The main theorem to ensure the existence of random Fourier features is shown here.

Theorem 1 shows that ${\zeta }_{\mathit{\omega }}(\mathbf{x}){\zeta }_{\mathit{\omega }}{(\mathbf{z})}^{⁎}$ is an unbiased estimator of $k(\mathbf{x},\mathbf{z})$ for shift-invariant kernels. Since $k(\mathbf{x},\mathbf{z})$ is a real number, we have ${\zeta }_{\mathit{\omega }}(\mathbf{x})=\cos ({\mathit{\omega }}^{\text{T}}\mathbf{x})$.

The idea is then to construct an explicit feature map $z:\mathcal{X}\to {\mathbb{R}}^m$, such that

$z_{\mathit{\omega }}{(\mathbf{x})}^T{z}_{\mathit{\omega }}(\mathbf{z})={\zeta }_{\mathit{\omega }}(\mathbf{x}){\zeta }_{\mathit{\omega }}(\mathbf{z})$

$=\cos ({\mathit{\omega }}^{\text{T}}\mathbf{x}-{\mathit{\omega }}^{\text{T}}\mathbf{z})$

$=\sin ({\mathit{\omega }}^{\text{T}}\mathbf{x})\sin ({\mathit{\omega }}^{\text{T}}\mathbf{z})+\cos ({\mathit{\omega }}^{\text{T}}\mathbf{x})\cos ({\mathit{\omega }}^{\text{T}}\mathbf{z}).$

Empirically, the feature map can then be constructed using

$\varphi (\mathbf{x})=\sqrt{\frac{1}{m}}{\left[\begin{array}{cccccc}\hfill \cos ({\mathit{\omega }}_1^{\text{T}}\mathbf{x})\hfill & \hfill \cdots \hfill & \hfill \cos ({\mathit{\omega }}_m^{\text{T}}\mathbf{x})\hfill & \hfill \sin ({\mathit{\omega }}_1^{\text{T}}\mathbf{x})\hfill & \hfill \cdots \hfill & \hfill \sin ({\mathit{\omega }}_m^{\text{T}}\mathbf{x})\hfill \end{array}\right]}^{\text{T}},$

where ${\mathit{\omega }}_1,\cdots ,{\mathit{\omega }}_m$ are independent and identically distributed samples drawn from $p(\mathit{\omega })$.

The algorithm is summarized in Algorithm 1. Details will be addressed in Chapter 7.

6.2.5.2 Nyström Methods: Subspace Learning

Another important family of kernel approximation techniques are the Nyström methods, where the effective rank of the kernel matrix is exploited in a more direct fashion. That is, one assumes an underlying subspace structure in the kernel matrix, i.e., $\mathbf{K}\approx \hat{\mathbf{K}}$ for some $\hat{\mathbf{K}}$ such that $rank(\hat{\mathbf{K}})=m<N$. The task is then to use the rank-deficient matrix $\hat{\mathbf{K}}$ to approximate the kernel matrix.

In its basic form, Nyström randomly selects a subset of the training data $\mathcal{G}\subset \mathcal{D}$ and constructs the approximation using

$\hat{\mathbf{K}}=\underset{\in {\mathbb{R}}^{N\times m}}{\underbrace{k({\mathbf{X}}_{\mathcal{D}},{\mathbf{X}}_{\mathcal{G}})}}\underset{\in {\mathbb{R}}^{m\times m}}{\underbrace{k{({\mathbf{X}}_{\mathcal{G}},{\mathbf{X}}_{\mathcal{G}})}^{-1}}}\underset{\in {\mathbb{R}}^{m\times N}}{\underbrace{k({\mathbf{X}}_{\mathcal{G}},{\mathbf{X}}_{\mathcal{D}})}}={\mathbf{K}}_{\mathcal{D}\mathcal{G}}{\mathbf{K}}_{\mathcal{G}}^{-1}{\mathbf{K}}_{\mathcal{G}\mathcal{D}}.$

The random subset selection is computationally simple and in many cases sufficient to capture the underlying data structure in many applications. Many more advanced sampling strategies have been proposed for different purposes. Most techniques cast the approximation problem as an estimation of the top m singular values of K. Essentially, they attempt to approximate the subspace as well as possible while trying to reduce the computational complexity and/or storage usage. For example, some of these techniques include subspace approximation using the incomplete Cholesky decomposition [17]; identifying representative points by clustering [18]; enabling parallelization and performance boosting by the ensemble Nyström method. Some other methods explore the intrinsic structure of the kernel matrix to obtain a more compact and efficient memory storage, such as the Memory-Efficient Kernel Approximation (MEKA) [8], Clustered Low-Rank Approximation (CLRA) [19] and the CLAss-Specific Kernel (CLASK) subspace approximation [7]. These techniques more or less share the same base algorithm with different sampling criteria and/or feature representation strategy. In the following sections, we explore the underlying framework of kernel subspace approximation and its adaptive learning algorithms.

6.3.2.1 Approximated Kernel Matrix

One computational advantage of kernel methods is that all computations are carried out by inner-products. The kernel matrix K (cf. Eq. (6.3)) that holds the pair-wise inner-product of the training data is then a key component of kernel methods. Essentially, the subspace approximation can be interpreted as weighted inner-products, which transforms the kernel matrix as

$\mathbf{K}\approx \tilde{\mathbf{K}}=\underset{{\mathbf{K}}_{\mathcal{D}\mathcal{G}}\in {\mathbb{R}}^{N\times |\mathcal{G}|}}{\underbrace{\left[\begin{array}{c}\hfill k{({\mathbf{X}}_{\mathcal{G}},{\mathbf{x}}_1)}^{\text{T}}\hfill \\ \hfill ⋮\hfill \\ \hfill k{({\mathbf{X}}_{\mathcal{G}},{\mathbf{x}}_N)}^{\text{T}}\hfill \end{array}\right]}}\mathbf{T}{\mathbf{T}}^{\text{T}}\underset{{\mathbf{K}}_{\mathcal{G}\mathcal{D}}\in {\mathbb{R}}^{|\mathcal{G}|\times N}}{\underbrace{\left[\begin{array}{ccc}\hfill k({\mathbf{X}}_{\mathcal{G}},{\mathbf{x}}_1)\hfill & \hfill \cdots \hfill & \hfill k({\mathbf{X}}_{\mathcal{G}},{\mathbf{x}}_N)\hfill \end{array}\right]}}\in {\mathbb{R}}^{N\times N},$

where $k({\mathbf{X}}_{\mathcal{G}},\mathbf{x})=\left[\begin{array}{c}\hfill k({\mathbf{x}}_{i_1},\mathbf{x})\hfill \\ \hfill ⋮\hfill \\ \hfill k({\mathbf{x}}_{i_{|\mathcal{G}|}},\mathbf{x})\hfill \end{array}\right]$ and indices $\{i_j:i_j\in {\mathcal{I}}_{\mathcal{G}},j=1\cdots |\mathcal{G}|\}$ denote the index set of the subset $\mathcal{G}$. The weighting matrix $\mathbf{T}{\mathbf{T}}^{\text{T}}$ (cf. Eq. (6.13)) is rank-deficient.

After kernel approximation, the size of the kernel matrix remains the same and the approximated kernel matrix $\tilde{\mathbf{K}}$ becomes rank-deficient, i.e., rank($\tilde{\mathbf{K}}$)=m. However, in combination with the matrix inversion lemma, the kernel matrix inversion can be reduced to

${(\mathbf{K}+\lambda \mathbf{I})}^{-1}\approx {(\tilde{\mathbf{K}}+\lambda \mathbf{I})}^{-1}=\frac{1}{\lambda }\mathbf{I}-\frac{1}{{\lambda }^2}{\mathbf{K}}_{\mathcal{D}\mathcal{G}}\mathbf{T}\underset{\in {\mathbb{R}}^{m\times m}}{\underbrace{{(\mathbf{I}+\frac{1}{\lambda }{\mathbf{T}}^{\text{T}}{\mathbf{K}}_{\mathcal{G}\mathcal{D}}{\mathbf{K}}_{\mathcal{D}\mathcal{G}}\mathbf{T})}^{-1}}}{\mathbf{T}}^{\text{T}}{\mathbf{K}}_{\mathcal{G}\mathcal{D}}.$

The computational complexity is listed as follows:

Due to the fact that $N\gg |\mathcal{G}|⩾m$, we have the overall complexity $\mathcal{O}(N|\mathcal{G}|m)$.

6.3.2.2 Approximated Sample Covariance Matrix Using Explicit Feature Vectors

Kernel approximation can be readily applied to create an explicit feature vector by a map $\tilde{\varphi }:\mathcal{X}\to {\mathbb{R}}^m$. Specifically,

$\tilde{\varphi }(\mathbf{x})={\mathbf{T}}^{\text{T}}\left[\begin{array}{c}\hfill k({\mathbf{x}}_{i_1},\mathbf{x})\hfill \\ \hfill ⋮\hfill \\ \hfill k({\mathbf{x}}_{i_{|\mathcal{G}|}},\mathbf{x})\hfill \end{array}\right]\in {\mathbb{R}}^m.$

Eq. (6.16) can then be used as the feature vector for the succeeding learning model. When applying Eq. (6.16) to linear learning techniques, the sample covariance matrix typically needs to be inverted. Let us assume that the feature vector $\tilde{\varphi }(\mathbf{x})$ is always centered (cf. Appendix 6.A.1), the (scaled) sample covariance matrix is defined as

$\mathbf{C}=\left[\begin{array}{ccc}\hfill \tilde{\varphi }({\mathbf{x}}_1)\hfill & \hfill \cdots \hfill & \hfill \tilde{\varphi }({\mathbf{x}}_N)\hfill \end{array}\right]\left[\begin{array}{c}\hfill \tilde{\varphi }{({\mathbf{x}}_1)}^{\text{T}}\hfill \\ \hfill ⋮\hfill \\ \hfill \tilde{\varphi }{({\mathbf{x}}_N)}^{\text{T}}\hfill \end{array}\right]$

$\begin{array}{ccc}\hfill & \hfill =\hfill & {\mathbf{T}}^{\text{T}}\left[\begin{array}{ccc}\hfill k({\mathbf{X}}_{\mathcal{G}},{\mathbf{x}}_1)\hfill & \hfill \cdots \hfill & \hfill k({\mathbf{X}}_{\mathcal{G}},{\mathbf{x}}_N)\hfill \end{array}\right]\left[\begin{array}{c}\hfill k{({\mathbf{X}}_{\mathcal{G}},{\mathbf{x}}_1)}^{\text{T}}\hfill \\ \hfill ⋮\hfill \\ \hfill k{({\mathbf{X}}_{\mathcal{G}},{\mathbf{x}}_N)}^{\text{T}}\hfill \end{array}\right]\mathbf{T}\hfill \\ \hfill & \hfill \in \hfill & {\mathbb{R}}^{m\times m}.\hfill \end{array}$

The computational complexity of ${\mathbf{C}}^{-1}$ is composed of:

Hence, we have the overall computational complexity $\mathcal{O}(N|\mathcal{G}|m)$.

In the next section, we focus on an adaptive algorithmic framework and its instantiations to construct desired subspaces.

6.4.2.1 Design Criteria

Generally speaking, we are interested in building a model (i.e., the approximated subspace) with a high generalization ability, which is measured by the performance on unseen datasets. The generalization ability is closely related to the model complexity. That is, a model with a high complexity tends to result in a high performance on the training data, but it might perform poorly on testing datasets and vice versa. It is referred to as the “overfitting” problem.

This can be observed by the bias-variance trade-off, where the performance statistics are measured when the model is trained using different training sets with a fixed training size. More precisely, when the model complexity is high, the search space of the model parameters is large and hence the bias of the model tends to be low. On the other hand, since the model is derived from the training data, the higher complexity the model has, the higher variance as a result we find.

The strategy for achieving a high generalization is twofold: one needs to (1) reduce the model complexity and (2) maintain a low empirical risk on the training data. By combining an intuitive illustration in Fig. 6.3 and the actual model representation in Eq. (6.16), we see that the model complexity (the “size” of the circle) is related to (1) the size of the subset $\mathcal{G}$ and (2) the number of columns in T; and the empirical risk (the “location” of the circle) depends on (1) the sampling criteria for $\mathcal{G}$ and (2) the construction strategy for the transformation matrix T. Given the analysis, in this section, we demonstrate some design criteria for Algorithm 2.

Rejecting samples with a low innovation: The “innovation” of a data point x is the projection error from $\phi (\mathbf{x})$ to the existing subspace. The sample is only accepted if the innovation is large enough, i.e.,

$k(\mathbf{x},\mathbf{x})-{\mathbf{k}}_{\mathcal{G}j}^{\text{T}}{\mathbf{invK}}_{\mathcal{G}}{\mathbf{k}}_{\mathcal{G}j}⩾\eta \in (0,1).$

When Eq. (6.23) is violated, it means that it is not necessary to include $\phi (\mathbf{x})$. Hence, the larger η is, the less data points are included in the subspace construction.

Dimension reduction by choosing principal components: Principal Component Analysis (PCA) [23] belongs to the most commonly used linear techniques for dimension reduction purposes. From Eq. (6.16), we see that, given the subset $\mathcal{G}$ and a hyperparameter $m<|\mathcal{G}|$, the transformation matrix $\mathbf{T}\in {\mathbb{R}}^{|\mathcal{G}|\times m}$ can be constructed by applying PCA on the dataset $\mathcal{U}=\{{[k({\mathbf{x}}_{i_1},\mathbf{x})\cdots k({\mathbf{x}}_{i_{|\mathcal{G}|}},\mathbf{x})]}^{\text{T}}\},\forall \mathbf{x}\in \mathcal{D}\}$. That is, let $\tilde{\mathbf{T}}$ be the matrix that contains the sorted principal vectors computed from $\mathcal{U}$ as its columns. The matrix T is obtained by truncation. We have

$\mathbf{T}=\tilde{\mathbf{T}}(:,1:m).$

Since $m<|\mathcal{G}|$, the model complexity is then further reduced.

Class Separability: In classification problems, the reconstruction error is not the only criterion to measure the quality of the subspace. When label information is available, the discriminative ability is preferably taken into consideration. This information can be encoded in various ways. For example, the CLAss-specific Subspace Kernel (CLASK) representation [7] encodes the information into the feature vector by constructing one subspace for each class. The sampling criteria depend on the between-class projection error. Fisher discriminant analysis [24] finds a transformation matrix T that maximizes the Fisher Quotient, which measures the class separability. Other constrained optimizations can be applied to finding T that results in a good class separation, which can be cast as metric learning [25–27] problems.

Ensemble techniques: One efficient way of reducing the variance is to learn multiple models from subsets of training data and the final estimate is based on an ensemble decision. One such example would be the ensemble Nyström method [28], where

$\hat{\mathbf{K}}=\sum _{r=1}^P{\mu }_r{\hat{\mathbf{K}}}_r$

and each ${\hat{\mathbf{K}}}_r$ is estimated from a subset of $\mathcal{D}$ and ${\mu }_r$ are the weights for $r=1\cdots P$, $P\in {\mathbb{N}}^{+}$.

6.4.2.2 Empirical Risk

Given a model $\mathcal{F}$ designed by the aforementioned criteria, empirical risks are measured to ensure that the “location” of the circle in Fig. 6.3 is not way off. Typically, with the same model complexity, the model corresponding to a lower empirical risk is preferred. Typically, there are two empirical risks to be considered.

Reconstruction error: The approximated subspace $\mathcal{F}$ (cf. Eq. (6.12)) has to be representative and is evaluated by the following reconstruction error on the training data. Let ${\hat{\mathit{\phi }}}_n$ be the projection of $\phi ({\mathbf{x}}_n)$ onto $\mathcal{F}$. The empirical risk of the reconstruction error (on the training set $\mathcal{D}$) is defined as

${\mathcal{E}}_{\mathcal{F}}=\frac{1}{N}\sum _{n=1}^N\frac{{\left||{\mathit{\phi }}_n-{\sum }_{i=1}^{|\mathcal{G}|}{a}_{n,i}^{⁎}{\hat{\mathit{\phi }}}_n|\right|}_2^2}{{\Vert {\mathit{\phi }}_n\Vert }^2}$

$=\frac{1}{N}\sum _{n=1}^N(1-\frac{{\left||{\sum }_{j=1}^{|\mathcal{G}|}{a}_{n,i}^{⁎}k({\mathbf{x}}_n,{\mathbf{x}}_i)\mathbf{T}{\mathbf{T}}^{\text{T}}k({\mathbf{x}}_n,{\mathbf{x}}_i)|\right|}_2^2}{k({\mathbf{x}}_n,{\mathbf{x}}_n)}),$

where $a_{n,i}^{⁎}$'s are found by

$a_{n,i}^{⁎}=\underset{a_{1,1},\cdots ,a_{N,m}}{\arg \min }{\mathcal{E}}_{\mathcal{F}}(a_{1,1},\cdots ,a_{N,m}).$

We see that, by setting the hyperparameters η (cf. Eq. (6.23)) to a small value, the reconstruction error ${\mathcal{E}}_{\mathcal{F}}$ becomes small. On the other hand, a small number of columns in T results in a large ${\mathcal{E}}_{\mathcal{F}}$ due to the truncation (cf. Eq. (6.24)).

Classification error: In classification problems, the ultimate risk function is the 0–1 loss, which is defined as

${\mathcal{L}}_{\mathcal{F}}=\frac{1}{N}\sum _{n=1}^N\mathbf{1}(f_{\mathcal{F}}^{⁎}({\hat{\mathit{\phi }}}_n)\ne y_n),$

where $y_n$ are the labels for data ${\mathbf{x}}_n$, 1 is the indicator function and $f_{\mathcal{F}}^{⁎}$ is found by minimizing ${\mathcal{L}}_{\mathcal{F}}$. Note that, given a training set, this empirical risk depends not only on the subspace approximation algorithm, but also on the classification learning model.