二項定理(binomial theorem)とランダムフォレスト(random forest)の関係って?

f:id:ts0818:20210109160913j:plain

10世紀初頭における最初の勅撰和歌集である『古今和歌集』の「読人知らず」の和歌を初出としている。世界の国歌の中で、作詞者が最も古いといわれている。当初は「祝福を受ける人の寿命」を歌ったものだが、転じて「天皇の治世」を奉祝する歌。

君が代 - Wikipedia

国歌としては、1869年明治2年)、軍楽隊教官だったイギリス人ジョン・ウィリアム・フェントンが日本に国歌がないのを残念に思い、練習生を介して作曲を申し出たことを始まりとしている1880年明治13年)、法律では定められなかったが、事実上の国歌として礼式曲「君が代」が採用された。そのテーマは皇統の永続性とされる。

君が代 - Wikipedia

⇧ 国歌誕生秘話じゃないけども、欧米の影響だったんですな、世界の国家で作詞者が最も古いってのも驚きだけど、込められた意味合いが「祝福を受ける人の寿命」を歌ってたんですな。

そんなこんなで、今回は「機械学習」とかですかね。

レッツトライ~。

 

二項定理(binomial theorem)って?

遥かかなたの記憶になりますが、高校の数学で習った公式ですね。

Wikipediaさんに聞いてみた。

初等代数学における二項定理(にこうていり、binomial theorem)または二項展開 (binomial expansion) は二項式代数的な展開を記述するものである。定理によれば、冪 (x + y)n は a xb yc の形の項のに展開できる。ただし、冪指数 b, c は b + c = n を満たす非負整数で、各項の係数 a は n と b に依存して決まる特定の正整数である。

二項定理 - Wikipedia

例えば

a xb yc の項の係数 a は二項係数  とも呼ばれる。

二項定理 - Wikipedia

⇧ ってな感じで、「二項定理(binomial theorem)」が分かれば、二項式の公式が導けますと。 

これら係数を n および b を動かして並べることでパスカルの三角形を描くことができる。これらの数は組合せ論においても現れ、 は n-元集合から b 個の相異なるを選ぶ組合せの総数を与える。

二項定理 - Wikipedia

⇧ ってな感じで、組合せの考え方が重要になってきますと。

そんな「二項定理(binomial theorem)」ですが、


二項定理【高校数学】式と証明#1

⇧ 上記の動画がめちゃくちゃ分かりやすいです。

ちなみに「多項定理(multinomial theorem)」は、

数学における多項定理(たこうていり、multinomial theorem)は二項定理における二項式多項式に対して一般化するもので、多項和 (multinomial) の冪を和の各項からなる積和へ展開する方法を記述するものである。

多項定理 - Wikipedia

⇧「二項定理(binomial theorem)」を応用する感じになるようですね。

 

www.geisya.or.jp

⇧ 式については、上記サイト様を参考にさせていただくと、

■二項定理(binomial theorem)

 (x_1 + x_2)^n = {}_n \mathrm{ C }_0{x_1}^n + {}_n \mathrm{ C }_1{x_1}^{n-1}{x_2} + {}_n \mathrm{ C }_2{x_1}^{n-2}{x_2} + \ldots \\ + {}_n \mathrm{ C }_k{x_1}^{n-k}{x_2}^k + \ldots + {}_n \mathrm{ C }_{n-1}{x_1}{x_2}^{n-1} + {}_n \mathrm{ C }_{n}{x_2}^n \\ (x_1 + x_2)^n = \displaystyle \sum_{k=0}^n {}_n \mathrm{ C }_k{x_1}^{n-k}{x_2}^k

 

■多項定理(multinomial theorem)

 (x_1 + x_2 + \ldots + x_m)^n = \displaystyle \sum_{k_1 + k_2 + \ldots + k_m = n}^n \frac{ n! }{ {k_1!}{k_2!}{\ldots}{k_m!} }{x_1}^{k_1}{x_2}^{k_2}\ldots{x_m}^{k_m}

 

って感じになるみたい。

 

ランダムフォレスト(random forest)って?

Wikipediaさんによりますと、機械学習アルゴリズムのひとつみたいですね。 

決定木を弱学習器とするアンサンブル学習アルゴリズムであり、この名称は、ランダムサンプリングされたトレーニングデータによって学習した多数の決定木を使用することによる。ランダムフォレストをさらに多層にしたアルゴリズムディープ・フォレストがある。対象によっては、同じくアンサンブル学習を用いるブースティングよりも有効とされる。

ランダムフォレスト - Wikipedia

⇧ ってな感じで、「決定木」ってものが関係してきますと。

「決定木」って?

⇧ はい、「木構造」が基本形らしいですと。英語だと「decision tree」と呼ばれますと。

というわけで、「木構造」はと言うと、

木構造(きこうぞう)とは、グラフ理論の木の構造をしたデータ構造のこと。

木構造 (データ構造) - Wikipedia

⇧ ってな感じで、一番上を起点(root)として分岐していくデータ構造ですと。

2021年1月12日(火)追記:↓ ここから

「決定木」は大きく分けて、

  • 回帰木(Regression Tree)
    • 「回帰問題」を扱う場合の決定木のこと
      「目的変数」が連続数値などの場合に利用される
  • 分類木(Classification Tree)
    • 「分類問題」を扱う場合の決定木のこと
      「目的変数」がラベル、フラグなどの場合に利用される

の2つに分かれるようです。

qiita.com

⇧ 上記サイト様が分かりやすいです。 

2021年1月12日(火)追記:↑ ここまで

 

で、「ランダムフォレスト(random forest)」って?

英語版のWikipediaによりますと、

⇧ ってな感じで、複数の「決定木(decision tree)」で処理された結果の中から「多数決(Majority-Voting)」で最終的な結果を決めるってアルゴリズムということですと。

何故、複数の「決定木(decision tree)」を経由させて判定するのか?

教師あり学習」の「機械学習」では、「オーバーフィッティング」、日本語だと「過学習」と呼ばれる現象に悩まされることが多いのだそうですが、それを抑制するためなんだそうな。

Random forests or random decision forests are an ensemble learning method for classificationregression and other tasks that operate by constructing a multitude of decision trees at training time and outputting the class that is the mode of the classes (classification) or mean/average prediction (regression) of the individual trees.

https://en.wikipedia.org/wiki/Random_forest

Random decision forests correct for decision trees' habit of overfitting to their training set. Random forests generally outperform decision trees, but their accuracy is lower than gradient boosted trees. However, data characteristics can affect their performance.

https://en.wikipedia.org/wiki/Random_forest

⇧ ってな感じで、単独の「決定木(decision tree)」だと「訓練用データ(trainig set)」に「オーバーフィッティング(overfitting)」してしまいがちなんですと。

え?

過剰とは言え、「訓練用データ(training set)」でちゃんと結果出してるんだから文句ないんじゃないの?って思うじゃない?

ここが、落とし穴というね。

つまり、特化し過ぎてるってことは、「汎用性」がないとも言えるわけですと。

機械学習」の目的っていうのは、あくまで「未知のデータ」入力に対して結果を出す必要があるのであって、「訓練用データ(training set)」入力に対して100点の結果を出したとしても、「未知のデータ」入力に対して50点の結果しか出せなかったら全く意味は無いんですと。

なので、 

  • 訓練用データ(training set)
    機械学習のモデルを学習させるための入力データ
  • テストデータ
    機械学習のモデルの性能を評価するための入力データ
  • 未知のデータ
    本番の入力データ

のいずれのデータにおいても、同等の結果が得られるようにする必要があるんですと。 

このあたりの匙加減はデリケートな部分のようで、

masamunetogetoge.com

与えられた訓練データを再現する力の事を表現力と呼びます。使うモデルの表現力が高すぎると、データの些細な挙動までモデルが学習してしまい、未知のデータの予測が難しくなります。
データに含まれる誤差の部分を無視する力を汎化性能と呼びます。汎化性能が大きすぎると、データの構造の大事な部分も無視してしまい、鈍感なモデルとなります。

汎化性能とは?過学習との関係を解説します | マサムネの部屋

トレードオフになってくるみたいですね。 

 

二項定理(binomial theorem)とランダムフォレスト(random forest)の関係って?

で、「二項定理(binomial theorem)」と「ランダムフォレスト(random forest)」の関係って?

lib-arts.hatenablog.com

アンサンブル学習は多数決のようなものなので、二項定理と多数決を紐づけて考察を行います。

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

⇧ 上記サイト様が詳しいです。

「ランダムフォレスト(random forest)」が「多数決」を採用してるところがポイントみたいですね。逆に言えば「多数決」を採用してるアルゴリズムであれば良いってことなのかな?

何故に、「多数決」と「二項定理(binomial theorem)」が関係してくるのか?

ここで、「多数決」って何でしたっけ?

多数決(たすうけつ、英語majority decision)とは、ある集団において意思決定を図る際に、多数派の意見を採用する方法のこと。

多数決 - Wikipedia

⇧ はい、出ました。

これって、「二項定理」と同じように「組み合わせ」の考え方を当てはめられるじゃない?ってことかと。

例えば、「ランダムフォレスト(random forest)」ってのは、複数の「決定木」の結果を「多数決」した結果を最終的な結果にするってことなのですが、どうしたって実際のデータとの間に「誤差」というものが発生しますと。

ちなみに、「教師あり機械学習」の世界では、実際の結果のことを「目的変数」というそうですが、「機械学習のモデル」の使命は、いかにしてこの「目的変数」に近い値を算出するかということみたいですね。

xtech.nikkei.com

⇧ 上記サイト様のイメージ図がイメージしやすいかと。

上図を参考にさせていただくと「予測されたアウトプット」の値と「正しいアウトプット(教師データ)」の値の間の「ギャップ(誤差)」の割合が少なければ少ないほど良いということですと。

「正しいアウトプット(教師データ)」 = 「予測されたアウトプット」+「ギャップ(誤差)」

と言えるのではないかと。

そう考えると、「目的変数」を100%の正解と考えた場合、それぞれの割合は

  • 目的変数

みたいな構成と見なせるってことですかね?

脱線しましたが、

「ランダムフォレスト(random forest)」は、複数の「決定木」の「多数決」で結果が決まるということだったので、仮に「決定木」を3つとした場合、

 (x_1 + x_2)^3 = \displaystyle \sum_{k=0}^3 {}_3 \mathrm{ C }_k{x_1}^{3-k}{x_2}^k \\  

 x_1 は、「多数決」で選ばれた値

 x_2 は、「多数決」で選ばれた値以外

ってな式で表せて、展開してみると、

 (x_1 + x_2)^3 = {}_3 \mathrm{ C }_0{x_1}^3{x_2}^{0} + {}_3 \mathrm{ C }_1{x_1}^{2}{x_2} + {}_3 \mathrm{ C }_2{x_1}^{1}{x_2}^{2} + {}_3 \mathrm{ C }_3{x_1}^{0}{x_2}^{3} \\ = \frac{ 3! }{ 0! ( 3 - 0 )! }{x_1}^3{x_2}^{0} + \frac{ 3! }{ 1! ( 3 - 1 )! }{x_1}^{2}{x_2} + \frac{ 3! }{ 2! ( 3 - 2 )! }{x_1}^{1}{x_2}^{2} + \frac{ 3! }{ 3! ( 3 - 3 )! }{x_1}^{0}{x_2}^{3} \\ = \frac{{3}{\cdot}{2}{\cdot}{1}}{{3}{\cdot}{2}{\cdot}{1}}{x_1}^3{\cdot}{1} + \frac{{3}{\cdot}{2}{\cdot}{1}}{{1}{\cdot}{2}{\cdot}{1}}{x_1}^{2}{x_2} + \frac{{3}{\cdot}{2}{\cdot}{1}}{{2}{\cdot}{1}{\cdot}{1}}{x_1}^{1}{x_2}^{2} + \frac{{3}{\cdot}{2}{\cdot}{1}}{{3}{\cdot}{2}{\cdot}{1}}{1}{\cdot}{x_2}^{3} \\ = {x_1}^3 + {3}{x_1}^2{x_2} + {3}{x_1}{x_2}^2 + {x_2}^3 

ここで、3つの数での「多数決」が成立するのは、 

  1. 3つの値が全て同じになる
  2. 2つの値が同じになる

の2パターンと考えられますと。

なので、 

f:id:ts0818:20210109151647p:plain

⇧ 上記の2つの数の合算で、「多数決」が決まることになるので、

「決定木」の結果を「80%」と想定して計算してみると、

 {(\frac{80}{100})}^3 + {3}{(\frac{80}{100})}^2{(\frac{20}{100})} 

 = ({0.8})^3 + {3}{\times}({0.8})^2{\times}({0.2})

 = 0.512 + {3}{\times}{0.64}{\times}{0.2}

 = 0.512 + 0.384

 = 0.896

ってな感じになりますと。

ここで、1を100%と考えた場合、

 = 89.6 %

ってな割合になりますと。 

「80%」の結果の「決定木」が、「多数決」の結果「89.6%」になるという不思議。

lib-arts.hatenablog.com

多数決の方が正答率が上がっていることが確認できます。ただしここで注意したいのが独立した試行であるからこうなったのであり、独立していない場合は0.7のままです。このことを考察すると、アンサンブル学習を行うにあたって分類器の相関を低くする必要性について納得できます。

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

⇧ ってことのようで、「ランダムフォレスト(random forest)」内部で使用している「決定木」同士の相関を低くすることが重要ってことみたいですね。

機械学習」についてもモヤモヤ感が募る一方ですが、少しづつ知識を身に着けていきたいところですかね。

今回はこのへんで。