1
$\begingroup$

The $\chi^2$ distance function is defined as

$$ \chi(u,v) = \sum_{i=1}^n \frac{(u_i-v_i)^2}{u_i+v_i} $$

and the $\chi^2$ kernel function, used in support vector machines, is $$ K(u,v) = \exp(-c \chi(u,v) ) $$ for some hyperparameter $c$.

This distance function and kernel are most commonly used to compare the similarities between two histogram samples, e.g. in bag-of-words or bag-of-feature applications.

The name suggests some connection with either the $\chi^2$ distribution, or the $\chi^2$ Pearson test. The closest I can get is that the $\chi^2$ distance is trying to approximate $$ \sum_{i=1}^k \frac{(O_i-E_i)^2}{E_i} $$

where $O_i$ is the number of observed samples in bin $i$ and $E_i$ is the expected number of samples in bin $i$. But, to say that this quantity asymptotically approaches a $\chi^2$ distribution with degree $k-1$, it doesn't seem connected to the distance function or kernel application that much.

Question: What is the connection between the $\chi^2$ distance function, or kernel application, to the $\chi^2$ distribution, especially for degree higher than 1 (and the PDF is not an exponential decay)? Or is there none and it's just a naming idiosyncrasy? Any sources is also appreciated Thank you!

$\endgroup$
1
$\begingroup$

The distance metric is usually attributed to either LeCam or I. Vincze. The reason why people started calling it $\chi^2$ is that it can be seen as "symmetrized Pearson", see this excerpt from On Measures of Entropy and Information, Tech. Note 009 v0.7, http://threeplusone.com/info , Gavin E. Crooks,2018-09-22:

enter image description here

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Interesting! But I still think it's odd because Pearson said this distance is $\chi^2$ for i.i.d. data. But this distance is not intrinsically a $\chi^2$ distance. Oh well... $\endgroup$ – Y. S. Jun 9 at 9:45
  • 2
    $\begingroup$ chi square test statistics has been used as a metric to express difference between distributions long before either LeCam or Vincze $\endgroup$ – carlo Jun 9 at 11:18
  • 1
    $\begingroup$ @Y.S. similarity is in the form to $\chi^2$ distribution, the form ended up to be useful outside its first intended purpose it seems $\endgroup$ – Aksakal Jun 9 at 12:58
1
$\begingroup$

I think it originated from [1], it seems inspired by the $\chi^2$ distance as you said, but it does not have any theoretical motivation.

The average between each feature is used as their expected value. Therefore,

$$ D(x, y) = \sum_i \frac{(x_i - \mu_i)^2 }{\mu_i} $$

where $$ \mu_i = \frac{x_i + y_i}{2} $$

such that $$ D(x, y) = 2 \sum_i \frac{\left(x_i - \frac{x_i + y_i}{2}\right)^2}{x_i + y_i} \\ = \frac{2}{4} \sum_i \frac{(2 x_i - x_i - y_i)^2}{x_i + y_i} \\ = \frac{1}{2} \sum_i \frac{(x_i - y_i)^2}{x_i + y_i} $$

The use with the RBF kernel is seen in [2], but no explanation is given besides that D(x, y) is a metric.

[1] Puzicha, J., Hofmann, T., & Buhmann, J. M. (1997, June). Non-parametric similarity measures for unsupervised texture segmentation and image retrieval. In Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition (pp. 267-272). IEEE.

[2] Vedaldi, A., & Zisserman, A. (2012). Efficient additive kernels via explicit feature maps. IEEE transactions on pattern analysis and machine intelligence, 34(3), 480-492.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I think the papers cited in the previous post are older, but these calculations are very clarifying! It seems like, in summary, it's a bit of a historical idiosyncrasy but doesn't imply the distance metric intrinsically has much to do with the $\chi^2$ distribution $\endgroup$ – Y. S. Jun 9 at 9:46

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.