增量熵计算

Let std::vector<int> counts是一个正整数向量，让N:=counts[0]+...+counts[counts.length()-1]是向量分量的总和。环境pi:=counts[i]/N，我使用经典公式计算熵H=p0*log2(p0)+...+pn*log2(pn).

The counts向量正在变化 --- 计数增加 --- 每 200 次变化我都会重新计算熵。经过快速谷歌和 stackoverflow 搜索后，我找不到任何增量熵计算的方法。那么问题来了：有没有一种增量方法，就像方差一样 http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Online_algorithm，用于熵计算？

编辑：这个问题的动机是使用此类公式进行增量信息增益估计VFDT http://homes.cs.washington.edu/~pedrod/papers/kdd00.pdf-像学习者一样。

解决： See 这个数学溢出帖子 https://mathoverflow.net/questions/133977/incremental-entropy-computation/134376#134376.

我导出了熵和基尼指数的更新公式和算法并做了笔记可以在 arXiv 上找到 http://arxiv.org/abs/1403.6348。 （注释的工作版本可用here http://blazsovdat.com/publications/incremental.pdf.) 另请参阅这个数学溢出 https://mathoverflow.net/questions/133977/incremental-entropy-computation/134376#134376 answer.

为了方便起见，我添加了简单的 Python 代码，演示了导出的公式：

from math import log
from random import randint
      
# maps x to -x*log2(x) for x>0, and to 0 otherwise 
h = lambda p: -p*log(p, 2) if p > 0 else 0

# update entropy if new example x comes in 
def update(H, S, x):
  new_S = S+x
  return 1.0*H*S/new_S+h(1.0*x/new_S)+h(1.0*S/new_S)

# entropy of union of two samples with entropies H1 and H2
def update(H1, S1, H2, S2):
  S = S1+S2
  return 1.0*H1*S1/S+h(1.0*S1/S)+1.0*H2*S2/S+h(1.0*S2/S)

# compute entropy(L) using only `update' function 
def test(L):
  S = 0.0 # sum of the sample elements
  H = 0.0 # sample entropy 
  for x in L:
    H = update(H, S, x)
    S = S+x
  return H

# compute entropy using the classic equation 
def entropy(L):
  n = 1.0*sum(L)
  return sum([h(x/n) for x in L])

# entry point 
if __name__ == "__main__":
  L = [randint(1,100) for k in range(100)]
  M = [randint(100,1000) for k in range(100)]
  
  L_ent = entropy(L)
  L_sum = sum(L)
  
  M_ent = entropy(M)
  M_sum = sum(M)
  
  T = L+M
  
  print("Full = ", entropy(T))
  print("Update = ", update(L_ent, L_sum, M_ent, M_sum))