断想：系列入力ベースの強化学習

　最近は状態や報酬などを系列データとして扱う強化学習に興味が出ている。端的に言えばDecision Transformer1 のことになる。

　特に、エピソードをまたいだ(across-episodicな)長い系列を入れることに可能性を感じる。着目点は違うが、やっていることとしてはAlgorithm Distillation2に近い。個人的に期待するacross-episodicの良い点としては、体験した成功例・失敗例をそのまま有効活用してサンプル効率を高めることにある。明示的な体験の参照ができない状況では、ニューラルネットのパラメータに勾配法で知識が反映されるまで例を活かすことができないが、それはどうしても遅くなってしまうのではないかというところが気になっている。

　改善されると嬉しい別の例をコンピュータ将棋で挙げると、（ランダム性を入れずパラメータ更新もない状況の想定でも）全く同じ棋譜で全く同じ負け方をすることを回避できるようになることだと思う。完全に同じ失敗を繰り返すのはあまりに知的でない振る舞いで、見ていてとても気分が悪い。これをなんとかしたい。

　体験を外部情報の一種として捉えると、LLMにおける検索の利用（Retrieval Augmented Generation）と類似した側面もあるのかもしれない。知識をニューラルネットのパラメータへ反映させるには学習量が必要そうなので、プロンプトの参照情報として与えてしまうという発想になる。

課題

　この方針の課題は、今のニューラルネット（Transformer）では入れられる系列長が短いことだと思う。GPT-3.5を例にすると16Kが上限となっている。将棋でどの程度過去の棋譜を入れられるか概算すると、

1局だいたい200手と考えて、片方の手番だけを入れるとして1局あたり100局面で、各局面は9x9トークンになり、たとえば10局分入れようとすると81000トークン

となる。単純にやるとまともに入れられないことがわかる。それに、コンピュータ将棋では推論速度も重要になるので、なんとか動くけど遅いという状況ではメリットがほとんどなさそうだ。できるだけ速度は落とさないままに過去の情報を活用できる必要がある。

対策1: 系列長に対して線形な計算量のアーキテクチャを使う

　もちろんTransformerの、系列長に対して2乗の計算量が必要になってしまう性質は多くの人が改善したいと考えており、様々に研究がされている。最近だとMamba3であるとか、Based4であるといったものが有力なのではないかと囁かれているらしい。

　論文などを多少見てはみたが、状態空間モデルをいろいろこねくり回して上手いことやる手法は数式・概念とかが難しく、さらっと読んですぐに理解できるというものではなかった。ここに関しては、多少興味はあるが自分でめちゃくちゃ試行錯誤していくほどのモチベーションはないし、多くの人が取り組んでいくだろうから、その成果だけを後々享受させてもらうという姿勢で良い気もしている。

対策2: 入れる系列の選び方を工夫する

　先程は単純に1局から100局面を全て入力するという考えで系列長を試算したが、それはあまりにも愚直なやり方ではある。RAGのように、検索概念を導入して、現局面と類似する過去の局面を探して入力に追加するというのも有望だろう。

　また、直感的にヒント情報として重要なのは、良い方向であれ悪い方向であれ予測を大きく外した局面だと思われるので、過去の体験に対してValueの予測ハズレ具合で重み付け（優先順序付け）をするのも可能性があるのではないかと感じる。これは経験再生における優先順位付け（Prioritized Experience Replay5）の発想そのままではある。

　いずれにしても、少量の効果的な状態だけ上手く系列の一部に取り入れることで、計算効率をそこまで下げずに精度に寄与できると面白いと思う。とりあえずはこちらの方向性で考えてみたいか、という気分。

  1. https://arxiv.org/abs/2106.01345↩
  2. https://openreview.net/forum?id=hy0a5MMPUv↩
  3. https://arxiv.org/abs/2312.00752↩
  4. https://hazyresearch.stanford.edu/blog/2023-12-11-zoology2-based↩
  5. https://arxiv.org/abs/1511.05952↩

週記 20231211~20231217

週記

　今週はDecision Transformerの実装をしていたが、あまり上手くいっていない。

　題材としては先週と同じで丸をクリックさせるタスクをやっており、ランダムエージェントで動かした100MステップのデータからDecision Transformerを学習させて、Returnに応じた方策が学習できている事自体は確認できた。

　しかし、動かすときにReturn1を目標として動作させると、Return1を得られる場合の行動しか取らないようになってしまう。つまり、カーソルが丸の中に入っていないのにクリックを連打している。確かに、最終的にはクリックで報酬が入るのでクリック動作自体が強くReturn1と結びついてしまうのはそうなのかもしれない。

　どうもTransformerが画像情報を上手く拾えていない気がする（のでReturnだけに依存した振る舞いをしている）。系列長を小さくするためにだいぶ大きいパッチサイズにしているのが良くないのかもしれないし、画像部分の位置エンコーディングとして学習可能なものではなく三角関数ベースでのx,y位置を指定するものの方が良いのかもしれない。あるいはCNNで埋め込みにいくか。このあたり結局どうした方が良いのかというのが難しい。

　簡単な題材から始めているつもりだったが、これでも全然簡単でなかったということがわかってきたので、さらに簡単にするためGUIから離れてグリッド世界でのActor-Criticからやり直している。

　3x3のグリッド世界で、これまでと同じように上下左右移動 + クリック動作で、自己位置とターゲット位置が重なっているときにクリックした場合だけ報酬を与えるということにする。3x3ならテーブルに乗っけられるのでそれでActor-Criticを書いて、ひとまずこれは1ステップのオンライン学習で上手くできることを確認した。

　ここからまた(1)CNNベースニューラルネット、(2)Transformer で、それぞれどうなるのかというのを見ていくことになるだろうか。グリッドを適宜広げていくと簡単にスパース報酬タスクになるので、この状態でいろいろ試行錯誤することになりそう。

競技プログラミング

　本当は日曜のコンテストまで終わってから書きたいところだったが、今日はAGCだったので原理的に無理だった。

  • ABC333 : パフォーマンス2190 レート1770(+58)

　前回に続いての成功で戻ってきた。これくらいが今の適正値なのではないか。もう少し下かな。

　FのDPがわりと早く解けているかもしれず、自分はひょっとしてDP得意な部類に入るのだろうか？ まぁ競技プログラミング歴で言ったら長い方ではあると思うので、典型DPというのはまだ戦える分野なのかもしれない。

週記 20231204~20231210

週記

　今週からGUI操作のプログラミングを始めている。

今週やったこと

　結局、機械にGUIを直接いじってもらうのがわかりやすいなという考えになって、GUIを操作させるプログラムを書いている。

　当面の目標としては「スクリーンショットを入力、マウス操作を出力としたできるだけEnd-to-Endなニューラルネットワークで将棋所を直接操作して指し、強化学習をしてランダム指しエージェントに勝つ」になるかと考えている。これを向こう1,2年くらいで達成できれば。

　GUI操作のプログラム自体は、UbuntuのC++ならxlibを使えばそこまで大変でもなかった。ただ、学習がとことん大変に思えるのでまだまだ将棋をやる段階ではないと思い、まずはSiv3Dでマウス操作を必要とする簡単なタスクを実装して、それを強化学習で解かせるところから始めている。

　【タスク】ランダム位置に出現する青い丸の中をクリックすると報酬が得られる。1回青い丸をクリックすると別のランダム位置に飛ぶ。（なんかFPSのエイム練習みたいだ。最初はもっと小さい丸にするつもりだったが、あまりにもランダムエージェントが報酬を得られないので丸がどんどん大きくなってきた……）

　ちゃんと方策勾配ベースの強化学習を実装したのは初めてなので、わりと苦労している。今はなんとかギリギリ学習できたような気配があるという段階。

　方策勾配だけでなく、今回エピソードという区切りを設けていないので非エピソディックな設定というのも初めてになっている。報酬に割引が必要というのをようやく実感した。将棋みたいなエピソード区切りが明確なゲームだと割引を考える必然性はあまりないからなぁ。

　今は離散行動で学習させているが、本当はカーソル移動を連続値にしたい。その他やりたいことはポツポツと。

　Pythonが全然好きになれなくて、こういうプログラムでもC++を担ぎ出してくることになるのは結局良くないのではないかという気はしている。今後「なんらかの学習済みパラメータを元にして学習を始める」ということをやりたくなったときにかなり面倒くさそう。このあたりどうするか。

競技プログラミング

  • ARC：パフォーマンス1356 レート1680(-31)
    • とうとう1600台まで落ちてきた。直近6コンテスト連続でマイナス！
  • ABC：unratedにならなければ久しぶりにプラスになりそう。E問題で詰まったときわりと早めにF問題読みにいったのが良かった
  • AHC：理由は自分でもよくわからないが、全くやる気が出なかった。

その他

　少しずつ、休日に自分のやりたいプログラミングができる状態になってきている。強化学習の勘所をもっと理解したいと思いつつ、でもやっぱり強化学習って本当に効率良いのかなという疑いも強い。まぁいろいろ見つつですか。

週記 20231127~20231203

週記

　あまり好ましくない業務が今週にまで食い込んでいたが、なんとかやりきったと思う。いや、若干不穏なところはいくらかあるが……。1年前から考えると状況は良くなっているのに、それでもこんなもんかという気持ちにはなってしまう。

DPO

　週の特に前半でDPOの論文をわりと時間かけて読んでいた。

　別にRLHFなんてやってみたことはないが、面倒くさそうではあり、その大変そうな工程を簡略化できるなら嬉しそう。それに、これ場合によっては一般の強化学習にも影響してくるのではないかと思った。報酬を定義より良い行動/悪い行動の順序付けの方が簡単、という状況はいくらかありそうだ。深い探索と浅い探索（あるいは探索なし）もそういう関係にならないかとか考えるけれど、ボードゲームなら報酬がわかりやすいからこんなことをする必要性はなさそうでもある。一般に、報酬を複雑に（多くの場合、学習を進みやすくさせるため細かく与えようとするから複雑になるのだと思う）するのではなく、疎な報酬から学習できるように頑張るべきではあるんだろうな。

JARVIS-1

　あとはJARVIS-1も若干面白そうではあり、勾配法のパラメータ学習なくても記憶部分に成功例を溜めていけばいくらかの学習（？）みたいな振る舞いにはなると。雑な目で見たら検索でLLMの性能を上げたい話と近いのだろうか（検索対象が外部データじゃなくて過去の体験になるだけ）。まぁ確かに何でもかんでもパラメータに反映させる必要もないのかなという気はする。両方が上手い感じに結びつくと嬉しいことになりそうではある。

　あとはシンボル操作みたいなところがな。論理性とかをどうやって実現すればいいのか。きっとどこかの頭いい人が良い方法を考えてくれると思うので、それを見てちゃんとおぉーとなれるようでいたい。

競技プログラミング

  • AtCoder Beginner Contest 331終了後：レート1711(-12)

　ローリングハッシュをセグメント木に乗せるゲームをあれだけの人が解けるのはすごいことだと思います。それでマイナスになるならそれはもう仕方ないという気分。

その他

　相変わらずやることに迷いがちで、いろいろなことを摘み食いしてはすぐ飽きて放り出す感じになっている。なにか数年単位でやることを決めたいと思って、もう2,3年経っているのではないか。まぁまぁこれが平常運転。

Direct Preference Optimizationを読む（その2）

論文

　その1

でDPOの損失関数

\mathcal{L} _ \mathrm{DPO} (\pi _ \theta; \pi _ \mathrm{ref})= - \mathbb{E} _ {(x, y_w, y_l) \sim \mathcal{D}} \left\lbrack \log \sigma \left( \beta \log \frac{\pi _ \theta (y _ w|x)}{\pi _ \mathrm{ref}(y _ w|x)} - \beta \log \frac{\pi _ \theta (y _ l|x)}{\pi _ \mathrm{ref}(y _ l|x)} \right) \right\rbrack \quad(7)

が導出できたので、この関数の性質を分析してみます。

勾配がどうなっているか

　まず微分してみます。整理するために

\hat{r} _ \theta (x, y) = \beta \log \frac{\pi _ \theta (y _ w|x)}{\pi _ \mathrm{ref}(y _ w|x)}

と置きます。後にこれは暗黙の報酬モデルであることが明らかになりますが、それはさておいて、まずは勾配を求めます。 f = \hat{r} _ \theta(x, y _ w) - \hat{r} _ \theta(x, y _ l)とすると、損失関数の中身は

h = \log \sigma(f)

という形式になっているので、連鎖律で

\frac{\partial h}{\partial \theta} = f' \sigma(f) (1 - \sigma(f)) \frac{1}{\sigma(f)}

となり、ロジスティック関数の性質から 1 - \sigma(f) = \sigma(-f)なので、結局勾配は f' \sigma(-f)となります。この1つ目は

f' _ \theta = \nabla _ \theta \log \pi _ \theta (y _ w | x) - \nabla _ \theta \log \pi _ \theta (y _ l | x)

であり、単純に良いものを増加させ、悪いものを低下させるように働きます。2つ目の

\sigma(-f) = \sigma(-\hat{r} _ \theta(x, y _ w) + \hat{r} _ \theta(x, y _ l))

がその係数であり、つまり報酬によって上手いこと重み付けがなされると解釈できます。

DPOのさらなる理論解析

　まず次のことを定めます。

定義1. 2つの報酬関数 r(x, y)と r'(x, y)が、ある関数 fに対して r(x, y) - r'(x, y) = f(x)となる場合、その2つの報酬関数は等価であるという。

　これは報酬関数の集合をクラスに分割する同値関係を定めていることになります。

　この同値関係について、次の補題2つがあります。

補題1. 同じクラスにある2つの報酬関数は、Plackett-Luceモデル（特にBradley-Terryモデル）の下で同じ嗜好分布を導く
補題2. 同じクラスにある2つの報酬関数は、制約付きRL問題の下で同じ最適方策を導く

　嗜好分布とは回答の良し悪し y _ w, y _ lの組についての分布で、補題1はunder-specification問題としてPlackett-Luceモデル族については知られている話のようです。報酬が一意に上手く定まらないわけですが、逆に補題2から、クラスさえ決まってしまえばどの報酬関数でも問題ないことがわかります。

【補題1の証明】

　一般的なPlackett-Luceモデル（Bradley-Terryモデルはこの内 K = 2の特殊なケース）を考えます。特定の報酬関数 r'(x, y) = r(x, y) + f(x)によって誘導されるランキング上の確率分布を p _ rとします。手順はほぼ自明で、expなので和が掛け算としてくくり出せて約分できるので同じということになります。

p _ r' (\tau | y _ 1, \dots, y _ K, x) = \Pi _ {k = 1} ^ {K} \frac{ \exp(r'(x, y _ {\tau(k)})) }{ \sum _ {j = k} ^ {K} \exp (r'(x, y _ {\tau(j)} ))} \\ = \Pi _ {k = 1} ^ {K} \frac{ \exp(r(x, y _ {\tau(k)}) + f(x)) }{ \sum _ {j = k} ^ {K} \exp (r(x, y _ {\tau(j)} ) + f(x))} \\ = \Pi _ {k = 1} ^ {K} \frac{ \exp(r(x, y _ {\tau(k)})) }{ \sum _ {j = k} ^ {K} \exp (r(x, y _ {\tau(j)} ))} \\ = p _ r (\tau | y _ 1, \dots, y _ K, x)

　補題2の証明もほぼ同様なので省略します。最適方策が \pi _ \mathrm{ref}(y | x) \exp \left( \frac{1}{\beta} r(x, y) \right)に比例する形でかけるのでexpが打ち消し合います。

　そして、以下の定理が成り立ちます。

定理1. 適当な仮定の下で、Plackett-Luce（特にBradley-Terry）モデルと一致するすべての報酬クラスは、再パラメータ化によって表現できる。この再パラメータ化は、ある方策 \pi (y | x)と与えられた参照方策 \pi _ \mathrm{ref}(y | x) を用いて、 r(x, y) = \beta \log\left(\frac{\pi(y|x)}{\pi _ \mathrm{ref}(y|x)}\right)の形をする。

（ちょっと書き方がわかりにくいのですが、要するに報酬をクラスとしてしか指定できていなかったところから、そのうちの一つに定まるという意味合いなのだと思います）

　証明の概要として、最適方策 \pi _ r (x, y)を導く報酬のクラスに属する任意の関数 r(x, y)に対して、以下のような写像 fを考えます。

f(r; \pi _ \mathrm{ref}, \beta) = r(x, y) - \beta \log \sum _ y \pi _ \mathrm{ref} (y|x) \exp \left( \frac{1}{\beta} r(x, y) \right)

これは要するに r(x, y)を \pi _ rの分配関数で正規化するような操作になっています。また、第二項は xについてだけの関数なので、定義1より報酬関数としてのクラスは変わらないことがわかります。ここで、その1で求めた報酬関数についての等式(5)（これはどの報酬関数についても成り立ちます）

r(x, y) = \beta \log \frac{\pi _ r (y|x)}{\pi _ \mathrm{ref}(y|x)} + \beta \log Z(x) \qquad(5)

を代入すると、きれいに消えて \beta \log \frac{\pi _ r (y|x)}{\pi _ \mathrm{ref}(y|x)}だけ残ります。つまり、どの報酬関数もこの写像 fによって一点に潰れるということなのではないかと思います。

　別の見方をすると、分配関数

Z(x) = \sum _ y \pi _ \mathrm{ref} \exp \left( \frac{1}{\beta} r(x, y) \right)

について、定理1を代入すると、

Z(x) = \sum _ y \pi (y|x) = 1

であることが直ちにわかるため、分配関数が1になる、という形で制約づけていると見なすこともできます。

Direct Preference Optimizationを読む（その1）

論文

　Direct Preference Optimizationという手法があるらしいです。

　LLM訓練の最終段ではRLHF(Reinforcement Learning from Human Feedback)として、人手で良し悪しを評価してあるデータセットを使って(1)報酬モデルの学習 (2)それを用いた強化学習 ということが行われたりします。冒頭の論文では、この2ステップは実は適切な損失関数を使った最尤法での学習だけで行えると主張しているようです。報酬関数の推定をすっ飛ばせるという話が面白そうだったので詳しく読んでみます。

前提：そもそもRLHFを確認

　まずRLHFとしてはFine-tuning language models from human preferencesに則るそうです。これだと次の3段階だとしているようです。

  1. SFT（Supervised Fine-Tuning）
  2. Preference Sampling and Reward Learning
  3. Reinforcement-Learning Optimization

(1) Supervised Fine-Tuning

　事前学習されたLanguage Modelから、更に関心のあるタスクでFine-Tuningを行うステップとなります。単純に最尤法で学習して、 \pi ^ {\mathrm{SFT}}を得ます。

(2) Reward Modelling

　SFTのモデルを使って、様々な入力xに対して2種類の回答 y _ 1, y _ 2を得ます。この2つについて、良い方を y _ w、悪い方を y _ lとします。またこの良い悪いの関係を y _ w \succ y _ lと表現します。この嗜好は潜在的な報酬関数 r ^ * ( y, x )によって生成されると仮定されますが、この報酬関数は未知のものです。

　こういった嗜好のモデル化には様々な手法があるらしいですが、ここではその中からBradley-Terryモデル[5]を使うこととします。Bradley-Terryモデルでは、人間の嗜好分布 p ^ *が次のように書けるとしています。

p ^ * (y _ 1 \succ y _ 2 | x) = \frac{\exp(r ^ * ( x, y _ 1 ))} {\exp(r ^ * ( x, y _ 1 )) + \exp(r ^ * ( x, y _ 2 ))} \qquad(1)

要するに報酬にexpをかけたものの割合で考えればいいらしいです。

　ここで、我々の手元には p ^ *からサンプリングされた固定データセット \mathcal{D} = \lbrace x ^ {(i)}, y ^ {(i)} _ w, y ^ {(i)} _ l \rbrace ^ N _ {i = 1}があるとします。報酬関数 r _ \phi (x, y)を適当なパラメータを持つ関数とモデル化すると、最尤法でパラメータを推定することができます。問題を二値分類として仮定して、負の対数尤度

\mathcal{L} _ R (r _ \phi, \mathcal{D}) = - \mathbb{E} _ {(x, y_w, y_l) \sim \mathcal{D}} \lbrack \log \sigma (r _ \phi(x, y _ w) - r _ \phi (x, y _ l)) \rbrack \qquad(2)

を最小化すればいいです。（式 (1)から(2)への変形は、分母分子を \exp(r ^ * ( x, y _ 1 ))で割ればすぐです）。 \sigmaは（標準）ロジスティック関数です。

(3) RL Fine-Tuning Phase

　学習した報酬関数を使って言語モデル自体を訓練します。もとの方策 \pi _ \mathrm{ref} = \pi ^ \mathrm{SFT}から外れすぎないように正則化を係数\betaで入れて

\max _ {\pi _ \theta} \mathbb{E} _ {x \sim \mathcal{D}, y \sim \pi(y | x)} \lbrack r _ \phi (x, y) \rbrack - \beta \mathbb{D} _ {\mathrm{KL}} \lbrack \pi _ \theta ( y | x ) || \pi _ \mathrm{ref} (y | x) \rbrack \qquad(3)

とします。これは微分不可能なので、強化学習として

r(x, y) = r _ \phi(x, y) - \beta (\log \pi _ \theta (y | x) - \log \pi _ \mathrm{ref} (y | x))

を考えてPPOとかで最適化します。

本題

　報酬関数から得られる最適方策を解析的に真面目に考えるといろいろ導けるらしいです。

　まず、先行研究[25, 26]に従うと、先の式(3)に対する最適解は次のようになることが簡単に示せるとのことです。

\pi _ r ( y|x) = \frac{1}{Z(x)} \pi _ \mathrm{ref}(y|x) \exp\left(\frac{1}{\beta} r(x, y) \right) \qquad(4)

　ここで Z(x)は分配関数

Z(x) = \sum _ y \pi _ \mathrm{ref} \exp \left( \frac{1}{\beta} r(x, y) \right)

です。

　付録A.1に証明が書いてあるので先にそれを見ましょう。

　まず、式 (3)を変形していきます。

\max _ {\pi _ \theta} \mathbb{E} _ {x \sim \mathcal{D}, y \sim \pi(y | x)} \lbrack r _ \phi (x, y) \rbrack - \beta \mathbb{D} _ {\mathrm{KL}} \lbrack \pi _ \theta ( y | x ) || \pi _ \mathrm{ref} (y | x) \rbrack \\ = \max _ {\pi} \mathbb{E} _ {x \sim \mathcal{D}} \mathbb{E} _ {y \sim \pi(y|x)} \left\lbrack r(x, y) - \beta \log \frac{\pi(y|x)}{\pi _ \mathrm{ref} (y|x)} \right\rbrack \\ = \min _ {\pi} \mathbb{E} _ {x \sim \mathcal{D}} \mathbb{E} _ {y \sim \pi(y|x)} \left\lbrack \log \frac{\pi(y|x)}{\pi _ \mathrm{ref} (y|x)} - \frac{1}{\beta} r(x, y) \right\rbrack \\ = \min _ {\pi} \mathbb{E} _ {x \sim \mathcal{D}} \mathbb{E} _ {y \sim \pi(y|x)} \left\lbrack \log \frac{\pi(y|x)}{\pi _ \mathrm{ref} (y|x)} - \log \exp \left( \frac{1}{\beta} r(x, y) \right) \right\rbrack \\ = \min _ {\pi} \mathbb{E} _ {x \sim \mathcal{D}} \mathbb{E} _ {y \sim \pi(y|x)} \left\lbrack \log \frac{\pi(y|x)}{\pi _ \mathrm{ref} (y|x) \exp \left( \frac{1}{\beta} r(x, y) \right) } \right\rbrack \\ = \min _ {\pi} \mathbb{E} _ {x \sim \mathcal{D}} \mathbb{E} _ {y \sim \pi(y|x)} \left\lbrack \log \frac{\pi(y|x)}{\frac{1}{Z(x)} \pi _ \mathrm{ref} (y|x) \exp \left( \frac{1}{\beta} r(x, y) \right) } \frac{1}{Z(x)} \right\rbrack \\ = \min _ {\pi} \mathbb{E} _ {x \sim \mathcal{D}} \mathbb{E} _ {y \sim \pi(y|x)} \left\lbrack \log \frac{\pi(y|x)}{\frac{1}{Z(x)} \pi _ \mathrm{ref} (y|x) \exp \left( \frac{1}{\beta} r(x, y) \right) } - \log Z(x) \right\rbrack \\ = \min _ {\pi} \mathbb{E} _ {x \sim \mathcal{D}} \mathbb{E} _ {y \sim \pi(y|x)} \left\lbrack \log \frac{\pi(y|x)}{\pi _ r (y|x)} - \log Z(x) \right\rbrack \\ = \min _ {\pi} \mathbb{E} _ {x \sim \mathcal{D}} \left\lbrack \mathbb{D} _ \mathrm{KL}(\pi (y|x) || \pi _ r (y|x)) + Z(x) \right\rbrack \qquad(14)

　（最後で急に Z(x)のlogが外れて符号が反転するのはどうしてでしょう。しばらく考えたけどわかりませんでした）

　結局 Z(x)は \piによらない関数であるため、argminを考えるときには関係ありません。そしてKLダイバージェンスが最小値になるのはまさにそれらが一致しているときなので、これで証明されました。

　さて、最適な方策

\pi _ r ( y|x) = \frac{1}{Z(x)} \pi _ \mathrm{ref}(y|x) \exp\left(\frac{1}{\beta} r(x, y) \right) \qquad(4)

がわかったので、これを r(x, y)について整理してみます。

r(x, y) = \beta \log \frac{\pi _ r (y|x)}{\pi _ \mathrm{ref}(y|x)} + \beta \log Z(x) \qquad(5)

となります。真の報酬 r ^ *を考えたときにもこの式が成立します。そして、式 (2)で表現したように、Bradley-Terryモデルの下では最適化したい負の対数尤度が報酬の差だけに依存するので、分配関数の部分が打ち消されます。（ここからの式変形がわざわざ付録A.2で書かれていますが、あまりにも自明なのでなんでこれがあるのかがよくわかりません）。単純に式 (2)に入れ込んで

\mathcal{L} _ \mathrm{DPO} (\pi _ \theta; \pi _ \mathrm{ref})= - \mathbb{E} _ {(x, y_w, y_l) \sim \mathcal{D}} \left\lbrack \log \sigma \left( \beta \log \frac{\pi _ \theta (y _ w|x)}{\pi _ \mathrm{ref}(y _ w|x)} - \beta \log \frac{\pi _ \theta (y _ l|x)}{\pi _ \mathrm{ref}(y _ l|x)} \right) \right\rbrack \qquad(7)

を損失関数として学習させればいいそうです。Pythonでのコード的に書くと

import torch.nn.functional as F
def dpo_loss(pi_logps, ref_logps, yw_idxs, yl_idxs, beta):
    """
    pi_logps: policy logprobs, shape (B,)
    ref_logps: reference model logprobs, shape (B,)
    yw_idxs: preferred completion indices in [0, B-1], shape (T,)
    yl_idxs: dispreferred completion indices in [0, B-1], shape (T,)
    beta: temperature controlling strength of KL penalty
    Each pair of (yw_idxs[i], yl_idxs[i]) represents the
    indices of a single preference pair.
    """
    pi_yw_logps, pi_yl_logps = pi_logps[yw_idxs], pi_logps[yl_idxs]
    ref_yw_logps, ref_yl_logps = ref_logps[yw_idxs], ref_logps[yl_idxs]

    pi_logratios = pi_yw_logps - pi_yl_logps
    ref_logratios = ref_yw_logps - ref_yl_logps

    losses = -F.logsigmoid(beta * (pi_logratios - ref_logratios))
    rewards = beta * (pi_logps - ref_logps).detach()
    return losses, rewards

とのことです。

週記 202311120~20231126

週記

　今週も一瞬だっった。どうしてこんなに早く過ぎ去ってしまったんだっけ。木曜日も休みだったはずなのに。だいたい本を読んでいる時間が長かった気がする。プログラミングをやる気がさっぱり起きず、将棋拡散モデルについては一切触れていない。

断想

　この土日は特に「やっぱりまた強化学習じゃね？」という気分で、Sutton & Barto本の第2版とかを買って（今更！）ぼちぼちと読んでいた。特に方策勾配定理あたりのところが気になって他の本とかWebページも見ているが、説明する人によって比例する量で止めたり期待値まで出しきったり、エピソディックな設定だったりそうじゃなかったり、なんか違いがあって難しい感じがしている。

　そういえばゲーム系だとエピソディックな設定が多いけど、1プレイとか1対局で区切らずにやってみたいということもチラッと思ったりする。もっと長期的に時間スケールを持つエージェントを仕立てたいというか。

　実践的には、昨今だと方策勾配法を使うならほぼPPOになっているんだろうか。しかしPPOも細かい工夫が実は大事とか大事じゃないとかで、イマイチ腑に落ちる感覚を得られていない。このあたりは実装と実験を繰り返さないとどうにもならなさそう。

　あと、そもそもやっぱり方策勾配法を直接使ってパラメータ更新していくことがどれだけ効率良いのかというのは自信がない。もう少しメタな反省と行動決定を求めたくなる気もする（直近一連の行動について振り返り、こういうところが悪かったので次はこうしてみよう、という思考ができないと、パラメータ更新だけでサンプル効率を上げきれるのか？ という疑問が残る）。

　LLM関連でそういうことをなにか上手いこと引っ掛けられないか、という曖昧な構想。まぁなにかやるとしたら、題材としては将棋を選ぶことになるのかなぁ。

競技プログラミング

  • AtCoder Beginner Contest 330終了後：レート1723(-32)

　なかなか下げ止まらない。解けなかった問題の復習すらしていないのでこんなもんかなという気もしつつ、これくらいで落ち着いてくれればいいんだけど。

その他

　読書の量がちょっと増やせてきているのは良いことだが、わりと目は滑っているのでそういう意味で調子は良くないとは思う。

週記 202311113~20231119

週記

　業務の方でいろいろ忙しい（？）せいで一週間があっという間だった。厳しい。

拡散モデル

(1)手駒まで生成できるようにした。

　まぁこれはやるだけではあるんだけど、手駒の表現をどうするかという問題は若干あり、今は各持ち駒に1トークンを割り当てている。現状は1つの局面を「81マス + 手駒先後で14個 + 手番を表す1個」で96トークンの系列としてTransformerに投げている。凝ろうと思えばいくらでもやれそうだが、こんなところ考える方が面倒だ。

(2)条件づけをできるようにしている

　ランダムな局面生成ができてもしょうがないので、現局面を条件として、次に有り得そうな局面を作りたい。最初は条件の与え方を「別トークンとして与えてCross-Attention」としていたのだが上手くいかず、「チャンネル方向に連結して入力」だとやや上手くいく気配が出てきている。が、どうも次の手ではなく現局面をそのまま返す意味のない学習をしてしまっているようだ。学習部分のなにかをミスしている気がするが、調査は後日。

　とりあえず、1棋譜だけをデータセットとして過学習させて上手くいくかの確認結果。

項目 結果
条件となる現局面
生成結果
教師局面

　全く同じものが出てきてしまっている。

　条件づけのやり方もどうするのが良いのかよくわからないな。こういうのは実装を読まなきゃわからなさそうなので、論文だけではどうにもか。

　条件づけを強めるためにClassifier Free Guidanceとかもできるはずで、そういうところもまだ全然わかっていない。先は長い。

競技プログラミング

  • ABC329 : レート変化 1841→1820(-21)
    • マージテク解かれすぎ回。E問題で詰まり過ぎていたせいで、知識で勝ちにならなかった。
  • ARC168 : レート変化 1820→1755(-65)（Predictor調べ）

　わりとちゃんと時間中は考えられていて良い感触なのだけど、感触と結果が一致するわけでもなく、かなりレートが下がってきた。競技プログラミングは自分の頭が悪いということを何度でも確認できるとても良い趣味です。

　土日のコンテストが終わってから週記書きたいと思ったがレート更新が間に合わないな。

その他

　NeRFとかGuassian Splattingとか、3D再構成についてのモチベーションが地に落ちている。そこができてもどうにもならないなという気持ちが強い。

　拡散モデルも土日のどちらかしか触れていない状況で、こんなのではいつまで経っても終わらない。悲しみ。

内発報酬だけで勝ちを目指せるのか断想

　ボードゲームで（ここでは具体的に将棋で）、最終的な勝ち・引き分け・負けに(+1, 0, -1)とか、(+1, 0.5, 0)とか、報酬を割り当てて最大化目指して強化学習するのがある程度上手くいくのはわかる。そういう明示的な報酬を与えずに、内発報酬のようなものだけで勝ちを目指すことは可能なのだろうか。

　とても強いエージェントを作りたいなら明示的な報酬を入れたほうが良いだろう。勝ちを目指すことが内発報酬だけで実現できるのか考えたいので、比較する対戦相手はランダム指しエージェントくらいで良い。「ランダム指しをするエージェントに対して有意に勝率の高いエージェントを内発報酬だけで作れるか？」という疑問になる。

　内発報酬としてある1つのシンプルな形は、その状態を訪れた回数に応じて、少ないほど大きい報酬を与えるというものになると思う。しかしそれで勝ちを目指すようになるとは思えない。将棋だと状態数が多すぎるの明示的に訪問回数を記録しておくことはできないが、もし仮にできたとして、単に新規な局面ばかりに行っても勝ちに方向づけられてはなさそう。

　局面だけじゃなくて結果は要りそうだ。1つの対局が終わったときに、その対局が「勝ち・引き分け・負け」の3種類のうちどれであったかという情報はもらえるとする。流石にそれがないと全くできない、ナンセンスな状況設定だとは思う。しかし、勝ちで+1という報酬は与えられない。言い換えれば、「1つの対局が終わったときに、謎のラベルA, B, Cのどれかがゲームの内容に応じてなんらかの法則にしたがってやってくるが、そのうちどれが目指すべきラベルなのかは教えられない」ということになる。

　勝ちと負けの非対称性は、負けることは簡単（すぐ投了すれば良い）が、勝つことは簡単ではないというところにあるのだと思う。対戦相手は投了を含まないランダム指しをするとして、こちらは投了を含めた合法手をとりあえずランダムに選びまくってみると、得られるラベルA, B, Cのうちに偏りが出てくる。負けに相当するラベルが多く出てくるはず。

　このラベル自体のカウントとして、得られにくいものを目指すとすればどうか。しかし、それだと最大でも勝率が5割にしかならない（勝ちが支配的になるとそれがたくさん得られるラベルになるので、勝ち、負けが逆転する）。「最初の方は投了しておいて勝ちラベルを確定させてからそれを目指す」とかそういうヒューリスティックなことを考えたいわけじゃないのでそれは無視する。（本質的に「投了」というのも一つの行動に過ぎず、なんか行動A_35を選んでみるとすぐ特定のラベルが返ってくるなぁという状況に過ぎない）

　なんらかの確率、あるいは量的指標みたいなものを最小化しようとすると自然と勝ちを最大化するようになってほしい。別にこの記事で結論は出ない。なんかできそうな気はするし、しかし下手をすると引き分けの方が実現が難しいので引き分けを目指すエージェントとかにもなりかねないのかもしれない。

　なにか有効なことを考えているのかどうかが自分でもわからない。ゲームが作られ、「勝ち」の状態が定義された時点で、もうその状態を目指すべきというだという情報が内包されている。「勝ち」とはどれか？ ということ自体を探らなければいけないゲームとはいったいどういうことなのか。

　ただ、根本的に将棋というゲームを生み出すことを考えると（人工知能には人間にできることは全てできてほしいめ、「将棋というゲームを考案すること」もできないといけない）、勝ちというのがどういう状態であるかというのを内部側から考えないといけない瞬間は出てきそうだ。

　わざわざゲームなるものを考え出し、それで勝敗を競いたがる、という性質がどういう考え方をすれば出てくるのか、という点が最近ちょっと気になっている。

週記 202311106~20231112

週記

　平日の5日中で4回も出社してしまったのもあって、疲労感も強く、一週間があっという間に過ぎ去った感覚になっている。

拡散モデル

　以下の論文のアイデアが良さそうと感じており、

まずは標準的な拡散モデルから触っておくかということで将棋を題材にちょっと進めている。例題ということで、floodgateの棋譜を使って、条件なしで局面（手駒もなく盤面だけ）を生成させている。

　UNetは9x9の将棋盤に使おうとすると、途中のボトルネック部分でサイズが壊れてしまうようだったので、全部TransformerでとりあえずShapeの整合性がつくようにしている。Transformerが性能良いかどうかはわからないけど、トークン化すれば適当にぶち込めるという便利さはある。コードは以下の通り。

　まぁHuggingfaceのtutorialを参考にぼちぼち変更を入れただけなので特に見るべきところもない。ノイズスケジューラのところが隠蔽されると本当に特別なことがなにもないので、そこを自前実装しなければ理解にはならないだろうな。将棋部分ではcshogiが便利でありがたかった。

　10エポックほど回してみたが、普通に二歩の局面が出てきたりするのでややイマイチな印象ではある。

　まぁ大まかには「こういう局面ありそうだよね」という気配はある。今後は

  • 手駒の追加
  • MaskGIT（Masked Generative Image Transformer）形式の導入
  • 条件付けとしての現局面を導入して次局面を生成させる
  • 読み手数導入

などを考えてはいる。どこまでやる気が続くかはわからない。

　拡散モデルで世界モデルをやろうとすると、拡散モデルのタイムステップと世界モデルのタイムステップで2つタイムステップが出てくるのでやや混乱しがち。

ゲーム

　だいたいリバース：1999をやっていた。第4章『群虎黄金』の最後までクリア済み。2,3,4章はどれも終わり方が印象的だった。迂遠な言い方も多くて若干理解するのが難しいところは多いんだけど、完全に意味不明でとっ散らかっているわけではないバランス感。でも全体的な世界観とかまだ掴みきれてないのはテキストなにか読み落としてしまったからだろうか。

読書

　円城塔とか伊藤計劃とか、以前読んでいたSFを振り返る時期が自分の中で到来している。自分が機械学習系の分野に足を踏み入れるきっかけになったと言えばそうなんだろう。そう思えば今は微妙に変な道に来てしまってはいないか。気づいたら思ってもいなかった方向に進んでいることはよくある。

その他

　しばらく若干忙しそうなのが不穏。忙しいというか、なんか、微妙。