- 大規模言語モデルは、長い算術計算のように複数のステップを要する問題でいきなり答えを出そうとすると失敗しがちだが、段階的な解法を作らせると、以前は難しかった問題も解けることがある
- 2022年に Google の研究者が提案した chain-of-thought prompting は、中間ステップを出力させるだけの単純な手法として広く普及したが、なぜ効果があるのかは今も分析対象である
- 研究者たちは 計算複雑性理論によって Transformer の能力と限界を調べ、並列処理に最適化された構造が、即座に答えを出さなければならない場合には計算能力を制限し得ることを示している
- Merrill と Sabharwal の理論研究によれば、中間ステップ数が入力サイズに比例して増え始めるところから chain of thought は実質的に役立ち、多くの問題ではそれ以上のステップが必要になる
- こうした結果は、実際のモデルが訓練中にその解法を必ず学ぶという意味ではないが、Transformer の限界を過大評価せず、新しいニューラルネットワーク構造を比較する枠組みを提供する
段階的な解法がモデル性能を変える理由
- 人は20桁の数の足し算のような問題を一度で正解しようとはせず、一の位から左へ計算を積み上げていく
- 大規模言語モデルも数ステップの算術問題には正答できるが、大きな数の和のように多くのステップを必要とする問題ではしばしば失敗する
- 2022年、Google の研究者はモデルに段階的な解法を生成するよう求めると、以前は難しそうに見えた問題を解けることを示した
- この手法は chain-of-thought prompting と呼ばれ急速に広まったが、効果が出る理由はまだ研究者たちが分析している段階である
Transformer が強力になった方法と構造上の制約
- 大規模言語モデルは、単語を数値列として表現し処理する人工ニューラルネットワークを基盤としている
- 学習前のパラメータはランダムな値から始まる
- モデルはインターネットから取得した大量のテキストで次の単語を予測し、実際のテキストとの差が小さくなるようにパラメータを調整する
- 2017年に Google の研究者が導入した Transformer は、言語モデル研究を大きく拡張した
- Transformer 以前のニューラルネットワークは、多くても数億個のパラメータを持つ程度だった
- 今日最大級の Transformer ベースのモデルは、1兆個以上のパラメータを持つ
- Transformer の中核構成要素は attention head である
- 入力テキスト全体をすばやく見渡し、次の単語予測に役立つ単語間のつながりを見つける
- その後、feedforward network が大きな計算を実行する
- 複数層の attention head と feedforward network を使う構造により、学習中に各単語に対する計算を同時に進められる
- この並列性のおかげで、大規模データと多数のプロセッサに学習を分散できる
- David Chiang は、大きなデータセットを活用するにはモデルも大きくなければならず、並列化なしでは学習は実用的でないと述べている
- 学習が終わった後の通常利用では、Transformer は1単語ずつ出力し、その出力を再び入力に付け加えて次の単語を生成する
- 構造は依然として並列処理に最適化されているため、研究者たちはこの並列性が計算能力の代償を生むのかを検討し始めた
複雑性理論から見た Transformer の計算能力
- ニューラルネットワークの学習過程を直接分析するのは難しいため、一部の研究者はパラメータを望む値に設定できると仮定し、Transformer の本質的な計算能力を分析している
- このアプローチでは Transformer を特定種のプログラム可能なコンピュータのように扱う
- どのような関数を計算できるのか
- どのような種類の問題を解けるのかを問う方法である
- 2019年、Pablo Barceló と共同研究者らは、固定数のパラメータを持つ理想化された Transformer が、適切な設定と反復的な出力の再入力によって Turing machine と同等に強力になり得ることを証明した
- この結果は重要な出発点だったが、実際の Transformer の力を過大評価しかねない非現実的な仮定に依存していた
- その後、研究者たちはより現実的な理論的枠組みを作り始めた
即答しなければならない Transformer の限界
- William Merrill と Ashish Sabharwal は、**回路複雑性（circuit complexity）**によって Transformer の並列構造が生む限界を分析した
- 2人は、Transformer が出力を再び入力に入れられず、最初の出力がそのまま最終回答でなければならない場合を扱った
- この理論的枠組みでは、Transformer は特定の複雑性クラスの外にある計算問題を解けない
- 比較的単純な例として、線形方程式の求解のような多くの数学問題がこのクラスの外にあると考えられている
- 並列性は学習を可能にする利点だが、即答を求められる状況ではコストになる
- Merrill は、入力を与えてすぐに答えを期待する形で使うと Transformer はかなり弱いと述べている
Chain of thought が限界を迂回する仕組み
- Merrill と Sabharwal の結果は、Transformer が出力を再利用できるときにどれほど強力になるのかという問いにつながった
- 実際の言語モデルにおける chain-of-thought reasoning はプロンプトの文言に影響されるが、モデルが段階的な解答を出力すれば、原理的には中間結果を次の Transformer の通過で再利用できる
- Peking University の研究チームは、2023年5月の論文で、Merrill と Sabharwal の枠組み上では通常の Transformer には不可能であるはずの一部の数学問題を扱った
- 中間ステップを許せば Transformer がこれらの問題を解けることを示した
- 2023年10月、Merrill と Sabharwal は chain of thought の計算能力をより詳しく分析した理論研究を発表した
- Transformer が最終回答を出す前に使える中間ステップ数に応じて、追加の計算能力がどのように変わるかを定量化した
- 2桁の数の足し算の例のように、入力が大きくなるほど必要な中間ステップも増える問題がある
- 20桁の数2つを足す最も単純な方法は、10桁の数2つを足す場合より2倍多くの中間の足し算ステップを必要とする
中間ステップは役立つが無料ではない
- Merrill と Sabharwal は、中間ステップがごく少ない場合、Transformer が得る利点も大きくないと分析した
- Chain of thought は、中間ステップ数が入力サイズに比例して増加し始めるところから実質的な効果を発揮する
- 多くの問題では、中間ステップ数が入力サイズよりはるかに大きく増える必要がある
- したがって chain of thought は万能の解決策ではない
- 原理的には、より難しい問題を解かせることはできる
- しかし相当な計算上の労力が必要になる
- Merrill は、1ステップの Transformer の限界を迂回する複数の方法に関心があり、chain of thought が最も経済的な方法ではないかもしれないと述べている
実際のモデルに適用する際の注意点
- 理論分析が実際の言語モデルについて語れる範囲は限られている
- Transformer が原理的に特定の問題を解けるという証明は、実際の言語モデルが訓練中にその解法を必ず学ぶという意味ではない
- Transformer の限界を扱う結果も、強い基準を前提としている
- どの Transformer も特定の問題をあらゆる場合に完全には解けないという意味である
- Daniel Hsu は、特定の特殊ケースはうまく処理できると述べている
- こうした分析は、Transformer を置き換え得る別のニューラルネットワーク構造を比較する枠組みになる
- 複雑性理論の分析であるネットワークがより強力に見えるなら、実環境でもより良い可能性があるという根拠になり得る
- 言語モデルが多様な実アプリケーションで使われる状況では、モデルが得意でないことも多いと認識しておく必要がある
1件のコメント
Hacker News の意見
思考の連鎖（chain-of-thought） は、論理や数学における厳密な連鎖になぞらえるべきではないと思う
モデルの段階的推論は、出力にそのレベルの厳密さを与えるものではなく、連鎖の強さは関連する文脈の強さでしかないため、人間が行う数学や論理よりはるかに弱い
この分野のモデルを日々扱っているが自分で作っているわけではない立場から見ると、基礎数学で教えられるような必然的なつながりは見えず、一定の年齢を超えた人間ならしないような失敗をモデルがするのをよく見る
結局のところ、関連する文脈を見つける作業に近く、強力ではあるものの、人間の論理的推論とは違う。人間はごく少数の概念から出発し、椅子に座って純粋な推論だけでも、遠くにある鉄壁の結論に到達できるが、モデルは文脈の間を飛び回っていることに近い
真面目にベイズ統計をやったことがある人なら、サンプラーが効率よくサンプルを引く前にしばらくウォームアップが必要だと知っている。思考の連鎖でも、モデルが正解をサンプリングできる正しい近傍に入る前に、少しさまよう必要があるという似たようなことが起きているように思う
多くの人は、疑わしい信念について十分考えたと思っているが、実際にはそうではない。文脈を使って次の思考や単語を推測し、最初から持っていた結論にたびたび到達する
鉄壁の結論と言うとき、実際には直感的に組み立てた後で、定義が十分に明確か、推論の飛躍が正当か、といった点を強く検証する過程が付いてくるのだと思う
だから本当に見たいのは、曖昧な英語文を、より形式的な推論エンジンに入れられる形へ変換する方法を LLM に教えることだ
例えば「イギリスの中にサッカー場はいくつ入るか」を LLM に直接聞くより、
get_size_football_field()とget_size_England()が平方メートル単位であると仮定して、それを計算するPython コードを書かせるほうがよい場合が多い自分はだいたいGo コード10行を超えると推論できなくなり、趣味でパズル解きを何度もやってみて、それがはっきりした
私たちには聴覚ループがあり、複雑な問題に出会うと「これで XYZ が分かった、次は何だろう……」というような呪文を繰り返し、よい次のステップが浮かぶとそれを文脈に追加する
ただし、遷移関数はいまのところ人間のほうがはるかに優れているだけだ
推論を文脈の中に書き込んでおくことで、後からより参照しやすくしているからだ。もちろん推測にすぎない
Karpathy から聞いたような単純化した説明では、Transformer モデルはトークンを生成（デコード）するときにだけ計算をする、というものだ
だから思考の連鎖を書いてより多くのトークンを生成すると、モデルに「考える」時間がより多く与えられる。もちろん、この説明がすべてのニュアンスを含んでいるわけではない
短い補完では、
A B1、A B2のように、もっともらしい可能性の空間がはるかに大きい。微妙な質問に短く答えろと言われると、思慮深い答え、見た目には正しそうな答え、説得力のあるたわごとなどがすべて可能になる一方で推論を説明するよう強制すると、もっともらしい補完の空間が狭まる。説得力のあるたわごとから始めても、正直に最後まで押し進めれば、結局は覆さなければならないという結論に至ることがある
これは、誠実な人の有害な信念に反論するとき、その信念の帰結を実際に展開させ、何となくよさそうに見えるものの影響を一緒にたどってみる方法がうまく機能する理由に似ている
もっともらしい補完空間を狭める要素でプロンプトを埋めることが、効果的なプロンプトエンジニアリングである理由も似ている
最も複雑な推論質問を投げても、次のトークンを生成するのにかかる計算量は、最も単純なはい／いいえ質問と同じであり、これは構造上の制約によるものだ
LLM に計算用の「落書き」データを生成させ、関連情報に注意を向けさせることは、この一定コストの限界を回避する方法だ。タスクが難しいほど、より多くの落書きが必要で、そうして初めて将来のトークンに必要な関連文脈がより多く残る
代わりに、LLM のワーキングメモリが活性値に制限されており、それがボトルネックになり得ることに気づいた。モデルは部分結果を出力に書いてから再び読むことで、ワーキングメモリを拡張できる
例えば「数字を1つ思い浮かべるが、言ってはいけない」とすると、その数字を保存する場所がない。テープ以外に一時的な保存場所がないからだ。しかし「段階的に考えよ」と言うと、中間結果、つまり思考をテープに保存することになり、思考に使える追加の保存空間が生まれる
「計算を増やす」という面もあるが、核心は、モデルが決定を下すときに限られた範囲だけへ集中するようプロセスを構成することだ
実質的には、互いを土台に積み上がる決定のツリー構造を作ることになる。中間トークンを生成すると、モデルはすでに折りたたまれた、より小さい決定集合だけに注意を向けられる
ただし、モデルが予想した誤った結果のために中間段階が偏る予期的な挙動も生むので、実際にはもう少し複雑だ
「計算に関する形式的研究は、1936年のTuringのチューリングマシンから始まった」という説明は、もっと遡る必要がある
1920年代のMoses Schönfinkelによる組合せ論理 https://en.wikipedia.org/wiki/Moses_Sch%C3%B6nfinkel と、1930年代初頭のAlonzo Churchによるラムダ計算 https://encyclopediaofmath.org/wiki/Lambda-calculus がある
ただし、これらのモデルは計算複雑性理論の基盤としてはやや適していない
Aristotleは、構造化された思考を形式化しようとした最初期の人物に近かったはずだ
Turingの計算装置は、人間の数学者が形式的な規則に従って記号を操作し、問題を計算として解く方法を形式化したものであり、同じ経験と、それがどれほど機械化しやすいかを考えてきた長い系譜に連なるものだった
算術について実際にこれを実装した最初の人物はPascalだった
LLMをめぐる議論の2つのモード、つまり「意識がある！」と「印象的なデータセットを持つ次トークン予測器にすぎない」は、おおむね別々の2つの集団から出ていると思う
LLMを先に知って後から機械学習の基礎を学んだ人たちと、機械学習の基礎を先に学んでから今日のLLMに触れた人たちだ
私は後者だが、基礎に対する先入観が大局を見るうえで限界を作る危険も実際にあるので、議論そのものは歓迎している
思考の連鎖については、元論文の結果のかなりの部分が、その後の試みでうまく再現されなかったという程度は知っている。それが日々変わるモデルの特異性なのか、もっと深い理由があるのかは分からない
ただ、以前、論文指導教員に、機械学習分野の人たちは昔の機械学習やAIの仕事をあまり知らないようだと不満を言ったところ、30年以上の研究歴を持つ指導教員が、自分が博士課程の頃にもすでにそういう不満はあったと言っていた
AIにはPittsとMcCullochから数えれば約80年、Turingから数えても長い仕事があまりに多く、他人の仕事を追いながら自分のテーマも深く掘るのは非常に難しい
たとえば強化学習の本を開くと、計画（planning）とほとんど同じ問題を、状態空間と行動空間という非常によく似た仮定で扱っているのに、まるで計画という分野が存在しないかのように見えることもある
付け加えると、それらは次トークン予測器であることに違いはない :P
Transformerがあれほど貧弱な近似で、しかも完全に無状態であるにもかかわらず、これほど印象的な結果を出せるという事実を見ると、ここに特別な秘訣が別にあるようには思えない
これは明白だと思っていた。LLMには人間のような内なる声や内的イメージがないので、答える前にまず頭の中で問題を最後まで考え切ることができない
そのため実際の出力領域を一種のメモ帳として使えば、答えを出す前により広い推論領域をカバーでき、人間のやり方に近くなる
「段階的に考えよ」というプロンプトで特定の質問を投げると、最終回答には役に立たない一時的な思考も出力するのが分かる。まさに、私たちがすぐには答えられない問題を解くときにしていることと同じだ
人間も紙とペンで一時的・中間的な考えや答えを書き留めることがある。LLMにはそうした道具はないが、出力を同じように使うことはできる
一部の**思考の木（Tree of Thoughts）**プロンプトは、LLMに2種類の出力を作らせる。1つは「内なる声で考える」もので、もう1つは人間に見せる出力だ
メソッド呼び出し機能や「ググる」能力を与えることも、ユーザーに見せる答えを作る前に思考と推論を行う方法と見なせる
モデルは考えられない。入力コンテキストを使って出力を予測しているだけだ
だから反復的に解く必要がある問題があるなら、中間段階をコンテキストに保存しなければならない。そうしないと、それらの段階の行き場がない
入力から出力を予測するという点が、なぜ考えられないという信念につながるのか分からない。思考というものがすべてそうなのかもしれないし、私たちには分からない
単純な理由ひとつで、
11 + 31 = 24がもっともらしく見えることを考えられる答えは数字であり、2桁の数字である点も、2桁の入力を足すときにはかなりもっともらしい。24は数学問題でよくある答えでもあり、約数も多い。さらに
1+3と1+1を足すときに出てくる数字も含まれているしかし「解法を示せ。11 + 31は十の位どうしを足して10 + 30 = 40、一の位どうしを足して1 + 1 = 2であり、40と2を合わせると24だ」という最後の文は、あまりもっともらしくない
あるいは「10 + 30 = 20、1 + 1 = 4、20と4を合わせると24だ」も同様だ
問題を分解すると、素早い誤答よりも確率の低い領域を通過しなければならない
ただし、計算複雑性による論証のほうがより強い。上の説明は単純な場合には十分な撹乱説明になり得るので、計算複雑性が重要だと主張する前に排除しなければならないかもしれない
複雑性の論証も直感的には当然だ。LLMを、各クロックサイクルごとにこれまでの入力に対して定数時間の順伝播を1回実行し、トークンを1つ出力するコンピュータと見れば、より多くのサイクルを与えれば、より多く計算できる
状態も使える。あるサイクルから次のサイクルへ状態を渡すメカニズムが非常に制限されていても可能だ
これは、単層パーセプトロンがXORを計算できないという古典的な問題の拡張にも似ている。ここでいう「サイクル」は、ある層から次の層へ進む進行のことだ
もちろん、細部が自明だという意味ではない。複数のクロックティックを使えるというだけでは、1ティックでどれだけできるかは説明できない
思考の連鎖の奇跡に関連していて、より単純な説明になり得るツイートがある
「段階的に考えてみよう！」というフレーズで検索すると、いくつかの結果の中に http://geteasysolution.com のようなサイトが出てきて、そこには数学の段階的な解法がたくさんある。かなり一般的だという点は考えさせられる
https://twitter.com/yanaiela/status/1765077404043952516
そのフレーズが、思考の連鎖の例が多いWebサイトの概念空間へモデルを誘導することはあり得るが、思考の連鎖が実際に思考の助けにならないのなら、出力がより良くなる結果にはつながらないはずだ
これはすでに明白だと思っていた。すべて文脈認識の問題だ
改善したいなら、プロンプトに用語を1つ追加して、より多くの考慮事項を開けばよい。コンテキストウィンドウの終端に達していないと仮定すれば、新しい単語の一つひとつが、より多くの文脈を持つ新しいベクトルを「解放」し、言語モデルはそれを考慮に加える
人間の脳が働く仕組みに見えるものとの類似性があまりに際立っているので、言語モデルをよりうまく使うための比喩として使わないほうが、むしろ筋が通らない
LLMを操作する方法と人間の脳を操作する方法、つまり適切な言葉を使う方法で同じ結果を得られるなら、なぜ違いがあると信じるべきなのか分からない
こういうことは、3Bモデルを使って研究していると時間とともに学べる。多くの人は避けているようだが、「古い」orca mini 3Bのような一部のモデルは非常に強力で、私は今でも使っている
必要なのはより良いプロンプトであり、このアプローチはとてもうまく機能する
最大の障害は、こうした小型モデルのコンテキストウィンドウがたいてい小さいことだが、小さなRoPE拡張、テキスト要約、文脈語の追加、プロンプト内の単語の文字を省略する、といった方法で、品質を大きく犠牲にせず回避できる
言語モデルの結果を改善したいなら、メンタリスト、詐欺師、マジシャン、ソーシャルエンジニアにならなければならない。奇妙に聞こえるが効果はある
MerrillとSabharwalは、中間ステップの数が入力サイズに比例して増えるときに初めて思考の連鎖が実際に役立ち始め、多くの問題では中間ステップ数がそれよりはるかに大きく増える必要があることを証明している
私の経験とも合っている。GPT-4は段階的な解法をさせると、「単純な」問題だけを分解できる。特に実際のステップ自体をさらに分解しなければならないO(n²)の複雑度では、作業をステップに分けはするが、サブタスクをさらにサブステップへ分解することに安定して失敗する。そのサブタスクを思考の連鎖プロンプトで解けるとしてもだ
思考の連鎖プロンプトは、LLMが答えを当てずっぽうで出さないようにしてくれるので、単純なO(n)計算には効くが、理論的にも経験的にも、あるO(n²)問題をO(n)個のO(n)サブ問題に分ける能力はないと思う。言うまでもなく、人間はそれよりはるかに賢く、ネズミでさえそうだ
思考の連鎖は「何とかやりくりすること（muddling through）」を思い起こさせ、知能の近似に対する正しいアプローチだという私の直感とすぐに合致する
https://studio.ribbonfarm.com/p/massed-muddler-intelligence#...