蒙特卡洛树自优化结合了大规模语言模型（LLMs）与蒙特卡洛树搜索（MCTS），以提升在复杂数学推理任务中的表现。通过结合系统性探索和启发式自优化机制，MCTSr解决了LLMs在策略和数学推理方面的局限，从而增强了LLMs内部的决策框架，使其更适应复杂任务。

我用LangChain实现了这个项目，代码在Github上。

蒙特卡洛树搜索（MCTS），简称，是一种在游戏和复杂的决策过程中使用的决策算法。它通过构建搜索树并模拟结果来估算行动的价值。该算法包含四个关键阶段。

1. 选择：从根节点开始，算法根据特定策略（例如：UCT（Upper Confidence Bound，UCB）在树上的应用）导航到有希望的子节点，直到达到一个叶节点为止。
2. 扩展：在叶节点处，如果它不表示游戏的终局状态，会添加一个或多个可行的新子节点，以展示潜在的未来行动。
3. 模拟或评估：从新添加的节点开始，算法通过随机选择动作进行模拟，直到游戏结束为止，从而评估节点的潜力。
4. 反向传播：模拟结束后，结果（胜利、失败或平局）被回传到根，更新每个访问节点的统计数据，以指导未来的决策。

UCT算法（即应用于树的上置信界算法）在MCTS选择阶段中扮演着关键角色，通过平衡探索与利用，选择使以下公式最大化的行为：

$
\text{[此处应填入原文中的公式，具体公式未给出，因此保持原文表述]}
$

该公式为：

其中 X¯ j 是行动 j 的平均奖励值，NC 是父节点被访问的总次数，n_j 是节点 j 在模拟过程中被访问的次数，C 是一个常数，用于平衡探索与利用之间的关系。

MCT 自我精炼（MCTSr）算法结合了蒙特卡洛树搜索（MCTS）与大型语言模型，通过迭代过程来精炼数学问题的答案。该算法将此精炼过程以搜索树的形式呈现，其中节点表示不同答案版本，边则表示对答案改进的尝试。

MCTSr的操作流程遵循MCTS的一般模式，遵循MCTS的一般模式。

1. 问题实例：问题 P 是正在处理的问题。
2. 节点集：A 是节点的集合，每个节点代表了问题 P 的可能的答案。
3. 行动集：M 是每个节点可用的动作集合，表示对答案进行可能的自我修改。
4. 奖励函数：R 根据修改的质量和有效性为节点自动生成奖励。
5. 自奖励存储：Ra 存储给定节点的自奖励采样结果，通过 R 函数实现。
6. 终止条件：T 确定何时停止搜索过程，例如达到最大迭代次数或达到满意的答案质量水平。
7. 值函数：Q(a) 根据累积奖励 Ra 和从子节点的反向传输估计答案节点 a 的价值。
8. 上置信界 (UCB)：U(a) 平衡利用与探索之间的关系，通过考虑价值函数 Q(a) 和访问节点 a 的次数 N(a)。
9. 父节点：Father(a) 返回节点 a 的父节点，如果 a 是根节点则返回空值。
10. 子节点：Children(a) 返回节点 a 的所有子节点集合，表示通过执行动作 m ∈ M 从 a 生成的所有可能状态。
11. 访问计数：N(a) 是访问节点 a 的总次数，用于计算其 UCB 值并评估探索和利用的程度。

通过迭代地通过自我反思驱动的自我提升并利用函数 R 抽取奖励来优化答案，MCTSr 力图找到解决数学问题的高质量方案。

算法的工作流程如下所示：

• 初始化步骤： 使用朴素模型生成的答案和一个虚拟响应（“我不知道”）建立一个根节点，以减少模型过拟合的可能性。
• 选择： 使用一个值函数Q对所有未完全扩展的答案进行评分。选择最高分的节点，通过贪心算法进一步探索和优化。
• 自我改进： 选定的答案通过Self-Refine框架进行优化，生成反馈m，指导优化过程，以生成更好的答案a’。
• 自我评估： 评估优化后的答案来采样奖励值并计算其Q值。根据模型的自反馈奖励以及其他约束，

1. 提示约束：在奖励评分时要严格遵守标准。
2. 满分抑制：将超过95分的奖励减去一个固定的数值。
3. 重复采样：多次采样节点的奖励来提高可靠性。

其中 Q(a) 是答案 a 的质量值。Ra 是 a 的奖励样本集合，min Ra 表示 Ra 中的最小奖励值，|Ra| 表示 Ra 的样本数量，而 Σ Ri a (i=1 到 |Ra|) 表示 Ra 中所有奖励的总和。

• 反向传播: 将精炼的答案的值反向传递给父节点及其他相关节点，以便更新树的值信息。如果任何子节点的Q值发生变化，则更新父节点的Q值。将子节点的Q值变化反向传递给父节点，以更新其Q值。

其中 Q′(a) 是考虑了其子节点影响后更新的答案 a 的质量值，Q(a) 是仅考虑奖励采样的初始质量值，而 maxi∈Children(a) Q(i) 表示 a 的所有子节点中质量值最高的那个。

• UCT 更新: 在更新所有节点的 Q 值之后，选出一组候选节点 C，以供进一步扩展或选择。利用 UCT 更新公式来更新所有节点的 UCT 值，为下一轮的选择做准备：

其中，Q(a) 代表答案 a 的 Q 值，N(·) 表示所有给定节点的总访问次数，c 是一个平衡探索和利用的常数，ϵ 是一个小常数，可以防止除以零的情况。

• 终止条件: 搜索会在满足一个或多个条件时结束，例如：

1. 早停：搜索改进减少或连续搜索结果重复。

2. 搜索限制：达到预设的展开次数或最大搜索深度限制。

3. 基于语言模型Logits的高级标准：达到语言模型Logits中预定义的指标。

一旦满足终止条件，根据Q值或其它标准从各个节点中收集最佳响应。

MCTSr在GSM数据集上的表现是，

• MCTSr的部署数量与成功率之间存在直接关联，特别是在GSM8K数据集中。
• 随着迭代次数的增加，GSM8K的成功率显著提高。
• 在GSM-Hard数据集中，即使增加部署数量，性能上限依然存在，这表明当前策略在处理复杂问题时有一定的局限性。

MCTSr、在MATH数据集上的表现如何

• 一级表现：进行 8 次滚动的 MCTSr 实现了 90.16% 的成功率，成功解决了 437 个问题中的 394 个。
• 五级表现：进行 8 次滚动的 MCTSr 实现了 34.06% 的成功率，成功解决了 1324 个问题中的 451 个。
• 总体表现：进行 8 次滚动的 MCTSr 实现了 58.24% 的累计成功率，解决了 5000 个问题中的 2912 个。这比零样本 CoT 初始的成功率为 24.36% 有了显著的提升。
• 随着滚动次数的增加，成功率也相应提升。

MCTSr在奥运级别数据集上的性能

封闭源代码大规模语言模型在数学数据集上的性能

• MCTSr 在所有三个数据集上始终优于零样本推理。
• 增加回放次数直接与更高的成功率（%）相关联，展示了该算法学习和优化其解决方案的能力。
• AIME: 零样本推理：2.36% 的成功率（解决了 22 个问题）。MCTSr（8 回放）：11.79% 的成功率（解决了 110 个问题）。
• GAIC 数学奥德赛：零样本推理：17.22% 的成功率（解决了 67 个问题）。MCTSr（8 回放）：49.36% 的成功率（解决了 192 个问题）。
• OlympiadBench：零样本推理：1.25% 的成功率（解决了 16 个问题）。MCTSr（8 回放）：7.76% 的成功率（解决了 99 个问题）。

获取通过蒙特卡洛树搜索自我优化的GPT-4级别数学奥林匹克题解 (2406.07394)

想了解更多见解吗？

不要错过这个系列中其他有趣的讨论。只需点击这里，发现最新的研究成果！

赶紧订阅，每周都能收到更新!!