はじめに
こんにちは。株式会社エイアイ・フィールドでプロダクト開発をしている久保です。この記事はエイアイ・フィールドアドベントカレンダー2021の21日目の記事です。先日出張でSITA2021にいってきました。この学会は情報理論に関する学会なのですが、この記事ではその情報理論の基礎の基礎であるシャノン・エントロピーについて書こうと思います。
エントロピーの定義
エントロピーは色々なところで使われる語です。熱力学であったり、統計力学であったり、それらの定義はつながっているのですが、ここでは情報理論におけるシャノン・エントロピーの定義を示します。
$\mathcal{X}$を有限集合（たとえば、$\mathcal{X} = \{1, 2, 3\}$）とし、$X$を$\mathcal{X}$上の確率変数とします。この時確率質量関数は$p_X(x) := \Pr\{X=x\}$で表されるとします。確率変数$X$のシャノン・エントロピー$H(X)$は
$$
H(X) := -\sum_xp_X(x)\log p_X(x) = \mathbb{E}[-\log p_X(X)]
$$
で定義されます。$\forall x\ 0 \leq p_X(x) \leq 1$より$\forall x\ 0 \leq -\log p_X(x)$なので、$0 \leq H(X)$がわかります。なお、$H(X) = 0 \iff \exists x\ p(x) = 1$なのがわかります。つまりエントロピーは確率があるところに偏っていると値が小さくなる量と言うことがわかります。また、証明を省きますが、$H(X) \leq \log|\mathcal{X}|$ということが知られており、これを達成するのは$p_X$が一様分布のときです。これらのことからエントロピーは確率変数の乱雑さを表す量と呼ばれます。
エントロピーの応用
エントロピーの応用として可逆圧縮の圧縮限界を示すというものがあります。
次のような記号列を考えてみましょう。
cbdbaaaaadbbacabaabaeaacaacfabba
この文字列は
text_ = 'cbdbaaaaadbbacabaabaeaacaacfabba'
for ch_ in 'abcdef':
print(ch_, ': ', text_.count(ch_))
# a : 16
# b : 8
# c : 4
# d : 2
# e : 1
# f : 1
のようにそれぞれの文字が含まれます。これのエントロピーは、
# a : 16 / 32 = 1 / 2
# b : 8 / 32 = 1 / 4
# c : 4 / 32 = 1 / 8
# d : 2 / 32 = 1 / 16
# e : 1 / 32 = 1 / 32
# f : 1 / 32 = 1 / 32
より 62/32 = 1.9375 bitsとなります1。さて今、これらを01で表すことを考えます。特に、瞬時符号というものを考えます。瞬時符号とは頭から読んでいった時にそのまま復号できる符号のことであり、それぞれの符号の接頭辞として他の符号を含まないものです。例えば、次のようなものが考えられます。
# a => 000
# b => 001
# c => 010
# d => 011
# e => 100
# f => 101
さて、このような変換をもとの文に施したときの1記号あたりの01の数はいくらになるでしょうか？
code = {
'a': '000',
'b': '001',
'c': '010',
'd': '011',
'e': '100',
'f': '101',
}
encoded = ''.join(code[ch] for ch in text_)
print(encoded)
print('0: ', encoded.count('0'))
print('1: ', encoded.count('1'))
print('total length: ', len(encoded))
# => 010001011001000000000000000011001001000010000001000000001000100000000010000000010101000001001000
# => 0: 77
# => 1: 19
# => total length: 96
全ての記号が3 bitsに変換されているので、平均的には3 bitsになりますね。この平均ビット長をもう少し短くできないでしょうか？例えば次はどうでしょう。
code = {
'a': '00',
'b': '01',
'c': '10',
'd': '110',
'e': '1110',
'f': '1111',
}
encoded = ''.join(code[ch] for ch in text_)
print(encoded)
print('0: ', encoded.count('0'))
print('1: ', encoded.count('1'))
print('total length: ', len(encoded))
# => 1001110010000000000110010100100001000001001110000010000010111100010100
# => 0: 47
# => 1: 23
# => total length: 70
少し短くなりました。この場合、平均ビット長は70/32で2.1875 bitsになります。理論的には、この平均ビット長はエントロピー程度まで小さくできることが知られています。例えば、次のようにしてみましょう。
code = {
'a': '0',
'b': '10',
'c': '110',
'd': '1110',
'e': '11110',
'f': '11111',
}
encoded = ''.join(code[ch] for ch in text_)
print(encoded)
print('0: ', encoded.count('0'))
print('1: ', encoded.count('1'))
print('total length: ', len(encoded))
# => 11010111010000001110101001100100010011110001100011011111010100
# => 0: 31
# => 1: 31
# => total length: 62
この時、平均ビット長は62/32で1.9375 bitsとなります。これはエントロピーと同じですね。更に注目すべきは符号化した後の0と1の数です。0と1の数がちょうど同じになっています。
直感的には平均ビット長を最小化したときには符号化後の記号のエントロピーは最大化していそうです。
今回は01の2シンボルで符号化しましたが、これを3シンボルにしたときなど考えてみると面白いかもしれません。
おわりに
今回はシャノン・エントロピーと、その性質、符号化との関係性について紹介しました。この乱雑さを表す性質は色々なところで現れ、機械学習の文脈でもシャノン・エントロピーの親戚である相対エントロピーや相互情報量などがよく現れます。情報理論やエントロピーについてもっと知りたい方はCover&Thomasなどを読んでみるとよいかもしれません。また、より深く興味を持った方はCsiszar & Kornerなどがおすすめです2。
情報理論は奥の深い分野です。その応用は符号や機械学習など色々なところに現れます。興味を持った方は是非いろいろと勉強・研究をして来年のSITAに参加しましょう3。