I have a question regarding machine learning and specifically kernel functions. Suppose we have a Kernel function, say $K(x)$, and also another distinct one, say $K'(x)$. I want to know is $K(K'(x))$ a kernel function as well? That is, if one feeds the output of a kernel function to another kernel, what does it mean? does it make sense or not?

Another question is about the expected behavior of linear combination of well-known kernels,such as RBF, polynomial and MLP. Suppose the MLP kernel yields 60% of accuracy in a classification task and RBF yields 85%. Does necessarily the RBF+MLP yield a better accuracy compared to the one resulted by MLP?


Let's go back to the definition of a Kernel. A Kernel is a function $k(x, x')$ such that

$$ k(x, x') = \phi(x)^T\phi(x). $$

for some $\phi$. One consequence of this is that the result of a Kernel applied to two elements from the same set is always a scalar. Thus, you cannot apply another Kernel to it, and can thus not compose Kernels.

I assume that instead you are interested in whether $\phi(\phi'(x))$ induces a proper Kernel. Supposing that the co-domain of $\phi$ and the domain of $\phi'$ match (i.e. you can feed the output of the former into the latter), this is the case.

Why? Because $\phi(\phi'(x))^T\phi(\phi'(x'))$ is a scalar product in the feature space induced by $\phi \cdot \phi'$, which is the definition of a Kernel.

Your second question: No, it might overfit more.

  • 1
    $\begingroup$ One of the problems with using combinations of kernels is that it means you have even more kernel parameters to tune, which means you are even more likely to run into problems with over-fitting the model selection criterion. In my experience, using a combination of kernels will only improve performance if it is based on expert knowledge, and is likely to make performance worse if the combination is selected in a purely data driven way. $\endgroup$ Apr 7 '14 at 14:56
  • $\begingroup$ @bayerj: Yeah that's right, but I'm thinking of K(X) as an operator which yields a kernel matrix not the scalar result, i.e. X is a data set in which each row corresponds to an observation and the output is a matrix containing the inner product for all pairwise observations. So the output of the first K(x) is a kernel matrix which is fed to the second one. According to the literature we can conclude that the combination is kernel because the the kernel matrix resulted from the second kernel has the key properties (symmetric and positive-definite) as well. $\endgroup$
    – Saeed
    Apr 7 '14 at 16:27
  • $\begingroup$ @Dikran Marsupial: what do you exactly mean by "expert knowledge"? You mean that we cannot expect any justifiable behavior about kernel combinations? It seems to be more data-dependent rather than knowledge-dependent, yes? $\endgroup$
    – Saeed
    Apr 7 '14 at 16:37
  • $\begingroup$ I mean that the choice of (combination of) kernel is made to enforce known invariances or to take advantage of regularities in the data that are known to exist a-priori. The problem with learning parameters (including the choice of kernel) from data is that the more parameters you introduce, the more data you will need to estimate the parameters reliably, and the amount rises exponentially in the worst case scenario. However in practice, the kernel is chosen in a completely data-driven way, which if evaluated thoroughly often turns out not to work very well IMHE (in my humble experience ;o). $\endgroup$ Apr 7 '14 at 16:54
  • $\begingroup$ @user3062492 Say $K: \mathbb{R}^{N x D} \rightarrow \mathbb{R}^{N x N}$ maps a data set to a Gram matrix, with $N$ the number of samples and $D$ the data dimensionality. How would you then compose one $K$ with another $K'$? $\endgroup$
    – bayerj
    Apr 7 '14 at 18:59

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.