Boostingの並列化

 パターン認識と学習の統計学のp.153に「バギングは並列化が可能であるので、並列計算機を用いることによって計算時間を大幅に短縮できるが、ブースティングは逐次的にしか計算できないので、計算時間は生成する弱仮説の数に比例して長くなることになる」と書いてあったので、ブースティングって並列化できないんだなぁ、と思っていたんだけれど、こないだAdaBoostをちょっと真面目に考えてみたら、弱学習器を選べば並列化が可能な場合もあるという事に気づいた。
 そもそも、よく読んでみると、パターン認識と学習の統計学には「ブースティングは並列化できない」とは一言も書いていない。これは実は意図的だったりするんじゃないかと思う。「生成する弱仮説の数に比例して計算時間が長くなる」というのはまったくその通りで、データの重み付けを逐次的に変更しながら学習を繰り返すというAdaBoostの仕様上、これはどうしようもない。ただ、計算時間を並列化によって大幅に削減することは、場合によっては可能である。
 以下ではAdaBoostに限って話を進めるけれど、類似する手法にはみんな当てはまる話になっていると思う。Schapireが提案したオリジナルのBoostingにまで適用できるかどうかは分からない。
 Boostingはたくさんの弱学習器を寄せ集めて強力な識別器を構成する手法であるが、今回は弱学習器としては、決定株(decision stump)を考える。きっちりと勉強したことがないアマチュアの悲しさ、自分の考えている決定株が一般的な物であるのかどうかわからないが、ここでは、ある素性が存在するか否かで1か-1の値を返す関数とする。(ここで閾値という自由度を持たせる場合と持たせない場合とで計算量は大きく変わるが、並列化が可能である事自体は変わらない。)
 AdaBoostでは、まず普通にデータから弱学習器をひとつ学習させ、一つ目の弱学習器が間違えたデータサンプルの重要度を大きくして次の弱学習器を学習させる。間違えたデータサンプルの重みを更新しながらどんどんと弱学習器を学習させていく事で、精度の良い分類器を構成する手法である。回帰問題などにも使えるそうだ。
 AdaBoostを並列化する際の問題点は、ラウンドTにおけるあるサンプルの重要度は、その一つ前のラウンドが完了しなければ得られないという事である。逆に考えると、ラウンドTで弱学習器を生成する部分に関しては、並列化の余地があるかどうかはケースバイケースである。
 決定株の場合は、素性毎にデータの分類をどれだけ失敗したかが損失であり、その和を最小とする弱学習器を各ラウンドで探すわけなので、

  • それぞれの素性毎に損失を計算する
  • データ量が多い場合は、データ自体も適当なサイズで区切る

 という、2種類の手法で並列化が可能である。非常に大きな並列度が欲しい場合にはこの2つを併用することも可能であるが、そうでない場合は素性毎に区切る方が実装は楽である。データを分割する場合、各データチャンクに対して損失を計算した後で、最後に損失を足し合わせるフェーズが必要になる。こういった処理は、MapReduceに載せやすい形をしているので、Hadoopなどを使えばよろしかろう。データが大量になればどうしてもそういう手法をとらざるを得なくなってくるが、小規模であれば素性毎に区切って8コアの計算機で動かしたりすれば充分だろう。
 弱学習器を決定株にしちゃっていいの、という疑問があるが、これに関しては応用次第としか言えないだろう。弱学習器として決定株を用いた場合、出来上がるのは普通の線形識別器であるが、これは自然言語処理のように高次元でスパースな問題に対してはうまくいくことが知られている。例えば、http://hillbig.cocolog-nifty.com/do/2008/02/post_7fbc_1.htmlでそういったことが説明されている。
 もうちょっとリッチな弱学習器で並列化がしたい、というような場合は、Parallelizing AdaBoost by weights dynamicsが参考になるかもしれない。PDF買うのにお金がかかるので、まだ読んでないけど…。
 最後に、せっかくなので、ブースティングの専門書へのアフィリエイトを貼っておく。ブースティングだけで一冊の本になっているのは和書ではこの本だけだと思う。ただ、この本は良い本だとは思うのだが、自分には少し難しすぎた。最近になってやっとある程度理解できるようになってきたけれど、まだまだわからないところも多い。アルゴリズムの説明も抽象度が高くて一旦AdaBoostを理解するまではよくわからなかったので、初心者は他の書籍やウェブで公開されている資料で、先に基礎的な部分を勉強した方が良いかもしれない。

ブースティング - 学習アルゴリズムの設計技法 (知能情報科学シリーズ)
金森 敬文 畑埜 晃平 渡辺 治
森北出版株式会社
売り上げランキング: 80862