In the paper

Rahimi, Ali, and Benjamin Recht. "Random features for large-scale kernel machines." Advances in neural information processing systems. 2008.

the author introduces a way to approximate stationary kernel function by a way of random sampling in the feature space. The author did an experiment to solve the following ridge regression

$$ \min_{w} ||Z'w - y||_2^2 + \lambda ||w||_2^2 $$

where $w$ would be a vector of $D$ dimension.

The dimension of $w$ does not make sense to me. In order to approximate the kernel function with sufficient accuracy, we need to use a high number of $D$. It gives me a feeling of a high risk of overfitting the model and my model is appeared to be overfitting when I am trying to make use of it.

A kernel ridge regression can be described by the following equation:

$$ f(x) = \sum_{i=1}^N \alpha_i k(x,x_i) $$

for $\alpha_i$ is computed by $\alpha = (K + \sigma^2 I)^{-1} y$.

In the paper, the author is trying to approximate $k(x,y)$ as

$$ \begin{array} \\ k(x,y) & = k(x-y) \\ & \approx \operatorname{E}(z(x)'z(y)) \\ & = \displaystyle \frac{1}{D} \sum_{j=0}^{D} z_{\omega_j}(x)z_{\omega_j}(y) \\ & \mbox{ for }\omega_j\mbox{ draw from }p(\omega)\\ \end{array} $$

Isn't the true approximation to the kernel machine should be

  1. For each data points $x_i$, $x_j$:
  2. Compute $K_{ij} = k(x_i,x_j) \approx \frac{1}{D} \sum_{k=0}^{D} z_{\omega_k}(x_i)'z_{\omega_k}(x_j)$
  3. Solve $(K + \sigma^2I)^{-1} y$

rather than sampling $D$ numbers of $z_\omega(x)$ and then fit a parametric model with $D$ parameters?

I think the author is trying to fit a linear model in the feature space (as $z(x)$ is the feature map) rather than the standard kernel trick which does not need to evaluate the feature map. But I don't understand why the author do not need to compute the sample average of $K$ (or do something similar to $z$)?

The implementation here is also fitting a model of $D$ parameter, no averaging step is done, which makes me quite confusing.

Let's say there are 1000 data points and the feature space is of infinite dimension and requires $D=10000$ to approximate $K$ with sufficient accuracy, am I going to fit 10000 parameters over 1000 data points?

What am I missing?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.