Similarity Function Tracking using Pairwise Comparisons

Kristjan H. Greenewald, Stephen Kelley, Brandon Oselio, Alfred O. Hero Iii

Abstract

Distance Metric Learning (DML) is fundamental for similarity-based algorithms, yet most existing methods assume a stationary data distribution. This paper introduces OCELAD, a framework designed to track evolving distance metrics in real-time. By employing an ensemble of online learners operating across multiple dyadic time scales, OCELAD adaptively weights models to handle both sudden concept shifts and gradual drifts. Experimental results on synthetic and real-world Twitter datasets show that OCELAD significantly outperforms traditional batch and online DML approaches in dynamic environments.

Introduction

Machine learning tasks such as k-Nearest Neighbors (k-NN) and K-means clustering rely heavily on a distance metric to quantify similarity. Distance Metric Learning (DML) typically aims to learn a Mahalanobis metric that satisfies pairwise constraints (e.g., "must-link" or "cannot-link"). However, in many real-world applications like social media analysis, the underlying relationships between data points are nonstationary. A fixed learning rate in online DML often leads to a trade-off: it is either too slow to adapt to sudden changes or too unstable during periods of slow drift.

Methodology

The proposed framework consists of two hierarchical layers:

  1. Retro-Initialized COMID Ensemble (RICE): This layer maintains multiple parallel learners using Composite Objective Mirror Descent (COMID). Each learner is assigned a specific learning rate corresponding to a dyadic time interval. To prevent "cold start" issues, new learners are retro-initialized with the state of existing high-performing learners.
  2. Online Convex Ensemble StrongLy Adaptive Dynamic Learning (OCELAD): This management layer adaptively weights the outputs of the RICE learners. By monitoring the regret of each "worker," OCELAD shifts focus toward faster learners during rapid shifts and toward slower, more precise learners during stable periods.
The multi-scale ensemble architecture of RICE-OCELAD.

This architecture provides strongly adaptive dynamic regret guarantees, ensuring robust performance over any sub-interval of the data stream regardless of how the underlying metric drifts.

Experimental Evaluation

The authors evaluated the framework using two primary benchmarks: synthetic nonstationary data and a real-world Twitter dataset.

Synthetic Performance

A 25-dimensional dataset was constructed with two competing 3-way clusterings in orthogonal subspaces. The ground truth similarity switched between these subspaces and underwent rotational drift at various speeds.

Performance comparison of RICE-OCELAD against baselines under varying drift conditions.

As shown in the performance plots, OCELAD maintains a consistently low k-NN error rate and high Normalized Mutual Information (NMI) for clustering, even as the drift rate fluctuates. In contrast, standard online methods like ITML or batch methods like LMNN fail to adapt or recover slowly from shifts.

Twitter Political Sentiment

The model was applied to 13,600 pairwise comparisons from political tweets during the 2016 US primaries. Using 194-dimensional TF-IDF vectors, OCELAD achieved a 7.8% Leave-One-Out k-NN error rate, a dramatic improvement over the 60.6% error rate seen with standard PCA. The algorithm successfully tracked the shifting relevance of keywords (e.g., "Benghazi", "Mizzou") as they became pivotal for distinguishing political groups during specific news cycles.

Conclusion

OCELAD offers a robust solution for tracking similarity functions in real-time without manual parameter tuning. While currently limited to linear Mahalanobis metrics, the multi-scale ensemble approach demonstrates clear advantages in handling nonstationary data. Future work includes extending the framework to non-linear metrics and incorporating active learning to reduce the reliance on labeled pairwise comparisons.

Summary updated

Abstract

Recent work in distance metric learning has focused on learning transformations of data that best align with specified pairwise similarity and dissimilarity constraints, often supplied by a human observer. The learned transformations lead to improved retrieval, classification, and clustering algorithms due to the better adapted distance or similarity measures. Here, we address the problem of learning these transformations when the underlying constraint generation process is nonstationary. This nonstationarity can be due to changes in either the ground-truth clustering used to generate constraints or changes in the feature subspaces in which the class structure is apparent. We propose Online Convex Ensemble StrongLy Adaptive Dynamic Learning (OCELAD), a general adaptive, online approach for learning and tracking optimal metrics as they change over time that is highly robust to a variety of nonstationary behaviors in the changing metric. We apply the OCELAD framework to an ensemble of online learners. Specifically, we create a retro-initialized composite objective mirror descent (COMID) ensemble (RICE) consisting of a set of parallel COMID learners with different learning rates, and demonstrate parameter-free RICE-OCELAD metric learning on both synthetic data and a highly nonstationary Twitter dataset. We show significant performance improvements and increased robustness to nonstationary effects relative to previously proposed batch and online distance metric learning algorithms.
BibTeX
@article{greenewald2017similarity,
  author = {Kristjan H. Greenewald and Stephen Kelley and Brandon Oselio and Alfred O. Hero III},
  title = {{Similarity Function Tracking using Pairwise Comparisons}},
  journal = {IEEE Trans. Signal Process.},
  year = {2017},
  doi = {10.1109/tsp.2017.2739100},
}
Figure