Sign Cauchy Projections and Chi-Square Kernel
The method of stable random projections is useful for efficiently approximating the l α distance (0 < α ≤ 2) in high dimension and it is naturally suitable for data streams. In this paper, we propose to use only the signs of the projected data and we analyze the probability of collision (i.e., when the two signs differ). Interestingly, when α = 1 (i.e., Cauchy random projections), we show that the probability of collision can be accurately approximated as functions of the chi-square (χ 2 ) similarity. In text and vision applications, the χ 2 similarity is a popular measure when the features are generated from histograms (which are a typical example of data streams). Experiments confirm that the proposed method is promising for large-scale learning applications. The full paper is available at arXiv:1308.1009.
There are many future research problems. For example, when α → 0, the collision probability is a function of the resemblance (of the binary-quantized data). This provides an effective mechanism for resemblance estimation in data streams.
This paper proposes to use a signed Cauchy random 
      projection to approximate the chi-square kernel with relatively low 
      errors. The motivation comes from generalizing the Sim-hash algorithm and 
      noting that chi-square is related to the collision probability. 
      Overall, the reviewer finds the finding quite interesting and 
      innovative, as no previous attempts seem to have linked chi-square with 
      random Cauchy projections. The paper is of importance to very 
      high-dimensional sparse approximations of the chi-square, which could find 
      its usage in a lot of text and image applications. One main 
      concern is that the writing is very bad, almost atrociously so. From the 
      beginning it is extremely unclear what is the goal of the paper. The first 
      theorem is almost irrelevant with the rest, as it gives a bound, just to 
      be said not tight. And starting from section 4, the focus has turned to 
      the alpha=1 case where links between the collision probability and the 
      chi-square is proposed, and later proved in the binary case. The logic 
      seems completely reversed and free-flowing, with occasionally theorems 
      that don't lead to anywhere (e.g. Theorem 1, and the approximation (12)). 
      The claims in the conclusion look out-or-order and random (e.g. lines 
      424-427). In general, this looks more like a research memo rather than a 
      rigorous, well-organized paper. Therefore I'm torn on a score between 5 
      and 6 since it looks like this paper should be completely re-written 
      before presented to readers. However, the finding itself is still 
      quite interesting. Lemma 5 is a strong result that established a low error 
      bound on the approximation in binary case. The result that one can 
      approximate cos^{-1}(chi^2) by inner product is new. A less satisfying 
      result is the way chi^2 is approximated, where cos needs to be applied to 
      transform sign(x)* sign(y) so that the approximation is no longer an inner 
      product thus don't enjoy computational savings in large-scale learning. It 
      will be interesting to see whether the approximated cos^{-1}(chi^2) can 
      translate to a linear approximation to the more useful chi2 CDF function, 
      or whether some more theoretical and empirical results can be found for 
      the cos^{-1}(chi^2). Other notes and relevant references: Note 
      that when alpha = 1, the bound in Theorem 1 corresponds to the geodesic 
      distance on the simplex, as defined in Lafferty and Lebanon. 
      Diffusion Kernels on Statistical Manifolds. JMLR 2005. Taking the 
      square root of all the input u, v is known as the Hellinger distance, 
      widely used in both NLP and vision but widely known as inferior to 
      chi-square. Chi-square is very important at least in computer 
      vision, quite a few papers have worked on its approximation. There are 
      some additional references that might be interesting for this topic: 
      Sreekanth, Vedaldi and Zisserman. Generalized RBF feature maps for 
      efficient detection. BMVC 2010 established an approximation for 
      exp-chi2, which has been empirically verified as much better than the chi2 
      kernel in classification accuracy. Also note exp-chi2 resembles the CDF of 
      the chi2 distribution, hence corresponds to the p-value of the chi2-test. 
      Therefore it's more appropriate than the chi2 itself as a comparison 
      metric. Also relevant is a recent arXiv paper provides a linear 
      approximation to chi2 with geometric convergence rate: Li, Lebanon 
      and Sminchisescu. A Linear Approximation to the chi2 Kernel with 
      Geometric Convergence. http://arxiv.org/pdf/1206.4074v3.pdf 
      which presents a formula to approximate each dimension of the chi2 
      kernel with several dimensions with geometric convergence rate. One can in 
      principle construct an approximation of chi2 on very high-dimensional 
      sparse features by doing a standard Gaussian random projection from such 
      an approximation. It would be interesting to compare these two approaches. 
      --------------------------------------------------------------------- 
      Comments on Rebuttal: The point the authors mentioned on 
      the ability for applications in streaming data is correct and interesting, 
      and give some merit to the otherwise unjustified acos(chi2) metric (since 
      it's computable for streams, even if it's not a well-understood metric 
      yet). Therefore I decide to change the score to 6. The main concerns are 
      still 1) Lack of theoretical and/or practical insights of the acos(chi2) 
      kernel. 2) Writing and organization of the paper. Performance 
      comparisons with the arXiv paper would be an interesting side note, but 
      that was not a factor in the score I gave with the initial review. The 
      score came from the above 2 concerns.