決定木とランダムフォレスト|はじめてのパターン認識11章 #5

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

#1では1章〜2章の内容、#2では3章〜4章の内容、#3では5,10章、#4では、6,7,8章の内容を取り扱いました。

#5では、11章の内容を決定木とランダムフォレストについて取り扱えればと思います。
分量的に9章と同時に取り扱おうと思いましたが、全くの別概念なので分けて#6で扱おうと思います。
多少#5と#6は他に比べ分量的に少ないですが、独立して扱ったほうが良さそうなのでそうしたいと思います。
以下、目次になります。


1. 11章内容(識別器の組み合わせによる性能強化)
1.1 ノーフリーランチ定理(11.1)
1.2 決定木(11.2)
1.3 バギング(11.3)
1.4 アダブースト(11.4)
1.5 ランダムフォレスト(11.5)
2. まとめ


1. 11章内容(識別器の組み合わせによる性能強化)

11章のテーマとして是非とも理解しておきたいのが、11.2の決定木にアンサンブル学習(複数識別器の組み合わせ学習)を行うことで、11.4のアダブーストになったり11.5のランダムフォレストになったりするということです。
アンサンブル学習は言葉自体は出てきていませんが、scikit-learnなどの実装にも出てくるので関連として覚えておくのが良い言葉だと思います。複数の分類器を組み合わせることで精度を上げるという試みはSOTA(State-of-the-Arts)のR&Dでもよく行われており、そのためSingleClassifierとMultiClassifierで分かれて評価が取り扱われたりなどもします。


1.1 ノーフリーランチ定理(11.1)

ここは飛ばして良いと思います。以後の節の方が圧倒的に重要度が高いので、ここを読む時間があるなら後ろの読解にあてる方が有意義です。


1.2 決定木(11.2)

全体的に説明が冗長な気がしますが、太字のキーワードは軽く抑えておくのが良いと思います。
ボトムアップ的な手法とトップダウン的な手法が出てきますが、本文中に言及がある通り、トップダウン的な手法を用いるケースがほとんどです。トップダウン的な手法にいくつか種類があり、CART(classification and regression tree)、ID3、C4.5などは有名なので言葉は覚えておくと良いと思います。11.2.1は若干冗長な印象なので飛ばして良いと思います。11.2.2のノード分割規則は重要なので抑えておくと良いです。重要なポイントとしては不純度と呼ばれる基準に基づいて規則の構築を行うということです。『代表的な不純度を表す関数』のところでまとめられているのですが、交差エントロピージニ係数(Gini index)による規則の構築についてはなるべく抑えておきたいです。これらの不順度に基づいてどのように規則を作っているかだけなるべく抑えておくと良いです。

https://ocw.hokudai.ac.jp/wp-content/uploads/2016/01/IntelligentInformationProcessing-2005-Note-11.pdf
若干冗長な印象なので、上記のpdfの方がわかりやすいかもしれません。こちらでID3についてつかんである程度他は流しておいても十分だと思います。
11.2.3も冗長な印象なので読み流す形で良いかと思います。


1.3 バギング(11.3)

11.3のバギングは(bagging)は複数の識別器を組み合わせる際に使用する手法なので、必ず抑えておくと良いです。バギングはBootstrap AGGregatINGから派生した語句だそうで(知らなかったです)、ブートストラップサンプルを用いて複数の識別器を学習させ、新しいデータは多数決で決めるという手法だそうです。ブートストラップサンプルに関しては#1ではそこまで触れていないのですが、2章に詳しいので確認しておくと良いと思います。ブートストラップサンプルについてはそれぞれ独立に生成できるため、バギングは並列的に処理が可能です。ちなみにこの際に多数決に利用する識別器の一つ一つを弱学習器と呼んでおり、言葉自体がよく出てくるので抑えておくと良いです。

また、バギングの弱点として識別器のばらつきがブートストラップサンプルにのみ依存するので決定木間の相関が高くなってしまい、性能強化が十分にできない可能性について言及されています。
これについては具体的な例を用いて考えてみましょう。0.7の確率で正解の弱学習器3つの多数決で決める際に相関係数が1の際と0の際(分類器が独立)に多数決で正解になる確率はどうなるかについてです。
相関係数が1の際は全て同じ判断を行うため、0.7のままです。
分類器が独立な場合は、{}_3 C_0×(0.7)^3 + {}_3 C_1×(0.7)^2×(0.3)^1 = 0.78399...となり多数決の方が正解となる確率を高くすることができます。あまり厳密な論理展開ではないですが、だいたいのイメージはこちらでつかめるのではないかと思います。


1.4 アダブースト(11.4)

ブースティングはバギングとは違い複数の弱識別器を用意して学習を直列的に行う手法のことです。
ここでは11.4.1で出てくるアダブースト(AdaBoost; adaptive boosting)をとりあえず抑えておくと良いです。アダブーストを理解するにあたって抑えると良いのが弱学習器の学習結果に従って学習データに重みが付与されるということです。具体的には
誤った学習データに対する重みを大きくし、正しく識別された学習データに対する重みを小さくすることで後から学習する識別器ほど誤りの多い学習データに集中して学習するようにします。
計算の流れに関してはアルゴリズム11.2にまとまっているのでこちらを元に掴むのがシンプルで良いのではと思います。

その他の記述はちょっと長い印象なので読み飛ばしてしまって良いと思います。


1.5 ランダムフォレスト(11.5)

ランダムフォレスト(Random Forests)はバギングを改良したアルゴリズムで、サンプルだけではなく特徴量もランダム選択することで相関の低い多様な決定木を生成できるようにした手法です。SVMやアダブーストと同等レベルの結果が得られると本ではされていますが、この辺の記述も時代によって異なるので注意が必要です。

処理の流れはアルゴリズム11.4にまとまっているのでこちらをもとにつかむのが良いと思います。その他は読み飛ばしても十分だと思います。


2. まとめ

決定木、アダブースト、ランダムフォレストなどはアルゴリズムの流れを含めてしっかり抑えておくと良いと思います。特に決定木における不順度を用いてノードを追加していく流れは抑えておきたいところだと思います。