「情報検索検索エンジンの実装と評価」Advent Calendar 23日目の記事です． adventar.org 本記事では，11章「融合・メタ機械学習」についてまとめます．

11章「融合・メタ機械学習」で扱う内容って？

一言で言えば，「アンサンブル学習」と「ランキング学習」です．

複数のモデルの出力を統合したモデルを考えることで，よりよい性能を得ようとするのが「アンサンブル学習(ensemble learning)」です．本章では，具体的な手法として 融合（凝集） ， スタッキング ， バギング ， ブースティング について扱います．

ランキング学習(learning to rank, LTR)は，結果がはっきりしているランキング例を用いて，ランク付け関数を学習するような手法です．クエリを入力とし，順序付きの検索結果を出力するモデルを作成したいときなどにも，ランキング学習は用いられます．

検索結果の融合

複数の出力を統合する一番シンプルなアプローチとして，複数の検索エンジンから返されるドキュメントリストをひとつに統合する検索結果の融合(search-result fusion)があります．検索結果の統合は， 固定カットオフ検索 , ランク凝集 , スコア凝集 の3つに分けて考えることが出来ます．

固定カットオフ検索

固定カットオフ検索は，それぞれのリストからの固定数のドキュメントが考慮される方法です．各リストにおけるドキュメントのランクは考慮しません．一番シンプルな方法として，それぞれのリストを投票とみなして，投票数が多い上位のドキュメントを選択する方法があります．

ランク凝集・スコア凝集

ランク凝縮はそれぞれのリストにおける各ドキュメントのランクを考慮する方法，スコア凝縮はそれぞれのリストの各ドキュメントのスコアも考慮する方法です．具体的なランク凝縮の方法として，逆順位融合(reciprocal rank fusion(RRF))があります．RRFでは，以下の式で表されるスコアでドキュメントを並べます．

$RRF_{score} = \sum_i \frac{1}{k + r_i ( d ) }$

ここで，dはドキュメント,iは統合するリストの添字， $r_i(d)$ はリストiにおけるドキュメントdの順位の逆数で，kは適当な定数です．要は，逆数順位の調和平均（逆数で平均をとって，さらにその逆数をとったもの）のようなものです． kとしては60を使うと良好な結果が得られることが知られているそうです．

スタッキング適応フィルタ

スタッキング (stacking)とは，メタ格付け器(meta-classifier, メタ識別器)を作成して，モデルの組み合わせ方もメタ識別器に学習させよう，という方法です． kaggleなどのデータ分析コンペでも，特性の異なる複数のモデルを組み合わせ，汎化性能を得るための手法として頻繁に用いられています．

本節では，メーラーに付随しているスパムフィルタのように，逐次モデルが更新されている適応フィルタを題材とし，スタッキングが説明されています．

バッチ格付け器のスタッキング

本節では，バッチ格付け器のスタッキングの際に問題となる，学習データと，実際に評価する本番のデータとの分布のズレについて扱っています．バッチ格付け器(batch classifier, バッチ識別器)は，11.2節のスパムフィルタのように逐次的にモデルがされない，学習データによって一度だけが学習されるような場合での格付け器を指します．このような場合，格付け器をスタッキングしようとすると，スタッキングされたモデルが学習データに過適合してしまい，本番環境で思ったような性能が出ない問題が置きがちです．

格付け器の過適合を避ける方法のひとつとして． ホールドアウト検証があります．これは，データを学習データTと，ホールドアウト集合（holdout set）または検証集合(validation set)Vの二つにわけ，Tを各モデルの学習に使い，Vを検証に使う，というものです．

より正確な検証方法として，交差検証(cross validation)もあります． k分割交差検証では，データをk個の集合に分割した後，ひとつを検証集合，残りを学習データとして，k回検証を繰り返します．

バギング

ブートストラップ凝集 (bootstrap aggregating)または バギング(bagging)とは，学習データLから重複を認めてサンプリングをしてブートストラップ訓練集合 $T_i$ を作り，それぞれのブートストラップ訓練集合 T_i ごとにモデルを作成したのち，それらを統合したモデルを得る方法です．

一般に，学習データLを単純に分割してT_iを作り，それぞれでモデルを作って統合することには，ほとんどメリットはありません．ひとつの大きな集合でT=Lで訓練すれば，同等の効果を得られるためです．バギングのミソは重複を認めてサンプリングして訓練集合を作っていることで，これによりブートストラップ集合はデータの母集団のよい近似になります．

バギングの代表的なアルゴリズムとしては，決定木を用いたランダムフォレストが挙げられます．

ブースティング

ブースティング (boosting)は，k番目の学習器で間違えたデータを，次には間違えにくくなるよう，各ドキュメント（学習データ）の重みを変えてk+1番目の学習器を学習し，最後にすべての学習器を統合する手法です．

バギングは汎化誤差を最小化するためにランダムに訓練データを操作しますが，ブースティングは学習誤差を最小化するために系統的に訓練データを操作します．ブースティングでもバギングでもよい分類機を生成できますが，基礎となる仮定はかなり異なっています．

ブースティングの代表的なアルゴリズムとしては，カメラの顔認識にも用いられているAdaBoostや，近年幅広く用いられているGBDT(gradient boosting decision tree, 勾配ブースティング決定木)などがあります．

mofumofu1729の計算機日記

プログラミングの勉強メモや日々の雑記など

「情報検索：検索エンジンの実装と評価」１1章融合・メタ機械学習