https://github.com/rasbt/python-machine-learning-book-3rd-edition/blob/master/ch03/ch03.ipynb を見ると決定木のところで Gini Impurity（ジニ不純度）やエントロピーとの比較が出ている。この不純度なるものが何かピンと来ないが手元の統計の本を見てもこういう名称では出て来ず、gg っても決定木の話とセットで出てきやすい。また、決定木の話も統計学の本ですぐに見つからず、お互いにちょっと分野が違うのか？という気持ちになる。
とりあえずよく分からないし、エントロピーの観点で以下の書を参考にする。
併せて、解析学として 新講解析学 | 学術図書出版社 - 大学・短大・高専・専門学校向けの教科書出版 を参考にする。「解析概論」に比べて実用的というか、わりとざっくりと使いたい形で記述してあることがあって役に立つ。*1
「情報理論」によるとエントロピーは状況の不確定度と定義されている。また、不確定度と大きいのはすべての状況が等確率で起こる場合で、どれが起こりそうかまったく予想ができないからという言葉での補足がある。
ある $n$ 個の独立な事象があるとして、いずれか 1 つが起こるという状況と、それぞれが起こる確率を $p_j,\ 1 \leq j \leq n$ としよう。いずれか 1 つが起こるとしたので、
$$
\begin{align*}
\varphi(p_1,\cdots,p_n) = p_1 + \cdots + p_n = 1
\tag{1}
\end{align*}
$$
が成立する。
エントロピー
この時、エントロピーは
$$
\begin{align*}
H(p_1,\cdots,p_n) = \sum_{j=1}^n p_j \log_2 \frac{1}{p_j} = - \sum_{j=1}^n p_j \log_2 p_j
\end{align*}
$$
で定義される。
$x \log_2 \frac{1}{x} = \log_2 \frac{1}{x} / \frac{1}{x}$ であるので、$x \downarrow 0$ の時、$\frac{1}{x} \uparrow +\infty$ であるので、$x \log_2 \frac{1}{x} \to +0$ である。よって、$H$ は $(p_1, \cdots, p_n) \in [0,1]^n$ と見る時、連続関数であり、最大値と最小値を持つ。これを特に (1) の束縛条件の元での極大値を求めたい。
Lagrange の未定乗数法によりある $\lambda \in \R$ をとって
$$
\begin{align*}
F(p_1,\cdots,p_n;\lambda) = H(p_1,\cdots,p_n) - \lambda \left(\sum_{j=1}^n p_j - 1 \right)
\tag{2}
\end{align*}
$$
と置く時、$\varphi(p) = 0$ のもと $p=p_0$ で $H(p_0)$ が極大値をとるのであれば、$F$ の各変数での偏微分も消えるようにできる。これを踏まえ、実際に $F$ の偏微分が消える $p$ の値から極大値をとる $p$ の当たりをつける。
$\frac{\partial F}{\partial p_j}(p) = 0$ とおくと、$- \log_2 p_j -1 + \lambda = 0$ より、$p_j = \exp (-1 + \lambda)$ となる。これは定数であり、任意の $j$ に対して同じであることから、$p_j = \frac{1}{n}$ が極大値をとる確率の候補となる。・・・そして実際は細かい検証をしたり境界での値と比較して最終判断を下さないとならないが、それを全部端折ってしまうことにして・・・事実としてここで最大値をとることが知られている。
Gini 不純度
次に Gini 不純度についてみる。
$$
\begin{align*}
G(p_1,\cdots,p_n) = \sum_{j=1}^n p_j(1 - p_j)
\end{align*}
$$
とおく。また、Lagurange の未定乗数法を使うことにして、$\lambda \in \R$ をとって、
$$
\begin{align*}
F(p_1,\cdots,p_n) = G(p_1,\cdots,p_n) - \lambda \left(\sum_{j=1}^n p_j - 1 \right)
\tag{3}
\end{align*}
$$
と置く。$\frac{\partial F}{\partial p_j} = 0$ とおくと、$1-p_j - p_j + \lambda = 0$ を得る。つまり、$p_j = \frac{1 + \lambda}{2}$ である。また定数であることから、$p_j = \frac{1}{n}$ が極大値をとる確率の候補となり、詳細な検証は端折ることにして、実際にここで $G$ が最大値をとることが知られている。
分類誤差
分類誤差
$$
E(p_1,\cdots,p_n) = 1 - \max_{j} \{p_j\}
$$
の最大値は簡単に求まる。適当な並び替えにより $p_1 \leq p_2 \leq \cdots \leq p_n$ とする。仮に $p_n < \frac{1}{n}$ とする。$\sum_j p_j < 1$ となり (1) 式に矛盾する。よって、$p_n \geq \frac{1}{n}$ である。$E$ を最大化するには $p_n$ を最小化できると良いため、$p_n = \frac{1}{n}$ にとれると良い。これは実際に $p_1 = \cdots = p_n = \frac{1}{n}$ で実現される。
と、ここまでエントロピー, ジニ不純度, 分類誤差について見てきた。いずれも何かしら $n$ 個の事象があるとしてそれらの事象が起こる確率が等しい時に最大値をとる。これを分類問題として考えると、今日の天気は？という問題を考えると、{晴れ, 曇り, 雨} という事象が等確率ということで、さっぱり天気が予測できないことに対応すると思う。何も分かっていないということだ。エントロピーの観点では「不確定度」ということになるが、確かに不確定だ。ちゃんと分類できる状態になく不確定でぼんやりした状態のことを「不純」と表現するのかもしれない。
とりあえず、これくらいのぼんやりした理解で先へ進んでみようと思う。
Python機械学習プログラミング 達人データサイエンティストによる理論と実践 - インプレスブックス によると、
ノードの不純度は、ノードが純粋ではない程度、すなわちノードに異なるクラスのサンプルがどの程度の割合で混ざっているのかを定量化する指標である。
とのこと。
とかで「雨」の中に「晴れ」がそこそこ混じれば不純度が高いということになるのだろう。エントロピーを用いた不純度はまだピンと来ない。
*1:特に定番とかそういう話の中で見ない本なのでよく分からないけど。
