nips nips2012 nips2012-338 nips2012-338-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Maayan Harel, Shie Mannor
Abstract: We introduce a new discrepancy score between two distributions that gives an indication on their similarity. While much research has been done to determine if two samples come from exactly the same distribution, much less research considered the problem of determining if two finite samples come from similar distributions. The new score gives an intuitive interpretation of similarity; it optimally perturbs the distributions so that they best fit each other. The score is defined between distributions, and can be efficiently estimated from samples. We provide convergence bounds of the estimated score, and develop hypothesis testing procedures that test if two data sets come from similar distributions. The statistical power of this procedures is presented in simulations. We also compare the score’s capacity to detect similarity with that of other known measures on real data. 1
[1] G. Monge. M´ moire sur la th´ orie des d´ blais et de remblais. Histoire de l’Academie Royale e e e des Sciences de Paris, avec les Memoires de Mathematique et de Physique pour la meme annee, 1781.
[2] L. R¨ schendorf. Monge–kantorovich transportation problem and optimal couplings. Jahresu bericht der DMV, 3:113–137, 2007.
[3] A. Schrijver. Theory of linear and integer programming. John Wiley & Sons Inc, 1998.
[4] Y. Rubner, C. Tomasi, and L.J. Guibas. A metric for distributions with applications to image databases. In Computer Vision, 1998. Sixth International Conference on, pages 59–66. IEEE, 1998.
[5] R.K. Ahuja, L. Magnanti, and J.B. Orlin. Network Flows: Theory, Algorithms, and Applications, chapter 12, pages 469–473. Prentice Hall, 1993.
[6] J.H. Friedman and L.C. Rafsky. Multivariate generalizations of the Wald-Wolfowitz and Smirnov two-sample tests. Annals of Statistics, 7:697–717, 1979.
[7] M.F. Schilling. Multivariate two-sample tests based on nearest neighbors. Journal of the American Statistical Association, pages 799–806, 1986.
[8] D. Kifer, S. Ben-David, and J. Gehrke. Detecting change in data streams. In Proceedings of the Thirtieth international conference on Very large data bases, pages 180–191. VLDB Endowment, 2004.
[9] A. Gretton, K. Borgwardt, B. Sch¨ lkopf, M. Rasch, and E. Smola. A kernel method for the o two sample problem. In Advances in Neural Information Processing Systems 19, 2007.
[10] B. Efron and R. Tibshirani. An introduction to the bootstrap, chapter 14, pages 178–188. Chapman & Hall/CRC, 1993.
[11] S. Wellek. Testing Statistical Hypotheses of Equivalence and Noninferiority; 2nd edition. Chapman and Hall/CRC, 2010.
[12] J. Shao, Z. Huang, H. Shen, J. Shen, and X. Zhou. Distribution-based similarity measures for multi-dimensional point set retrieval applications. In Proceeding of the 16th ACM international conference on Multimedia MM 08, 2008.
[13] J. Frank, S. Mannor, and D. Precup. Data sets: Mobile phone gait recognition data, 2010.
[14] S. Boyd and L. Vandenberghe. Convex Optimization, chapter 5, pages 258–261. Cambridge University Press, New York, NY, USA, 2004.
[15] T. Weissman, E. Ordentlich, G. Seroussi, S. Verdu, and M.J. Weinberger. Inequalities for the l1 deviation of the empirical distribution. Hewlett-Packard Labs, Tech. Rep, 2003. 9