7
$\begingroup$

Originally posted in stats.SE but never got an answer so reposting here.

Is it ever a bad idea to normalise the kernel matrix? By this I mean the method described on page 113 of Shawe-Taylor & Cristianini's "Kernel Methods for Pattern Analysis" (matlab notation):

% original kernel matrix stored in variable K
% output uses the same variable K
% D is a diagonal matrix storing the inverse of the norms
D = diag(1./sqrt(diag(K)));
K = D * K * D;

I'm specifically thinking of text mining, where the kernel is formed from the $tf-idf$ matrix $T$ (i.e. $K = T T'$). The reason I'd like to normalise is that I'm thinking of combining several of such kernels (e.g. from bigrams, trigrams etc.) but I'm getting some really weird results when I do.

Summing the kernels without normalisation results in one or the other dominating. (I could use a weighted sum - such as using $1/||K||_F$ where $||\cdot||_F$ is the Frobenius norm but this seems a bit of a hack - this is unsupervised learning).

$\endgroup$

1 Answer 1

5
$\begingroup$

As long as you understand what you're doing you'll be fine :-)

You're actually normalizing your data to have unit length in feature space. It is equivalent to use this kernel: $K(x,y)/\sqrt{K(x,x)K(y,y)}$. Your data will now fall on a hypersphere of radius 1 in feature space. When you add kernel matrices you're actually "concatenating" feature (not exactly true for all kernels but is is a way to think about it). However in the normalized case the new features will fall on a hypersphere of bounded, known radius.

Could it hurt?

Sure, does the actual value of the feature tell you anything? Consider the case of (normalized) linear kernel [10,10] is a sure 1 and [20,20] is a sure -1 then doing normalization would not be a good idea for your data using this kernel.

This paper a paper about these type of issues.

$\endgroup$
3
  • $\begingroup$ nice reference - not seen that one before $\endgroup$
    – tdc
    Feb 19, 2012 at 9:43
  • $\begingroup$ This is interesting. Is it easy to see that the normalized kernel is a kernel? And is this related to the normalization that people do in spectral clustering? $\endgroup$
    – yeewhye
    Feb 19, 2012 at 13:56
  • $\begingroup$ I think it is straight forward. If K(x,y) is a valid dot product (it is \gamma(x)\cdot \gamma(y) in some space), $K(x,y)/\sqrt{K(x,x)K(y,y)}$ is the dot product in the following mapping \theta(x)=\gamma(x)/||\gamma(x)|| $\endgroup$
    – carlosdc
    Feb 19, 2012 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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