End-to-end Kernel Learning
via Generative Random Fourier Features

In kernel methods, a positive definite kernel $k(\mathbf{x},\mathbf{x^{\prime}})$ with $\mathbf{x},\mathbf{x^{\prime}}\in\mathcal{R}^{d}$ defines a map $\Phi:\mathcal{R}^{d}\to\mathcal{H}$, which satisfies $k(\mathbf{x},\mathbf{x^{\prime}})=\langle\Phi(\mathbf{x}),\Phi(\mathbf{x^{\prime}})\rangle_{\mathcal{H}}$, where $\langle\cdot,\cdot\rangle_{\mathcal{H}}$ denotes the inner product in a Reproducing Kernel Hilbert Space $\mathcal{H}$. However, in large-scale kernel machines, there exist unacceptable high computation and memory costs: $\mathcal{O}(n^{2})$ kernel evaluations, $\mathcal{O}(n^{2})$ in space, and even $\mathcal{O}(n^{3})$ in time to compute the inverse of the kernel matrix. Therefore, randomized features are introduced in large-scale cases to approximate the kernel function [5]. The theoretical foundation is based on the Bochner’s theorem [9], which indicates that the Fourier transform of a kernel function is associated to a probability distribution: A continuous and shift-invariant kernel $k(\mathbf{x},\mathbf{x^{\prime}})=k(\mathbf{x}-\mathbf{x^{\prime}})$ on $\mathcal{R}^{d}$ is positive definite if and only if $k(\cdot)$ is the Fourier transform of a non-negative measure $p(\mathbf{w})$. That is,

Considering a real-valued, shift-invariant and positive definite kernel $k$, by applying the Euler’s formula $e^{\mathrm{j}x}=\cos(x)+\mathrm{j}\sin(x)$ to Eq.(3), we have

Therefore, one can construct an explicit feature map $\phi:\mathcal{R}^{d}\to\mathcal{R}^{2D}$ as follows:

known as the random Fourier features [5]. The set of weights $\{\mathbf{w}_{i}\}^{D}_{i=1}$ is sampled from the spectral distribution of the kernel function. The mapped random Fourier features satisfy $\phi(\mathbf{x},\{\mathbf{w}_{i}\}^{D}_{i=1})^{T}\phi(\mathbf{x^{\prime}},\{\mathbf{w}_{i}\}^{D}_{i=1})\approx k(\mathbf{x},\mathbf{x^{\prime}})$ [5]. A detailed analysis of the convergence can be found in [10].

The vanilla RFFs [5] accelerate the large-scale kernel machines a lot and are data-independent. Afterwards, RFFs have been widely utilized, including the kernel approximation [11], extreme learning machines [12], the bias-variance trade-off in machine learning [13] and the kernel learning task [6, 7]. A systematic survey on RFFs-based algorithms can be found in [14].

Inspired by the vanilla RFFs, learning the features is equal to learning the weights $\{\mathbf{w}_{i}\}^{D}_{i=1}$, while learning the weights is equal to learning the kernel distribution. Hence, to efficiently learn the distribution, generative models are introduced.

Generative models have been widely applied in learning distributions from data [15]. Various generative models can be categorized into two types: models that perform explicit probability density estimations, and models that perform as a sampler sampling from the estimated distribution without a precise probability function.

Suppose a training set includes samples from a distribution $\mathbb{P}_{data}$, then the first type of generative models returns an estimation $\mathbb{P}_{model}$ of $\mathbb{P}_{data}$. Given a particular value as input, the estimation $\mathbb{P}_{model}$ will output the corresponding probability. While the second type tries to learn the latent $\mathbb{P}_{data}$ as well, but in a rather different way: The learned model actually simulates a sampling process, through which one can generate more samples from the estimated distribution.

There exist lots of researches in the second type of generative models using a deep neural network as the sampler. In computer vision, the family of generative adversarial networks (GANs) [16] has shown great generality in various situations [17, 18]. The generative network in GANs performs as a useful image generator, which generates images by sampling from the learned image distribution. Besides, in Bayesian deep learning, there is a series of hypernetwork-based works, which use a neural network, called hypernet, to generate the parameters in another neural network, called primary net. The hypernet also performs as a sampler to learn the parameter posterior distribution of the primary net [19, 20].

Therefore, the generative networks are employed in the proposed GRFFs due to the powerful distribution learning ability. The resulting merits are two-fold: On the one hand, the GRFFs could learn a well-generalized kernel distribution from data. On the other hand, the generative networks could produce non-deterministic weights, bringing the adversarial robustness gains.

Previous RFFs-based kernel learning methods construct random features via sampling from the spectral distribution of the kernel [5] or via approximating the ideal kernel [6, 7], and then train a classifier on these features. The classification performance of the random features learned in this two-stage manner can perhaps be further improved. Therefore, we propose generative RFFs to jointly learn the features and the classifier by optimizing the expectation risk minimization problem in an end-to-end manner, which leads to a one-stage solution with better classification performance.

We first describe a general framework of our one-stage model, illustrated in Fig.1. A generator is designed to learn and to sample from the latent kernel distribution. Then, the generative random Fourier features of the original data are constructed by the sampled weights from the learned distribution. Finally, a linear classifier is applied to the features to categorize them.

The generator in our method performs as a sampler. It implicitly learns some distribution $\mathbb{P}_{k}$ and generates samples from it. Given an arbitrary noise distribution $\mathbb{P}_{0}$ and a set of noises $\mathbf{N}=\{\mathbf{n}_{i}\}^{D}_{i=1}$ sampled from $\mathbb{P}_{0}$, the generator $\Phi_{G}$ takes them as input and generates the corresponding set of weights $\{\mathbf{w}_{i}\}^{D}_{i=1}$ sampled from $\mathbb{P}_{k}$:

Given a training set $\{(\mathbf{x}_{i},y_{i})\}_{i=1}^{n}$, the generative random Fourier features $\mathbf{z}_{i}$ of each training point $\mathbf{x}_{i}$ will be constructed with full use of the $D$ weights $\{\mathbf{w}_{j}\}^{D}_{j=1}$ according to Eq.(5):

Notice that the weight $\mathbf{w}_{j}$ and the data point $\mathbf{x}_{i}$ are of the same dimension and that the dimension of $\mathbf{z}_{i}$ equals to $2D$. In the end, the linear classifier $\Phi_{C}$ will be applied on the GRFFs $\mathbf{z}_{i}$ to predict the label $\hat{y}_{i}=\Phi_{C}(\mathbf{z}_{i})$.

Denote $\theta_{G}$ and $\theta_{C}$ as the parameters of the generator $\Phi_{G}$ and the linear classifier $\Phi_{C}$ respectively. Combining Eq.(6) and Eq.(7), we have the following empirical risk minimization (ERM) problem:

The end-to-end training strategy by straightly optimizing the ERM problem naturally allows us to employ a multi-layer structure of GRFFs, shown in Fig.2. To be specific, with one generator, we can build the random features of the original data, which can be viewed as the first layer of features. Then, with another generator, a second layer of random features can be constructed in the same way based on the features from the previous layer. After such a layer-by-layer operation, the random features in the last layer are followed with an FC layer. The total networks, i.e., all the generators and the last FC layer, are again jointly trained to solve the ERM problem. In this way, in each layer, there exists a corresponding generator which models the specific distribution on this layer of features, indicating a good kernel learned on features.

In those two-stage approaches [5, 6, 7], the distribution is associated with a pre-defined kernel, which is restricted to a single-layer structure, since the kernel for the multi-layer case is not clear. By contrast, we cover the multi-layer case, and thus have an advantage in learning a much more linear-separable pattern from data under the guidance of the learned kernels on features.

Without loss of generality, a detailed elaboration on the two-layer structure is presented below as an example, which could be naturally generalized to any number of layers (see Alg.1). Denote $\Phi_{G_{1}}$ and $\Phi_{G_{2}}$ as the two generators in the first and second layers respectively. The two generators, $\Phi_{G_{1}}$ and $\Phi_{G_{2}}$, take two sets of noises $\mathbf{N}_{1}=\{\mathbf{n}_{i}^{1}\}_{i=1}^{D_{1}}$ and $\mathbf{N}_{2}=\{\mathbf{n}_{i}^{2}\}_{i=1}^{D_{2}}$ independently sampled from the same distribution $\mathbb{P}_{0}$ as input respectively, and generate the corresponding weights $\mathbf{W}_{1}=\{\mathbf{w}_{i}^{1}\}_{i=1}^{D_{1}}$ and $\mathbf{W}_{2}=\{\mathbf{w}_{i}^{2}\}_{i=1}^{D_{2}}$:

where $\mathbb{P}_{k_{1}}$ and $\mathbb{P}_{k_{2}}$ are the distributions modeled by $\Phi_{G_{1}}$ and $\Phi_{G_{2}}$ respectively.

In the first layer, a training sample $\mathbf{x}_{i}$ cooperates together with $\mathbf{W}_{1}$ to construct the generative random Fourier feature $\mathbf{z}_{i}^{1}$ according to Eq.(5):

Then, the random feature $\mathbf{z}_{i}^{1}$ cooperates together with the generative weights $\mathbf{W}_{2}$ from the second layer to construct the generative random Fourier feature in the second layer $\mathbf{z}_{i}^{2}$ in the same way:

Again, notice that $\mathbf{w}^{1}_{j}$ and $\mathbf{x}_{i}$ are of the same dimension and that the dimension of $\mathbf{z}^{1}_{i}$ equals to $2D_{1}$. Accordingly, the dimension of $\mathbf{w}^{2}_{j}$ equals to $2D_{1}$ and the dimension of $\mathbf{z}^{2}_{i}$ equals to $2D_{2}$. Finally, there is a linear classifier $\Phi_{C}$ applied to the last random feature $\mathbf{z}_{i}^{2}$ to output the prediction.

Now we rewrite the ERM problem in Eq.(8) for the two-layer GRFFs as follows,

Advantages of the multi-layer structure are obvious. The generator in the current layer actually models some distribution on features from the previous layer, indicating a good kernel on features. Besides, associated with the proposed progressively training strategy (introduced in section 3.3), during the whole training process, by updating the generators layer-by-layer, there are distinct improvements on both the loss curves and the accuracy curves (see Fig.3), implying that adding more layers leads to significant performance leaps. More details about the distributions on features are illustrated in section 4.

For the multi-layer generative random Fourier features, since there exist several generative networks, it is hard to efficiently update all the parameters in multiple networks simultaneously, which possibly results in a total failure of convergence [21]. Therefore, inspired by the training in ProGAN [18], we propose a progressively training strategy to efficiently train the multiple generators in an inverse and layer-by-layer order.

The progressively training strategy contains several phases. The number of phases equals to the number of generators. In the first phase, we freeze the update of all the parameters except the last generator and the FC layer. After the training converges, we step into the next phase. Now the penultimate generator is unfrozen and gets updated together with the last one and the FC layer until convergence, while the others are still kept fixed. In such an inverse and layer-by-layer order, we progressively unfreeze the generators in each layer, add them to the training sequence one by one, and finally train all these generators together with the FC layer, which is empirically proved as an efficient training way for the multi-layer structure. This progressively training alogrithm is demonstrated in Alg.1.

In addition, more details of the generator are described. Every generator is parameterized as a multi-layer perceptron (MLP), which can be viewed as a composition of several cascaded blocks. Among these blocks, except for the last one, each block sequentially holds a linear layer, a batch normalization [22] layer, and an activation layer with leaky ReLU function. In the last block, we remove the batch normalization layer and replace leaky ReLU with tanh function as the activation. Fig.1 illustrates the described components inside the generator. Furthermore, one can customize the network according to the practical cases. For example, it is allowed to increase the number of blocks in the MLP to enhance its learning ability or to add dropout [23] to alleviate overfitting. The number of neurons in the last FC layer can be modified freely for multi-classification or regression tasks.

The standard normal distribution is set as the input noise distribution $\mathbb{P}_{0}$, which corresponds to a radial basis function (RBF) kernel, the most widely used universal kernel. At each iteration, we independently resample noises from $\mathbb{P}_{0}$ to optimize the generators on the expectation of the distribution, and update simultaneously the parameters of the generators and the classifier by Adam [24] optimizer. We choose the cross entropy function as the loss function $L$. One can estimate whether the model is trained until convergence by watching the variation of the cross entropy loss value, with which the final classification performance is closely connected.

For the inference process, given a new sample $\mathbf{x}_{new}$, random noises are first sampled from $\mathbb{P}_{0}$, then the weights are generated via the generators, then the corresponding generative random Fourier feature $\mathbf{z}_{new}$ is constructed via the weights and $\mathbf{x}_{new}$ by applying Eq.(7) or Eq.(10), Eq.(11). Finally, the linear classifier $\Phi_{C}$ will predict the label of $\mathbf{x}_{new}$.

So far, we finish building an end-to-end, one-stage kernel learning method, which implicitly learns the kernel distribution by solving an ERM problem via the generative RFFs. To learn the latent kernel distribution, a generative network is designed to simulate the sampling process without an explicit definition of the probability density function of the distribution. Besides, jointly learning the features and the classifier allows us to increase the depth of features. The resulting multi-layer structure can learn a good kernel on features and thus even boosts the generalization performance. In addition, a progressively training strategy is proposed to efficiently train the multiple generative networks.

Remark We would like to reiterate the following facts. It’s worth noting that the initial motivation of RFFs-based methods is to reduce the time and space complexity in large-scale kernel machines. For instance, the vanilla RFFs [5] speed up the kernel machines a lot, then get even accelerated in [6]. Further, random features are then extended to kernel learning, since RFFs actually provide a good justification for kernel learning in the spectral cases. The researches in [6, 7] are two typical kernel learning algorithms via random features, see a recent survey [14] on the development of RFFs-based algorithms for kernel learning. Regarding to our method, the target is to perform kernel learning via RFFs, but NOT reducing the time-consuming. In fact, since the neural network requires training, our method and the method in [7] are inevitably inferior in the processing speed during training and inference, compared with those algorithms specifically designed for kernel acceleration [5, 6]. Instead, the purpose of our method is to learn a more well-generalized kernel based on the fact that the optimization objective in [6, 7], i.e., solving the target alignment, is not necessarily optimal in classification tasks. To achieve such a purpose, we introduce the generative networks and adopt an end-to-end scheme to reach a one-stage solution. The resulting two merits of this solution, better generalization and stronger robustness, will be empirically illustrated in the next section.

For the synthetic set, we generate $\{\mathbf{x}_{i}\}_{i=1}^{n}\sim\mathcal{N}(0,I_{d})$ with $y_{i}=\mathrm{sign}(\|\mathbf{x}_{i}\|^{2}-\sqrt{d})$, where $d$ is data dimension. The training set includes ${10}^{4}$ samples and the test set contains ${10}^{3}$ samples. Fig.4a shows the data distribution when $d=2$. An RBF kernel is ill-suited for this data set since the Euclidean distance used in this kernel fails to correctly capture the data pattern near the boundary [6]. One may need to carefully tune the kernel width to alleviate the inherent inappropriateness between the RBF kernel and the data set.

Fig.4b illustrates the test errors of different methods corresponding to different data dimensions $d\in\{2,4,6,8,...,18,20\}$. Both RFF and OPT-RFF manifest a sharp performance decrease along with the increase of $d$. By contrast, IKL and ML-GRFF both have rather stable performance as the dimension $d$ increases, since they try to learn the kernel distribution via a neural network without any prior kernel function definition. Particularly, by directly optimizing the ERM problem in an end-to-end manner, ML-GRFF characterizes the data pattern much better than the others and achieves the lowest test errors. Fig.4c shows the comparison results on the training and test sets of SL-GRFF and ML-GRFF respectively. In a wide range of data dimensions, ML-GRFF always has an evident superiority of classification errors on the test set over SL-GRFF.

Besides, to visualize the generative RFFs, we take PCA [25] to extract the top-3 principal components of random features in SL-GRFF and different layers of ML-GRFF, shown in Fig.5. SL-GRFF and ML-GRFF are trained on the synthetic data of two dimensions, $d=8$ and $d=24$, respectively. When $d=8$, both SL-GRFF and ML-GRFF have similar performance, while when $d=24$, ML-GRFF performs better than SL-GRFF. For ML-GRFF, the extracted principal components in the 1st layer (see Fig.5b and Fig.5e) do not show any evident linear separability. But, the components in the 2nd layer (see Fig.5c and Fig.5f) follow a clear linear separable distribution. For SL-GRFF, we can also see the linear separability of the extracted components from Fig.5a and Fig.5d, which is obviously weaker than that of the extracted components of the 2nd layer in ML-GRFF. Hence, by going deeper and deeper, ML-GRFF is able to learn a good kernel on features, which results in better performance.

To illustrate the traits of the progressively training strategy, we record the loss and accuracy curves during training on the synthetic data of different dimensions in Fig.6. When the data is easy to be separated, i.e., it is low-dimensional ($d=2$), the whole training process does not show much differences between the two training phases in Fig.6a and Fig.6b. As the dimension increases, there are obvious improvements, i.e., the drop of loss and the step-up of accuracy, from the 1st training phase to the 2nd training phase in Fig.6c $\sim$ Fig.6f, at the turning point of the 200-th epoch. By progressively training the generators layer by layer, the convergence is achieved and there is good performance.

The models are trained on $7$ small-scale data sets and $3$ large-scale data sets. We randomly pick half of the data as the training set, the other half as the test set, except for the data sets of which the training and test sets have already been divided. After normalizing the data to ${[0,1]}^{d}$ in advance by min-max normalization, $20\%$ of the training data are randomly selected as the validation set. For RFF and OPT-RFF, the validation set is adopted to perform validations on a group of 10 $\gamma$-s ranging from $0.5$ to $1.4$ with an interval of $0.1$, where $\gamma$ is the steep hyper-parameter in the RBF kernel: $k(\mathbf{x},\mathbf{x}^{\prime})=\exp(-\gamma||\mathbf{x}-\mathbf{x}^{\prime}||^{2})$. For MLP and ML-GRFF, during training, models that achieve best performance on the partitioned validation set are selected. All the experiments on every data set are repeated 5 times.

Tab.1 and Tab.2 illustrate the training and test accuracy of different methods on the small-scale and large-scale data sets respectively. The sizes of the training and test sets and the data dimensions are also listed in the two tables. One can find that in most cases, ML-GRFF outperforms RFF and OPT-RFF a lot and achieves competitive (sometimes even slightly better) results compared with MLP.

As aforementioned, the promising performance on generalization of the proposed one-stage, end-to-end kernel learning method is empirically validated on both synthetic and real-world data. In the following, we conduct another experiment on adversarial robustness to demonstrate the superiority of our GRFF.