AIに人間のように計画を立てることを教えるにはどうすればよいでしょうか?

この記事は公開アカウント「Reading Core Technique」（ID: AI_Discovery）から転載したものです。

人間の計画は階層的です。夕食を作るといった単純なことでも、海外旅行といったもっと複雑なことでも、私たちは通常、まず頭の中で達成したい目標を概説し、それからその目標をさらに細分化して一連の詳細なサブ目標、サブサブ目標などに分類します。最終的に、実際の一連の行動は当初の計画よりもはるかに複雑になります。

[[344748]]

効果的な計画を立てるには、階層型計画の本質の根底にある抽象的で高レベルの概念を理解する必要があります。今日に至るまで、人間がそのような抽象的な概念を獲得するプロセスは不明のままです。

人間は、この高レベルの概念を自発的に構築し、タスク、報酬、環境の構造に基づいて効率的な計画を立てることができます。同時に、この動作は基礎となる計算の形式モデルと一致しているため、これらの発見は確立された計算原理に基づいており、階層型プログラミングに関する以前の研究と関連しています。

階層計画の例

上の図は、階層的計画の例を示しています。これは、ある人がケンブリッジのオフィスを離れ、インドのパトナに行き、夢の結婚式の装飾品を購入する計画を立てる様子を示しています。円は状態を表し、矢印は状態間の遷移を表します。各状態は、下位レベルの状態のセットを表します。太字の矢印は、通常最初に思い浮かぶ高レベルの状態間の遷移を示します。

ベイジアンの視点

階層型計画を計算エージェントに適用すると、モデルはより高度な計画機能を持つことができます。特定の環境構造下での生成プロセスを想定することで、階層的表現をベイズの観点からモデル化できます。この問題に関する既存の研究には、階層に関する一連の単純化された仮定の下で階層表現を取得するための計算フレームワークの開発、つまり、報酬のない環境の精神的表現の下で人々が計画に便利な状態のクラスターをどのように作成するかをシミュレートすることが含まれます。

クラスターの形成を予測し、そのモデルを人間のデータと比較するために、クラスターの階層的発見と報酬を組み合わせたベイズ認知モデルを作成しました。

静的報酬メカニズムと動的報酬メカニズムの両方の状況を分析し、人間は報酬情報を高レベルのクラスターに一般化し、報酬情報を使用してクラスターを作成することを発見しました。これは、モデルが報酬の一般化と報酬ベースのクラスター形成を予測できることを示しています。

理論的背景

心理学と神経科学が交わる重要な分野は、人間の行動が規定された行動とどのように関係しているかを正式に理解することです。私たちが知りたいのは、タスクを完了した後、AI は次にどのような計画と方法を使用するのか、人間はどのようにして有用な抽象概念を発見するのか、ということです。

この質問が興味深いのは、人間と動物が新しい環境に適応する独自の能力を持っているからです。動物の学習に関する過去の文献では、この柔軟性は目標の階層的表現に由来し、複雑なタスクをさまざまな環境に拡張できる低レベルのサブルーチンに分解できることが示唆されています。

グループ化

グループ化は、アクションがより遠い目標を達成する遅延アクションシーケンスに結合されたときに発生し、通常は、学習が目標指向システムから、アクションが定型的な方法で実行される習慣的システムに移行した後に発生します。

計算の観点から見ると、この階層的表現により、エージェントはオープン ループでアクションを迅速に実行でき、既知の問題に遭遇したときに使い慣れたアクション シーケンスを再利用できます。さらに、確立されたアクション シーケンスを適応させて以前に遭遇した問題を解決できるため、より迅速に学習し、より長い時間枠で計画を立てることができます。

エージェントは、目標に関連する詳細を考慮する必要はありません。たとえば、店に行くという目標は、立ち上がって左足を前に出し、右足を前に出す、などではなく、部屋を出て、歩き、店に入るというように分解されます。

階層的強化学習

エージェントが報酬につながる決定をどのように行うかが強化学習の主題です。階層的強化学習 (HRL) は、階層的学習と計画を記述するための主流のフレームワークになり、HRL モデリングの研究では、モデルを構築するための潜在的な方法に関するアイデアが存在しています。

著者は、人々が自発的に環境を計画を制約する状態のクラスターに計画することを懸念しています。この階層的な計画は、低レベルのアクションを伴い、人間の限られた作業記憶容量に依存するフラットな計画よりも、時間と記憶の点で効率的です。

下の図では、太いノードとエッジは、計画を計算するために考慮され、短期メモリに保持される必要があることを示しており、灰色の矢印はクラスターのメンバーシップを示しています。低レベル グラフ G では、状態 s から状態 g への計画に必要なステップは、実際に計画を実行するために必要なステップと少なくとも同じです (上)。高レベル グラフ H を導入すると、この問題が軽減され、計算コストが削減されます (中央)。同時に、再帰階層をさらに拡張すると、計画に必要な時間とメモリが削減されます (下)。

ソルウェイらは最適な層の正式な定義を提供したが、脳がそれをどのように発見するかについては具体的に述べなかった。最適な階層化は、グラフ構造や環境の観測可能な特徴、特に報酬の分布など、環境の構造に依存すると仮定します。

モデル

エージェントが環境をグラフとして見ていると仮定します。グラフでは、ノードは環境内の状態であり、エッジは状態間の遷移です。これらの状態と遷移は抽象的なものになることもあれば、地下鉄の駅やそこを通る列車の路線のように具体的なものになることもあります。

構造

観測可能な環境はグラフ G = (V, E) として表され、潜在層は H として表されます。 G と H はどちらも重み付けされておらず、無向であり、H はクラスターで構成されます。G 内の各低レベル ノードは 1 つのクラスターにのみ属し、これらのクラスターを接続するブリッジまたは高レベル エッジがあります。クラスター k と k′ 間のブリッジは、v∈k かつ v′∈k′ となるようなエッジが v′∈V の間に存在する場合、つまり H のすべての高レベル エッジには G 内の対応する低レベル エッジがある場合にのみ存在します。

次の図では、色はクラスターの割り当てを示しています。プランニング時に、プランナーは黒いエッジを考慮しますが、灰色のエッジは無視します。太いエッジはクラスター間の遷移に対応します。クラスター w と z 間の遷移はブリッジを介して行われます。

高レベルグラフ（上）と低レベルグラフ（下）の例

報酬を追加する前に、学習アルゴリズムは最適なレイヤーを検出する際に次の制約を受けます。

• 小さなクラスター
• クラスター内の緊密な接続
• クラスター間の疎な接続

ただし、クラスターが小さすぎるのは望ましくありません。極端な場合、各ノードが独自のクラスターになり、階層が役に立たなくなります。さらに、クラスター間のスパース接続が望ましい一方で、基礎となるイメージのプロパティを保持するために、クラスター間のブリッジも存在することが望まれます。

クラスタリングの事前条件として、離散時間ランダム中華レストランプロセス (CRP) を使用しました。階層的発見は、生成モデルを反転して階層的 H 事後確率を取得することによって実現されます。で正式に提示された生成モデルは、この階層を生成します。

賞

グラフ G のコンテキストでは、報酬は頂点の視覚的な特徴として解釈できます。人々は通常、視覚的な特徴に基づいてクラスタリングするため、報酬誘導クラスタリング モデルは合理的です。さらに、各状態はランダムに決定された報酬を提供し、エージェントの目標は総報酬を最大化することであると仮定します。

クラスタリングによって報酬が誘発されると想定しているため、確立された各クラスタには同等の報酬が与えられます。クラスター内の各ノードには、等報酬クラスターを中心とした分布から抽出された等報酬が与えられます。最後に、各表示報酬は、そのノードの同等の報酬を中心とした分布から抽出されます。

推論を単純化するために、まず報酬は一定かつ静的であると仮定します。観測ごとに固定確率で変化する特定の報酬は、動的としてマークされます。

私たちは、人間の行動に関する仮説を検証し、モデルの予測力を理解するために 2 つの実験を行いました。特に、クラスターが報酬の推論をどの程度促進するか、報酬がクラスターの形成をどの程度促進するかを調査します。それぞれの実験では、人間のデータを収集し、それをモデルの予測と比較しました。

クラスター誘導報酬

最初の実験の目的は、報酬が状態のクラスター全体にどのように広がるか理解することでした。グラフ構造がクラスターの形成を促進するかどうか、また人々がノードで観察された報酬をそのノードが属するクラスターに一般化するかどうかをテストしました。

確立する

次のシナリオに従って、32 人の被験者に次に訪問するノードを選択するように依頼します。人間の偏見や未導入のグラフィック構造がないことを確認するために、次の図またはその反転バージョンが参加者にランダムに提示されました。参加者は、より大きなクラスター内にあるラベル付きノードに近いノード、つまり最初のケースでは青いノードの左側にある灰色のノード、2 番目のケースでは青いノードの右側にある灰色のノードを選択すると予測しました。

参加者には次のタスクと関連図が提示されました。

あなたは、複数の独立した鉱山とトンネルで構成される大規模な金鉱山で働いています。鉱山のレイアウトを下の図に示します (各円は鉱山を表し、各線はトンネルを表します)。報酬は毎日支払われ、さらにその日に見つけた金の 1 グラムごとに 10 ドルが支払われます。 1 日に 1 つの鉱山を掘り、その日の金の生産量 (グラム単位) を記録します。過去数か月間、各鉱山では平均して 1 日あたり約 15 グラムの金が生産されていることがわかります。昨日、下の写真の青い鉱山を掘って、30グラムの金を手に入れました。今日は、2 つの鉱山 (灰色の部分) のうちどちらを掘りますか? 選択した鉱山に丸を付けてください。

参加者に示された鉱山地図

ほとんどの参加者は、以下の桃色とラベンダー色のノードによって表されるさまざまなクラスターを自動的に識別し、これらのクラスターに基づいてどのクラスターを選択するかを決定することが期待されます。ラベル 30 (平均よりもはるかに大きい) のノードが桃色のクラスター内にあるため、参加者はラベンダー色のノードよりも桃色のノードを選択すると想定されます。

参加者には、クラスター内の鉱山に類似した鉱山の図が示されました。

推論

メトロポリス・ウィズイン・ギブス・サンプリングを使用し、H 近似にベイズ導出を適用しました。このサンプル セットは、H の後続のサンプリングを通じて H の各コンポーネントを更新し、メトロポリス-ヘイスティングス ステップで他のすべてのコンポーネントを調整するために使用されます。連続成分の提案分布としてガウスランダムウォークを使用し、グループ化された割り当ての提案分布として前提となる CRP 事前分布を使用します。この方法は、定義された効用関数に従うランダムなヒルクライミングアルゴリズムとして解釈できます。

結果

参加者は実グループとシミュレーショングループそれぞれ32名でした。モデルによって出力された最初の 3 つのクラスターを以下に示します (左側の領域)。上位 3 つの結果はすべて同じであり、モデルが色分けされたグループを高い信頼度で識別したことを示しています。

参加者モデルと静的報酬モデルの結果は下の棒グラフ (右パネル) に示されており、次にノード 2 を訪問することを選択した人間とシミュレートされた被験者の割合を示しています。黒の実線は平均を表し、黒の破線は 2.5% および 97.5% パーセンタイルを表します。

クラスタリング実験における報酬一般化の結果

以下の表の p 値は、左側または右側の灰色のノードを選択するのではなく、ヌル値が二項分布していると想定される右側二項検定を使用して計算されます。有意水準は0.05であり、人間の実験結果とモデル結果の両方が統計的に有意でした。

人間の行動と静的報酬モデル

報酬誘導クラスタリング

2 番目の実験の目的は、報酬がクラスタリングを誘発するかどうかを判断することでした。グラフの構造自体がクラスタリングを誘発しない場合でも、隣接する位置にある同じ報酬を持つノードはクラスタリングされると予測されます。

Solway らによる研究によると、人々は階層の境界を越える回数が最も少ない経路を好むことが示されています。したがって、2 つの同一パスのうち、いずれかを選択する唯一の理由は、階層境界を通過するパスの数が少ないことです。これに対する反論としては、人々はより高い報酬のある道を選ぶだろう、というものがあります。

ただし、以下に詳述する設定では、報酬は選択されたパスに沿って徐々に蓄積されるのではなく、目標状態でのみ提供されます。さらに、報酬の大きさは試行ごとに異なりました。したがって、あるパスに沿ったノードの報酬が高いという理由だけで、人々がそのパスを好む可能性は低くなります。

確立する

この実験は、Amazon Mechanical-Turk (MTurk) を使用してオンラインで実施されました。参加者には次のタスクコンテキストが与えられました。

トンネルでつながれた金鉱山のネットワークで働く鉱夫だと想像してください。各鉱山は毎日一定量の金（「ポイント」と呼ばれる）を生産します。毎日、あなたの仕事は、開始鉱山から目標鉱山まで移動し、目標鉱山でポイントを集めることです。特定の日には、好きな鉱山を自由に選ぶことができます。この時点で、最も高いポイントを獲得できる鉱山を選択するようにしてください。その他の日には、利用できる鉱山は 1 つだけです。この鉱山のポイントは緑色で、他の鉱山のポイントは灰色で選択できません。現時点では、利用可能な鉱山にのみ移動できます。各鉱山のポイントが記載されています。現在の鉱山は太い枠で強調表示されます。矢印キー（上、下、左、右）を使用して鉱山間を移動できます。目的の鉱山に到達したら、スペースキーを押してポイントを集め、翌日の作業を開始します。実験期間は100日間（トライアル）となります。

参加者には次の図表（左）が提示されました。左右の非対称性の可能性を制御するために、参加者は、前回の実験と同様に、図に示されているレイアウトまたはその水平反転バージョンのいずれかにランダムに割り当てられました。予想される誘導クラスターも描かれており、参照用にノードに番号が付けられています (右)。

MTurk 参加者に示された鉱山マップ (左) と可能性のあるクラスター (右)

最初のケースは、参加者が任意の鉱山への自由選択ナビゲーションを選択した場合、2 番目のケースは、参加者が特定の鉱山への固定選択ナビゲーションを選択した場合とします。参加者は、無作為な回答を抑制するために、各試行ごとに金銭的な報酬を受け取りました。

各試行において、報酬値は確率 0.2 で変化しました。新しい報酬は[0, 300]の区間からランダムに抽出されます。ただし、試行間では、報酬のグループ化は一定のままでした。ノード 1、2、3 は常に 1 つの報酬値を共有し、ノード 4、5、6 は別の報酬値を共有し、ノード 7、8、9、10 は 3 番目の報酬値を持っていました。

最初の 99 回の試行では、参加者はクラスターの階層構造を構築することができました。実験の最終試行では、参加者はノード 6 からノード 1 に移動する必要がありました。報酬が上記のようなクラスタリングを誘発すると仮定すると、2 つのクラスター境界を越えるノード 7 を通るパスよりも、1 つのクラスター境界のみを越えるノード 5 を通るパスを選択する参加者が増えると予測されます。

推論

固定選択ケースをモデル化するには、100 回の試行すべてにおけるタスクが、参加者に提示された 100 回目の試行と同一であると仮定しました。まず、すべてのテストで一定である静的報酬を想定します。次に、動的報酬、つまり試行ごとに報酬が変化すると仮定します。

モデルが参加者が選択したノードを予測した以前の実験とは異なり、この実験では、開始ノードから参加者が選択したターゲットノードまでの完全なパスの 2 番目のノードに焦点を当てました。そこで、モデルを人工データと比較するために、幅優先探索の変形（以下、階層型BFSと呼ぶ）を使用して、開始ノード（ノード6）からターゲットノード（ノード1）までのパスを予測します。

静的な報酬。各被験者について、メトロポリス・ウィズイン・ギブス・サンプリングを使用して事後分布からサンプリングし、最も可能性の高い層、つまり事後確率が最も高い層を選択します。次に、階層型 BFS を使用して、最初にクラスター間のパスを見つけ、次にクラスター内のノード間のパスを見つけます。

ダイナミックな報酬。動的報酬にはオンライン推論を使用します。シミュレートされた参加者ごとに、各試行のサンプリングは 10 ステップのみ実行され、その後、層別化が保存され、変更された報酬に関する情報が追加されました。次に、保存したレイヤーから再度サンプリングを開始します。人工実験では、報酬は集団全体で常に等しかったものの、各試行の開始時に報酬は確率 0.2 で新しい値に再ランダム化されました。

この推論方法は、人間の参加者が多くの試行を通じて累積的に学習する方法をシミュレートします。この実験では、人々は一度に 1 つのレイヤーのみを記憶し、複数のレイヤーを同時に更新しないと想定しました。このタイプの推論では接続されていないクラスターがより多く発生するため、対数事後確率は接続されていないクラスターにペナルティを課すように変更されます。

結果

人間グループと2つのシミュレーショングループの両方に95人の参加者がいました。ノード 5 を通るパスとノード 7 を通るパスを選択する参加者の数が等しいことは、帰無仮説を表しています。これは、他の情報がない場合、2 つのパスの長さが等しいと仮定すると、参加者がどちらかのパスを他方よりも選択する可能性が等しいためです。

人間の行動と静的および動的報酬モデル

上記の表に示すように、人間による試験と静的報酬モデリングの結果は、α = 0.05 で統計的に有意です。さらに、以下に示すように、人間を対象とした試験の結果は、0.5 を中心とした正規分布の 90 パーセンタイルにあり、帰無仮説の下での予想される割合を示しています。

この図には、静的報酬モデルによって識別されるクラスター (最初の行)、切断されたコンポーネント間で形成されたクラスターを含む静的報酬モデル (2 番目の行)、および動的報酬モデル (3 番目の行) が含まれています。

特定されたクラスターをシミュレートする

静的な報酬。各サンプルを生成するために、1000 回の Metropolis-in-Gibbs サンプリングを使用し、各サンプルのバーンインとラグを 1 に設定しました。静的報酬でのシミュレーションでは、統計的に有意なレベルまでノード 5 を通るパスが確実に優先されます。さらに、目的は人間の行動をモデル化することなので、人間のデータも統計的に有意である（0.0321 < α = 0.05）ことを考えると、この結果は理にかなっています。

人間とシミュレーション対象の選択

ダイナミックな報酬。人間の試験をシミュレートするために、事後サンプリングのために試験ごとに 10 回のメトロポリス・ウィズイン・ギブス反復で 100 回の試験を実行しました。バーニンとラグは再び 1 に設定されます。

動的報酬モデルの下でのシミュレーション対象者のグループは、静的報酬モデルの下でのグループよりも仮説から遠ざかっていましたが、オンライン推論法は静的報酬よりも人間のデータのモデルを作成するのに適しているように思われました。動的報酬モデルでは、56 人の人間の参加者と 54 人のシミュレーション参加者がノード 5 を選択しました (3.4% の差)。一方、静的報酬モデルでは、64 人のシミュレーション参加者がノード 5 を選択しました (18.5% の差)。

上の棒グラフは、選択されたパスの 2 番目のノードがノード 5 である人間とシミュレーターの割合を示しています。黒の実線は帰無仮説を与えられた場合の期待割合を示し、黒の破線は 10 パーセンタイルおよび 90 パーセンタイルを示します。

人間は、階層的な計画をサポートする状態のクラスターに環境を自発的に編成し、さまざまな抽象化レベルのサブ問題に分割することで困難な問題を解決できるようにしているようです。人々は、大小さまざまなタスクを達成するためにこれらの階層的なステートメントに頼っており、多くの場合、最初の試みで成功します。

最適な階層はグラフの構造だけでなく、環境の視覚的特徴、つまり報酬の分配にも依存することを示します。クラスタリングが静的報酬をどのように誘発するか、また静的報酬と動的報酬の両方がクラスタリングをどのように誘発するかを理解するために階層型ベイジアン モデルを構築し、ほとんどの結果が、モデルが人間の行動をどれだけ正確に捉えているかという点で統計的に有意であることを発見しました。