# Incremental entropy computation

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?

-
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. –  user111691 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. –  user111691 Jul 3 '13 at 15:44

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.

-
Thanks, I will look into it. :-) –  user111691 Jun 19 '13 at 11:10

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.

-

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

-
This is very helpful, thanks! –  user111691 Jun 18 '13 at 16:32