Locally Adaptive Nearest Neighbors

When training automated systems, it has been shown to be beneficial to adapt the representation of data by learning a problem-specific metric. We extend this idea and, for the widely used family of k nearest neighbors algorithms, develop a method that allows learning locally adaptive metrics. To demonstrate important aspects of how our approach works, we conduct a number of experiments on synthetic data sets, and we show its usefulness on real-world benchmark data sets. Machine learning models increasingly pervade our daily lives in the form of recommendation systems, computer vision, driver assistance, etc., challenging us to realize seamless cooperation between human and algorithmic agents. One desirable property of predictions made by machine learning models is their transparency, expressed in such a way as a statement about which factors of a given setting have the greatest influence on the decision at hand - in particular, this requirement aligns with the EU General Data Protection Regulations, which include a "right to explanation" [1].