第 11 名解决方案 (majimekun)

这是 majimekun 团队的解决方案。majimekun 由 @niwatori、@akimaru 和 @keisho 组成。

这次竞赛 uniquely interesting（独特有趣）。我想向组织者表达感谢。然而，我们认为如果没有二分搜索组件，竞赛可能会更加引人入胜，从而允许更多样化的策略和创造性的问题解决。

总结

我们的解决方案主要归类为离线策略（offline policy）方法。采用离线策略的主要动机是，虽然拥有 7~9B 参数的大语言模型（LLM）可能难以基于 20 个问答对做出准确的猜测，但它在回答单个关键词和问题对时表现良好。

我们预先准备了关键词列表、问题列表、所有（关键词，问题）对的概率表以及关键词的先验概率。在推理过程中，我们通过最小化条件熵来得出最佳问题，并猜测最大似然的关键词。我们的关键词列表是使用 LLM 生成的，问题列表是从公开回放和 LLM 获得的，概率表是由 LLM 计算的。

根据 @lohmaa 提供的精彩统计数据，我们在评估期间纯 LLM 猜测者（Guesser）的胜率如下（需要注意的是，获胜概率取决于配对的回答者）：

• submission_id=39526145 (K=10): 3/14 (21.4%)
• submission_id=39527069 (K=400): 5/40 (12.5%)

其中 K 是一个限制关键词最大和最小先验概率之间比率的参数。

回答者 (Answerer)

回答者组件相对 straightforward（直接）。它由一些基于规则的逻辑和三个 LLM 之间的多数投票组成。

规则库 (Rulebases)

如果问题匹配以下正则表达式，回答者将进行响应：

• startswith 和 endswith: (starts|start|begins|begin|end|ends) with the letter [\'"]?([a-zA-Z])[\'"]?\?$
• contains: (includes|include|contains|contain) the letter [\'"]?([a-zA-Z])[\'"]?\?$
• 字典顺序： keyword.*(?:come before|precede) \"([^\"]+)\" .+ order\?$

字典顺序的正则表达式也捕获了 Agent Alpha 类型的问题。

大语言模型 (LLMs)

如果问题无法通过规则库回答，我们依赖三个 4-bit 量化 LLM 的多数投票：gemma-9B、llama3.1-8B 和 mistral-7B。

我们假设在这种嘈杂的环境中，多数投票比使用单个 8-bit 模型更 robust（稳健），所以我们选择了使用这三个模型。最初考虑了四个模型，包括 phi-3-small，但在粗略模拟后，我们选择了最终的三个模型。

由于同时加载两个以上的模型会超出 GPU 内存限制，我们为每次推理加载和卸载模型。我们通过旋转推理顺序（如 ABC/CAB/BCA/…，其中 A、B 和 C 代表每个模型），将每回合的模型加载次数从三次减少到两次。

最初，我们使用通过汇总代表 token 的贡献获得的模型输出概率。然而，这种方法的表现不如基于文本生成的简单多数投票。可能是我们在实现中的概率计算缺少了一些 token。

猜测者 (Guesser)

我们的猜测者基于离线策略。我们准备了关键词列表、问题列表、关键词和问题对的概率表，以及每个关键词的先验概率。

推导最佳问题和最佳关键词遵循直接的逻辑。给定已知的问答对列表，最佳问题通过最小化条件熵来确定：

其中 \(k\) 代表关键词，\(q\) 代表问题，\(q_1,...,q_t\) 是已经问过的问题（和答案）。这是使用贝叶斯定理计算的，数值计算的复杂度为 O(KQ)，其中 K 是关键词数量，Q 是问题数量。

最佳关键词可以通过以下方式得出：

我们还结合了关键词的先验概率 \(p(k)\)。推导先验概率的逻辑在下一节中描述。

关键词列表生成

关键词列表在离线策略中至关重要，因为我们无法猜测不在列表中的关键词。然而，关键词越多，就越难找到正确答案。糟糕的关键词会对问题选择和实际猜测产生负面影响。因此，我们必须在一定程度上找到 recall（召回率）和 precision（精确率）的良好平衡。

为了评估关键词列表的质量，我们将公开关键词随机分为训练关键词列表和验证关键词列表。我们仅使用训练关键词生成关键词列表，并使用验证列表评估 recall 和 precision（或词汇数量）。

我们尝试了各种生成关键词列表的方法：

• 使用 WordNet 中 physical_entity.n.01 的所有后代
  • Recall: ~46%, 词汇大小：~35000
• 使用训练关键词在 WordNet 中的邻居（例如，每个关键词的父节点的子节点）

最终，我们发现使用 LLM（ChatGPT 和 Gemini）生成关键词产生了出乎意料的更好质量。我们假设 Kaggle 主办方也使用了 LLM 来生成他们的关键词列表。通过提供一部分训练关键词作为 few-shot 示例，我们重复该过程多次收集关键词。

使用 LLM 的另一个优势是，我们可以根据 LLM 生成关键词的频率来估计其在公开/私人关键词列表中出现的可能性。我们发现精确率和频率之间存在明显的相关性。利用这种相关性，我们基于这些频率定义了先验概率，并将其纳入最佳问题和猜测计算中。得益于先验概率，我们可以在保持词汇数量的同时有效地提高精确率。

下图显示了随着频率阈值的变化，验证关键词列表的关键词数量和 recall。最右侧的点对应 frequency>=2。经过粗略的本地模拟，我们选择 2 作为阈值。

在 LLM 的帮助下移除明显的非对象关键词后，我们的最终关键词列表包含约 32,000 个条目。

问题列表生成

由于最佳问题是自动推导的，拥有更多问题可以提高猜测者的性能。瓶颈在于计算 p(keyword, question) 概率表的计算资源。

我们准备了以下来源的问题：

• 规则库，例如“这个词以'a'开头吗？”
• 从公开对局记录中收集的问题
• 由 LLM 生成的问题

最终的问题列表包含约 1,000 个问题。

一个遗憾是我们应该添加更多问题。根据回放记录，我们的机器人有时会结束于询问许多"startswith"问题，可能是因为问题太 coarse（粗糙），没有更有用的问题了。

概率表标注

我们需要 p(question="yes"|keyword)，即每个关键词和问题对的“yes"回答概率。
我们假设环境中的许多回答者使用 LLM，平均而言，本地使用 LLM 计算的 p(keyword, question) 与实际环境不会有显著差异。因此，我们使用了四个 LLM 的平均概率：gemma-9B、llama3.1-8B、mistral-7B 和 phi-3-small。我们通过汇总"yes"、"right"、"correct"及类似术语的 token 概率来得出"yes"概率。
我们使用 vLLM 来加速除 gemma-9B 之外的所有模型的推理（因为 OOM 或其他原因）。此过程需要相当数量的计算资源。

Agent Alpha

我们在两个机器人中都包含了 Agent Alpha 功能。词汇表是来自 WordNet 和猜测者中使用的关键词列表的简单组合。词汇表大小约为 173,000。

一个遗憾是，既然我们可以预测会有许多具有 Agent Alpha 功能的机器人，并且找到答案的步数强烈影响二分搜索机器人之间匹配的胜率，我们应该更仔细地改进 Agent Alpha 部分。这可能包括更深思熟虑地选择关键词列表，或者如上所述基于先验概率优先考虑可能的单词。