ハフマン符号化と交差エントロピー

ハフマン符号化が交差エントロピーとつながってて面白かった

例えば文字列「ABAACBDA」をエンコードするとする。工夫せずにエンコードしようとすると以下の通り。

するとエンコードされた文字列は「00 01 00 00 10 01 11 00」の16ビットとなる。ハフマン符号化では出現頻度の多い文字に少ないビット数を割り当てることでデータの圧縮を可能にしている。例えば今回の文字列を以下のように割り当てると

エンコードされた文字列は「0 10 0 0 110 10 111 0」の14ビットとなり少し圧縮された。今回は例があまり適切ではなかったがものによっては70%以上圧縮されたりする。実際は適当に割り当てるのではなくハフマン木というものを作って効率の良い割り当てを行う。

1文字に割り当てられるビット数の平均を平均符号数といい以下の式で表す。

$$\sum p(x_i)bit(x_i)$$

$p(x_i)$ は文字 $x_i$ が出現する確率で $bit(x_i)$ は文字 $x_i$ に割り当てるビット数。 $bit(x_i)=\log{\frac{1}{p(x_i)}}$ の時に平均符号長が最小となることが証明されているので書き直すと

$$H=\sum p(x_i)\log{\frac{1}{p(x_i)}}$$

Hをエントロピーと呼んだりするらしい。
ここで、確率分布 $P$ に従う文字列を、確率分布 $Q$ で最適化された方式でエンコードした時のエントロピーを考えると

$$H=\sum P(x_i)\log{\frac{1}{Q(x_i)}}$$

となる。このような式を交差エントロピーと呼んだりするらしい。PとQの分布が異なるとHの値は大きくなる。逆に言えば交差エントロピーが小さい時はPとQの確率分布は同じようなものだと推定できる。この性質を利用して機械学習で損失関数として使われたりする。例えばtensorflowでは次のように記述。

cross_entropy = -tf.reduce_sum(y_*tf.log(y))

もっとも、最近では交差エントロピーを計算する関数がすでに用意されているのでいちいち書く必要はないが。