2
$\begingroup$

Given a probability distribution $(X,p)$, its entropy is defined as $H=-\sum_{x\in X} p(x)\log p(x)$.

Given a sample of observations $x_n,n=1..N$, one can estimate $p(x)=\frac{\#\{i:x_i=x\}}{N}$ and thus $H$.

Suppose, however, that $X=P(B)$ the power set of set $B$ and the observations are subsets of $B$: $x_n\subset B$ and the number of observations $\#B=k\ll N\ll 2^k=\#P(B)$. E.g., $k=50$ and $N=10^4$.

I.e., there are not enough observations to estimate the probability of every separate subset.

How would I estimate the entropy of the distribution?

E.g., one can define a probability distribution on $B$ as

\begin{align} m(b)&=\sum_{x\ni b}p(x) \\ M &= \sum_{b\in B} m(b) \\ p_B(b) &= \frac{m(b)}{M}. \end{align}

What can be said about entropy of $(X=P(B),p)$ based on the entropy of $(B,p_B)$? (the latter is easy to estimate based on the sample).

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Is it important to the structure of the distribution that the observations are subsets? If we just think of the observations as integers between $1$ and $2^k$, then this sounds very hard: every distribution that is uniform on $\Omega(N^2)$ supports will look the same (no repeated samples), so distinguishing support size of $N^2$ from $2^k$ sounds impossible to me (but their entropies are very far apart). $\endgroup$
    – usul
    Commented Apr 2, 2014 at 19:51
  • $\begingroup$ @usul: yes, it is the critical point $\endgroup$
    – sds
    Commented Apr 2, 2014 at 20:25
  • $\begingroup$ @sds are you saying that every observed count is 1 $\endgroup$
    – guest
    Commented Apr 2, 2014 at 20:27
  • $\begingroup$ @guest: I am saying that the structure of X as the power set is important for applications. $\endgroup$
    – sds
    Commented Apr 2, 2014 at 20:29
  • 1
    $\begingroup$ @sds, then maybe you can make some assumption about the distribution in terms of the subsets. Otherwise it may not be doable.... $\endgroup$
    – usul
    Commented Apr 3, 2014 at 2:17

3 Answers 3

Reset to default
2
$\begingroup$

I don't think the power-set structure helps you estimate entropy better. The following extreme cases all give the same entropy for $p_B$, but entropy of the power set observation ranges from 0 to $N$ (the full range).

  • Extreme case 1, if you only observe $B$, your entropy $H(X)$ is zero, while entropy of $p_B$ is maximum, $\log_2(N)$.
  • Extreme case 2, if you observe $\{1\}, \ldots, \{N\}$ uniformly, entropy is $H(X)=\log_2(N)$, and entropy of $p_B$ is also $\log_2(N)$.
  • Extreme case 3, if you observe all subsets equally likely, entropy $H(X)$ is $N$, while the entropy of $p_B$ is $\log_2(N)$

If entropy of $p_B$ is very small, that might restrict the maximum possible entropy for the power set observation, but I do not see an inequality. Even if there's an inequality, I don't think it can be tight.

As @guest suggested, using generic entropy estimators that perform well in the undersampled regime might be the best bet. @guest suggested my paper (thanks!), here are some more choices.

Improve this answer
$\endgroup$
1
$\begingroup$

This paper explains entropy estimation without distribution estimation in the undersampled regime.

Improve this answer
$\endgroup$
2
  • $\begingroup$ thanks, but the paper does not use the power set structure. $\endgroup$
    – sds
    Commented Apr 2, 2014 at 21:17
  • $\begingroup$ and code for the paper: github.com/pillowlab/PYMentropy $\endgroup$
    – Memming
    Commented Apr 2, 2014 at 23:30
1
$\begingroup$

If you'd rather use a frequentist method (instead of the Bayesian approach described above), then a recent paper (that also reviews the literature on this) is this one.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .