3

std::vector<int> countsを正の整数のベクトルとしN:=counts[0]+...+counts[counts.length()-1]、をベクトル成分の合計とします。設定pi:=counts[i]/Nすると、古典的な公式を使用してエントロピーを計算しH=p0*log2(p0)+...+pn*log2(pn)ます。

countsベクトルが変化しています --- カウントが増加します --- 200 回の変化ごとにエントロピーを再計算します。グーグルとスタックオーバーフローで簡単に検索した後、増分エントロピー計算の方法が見つかりませんでした。質問:エントロピー計算のための、分散のようなインクリメンタルな方法はありますか?

編集: この質問の動機は、VFDTのような学習者における増分情報利得推定のためのそのような式の使用でした。

解決済み:この mathoverflow の投稿を参照してください。

4

2 に答える 2

1

エントロピーとジニ指数の更新式とアルゴリズムを導き出し、そのメモを arXiv で利用できるようにしました。(メモの作業バージョンはこちらから入手できます。) また、この mathoverflow の回答も参照してください。

便宜上、簡単な 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)
于 2013-06-21T11:44:10.620 に答える