第 13 名解决方案 - XGBoost 集成

作者: Gabor Balazs
发布日期: 2024-12-03
竞赛: UM - MCTS 变体游戏博弈强度竞赛
排名: 第 13 名

UM - MCTS 变体游戏博弈强度竞赛第 13 名解决方案

我要感谢所有组织者和参与者，这次竞赛是一次极好的经历。意外且幸运地是我获得了第 13 名，因为我从许多公开排行榜 (LB) 得分均为 0.420 的模型中，挑选出了唯一一个私有排行榜 (PB) 得分为 0.425 的模型（除了冠军模型外，其他模型在 PB 上的得分均为 0.426）。

方法概述

我的最终模型采用了三个集成模型的中位数，每个集成模型由来自 10 折交叉验证 (CV) 的 10 个 XGBoost (XGB) 回归器的线性组合形成。如图所示：

       ┌─► 10 折 CV ─► 10 个 XGB ─► 线性组合 ─► 1 个模型 ─┐
数据 ─┼─► 10 折 CV ─► 10 个 XGB ─► 线性组合 ─► 1 个模型 ─┼─► 中位数
       └─► 10 折 CV ─► 10 个 XGB ─► 线性组合 ─► 1 个模型 ─┘

我还使用了代理翻转 (agent-flip) 数据增强、一些特征工程，并试图通过 Bagging、列子采样 (column sub-sampling) 和 boosting 过程中的早停 (early stopping) 来避免过拟合。所有 XGB 模型的输出也被 clipping 到目标范围 [-1,1]。

提交细节

我删除了所有空值和零方差特征。我还依次删除了与另一列相关性至少为 95% 的列。

代理翻转数据增强

与其他人类似，我也交换了 train 数据中的 agent1 和 agent2 列，将 AdvantageP1 列反转为 1-train['AdvantageP1']，并翻转目标 utility_agent1 的符号（我最后没有使用 num_wins_agent1 和 num_losses_agent1 字段）。起初，以及为了训练最终模型，我只对对称游戏 (train['Asymmetric'] == 0) 使用了这种增强，因为我担心创建“太不现实”的场景。后来我对所有数据进行了增强，但我的 XGB 线性组合只能达到 0.422 的分数（我承认这方面调优较少）。我提交的第二个最终模型（10-10 个 LGB 和 XGB 模型的集成）是在所有增强数据上训练的，其 LB 得分 0.421 最终在 PB 上达到 0.428。

特征工程

区分代理游戏体验的唯一特征是 AdvantageP1。至少我阅读了其他随机播放行为指标的 ludii 代码，发现它们对代理是对称的。因为我在 boosting 中使用了相当激进的列子采样以防止游戏记忆化，我想确保这个特征被选中的概率更高。因此，我通过将其与高 gain 重要性的特征混合，添加了以下变体（X 是处理过的 train 数据）：

X = X.with_columns([
    pl.Series('SgnAdvP1MulGameTreeComplexity',
              (X['AdvantageP1']-0.5) * X['GameTreeComplexity']).clip(-300, 300),
    pl.Series('SgnAdvP1MulBalance', (X['AdvantageP1']-0.5) * X['Balance']),
    pl.Series('SgnAdvP1DivVariance1',
              (X['AdvantageP1']-0.5) / (2.0-X['OutcomeUniformity'].clip(0,1))),
    pl.Series('SgnAdvP1DivDrawFrequency',
              (X['AdvantageP1']-0.5) / (1.0+X['DrawFrequency'].clip(0,1))),
    pl.Series('SgnAdvP1MulCompletion', ((X['AdvantageP1']-0.5) * X['Completion'])),
    pl.Series('SgnAdvP1PerPlayoutsPerSeconds',
              (X['AdvantageP1']-0.5) / (X['PlayoutsPerSecond'] + 1e-4)).clip(-0.5, 0.5),
    pl.Series('SgnAdvP1DivDurationTurnsNotTimeouts',
              (X['AdvantageP1']-0.5) / (X['DurationTurnsNotTimeouts']+1e-6)).clip(-0.5, 0.5),
    pl.Series('SgnAdvP1MulBranchingFactorMedian',
              (X['AdvantageP1']-0.5) * X['BranchingFactorMedian']).clip(-90, 90),
    pl.Series('SgnAdvP1MulBranchingFactorAverage',
              (X['AdvantageP1']-0.5) * X['BranchingFactorAverage']).clip(-100, 100),
])

我删除了许多主要描述棋盘物理特征的特征，因为它们在 gain 特征重要性指标上表现相对较高（前 50-100 名），我不相信它们能很好地泛化：

X = X.drop([
    'PieceNumberAverage', 'PieceNumberMaximum', 'NumPlayableSitesOnBoard'
    'NumColumns', 'NumRows', 'NumCorners', 'NumOuterSites', 'NumLayers',
    'NumVertices', 'NumTopSites', 'NumRightSites', 'NumCentreSites',
    'NumConvexCorners', 'NumConcaveCorners', 'NumPhasesBoard',
    'NumContainers', 'NumComponentsType', 'NumStartComponentsBoard',
    'NumStartComponentsHand', 'NumStartComponents',
])

我还使用了这些特征以避免因之前的删除而丢失所有信息：

X = X.with_columns([
    pl.Series('IsSquaredBoard', X['NumRows'] == X['NumColumns']),
    pl.Series('PlayoutsPerMoves',
              X['PlayoutsPerSecond'] / (X['MovesPerSecond']+1e-6)).clip(0, 1),
    pl.Series('PieceNumberRatio', X['PieceNumberAverage'] / X['PieceNumberMaximum']),
    pl.Series('AverageTurns', X['NumPlayableSitesOnBoard'] / X['PieceNumberAverage']),
    pl.Series('ActionsPerTurn', X['DurationActions'] / X['DurationTurns']).clip(1, 300),
])

最后，我还删除了 GameRulesetName、EnglishRules 和 LudRules 列。不幸的是，我无法利用它们。

Boosting

我使用了 StratifiedGroupKFold 进行 10 折交叉验证，按 GameRulesetName 分组，并使用整数类标签 (y_data*10).round(decimals=0).astype(int) 进行分层。我的三个 boosting XGB 回归器的参数非常相似（括号中显示了差异）：

max_leaves=[250, 200, 250], max_depth=[35, 30, 35],
n_estimators=[3500, 4000, 3500], learning_rate=[0.04, 0.03, 0.04],
subsample=[0.9, 0.75, 0.9], colsample_bylevel=0.5, colsample_bynode=0.25,
min_child_weight=25, min_split_loss=1e-4, reg_lambda=2.0, reg_alpha=4.0,
max_bin=64, max_cat_threshold=32, grow_policy='lossguide', enable_categorical=True,

我使用了大量的叶子和相当的深度，所以我试图通过列子采样来抵消潜在的过拟合，这使得每次分割只留下 0.5 * 0.25 = 0.125 部分的特征。正则化参数来自早期的网格搜索运行，但我最后只调整了前三行的参数。我对第一个模型使用了 10% 的训练数据进行早停，最小 delta 为 1e-5，而其他两个模型没有早停。每次 CV 训练都使用相同的数据洗牌种子和不同的估计器种子进行了几次 (3-5 次)，然后我为每个分割挑选了最佳模型以优化"CV 分数”。由于这对 LB 也有帮助，我将其合理化为我自己的随机重启技术。:)

线性组合（堆叠）

我使用最小化所有样本上 RMSE 的权重，线性组合了来自 CV 运行的 10 个 XGB 模型。为了考虑 clipping，首先我计算了 yhats 中所有模型的所有预测值（所以它是一个 10 行且列数与样本数相同的数组），然后使用以下代码最小化 RMSE（y 包含训练目标值）：

from scipy.optimize import minimize

def fobj(w):
    return (np.mean(np.square(np.clip(np.dot(w, yhats), -1.0, 1.0) - y))
            + 1e5 * min(0, np.min(w))**2)

w = np.ones(yhats.shape[0]) / yhats.shape[0]
res = minimize(fobj, w)
wopt = res.x
rmse_opt = calc_rmse(np.dot(wopt, yhats).clip(-1, 1), y)

也就是说，我从均匀权重开始搜索，惩罚负权重，并考虑了 clipping。最终模型中三个线性组合的结果如下：

wopt1 = [0.086247, 0.144699, 0.133306, 0.101278, 0.130589,
         0.136385, 0.076667, 0.139516, 0.108264, 0.106763]
wopt2 = [0.1059  , 0.14333 , 0.113467, 0.111721, 0.120991,
         0.137219, 0.097818, 0.12802 , 0.094427, 0.12176 ]
wopt3 = [0.115637, 0.109509, 0.119757, 0.126103, 0.134074,
         0.137645, 0.076969, 0.118834, 0.125846, 0.098289]

它们的总和分别为 1.164、1.175 和 1.163，所以最终我也像其他人提到的那样推高了预测值。我没有考虑非线性组合，因为我太担心过拟合了。

其他事项

LightGBM (LGB) 和 CatBoost (CAT)

我经常使用 LGB 来调整其参数，然后将类似的设置应用到 XGB 和 CAT。LGB 在 CPU 上的运行速度是其他模型的两倍多，所以我可以将 GPU 配额保留给最有希望的运行。我设法将 LGB 和 CAT 模型在 LB 上的得分降低到 0.421，但我只设法让 XGB 模型达到 0.420。事实上，我最终模型集成中的每个 XGB 组合都达到了 0.420，因此我选择了这个而不是 LGB-XGB-CAT 变体（它们在 PB 上各自得分为 0.421，合计为 0.420，但在 PB 上合计仅为 0.426）。

失败的尝试

与第 9 名解决方案类似，我也尝试使用传递性进一步增强数据，即如果代理 A 总是战胜代理 B，而代理 B 总是战胜代理 C，那么代理 A 应该总是战胜代理 C。我只对对称游戏考虑了这一点，甚至应用了多次迭代规则并删除了出现矛盾的所有情况，但这对 CV 没有帮助，最终使 LB 分数增加了 0.002。
我尝试使用一些游戏属性添加最近邻特征，但通常最终 CV 分数较差，遭受过拟合之苦。
由于线性组合权重的总和大于 1，并且在 LB 上具有强大且一致的优势，我有点担心私有数据中不会出现相同的偏差。所以我希望通过为对称和不对称游戏训练单独的模型来减少这种情况（第二种情况的模型要小得多），但它在 LB 上的表现总是差得多（大约 0.428），所以我放弃了这个想法。
我尝试将预测值限制为训练数据中出现的值，但这实际上增加了我的 CV 误差。
我尝试使用对称预测的平均值（甚至仅针对对称游戏）来进行测试数据的代理翻转增强，翻转模型输出的符号，并将其与正常预测平均。但这使我的 LB 分数降低了 0.001，所以我放弃了这个想法。
我还尝试使用 LudRules 列在预测时检测我是否在训练中见过该样本，如果是，则使用更激进的模型（甚至可以使用 LudRules 列），但这并没有提高我的 LB 分数。正如竞赛主持人提到的，训练数据和测试数据之间没有重叠的游戏，所以这里没有什么 surprises。

13th Place Solution - XGBoost ensemble