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

Is it possible to compute a conditional entropy (see the two following formulas) in an incremental manner ? That is, the sets C and K are not fix: each time we have a new element c, set K may increase or not; and I want to update the current conditional entropy value each time we have a new element c.

Basically, I want to know if it is possible to have an incremental expression for this conditional entropy, like it is the case for example for the mean which can be computed by: $\bar X_n = n^{-1}[X_n + (n-1)\bar X_{n-1}]$

  • Conditional entropy formula 1: $$H(C|K) = - \sum_{k=1}^{|K|} \sum_{c=1}^{|C|} \frac{a_{ck}}{N} log \frac{a_{ck}}{\sum_{c=1}^{|C|} a_{ck}}$$ $$H(C) = - \sum_{c=1}^{|C|} \frac{\sum_{k=1}^{|K|} a_{ck}}{N} log \frac{\sum_{k=1}^{|K|} a_{ck}}{N}$$

  • Conditional entropy formula 2: $$H(K|C) = - \sum_{c=1}^{|C|} \sum_{k=1}^{|K|} \frac{a_{ck}}{N} log \frac{a_{ck}}{\sum_{k=1}^{|K|} a_{ck}}$$ $$H(K) = - \sum_{k=1}^{|K|} \frac{\sum_{c=1}^{|C|} a_{ck}}{N} log \frac{\sum_{c=1}^{|C|} a_{ck}}{N}$$

Note: $a_{ck}$ may refer to something like a distance between elements c and k, or the number of elements of type c that are in k, or something like that ... and $N$ is $\sum_{k=1}^{|K|} \sum_{c=1}^{|C|} a_{ck}$

share|improve this question
    
Your question will be easier to read if you include the equations via LaTeX code in the question itself, instead of via external links. (The site can process and display such code directly.) –  Vaughn Climenhaga Feb 24 '12 at 20:25
    
@VaughnClimenhaga I've just edited my post to add the Latex code. –  shna Feb 24 '12 at 22:03
    
what is $N$? Is it $|K| |C|$? –  Suvrit Feb 24 '12 at 23:14
    
I have edited my post to be more clear. –  shna Feb 28 '12 at 19:21
1  
Dear shna, your question seems to be closely related to this one:mathoverflow.net/a/134376/34944. –  Blaz Sovdat Jun 29 '13 at 9:30
show 1 more comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.