1
$\begingroup$

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}$

$\endgroup$
5
  • $\begingroup$ 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.) $\endgroup$ Feb 24, 2012 at 20:25
  • $\begingroup$ @VaughnClimenhaga I've just edited my post to add the Latex code. $\endgroup$
    – shna
    Feb 24, 2012 at 22:03
  • $\begingroup$ what is $N$? Is it $|K| |C|$? $\endgroup$
    – Suvrit
    Feb 24, 2012 at 23:14
  • $\begingroup$ I have edited my post to be more clear. $\endgroup$
    – shna
    Feb 28, 2012 at 19:21
  • 1
    $\begingroup$ Dear shna, your question seems to be closely related to this one:mathoverflow.net/a/134376/34944. $\endgroup$ Jun 29, 2013 at 9:30

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.