Streaming and sublinear approximation of entropy and information distances

DOI10.1145/1109557.1109637MaRDI QIDQ3581507zbMATH OpenOpenAlexFDO

Authors Sudipto Guha, Andrew McGregor, Venkatasubramanian Suresh

Publication date 16 August 2010

Published in Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0508122

Mathematics Subject Classification ID

Randomized algorithms (68W20) Measures of information, entropy (94A17)

Abstract: In many problems in data mining and machine learning, data items that need to be clustered or classified are not points in a high-dimensional space, but are distributions (points on a high dimensional simplex). For distributions, natural measures of distance are not the $el{l}_p$ norms and variants, but information-theoretic measures like the Kullback-Leibler distance, the Hellinger distance, and others. Efficient estimation of these distances is a key component in algorithms for manipulating distributions. Thus, sublinear resource constraints, either in time (property testing) or space (streaming) are crucial. We start by resolving two open questions regarding property testing of distributions. Firstly, we show a tight bound for estimating bounded, symmetric f-divergences between distributions in a general property testing (sublinear time) framework (the so-called combined oracle model). This yields optimal algorithms for estimating such well known distances as the Jensen-Shannon divergence and the Hellinger distance. Secondly, we close a $(logn)/H$ gap between upper and lower bounds for estimating entropy $H$ in this model. In a stream setting (sublinear space), we give the first algorithm for estimating the entropy of a distribution. Our algorithm runs in polylogarithmic space and yields an asymptotic constant factor approximation scheme. We also provide other results along the space/time/approximation tradeoff curve.

Cited in

(14)

• Sketching information divergences
• Hierarchical sampling from sketches: Estimating functions over data streams
• Multiple pass streaming algorithms for learning mixtures of distributions in \(\mathbb R^d\)
• Testing shape restrictions of discrete distributions
• Fast adaptive algorithms for abrupt change detection
• Improved algorithms for distributed entropy monitoring
• An automatic inequality prover and instance optimal identity testing
• Big data on the rise? Testing monotonicity of distributions
• Multiple Pass Streaming Algorithms for Learning Mixtures of Distributions in ${\mathbb R}^d$
• Optimal sampling from sliding windows
• Recovering structured probability matrices
• Lifting uniform learners via distributional decomposition
• Range (Rényi) entropy queries and partitioning
• Range entropy queries and partitioning

This page was built for publication: Streaming and sublinear approximation of entropy and information distances

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581507)