二項定理と多数決｜高校数学の演習を通して理解する決定木・ランダムフォレスト #2

f:id:lib-arts:20190427143114p:plain

上記ではニューラルネットワークを中心に取り扱いましたがその他アルゴリズムも取り扱えればということで、決定木・ランダムフォレストについて新規で連載をスタートしました。
#1では微分の最小値問題の復習と関数の増減表について取り扱いました。
https://lib-arts.hatenablog.com/entry/math_rf1
#2では二項定理について取り扱います。
以下、目次になります。

1. 例題③ 二項定理と二項係数
2. 例題④ 予測の独立性と多数決
3. まとめ

1. 例題③ 二項定理と二項係数
1節では二項定理と二項係数に関して取り扱います。二項定理では(a,b)などの二つの項の和のn乗である、 $(a+b)^n$ を取り扱った定理です。二項定理の数式は以下のように表すことができます。
$(a+b)^n = \sum_{k=0}^n{}_n\mathrm{C}_ka^{k}b^{n-k}$

この時右辺に現れる ${}_n\mathrm{C}_k$ を二項係数と読んでいます。例題③ではこの数式を元にいくつか具体的な問題を出せればと思います。

ex.03
以下のそれぞれの数式における、対応する係数を計算せよ。
(1) $(1+x)^2$ における $x$ の係数
(2) $(1+x)^3$ における $x^2$ の係数
(3) $(1+x)^4$ における $x^2$ の係数
(4) $(1+x)^8$ における $x^3$ の係数
(5) $(a+b)^5$ における $a^2b^3$ の係数

Answer.
(1) ${}_2\mathrm{C}_1 = \frac{2}{1} = 2$
(2) ${}_3\mathrm{C}_2 = \frac{3×2}{2×1} = 3$
(3) ${}_4\mathrm{C}_2 = \frac{4×3}{2×1} = 6$
(4) ${}_8\mathrm{C}_3 = \frac{8×7×6}{3×2×1} = 56$
(5) ${}_5\mathrm{C}_3 = \frac{5×4×3}{3×2×1} = 10$

解説.
二項定理を利用して二項係数を求めると上記のようになります。二つの項に冒頭で取り扱った(a,b)を使って $(a+b)^n$ を考えても良いですが、 $(1+x)^n$ のような多項式や、 $(p+(1-p))^n$ のような確率に二項定理を適用するなどの例もあります。
ここで組み合わせ(Combination)のCが用いられている理由としては、展開の際にn個から対象の文字がk回選ばれる組み合わせを計算していると考えると良いです。
ちなみにこの二項係数を計算するにあたってはパスカルの三角形という考え方もあり、美しい形になるのでscipy.linalgを用いた実装を下記にご紹介します。

f:id:lib-arts:20190427170854p:plain
このように二項係数を求めることもできます。

2. 例題④ 予測の独立性と多数決
2節では1節で取り扱った二項定理を元に、ランダムフォレストに利用されているアンサンブル学習について考察を行います。アンサンブル学習は多数決のようなものなので、二項定理と多数決を紐づけて考察を行います。確率pでうまく推論できるとした際に、n個の分類器を考えると二項定理は以下になります。
$(p+(1-p))^n = \sum_{k=0}^n{}_n\mathrm{C}_kp^{k}(1-p)^{n-k} = 1$
ここで、nを簡易化のためにnを奇数とすると多数決で決定を行うとする際に正答する確率は
$\sum_{\frac{n+1}{2}}^{n}{}_n\mathrm{C}_kp^{k}(1-p)^{n-k}$
となります。これを元のpと比べてどうなるかがここでの関心事です。

ex.04
(1) 確率p=0.7で正答する際に、3回の独立した試行の多数決が正答する確率を求めよ。
(2) 確率p=0.7で正答する際に、3回の非独立な試行の多数決が正答する確率を求めよ。ただし、それぞれの試行は完全に相関しているものとする。
(3) 確率p=0.7で正答する際に、5回の独立した試行の多数決が正答する確率を求めよ。
(4) p(多数決)とp(単体)の比が最大になるpを求めよ。（発展）

Answer.

(1) $\sum_{k=2}^3{}_3\mathrm{C}_k0.7^{k}0.3^{3-k} = 0.7^2×0.3×3+0.7^3 = 0.78399...$
(2) 独立した試行でないためpの値と変わらず、0.7
(3) $\sum_{k=3}^5{}_5\mathrm{C}_k0.7^{k}0.3^{3-k} = 0.7^3×0.3^2×10+0.7^4×0.3×5+0.7^5 = 0.836919999$
(4)
p(多数決)/p(単体)をP(ratio)とおき、P(ratio)を計算する。
$P(ratio) = \frac{\sum_{k=2}^3{}_3\mathrm{C}_k0.7^{k}0.3^{3-k}}{p} = \frac{3p^2(1-p)+p^3}{p} = 3p - 2p^2$
ここで、P(ratio)をpで微分する。
$\frac{δP(ratio)}{δp} = -4p+3$
したがって、p=0.75の際にP(ratio)は最大となる。

解説.
以下、結果を解釈していきます。まず(1)では3回の独立した試行の多数決によって、p=0.7が0.783..となっており、多数決の方が正答率が上がっていることが確認できます。ただしここで注意したいのが独立した試行であるからこうなったのであり、独立していない場合は0.7のままです。このことを考察すると、アンサンブル学習を行うにあたって分類器の相関を低くする必要性について納得できます。(3)は(1)の類題です。
(4)は発展問題として設けましたが、値の比較にあたっては比を計算して考察すると洞察が得られることが多いです。3つの多数決を計算する際はp=3/4でP(ratio)は最大になるのに加え、pが3/4以下では常に値が増加し、3/4以上では常に値が減少します。また、p=1/2とp=1でP(ratio)は1になるのも把握しておくと面白いです。

3. まとめ
#2では二項係数の和と多数決について考察することでアンサンブル学習の妥当性について論理展開を行いました。
#3では決定木の学習にあたっての不純度(inpurity)の関数について考察してみれればと思います。