読者です 読者をやめる 読者になる 読者になる

ボツネタ集(だいたいランダムフォレスト)

どうでもよいまえがき
今回の記事を最後に、機械学習関係の記事は、しばらくお休みにします!

  • 我流すぎて、機械学習の知識が不足していて、記事を書くのに妙に時間がかかる。
  • 最近、機械学習マッチで結果を出してないので、その中で記事を書いても、自分の中で説得力がいまいち。

というわけでしばらくの間は、機械学習について、以下のことに専念します。

  • 本とか論文とか読んでインプット
  • 機械学習マッチで結果を出す

ただ、記事を書こうと思ってたボツネタがあるので、勢いで書きました。雑です。メモ書き程度だと思ってもらえば。

それではスタートじゃ!!!!

ボツネタ1 : ID分解

世の中のIDというものは、複数の情報を持っていることがあります。これを別の特徴量として追加します。数学も機械も関係ない、セコいテクニックですが、意外と実戦的かもしれません。

まず、データを眺めてください。
f:id:shindannin:20150425163540p:plain

自分だったら、x0のidの赤で囲われた桁を、別な特徴量として追加します。紫で囲った部分も念のため追加するかもしれません。なぜでしょう?
f:id:shindannin:20150425163552p:plain

なぜかというと、いろいろと法則に気づくからです。

  • 紫の最初の5桁は、startdayが同じとき、常に同じ値になります。日時にかかわる値だと推測できます。ただ、この5桁とstartdayの大小関係違うので、一応特徴量として追加します。
  • 赤の桁は、完全に独立した値です。0~2の値しかとりません。とてもあやしいので、特徴量として追加します。
  • 下2桁と3桁は常に31なので不要です。
  • 下1桁はcyclesと常に同じ値なので不要です

f:id:shindannin:20150425163601p:plain

まぁ、ただ注意点は、

  • 分解前の元のIDを削るのは、特に慎重になったほうがいいです。気づいてない重要な情報があるかもしれないので。とりあえずは分解したのを追加するだけにとどめておきましょう。
  • つねに同じ値というのも、必ず全部のデータで常に同じ値になってるか確認しましょう。まれに違うことがあって、それが重要度の高い特徴量になってたら。大惨事です。

データを数値でも眺めるのは本当に重要です。機械学習する前に、必ず見るようにしましょう。まぁ、こういうのすら自動化するのが最高ですけどね。

ボツネタ2 : ランダムフォレスト実装例の簡単なバリエーションについて

過去の記事で、ランダムフォレストといってもバリエーションがいろいろあるといって逃げっぱなしなので、「ちょっとは説明しないと…」という罪悪感をかんじていました。

  • 効果 : ★が大きいほど、効果が高そう…といいたいですが、完全に自分の経験上なので、信ぴょう性はあまりないです。
  • 謎度 : ★が大きいほど、めったにみかけないもので、謎度を高くしてます。

C++の実装例を使って、ちょっと説明します。改良はみんなの宿題!

ルートバッグ1.5倍

効果 ★
謎度 ★★★★★
TopCoderのPsyhoさんのコードをみて知ったテクの中でも、もっとも謎なものです。

ブートストラッピングでは、ルートバッグのサイズは元のデータは0.632倍が使われています。
bootstrap - What is the .632+ rule in bootstrapping? - Cross Validated
実装例のrootBagSizeRatioの部分です。
115行目

const int rootBagSize = static_cast<int>(numData * rootBagSizeRatio); // ルートに入るデータの数
root.bags.resize(rootBagSize);

#if INCMSE
vector <int> freq(numData); // データ番号別の、ルートに選ばれた個数
#endif // INCMSE

// ブートストラップサンプリング
for (int i = 0; i < rootBagSize; i++)
{
    // ここで、同じIDが選ばれる可能性があるが、問題なし。
    int row = randxor.random() % numData;
    root.bags[i] = row;
#if INCMSE
    freq[row]++;
#endif // INCMSE
}

rootBagSizeRatioの部分は、調整するにしても、普通は1以下の値を入れようと考えますが、Psyhoさんはここで1.5倍のように、1を超える値を入れてくることもあります。いったいどういう意味があるのか分かりませんが…。
なお、

  • 1.5倍を入れるようにした場合でも、OOBデータもわずかに残ります。重複も許してるので。
  • このままだと計算時間も長くなるので、防ぐために特徴量毎にweightという変数を用意し、何回でてきたかをとっておけば、計算時間は長くなりません。ソースコードの改良は読者の宿題!!

領域を分けるとき、全部の境界を試す

効果 ★★★
謎度

Rのランダムフォレスト実装であるので、そちらが標準だと思います。

ある特徴量の、全部の境界を試してます。自分の実装例では以下のように、numRandomPositions個しか試していません。
224行目

for (int j = 0; j<numRandomPositions; j++)	 // どの位置で分けるか
{
    const int positionID = randxor.random() % SZ(node.bags);
    const FeatureType splitValue = features[node.bags[positionID]][featureID];

ただ、多く分けるほうが必ず良いというわけでもありません。特に、少ない特徴量で似たような木ができる現象の要因になることも。計算時間も長いです。

上記の実装を全部の境界で切るようにしたいなら、

for (int j = 0; j<SZ(node.bags); j++)	 // どの位置で分けるか
{
    const int positionID = j;

とすれば、機能としてはRの実装と一緒になりますが、速度としてはお話にならないです、ダメ!前回の日記で述べた式

  {Σ[i∈P](Yi-E[P])^2}                          - {Σ[i∈L](Yi-E[L])^2}                          - {Σ[i∈R](Yi-E[R])^2}
= {Σ[i∈P]Yi^2} - 2E[P]{Σ[i∈P]Yi} + |P|E[P]^2 - {Σ[i∈L]Yi^2} + 2E[L]{Σ[i∈L]Yi} - |L|E[L]^2 - {Σ[i∈R]Yi^2} + 2E[R]{Σ[i∈R]Yi} - |R|E[R]^2  ... 2乗を展開した
=                - 2E[P]{Σ[i∈P]Yi} + |P|E[P]^2                  + 2E[L]{Σ[i∈L]Yi} - |L|E[L]^2                  + 2E[R]{Σ[i∈R]Yi} - |R|E[R]^2  ... {Σ[i∈P]Yi^2} = {Σ[i∈L]Yi^2} + {Σ[i∈R]Yi^2} で消した。
=                - 2E[P]S[P]         + |P|E[P]^2                  + 2E[L]S[L]         - |L|E[L]^2                  + 2E[R]S[R]         - |R|E[R]^2 ... 総和Sであらわした
=                - 2S[P]^2/|P|       + S[P]^2/|P|                 + 2S[L]^2/|L|       - S[L]^2/|L|                 + 2S[R]^2/|R|       - S[R]^2/|R| ... E[A] = S[A]/|A|で平均Eを消した
=                -  S[P]^2/|P|                                    +  S[L]^2/|L|                                    +  S[R]^2/|R|                    ... 足し算

これで評価するようにすれば、xが小さいほうから高速に全ての分け方を試せます(予めqsortを使います)。まぁ、説明不足なので、本家のソースコードregTree.cの関数findBestSplitを熟読して、実装しましょう。読者の宿題!
なお、後述する平均2乗誤差、3乗誤差や1.5乗誤差を変えるというのをやると、以上の数式展開が使えず、速くできません。

領域を分けるとき、任意の場所で分けられるようにする。

効果 ???
謎度 ★★★
一度も試したことはありません。上記の例ではデータのある場所で分けていますが、現在のノードに入ってるデータの、特徴量xの最大と最小を求めておき、(max-min)*rand + min の位置で切るといった感じの実装で、任意の場所で分けることができます。これをやるとxの値の差で選ばれる確率が変わるようになるので、いろいろと問題が起きそうな気もしますが…。

領域を分けるとき、マージン最大化っぽいことをする

効果 ★★
謎度
過去の日記で、yowaさんからコメントをいただきました。Rの実装でもやっているので、謎ではありません。
ランダムフォレストのつくりかた(C++の実装例つき) - じじいのプログラミング

おそらく日記をみて、「せっかく赤色と青色の領域を分けるのに、なぜ、わざわざギリギリの点上で分けるのか。中間で分けた方がいいのではないか」と思った人もいるのではないかと思います。それです。

改良前
278行目

node.value = bestValue;

改良後はこんなかんじになるでしょうか。

FeatureType nextValue = -BIG;

for (int i = 0; i < SZ(node.bags); ++i)
{
    if( features[node.bags[i]][bestFeatureID] < bestValue)
    {
        nextValue = max(nextValue, features[node.bags[i]][bestFeatureID]);
    }
}
node.value = (bestValue + nextValue) / 2.0;
if (!(node.value > nextValue)) node.value = bestValue;

あまり効果があった経験はないのですが、計算のオーダーが増えるわけでもないので、いれていいと思います。

木の深さに応じ、特徴量を選ぶ数numRandomFeaturesを変える

効果 ★★★
謎度 ★★★

以下のnumRandomFeaturesは、通常は固定ですが、これを木の深さに応じて変えます。

198行目

for (int i = 0; i<numRandomFeatures; i++)
{
    // x0,x1,x2...の、どの軸で分けるかを決める
    int featureID = randxor.random() % numFeatures;

実装は読者の宿題!まぁ、これは簡単でしょう。木の深さを表す変数をノードにもたせておき、numRandomFeatures[depth]みたいにすればよろしい。

これは割と効果があります。特に、後述する似た木ができる現象を避けるのに使えます。つまり、木の浅いところではnumRandomFeaturesの値を少なく、深いところではnumRandomFeaturesを大きめにすると良いです。

MSE以外の誤差を使用する

効果 ★★
謎度 ★★★

311行目

double lossFunction(double y, double mean) const
{
    return (y - mean)*(y - mean);
}

ここを、絶対値の3乗誤差、絶対値の1.5乗誤差、絶対値などに置き換える方法です。

ボツネタ3 : ランダムフォレストで似た木ばかりができると予測性能が落ちる

ランダムフォレストで、同じような木がたくさんできてしまうと、極端に予測性能が落ちることがあります。以下のような条件のとき要注意です。

  • 特徴量が少ない(10個以下)
  • 特徴量に比べて、ノード分割の際に選ぶ数numRandomFeatures(RのmTry)が多い。(目安は、回帰 特徴量の数/3、分類 特徴量の数^0.5)
  • 切る場所を試す数numRandomPositionsが大きい(Rだと全部で切るので、多い)

木をたくさん増やすことである程度解消できますが、限度があります。ちゃんとパラメータを調整して、避けましょう。

以下の図は、特徴量が7個しかないケースで、予測性能が極端に落ちたときの、決定木10本をビジュアライズしたものです。

  • 上側がルートです。
  • 帯の長さが、ノードの属するデータの個数に当たります。
  • 帯の色が、ノードをどの特徴量xで分割したかにあたります。計7色。

これを見ると、一見カラフルで、いろんな木ができてますが、上部の色はだいたい、茶色か水色か黄緑しか来ていないことが分かります。
f:id:shindannin:20150425190854p:plain

念のため、上記の画像を出力するコードも貼っておきます。htmlで出力する手抜きなやつですが…。

    void visualize(int id)
    {
        char path[1001];
        sprintf(path,"../visual/VisualTree.html");
        FILE *fp = fopen(path, id==0 ? "w" : "a");

        vector <string> colors = 
        {
            "Red",
            "Maroon",
            "Yellow",
            "Olive",
            "Lime",
            "Aqua",
            "Teal",
            "Blue",
            "Green",
        };

        if (fp)
        {
            fprintf(fp,"<canvas id=\"sample%d\" width=\"15000\" height=\"300\">\n",id);
            fprintf(fp,"<p></p>\n");
            fprintf(fp,"</canvas>\n");
            fprintf(fp,"<script>\n");
            fprintf(fp,"var canvas = document.getElementById('sample%d');\n",id);
            fprintf(fp,"var context = canvas.getContext('2d');\n");

            float xRatio = 0.5f;

            queue < pair <int, int> > q; // ノード番号, 左座標
            q.push(make_pair(0,0));
            while(!q.empty())
            {
                pair <int,int> now = q.front();
                q.pop();

                const TreeNode& nd = m_nodes[now.first];


                fprintf(fp,"context.fillStyle = \"%s\";\n", colors[(nd.featureID+SZ(colors))%SZ(colors)].c_str());
                fprintf(fp,"context.fillRect(%d,%d,%d,%d);\n", now.second, 10*nd.level, (int)(SZ(nd.bags)*xRatio), 10);

                if(!nd.leaf)
                {
                    q.push(make_pair(nd.left,now.second));
                    q.push(make_pair(nd.right,now.second+(int)(SZ(m_nodes[nd.left].bags)*xRatio)));
                }
            }
            fprintf(fp,"</script>\n");
            fclose(fp);
        }
    }

ボツネタにすらまとめられなかったボツネタ

カテゴリカル変数ごとに、他の特徴量xや目的変数の統計データを求めて、新たな特徴量として追加する。

機械学習は、基本不等式で分けるので、カテゴリカル変数(列挙型)はやっかい。そのままは使えない。ただ集計して特徴量を足すのに使いやすい。カテゴリカル変数x1をだとしたら、x1の値ごとに、他の特徴量x2,x3..やyを集計して(足す・割る・割合を求める・最大・最小)、新たな特徴量を追加する話。なぜボツにしたかというと、
ランダムフォレストのつかいかた - じじいのプログラミング
の「同種のデータとのかかわりを表す変数を追加する」とネタがかぶってるから。ただ、あの記事ではカテゴリカル変数とは言わなかったので、改めて書くか迷った。ただ非常に効果があるテクニックなので、みなさん使ってほしいです。

ブースティングのC++の実装例

C++の実装例で決定木の部分は実装してるので、てきとーなブースティング(木0の予測外れ分を木1のyとツッコむ)というのを実装するのは割と簡単。ただ、まじめなブースティングは、木の重みづけの部分とかも含めて理論になってるっぽく、そこは理解してないので、やめた。また、実戦で使ったことがないのも不安なので、やめた。







以上です。では、さようなら~。ほっほー。