トップ > Kaggle > KaggleのCTR予測コンペで上位10%に入るまでの試行錯誤

KaggleのCTR予測コンペで上位10%に入るまでの試行錯誤

Kaggle 機械学習

週末KagglerとしてavazuのCTR予測コンペに参加しました。Kaggleは機械学習版のISUCONだと思ってもらえばよいです。コンペ自体は終わっているので、late submiteであまり意味はないかもしれません、練習です。leaderboard上で上位10%以内に行けたので、そこまでの試行錯誤をメモしておきます。謎ノウハウ(?)を持っているガチ勢じゃないと上位に行けないものかと思っていましたが、基本に忠実にやればこれくらいの順位(上位7.6%)に行けましたし、他の人の工夫を垣間見えるという意味でも現場の機械学習やり始めたエンジニアにお薦めできそうでした。

参加の動機

そもそもなぜ今のタイミングでkaggleに取り組むのか、参加への動機を書いておきます。

  • 手掛けたことのあるタスクの幅を広げたい
    • nlpだと土地勘があって、うまくいかなくても何となく対処法が分かることが多いけど*1、そうでないドメインでもある程度できるように
    • 今回はCTR予測だけど、他のコンペもぼちぼちやっていきたいですね
  • 大きめのデータセットでの学習に慣れる
    • nlpだと教師データが数万文でやることが多いし*2、社内タスクでも人手でアノテーションするとそのくらいのオーダーのデータしか扱わないことが多い
    • 数千万規模のデータで試行錯誤(特徴量チューニング/ハイパラチューニング)の肌感覚を掴む
  • 使ったことのない手法やツールを試してみる
    • 仕事だと期日もあるし、使い慣れてる手法やツールを選びがち
  • 対外的な自分の実力を客観的に知る
    • 社内だと同じタスクをやる人が多くて数人、一人ということもありがちなので、自分の作った分類器がどれくらいいいのか客観的に知る機会が実はあまりない
    • 同じタスクに1000人規模でチャレンジして、その過程や結果がディスカッションやコードの形として残っているので、それらを自分の血肉としたい
    • もちろん、プロダクションで入れるときは目視して十分な精度あるかは確認しますが…

目標感: 頑張りすぎずに上位10%以内に入る

コンペなので順位が出ますが、あまり凝った方法を使わないで上位10%以内に入ることを目標としました。理由としては以下の通りです。

  • 週末くらいしかまとまった時間をそもそも取りにくい
  • リッチな計算機環境はない
    • 手元のmacbookのみ(メモリは使えて10GB程度)で戦うので、あまり凝ったチューニングはできない
    • 一時的にEC2を借りる手もあるけど、それは開催中のコンペに参加する時でいいかな…
  • 上位勢はそもそもプロダクションでは使えなさそうな(kaggleでしか使えなさそうな)特徴量を使っているので、あまり深追いしすぎても仕事に生かせる部分は減っていく
    • 例: ある日の午前3時のCTR予測をしたいのに、なぜかその日全体の閲覧数/クリック数が特徴量に入ってる(3時台のおすすめアイテムを計算したい時には使えない特徴量)
  • 終わってるコンペなので、賞金は手に入らない

残りは取り組んだ方法について時系列で書いていきます。以下、スコアはLeaderboardのPrivate Scoreのことを意味しています。

試行錯誤

AthenaとRedashによる探索的データ解析

やみくもに機械学習やっていくのは筋悪だなと思い、まず探索的データ解析(EDA: Exploratory Data Analysis)をすることにしました。コンペによってはカーネルでEDAした結果を置いてくれている人もいるので、それを参考にするのもよいと思いますが、練習なので今回は自分でやります。時系列要素があるので、なるべくシャッフルやサンプリングしないで解析したいなと思うものの、学習データが4000万件以上あるので手元で解析するのはなかなか大変です。そこで、今回はAthenaとRedashを使ってデータ解析をすることにしました。

学習用データを解凍してcsvにして、S3に置きます。圧縮済みのものを置いてもAthenaは動きますが、SELECTが返ってくるのは解凍済みのほうが早かったので、Kaggle用途には直接csvを置いておけばよさそうです(圧縮済み1GB、解凍後5GBくらいなので、スキャン量は多少多くなる)。スキーマはこんな感じで適当に作ります。

Athena用のテーブルのスキーマ定義

DROP TABLE ctr_practice.ctr_practice;
CREATE EXTERNAL TABLE ctr_practice.ctr_practice (
  `id` string,
  `click` int,
  `hour` string,
  `C1` string,
  `banner_pos` int,
  `site_id` string,
  `site_domain` string,
  `site_category` string,
  `app_id` string,
  `app_domain` string,
  `app_category` string,
  `device_id` string,
  `device_ip` string,
  `device_model` string,
  `device_type` string,
  `device_conn_type` string,
  `C14` string,
  `C15` string,
  `C16` string,
  `C17` string,
  `C18` string,
  `C19` string,
  `C20` string,
  `C21` string
)
ROW FORMAT SERDE 'org.apache.hadoop.hive.serde2.lazy.LazySimpleSerDe'
WITH SERDEPROPERTIES (
  'serialization.format' = ',',
  'field.delim' = ','
) LOCATION 's3://ctr-practice/'
TBLPROPERTIES (
  'has_encrypted_data'='false',
  'skip.header.line.count'='1'
);

こんな感じで日付毎のクリック率の推移を可視化したり、カテゴリ変数毎のクリック数をテーブルに出してデータ分析を進めていきました。

手元で解析するのが億劫になるようなデータサイズでも、Athenaでは簡単なSELECTなら5秒程度、cardinatityの高いGROUP BYなどが入っても3分程度で返ってくるので、かなりお手軽です。5GB程度のデータをかなりフルスキャンしてデータ分析しましたが、200円程度で週末Kagglerのお財布にも優しくて安心。

見所としてはAthenaはウィンドウ関数にも対応している(Presto互換)ので、SQLだけで比較的強力な特徴量が作れるといったことでしょうか。例えば同じdevice_idが前回に登場した時刻を出して、その差分を計算し、それを特徴量として追加するといったことも簡単にできます(手元でpandasでやるのは若干面倒)。ウィンドウ関数は10年戦えるデータ分析入門で勉強しました。普通に実務のデータ分析で便利。

SELECT id,
       device_id,
       hour,
       prev
FROM
  (SELECT id,
          device_id,
          hour,
          lag(hour, 1) over(partition BY device_id
                            ORDER BY hour) AS prev,
   FROM ctr_practice.ctr_practice
   ORDER BY id LIMIT 1000000)
WHERE (NOT prev IS NULL)
  AND (hour != prev);

BigQueryで同じように探索的データ解析をYouTubeで紹介されている方もいらっしゃるので、こちらも参考になりました。


BigQueryでKaggle入門 Part 1(コンペ解説 + EDA紹介)

ベンチマークをまず超える

全部0.5を返すのがベンチマークだったので、学習データでのCTRの平均値をひたすら返す君を最初のsubmitにしました。評価指標はlogloss(クロスエントロピー)で、0/1の結果だけではなく結果の確信度も考慮した指標で評価されます。この時のスコアが0.4405302でした。後段の学習ベースの方法がきちんとうまく行っているかの判断材料になるので、初期段階でやっておきたいですね。

線形分類器でシンプルな特徴量

次に学習データに与えられているカテゴリカルな特徴量をonehot encodingして、線形分類器に食わせるだけのものを作りました。学習にはvwを使いました。

学習が高速で、省メモリでラップトップ参加者にも非常に優しいツールでした。また、コマンドラインから組み合わせ特徴量を作ることができるというのも嬉しいポイントでした。学習データが4000万行あるので、テキストファイルに組み合わせ特徴量を吐いていると30分程度かかってしまい、試行錯誤が非常にやりにくくなってしまいます。コマンドラインから組み合わせ特徴量を作れると、テキストファイルに組み合わせ特徴量を吐き出す手間が省けて助かりました。

awkでvw形式に吐き出します。文字列から特徴量idへの変換もvwが中でやってくれるので本当にお手軽ですね。

% awk -F, 'NR > 1 {print ($2*2)-1, "|a", "a_"$4, "|b", "b_"$5, "|c", "c_"$6, "|d", "d_"$7, "|e", "e_"$8, "|f", "f_"$9, "|g", "g_"$10, "|h", "h_"$11, "|i", "i_"$12, "|j", "j_"$13, "|k", "k_"$14, "|l", "l_"$15, "|m", "m_"$16, "|n", "n_"$17, "|o", "o_"$18, "|p", "p_"$19, "|q", "q_"$20, "|r", "r_"$21, "|s", "s_"$22, "|t", "t_"$23, "|u", "u_"$24, "|v", "v_"substr($3, 7, 2)}'

シンプルな特徴量のみで学習。スコアは0.4153354程度でした。正則化項は結構小さめ(1e-7くらいのオーダー)でないと正則化が強すぎるようで、学習がうまくいきませんでした。

時系列要素を忘れていて過学習発生

vwにハイパラチューニング用のスクリプトが付属しているので、これを使うと便利です。(その1/その2)。これを使ってハイパラチューニングをしていると、手元の開発用データではよかった設定が、submitしてみるとだいぶ悪化しているという現象に遭遇しました。データを眺めてみたところ、時系列的な要素を考慮し忘れているのが原因でした。学習データをシャッフルして8:2に分割して開発用データを作っていましたが、新しい広告やユーザーがどんどん入ってくるので、シャッフルしてしまうと時系列要素が壊れてしまいます。学習データの最終日(10月30日)を開発用データとしたところ、leaderboardの傾向と一致しました。時系列要素のあるチューニングは難しいことが多いので、Kaggleはちょうどよい練習になりますね。

特徴量エンジニアリングに苦しむ

ここからスコアを上げるのに難儀しました。vwでは組み合わせ特徴量にワイルドカードを使うことができます。発火している特徴量の全ての組み合わせを考えてくれるってやつです(例えば-q ::や-q a:など。後者はaと他の全ての特徴量の組み合わせを考慮)。何も考えずに実行するもスコアはあまり変わらず…。ディスカッションの様子を見ていると、組み合わせ特徴量が重要であることは疑いようがなかったので、ワイルドカードにしたことにより不必要な特徴量も入ってしまったのでしょう。匿名化されている特徴量もありますが、意味を考えながら有効そうな組み合わせを人手で追加していきました。スコアは0.3945532まで上がりました(とはいえまだまだ750位くらい…)。

かなりスパースなデータなので、登場頻度の少ない特徴量は足切り(頻度10回未満のものはUNKNOWNにする)すれば汎化されて良いのではと思って試しましたが、自分の手元ではあまり効果がありませんでした。なんでだ…。

Factrization Machine(その1)

組み合わせ特徴量といえばFactorization Machine(FM)だよねと思ったので試してみます。vwがFMをサポートしていたので、そのままやってみました(::8のようなワイルドカードを使った)。スコアは0.3936758で650位前後で思ったよりは上がらず。1位の人もFMだし、きっと何か勘違いしているかチューニングの仕方が悪かったんだろう…。libfmなど本家のものを使ってみるといい結果が得られるかもしれません。

追記: やり方を変えたFactrization Machine(その2)ではもう少し精度が上がりました。

重みの更新方法を変える

sparseなデータで登場頻度も結構異なるので、重みの更新方法をsgdのように特徴量全部同じ幅でやるのではなくadagrad的な更新方法にすればよくなるのではと思って試しました。vwでのオプションは--adaptive --invariantか--ftrl --ftrl_alpha 0.01 --ftrl_beta 1といったやつです。これはまあまあうまくいってスコアが少し改善(0.3938853)しました。関連論文は恐らくこの辺。

しかし、これでもまだ700位前後。

GBTMで特徴量の組み合わせを考慮

人間による特徴量チューニングに疲れてきたので、決定木ベースの方法で組み合わせを見ることにしました。決定木ベースの方法を使うのは初めてだったので、色々分からないことがだらけでした。

baggingとboostingの違いについても今回初めて知りました。baggingは学習データや使用する特徴量をサンプリングすることで少し異なる識別器を多数学習するような方法です。各学習器は独立に学習することができます(random forestはこっちっぽい)。一方、boostingは最初に学習器を作ったらその学習器の出力と学習データの損失を元に次の学習器を作るような逐次的な学習を行なっていきます(gradient boosting tree modelはこちら)。Gradient Boosting from scratchなどを参考にしました。

使うならrandom forestかxgboostかなと思っていましたが、最近はlightgbmというのが省メモリで高速っぽかったのでこれを試しました。vwは1GBくらいでも動いてくれましたが、lightgbmは省メモリになるような設定をしても8GBくらい持って行くので、ラップトップではこの辺が限界っぽい…。xgboostはOOMでshellに殺されてしまいました。

vwとは違って特徴量idへの変換は自分で行う必要があります。MurmurHash3を使ってfeature hashingすることで対応しました。最初はpython組み込みのhash関数を使っていましたが、セキュリティ要件で実行の度に結果が変わってしまうということに気付かず、精度が全然出なくてしばらく悩んだというのは笑い話です。hashのbinのサイズは大きいほうがcollisionしなくなりますが、大きすぎると学習の際にメモリを食うようになります。vwを使っているときに24程度(次元数が224で大体800万程度)でも十分精度は出ていたので、ここでも同じものを使いました。

お手軽feature hashingスクリプト

import csv
import sys
import mmh3

input_file = sys.argv[1]
hash_bin = 2**24

with open(input_file, "r") as i:
    reader = csv.reader(i, delimiter=",")
    header = next(reader)

    for words in reader:
        result = []
        click = None
        for idx, word in enumerate(words):
            h = header[idx]
            feature = word
            if h == "click":
                click = feature
            else:
                feature = mmh3.hash("%s_%s" % (h, word)) % hash_bin
                result.append(feature)
        result.sort()
        if click is not None:
            print("%s " % click, end="")
        print(" ".join(map(lambda x: "%s:1" % x, result)))

木の数を増やしまくると学習時間がどんどん増えていくので、leafの数を増やす方向でやっていきました。サンプリングレートなど色々チューニング要素がありますが、手元であれこれ試すのが厳しかったので、他はディフォルトパラメータでやりました。スコアは0.3930893で500位程度。チューニングを頑張ればこれはもう少し上がると思います。

% lightgbm data=xgboost_train_shuf.txt objective=binary metric=binary_logloss max_bin=127 num_trees=300 num_leaves=127

余談ですが、決定木ベースの手法はデコード(予測パート)が遅いですね…。全部の木をleafまで舐めないといけないからそりゃそうかって感じですが、こんだけ遅いとnlpのようなデコード速度もそれなりに求められるアプリケーションにはなかなか難しいという発見が今さらながらありました。

カリブレーション

これも初めて知りました。学習器の出力する確率の平均とテストデータの平均が一致するかはやってみないと分かりません。一致して欲しい気はするけど、一致する保証など特にない。平均がズレている場合にそこの補正をしましょうというのがprobability calibrationという方法です。難しそうな響きがするけど、やることは簡単。少しですが、精度が上がりました。テストデータの平均は分からないので、学習データの平均はと一致するようにカリブレーションしました。

カリブレーションするための簡単なPythonスクリプト

import sys
import math

def inv_logit(x):
    return math.log(x / (1.0 - x))

def logit(x):
    return 1.0 / (1.0 + math.exp(- x))

train_avg_ctr = 0.169806
pred_sum_ctr = 0.0
cnt = 0.0

result = []
for line in sys.stdin:
    ctr = float(line)
    result.append(ctr)
    pred_sum_ctr += ctr
    cnt += 1.0

pred_avg_ctr = pred_sum_ctr / cnt

for item in result:
    intercept = inv_logit(pred_avg_ctr) - inv_logit(train_avg_ctr)
    # print("%s\t%s" %(item, logit(inv_logit(item) - intercept)))
    print(logit(inv_logit(item) - intercept))

Factrization Machine(その2)

ワイルドカードで全ての組み合わせを考慮しているからFactrization Machineの精度が思ったほど出ていないのではと思ったので、多少組み合わせ方を考えてみることにしました。データのフィールド名に

  • siteに関するもの
  • appに関するもの
  • deviceに関するもの
  • categoryに関するもの

といった種類が分かれていたので、それら毎に組み合わせてみることにしました。上から仮にa/b/c/dと名前だとすると、ab/bc/cdといった感じでフィールドの組み合わせ方を指定してFactrization Machineの学習を行ないました。スコアは0.3916204で230位まで上がりました。

アンサンブル

性質の異なる3つのモデル(人手による組み合わせ特徴量/LightGBM/Factorization Machine)ができたので、アンサンブルをやってみることにしました。データからそれぞれの学習器の重みを決定してもよかったのですが、今回はお手軽にやるのが目的なので、単純にmodel averagingします。これが意外と効いてスコアは0.3895500(122位で上位7.6%)まで伸ばすことができました。

ちなみにvwでパラメータだけ変えたものをアンサンブルしても、同じような出力を出すのでアンサンブルしても精度向上はほとんどありませんでした。アンサンブルで性能が上がるかどうかは性質の異なる学習器を複数作れるかどうにかかっていそうです。

他のチームで参考になった方法

GBMの特徴量をvwに入れる

各データをGBMの各木に食わせて、それぞれどのleafにたどり着いたかというカテゴリカルな変数を特徴量にしてvwに食わせるという特徴量エンジニアリングです。1位の人もやっているようで、GBDT featureと呼ばれている。

後段でGBMの結果とアンサンブルする方法と精度がどれくらい違うのかは自分でも試してみたいですね。

カテゴリカル変数を実数の特徴量に置き換えていく

こちらを参考に。集計が必要な分ちょっと面倒ですが、one-hotとは違った特徴量になるので、アンサンブルすると効きそうですね。自分の試行錯誤では出てこないアイディアだったので、なるほどという感じでした。id:ultraistさんも書かれていますが、集計期間は少し気を使う必要がありそうですね。

追記: 識者に教えてもらいましたが、この手の特徴量エンジニアリングはCount Encoding/LabelCount Encoding/Target Encodingなどと呼ばれているそうです。以下に詳しく書いてありました。一つコンペに参加すると色々情報が集まってきてお得!

まとめ

  • 手元のMacbookだけ&基本的なテクニックで上位10%以内に入ることができた
    • 今回はログデータでしたが、画像データの場合はさすがに無理かも...
  • 他者の回答や技術を参考にできるので、本に載っていないような生きた技術を学ぶことができる
  • 自分が使ったことがないツールや初めてのタスクを練習するのにはうってつけ
    • 今回はFactorization MachineやGradient Boosting Decision Treeの様子が分かってよかったです

というわけでKaggleオススメです。

Pythonではじめる機械学習 ―scikit-learnで学ぶ特徴量エンジニアリングと機械学習の基礎

Pythonではじめる機械学習 ―scikit-learnで学ぶ特徴量エンジニアリングと機械学習の基礎

*1:CoNLL2015のShared Taskだけはチームで一度出たことがあった

*2:機械翻訳は例外的