Regurarized Greedy Forest

最近、決定木ベースの手法ではxgboost が主流となってきています。実際、xgboost やrandomForest は手軽に結構良い精度が出るので、まずはじめに試すとしたらこのあたりの手法かなと思います。
 Regurarized Greedy Forest (以下、RGF と略す)は、C++ で書かれていることとトレーニングに時間がかかるため、あまり普及はしていないように感じます。ただ精度に関してはxgboost より良いことも多い印象があります。
Regularized greedy forest (RGF) in C++
こちらからダウンロードすることができます。RGF の使い方やアルゴリズムについては付属のpdf に詳しく書かれています。アルゴリズムについては時間があるときに追記しようと思います。

  • コンペでの使用状況
  • metric とloss の目安
  • 使用上の注意点
  • パラメータ
  • python のwrapper
  • R のwrapper

コンペでの使用状況

  • 実際に、kaggle のコンペでもときどき使用されていて、2 値分類ではWest Nile Virus Prediction のコンペで2 位の方がRGF を用いていました。

GitHub - diefimov/west_nile_virus_2015: the 2nd place solution for West Nile Virus Prediction challenge on Kaggle

  • またHiggsBoson のコンペの2位の方も使用されていました。

GitHub - TimSalimans/HiggsML: My second place solution to the Higgs Boson Machine Learning Challenge

  • 多クラス分類でも使用されている方がいました。otto のコンペで、商品を9 つのクラスに分類する問題で、stacked generalization の1st level に使用されていました。コードも公開されていますので、参考になると思います。

otto_2015/model.rgf.stack.R at master · diefimov/otto_2015 · GitHub

metric とloss の目安
以後、RGFの使い方を中心に見ていきます。まず評価関数に対してどのようにfit させるかについてです。
rgf のloss はLog, LS, Exp の3つから選択することになりますが、毎回3 つとも試すのは面倒なので第一候補の目安としては、経験的に次の表のように選べばよさそうです。

metirc loss
logloss LS (or Log)
auc Log(or LS)
rmse LS

使用上の注意点:
クラス分類では、そのクラスに属するかどうかが +1 と-1 で表現されています。(ただし、wrapper を使う分には気にしなくてもOK。)
perl を使うため事前にインストールする必要があります。

パラメータ
reg_L2: 正則化パラメータ
1, 0.1, 0.01 を基本的に試す。
loss: 損失関数(LS, Log, Expo)
LS: square loss, (p-y)^2/2;
Expo: exponential loss, exp(-py);
Log: logistic loss, log(1 + exp(-py));

test_interval: 100
test_interval ごとにモデルをセーブします
max_leaf_forest: 500
葉の数がmax_leaf_forest に到達するまで実行します。
Verbose: 進捗

実装関連
train_x_fn: 訓練データのデータ点
train_y_fn: 訓練データのラベル
test_x_fn: 検証用データのデータ点
model_fn: 予測に用いるモデルのファイル
prediction_fn: 予測したデータを格納するファイル名
SaveLastModelOnly: 最後に実行したモデルだけがセーブされる
model_fn_for_warmstart: 指定したファイルから訓練の続きを行える。(early stopping の実装などに使える)

python のwrapper
python では、便利なwrapper が以下の2 つあります。
GitHub - MLWave/RGF-sklearn: Scikit-learn API toy wrapper for Regularized Greedy Forests

GitHub - fukatani/rgf_python: Python Wrapper of Regularized Greedy Forest.
です。後者の方を試してみます。

git clone https://github.com/fukatani/rgf_python.git 
python setup.py install

なのですが、自分の環境では失敗したため、rgf.py をそのまま読み込むことにしました。実行する前にrgf.py の

loc_exec = 'C:\\Users\\rf\\Documents\\python\\rgf1.2\\bin\\rgf.exe'
loc_temp = 'temp/'

この部分を修正する必要があります。

from sklearn import datasets
from sklearn.utils.validation import check_random_state
from sklearn.cross_validation import StratifiedKFold
from rgf import RGFClassifier

iris = datasets.load_iris()
rng = check_random_state(0)
perm = rng.permutation(iris.target.size)
iris.data = iris.data[perm]
iris.target = iris.target[perm]

rgf = RGFClassifier(max_leaf=400,
                    algorithm="RGF_Sib",
                    test_interval=100,)

# cross validation
rgf_score = 0
n_folds = 3

for train_idx, test_idx in StratifiedKFold(iris.target, n_folds):
    xs_train = iris.data[train_idx]
    y_train = iris.target[train_idx]
    xs_test = iris.data[test_idx]
    y_test = iris.target[test_idx]
    rgf.fit(xs_train, y_train)
    rgf_score += rgf.score(xs_test, y_test)

rgf_score /= n_folds
print('score: {0}'.format(rgf_score))
# score: 0.959967320261

となって動作していることが確認できます。こちらでは、多クラス分類にも対応しています。(original は2値分類のみ。)

R のwrapper
R でのwrapper はまだ見られない感じで、とりあえず自分のを貼っておきます。
GitHub - puyokw/RGF-R: R wrapper for Regularized Greedy Forest
これをrgf-src.R として使用しています。
path にはrgf1.2 があるディレクトリを指すようにしてください。今のところ、2値分類でMetircs がlogloss の場合のみになっています。(夏休みにもう少し更新していきたいと思っています。auc とrmse(regression) と多クラス分類への対応)
たとえばnumerai のデータを用いてみます。feature はfeature1 からfeature21 まででmetrics はlogloss の2 値分類となっています。

path <- 'C:/Users/KawaseYoshiaki/Desktop/tmp/'
source(paste0(path,'rgf-src.R'))
train <- read_csv(paste0(path,"numerai_training_data.csv"))
test <- read_csv(paste0(path,"numerai_tournament_data.csv"))
testId <- test$t_id
target <- train$target
test$t_id <- NULL 
train$target <- NULL

(tmp <- RGFCV(train,target,nround=500,lambda=1,nfold=5) )# 200, 0.6916646 

pred <- RGF(train,test,target,nround=tmp$bestNum*100,lambda=1)
submission <- data.frame(t_id=testId, probability=pred$prediction)
write_csv(submission,paste0(path,'rgf.csv'))

f:id:puyokw:20160717202732p:plain
検証の間隔が100 ごとになっているため、今のところbestNum の値が1/100 で出力しているため、pred のときのnround は100 倍しています。

時間があるときにまた追記していきたいと思っています。

カテゴリー変数に embedding layer を用いたNeural Net

kaggle のRossmann の3 位のNeokami Inc(entron)さんの用いた手法が面白かったので、その概要の紹介などをしていきたいと思います。
まず手法の名前は、"Entity Embeddings of Categorical Variables" で、
[1604.06737] Entity Embeddings of Categorical Variables
論文にもなっています。コードはGithub にありますので、興味のある方はご覧ください。
github.com
(これはPython3 を用いて書かれています。)

embedding layer を用いた他のコンペでの有力なsolution。
kaggle のtaxi コンペ: Taxi Trajectory Winners’ Interview: 1st place, Team ? | No Free Hunch
Netflix: Deep learning solution for netflix prize | karthkk

Rossmann のコンペでは、いくつかの日に対して各店舗の売上の予測を行っています。
今回は"Entity Embeddings of Categorical Variables"の手法について見ていきます。まずカテゴリ変数の扱いはたいてい、1つの変数ですべて整数に置き換えて表現、あるいはone-hot encoding のようにダミー変数で boolean 型で表現するだと思いますが、この手法を用いることで、カテゴリー変数の近さ(類似度)を図示できるというのが面白いところです。たとえば、曜日については
f:id:puyokw:20160521214850p:plain
のように図示されます。これを見ると平日と休日で売り上げの傾向が異なるというのが分かります。同様に、店舗ごとや月ごとのデータもプロットできます。(上記のgithub に記載されています)
f:id:puyokw:20160521215346p:plain

カテゴリー変数を上手く扱いたいときあるいは、NN でカテゴリー変数が多いときに試してみたいなと思っています。
やり方としましては、NeuralNet でembedding layer を用いて学習し、そのモデルを用いてt-sne で次元を落として視覚化しています。
コードの方は、

models = []
# 曜日 7 -> 7 x 6 -> 6 
model_dow = Sequential()
model_dow.add(Embedding(7, 6, input_length=1))
model_dow.add(Reshape(dims=(6,)))
models.append(model_dow)

# 月 12 -> 12 x 6 -> 6 
model_month = Sequential()
        model_month.add(Embedding(12, 6, input_length=1))
        model_month.add(Reshape(dims=(6,)))
        models.append(model_month)
# 他も同様
# 上で定義したモデルを結合する
self.model = Sequential()
self.model.add(Merge(models, mode='concat'))
# 以下はいつも通り
self.model.add(Dropout(0.02))
self.model.add(Dense(1000, init='uniform'))
self.model.add(Activation('relu'))
self.model.add(Dense(500, init='uniform'))
self.model.add(Activation('relu'))
self.model.add(Dense(1))
self.model.add(Activation('sigmoid'))
self.model.compile(loss='mean_absolute_error', optimizer='adam')

で、イメージとしては
f:id:puyokw:20160523013817p:plain
となります。
次に、始めに図示していたplot のやり方についてです。これは上図の7 x 6 や12 x 6 となっている部分を視覚化のためにどちらも 6 -> 2 次元(3次元でもOK)へとt-sne で次元を落とします。すなわち、それぞれ 7 x 2 と 12 x 2 となります。

import pickle
from sklearn import manifold
import matplotlib.pyplot as plt
import numpy as np

# 作成したNN のmodel を読み込む
with open("models.pickle", 'rb') as f:
    models = pickle.load(f)

# entity embedding layer の重みをそれぞれ分かりやすい名前を付ける
model = models[0].model
weights = model.layers[0].get_weights()
store_embedding = weights[0]
dow_embedding = weights[1]
year_embedding = weights[4]
month_embedding = weights[5]
day_embedding = weights[6]
german_states_embedding = weights[20]
woy_embedding = weights[21]
weather_event_embedding = weights[30]

# entity embedding layer の重みに対してt-sne を適用する
# 曜日
tsne = manifold.TSNE(init='pca', random_state=0, method='exact')
Y = tsne.fit_transform(dow_embedding)
names = ['Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat','Sun']
# plot する
plt.figure(figsize=(8,8))
plt.scatter(-Y[:, 0], -Y[:, 1])
for i, txt in enumerate(names):
    plt.annotate(txt, (-Y[i, 0],-Y[i, 1]))

plt.savefig('dow_embedding.png')

# 月
tsne = manifold.TSNE(init='pca', random_state=0, method='exact')
Y = tsne.fit_transform(month_embedding)
names = ['Jan', 'Feb', 'Mar', 'Apr', 'May', 'Jun', 'Jul', 'Aug', 'Sep', 'Oct', 'Nov', 'Dec']
plt.figure(figsize=(8,8))
plt.scatter(-Y[:, 0], -Y[:, 1])
for i, txt in enumerate(names):
    plt.annotate(txt, (-Y[i, 0],-Y[i, 1]))

plt.savefig('month_embedding.png')

などで行えます。距離はt-sne 空間での距離となっています。
他のコンペで実際に試してみたいなと思っています。

stacked generalization

[概要]
最近のkaggle のコンペのwinning solution で、stacked generalization がよく使われています。これの元になった論文は、1992 年のWolpert さんによるものです。
triskelion さんのブログKaggle Ensembling Guide | MLWave
の中でもこの手法についての説明があります。

様々な学習器を上手く組み合わせて、より精度の良いモデルを作ろうというのが基本的な考え方です。具体的には次の図のような感じです。
f:id:puyokw:20151211225201p:plain
level 0 は、元となるデータです。またこの場合における各学習器はgeneralizer と呼ばれています。level 0 のデータにgeneralizer を適用して生成されたデータがlevel 1 のデータとなります。
その後も、同様に名づけられています。

[過去のコンペ]
まずは、多層パーセプトロンのように単純に組み合わせた場合の例を挙げます。
Otto のコンペでは、1 位、2 位、4 位の方はこの手法を使われていました。これは多クラス分類で、9 つのクラスに分ける問題で、評価関数はmlogloss です。
4 位の方はgithub にコードをupload されていますので、気になる方は参照してください。
1 位の方のモデル(kaggle のforum にて):
1st PLACE - WINNER SOLUTION - Gilberto Titericz & Stanislav Semenov - Otto Group Product Classification Challenge | Kaggle
2 位の方のモデル(kaggle blog にて):
Otto Product Classification Winner’s Interview: 2nd place, Alexander Guschin ¯\_(ツ)_/¯ | No Free Hunch
4 位の方のコード(github):
GitHub - diefimov/otto_2015

応用版は、さらに複雑なネットワークを形成したモデルです。
Dato のコンペは2 値分類で、評価関数はauc です。
Dato Winners’ Interview: 1st place, Mad Professors | No Free Hunch

こちらでは、階層をまたいだグラフになっています。

[訓練データの作り方]
まず検証用のデータは、いつも通りに訓練データを用いてモデルを作成して検証用のデータに適用します。
次に、1 段階上で使用する訓練データを作成します。ここでは、nfold =2 の場合で概略を説明します。
f:id:puyokw:20151204235306j:plain
cross validation の要領で、validation data の予測値を集めたものが次の段階で使用する訓練データになります。
nfold を増やすと、次の段階で使用するトレーニングデータの平均値が良くなります。しかしその反面、分散(標準偏差)が増えたり、計算に時間が掛かったりします。
分散が増えると、元のデータと異なる傾向のものになってしまう危険性があります。すなわち、cv score は改善しているのに、提出してみると酷いスコアが出てしまいます><
分散が大きいときの対策としては、nfold を小さくする、あるいはbagging をすることが考えられます。

自明なことですが、下位のモデルが改善すれば、それが伝播してより上位のgeneralizer が生成するモデルも良くなります。
またstacker model は、stacked generalization を使用するつもりがなくても、xgboost + NeuralNet のような単純なensemble をする場合に、どのくらいの割合で混ぜるのかを調べるのにも有用です。

チューニングのやり方は他のモデルと同様に、

  • cv score
  • 変数重要度(xgboost やrandomForest などでは)

を見ながら行っていきます。


[実際に試してみました]
ここでは、Otto のコンペのデータで実際にstacked generalization を使用してやり直した際に使用したモデルです。
上記の図を再掲しますが、これがそのときに使用したモデルです。
f:id:puyokw:20151211225201p:plain
コードはほぼcross validation を自分で書くだけのようなもので、やり方だけ確認して自分で組んでみるのが良いかなと思います。ちなみに、2nd level のxgboost による変数重要度の上位30 項目は次のようになっています。
f:id:puyokw:20151211225243p:plain
各々の学習器の何が効いているのかが、ちらっと垣間見えます。また上記の図では、モデルを簡略化して書いていまして、実際のところ、1st level の学習器の詳細は次のようになっています。

  • randomForest (n_estimators=300) + calibration
  • extraTrees (n_estimators=300) + calibration
  • xgboost (max_depth = 12, eta = 0.01)
  • kNearestNeighbor (k=2,4,8,16,32,64,128,256,512,1024,2048)
  • NeuralNet ( hidden-dropout の順に、中間層が次のような3 パターンを試しています。

512-0.5-512-0.5,
512-0.5-512-0.5-512-0.5,
512-0.5-512-0.5-512-0.5-512-0.5 )

  • svm(cost = 10)

今回の評価関数はmlogloss で、各クラスの境界付近を各学習器がどのように分けているのかが非常に重要で、mlogloss が0.40 を下回るにはそこを意識する必要があったように思えました。
ちなみに、今回試したモデルでのスコアは次のようになってました。
f:id:puyokw:20151211225338p:plain
Public LB score: 0.39756, Private LB score: 0.39869 でした。

ここで、使用したコードはgithub
github.com
にup していますので、気になる方はご覧ください。