Santa24 第 10 名 - 我的心得

引言

首先，我要感谢组织者使这次比赛成为可能，并感谢我的队友 @titericz、@deeper、@lucienderubempre 和 @nlztrk 对我们团队最终结果的贡献。我还要感谢那些公开分享他们的想法、结果、实验和代码的人们。我从公开的 Notebook 中学到了很多新东西，从数学到编程。

以下是我对这次比赛的个人看法。这不是一份详尽的报告，而是我决定分享的一些想法。也许我的队友可以在评论或其他帖子中补充一些内容。

在这次比赛中，我只使用了模拟退火（Simulated Annealing, SA）。取得好成绩的关键在于：

1. 实验 SA 的起始句子并选择合适的句子
2. 良好理解和控制 SA
3. 计算资源

我在比赛中期分享的 公开 Notebook 实际上与我最终使用的代码非常接近。最终稍加 refined 的版本可以在 GitHub 上找到。

详情

实验 SA 的起始句子并选择合适的句子

SA 起始句子的选择至关重要，因为在实际优化中，SA 算法通常无法从与起始句子差异太大的句子达到局部最小值，尤其是对于长句子。

最好的例子是第 5 个样本。在这次比赛早期就发现，带有停用词开头的排序文本 [停用词] + [字母排序文本] 具有约 48 的低困惑度（perplexity），是 SA 的一个相当好的起始句子。然而，从这样的起始句子出发，不可能达到金牌所需的困惑度。相反，有必要发现两个字母排序块可以导致具有更低困惑度的起始句子，并将其用作起始句子。两个字母排序文本块的想法是由 @woosungyoon 在 公开 Notebook 中公开披露的。在对公开 Notebook 进行一些实验后，我切换回自己的代码，并使用以下句子结构作为起始猜测：

[停用词（不含 and）] + [字母排序块 1] + [and and and] + [字母排序块 2]

其中两个字母排序文本块是随机采样的。从这样的句子开始，最终允许获得困惑度为 28.5 的解决方案。

良好理解和控制 SA

首先，我想提到在线迷你书籍 Simulated Annealing Afternoon，它提供了非常好的 SA 介绍。

邻域生成

生成邻域的两个主要操作是：

1. 交换两个词：12345 ⟶ 14325
2. 提取一个词并将其插入新位置：12345 ⟶ 13425

在比赛结束时，我只使用了这两个操作。在某个时刻，我发现仅对停用词使用相同的两个操作可能很有用。这允许在初始阶段加速具有许多停用词的句子的优化，但当停用词已经接近某些最佳位置时，这就不是很有用了。另一个我使用了一段时间的操作是循环旋转，即 12345 ⟶ 45123，这可能有助于找到样本 #2 的解决方案。

我没有看到使用公开建议的更复杂的邻域生成方式有任何好处。首先，当我尝试它们时，我没有看到结果改善。其次，它们通常可以从更基本的操作派生出来。最后，如果它们不能以合理的频率提供有用的邻域，它们会燃烧计算资源。这就是为什么如上所述，我最终只使用了两个基本操作 - (1) 交换两个词和 (2) 提取一个词并将其插入新位置。

理解 SA 基础

初始温度、最终温度、冷却计划、温度数量、每个温度的迭代次数（如果使用）、接受率监控等。所有这些都允许人们理解优化实际上在做什么，是否有效，并设计你想要的优化。

我使用了三种类型的 SA 运行，这是通过适当选择超参数设计的：

(a) 高温探索。在这种情况下，我从大温度开始，通常使用未优化的起始句子，并运行优化一段时间以找到一些有前景的局部最小值。

(b) 预热运行。尝试通过使用高起始温度增加困惑度来 escape 当前的局部最小值。

(c) 低温探索。SA 在低温下运行，试图在当前局部最小值附近寻找被忽略的东西。

这三种类型的 SA 运行的组合使我能够在这次比赛中取得进展。它简单而高效。

计算资源

计算资源在这次比赛中非常重要。如果最终答案是已知的且路径清晰，即使使用 Kaggle 慷慨提供的计算资源也可以得到它。然而，对新想法的快速实验、调整和理解 SA 算法等，严重依赖于可用的计算资源。

结语

即使是“有趣”的圣诞 Kaggle 比赛也可能很艰难，并且是学习的来源。我祝贺每一位能够在 2024 年 Santa 比赛中提高技能和扩展知识的人。