MCTS & rStar

蒙特卡洛樹(shù)搜索（MCTS）

蒙特卡洛樹(shù)搜索（MCTS）是一種用于解決復(fù)雜決策問(wèn)題的算法，常用于游戲等領(lǐng)域。它的基本思想是通過(guò)構(gòu)建一棵搜索樹(shù)并模擬各種可能的行動(dòng)來(lái)估計(jì)每個(gè)行動(dòng)的價(jià)值。MCTS的過(guò)程可以分為四個(gè)主要步驟：

1. 選擇（Selection）：

    從根節(jié)點(diǎn)開(kāi)始，根據(jù)某種策略（如UCT）遍歷子節(jié)點(diǎn)，直到找到一個(gè)葉節(jié)點(diǎn)。

    UCT（Upper Confidence Bound applied on Trees）是一種平衡探索和利用的策略。

2. 擴(kuò)展（Expansion）：在葉節(jié)點(diǎn)，如果它不是終止?fàn)顟B(tài)，則添加一個(gè)或多個(gè)子節(jié)點(diǎn)，表示未來(lái)可能的行動(dòng)。
3. 模擬（Evaluation）：從新添加的節(jié)點(diǎn)中隨機(jī)選擇一個(gè)，進(jìn)行隨機(jī)模擬，直到達(dá)到終止?fàn)顟B(tài)，以此估計(jì)該節(jié)點(diǎn)的潛在價(jià)值。
4. 反向傳播（Backpropagation）：將模擬結(jié)果（贏、輸或平局）反向傳播到遍歷過(guò)的節(jié)點(diǎn)，更新統(tǒng)計(jì)數(shù)據(jù)（如獎(jiǎng)勵(lì)或訪(fǎng)問(wèn)次數(shù)），以指導(dǎo)未來(lái)的決策。

通過(guò)這些步驟，MCTS逐步構(gòu)建決策樹(shù)，幫助在狀態(tài)空間巨大時(shí)找到最優(yōu)策略。

rStar框架

rStar框架是基于MCTS的擴(kuò)展，通過(guò)多種推理動(dòng)作來(lái)增強(qiáng)小型語(yǔ)言模型的解決問(wèn)題的能力。rStar的包含多種推理動(dòng)作：

• A1：提出一步思考：基于之前的步驟生成下一步推理。
• A2：提出剩余思考步驟：一次性生成所有剩余的推理步驟。
• A3：生成下一個(gè)子問(wèn)題和答案：將主問(wèn)題分解為一系列子問(wèn)題，逐一解決。
• A4：重新回答子問(wèn)題：重新回答之前生成的子問(wèn)題，提高準(zhǔn)確性。
• A5：重述問(wèn)題/子問(wèn)題：重述問(wèn)題以澄清條件，減少誤解。

這些動(dòng)作使rStar能夠動(dòng)態(tài)選擇推理路徑，增強(qiáng)MCTS的探索能力。

RARE方法

推理過(guò)程：該過(guò)程結(jié)合了生成和事實(shí)性評(píng)分。(1)檢索增強(qiáng)生成器使用蒙特卡洛樹(shù)搜索(MCTS)產(chǎn)生多個(gè)候選推理軌跡；(2)檢索增強(qiáng)事實(shí)性評(píng)分器評(píng)估每個(gè)推理軌跡的事實(shí)準(zhǔn)確性；(3)選擇事實(shí)性得分最高的軌跡作為最終答案。

通過(guò)檢索增強(qiáng)生成器和RAFS兩個(gè)階段，RARE系統(tǒng)地將基于檢索的證據(jù)整合到推理過(guò)程中，優(yōu)化了推理的連貫性和事實(shí)準(zhǔn)確性。這種方法使RARE非常適合于常識(shí)和推理等知識(shí)密集型任務(wù)。

1.檢索增強(qiáng)生成器

這一階段基于MCTS（蒙特卡洛樹(shù)搜索）的自生成器，引入了兩個(gè)新的檢索增強(qiáng)動(dòng)作，動(dòng)態(tài)獲取相關(guān)外部信息。這些動(dòng)作通過(guò)將上下文化知識(shí)整合到中間推理步驟中，提高了候選推理軌跡的相關(guān)性和準(zhǔn)確性，特別是對(duì)于復(fù)雜問(wèn)題。

為了通過(guò)外部知識(shí)增強(qiáng)推理過(guò)程，引入了兩個(gè)新動(dòng)作到檢索增強(qiáng)生成器中：

• A6：搜索查詢(xún)生成與信息檢索

該動(dòng)作提示LLM根據(jù)初始問(wèn)題構(gòu)建搜索查詢(xún)并執(zhí)行信息檢索。檢索到的文檔提供了額外的上下文，豐富了推理軌跡，支持生成器形成更全面、更具上下文相關(guān)性的最終答案。

• A7：子問(wèn)題檢索與重答

該動(dòng)作通過(guò)動(dòng)作A3生成的子問(wèn)題進(jìn)行細(xì)化。對(duì)于每個(gè)子問(wèn)題，生成器檢索特定的相關(guān)信息并使用它來(lái)重新回答子問(wèn)題。這種方法提高了中間推理步驟的準(zhǔn)確性，從而增強(qiáng)了整個(gè)推理軌跡的連貫性和事實(shí)可靠性。

通過(guò)這些檢索增強(qiáng)動(dòng)作，生成器可以探索更廣泛的解決方案空間，導(dǎo)致邏輯連貫且富含外部信息的推理路徑。

2. 檢索增強(qiáng)事實(shí)性評(píng)分器（RAFS）

這一階段用檢索增強(qiáng)事實(shí)性評(píng)分器替換了rStar中的鑒別器，評(píng)估每個(gè)候選軌跡的事實(shí)可靠性。評(píng)分器驗(yàn)證中間推理步驟與檢索證據(jù)的一致性，分配一個(gè)反映軌跡與外部知識(shí)一致程度的事實(shí)性評(píng)分。選擇事實(shí)性評(píng)分最高的軌跡作為最終答案，優(yōu)先考慮最具事實(shí)支持的推理路徑。這種選擇確保了推理的連貫性和事實(shí)對(duì)齊，增強(qiáng)了響應(yīng)的可信度。

RARE引入了檢索增強(qiáng)事實(shí)性評(píng)分器（RAFS）。RAFS通過(guò)用LLaMA 3.1替換GPT-3.5-turbo，并用包含一般領(lǐng)域知識(shí)（Wikipedia）和醫(yī)學(xué)領(lǐng)域資源（PubMed、StatPearls和醫(yī)學(xué)教科書(shū)）的語(yǔ)料庫(kù)索引檢索系統(tǒng)替換Google Search，從而適應(yīng)特定領(lǐng)域的需求。為了評(píng)估生成推理路徑的事實(shí)準(zhǔn)確性，RAFS在四個(gè)系統(tǒng)性步驟中評(píng)估每個(gè)候選軌跡，如下圖。

• 分割成語(yǔ)句
  每個(gè)推理軌跡被分割成單獨(dú)的語(yǔ)句。這種分段使得RAFS能夠獨(dú)立驗(yàn)證離散推理步驟的事實(shí)準(zhǔn)確性，增強(qiáng)了整體評(píng)估的可靠性。
• 生成檢索查詢(xún)
  對(duì)于每個(gè)語(yǔ)句，RAFS使用LLM生成多個(gè)檢索查詢(xún)，旨在檢索與上下文相關(guān)的證據(jù)。這些查詢(xún)針對(duì)可以支持或反駁每個(gè)語(yǔ)句內(nèi)容的信息，確保全面的事實(shí)驗(yàn)證。
• 檢索信息
  檢索系統(tǒng)收集與每個(gè)生成的查詢(xún)相對(duì)應(yīng)的文檔或信息。這些證據(jù)為評(píng)估每個(gè)推理步驟與外部來(lái)源的一致性提供了事實(shí)基礎(chǔ)。
• 使用檢索信息進(jìn)行評(píng)分
  每個(gè)語(yǔ)句與檢索到的證據(jù)進(jìn)行比較，并標(biāo)記為“支持”或“不支持”（如上圖所示，RAFS為每個(gè)語(yǔ)句輸出一個(gè)事實(shí)性得分以及“支持”或“不支持”的標(biāo)簽。），基于與信息的對(duì)齊情況。推理路徑的整體事實(shí)性得分計(jì)算為支持語(yǔ)句的比例，指示軌跡的事實(shí)可靠性。這種評(píng)分有助于從多個(gè)候選者中選擇最可靠的推理路徑，使RARE能夠優(yōu)先考慮與經(jīng)過(guò)驗(yàn)證的外部知識(shí)緊密對(duì)齊的響應(yīng)。

參考文獻(xiàn)

RARE: Retrieval-Augmented Reasoning Enhancement for Large Language Models，https://arxiv.org/pdf/2412.02830v3

本文轉(zhuǎn)載自公眾號(hào)大模型自然語(yǔ)言處理  作者：余俊暉

原文鏈接：??https://mp.weixin.qq.com/s/L1zyKkJh3zYMEOHcLjLTQw??