Help us understand the problem. What is going on with this article?

Stacked Generalizationで分類器のスコアをひねり出す

More than 3 years have passed since last update.

概要

データ解析くらぶ第一回に向けて準備してたら抽選で落ちてしまったので用意してた内容を記事にしてみました。

Kaggleの上位者たち[1]は一つの分類器の予測のみを使用することはほとんどなく、複数の(場合によっては数百個の)分類器の結果を組み合わせるensemble learningを用いるそうです。

この記事では分類器を組み合わせる手法の一つであるStacked Generalization[3]を実装して、その効果を試してみます。

ensemble いろいろ

winner takes all

これは機械学習を少しかじったことがある人なら誰でもやったことがあるかと思います。
例えばある分類問題に対して、SVM、decision tree、 kNNそれぞれの精度をcross validationによって確認して、
最も精度が高いモデルを採用するという方法です。

複数の分類器の結果を平均する

簡単だけど効果が高い方法です。
例えばKaggleのあるcompetitionの上位15人のユーザーの予測結果を平均するだけで、1位のスコアを遥かに上回る結果を得られることもあります[1]。
また相加平均だけでなく相乗平均や重み付き平均を使う場合もあるようです[1]。

Stacked Generalization

前述の2方法はStacked Generalizationの特別な場合となっています。
下位の複数の分類器のout-of-the-fold(後述)データの予測結果を、再び上位の分類器に学習データとして与えるもので、
これにより下位の分類器の汎化誤差を抑え、分類器同士で弱点を補完しあうような作用を生むことができます。

Stacked Generalizationの理論

概要

basic_flow.png

基本的に、データは図の下から上に流れます。
ただし、各分類器に与える「学習データ」と「予測するデータ」の選び方が複雑で、適切に設計することで、layer 0 の分類器の汎化誤差を打ち消すように layer 1 の学習をすることができます。
以降は主にその設計についての説明になります。

学習データの分割

data_split.png

図のように、train_dataとして学習データ(入力データ+教師ラベル)とtest_dataとして予測するべきデータ(入力データのみ)が与えられているとします。
Stacked Generalizationのために、まずはtrain_dataを幾つかのfoldに分けます(図は3個)。
これらのfoldはtrain_data全体をカバーしていて、尚且つダブっていない必要があります。

layer 0 でpartition dataを学習、予測

partition.png

次に、図のようにlayer 0でout-of-the-foldデータを予測します。
ここではtrain_dataしか使いませんが、学習に使っているデータのデータ(out-of-the-fold)を予測している点がポイントで、
これによって汎化能力を加味したデータを出力することになります。
この処理をそれぞれの分類器で実施し、結果を列方向につなげます。

layer 0 でtrain data全体を学習、予測

whole.png

図のようにtrain data全体を学習し、test dataの予測結果を出力します。
このデータはlayer 1の予測のための入力として使います。
前項と同様に、分類器毎の結果を列方向につなげます。

layer 1

layer1.png

layer 1 では、layer 0 の out-of-the-foldのデータを使って学習し、
layer 0 の「train data全体を用いた学習に対するtest dataの予測結果」を入力として最終的な予測結果とします。
layer 1 の学習データはlayer 0 のout-of-the-foldの予測結果を使っているため、layer 0 の分類器の汎化誤差があれば、
その誤差を少なくするような学習をすることができ、精度向上につながるというわけです。

さて、layer 1 の学習器として「もっとも誤差の小さい列=分類器を使う」とすれば、cross-validationの結果が最も優秀なclassifierをそのまま使うことになるので"winner takes all"モデルとなりますし、
また layer 1で単純に平均をとればまた先述した平均モデルとなり、
どちらのモデルも実はStacked Generalizationの特別なケースであると見ることができます。

実装

dustinstansburyさんnamakemonoさんのリポジトリを参考にさせていただきました。

Generalizer抽象クラス

元論文[3]に従って、これまで「分類器」と呼んできたモデルはGeneralizerの具象クラスとして扱います(なぜGeneralizerというかは[3]参照)。

必要な機能はtrainpredictです。

generalizer.py
class Generalizer:
    def __init__(self):
        self.model = None
    def train(self, data, label):
        raise NotImplementedError

    def predict(self, data):
        raise NotImplementedError

この記事の例ではlayer 0 にRandom ForestとExtra Trees、layer 1に Logistic Regressionを使うのでそれぞれwrapしておきます。

random_forest.py
class RandomForest(Generalizer):
    def name(self):
        return("random_forest")

    def train(self, data, label):
        rfc = RandomForestClassifier(n_estimators=100, n_jobs=-1, criterion='gini')
        self.model = rfc.fit(data, label)

    def predict(self, data):
        return(self.model.predict_proba(data))
extra_trees.py
class ExtraTrees(Generalizer):
    def name(self):
        return("extra_trees")

    def train(self, data, label):
        et = ExtraTreesClassifier(n_estimators=100, n_jobs=-1, criterion='gini')
        self.model= et.fit(data, label)

    def predict(self, data):
        return(self.model.predict_proba(data))
logistic_regression.py
class LogisticRegression(Generalizer):
    def name(self):
        return("logistic_regression")

    def train(self, data, label):
        rfc = LR()
        self.model = rfc.fit(data, label)

    def predict(self, data):
        return(self.model.predict_proba(data))

学習データの分割

sklearn.cross_validation.StratifiedKFoldがその実装の一つでしょう。
ただのKFoldだと、教師ラベルに偏りがでてしまうのでStratifiedKFoldの方が有利です[1]。

layer 0 partition dataの学習、予測

stacked_generalization.py
    def guess_layer0_with_partition(self, generalizer):
        generalizer_prediction = numpy.empty((0, self.n_classes))
        for train_index, test_index in self.skf:
            generalizer.train(self.train_data[train_index], self.train_target[train_index])
            generalizer_prediction = numpy.vstack((
                generalizer_prediction,
                generalizer.predict(self.train_data[test_index])))

        reorder_index = [test_index for _, test_indices in self.skf for test_index in test_indices]
        return(generalizer_prediction[reorder_index, :])

generalizer毎に上のメソッドを適用します。StratifiedKFoldによってデータの行の順序が変わってしまっているので最後に並べなおします。

layer 0 train data全体の学習、予測

stacked_generalization.py
    def guess_layer0_with_whole(self, generalizer):
        generalizer.train(self.train_data, self.train_target)
        return(generalizer.predict(self.test_data))

これは何も捻りはなく、そのまま。

layer 1

stacked_generalization.py
    def guess_layer1(generalizer, train_data, train_target, test_data):
        generalizer.train(train_data, train_target)
        return(generalizer.predict(test_data))

上のメソッドをこんな感じで呼び出します。

main.py
StackedGeneralization.guess_layer1(
        LogisticRegression(),
        numpy.hstack(layer0_partition_guess),
        train_target,
        numpy.hstack(layer0_whole_guess))

全コード

githubに載せておきました。
layer 0 の各モデルの学習データを途中でセーブしたりロードできると実践的で便利なので、そういうことができる設計にしてたのですが途中で力尽きて中途半端になっています\(^o^)/

実行結果

手法 log loss of test data prediction (the lower, the better)
Random Forest 0.43849
Extra Trees 0.46627
Stacked Generalization of the above two models 0.39416

表のように、単純な2個のモデルを組み合わせるだけで高い精度を得られました。
実際のKaggle competitionではlayer 0 に数十個、数百個の分類器を用いるようです[1][4]。

黒魔術のパラドックス

アルゴリズムを考える立場の人たちの間では、任意性が低く一意的な誰でも使うことができる手法がいいものであるという前提があるような気がします。
Stacked Generalizationは元論文[3]でも触れられていますが、任意性が非常に高く黒魔術("black art")的な側面が強いかと思います。
ではなぜKaggleのようなコンペティションで黒魔術がよく使われるかというと、一意的なアルゴリズムでは他の参加者と差別化が難しく、黒魔術を使っても手間をかけてチューニングをすれば高スコアを出すことができるからでしょう。

任意的(黒魔術) 一意的
高精度 Kaggleで高いランクをとる手法 発明したい、画期的な何か
低精度 使わなくていい 入門で勉強するアルゴリズム

表の「画期的な何か」が提案されたらKaggleのようなコンペティションもあまり面白くなくなるのか、
それとも必ず黒魔術でスコアを高める余地は残るのか・・・。とても興味深いです。

参考資料

  1. General Tips for participating Kaggle competitions : Master Tierの方のスライド
  2. データ解析くらぶ#01
  3. Stacked Generalization
  4. データ解析くらぶ#01でスコアが良かった方のリポジトリ
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした