kaggle(UM-MCTSコンペ)振り返り(11th Place) &上位解法
自己紹介
Kaggle Competitions MasterのRyushiです！
- Kaggle account: https://www.kaggle.com/ryushisa
- X account: https://x.com/ryukwirt/
UM-MCTSコンペでは11thでgold medalを取りました。
本記事では、振り返りと上位ソリューションをまとめました！
UM-MCTSコンペとは
UM-MCTSコンペ（以下、本コンペ）では、あるゲームにおいて、異なるモンテカルロ木探索（MCTS）アルゴリズムのバリエーションがどの程度のパフォーマンスを発揮するかを予測するモデルを構築します。与えられるデータは、ゲームの特徴を記述したリストであり、それに基づいて各MCTSバリエーション同士の勝敗を予測するコンペでした。
タスク説明
72体のエージェントが1000以上のゲームで15、30、または45回対戦し、対戦の勝率を予測するタスクです。各レコードには、対戦エージェントの組み合わせ、勝利数、勝率、その他の特徴量が含まれています。
勝率は utility_agent1 カラムで表され、この値は -1 から 1 の範囲を取ります。-1 は全敗、1 は全勝を意味し、値が高いほど agent1 の勝率が高いことを示します。
上位解法
11th(ours)
手前味噌ですが、自分たちのものから書かせていただきます
solution link
CV戦略
総ゲーム数を基準とした StratifiedGroupKFold を使用しました。
ゲーム数によって分布が異なる可能性があるという議論を参考に、ゲーム総数で層化を行いました。
GameRulesetName と EnglishRules
ホストからテストデータには未知の GameRulesetName 値が含まれていると明言されていたため、GameRulesetName に対してTF-IDF特徴量を使用することはリスクがあると判断しました。
また、EnglishRules に関しては、「Ludus Coriovalli」のようなバリエーションを含むノイズが多いと分かりました。
したがって、GameRulesetName と EnglishRules を特徴量として使用しないことを決定しました。
Ryushiパート
UM Gradient Boosting Models Train&Infer をベースに構築しました。このノートブックは、LightGBM、XGBoost、CatBoostでの実験を非常に簡単に行える便利なものでした。最終的には CatBoost のみが最良の結果を出したため、これを使用しました。
特徴量
-
使用した特徴量
最良のシングルモデルでは約180の特徴量のみを使用しました。 -
削除した特徴量
- ユニークな値が1つしかない特徴量
- 95%以上が欠損値の特徴量
- 頻度ベースの特徴量と
_componentsカラム（すべて削除したわけではなく、情報量が多いと判断したものは残しました）。-
残したfrequency系の特徴量:
['DrawFrequency', 'StepDecisionFrequency', 'FromToDecisionEmptyFrequency', 'SetNextPlayerFrequency', 'RemoveEffectFrequency', 'MoveAgainFrequency', 'StepDecisionToEmptyFrequency'] -
残したcomponents系特徴量:
['NumStartComponentsBoard', 'NumStartComponentsHand', 'NumStartComponents', 'NumStartComponentsBoardPerPlayer', 'MarkerComponent']
-
残したfrequency系の特徴量:
-
多重共線性を考慮して削除した特徴量
以下のように相互相関が90%以上の特徴量を特定し、例えば以下のようなものは、ScoreDifferenceVarianceのみを残して他を削除しました。
['ScoreDifferenceVariance', 'ScoreDifferenceMedian', 'ScoreDifferenceMaximum', 'ScoreDifferenceChangeAverage', 'ScoreDifferenceMaxDecrease', 'ScoreDifferenceAverage', 'ScoreDifferenceMaxIncrease', 'ScoreDifferenceChangeLineBestFit']
こういった特徴量が結構多かったので、丁寧に除去しました。
-
追加した特徴量
-
LudRulesの長さ -
LudRulesのstart、play、end部分から作成した特徴量（詳細は2gパート参照） -
LudRules内に'Draw'、'Win'、'Loss'が登場する回数を抽出。
-
その他
- データ拡張(詳しくはktm part)
CV/LBスコア
| CV | Public LB | Private LB | |
|---|---|---|---|
| exp057 | 0.4092 | 0.422 | 0.432 |
| exp058 | 0.4087 | 0.422 | 0.432 |
| exp059 | 0.4070 | 0.422 | 0.432 |
| exp069 | 0.4082 | 0.424 | 0.432 |
| exp071 | 0.4079 | 0.424 | 0.432 |
ktmのパート
-
データ拡張:
agent1とagent2を入れ替え、1 - AdvantageP1と-utility_agent1を適用し、swapped flagカラムを追加。 -
マルチターゲット予測:
utility_agent1とdraw_ratioをCatBoostのMultiRMSE lossで予測。 -
データ生成:
公開されているLudii Portalのルールを使用し、追加のトレーニングデータを生成（約30,000～40,000行）。
CV/LB
| exp | CV | LB | private | target enc | Multi Target | additional data |
|---|---|---|---|---|---|---|
| exp084 | 0.4015 | 0.429 | 0.434 | ✓ | ✓ | |
| exp088 | 0.4006 | 0.427 | 0.433 | ✓ | ✓ | ✓ |
| exp094 | 0.4034 | 0.43 | 0.436 | ✓ | ✓ | |
| exp101 | 0.4016 | 0.429 | 0.435 | ✓ | ✓ |
2gパート
MCTS Starter を基に構築しました。以下の変更を加えて複数のモデルを準備しました：
-
データの追加:
agent1とagent2を入れ替えるデータを追加しました。 -
引き分けの予測: バイナリ分類を用いて引き分けかどうかを予測。引き分けの可能性が高い場合は、
utility_agent1を0に設定。 -
LudRules の分割とTF-IDFの適用: LudRules を
start、play、endの各セクションに分割し、それぞれにTF-IDFを適用しました。 -
特徴量の作成: LudRules の
start、play、endセクションから以下のような特徴量を作成：-
depth_nest: セクション内のネストの深さ（()や{}の数を用いて計算）。 -
num_condition: セクション内の"if"ステートメントの数。 -
chr_len: セクションの長さ。 -
unique_start_pieces: セクション内の"place"の出現回数。 - その他、多数の特徴量を作成。
-
CV/LB
| CV | Public LB | Private LB | |
|---|---|---|---|
| 017-1 | 0.4092 | unknown | unknown |
| 018-1 | 0.4073 | 0.422 | 0.431 |
| 024-1 | 0.4070 | 0.422 | 0.431 |
| 025-1 | 0.4094 | 0.422 | 0.430 |
Stackingパート
スタッキングを採用することで大幅にスコアを改善しました。FoldごとにCVが大きく異なる課題があり、スタッキングを単純なアンサンブルより効果的と判断。Optunaを使用して最適化した結果が以下です：
| CV | Public LB | Private LB | Experiments used in the stacking training | Fold 0 | Fold 0 CV | Fold 1 | Fold 1 CV | Fold 2 | Fold 2 CV | Fold 3 | Fold 3 CV | Fold 4 | Fold 4 CV |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0.3912 | 0.419 | 0.424 | ['ryushi_exp057', 'ryushi_exp058', 'ryushi_exp059', 'ryushi_exp069', 'ryushi_exp071', 'tsuji_017-1', 'tsuji_018-1', 'tsuji_024-1', 'tsuji_025-1', 'ktm084', 'ktm088', 'ktm094', 'ktm101', 'ktm084_draw', 'ktm088_draw', 'ktm101_draw'] | ['tsuji_025-1', 'ktm101', 'ktm088_draw'] | 0.3977 | ['ryushi_exp057', 'ryushi_exp058', 'ryushi_exp059', 'ryushi_exp069', 'tsuji_018-1', 'tsuji_024-1', 'tsuji_025-1', 'ktm084', 'ktm088', 'ktm094', 'ktm088_draw', 'ktm101_draw'] | 0.3677 | ['ryushi_exp059', 'tsuji_018-1', 'ktm084_draw', 'ktm101_draw'] | 0.38142 | ['ryushi_exp057', 'tsuji_017-1', 'ktm084', 'ktm088', 'ktm084_draw', 'ktm101_draw'] | 0.40944 | ['tsuji_017-1', 'tsuji_024-1', 'ktm088', 'ktm094', 'ktm101', 'ktm084_draw', 'ktm088_draw'] | 0.39866 |
最終提出戦略
CVスコアとLBスコアを考慮して、以下2つの提出を選びました：
- CV+LB best: CVとLBが最良だったスタッキングモデル
- CV best: CVスコアが最良だったサブミッション
Tips
Nelder-Mead
Nelder-Mead法を使用して、各サブミッションの重みを最適化しました。この方法では、重みの合計が1でない場合でも、CV/LBスコアが向上しました（この時の重み合計は約1.14）。
3rd
二段階フリップ拡張スタッキングとコード
概要
データ拡張と安定したCV-LBパイプラインの構築（LBを重視）が鍵となりました。プライベートリーダーボードの変動がほとんどなく、公開データとプライベートデータが同じ分布であることが示されています。
solution link
データ拡張
- エージェント1とエージェント2のペアを反転（agent2-agent1に変更）
-
AdvantageP1を1 - AdvantageP1に変更 -
utility_agent1を-utility_agent1に変更 - その他の特徴量はそのまま保持
クロスバリデーション
StratifiedGroupKFold を GameRulesetName で実施し、utility_agent1 のマイナークラスを近隣クラスに変更しました。
特徴量エンジニアリング
- この素晴らしいノートブックからの特徴量を追加
-
EnglishRulesのTF-IDF-SVD特徴量を追加し、max_featuresの最適パラメータをLBスコアに基づいて調整
特徴量選択
Null Importance Feature Selectionを使用し、ターゲットシフト時に大きく変動する特徴量を除去しました。
ハイパーパラメータチューニング
Optunaを用いてLightGBMとCatBoostの最適なハイパーパラメータを探索しました。
モデル
二段階モデルを採用：
- 第一段階：フリップ拡張データを使用して元のトレインデータとテストデータを予測
- 第二段階：アウトオブフォールド（OOF）予測を特徴量として利用
アンサンブル
最終提出はLightGBMとCatBoostを3つのシードで平均化してブレンドしました。
ポストプロセッシング
最終予測の平均値が元の値より低かったため、係数（1.12）を掛けてLBスコアを0.002改善しました。
効果がなかった方法
- LudRulesのTF-IDF
- BERT埋め込み
- より多くのエージェント1-エージェント2ゲームグループを用いた疑似ラベル
- ニューラルネットワーク
ノートブック
まとめ
このソリューションは、データ拡張と安定したモデル構築に重点を置き、効果的な特徴量エンジニアリングとハイパーパラメータのチューニングを組み合わせることで高いパフォーマンスを達成しました。特に、二段階のスタッキングモデルとエンハンスドデータ拡張手法が成果に寄与しています。
5th
このチームは２人で別のパイプラインを作って最後混ぜていました。
solution link
Anil's Pipeline
使用アルゴリズム
- CatBoost
-
Stratified Group 10-Fold Cross-Validation
- @yunsuxiaozi氏のスキームをベースとした方法。
データ拡張
- エージェント1とエージェント2をスイッチし、ラベル（アドバンテージとユーティリティ）を反転することで、学習データの拡張を実施。
- 推論時にも同様の拡張データを生成し、元の予測結果と平均を混ぜる。
スコア
- CV OOF: 0.4059 ～ 0.4030 (TTAあり)
- LBスコア: 0.421 / 0.427
特徴量エンジニアリング
- 調整済みアドバンテージを新たな特徴量として追加：
((pl.col("AdvantageP1") * pl.col("Completion")) + (pl.col("Drawishness")/2)).alias("adv_p1_adj") ((pl.col("AdvantageP2") * pl.col("Completion")) + (pl.col("Drawishness")/2)).alias("adv_p2_adj")
Sercan's Pipeline
Sercan's Pipelineは、CatBoost、LightGBM、DeepTablesを組み合わせた多彩なアプローチを採用していました。
モデルの概要
DeepTables
- Min-Maxスケーリング
- Group 6-Fold Cross-Validation
-
学習設定:
- Learning Rate Scheduler
- Adam Optimizer
- ネットワーク構造:
nets = ['dnn_nets'] + ['fm_nets'] + ['cin_nets'] + ['ipnn_nets'] hidden_units = ((1024, 0.0, True), (512, 0.0, True), (256, 0.0, True), (128, 0.0, True)) embeddings_output_dim = 4 embedding_dropout = 0.1 apply_gbm_features = True epochs = 7 learning_rate = 0.001
GBDT
- LightGBM と CatBoost を積み重ねた構造
- Group 5-Fold Cross-Validation
- TF-IDF特徴量を使用：
- EnglishRules、LudRules、agent1、agent2から抽出。
後処理
- 最終予測に対して後処理を適用。
- 加重アンサンブルを使用。
7th
ツリーとニューラルネットのアンサンブル
CV（クロスバリデーション）
-
課題：ゲーム数に基づく
GameKFとルールセット名に基づくGameRulesetNameKFのどちらがCVとLBに適しているか判断が難しい。 -
アプローチ：
- 最終的には
GameKF+Game+ ラベルでstratifyを採用。 - テストセットでは新しいゲームが支配的と考えたが、プライベートボードで最終的なアンサンブルの重みが機能しなかった可能性あり。
- 最終的には
データ拡張
-
フリップ拡張：
- 他のチームと同様に、エージェント1とエージェント2を入れ替え、
AdvantageP1とラベルも反転させる。 - これによりLBが約0.01改善。
- 他のチームと同様に、エージェント1とエージェント2を入れ替え、
-
テストタイムTTA：
- フリップデータを組み合わせて使用。
ツリーモデル
-
パフォーマンス：
- ツリーモデルはニューラルネットよりも優れ、LB上での結果が安定。
-
重要なポイント：
- 数値特徴量の手動クロス特徴量（乗算・除算など）をトップ20の数値特徴量で作成。
- トップ5、10、15までのクロスでCVとLBが大幅に改善。トップ25以降はLBが低下。
-
ターゲットエンコーディング：
- LBを0.001改善。
-
モデルの深さ：
- LightGBM：深さ16
- CatBoost：深さ10
-
過学習防止：
- LightGBMの
reg_lambdaを高め（例：10） - CatBoostの
random_strengthを高め（例：10）
- LightGBMの
-
DARTモード：
- CVは改善するがLBは低下。
-
GKF + GameのCVが不適切だった可能性あり。LBを信頼。
ツリーモデルの結果
-
LightGBM：
- 単一モデル：10フォールド
- LBスコア：419
- PBスコア：425
-
CatBoost：
- 単一モデル：5フォールド
- LBスコア：422
- PBスコア：428
- 最終的なアンサンブルへの貢献は限定的。
アンサンブル
-
シンプルなブレンド：
- LightGBM + CatBoost
- LBは約0.001改善。ただし、PBには改善なし。
ニューラルネットモデル（NN）
- 参考ノートブック：MCTS DeepTables + NN
-
アプローチ：
- Torchを使用してNNモデルを実装。
- トップ数値特徴量をビン化し、LightGBMのツリーレーフ特徴量（深さ5、200ツリー）を追加。
- CIN + FMをプーリング層として使用。
- ラベル拡張（マルチクラス）を適用。
-
パフォーマンス：
- LBが安定せず、CVでも劣る（
GKF + Game）。 - 幸運にも5フォールドのNNモデルでLB419、PB427を達成。
- ランダム性により通常LB約423。
- LBとPBが一致しているため、最良のLB NNモデルを使用。
- LBが安定せず、CVでも劣る（
ポストプロセッシング
-
最適化：
- OOF予測を用いて
a * x + b形式で全体のRMSEを最適化。
- OOF予測を用いて
アンサンブル戦略
-
ベストモデル：
- LB416、PB423
- LightGBM（10フォールド） + ニューラルネット（5フォールド）を重み1, 0.75でシンプルにブレンド。
今後の改善点
-
GKF + GamerulesetnameでのCVに戻し、CVとLBをテスト。 - OOFメソッドを用いたスタッキングの試行。
まとめ
このソリューションは、ツリーモデルとニューラルネットモデルのアンサンブルに重点を置き、データ拡張やクロスバリデーションの工夫を行いました。ツリーモデルの安定したパフォーマンスを活かしつつ、ニューラルネットの可能性も探求しましたが、最終的にはツリーモデルのブレンドが主な改善要素となりました。ポストプロセッシングやアンサンブルの工夫により、LBスコアを微調整しています。
反省(Prize圏との差)
個人的な反省です。
金圏上位の方々のsolutionを読んでいて、flip augmentationなどは気付けていたものの、single modelで力の差を感じました。
僕はcatboostしかまともにスコアが出せなかったですが、lightgbmやxgboostなどのgbdt系モデルやNN系で強いのを作っているチームが多くみられました。
僕らはスタッキングでかなり精度が上がることがわかっていたので、この辺りの多様性のあるモデルが作れていたらprizeも夢ではなかったのではないかと思うと悔しいです。
チームでの取り組み
ここからのパートはチームマージと、コンペ期間中どのようにチームメンバーとコミュニケーションを取っていたかなどを書きたいと思います。ほぼ日記のようなものです。
Solo期
僕が参戦したのは1.5ヶ月前くらいからですが、最初の2週間はsoloで取り組んでいました。この期間に何とかsilver圏まで順位を上げました。
Team期 (RYUSHI & ktm)
Solo銀にたどり着いたところでktmさんにmergeしていただきました。初回mtgでktmさんのEDA（probing含む）の鋭さに驚いたのを今でも覚えています。
その後関西kaggler会に参加し、二人ともKansai-kagglerをチーム名に入れたら金メダルを取った経験があったのでチーム名を”Kansai-kaggler”に変更しました。
Team期 (Kansai-kaggler)
残り3週間くらいで当時LBの近くにいた2gさんにmergeしていただきました。
やり取りは全てDiscordで行っていました。定例mtgを週1回設けるほかに、#もくもくというボイスチャンネルがあり、ここで黙々作業していたりもしました。大体僕は週4、5回開いていました。たまにチームメイトも入ってきてくれて、そこから突如mtgが始まり気づけば3時間みたいなこともありました笑
余談
その1
今回チームを組んでいただいた2gさんと一緒にmasterになることができました。実は二人とも金1、銀1だったので銀でもmasterのなれたのですが、終盤は金しか狙っていませんでした。この意識が金メダルにつながったようにも思います。
僕と2gさんが同じタイミングでmasterに昇格したことで、HMSコンペの金圏が全てmaster以上になったのもエモかったです笑
その2
コンペが終わったその日に、チーム“miranory”のお二人と、ボードゲームカフェに行きました。序盤から意識していたチームであり、強かったです。コンペ終了直後に感想戦ができて楽しかったです。
Discussion