Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

After a quick internet search I found no method for incremental entropy computation.

Question 1

Let $\{x_i\}_{i=1}^n$ and $\{x_i\}_{i=1+n}^{n+m}$ be two samples and let $S_i^j:=\sum_{k=i}^j x_k$. Define entropy $$H_i^j:=-\sum_{k=i}^j\frac{x_k}{S_i^j}\log_2\frac{x_k}{S_i^j}.$$ Is there an algorithm --- computationally cheaper than complete recomputation --- to compute $H_1^{n+m}$ using only $H_1^n$ and $H_{n+1}^{m+n}$ or similar statistics?

Question 2

Is there an algorithm to incrementally compute entropy as new numbers $x_i$ come in, much like there's such an algorithm for variance?

share|improve this question
1  
As a general remark, it’s important to take into account problems with entropy estimation for finite strings – eg. researchspace.auckland.ac.nz/bitstream/handle/2292/3774/… –  Waldemar Jul 1 '13 at 10:18
    
Thanks for the comment. I came across the problem as posed in the question when dealing with incremental decision tree learning where one usually uses entropy as the impurity measure. –  blazs Jul 3 '13 at 15:41
    
Also, it would be nice to have such formulae for conditional entropy; user `shna' asked this question some time ago here. –  blazs Jul 3 '13 at 15:44

3 Answers 3

up vote 2 down vote accepted

Using Andre's identitiy, I derived more general formulas (and algorithms). I made the note with derivations available on arXiv. Comments are more than welcome.

For convenience I also give proofs of (some of) the results here.

Lemma. Let $\{x_i\}_{i=1}^n$ be a sample of positive real numbers $x_i>0$, let $S_n:=x_1+x_2+\ldots+x_n$ be the sum of sample elements, and let $H_n:=-\sum_{i=1}^n\frac{x_i}{S_n}\log_2\frac{x_i}{S_n}$ be the sample entropy. For any positive real number $R>0$ we have $$-\sum_{i=1}^n\frac{x_i}{R+S_n}\log_2\frac{x_i}{R+S_n}=\frac{S_n}{R+S_n}H_n-\frac{S_n}{R+S_n}\log_2\frac{S_n}{R+S_n}.$$ Proof. To see this notice that $\frac{x_i}{R+S_n}=1\cdot\frac{x_i}{R+S_n}=\frac{S_n}{S_n}\frac{x_i}{R+S_n}=\frac{x_i}{S_n}\frac{S_n}{R+S_n}.$ The lemma follows by plugging this into $-\sum_{i=1}^n\frac{x_i}{R+S_n}\log_2\frac{x_i}{R+S_n}$ and doing some algebra.

Now we can prove Andre's claim.

Claim. Let $\{x_i\}_{i=1}^n$ be a sample and $H_n$ and $S_n$ be the sample entropy and the sum of the sample elements, respectively. Suppose new element $x_{n+1}$ ``comes in''. Then we have $$H_{n+1}=\frac{S_n}{S_{n+1}}H_n-\frac{S_n}{S_{n+1}}\log_2\frac{S_n}{S_{n+1}}-\frac{x_{n+1}}{S_{n+1}}\log_2\frac{x_{n+1}}{S_{n+1}}.$$ Proof. Clearly, we have $$H_{n+1}=-\sum_{i=1}^{n+1}\frac{x_i}{S_{n+1}}\log_2\frac{x_i}{S_{n+1}}=-\sum_{i=1}^{n}\frac{x_i}{S_{n+1}}\log_2\frac{x_i}{S_{n+1}}-\frac{x_{n+1}}{S_{n+1}}\log_2\frac{x_{n+1}}{S_{n+1}}.$$ Claim follows by applying the lemma.

Theorem 1. Let $\{x_i\}_{i=1}^n$ and $\{y_i\}_{i=1}^m$ be two samples of positive real numbers and let $H_n$ and $S_n$ and $H_m$ and $S_m$ be the corresponding sample entropies and sums of sample elements, respectively. Let $z_i:=x_i$ for $1\le i\le n$ and $z_i:=y_{i-n}$ for $n+1\le i\le n+m$, i.e., define $z_i$ as the ''sample union''. Let $Z_{n+m}:=S_n+S_m$ and let $H_{n+m}$ be the entropy of the ``sample union''. Then we have $$H_{n+m}=\frac{S_n}{Z_{n+m}}H_n-\frac{S_n}{Z_{n+m}}\log_2\frac{S_n}{Z_{n+m}}+\frac{S_m}{Z_{n+m}}H_m-\frac{S_m}{Z_{n+m}}\log_2\frac{S_m}{Z_{n+m}}.$$ Proof. As in the previous proof, write $$H_{n+m}=-\sum_{i=1}^{n+m}\frac{z_i}{Z_{n+m}}\log_2\frac{z_i}{Z_{n+m}}=-\sum_{i=1}^n\frac{x_i}{Z_{n+m}}\log_2\frac{x_i}{Z_{n+m}}-\sum_{i=1}^m\frac{y_i}{Z_{n+m}}\log_2\frac{y_i}{Z_{n+m}}.$$ The theorem follows by applying the lemma twice.

Theorem 2. Let $\{x_i\}_{i=1}^n$ be a sample of positive real numbers, and let $S_n$ and $H_n$ the sum of sample elements and sample entropy, respectively. Suppose elements $x_{i_j}$ increase by $r_j>0$ for $1\le j\le k<n$. Let $r:=r_1+r_2+\ldots+r_k$. Then the entropy becomes $$\frac{S_n}{S_n+r}H_n-\frac{S_n}{S_n+r}\log_2\frac{S_n}{S_n+r}-\sum_{j=1}^k\left(\frac{x_{i_j}+r_j}{S_n+r}\log_2\frac{x_{i_j}+r_j}{S_n+r}-\frac{x_{i_j}}{S_n}\log_2\frac{x_{i_j}}{S_n}\right).$$ Proof. The idea is to substract the old therms and apply the lemma for the new terms.

share|improve this answer

Regarding Question 2: By omitting the index $i$ in your notation, it holds the identity $$ H^{N+1} = \frac{S^N}{S^{N+1}} H^{N} - \frac{S^N}{S^{N+1}} \log \frac{S^N}{S^{N+1}} - \frac{x_{N+1}}{S^{N+1}}\log \frac{x_{N+1}}{S^{N+1}} . $$ In this form, the formula is probably not well suited for numerical applications due to cancellations.

share|improve this answer
    
Thanks, I will look into it. :-) –  blazs Jun 19 '13 at 11:10

I think that the following paper is closely related to your questions: http://hal.inria.fr/docs/00/60/90/65/PDF/RR-7663.pdf

share|improve this answer
    
This is very helpful, thanks! –  blazs Jun 18 '13 at 16:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.