Diversity Maximization in the Presence of Outliers

Daichi AmagataAAAI 2023 · DOI

TL;DR

This paper tackles the crucial problem of selecting a diverse subset of data points, a task vital for summarizing large datasets. The key innovation is addressing the challenge of "outliers" – data points that are far from the rest – which can severely skew existing diversity maximization algorithms. The authors propose two novel algorithms that effectively identify and ignore outliers, offering both theoretical guarantees and significant speedups in practice.

What Problem Does This Paper Address?

Imagine you have a massive dataset, say, millions of customer reviews or sensor readings. You want to create a smaller, representative "summary" of this data that captures its diversity. The "diversity maximization" problem aims to select a subset of k points from the original dataset such that these k points are as spread out as possible. This is useful for tasks like data summarization, search result diversification, and building robust machine learning models.

However, real-world datasets are rarely perfect. They often contain "outliers" – data points that are unusually far from the typical data distribution. These outliers can be due to errors, rare events, or simply noise. Standard diversity maximization algorithms, like the popular "furthest point retrieval" (GMM), are highly sensitive to these outliers. If an outlier is picked, it can dominate the selected subset, making the summary unrepresentative and potentially leading to the "garbage in, garbage out" problem for downstream applications. This paper addresses this critical gap by developing methods that can perform diversity maximization even when outliers are present.

Methods

The paper introduces two main algorithms designed to handle outliers:

  • GREEDY: This algorithm leverages the existing GMM algorithm but with a clever twist. It first runs GMM on a slightly larger set of points (k + z, where z is the estimated number of outliers). The intuition is that GMM, being sensitive to outliers, will likely pick them in this larger set. By analyzing the output of this initial GMM run, GREEDY can identify and filter out the most likely outliers. Finally, it runs GMM again on the cleaned data to select the k diverse points. This algorithm offers a guaranteed approximation factor and runs in O((k + z)n) time.
  • CORESET: This algorithm offers a significant speedup by separating the process into offline and online phases. It first constructs a "coreset" – a smaller, representative subset of the data that preserves its diversity properties. This coreset is built using GMM on a small number of points (c, related to z). Once the coreset is built (an offline step), the online algorithm (STREAMING) can quickly find a diverse subset of size k from this coreset. The key advantage is that the online processing time becomes independent of the original dataset size (n), running in O(kz) time. This algorithm provides a good approximation with a high probability of success.

Datasets

The authors evaluated their algorithms on four real-world datasets:

  • FCT: Forest cover type data (10-dimensional).
  • Household: Sensor readings (7-dimensional).
  • KDD99: Network packet records (16-dimensional).
  • Mirai: Mirai malware infected network capture data (115-dimensional).

These datasets were normalized to have a consistent scale, and z outliers were artificially injected to simulate real-world scenarios, following practices from previous outlier detection studies. Euclidean distance was used as the metric.

Key Insights and Ideas

  • Outliers are a major problem for existing methods: The paper convincingly demonstrates (with examples and experimental results) that standard diversity maximization algorithms fail when outliers are present, producing unrepresentative results.
  • Leveraging outlier sensitivity: Instead of trying to make algorithms robust to outliers directly, the GREEDY algorithm cleverly uses the sensitivity of GMM to outliers to identify them.
  • The power of coresets for speed: The CORESET algorithm highlights how pre-processing data into a smaller coreset can dramatically speed up online queries, making diversity maximization practical for extremely large datasets.
  • Theoretical guarantees matter: The paper provides both theoretical approximation guarantees and practical performance improvements, bridging the gap between theory and application.

Key Results

  • GREEDY: Achieves a ½-approximation guarantee and effectively removes outliers. It is significantly faster than a naive baseline approach that also tries to remove outliers.
  • CORESET: Offers a 6(1+ε)-approximation guarantee with a high probability of success. Its most striking result is its speed: CORESET is orders of magnitude faster than the baseline algorithm (up to 67,000 times faster on some datasets), with its running time independent of the original dataset size n.
  • Experimental validation: The proposed algorithms consistently outperform the baseline in terms of speed while maintaining competitive diversity scores (div(S)) across various datasets and parameter settings (k and z). The experiments also show that the diversity of the selected subsets is robust to the number of injected outliers.

Limitations and Future Work

  • Outlier definition: The paper relies on specific assumptions about how outliers are defined (e.g., being significantly further from other points than inliers). Extending the algorithms to handle different outlier definitions is a direction for future work.
  • Fairness constraints: The authors acknowledge that in many real-world scenarios, diversity maximization needs to be combined with fairness constraints (e.g., ensuring representation across different demographic groups). This is identified as an open research problem.
  • Coreset size: While CORESET is very fast, its performance depends on the size of the coreset, which is related to the number of outliers z. The paper notes that if z is very small, the coreset size might increase, impacting performance, though the guarantee still holds.

Summary updated

BibTeX
@inproceedings{amagata2023diversity,
  author = {Daichi Amagata},
  title = {{Diversity Maximization in the Presence of Outliers}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i10.26454},
}
Figure