jmlr jmlr2013 jmlr2013-79 jmlr2013-79-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Arnaud Guyader, Nick Hengartner
Abstract: Motivated by promising experimental results, this paper investigates the theoretical properties of a recently proposed nonparametric estimator, called the Mutual Nearest Neighbors rule, which estimates the regression function m(x) = E[Y |X = x] as follows: first identify the k nearest neighbors of x in the sample Dn , then keep only those for which x is itself one of the k nearest neighbors, and finally take the average over the corresponding response variables. We prove that this estimator is consistent and that its rate of convergence is optimal. Since the estimate with the optimal rate of convergence depends on the unknown distribution of the observations, we also present adaptation results by data-splitting. Keywords: nonparametric estimation, nearest neighbor methods, mathematical statistics
L. Ambrosio and P. Tilli. Topics on Analysis in Metric Spaces. Oxford University Press, Oxford, 2004. L. Ambrosio, M. Miranda, Jr., and D. Pallara. Special functions of bounded variation in doubling metric measure spaces. In Calculus of Variations: Topics from the Mathematical Heritage of E. De Giorgi, volume 14 of Quad. Mat., pages 1–45. Dept. Math., Seconda Univ. Napoli, Caserta, 2004. G. Biau and L. Devroye. On the layered nearest neighbour estimate, the bagged nearest neighbour estimate and the random forest method in regression and classification. Journal of Multivariate Analysis, 101(10):2499–2518, 2010. G. Biau, F. C´ rou, and A. Guyader. On the rate of convergence of the bagged nearest neighbor e estimate. Journal of Machine Learning Research (JMLR), 11:687–712, 2010. G. Biau, L. Devroye, V. Dujmovi´ , and A. Krzy˙ ak. An affine invariant k-nearest neighbor regresc z sion estimate. Journal of Multivariate Analysis, 112:24–34, 2012. F. C´ rou and A. Guyader. Nearest neighbor classification in infinite dimension. ESAIM: Probability e and Statistics, 10:340–355, 2006. K. Chidananda Gowda and G. Krishna. Agglomerative clustering using the concept of mutual nearest neighbourhood. Pattern Recognition, 10(2):105–112, 1978. 2374 M UTUAL N EAREST N EIGHBORS E STIMATE K. Chidananda Gowda and G. Krishna. The condensed nearest neighbor rule using the concept of mutual nearest neighborhood. IEEE Transactions on Information Theory, 25(4), 1979. L. Devroye. Necessary and sufficient conditions for the pointwise convergence of nearest neighbor regression function estimates. Zeitschrift f¨ r Wahrscheinlichkeitstheorie und Verwandte Gebiete, u 61(4):467–481, 1982. L. Devroye, L. Gy¨ rfi, and G. Lugosi. A Probabilistic Theory of Pattern Recognition. Springero Verlag, New York, 1996. E. Fix and J.L. Hodges. Discriminatory analysis, non-parametric discrimination: consistency properties. Technical report, USAF school of aviation and medicine, Randolph Field, 1951. E. Fix and J.L. Hodges. Discriminatory analysis: Small sample performance. Technical report, USAF school of aviation and medicine, Randolph Field, 1952. L. Gy¨ rfi, M. Kohler, A. Krzy˙ ak, and H. Walk. A Distribution-Free Theory of Nonparametric o z Regression. Springer-Verlag, New York, 2002. J. Heinonen. Lectures on Analysis on Metric Spaces. Universitext. Springer-Verlag, New York, 2001. I.A. Ibragimov and R.Z. Khasminskii. Nonparametric regression estimation. Doklady Akademii Nauk SSSR, 252(4):780–784, 1980. I.A. Ibragimov and R.Z. Khasminskii. Statistical Estimation: Asymptotic Theory. Springer-Verlag, New York, 1981. I.A. Ibragimov and R.Z. Khasminskii. Bounds for the quality of nonparametric estimation of regression. Akademiya Nauk SSSR. Teoriya Veroyatnoste˘ i ee Primeneniya, 27(1):81–94, 1982. ı H. J´ gou, C. Schmid, H. Harzallah, and J. Verbeek. Accurate image search using the contextual e dissimilarity measure. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(1): 2–11, 2010. S. Kpotufe. k-NN regression adapts to local intrinsic dimension. In NIPS Proceedings, pages 729– 737, 2011. E. Liiti¨ inen, F. Corona, and A. Lendasse. Residual variance estimation using a nearest neighbor a statistic. Journal of Multivariate Analysis, 101(4):811–823, 2010. H. Liu, S. Zhang, J. Zhao, X. Zhao, and Y. Mo. A new classification algorithm using mutual nearest neighbors. In Conference on Grid and Cloud Computing, pages 52–57, 2010. D. Qin, S. Gammeter, L. Bossard, T. Quack, and L.J. Van Gool. Hello neighbor: accurate object retrieval with k-reciprocal nearest neighbors. In Computer Vision and Pattern Recognition, pages 777–784, 2011. M. Radovanovi´ , A. Nanopoulos, and M. Ivanovi´ . Hubs in space: popular nearest neighbors in c c high-dimensional data. Journal of Machine Learning Research (JMLR), 11:2487–2531, 2010. 2375 G UYADER AND H ENGARTNER C.J. Stone. Consistent nonparametric regression. The Annals of Statistics, 5(4):595–645, 1977. C.J. Stone. Optimal rates of convergence for nonparametric estimators. The Annals of Statistics, 8 (6):1348–1360, 1980. C.J. Stone. Optimal global rates of convergence for nonparametric regression. The Annals of Statistics, 10(4):1040–1053, 1982. 2376