はじめに

　機械学習でも登場する情報理論におけるエントロピーを1つずつ確認していくシリーズです。

　この記事では、平均情報量の最大値を扱います。

【前の内容】

【今回の内容】

はじめに
平均情報量の最大値(最大エントロピー)の導出
参考文献
おわりに

平均情報量の最大値(最大エントロピー)の導出

　平均情報量(average information)の最大値を導出して、グラフで確認します。平均情報量の最大値は最大エントロピー(maximum entropy)とも呼ばれます。
　平均情報量については「平均情報量(エントロピー)の定義 - からっぽのしょこ」を参照してください。

最大値の計算式

　まずは、平均情報量を数式で確認します。

　排反な $n$ 個の事象からなる事象系 $\mathbf{x}$ の確率分布を $p(\mathbf{x})$ を

$\displaystyle \mathbf{x} = (x_1, x_2, \cdots, x_n) ,\ 0 \leq p(x_i) \leq 1 ,\ \sum_{i=1}^n p(x_i) = 1$

として、平均情報量 $H(\mathbf{x})$ は、自己情報量 $I(x) = - \log_2 p(x)$ の期待値で定義されるのでした。

$\displaystyle H(\mathbf{x}) = - \sum_{i=1}^n p(x_i) \log_2 p(x_i)$

　1つの事象の確率が1のとき、最小値 $H_{\min}(\mathbf{x}) = 0$ になります。ただし、0と(負の)無限大の積を0とします。
　全ての事象が等確率のとき、最大値 $H_{\max}(\mathbf{x}) = \log_2 n$ になります。

最大値の導出

　次は、平均情報量の最大値の計算式を導出します。

平均情報量が最大となる確率分布

　平均情報量 $H(\mathbf{x})$ が最大となる確率分布 $p(\mathbf{x})$ を求めます。
　 $p(\mathbf{x})$ には、総和が1であるという制約条件があります。そこで、ラグランジュ乗数 $\lambda$ を用いて式( $p(\mathbf{x})$ の関数) $L(p(\mathbf{x}))$ を立てて、ラグランジュの未定乗数法を用いて制約条件付き最大化問題として解きます。

$\displaystyle \begin{aligned} L(p(\mathbf{x})) &= H(\mathbf{x}) + \lambda \left( \sum_{i=1}^n p_i - 1 \right) \\ &= - \sum_{i=1}^n p_i \log_a p_i + \lambda \left( \sum_{i=1}^n p_i - 1 \right) \end{aligned}$

　式を分かりやすくするため $p_i = p(x_i)$ とおき、一般化するため底を $a$ としています。

　 $L(p(\mathbf{x}))$ を $i$ 番目の事象の確率 $p_i$ に関して微分します。

$\displaystyle \begin{align} \frac{d L(p(\mathbf{x}))}{d p_i} &= \frac{d}{d p_i} \left\{ - \sum_{i'=1}^n p_{i'} \log_a p_{i'} + \lambda \left( \sum_{i'=1}^n p_{i'} - 1 \right) \right\} \\ &= - \frac{d}{d p_i} \left\{ \sum_{i'=1}^n p_{i'} \log_a p_{i'} \right\} + \lambda \frac{d}{d p_i} \left\{ \sum_{i'=1}^n p_{i'} - 1 \right\} \tag{1} \end{align}$

　 $i$ 番目の確率 $p_i$ と混同しないように総和に関するインデックスを $i'$ で表記しています(数学的な意味はありません)。

　式(1)の前の因子の微分は、 $p_i$ と無関係な項が微分によって消える(0になる)ので

$\displaystyle \begin{aligned} \frac{d}{d p_i} \left\{ \sum_{i'=1}^n p_{i'} \log_a p_{i'} \right\} &= \frac{d}{d p_i} \Bigl\{ p_1 \log_a p_1 + \cdots + p_i \log_a p_i + \cdots + p_n \log_a p_n \Bigr\} \\ &= \frac{d}{d p_i} p_1 \log_a p_1 + \cdots + \frac{d}{d p_i} p_i \log_a p_i + \cdots + \frac{d}{d p_i} p_n \log_a p_n \\ &= 0 + \cdots + \frac{d}{d p_i} p_i \log_a p_i + \cdots + 0 \\ &= \frac{d}{d p_i} p_i \log_a p_i \end{aligned}$

$i$ 番目の項のみ残ります。
　さらに、積の微分 $(f(x) g(x))' = f'(x) g(x) + f(x) g'(x)$ と合成関数の微分 $(f(g(x)))' = f'(g(x)) g'(x)$ 、対数の微分 $(\log_a x)' = \frac{1}{x \log_e a}$ により

$\displaystyle \begin{align} \frac{d}{d p_i} p_i \log_a p_i &= \frac{d p_i}{d p_i} \log_a p_i + p_i \frac{d \log_a p_i}{d p_i} \\ &= \log_a p_i + p_i \frac{1}{p_i \log_e a} \frac{d p_i}{d p_i} \\ &= \log_a p_i + \frac{1}{\log_e a} \tag{2} \end{align}$

となります。 $e$ はネイピア数であり、 $\log_e x$ は自然対数です。

　式(1)の後の因子の微分も、 $p_i$ と無関係な項が消えるので

$\displaystyle \begin{align} \frac{d}{d p_i} \left\{ \sum_{i'=1}^n p_{i'} - 1 \right\} &= \frac{d}{d p_i} \Bigl\{ p_1 + \cdots + p_i + \cdots + p_n - 1 \Bigr\} \\ &= \frac{d p_1}{d p_i} + \cdots + \frac{d p_i}{d p_i} + \cdots + \frac{d p_n}{d p_i} - \frac{d 1}{d p_i} \\ &= 0 + \cdots + 1 + \cdots + 0 - 0 \\ &= 1 \tag{3} \end{align}$

$i$ 番目の項のみ残り、 $\frac{d x}{d x} = 1$ なので1になります。

　式(2)と式(3)を式(1)に代入します。

$\displaystyle \begin{align} \frac{d L(p(\mathbf{x}))}{d p_i} &= - \left( \log_a p_i + \frac{1}{\log_e a} \right) + \lambda \tag{1'}\\ &= - \log_a p_i - \frac{1}{\log_e a} + \lambda \end{align}$

　ラグランジュ関数 $L(p(\mathbf{x}))$ の $p_i$ に関する微分 $\frac{d L(p(\mathbf{x}))}{d p_i}$ が得られました。
　ちなみに、底がネイピア数 $a = e$ のとき(自然対数を用いて情報量を定義する場合)、 $\log_e e = 1$ なので、2つ目の項が $-1$ になります。

　 $\frac{d L(p(\mathbf{x}))}{d p_i}$ を $0$ とおき、 $p_i$ に関して式を整理します。

$\displaystyle \begin{align} \frac{d L(p(\mathbf{x}))}{d p_i} = - \log_a p_i - \frac{1}{\log_e a} + \lambda &= 0 \\ \Rightarrow \log_a p_i &= \lambda - \frac{1}{\log_e a} \tag{4} \end{align}$

　底を $a$ として両辺の指数をとります。

$\displaystyle p_i = a^{\lambda - \frac{1}{\log_e a}}$

　両辺を $i$ に関して和をとると、制約条件 $\sum_{i=1}^n p_i = 1$ より $p_i$ の項が消えます(1になります)。

$\displaystyle \begin{aligned} \sum_{i=1}^n p_i &= \sum_{i=1}^n a^{\lambda - \frac{1}{\log_e a}} \\ \Rightarrow 1 &= n a^{\lambda - \frac{1}{\log_e a}} \\ \Rightarrow \frac{1}{n} &= a^{\lambda - \frac{1}{\log_e a}} \end{aligned}$

　底を $a$ として両辺の対数をとり、 $\lambda$ に関して式を整理します。

$\displaystyle \begin{aligned} \log_a \frac{1}{n} &= \lambda - \frac{1}{\log_e a} \\ \Rightarrow \lambda &= \log_a \frac{1}{n} + \frac{1}{\log_e a} \end{aligned}$

　この式を式(4)に代入します。

$\displaystyle \begin{align} \log_a p_i &= \left( \log_a \frac{1}{n} + \frac{1}{\log_e a} \right) - \frac{1}{\log_e a} \tag{4'}\\ &= \log_a \frac{1}{n} \end{align}$

　底を $a$ として両辺の指数をとります。

$\displaystyle p_i = \frac{1}{n}$

　平均情報量を最大化する $i$ 番目の事象の確率 $p_i$ が得られました。

　他の事象の確率についても同様に求められます。

$\displaystyle p(x_i) = \frac{1}{n} \quad (i = 1, 2, \dots, n)$

　このとき $p(\mathbf{x})$ は、総和が1であるという制約条件を満たします。

$\displaystyle \sum_{i=1}^n p(x_i) = \frac{n}{n} = 1$

　全ての事象の確率が等しい(一様分布)とき平均情報量が最大になるのが分かりました。

平均情報量の最大値

　平均情報量の定義式に一様な確率分布を代入して、最大値 $H_{\max}(\mathbf{x})$ を求めます。

$\displaystyle \begin{aligned} H(\mathbf{x}) &= - \sum_{i=1}^n p(x_i) \log_2 p(x_i) \\ &= - \sum_{i=1}^n \frac{1}{n} \log_2 \frac{1}{n} \\ &= - \biggl( \underbrace{ \frac{1}{n} \log_2 \frac{1}{n} + \cdots + \frac{1}{n} \log_2 \frac{1}{n} }_n \Biggr) \\ &= - \biggl( \underbrace{ \frac{1}{n} + \cdots + \frac{1}{n} }_n \biggr) \log_2 \frac{1}{n} \\ &= - \frac{n}{n} \log_2 \frac{1}{n} \\ &= - \log_2 \frac{1}{n} \\ &= \log_2 n = H_{\max}(\mathbf{x}) \end{aligned}$

　対数の性質より $\log_a \frac{1}{x} = - \log_a x$ です。
　平均情報量の最大値の計算式が得られました。

可視化

　最後に、事象の数と平均情報量の最大値の関係をグラフで確認します。
　対数関数については「対数の定義 - からっぽのしょこ」を参照してください。

　利用するパッケージを読み込みます。

# 利用パッケージ
library(tidyverse)

　この記事では、基本的にパッケージ名::関数名()の記法を使うので、パッケージを読み込む必要はありません。ただし、作図コードがごちゃごちゃしないようにパッケージ名を省略しているため、ggplot2を読み込む必要があります。
　また、ネイティブパイプ演算子|>を使っています。magrittrパッケージのパイプ演算子%>%に置き換えても処理できますが、その場合はmagrittrも読み込む必要があります。

　 $\mathbf{x} = (x_1, \cdots, x_n)$ の事象数 $n$ が変化したときの、等確率となる各事象の確率と、最大となる平均情報量の変化を可視化します。

　事象の数と対数の底を指定して、一様分布の平均情報量(最大エントロピー)を計算します。

# 事象数の最大値を指定
n_max <- 100

# 底を指定
a <- 2

# 最大エントロピーを計算
H_max_df <- tibble::tibble(
  n     = 1:n_max, # 事象の数
  p_x   = 1 / n,   # 各事象の確率:(等確率)
  #H_max = logb(n, base = a) # 平均情報量:(最大値)
  H_max = - logb(p_x, base = a) # 平均情報量:(最大値)
)
H_max_df

## # A tibble: 100 × 3
##        n   p_x H_max
##    <int> <dbl> <dbl>
##  1     1 1      0   
##  2     2 0.5    1   
##  3     3 0.333  1.58
##  4     4 0.25   2   
##  5     5 0.2    2.32
##  6     6 0.167  2.58
##  7     7 0.143  2.81
##  8     8 0.125  3   
##  9     9 0.111  3.17
## 10    10 0.1    3.32
## # … with 90 more rows

　事象の数 $n$ として使う最大の数をn_maxとして整数を指定して、1からn_maxまでの整数を作成します。
　事象の数ごとに、等確率の値(一様分布の各確率) $p(x_i) = \frac{1}{n}$ を計算します。
　事象の数ごとに、最大エントロピー $H_{\max}(\mathbf{x}) = - \log_2 \frac{1}{n} = \log_2 n$ を計算します。二進対数 $\log_2 x$ の場合はlog2()、自然対数 $\log_e x$ の場合はlog()、任意の底の対数 $\log_a x$ の場合はlogb()を使います。

　事象の数と一様分布の確率の関係のグラフを作成します。

# 事象の数と一様な確率の関係を作図
ggplot() + 
  geom_line(data = H_max_df, 
            mapping = aes(x = n, y = p_x)) + # 一様分布の確率
  labs(title = "probability", 
       subtitle = expression(list(x == (list(x[1], cdots, x[n])), p(x[i]) == frac(1, n))), 
       x = expression(n), 
       y = expression(p(x[i])))

　事象の数が増えるほど、各事象の確率が小さくなるのが分かります。

　事象の数と最大エントロピーの関係のグラフを作成します。

# タイトル用の文字列を作成
title_label <- paste0(
  "list(", 
  "a==", a, ", ", 
  "x == (list(x[1], cdots, x[n])), ", 
  "H[max](x) == log[a]*n", 
  ")"
)

# 事象の数と最大エントロピーの関係を作図
ggplot() + 
  geom_line(data = H_max_df, 
            mapping = aes(x = n, y = H_max)) + # 一様分布の平均情報量
  labs(title = "maximum entropy", 
       subtitle = parse(text = title_label), 
       x = expression(n), 
       y = expression(H[max](x)))

　事象の数が増える(各事象の確率が小さくなる)ほど、最大エントロピーが大きくなるのが分かります。

　この記事では、平均情報量(エントロピー)の最大値を導出しました。次の記事では、条件付きエントロピーの定義を確認します。

参考文献

わかりやすいディジタル情報理論(改訂2版)

作者:塩野充,蜷川繁
オーム社

Amazon

おわりに

　ラグランジュ乗数法だー懐かしーと思いながらサクっと書けました。参考にした本では2次元の例だったので単に微分しただけでしたが、せっかくなのでやってみました。

　ところで、PRMLの続きを読む気が戻らないから、少し知っている内容を深めたり広げたりするような別の本を読んでお茶を濁しているのですが、この内容ってPRMLに載ってるんですね。相互情報量までほぼ書き終わってから、KL情報量と何が違うんだっけと調べてたら気付きました。でもPRML版のエントロピー関連の説明を読んでもよく分かりませんでした。やっぱりまだしばらくいいや。

【次の内容】