7th Place Solution SA SA SA

第 7 名解决方案 SA SA SA

作者: Max2020 (Grandmaster)
发布时间: 2025-02-04
竞赛排名: 第 7 名

感谢 Kaggle 主办方设计了精彩的竞赛题目。我玩得很开心。

以前没有深入参加过 Santa 竞赛，所以在比赛初期找了一本 Sean Luke 写的《Essentials of Metaheuristics》。读完之后深受启发。基于书中的知识，我设计了以下解决方案。我将由简入繁地描述我的方案设计过程，希望能帮助像我这样的新手。

太长不看 (TL;DR)：结合迭代局部搜索 (ILS) 与模拟退火 (SA)，并利用剪枝距离矩阵、缓存机制和分布式并行计算，高效评估离散序列排序问题的解决方案。

模拟退火搜索 (SA Search)

我从一个基础的模拟退火 (SA) 方法开始，它包含三个关键组件：

温度随每一步降低。
当前解决方案 undergoes 微调 (tweak)。
如果微调后的解决方案更好，则接受；否则以一定概率接受。

# 1. 初始化
# 2. 当温度高于停止阈值时：
    # 2.1 生成邻居解决方案：neighbor_solution = tweak(cur_solution)
    # 2.2 如果邻居更好，接受它。
    # 2.3 如果邻居更差，以一定概率接受；
    #       否则，保持当前解决方案。
  
    # 2.4 降低温度。

微调操作的设计

我设计了多种邻域操作（微调操作），包括：
- 插入 (Insertion)：将长度为 \(m_1\) 的连续子序列插入到另一个位置。
- 交换 (Swap)：选择并交换两个长度为 \(m_2\) 的子序列。
- 局部洗牌 (Local Shuffle)：随机打乱长度为 \(m_3\) 的片段。
为了高效生成所有可能的扰动，我预计算了所有潜在扰动的索引，并使用 NumPy 索引一次性检索所有可能性。
- 当 \(m_1, m_2 = 1\sim20\) 且 \(m_3 = 1\sim5\) 时，每次微调生成约 50 万个候选解决方案。
- 当 \(m_1, m_2 = 1\sim65\) 且 \(m_3 = 1\sim5\) 时，每次微调生成约 100 万个候选解决方案。
这些邻域操作创造了大量的排列。在每一步中，我使用批处理来一次性推断和评估 \(k\) 个随机候选者（其中 \(k\) 范围为 1000 到 5000）。

批量邻域搜索

考虑到大型语言模型中矩阵操作的计算优势，我旨在通过执行批量评估而不是在循环中一次处理一个句子来最大化推理效率。因此，我不是微调单个邻居并评估它，而是微调一大批邻居并选择最好的一个。

如果最好的邻居取得了更好的分数，则接受它。
否则，以一定概率接受次优解决方案以引入随机性并 escape 局部最优。如果接受，则从前 10 个候选者中随机选择一个解决方案。

现在的 SA 搜索伪代码如下：

# 1. 初始化
# 2. 当温度高于停止阈值时：
    # 2.1 生成一批邻居解决方案：neighbor_solutions = tweak(cur_solution)
    # 2.2 执行批量推理：neighbor_scores = batch_infer(neighbor_solutions)
    # 2.3 如果有邻居更好，接受最佳解决方案。
    # 2.4 如果没有邻居更好，从前 10 名中概率性地接受次优解决方案。
    # 2.5 降低温度。

多轮模拟退火搜索 (Repeat SA Search)

鉴于 100 词序列的邻域空间巨大，随机采样 \(k\) 个候选者可能仍然会错过更好的邻居。因此，我通过迭代应用 SA 来动态调整搜索粒度，增加每个温度步骤的尝试次数以进行更精细的搜索。

为了确定何时停止重复 SA 搜索，我引入了一个早停耐心机制 (early-stopping patience mechanism)。最初，耐心值很高，允许连续三次 unsuccessful 搜索。后来，耐心值降低，在后期阶段，单次 unsuccessful 搜索即终止过程。

重复 SA 搜索的伪代码如下：

# 1. 初始化耐心值和初始解决方案
# 2. 当耐心未耗尽时：
    # 2.1 初始化起始温度
    # 2.2 当温度高于停止阈值时：
        # 2.2.1 每个温度步骤执行多步：
            # 2.2.3 生成一批邻居解决方案。
            # 2.2.4 执行批量推理。
            # 2.2.5 如果最佳解决方案更好则接受。
            # 2.2.6 否则，从前 10 名中概率性地接受次优解决方案。
            # 2.2.7 降低温度。
    # 2.3 记录 unsuccessful 尝试。
    # 2.4 增加每个温度的步数。

迭代局部搜索 (ILS)

重复 SA 搜索倾向于陷入局部最优，需要大扰动 (large perturbation)来 escape。然而，过度的扰动会将搜索减少为随机探索，而不足的扰动则无法 escape 局部最小值。

我采用的扰动策略涉及随机选择 perturb_rank 个位置并打乱这些位置中的单词。

我设置了初始 perturb_rank 为 35。如果当前局部搜索产生的结果优于之前的最佳结果，我将 perturb_rank 缩放一个因子并继续搜索。

ILS 伪代码如下：

初始化参数
while True:
    cur_sent = perturb(cur_sent, perturb_rank)
    local_bst = cur_sent 周围的局部搜索 (即重复 sa 搜索) 

    if local_bst < global_bst:
        perturb_rank *= 2/3
        更新 cur_sent 和 global_bst
    elif local_bst < prev_local_bst:
        perturb_rank *= 5/6
        更新 cur_sent
    elif local_bst >= prev_local_bst:
        perturb_rank = 35

高效分数缓存

为了避免冗余的困惑度 (perplexity) 计算，我使用了一个实现为字典的分数缓存 (score cache)，其中键是句子表示，值是困惑度分数。

为了优化存储效率，我：

将单词编码为整数。
将整数列表转换为紧凑的二进制表示。
将它们存储为二进制数组，显著减少了内存使用。

为了支持可恢复的存储操作，磁盘访问是必要的。为了进一步加速磁盘读取和加载速度，我利用了 msgpack 包，这显著提高了性能。

这种方法将句子表示的存储空间从 685 字节 (字符串) 减少到 121 字节 (二进制编码)，增强了缓存性能。

剪枝 (Pruning)

使用距离矩阵进行剪枝

对于邻域内的大规模排序，计算成本巨大。如果有一种有效的方法事先剪枝邻域中的候选解决方案，搜索效率可以显著提高。

受语言模型朴素理解的启发，并以简单的 2-gram 模型为线索，我们假设句子的最终困惑度与其所有 2 词组合有关。这个假设允许我们将困惑度计算转化为旅行商问题 (TSP) 风格的距离计算。我们使用距离矩阵表示“城市”（即单词）之间的距离。例如，考虑一个由 100 个单词组成的文本 (text5)，由索引 0–99 表示；令牌 </b> 和 </s> 分别由 100 和 101 表示， resulting 距离矩阵大小为 102×102。(注意：由于某些单词重复，实际实现细节中省略了一些索引。)

然而，距离矩阵本身的初始化和动态演化提出了新的挑战。我采用了一个非常简单的方法：

记录局部最优：每次算法陷入局部最优时，我记录该解决方案，手动维护大约 20 个局部最优。
矩阵初始化：我创建一个空白距离矩阵，并将这些局部最优解决方案中存在的 2-gram 组合对应的单元格初始化为相对较低的值（例如 47）。对于从未出现在任何历史局部最优解决方案中的边，我将它们对应的矩阵条目初始化为较高的值（例如 100）。

使用 NumPy 和这个距离矩阵，可以在几百毫秒内排序和剪枝 100 万个候选解决方案——大致将搜索效率提高了 100 倍。

# self.paths[:, 0] = 100, self.paths[:, -1] = 101
self.paths[:, 1:-1] = ng.gen_all_neib(current)  
distances = np.sum(self.distance_matrix[self.paths[:, :-1], self.paths[:, 1:]], axis=1)  
sorted_idx = np.argsort(distances)

seled_idx = np.concatenate([
    sorted_idx[:int(5 * k / 6)],
    np.random.choice(
        sorted_idx[int(5 * k / 6):], k // 6, replace=False)
])  
neighbors = np.unique(self.paths[:, 1:-1][seled_idx], axis=0).tolist()

动态优化距离矩阵

上述手动维护的距离矩阵很容易偏向历史局部最优。理想情况下，距离矩阵应该动态更新和优化。在搜索过程中，对于困惑度低于某个阈值（例如 33、32 或 31）的解决方案，我们提取这些解决方案中包含的边，然后更新距离矩阵中的相应值。最后，距离矩阵中的每个单元格持有包含该特定边的所有解决方案的平均困惑度。

if min(uncached_scores) < int(self.globe_bst[0] + 2):  
    old = (self.distance_matrix <= int(self.globe_bst[0] + 2)).sum()  

    min_neighbors = [
        l1 for l1, l2 in zip(uncached_neighbors, uncached_scores)
        if l2 < int(self.globe_bst[0] + 2)
    ]  
    min_scores = [
        l1 for l1 in uncached_scores
        if l1 < int(self.globe_bst[0] + 2)
    ]  
    bst_miniseqs = [[100] + nei + [101] for nei in min_neighbors]  
    bst_miniedges = [extract_edges(miniseq) for miniseq in bst_miniseqs]  

    count_arr = np.ones(101 * len(bst_miniedges))  
    score_arr = np.repeat(np.array(min_scores), 101)  
    edges_arr = np.array(sum(bst_miniedges, []))  
    unique_edges, inverse_indices = np.unique(edges_arr, return_inverse=True, axis=0)  
    grouped_count = np.bincount(inverse_indices, weights=count_arr)  
    grouped_score = np.bincount(inverse_indices, weights=score_arr)  

    n0, n1 = zip(*unique_edges)  
    self.distance_matrix[n0, n1] = (
        self.distance_matrix[n0, n1] * self.count_matrix[n0, n1] + grouped_score
    ) / (self.count_matrix[n0, n1] + grouped_count)  
    self.count_matrix[n0, n1] = self.count_matrix[n0, n1] + grouped_count

我认识到这部分可能有点难以理解。更 refined 的方法是根据每个特定边的困惑度调整距离矩阵，而不是使用整个解决方案的 aggregate 困惑度来更新矩阵。我原本计划在后续版本中改进这一点，但幸运的是，这个版本已经实现了 28.5 的最终困惑度。

我提供了方法的高层概述，但可能还有一些我没有讨论的额外实现细节。如果你好奇，我的源代码可用。

查看源代码 https://www.kaggle.com/code/max2020/santa24-7th-place-solution