技术博客
首页 所有文章 标签 分类 关于
技术博客

目录

详细解释大模型逻辑推理中的mcts蒙特卡洛搜索树

 收录于 未分类
   约 8126 字   预计阅读 17 分钟 
https://bing.ee123.net/img/rand?artid=144702801

详细解释大模型逻辑推理中的mcts蒙特卡洛搜索树

答案

蒙特卡罗树搜索（Monte Carlo Tree Search, MCTS ）是一种用于解决复杂决策问题的算法，广泛应用于游戏和 其他需要战略规划 的场景。它通过随机化的方法在树状结构中探索可能的决策路径，以寻找最佳决策。MCTS的核心思想在于通过 探索（exploration）和利用（exploitation） 相结合，从而逐步优化决策过程。

MCTS的基本原理

MCTS的主要步骤包括：

  1. 选择 ：从 根节点开始，选择未完全展开 的节点，通常使用 贪心策略或基于

    上置信界（Upper Confidence Bound, UCB） 的方法来决定下一个要探索的节点。

  2. 扩展 ：在 选定的节点上 创建 一个或多个子节点 ，表示 可能的后续状态 。

  3. 模拟 ：从新扩展的 节点开始进行随机模拟 ，直到达到终止状态。这个步骤通常 通过随机选择行动来完成。

  4. 反向传播 ：将模拟结果反馈到 树中的所有父节点 ，以更新这些 节点的胜率 和访问次数。

通过多次迭代这些步骤， MCTS能够逐步收敛到最优决策 。

MCTS在大模型推理中的应用

在大语言模型（LLM）的推理过程中，MCTS被用来增强模型的逻辑推理能力。例如，研究者们提出了将MCTS与LLM结合的方法，如 MCT Self-Refine（MCTSr ），旨在提高模型在复杂数学推理任务中的表现。这种方法通过以下几个步骤构建 蒙特卡罗搜索树 ：

  • 初始化 ：使用模型生成的答案和 虚拟响应建立根节点 ，以减少 模型过度拟合 。
  • 选择 ：根据值函数Q对所有未完全展开的答案进行排序，并采用贪心策略选择值最高的节点进行进一步探索。
  • 自我修正 ：对 选定答案进行优化 ，通过 生成反馈 指导优化过程。
  • 反向传播 ：将优化结果反馈到树中，以更新各节点的信息。

这种结合使得模型不仅能够进行有效的自我评估，还能通过系统性的探索来提高推理能力，从而在解决奥林匹克级别数学问题时表现出显著优势

。

MCTS与逻辑推理能力

尽管大语言模型在逻辑推理方面存在争议，许多研究表明，通过引入MCTS等算法，可以显著提升其推理能力。MCTS提供了一种 结构化的方法 ，使得模型能够更好地处理复杂问题，而不仅仅依赖于模式匹配。这种方法论上的创新为未来AI的发展提供了新的方向，尤其是在需要高水平推理和决策支持的应用场景中

。总之，蒙特卡罗树搜索作为一种强大的决策工具，在提升大语言模型逻辑推理能力方面展现出了巨大的潜力。通过系统化的探索和优化，它为解决复杂推理任务提供了有效的框架。

Poe

蒙特卡洛搜索树（Monte Carlo Tree Search, MCTS）是一种广泛应用于决策过程和逻辑推理的算法，尤其在游戏 AI 和复杂决策问题中表现优异，例如围棋、国际象棋以及更广泛的规划和搜索问题。在大模型（如 GPT 系列）中，MCTS 也可以用于 逻辑推理 和 生成具有更好决策质量 的回答。以下是对 MCTS 的详细解释及其在逻辑推理中的应用。

蒙特卡洛搜索树的核心思想

MCTS 是一种基于 随机采样和树搜索 的算法，它通过 增量式地构建搜索树 来找到最优决策。MCTS 的核心思想是通过模拟（蒙特卡洛）对未来可能的状态进行评估，并逐渐集中搜索到更优的区域。其主要步骤包括 树的扩展 和 模拟评估 ，最终找到最佳策略。

MCTS 的工作流程

MCTS 的工作流程通常分为四个主要阶段，按顺序进行：

1. 选择 (Selection)

在现有的搜索树中，从根节点开始，按照某种策略（如 UCB1 算法）选择一个子节点，直到到达一个尚未完全扩展的节点。

  • UCB1（Upper Confidence Bound for Trees）公式 ：

  • https://i-blog.csdnimg.cn/direct/4539020fc500409a879e1f8625c4207a.png

    UCB=wini+Cln⁡Nni

  • UCB = \frac{w_i}{n_i} + C \sqrt{\frac {\ln N} {n_i}}

  • UCB=ni​wi​​+Cni​lnN​​

    • wiw_iwi​: 当前 节点的累计奖励。
    • nin_i ni​: 当前节点被访问的次数。
    • NN N: 父节点的访问次数。
    • CCC: 控制 探索与利用 平衡的参数。

    选择时会平衡“探索 未知的节点”（高潜力 ）和“ 利用已有的高奖励节点”（当前最优 ）。

2. 扩展 (Expansion)

当到达一个尚未完全扩展的节点时，为该节点添加一个或多个孩子节点。扩展的节点通常是当前状态的一个可能动作。

  • 如果当前节点是叶子节点，则选择一个可能的动作来扩展搜索树。

3. 模拟 (Simulation / Rollout)

从新扩展的节点开始进行随机模拟（Rollout），直到到达终止状态（如游戏结束或达到深度限制）。在模拟阶段，通常使用简单的随机策略来选择动作。

  • 模拟的结果会返回一个评估值，表示该路径的质量（例如，游戏胜利、失败或奖励值）。

4. 回溯更新 (Backpropagation)

将模拟结果沿着路径向上传播，并更新路径上每个节点的统计信息。

  • 每个节点会更新：
    • 访问次数 nin_ini​ ：该节点被访问的次数。
    • 累计奖励 wiw_iwi​ ：从该节点开始的路径的总奖励。

通过多次重复上述四个阶段，搜索树会逐渐集中在最优的决策路径上。

MCTS 的优点

  1. 无需完全模型 ：MCTS 不需要对问题的状态转移有完整的先验知识，只需能够模拟未来状态即可。
  2. 逐步改进 ：MCTS 是一种 anytime 算法，可以随着计算时间的增加逐步提高决策质量。
  3. 平衡探索与利用 ：通过 UCB1 等策略，MCTS 在未知区域的探索和已知区域的利用之间找到平衡。

大模型逻辑推理中的 MCTS

在大模型（如 GPT 系列）中，MCTS 可用于 增强逻辑推理能力 ，尤其是在需要从多个可能的推理路径中选择最佳路径的场景中。以下是具体的应用方式：

1. 生成多种 推理路径

  • 大模型可以根据 当前输入生成多个可能的推理路径 （类似于在树中扩展节点）。
  • 每条路径对应 搜索树中的一个分支 ，表示 不同的逻辑推理方向 。

2. 路径评估

  • 使用大模型对每条路径进行评估，类似于 MCTS 的模拟阶段。
  • 评估标准可以包括：
    • 推理的 逻辑性和一致性。
    • 与 上下文的相关性。
    • 目标达成的可能性。

3. 路径选择与扩展

  • 根据路径的评估结果，使用类似 UCB1 的策略选择最优路径进行进一步扩展。
  • 大模型可以辅助进行更深层次的推理，生成下一步的可能性。

4. 最终决策生成

  • 通过多次模拟和评估，找到最优的推理路径，并将其作为最终输出。

MCTS 在逻辑推理中的优势

  1. 解决多步推理问题 ：

    • 在复杂的逻辑问题中，推理路径可能包含多个步骤。MCTS 通过模拟和评估找到最优路径，避免了全局搜索的高昂计算成本。

  2. 提高推理质量 ：

    • 通过多次模拟和评估，MCTS 可以筛选出更高质量的推理路径，减少逻辑错误。

  3. 整合不确定性 ：

    • 当存在多种可能的推理路径时，MCTS 能够在不确定性中找到最优解。

示例：基于 MCTS 的逻辑推理

假设有这样一个逻辑推理问题：

“如果今天下雨，明天可能会延迟上班。如果明天延迟上班，项目可能会延期。如果项目延期，公司会损失利润。”

大模型可以用以下步骤结合 MCTS 进行推理：

  1. 生成初始推理路径 ：

    • 路径 1：今天下雨 → 明天延迟上班 → 项目延期 → 公司损失利润。
    • 路径 2：今天下雨 → 明天延迟上班 → 项目未延期 → 公司无损失。
    • 路径 3：今天未下雨 → 明天正常上班 → 公司无损失。

  2. 路径扩展与评估 ：

    • 评估每条路径的可能性和逻辑一致性。例如，大模型可以判断路径 1 的可能性较高。

  3. 选择最优路径 ：

    • 使用 MCTS 的选择策略，进一步探索路径 1，生成更详细的后续推理。

  4. 输出最终推理 ：

    • 最优路径的推理结果作为大模型的回答。

总结

蒙特卡洛搜索树是一种强大的搜索算法，在大模型逻辑推理中可以用来处理复杂的多步推理问题。通过结合大模型的生成能力和 MCTS 的决策优化能力，我们能够在不确定性和复杂性较高的问题中生成更准确、更高质量的答案。

MCTS

蒙特卡罗树搜索（MonteCarloTreeSearch，MCTS）是一种广泛应用于博弈和复杂决策过程的决策算法，它通过构建搜索树并模拟结果来估计/更新行动的价值。通常，MCTS算法包括四个不同的阶段：

  • 选择：算法从根节点开始，根据特定的策略（如UCT/UCB）在有希望的子节点之间进行导航，直到到达一个叶节点。
  • 扩展：在叶节点，除非它代表游戏的终端状态，否则将添加一个或多个可行的新子节点来说明潜在的未来移动。
  • 模拟或评估 ：从新添加的节点开始，算法进行随机模拟——通常被称为"滚动"——通过任意选择移动，直到达到游戏的结论，从而评估节点的潜力。
  • 反向传播：模拟后， 结果（赢、输或平局）被传播。

通过这些阶段的反复迭代，MCTS 逐步构建决策树 ，在由于 状态空间的巨大 而无法直接计算最佳策略的情况下，提炼出最优决策策略。

置信度 上限（ Upper Confidence Bound UCB）算法，或者说应 用在树结构的上限置信区间 （Upper Confidence Bound Applied to Trees UCT ）算法；在MCTS的选择阶段是至关重要的，通过 选择最大化的行为 来平衡探索和利用：

https://i-blog.csdnimg.cn/direct/a53b6944b19d46cfa1a1755dd6179857.png

其中 https://i-blog.csdnimg.cn/direct/39a71ab65b2343779a50c86d88fffef8.png 为动作 https://i-blog.csdnimg.cn/direct/9aa18f5290a5477f8e3e9c1e523b0c81.png 的平均奖励， https://i-blog.csdnimg.cn/direct/28fbfaa64d424fe483421d4492640018.png 为 父节点的总访问次数 ， https://i-blog.csdnimg.cn/direct/4263604c8fb54b83bf3fe9ff4ef896a0.png 为模拟访问节点j 的次数， C为平衡探索和利用的常数。

MCTSr（MCT Self-Refine）算法将蒙特卡罗树搜索（MonteCarloTreeSearch，MCTS）与LLM相结合，将数学问题解的迭代精炼（refine）过程抽象为搜索树结构。这棵树上的节点代表不同版本的答案，而边表示改进的尝试。该算法的操作流程遵循MCTS算法的一般模式。具体来说，我们采用自我反思驱动的自我完善来完善答案；使用模型的自我奖励能力对不同答案版本的奖励进行抽样。

为了方便理解MCTSr算法，定义了以下符号和函数：

  • P：正在处理的问题实例。
  • A：节点的集合，每个节点代表P的一个潜在答案。
  • M：每个节点上可用的一组操作，表示对答案可能进行的自完善修改。
  • R：根据修改的质量和有效性对节点的自我奖励进行抽样的函数。
  • Ra：存储节点a所有自奖励抽样结果的集合，具有自奖励函数R。
  • T：根据达到最大迭代次数或获得满意的答案质量等标准确定搜索过程终止的函数。
  • Q(a)：一个估计答案节点价值的值函数a，由累积奖励Ra和子节点的反向传播推导而来。
  • U(a)：节点a的Q值的置信度上限，以平衡开采和勘探之间的关系。
  • Father(a)：返回给定节点a的父节点的函数。如果a是根节点，则此函数返回null或特定标识符。
  • Children(a)：返回给定节点a的所有子节点集合的函数，表示通过执行操作m∈M从a派生的所有可能状态。
  • N(a)：节点a的总访问量，用于计算节点的UCB值，评估节点的勘探开发状况。因为我们将为每次访问取样一个奖励，所以这个值等于|Ra|。

方法论

MCTSr的主要结构如下：

https://i-blog.csdnimg.cn/img_convert/a8e3f500a1b23f543109919371319700.png

详细介绍每个组件MCTSr的主要工作流程如下：

  • 初始化：根节点是使用原始模型生成的答案和假回答（如 “我不知道”）建立根节点，以最小化模型过拟合倾向。
  • 选择：算法采用值函数Q对所有未完全展开的答案进行排序，并采用贪心策略选择值最高的节点进行进一步的探索和细化。
  • Self-Refine：选择的答案a使用自精炼（refine）框架进行优化。最初，模型生成一个反馈m，指导精炼（refine）过程生成一个增强的答案 。
  • 自我评价：对精炼（refine）后的答案进行评分以获得一个奖励值，并计算其Q值。这涉及到模型自我奖励反馈和约束，如严格的评分标准和抑制满分，以确保评分的可靠性和公平性。
  • 反向传播：将精炼（refine）答案的值向后传播到它的父节点和其他相关节点，以更新树的值信息。如果任何子节点的Q值发生变化，则更新父节点的Q。
  • UCT更新：在更新了所有节点的Q值之后，我们确定候选节点的集合C，以便进一步扩展或选择，然后使用UCT更新公式更新下一个选择阶段的所有节点的UCT值。

该算法遍历这些阶段，直到达到终止条件满足T，包括推出限制或最大探索深度，不断改进答案的质量，并探索新的可能性。

总览

在解答数学问题时，MCTSr中的大模型首先会像正常流程一样生成初步答案（甚至可以是“我不知道”），但并不会直接作为输出。

为了改进这个初始答案，MCTSr算法会对其进行评估和反馈，语言模型会被要求对答案进行评价和批评，分析其中可能存在的问题。

然后大模型基于反馈进行自我修正，产生一个新的答案，这个新版本会纳入搜索树中，成为一个新的子节点。

针对多个子节点，系统会进行评分和奖励采样，计算出该节点的“Q值”（a表示答案节点，Ra表示a的奖励样本集合，|Ra|表示样本数量），可以看出Q值的计算综合考虑了节点在最坏情况和平均情况下的表现。

为了提高评估的可靠性，系统采用了严格的打分标准，并会进行重复采样，同时还采取了禁止模型给出满分等策略。

然后基于Q值，MCTSr会使用改进的UCB公式计算每个叶子节点的UCT值，选择UCT值最高的节点进行扩展。

计算UCT值的目的，是为了平衡了节点的平均奖励和访问频率，避免单纯追求高Q值导致的效率下降。

此外，作者修正的UCT计算公式中还引入了动态调整探索系数c，以便在搜索过程中适应不同的问题复杂度，并在探索广度和深度之间做出平衡。

被选中的节点，会通过大模型再次进行自我修正，生成新的答案节点，然后再次进行自我评估并计算Q值。

新的Q值会被并反向传播到其父节点和祖先节点，确保了搜索树中节点的质量评估随着搜索的进行而不断改进。

根据新的Q值和访问次数，各个节点的UCT值也会被重新计算。

接着，上述步骤会被不断重复，直到满足预设的终止条件，此时具有最高Q值的答案节点被视为问题的最优解。

总的来说，通过蒙特卡洛搜索、自我完善与大模型的集合，MCTSr实现了数学问题最优解的生成。

UCB是一种实现总奖励最大化的方式，UCT是将UCB策略应用于树形搜索问题的一种算法；可以看作是差不多的东西。

Self-Refine

在self-refine的过程中，通过多轮对话精化prompt引导模型优化一个答案 到问题 。最初，模型生产关于 的反思性或批判性评论 。随后在 的指导下，该模型修改 以产生改进版本 。这种迭代精化提高了答案的质量，利用结构化反馈来驱动答案的演变。

自我评价

在数学问题 的精化问题中，答案 的 值被定义为进一步提炼 为高级答案的预期质量，这是因为从 到其重写形式的过渡具有马尔科夫性质。与传统的MCTS（ 估计状态 中的行动值 ）不同，这里的 来自归属于 的奖励函数值的多个采样。

该模型利用自奖励（self-reward）方法来估计 的奖励。其中需要提供从-100到100的奖励分数。我们发现，在没有约束的情况下，模型的奖励倾向过于平滑，导致在实践中答案之间缺乏比较区分。为了解决这个问题，设计了三个约束：

  • 提示约束：模型在奖励评分时必须遵守最严格的标准。
  • 满分抑制：指示模型不提供完整的反馈分数；任何超过95分的奖励都会减少一个固定的数量，以抑制过高的分数。
  • 重复采样：对搜索树节点的每次访问都涉及对该节点的奖励进行重复采样，以增强自我评估的可能性。需要注意的是，在对一个节点的子节点进行奖励采样时，也将对其父节点进行奖励采样，以增加奖励采样的样本量。

采样后，计算 的 值。为抵消自奖励函数的平滑倾向，在期望奖励中加入最小值约束，进一步细化答案质量估计。

其中 为答案 的质量值， 为 的奖励样本集合， 为 中的最低奖励， 为样本数量， 为 中所有奖励的总和。这个公式通过平均奖励的最小值和平均值，平衡最坏情况和平均结果来计算 。

反向传播

在所有叶节点的奖励值采样和 值更新完成后，将会将此更改传播到其父节点和祖先节点。在此更新过程中，如果节点 的子节点集合Children(a)中的任何元素的 函数值发生变化，则该节点的 函数值将更新为

其中 是考虑其子节点影响的答案 的更新质量值， 是仅考虑其奖励样本的朴素质量值， 代表 的子节点中最高的质量值。该公式通过对当前值及其后续子节点的最佳可能结果求平均值来改进 。

更新UCT和Selection

在更新树中所有节点的 值之后，我们继续进行下一轮选择的选择阶段。这个过程包括一下步骤。

候选节点选择：利用数学问题精化过程的马尔可夫性质。专注于选择所有叶节点和那些未完全扩展的叶节点，而不考虑精化路径的历史是可行的。这种路径无关性有助于简化我们的问题。在选择节点时，我们不再需要从根节点开始，而是按层次顺序遍历树中的节点。

但是，考虑到在此任务中充当策略的LLM可以为任何答案状态 生成无限数量的细化操作 。每个节点都可能面临一组无限的扩展操作。因此，借鉴贝叶斯优化中的期望改进概念，本文提出了两个确定"完全扩展"的标准：

  • 节点的子节点数量达到预定义的限制。
  • 至少有一个子节点的 值超过该节点。

我们根据这些标准确定候选节点的集合 ，以便进一步扩展或选择。该策略有助于准确定义哪些节点可能在后续搜索中产生更高价值的答案，从而提高整体搜索效率和结果质量。

UCT更新：借鉴AlphaGo，我们使用UCT和UCB-1方法来平衡节点的探索和利用；对于候选集 中的节点 ，其 值为：

其中 是答案 的 值， 是给定节点的总访问次数， 是平衡利用和探索的常数， 是用于避免被零除的小常数。

排序和选择：根据候选集 的UCT值，我们可以选择一个最优节点，通过贪婪采样或重要性采样来探索精炼（refine）过程。

终止函数

在MCTSr算法中，搜索终止函数准则 可以从以下几个条件推导出来：

  1. 提前停止：当搜索结果的改进效果减少或连续搜索产生重复结果时，就会终止。
  2. 搜索约束：一旦展开数量达到预定限制，或当树中的一个或多个节点满足最大深度约束时，搜索将终止。
  3. 基于语言模型Logits的高级标准：搜索基于来自语言模型Logits的预定义指标进行总结。

一旦满足了终止功能条件 ，我们就可以根据 值或是其他条件从树节点中收集最佳答案。

相关工作

蒙特卡罗树搜索（MonteCarloTreeSearch，MCTS）被广泛应用于各个领域，以高效地解决复杂问题。Pitanov探讨了MCTS在多智能体寻路中的应用，展示了其优于启发式搜索算法如A*的优越性。此外，Yang将MCTS与启发式、无监督和监督学习方法相结合，有效地解决了列车时刻表问题（TTP）。此外，Li介绍了一个通用的方法来解决各种类型的SAT问题，使用一个统一的框架，包括MCTS。Vagadia开发了PhyPlan，这是一个物理信息规划框架，将物理信息神经网络与改进的MCTS相结合，使机器人能够有效地执行动态物理任务。总之，MCTS已被证明是解决不同领域各种复杂问题的通用和有效的数学解决方案，包括机器人，游戏求解和优化。研究人员通过将MCTS与其他算法和框架集成来解决越来越具有挑战性的任务，继续探索和增强MCTS的能力。

最近的研究在增强大型语言模型（llm）的数学推理方面取得了显著进展。Du引入了一种方法，让多个法学硕士共同讨论和完善答案，显著提高推理和事实准确性。Luo开发了WizardMath，它利用来自进化-指导反馈的强化学习，在数学基准上超越现有的法学硕士。与此同时，Lu创建了MathVista，一个可视化的数学基准，GPT-4V的准确率达到49.9％，突出了相对于人类表现的差距。Yu介绍了MetaMath，这是一个擅长数学挑战的微调模型，Yuan证明了预训练损失和拒绝采样微调可以优化LLM的性能，特别是在不太先进的模型中。这些研究表明了重大的进展，但强调了法学硕士数学推理的持续研究的必要性。

大型语言模型（llm）的最新进展显著提高了它们的数学推理能力。然而，他们仍然面临复杂的问题，需要多个推理步骤，导致逻辑或数字错误。为了解决这一限制，Chenetal.(2024)建议结合蒙特卡罗树搜索（MCTS）来增强微调llm的数学推理能力，而无需额外的微调步骤。Xu(2023)利用MCTS和轻量级能量函数，模型可以对决策步骤进行排序，实现即时7反应和精确推理，从而提高数学推理基准的性能。然而，它仍然缺乏一个框架，结合llm的自精炼能力和自奖励评估方法，使用蒙特卡洛树搜索算法迭代地精炼模型的响应。

结论

本文论证了MCT self-refine（MCTSr）算法在提高大型语言模型（LLMs）求解复杂数学问题的能力方面的有效性。通过将蒙特卡洛树搜索（MCTS）与llm集成，MCTSr解决了准确性和可靠性方面的关键挑战，特别是在数学推理任务中。实验结果证实，在跨多个数据集解决问题的成功率显著提高，包括在奥林匹克级数学挑战中的显着表现。

此外，该研究推进了llm在复杂推理任务中的应用，并为未来AI技术的整合奠定了基础，以提高决策和推理的准确性。尽管MCMCTSr在数学问题解决方面展示了潜力，但其在更广泛背景下的适用性，如黑盒优化和自驱动对齐，仍有待探索，未来的工作将优化算法组件。

参考

逻辑推理与决策规划：LLM+MCTS[2]

MCT Self-Refine算法原理解读与代码复现[3]

参考资料

[1]

arxiv论文地址：Accessing GPT-4 level Mathematical Olympiad Solutions via Monte Carlo Tree Self-refine with LLaMa-3 8B:

[2]

逻辑推理与决策规划：LLM+MCTS:

[3]

MCT Self-Refine算法原理解读与代码复现:

个人观点，仅供参考

更新于 2025-01-09
 人工智能
返回 | 主页