Tree of Thoughtとは｜1本道は行き止まりへ、枝を2本残したら1.6倍見て解に届いた

1本道は行き止まりへ、枝を2本残したら1.6倍見て解に届いた

探索木を実際に走らせました。1本道は7本見て行き止まり、上位2本を残すと11本見て解に到達します。

Tree of Thoughtがどう効くのかを、探索木を作って走らせました。用意したのは深さ4の木で、1手目でいちばん有望に見える枝の先に解がないものです。

木の形と評価値はこちらで置いていますが、2つの手順は本当に実行して到達と展開数を数えています。

// 1本道: 毎回いちばん有望な子だけを選んで降りる。戻らない
function greedy(node) {
  let expanded = 0, cur = node, path = [];
  while (cur.children.length) {
    expanded += cur.children.length;                       // 子を見た数を数える
    cur = cur.children.reduce((a, b) => (b.score > a.score ? b : a));
    path.push(cur.id);
  }
  return { reached: !!cur.goal, expanded, path };
}

// 枝を分ける: 各段で上位 k 本を残して降りる
function beam(node, k) { /* 各段で next を score 順に並べ、先頭 k 本だけ残す */ }

深さ4の探索木。1手目でいちばん有望に見える枝の先に解はない

手順        解に到達  見た枝の数  たどった経路
1本道で進む   しない              7本  A → A1 → A1a → A1a1
上位2本を残す  した              11本  B → B1 → B1a → B1a1
上位3本を残す  した              14本  B → B1 → B1a → B1a1

見た枝の数の比: 1.6倍（上位2本を残す場合）

1本道の手順はAへ進み、そのまま行き止まりに着きました。Aは1手目でいちばん有望に見える枝です。

見かけに引きずられる

この木では、解はBの先にあります。ところがBは1手目の評価でAより低く、1本道の手順はBを見た時点で捨てています。

しかも捨てたあと戻りません。ですから行き止まりに着いても、そこで終わります。

残せば選び直せる

上位2本を残す手順では、1手目でAとBの両方を保持します。2手目でBの先が高く評価されたため、そちらが残って解に届きました。

代償は見る枝の数です。7本から11本に増えています。1.6倍という比は、この木が小さいためで、木が広いほど差は開きます。

本数を増やしても同じ

3本に増やした場合も、到達する経路は2本のときと同じでした。増えたのは見る枝の数だけで14本です。

Tree of Thoughtとはどういう進め方なのか

考えを1本に絞らず、複数の候補を枝として残しながら進めます。途中で評価して、見込みの薄い枝を落とします。

Tree of Thoughtは、次の一手の候補を複数出し、それぞれを枝として残しながら進める方法です。日本語では思考の木とも呼ばれます。

1段の中身

1段でやることは3つです。候補を出す、それぞれを評価する、上位だけ残す。残した枝それぞれについて、また同じことを繰り返します。

評価の基準はこちらで用意します。ここが作れないと、どの枝を残すか決められません。

道筋が結果を左右する

この考え方が要る理由は、探索の性質にあります。Anthropicは調査の仕事について、複雑な題材を探るのに決まった道筋を固定して書き込むことはできず、その過程は本質的に動的で、どの道を通ったかに左右されると述べています。

同じ文書では、モデルが多くの手にわたって自律的に動き、途中で得た結果をもとにどの方向を追うかを決める必要があるとも書かれています。途中で選び直すことが前提になっている、という整理です。

似た進め方との違い

1本の筋道を書かせるだけの方法はChain of Thoughtの記事で、同じ問いを複数回解かせて多数決を取る方法は自己整合性の記事で扱っています。Tree of Thoughtは、途中で分岐して選び直せる点が両者と違います。

探索の枝は何本残せばよいのか

2本から始めます。増やしても到達が変わらないことがあり、そのときは見る枝が増えるだけです。

Tree of Thoughtで残す本数は、増やせば良くなるとは限りません。前の節では2本と3本で到達が同じでした。

そもそも使うべきか

1. 途中で選び直したい仕事。調べた結果で次の方向が変わる
2. 候補を評価する基準が作れる仕事。良し悪しを数値にできる
3. 手順が決まっている仕事。探索する必要がない
4. 評価の基準が作れない仕事。残す枝を選べない

3番目と4番目には向きません。特に4番目では、枝を残しても選べないので1本道と変わりません。手順が読める仕事の組み方は決定的ワークフローの記事で扱っています。

調べものには合う

向いているのは、進みながら方向が変わる仕事です。Anthropicも調査について、調べ進めるなかで方向を変えたり、周辺のつながりを探ったりできる柔軟さが要ると述べています。

逆に、最初から答えへの道筋が見えている仕事に持ち込むと、探索の手間だけが乗ります。

本数と費用

残す本数は、そのまま見る枝の数に効きます。実測では2本で11本、3本で14本でした。1段あたりの候補が多い木では、この伸び方がさらに急になります。

ですから2本から始めて、到達しない場合にだけ増やすのが実際的です。増やす前に、評価の基準を見直すほうが効くこともあります。