kaggleコンペ「Riiid! Answer Correctness Prediction」に参加しました
10月6日から1月7日まで開催されていたkaggleの「Riiid! Answer Correctness Prediction」に参加しました。全3,406チームが参加した中で、publicLB59位 / privateLB63位で銀メダルを取得することができました。初の銀メダルということで大変嬉しいです。
上位にはたくさんの日本人kagglerの方々がいる中でどこまで有用か分かりませんが、自分のメモとして取り組み内容・解法を簡単にまとめたいと思います。
コンペの概要
TOEIC学習アプリのログデータを元に、将来のユーザの正解/不正解を予測するタスクです。評価指標はAUCでした。
学習用データ
学習に用いるデータは下記の通りでした。
- train.csv
- questions.csv
- lectures.csv
train.csvがメインのデータで、ユーザ行動のログです。ユーザの行動には、「問題に回答」「講義を見る」の2種類があり、questions.csvとlectures.csvに問題と講義のメタデータが格納されていました。このうち、予測対象なのは問題の方ですが、講義の閲覧履歴も副次的な情報として利用が出来ました。
データ項目としては、下記の通り（抜粋）。
<train.csv>
- 正解/不正解
- ユーザの回答
- 問題/講義のID
- timestamp(各ユーザごと開始を0とした相対値)
- 前回の問題の回答時間
- 前回の問題の解説を見たかどうか
<questions.csv>
- 問題の答え
- TOEICのPart
- Tag
<lectures.csv>
- TOEICのPart
- Tag
- 講義の種類
データ項目としてはそこまでリッチではないですが、一方で40万人近くのユーザの行動ログが合計100Mレコード程度ありました。
テストデータ
テストデータはファイルとしては提供されずに、Time-series APIによって出力されました。このAPIの出力データはnotebook上ではごく少数のサンプルデータしか見る事が出来ず、submitすることによって内部で処理が走り全データの推論が行われる仕組みでした。APIによる出力は時系列の順番を保って順に出力されます。
テストデータは時系列上、trian.csvの後に位置し、合計2.5Mレコード（前半20%がPublic/残りがprivate）でした。trainで登場している既存ユーザとtestで新規に登場する新規ユーザ両方が含まれていました。
コンペの特徴
Time-series APIによるテストデータ出力が今回のコンペの特出すべき点だったと思います。時系列に沿ってデータが順次出力されるので、これらの情報を元に推論フェーズの中で特徴量を更新していく必要がありました。testのデータ数はそこまで多くないですが、iter回数が膨大なので、何も工夫せずに処理を組むと普通に9時間を超えErrorになってしまいます。この点はこのコンペの難しい部分ではありましたが、一方でコンペを現実世界の問題に近づけ、競技性も高めており、非常に良い仕組みだったと思います。
解法
このdiscussionでも共有されているようなTransformerベースのモデルを使っているチームが多かったと思いますが、僕はGBDTで取り組みました。途中でGBDTでの限界を感じ、Transformerモデルの検討を考えましたが、時間・スキル面でそれが叶わず、GBDTで走りきる形になりました。
validation
こちらのtitoさんのnotebookを利用させて頂きました。
元々のtrainデータはユーザでsortされているため、そのままの並びで分割してしまうと、validがほぼ新規ユーザになってしまうため適切ではありませんでした。またデータのtimestampは各ユーザごとの相対値のため、これを用いることもできません。この解決策として、上記のnotebookではユーザごとランダムなoffsetを加算したtimestampを作成しています。こうすることにより、仮想的にtimestampを絶対値として取り扱うことができ、この値でsortしたデータを任意に分割することで良い感じにvalidationを切ることができました。
model
下記モデルのアンサンブル
- LightGBM(全データ) SeedAvg×3
- LGB + CAT stacking(valid:0.90-0.95)
- LGB + CAT stacking(valid:0.95-)
推論フェーズでの時間制限がシビアなため多種多様なモデルをアンサンブルすることは難しく、同一の特徴量セットを用いてvalidの切り方やモデル種を変更した複数モデルの平均を取りました。ただ、アンサンブルでの伸びはあまりなく、単体0.800→アンサンブル0.801でした。
特徴量
大別すると、「質問に関する特徴量」と「ユーザに関する特徴量」を作成しました。元々のデータ項目と併せて計87個の特徴量を使用しました。
<質問に関する特徴量>
- questionsのtag（listを個別に分解 tag1 - tag6）
- トータル回答回数 / 正解数 / 正答率
- （各ユーザ初回の）トータル回答回数 / 正解数 / 正答率
- （各ユーザ2回目以降の）トータル回答回数 / 正解数 / 正答率
- elapsed_timeの合計・平均
- had_explanationの合計・率
- 同一bundleでの正答率平均
<ユーザに関する特徴量>
- トータル回答回数 / 正解数 / 正答率 (全体＆part別)
- 前回のtimestampとのdiff
- 一つ前の正解/不正解のtimestampとのdiff
- その問題を過去に何回解いたか
- その問題を正解したことがあるか
- 以前解いたことがある問題の正答率
- 回答頻度 (回答回数とtimestampの割り算)
- 質問正答率の平均（全て / 正解のみ / 不正解のみ）
- 前回の質問正答率とのdiff
- 直近5回分のtimestamp_diff / answered_correctly / part / 質問正答率
- lectureの総受講回数
全ユーザの回答結果を用いて算出した質問ごとの正答率はその問題の難易度を示すものとして有用でした。同様にユーザごとの正答率は、そのユーザの能力を示す指標となります。また、同一の問題を同じユーザが何度も解くケースが見られました。このようなケースでは当然正解する可能性が高まりますので、繰り返しかどうかというのも重要な情報でした。これらの組み合わせで、各ユーザ2回目以降の回答での質問ごとの正答率、ユーザごと正解した問題の質問正答率の平均、というような形でケース別の特徴量を生成していきました。
また、題材となっているアプリにおいて既にAIチュータによる問題の出し分けが行われていると考えると、ユーザに対して問題が簡単過ぎれば難易度を上げ、難しすぎれば難易度を下げ、という形で調整が行われていると想定しました。このような動きのどの局面にいるのかを表現することを狙いとして、質問正答率のdiffやshiftを作成しました。
diff、shift系の特徴量はかなり有用で、timestampのshift系の特徴量も寄与が大きかったです。同日に連続して解いている途中なのか、それとも間を置いて取り組んでいるのかを示す有効な特徴量として機能したのではと思うのですが、寄与度から考えるにそれ以上の何かがあるのかもしれません。shift量に関して直近5回というのは感覚的に短期すぎる気がしていますが、cvの結果を元に決定しました。
長期的な傾向を大まかに示す平均系の特徴量と、短期的な傾向を詳細に示すshift,diff系の特徴量という棲み分けをイメージして検討していました。attentionを用いると長期的な関係性をもっと上手く表現出来て、それが0.8以上の領域の鍵なのかなと勝手に想像しますが、全然分かってません（solutionで勉強させてもらいます。）
試したが上手く行かなかったアプローチ
全体的に混み入った特徴量はことごとくうまく行きませんでした。
- questionのグルーピング(TAGベース、2つの質問間の連関係数、難易度のrank化など)
- 直近のlecture受講とのtimestampのdiff
- 各ユーザごと1番最初のquestion_id
- 各ユーザごと先頭30問の成績
- ユーザrating(質問難易度を加味したスコアリング)
- timestampをdayに変換し、dayごと集計
直近のlecture受講とのtimestampのdiffは、cvでは+0.001程度効いていたのですが、LBスコアは低下しました。
合計の回答数が30のユーザが突出して多いことから、最初の30問はアプリ利用開始時のユーザ能力測定のための問題セットと考えました。また、この前半30問は決まった問題が出力されることが多そうだったので、この先頭30問をユーザの初期能力として特徴量を作りました。がこれもうまくいかず。
その他、questionをグルーピングしたりユーザのratingスコアのようなものも検討しましたがうまくいかず。これらのアプローチがダメというよりは適切に落とし込みができなかったような気がしています。
具体的な取り組み方
特徴量検討
全データを用いると加工や学習に時間が掛かりすぎるため、全体の10%のデータで特徴量の検討を行いました。
データ加工処理
今回のコンペでは、一方で100Mレコードの学習データを一気に処理する、もう一方で小数のテストデータを元に特徴量を逐次的に更新する必要がありました。そのため、同じ特徴量でもtrainとtestで別々の処理を実装しました。
trainについては、pandasのgroupby+cumsum/cumcountやshift、fillna(method='ffill')などを使って、各レコード時点の特徴量を生成しました。
train終了時点の情報を元にuser_idをkeyとする特徴量算出のための情報を集めたテーブルを作成し、これをtestフェーズで順次更新する処理を実装しました。更新するのはユーザに関する情報のみで、質問に関しては一貫してtrain全体で算出した特徴量を用いました。train/testの比率から影響は軽微と考え、処理時間短縮のためにこのようにしました。
testフェーズの特徴量更新処理のテスト
上記のように、trainとtestで別々の処理を実装しますが、当然最終的な出力は一致させる必要があります。ただ、testの処理は秘匿化されており、その結果であるpublicLBのスコアでしか処理の正しさを推し量れません。これでは仮にcvとpublicLBの乖離が発生した時に、それが追加した特徴量自身の問題なのか、その実装に誤りがあるのか切り分け出来ませんし、仮に実装の誤りと考えたとしてもそのバグを潰すために何回もsubするのは非効率です。
この解決策として、trainデータを用いて推論フェーズのシミュレーションを用意しました。これまたtitoさんのこちらのnotebookをマイナチェンジして用いました。
trainのデータ処理を行いその後分割したvalidデータと、シミュレータによって逐次的に処理したvalidデータ、両者でスコアが一致するか / 各特徴量が一致するかを検証しました。このテストを特徴量を増やす度に実行してバグ取りを行いました。殆どの特徴量で何らかのバグが埋め込まれていたので、このテストは非常に有用でした。やはりテスト大事。石に刻んでおきたい。
testフェーズの処理時間短縮
%%timeで各処理を時間計測して処理時間の短縮を検討しました。結局は、ユーザ特徴量をuser_idをindexとしたpandasのDataFrameで保持しておき、各要素に対して.at[user_id, 'hoge']でアクセスする形が処理時間的にも実装的にも楽だったので、この形に落ち着きました。
testフェーズのメモリ容量削減
処理時間ほどシビアではないですが、一部工夫をしないといけない点がありました。各ユーザごとその質問をこれまで何回答えたか・正解したか、というのは重要情報ですが、これをそのまま実装すると、40万ユーザ×14000質問の組み合わせとなりメモリ的にかなり厳しいことになります。
これに対処するために、こちらのdiscussionを参考に、user_idをkey,14000個のビット配列をvalueとしたdictを用いました。配列要素一つ一つがquestion_idに対応し、0/1をそれぞれ、問題を解いたことがない/ある、問題を正解したことがない/ある、と捉えることでユーザごとその質問を解いたことがあるか、正解したことがあるかの情報を保持しました。
また、質問に答えたかどうかではなく、その回数まで使うとcvスコアが無視できないレベルで向上したので、こちらは回数まで保持しました。dictの方で0,1回までは切り分けができるので、回答数が2回以上のパターンのみ別で保持するようにしました。(user_id, question_id)のmultiIndexのDataFrameを用いました。
その他
teamとしての取組
今回、比較的素直な題材だったので入門に良いかなと思い、kaggleに興味があるけど参加したことがない同僚を誘ってteamを組みました。
baselineを僕の方で作って、trainでの特徴量検討の部分を各自自由に進めるという形を試みました。連絡にはslackを使い、特徴量の検討状況はスプレッドシートにまとめるという形にしました。ただ年末で忙しかったのか、はたまた題材が悪かったのか、フォローが足りなかったのか、全員脱落してしまって、気付いたらソロで戦っていました。
分析コンペでの学びは大きいと思うので引き続き布教・勧誘・拉致に励みたいと思います。
今後の取組
この記事でも書いた通り、ローカルマシンを購入しました。この投資回収の意味も込めて今年中にはmasterになりたいと思っています。
圧倒的にNN力が不足しているので、まずはCASSAVAコンペでpytorchの練習をしたいと思います。対戦よろしくお願いします。
