Data normalization for RBF kernel

Question

I have a matrix of values where rows are individuals and columns are attributes. I want to extract a similarity value for every pair of individuals, and I use an rbf kernel: $$k(x_i,x_j) = \exp\left(-\gamma\|x_i-x_j\|^2\right),$$ where $\gamma = \frac{1}{(2\sigma)^2}$.

Since any attribute has its own range, I suppose that a normalization step is necessary to get a sound similarity value.

I divided each value in column (attribute) $i$ by the norm of column $i$, but now as output from the RBF kernel I get values very near to $1$, and I should use a very "high" $\gamma$ value ($\approx$ 500) to spread out the similarity values between $0$ (not similar) and $1$ (similar).

Is this kind of data normalization "sound" for RBF kernel?

Should I normalize the rows (individuals) rather than the columns (attributes)?

Answer 1

As you can see in the formula, RBF uses Euclidean distance along its calculations. Do you have any reasons to believe that Euclidean distance accurately captures notion of a distance in the data space? I doubt that.

There are several reasons Euclidean distance is not as good as we'd like it to be:

1. Different features may have different scales. If one feature is, say, distance from one city to another in meters, and the other one is height of an object in meters, then clearly the first one would affect the distance much more than the later one.

2. Features may be correlated. Suppose an extreme case when one features is replicated several times (that means it has correlation of 1 with copies): $(x, y, y, y, y) \in \mathbb{R}^5$. This is essentially $\mathbb{R}^2$ space "embedded" into $\mathbb{R}^5$. So, according to the $\mathbb{R}^5$-distance $(2, 0, 0, 0, 0)$ is closer to the origin $(0, 0, 0, 0, 0)$, than $(0, 1, 1, 1, 1)$. But in $\mathbb{R}^2$ it'd be the other way round!

So how can you normalize your data to address there issues? The answer is whitening. Basically, you transform your data by linear transformation $M$ so that resultant covariance matrix is an identity matrix:

$$ I = \mathbb{E}[(M X) (M X)^T] = M \mathbb{E}[X X^T] M^T \Rightarrow M^{-1} M^{-T} = \mathbb{E}[X X^T] $$

Covariance matrix is symmetric, so we might expect $M$ to be symmetric as well, thus having

$$ M^{-2} = \mathbb{E}[X X^T] \Rightarrow M = \mathbb{E}[X X^T]^{-1/2} $$

P.S. Of course, you'd like to center your data first.

Answer 2

Your normalization sounds fine. It is perfectly possible that you need large values of $\gamma$ before you get good results ($\gamma$ must be tuned). The simplest and most common approach is to scale all features to $[0, 1]$ or $[-1, 1]$, for instance by dividing column-wise by the maximum absolute value.

Normalizing rows is usually not a good idea, though it works well for some applications (for instance computer vision). You should focus on normalizing columns.

PS: I assume by high values of $\gamma$ you mean high absolute values, because $\gamma$ should always be negative, unless you meant $\kappa(x_i,x_j) = \exp(-\gamma \|x_i-x_j\|^2)$ (note the minus sign).