epsilon-Kernel Coresets for Stochastic Points.

Lingxiao Huang, Jian Li, Jeff M. Phillips, Haitao WangESA 2016 · OpenReview

TL;DR

This paper introduces the concept of "epsilon-kernel coresets" for uncertain point data, which are smaller, representative datasets that approximate geometric properties of the original uncertain data. They develop efficient algorithms to construct these coresets for approximating expected width and probability distributions of width, crucial for handling noisy real-world data in geometric optimization.

What Problem Does This Paper Address?

In today's data-rich world, many applications generate data that is not precise but rather probabilistic or uncertain. This uncertainty arises in various forms, such as points that might exist with a certain probability (existential model) or points whose locations are described by probability distributions (locational model). Analyzing and optimizing geometric properties of such uncertain datasets is a significant challenge. Traditional geometric algorithms often assume precise input, making them unsuitable for these scenarios. This paper tackles the problem of creating compact representations (coresets) for uncertain point sets that can efficiently approximate geometric measures like the "width" of the point set in any direction.

Methods

The core contribution is the development of epsilon-kernel coresets for uncertain points. The paper defines two main types of coresets:

  • E-EXP-KERNEL: Approximates the expected directional width of the uncertain point set.
  • (ε, τ)-QUANT-KERNEL: Approximates the probability distribution of the directional width.

The authors explore two models of uncertainty:

  • Existential Uncertainty Model: Each point exists with a probability $p_v$.
  • Locational Uncertainty Model: Each point's location is a random variable.

Key techniques include:

  • Minkowski Sums: Used to relate the expected width of uncertain points to the width of a deterministic convex polytope.
  • VC Dimension and Uniform Convergence: Applied in the analysis of (ε, τ)-QUANT-KERNELS, particularly for handling probability distributions.
  • Random Sampling and Poissonization: Employed to construct coresets, especially for the (ε, τ)-QUANT-KERNEL, by transforming Bernoulli distributions into Poisson distributions.
  • Deterministic Coreset Techniques: Leveraging existing results for deterministic point sets (e.g., from [7]) and adapting them to the stochastic setting.

A significant finding is that while deterministic coresets can often be subsets of the original data, this is not always possible for uncertain data, especially without additional assumptions.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and algorithms for abstract models of uncertain data rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Coresets for Uncertainty are Different: Unlike deterministic settings where coresets are often subsets of the input, for uncertain data, coresets might need to be constructed from deterministic points or have a different structure, especially if a strict subset constraint is imposed.
  • Approximating Expected vs. Distributional Properties: The paper distinguishes between approximating the average behavior (expected width) and approximating the entire range of possibilities (width distribution), requiring different coreset definitions and construction techniques.
  • The Power of Minkowski Sums: The connection between the expected width of uncertain points and the width of a deterministic Minkowski sum polytope provides a crucial theoretical bridge.
  • Poissonization as a Tool: Replacing Bernoulli variables with Poisson variables simplifies analysis and construction, particularly for approximating probability distributions of geometric measures.
  • Trade-offs in Coreset Construction: The paper highlights trade-offs between coreset size, construction time, and whether the coreset points are independent or correlated.

Key Results

  • E-EXP-KERNEL Existence: An E-EXP-KERNEL of size $O(\varepsilon^{-(d-1)/2})$ exists for both existential and locational uncertainty models and can be constructed in nearly linear time.
  • Subset Constraint Difficulty: For general uncertain points, an E-EXP-KERNEL with a subset constraint (i.e., a subset of the original uncertain points) might require a sublinear size, but this is not always possible. However, under a "β-assumption" (lower bound on existential probabilities), such coresets are possible.
  • (ε, τ)-QUANT-KERNEL Construction: A simple algorithm constructs an (ε, τ)-QUANT-KERNEL of size $O(\tau^{-2}\varepsilon^{-(d-1)/2})$ in linear time. Improved constructions for existential models achieve nearly linear time and independent points.
  • Applications: The developed coresets are shown to be applicable to problems like approximating the extent of uncertain functions, maintaining extent measures for stochastic moving points, and various shape-fitting problems (minimum enclosing ball, spherical shell, cylinder, etc.) under uncertainty.

Limitations and Future Work

  • Subset Constraint: The paper explicitly notes that for general uncertain points, an E-EXP-KERNEL that is a subset of the original uncertain points might not exist with sublinear size. This limitation is addressed by the "β-assumption" or by allowing deterministic coresets.
  • Fractional Powers: While the paper introduces (ε, r)-FPOW-KERNELS to handle fractional powers in objective functions (e.g., for minimum spherical shell), it notes that directly using E-EXP-KERNELS for these problems is not straightforward, unlike in the deterministic setting.
  • Future Work: The paper suggests that the techniques developed, particularly the connections to VC theory and Tukey depth, may be useful for other geometric optimization problems in stochastic settings. The application to minimum enclosing ball and spherical shell problems for stochastic points is highlighted as an area where further work is needed, especially for handling fractional powers without the β-assumption.

Summary updated

Abstract

With the dramatic growth in the number of application domains that generate probabilistic, noisy and uncertain data, there has been an increasing interest in designing algorithms for geometric or combinatorial optimization problems over such data. In this paper, we initiate the study of constructing epsilon-kernel coresets for uncertain points. We consider uncertainty in the existential model where each point's location is fixed but only occurs with a certain probability, and the locational model where each point has a probability distribution describing its location. An epsilon-kernel coreset approximates the width of a point set in any direction. We consider approximating the expected width (an epsilon-EXP-KERNEL), as well as the probability distribution on the width (an (epsilon, tau)-QUANT-KERNEL) for any direction. We show that there exists a set of O(epsilon^{-(d-1)/2}) deterministic points which approximate the expected width under the existential and locational models, and we provide efficient algorithms for constructing such coresets. We show, however, it is not always possible to find a subset of the original uncertain points which provides such an approximation. However, if the existential probability of each point is lower bounded by a constant, an epsilon-EXP-KERNEL is still possible. We also provide efficient algorithms for construct an (epsilon, tau)-QUANT-KERNEL coreset in nearly linear time. Our techniques utilize or connect to several important notions in probability and geometry, such as Kolmogorov distances, VC uniform convergence and Tukey depth, and may be useful in other geometric optimization problem in stochastic settings. Finally, combining with known techniques, we show a few applications to approximating the extent of uncertain functions, maintaining extent measures for stochastic moving points and some shape fitting problems under uncertainty.
BibTeX
@inproceedings{huang2016epsilon,
  author = {Lingxiao Huang and Jian Li and Jeff M. Phillips and Haitao Wang},
  title = {{epsilon-Kernel Coresets for Stochastic Points.}},
  booktitle = {ESA},
  year = {2016},
  url = {https://openreview.net/forum?id=NbD4ORym6mj},
}
Figure