The theoretical study for nearest neighbor (NN) information goes back to T. Cover and P. Hart’s work in the 1960s connecting the NN information to the underlying probability density functions. The predictions from this theoretical approach are very powerful in a many-data situation, while the empirical study in general does not show the prediction even with many data.
In this talk, I will introduce how the powerful prediction for NN classification can be achieved through metric learning which is directly derived from the T. Cover’s work. I will first show how the learned metric in this work is fundamentally different from conventionally learned metric. In several contemporary machine learning problems, the proposed method can be widely applied achieving state-of-the-art performances, while the conventional metric learning algorithms do not make good performances. In addition, I will show how our understanding of the theoretical properties of NNs can be used to develop optimal strategies for NN classification. Well-known heuristics such as the majority voting in k-NN classification can be explained and exploited in this theoretical context.
Finally, I will show how all of these understandings of NN behavior can motivate better usages of other nonparametric methods such as kernel Nadaraya-Watson estimator.
Dr. Yung-Kyun Noh is currently a BK assistant professor in the department of Mechanical and Aerospace Engineering at Seoul National University (SNU). His research interests are metric learning and dimensionality reduction in machine learning, and he is especially interested in applying statistical theory of nearest neighbors to real and large datasets. He received his B.S. in Physics from POSTECH and his Ph.D. in Computer Science from Interdisciplinary Program in Cognitive Science at SNU. He was a postdoctoral fellow in the same department he is now affiliated with at SNU and a research professor in the department of Computer Science at KAIST. He was a visiting scholar in the Sugiyama Lab at the Tokyo Institute of Technology and worked with Prof. Masashi Sugiyama and in the GRASP Robotics Laboratory at the University of Pennsylvania where he worked with Prof. Daniel D. Lee.