Random Forest とその派生アルゴリズム

はじめに

こんにちは。 Machine Learning Advent Calendar 2013、 12月4日担当のkazoo04です。
最近引っ越しをしまして、家ではインターネットが使えないつらい生活を送っています。

今日は最近気になってるアルゴリズムである Random Forest や、その派生アルゴリズムについて紹介したいと思います。

Random Forest はその使いやすさや性能の高さ、 Kinect による身体部位推定などで利用されていることから近年注目されており、この記事をご覧の方もよくご存知かと思います。
社内でも RF を便利に扱えたり、高速に計算したり、AWS で大量のデータを扱ったりするミドルウェアやライブラリを作ったりしています。

最近はさらに色々な応用例が発表されたり、面白そうな派生アルゴリズムが出てきたので一部ご紹介します。

Random Forest

Random Forest は、Leo Breiman が2001年に提案したアンサンブル学習の一種です。
簡単にいうと、たくさんの決定木を生成して多数決をとるという単純なアルゴリズムです。このようなアプローチのアルゴリズムには、Bagging や Boosting (そういえば Bagging 自体 Breiman の考案でした) に代表されるように、いろいろな手法が存在しますが、 RF は以下のようになかなかよい特徴を持っています。

• 学習・識別が高速
• 多クラス識別が用意
• 回帰にも使える
• 並列化可能
• 特徴のスケールや距離尺度に影響を受けない
• 実装が比較的容易
• ノイズ(誤った教師データ)に対して頑健
• 特徴が名義尺度でもOK
• 欠損値を許容できる
• Cross validation しなくていい

……すばらしいですね！
私は去年の Advent Calendar で SCW を扱いましたが、Random Forest も非常に使い勝手の良いアルゴリズムだと思います。
デメリットとしては、過学習しやすいことやメモリを食うことが挙げられますが、これらについてはいくつかの工夫を行うことによって緩和することが可能です。

基本的なアルゴリズム

まず、データセットから重複を許して T 個のサブセットを作成します。
それらすべてのサブセットに対して弱識別器となる決定木を生成します。
決定木については適当に CART などのアルゴリズムを使いますが、
過学習を防ぐために木が一定以上の深さになったら学習を打ち切ることもあります。

分割関数については、データによって適時変える必要がありますが、基本的には2分決定木でよいようです。もっとたくさんの子に分割する方法も考えられますが、そうしたところであまり精度は上がらないといわれています。

その結果、T個の決定木が生成されることになるので、最後に多数決をとったり単純ベイズ分類器を使ったりして強学習器を作ります。
単純ベイズ分類器を使うよりは Complement Naive Bayes や AODE やその他機械学習アルゴリズムを使ったほうがいいと思いますが、今回の本質とは逸れるので省きます。

派生アルゴリズム

Extremely Randomized Trees

ERT の考え方は簡単です。
RF では 決定木を作るときに分岐させる位置を網羅的に探索し、なんらかの基準でもっとも良い部分を選びますが、 ERT では単にランダムで選択します。

サブセットの抽出をせずに、すべてのデータを用いる方法と、RF同様データをランダムに選んでサブセットを作成する方法が提案されています。

あまりに適当な感じですし、実際ちょっと精度が低下することも多いものの、メリットもあります。
ひとつは学習の高速化が見込めること、もうひとつは教師データが少なくても過学習しにくいことです。
RF は学習データが多くないと特に過学習しやすいので、ここを改善できるのはデータセットによっては大きなメリットです。

Alternating Decision Forests

通常のアルゴリズムとは異なり、幅優先で木を生成していくアルゴリズムです。
普通の RF では、サブセットから決定木を作成し、終わったらまた次のサブセットから決定木を作成していきます。
この手法では、まず深さ1ですべてのサブセットから決定木を生成し、それが終わったら深さ2で木を構築し…と、すべての木の根ノードを全部用意しておいて、一度に1ずつ深くしていくという方法をとります。
このとき、個々の木ではなくて、全体として損失関数を最小化するようにノードを追加していくことで、 RF より性能が向上するらしいです。

Random Ferns

OpenCV の Ferns 特徴量と関係があるのかと思いましたが別物みたいです。
RF というか決定木ではある分割関数をノードにして、2つに分岐させていきますが、 Random Ferns では 決定木の同じ深さのノードでは同じ分割関数を使ってしまうというアルゴリズムです。
ERT と同様、非常に大雑把なアルゴリズムであり、精度も低下してしまいますが、学習がかなり高速になるのと、過学習はしにくくなります…が、あまり詳しいところはまだよくわかっていません…。

色々な使い方

あんまり詳しくないですが以下の様なことにも使えるらしいです。

• 回帰
• 半教師あり学習

Depth 情報を使った姿勢推定

Shotton et al. "Real-Time Human Pose Recognition in Parts from Single Depth Images"

画像の領域セグメンテーション

Perbet et al. "Random Forest Clustering and Application to Video Segmentation"

キーポイントマッチング

Nishimura et al. "2段階のRandomized Treesを用いたキーポイントの分類"

通常の単一カメラでの姿勢推定

Yu et al. "Unconstrained Monocular 3D Human Pose Estimation by Action Detection and Cross-modality Regression Forest"

http://www.youtube.com/watch?v=rrXvzZOU-Ao

CVPR 2013: Unconstrained Monocular 3D Pose ...

おわりに

Random Forest や Extremely Randomized Trees は、 R, scikit-learn, OpenCV などに実装されており、容易に使うことができます。
最初に述べた通り、これらのアルゴリズムは非常に使い勝手が良く、今後も色々な応用例が発表されていくと思います。
これを気に RF 系のアルゴリズムを触ってみるのはいかがでしょうか。