Streaming and Sublinear Approximation of Entropy and Information Distances

Details Streaming and Sublinear Approximation of Entropy and Information Distances Streaming and Sublinear Approximation of Entropy and Information Distances

2005-08-27

arxiv.org/abs/cs/0508122v2

Computer Science

Data Structures and Algorithms

18 pages

Scientific paper

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 $\ell_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 $(\log n)/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.

Affiliated with

Also associated with

No associations

Rating

Streaming and Sublinear Approximation of Entropy and Information Distances does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Streaming and Sublinear Approximation of Entropy and Information Distances, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Streaming and Sublinear Approximation of Entropy and Information Distances will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-187170