マルコフ連鎖は元祖の言語モデルである

248日前原文(elijahpotter.dev)

概要

AIブーム の個人の心理的変遷についての考察
Markov連鎖 を用いたテキスト自動補完の実装例
確率行列 ・ベクトルによる状態遷移の説明
テキスト生成時の 定常状態問題 とその回避策
RustとWebAssemblyによる実装上の工夫

AI Buzzはもう退屈

AIブーム の心理的段階を4つに分類
- 第1段階: 驚嘆
  - コンピュータと自然な会話ができることへの感動
  - 未来への無限の可能性を感じる段階
- 第2段階: フラストレーション
  - 実際の用途では期待ほど役立たない現実
  - 情報や論理の誤りが多く、信頼できない
- 第3段階: 混乱
  - 自分は興味を失ったが、周囲はまだ盛り上がっている
  - 自分の考えが間違いだったのかと疑問に感じる
- 第4段階: 退屈
  - 新しい言語モデルが次々登場し、飽和感
  - 原点回帰や基礎からの学び直しへの欲求
  - Markov連鎖 への関心

Markov連鎖によるオートコンプリート

Markov連鎖 とは
- Andrey Markov考案の 確率的遷移モデル
- 各状態から次状態への遷移確率で表現
- 例：Aliceがスーパーとプラネタリウムを行き来する確率
遷移確率表の作成
- 各状態間の遷移を表形式で整理
- 状態が不確定な場合は 確率ベクトル で表現
- 次状態の確率計算は 行列とベクトルの積 で求める
行列による一般化
- 遷移確率表＝ 遷移行列T
- 現在位置の確率分布＝ 状態ベクトルs
- 行列積 Ts で次時刻の状態分布を計算
- nステップ先は T^n s で予測

テキスト補完への応用

辞書作成
- サンプルテキストから単語リストを生成
- 各単語にインデックスを割り当てる
遷移行列の構築
- テキストをインデックス列に変換
- 各単語間の遷移回数をカウントし、 遷移回数行列C を作成
- 列ごとに合計し、 確率行列M へ正規化
補完の実装方法
- ユーザー入力の最後の単語を特定
- 対応するインデックスで単位ベクトルを作成
- M × s で次に来る可能性の高い単語を算出
- 最も確率の高い単語を候補として提示

テキスト生成と定常状態問題

素朴な生成方法の課題
- 常に最頻単語を選ぶと、 定常状態 に収束し単調な出力になる
- ランダム性を加えても、長期的には同じ問題に直面
筆者の解決策
- ランダムな対角行列R を生成
- R × s の最大値インデックスを選択し、ランダム性と多様性を確保

実装面での工夫

Rust＋WebAssembly によるパフォーマンス重視の実装
HashMap でインデックス変換・遷移回数管理を高速化
ユーザーインターフェースとして
- 「Choose Word」ボタンや右矢印キーで自動選択
- 候補単語をタップして手動選択も可能

まとめ

AIブームの心理的変遷 と、原点回帰としての Markov連鎖 への興味
確率行列 を活用したシンプルなテキスト補完・生成手法
定常状態問題 を回避するための工夫
実装を通じて得た気付きと、技術的な楽しさ

Hackerたちの意見

カーニハンとパイクの「プログラミングの実践」には、すごくエレガントなマルコフがあったよね。

└

それに、Mark V. Shaneyはロブ・パイクによって設計されてUsenetに投稿されたけど、それはかなり前のことだよ。

└

これもね！ http://c9x.me/cbits/

4〜6年前くらいに、Slackの会話からエクスポートしたデータを使って、よくいたユーザーを再現するためにマルコフ連鎖をトレーニングしたことがあるんだ。全部Pythonで書いたけど、統計や数学の知識はあんまりなかったけど、原理は理解してた。ボットを作って、自分が管理してるSlackに参加させて、タグ付けしたり、その人がいつも反応することを言うと反応するようにしてた（ハードコーディング）。まぁ、反応は結構めちゃくちゃだったし正確じゃなかったけど、時々そのボットがその人っぽく聞こえるのを見てみんなで大笑いしたよ。ランダムな他の言葉と混ざり合ってたけどね :D

└

同じようなプログラムを「AWAY」ボットとして作ったことがあって、過去の会話のトランスクリプトを元にSkypeに接続してたんだ。当時（2009年）は台湾に住んでたから、アメリカの友達とチャットするために寝るときに起動してた。約12時間の時差があったからね。でも、トランスクリプトを読み返すと、ちょっと精神的におかしくなりそうな感じがしたよ。

ランダムな豆知識だけど、15年以上前はマルコフ連鎖が自動生成テキストの定番だったんだ。Googleは今ほどスパムを見分けるのが上手じゃなかったから、アフィリエイトマーケティングが密集してるトピック（例えば、特定の薬や商品）では、検索結果ページがマルコフ連鎖で作られたウェブサイトで溢れかえってた。

問題はマルコフ連鎖の線形的な性質なんだ。確かに分岐はできるけど、観測の後は新しい状態に絶対に移行するからね。AがBに行って、BがCに行くみたいな感じ。これが問題になる理由を理解するためのクラシックな問題は、パターンが縦の2Dビットマップを入力することなんだけど、データを左から右に渡してるから、マルコフ連鎖はそれを処理できないんだ。完全にパターンを見逃しちゃう。言語でも似たようなことが起こる。言語は線形じゃないし、数文前のコンテキストが現在の文字列の確率を変えるべきなんだ。アテンションメカニズムがこれに対して最善の方法だけど、マルコフ連鎖は数音節をつなげる以上のことには苦労してる。マルコフ連鎖で遊んだことがたくさんあるけど、スキップ状態を試したりしたけど、最終的にはコンテキストを扱うためにアテンションメカニズムに似たことをすることに押し込まれるんだよね。

└

マルコフ連鎖のマルコフ連鎖がこの状況で役立つかな？2Dビットマップパターンが縦のときに一つ、左から右のときに別の一つが動く感じ？

└

たくさん時間をかけた後に探求するのは面白いと思う？特定の文脈で実用的に使える可能性があると思う？それとも、ほとんどの場合、サービスや一貫したLLMを使った方が楽だと思う？

└

観察の後、あなたは絶対に新しい状態にいる。マルコフ連鎖の本質的な特性は、マルコフ性を維持することだよ：P(X_n+1 = x_n+1 | X_n = x_n, ..., x_1) = P(X_n+1 = x_n+1 | X_n = x_n)。つまり、現在の状態が与えられたとき、未来は過去の状態に条件的に独立しているってこと。デコーダーのみのLLM（人々が使う主要なLLMのほとんど）はマルコフ性を維持していて、マルコフ連鎖として正しく理解できることを認識する価値があるよ。> 注意機構はこれに対して最良のもので、マルコフ連鎖は数音節をつなげる以上のことには苦労してる。注意はマルコフ性の維持には関係なくて、状態の非常に複雑な表現を可能にするんだ。これがデコーダーのみのLLMが力を発揮するところだよ。要するに、ほとんどの人が使うLLMは実質的にマルコフ連鎖なんだ。

└

複数のホップ依存関係をマルコフ連鎖としてモデル化するには、状態空間を直積で拡大すればいいよ。実際に意味があるかは別だけど、理論的にはマルコフ連鎖はものすごい表現力を持ってる。

マルコフ連鎖を短いシーケンスの長さ（4〜5文字）で生成するようにプログラムすると、面白いポルタメンタウが作れるよ。90年代初頭に、典型的な技術文献を元にトレーニングしたら、「マーケテクチャー」っていう言葉が出てきたのを覚えてる。

└

それ、企業のバズワード生成機みたいだね。

あぁ、マルコフ連鎖ね。昔、Mark V. Shaneyがロブ・パイクによって設計されて、Usenetに投稿されたんだ。Veritasiumの動画「ほぼ何でも予測する奇妙な数学」では、マルコフ連鎖の歴史について詳しく話してるよ。

└

すごく分かりやすい説明だね。俺のよりも全然いいよ。

好きか嫌いかは別として、LLMは実質的に高次のマルコフ連鎖だよね。

└

限定的な自己修正を持つマルコフ連鎖。

└

その通り。文法空間や抽象構文木の空間でのマルコフ連鎖って考えてる。n-gramの単語の連鎖じゃなくてね。注意機構は文法木の親を特定したり、代名詞のような他のバックリファレンスを識別するのに役立ってると思う。プログラミング言語の場合は、変数のバックリファレンスとかね。

└

すべてのコンピュータが有限状態機械であるという意味ではね。

まだ誰もこのクラシックを言及してないなんて信じられない！ https://www.tumblr.com/kingjamesprogramming Slackの初期の頃に、みんなが書いたメッセージをログに記録するチャットボットを作ったんだ。それを使って、特定のトリガーワードに反応してランダムなことを言わせてた。めっちゃ面白かったけど、上司が私が彼らの会話を全部記録してることに気づいて、当然のようにそれをオフにさせられた。

この記事の「遷移行列の構築」セクションに間違いがあるみたい。正規化係数を持つ対角行列Dを示す代わりに、正規化されたマルコフ行列Mを表示してて、正規化されていない行列Cと等しいと間違って主張してる。

いい感じの例だね。果物の例の最後に「ストップ」トークンを追加するといいかも。そうすれば、小さなモデルが動くときに自分でストップを呼び出せる。ADHDに一般化するには、スピーカー（トークン生成器）を静かに「聞く」ことができる別のモデルを作って、マルコフ連鎖が「ストップ」を予測するまで待機させて、自分の生成モデルを動かし始める。スピーカーが話し終わったかどうかは関係なしにね。そうすれば、二つのインスタンスが時間効率よくお互いに会話を中断しながらできる。

ハクソク