Online Adaptive Mahalanobis Distance Estimation
Mahalanobis metrics are widely used in machine learning in conjunction with methods like $k$-nearest neighbors, $k$-means clustering, and $k$-medians clustering. Despite their importance, there has not been any prior work on applying sketching techniques to speed up algorithms for Mahalanobis metrics. In this paper, we initiate the study of dimension reduction for Mahalanobis metrics. In particular, we provide efficient data structures for solving the Approximate Distance Estimation (ADE) problem for Mahalanobis distances. We first provide a randomized Monte Carlo data structure. Then, we show how we can adapt it to provide our main data structure which can handle sequences of \textit{adaptive} queries and also online updates to both the Mahalanobis metric matrix and the data points, making it amenable to be used in conjunction with prior algorithms for online learning of Mahalanobis metrics.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringDimensionality ReductionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Infinite-dimensional Mahalanobis Distance with Applications to Kernelized Novelty Detection
The Mahalanobis distance is a classical tool used to measure the covariance-adjusted distance between points in $\bbR^d$. In this work, we extend the concept of Mahalanobis distance to separable Banach spaces by reinterp…
Anomaly DetectionNovelty DetectionSemi-supervised Anomaly DetectionSupervised Anomaly Detection+2Mahalanonbis Distance Informed by Clustering
A fundamental question in data analysis, machine learning and signal processing is how to compare between data points. The choice of the distance metric is specifically challenging for high-dimensional data sets, where t…
ClusteringMahalanobis Distance Metric Learning Algorithm for Instance-based Data Stream Classification
With the massive data challenges nowadays and the rapid growing of technology, stream mining has recently received considerable attention. To address the large number of scenarios in which this phenomenon manifests itsel…
ClassificationDrift DetectionGeneral ClassificationMetric LearningMahalanobis distance-based robust approaches against false data injection attacks on dynamic power state estimation
Many researchers have studied false data injection (FDI) attacks in power state estimation, but existing state estimation approaches are still highly vulnerable to FDI attacks. In this paper, we investigate the problem o…
State EstimationEfficient Minimax Strategies for Square Loss Games
We consider online prediction problems where the loss between the prediction and the outcome is measured by the squared Euclidean distance and its generalization, the squared Mahalanobis distance. We derive the minimax s…
Density EstimationPrediction