AIとグラフ

セミナー概要

6月のマルレクのお知らせです。

一部の方には、6月のマルレクは、量子コンピュータでの最近のブレークスルーを取り上げると予告していたのですが、予定を変更しています。すみません。

今回のセミナーは、次のような構成を考えています。

⚫️ Part 1 「画像とグラフの違いを考える」
⚫️ Part 2 「グラフの認識の難しさ」
⚫️ Part 3 「AIのAgent Model のグラフ表現

Part 1 「画像とグラフの違いを考える」

今回のセミナーでは、まず最初に、現在のマルチ・モーダルを指向するAI技術には、得意とする領域と不得意とする領域があることを、グラフの問題を通じて考えます。

セミナーの Part 1 「画像とグラフの違いを考える」 は、こうした実験と考察をまとめたものになります。繰り返しになりますが、このお誘いでも、その概要を紹介したいと思います。

こうした問題は、たまたま見つかった不具合ではなく、基本的には、現在の大規模言語モデルをベースとする生成AI技術が、人間のもつ数学的認識能力をうまく取り込めていないことの表れだと僕は考えています。

 【 画像の生成 】
GPT4oのDall.E を用いたテキストからの画像生成能力は、素晴らしいものです。

 【 グラフの認識 】
画像としてのグラフの認識は、時々、ハルシネーションを起こしますが、グラフのノードとエッジのラベルを理解し、グラフの隣接行列を構成できるほど高度です。

 【 グラフの生成 】
ただ、グラフの画像の出力に、Dall.Eは向いていません。出力されたグラフの画像は、彼が理解しているグラフの特徴を反映していないし、あるいは、反映させることができないように見えます。

画像を扱うマルチ・モーダルなシステムとして、画像グラフの知覚能力と画像グラフの生成能力には、大きな非対称性があるのです。

 【 一般的な画像とグラフの画像の認識の違い 】

AI: マルチモーダルな生成AI技術は、基本的には、「言語理解と画像理解は、統一したフレームのもとで可能である」と考えるんだ。それは、成功しているように思うよ。

人間: 確かに、言語による表現も画像による表現もembeddingで表現される。
また、現在のAIの成功を支えているのはembedding技術だというのも確かだ。

ただ、グラフは画像としても表現されるけど、グラフをembeddingで表現するのって奇妙だと思わない? 言語的認識と数学的認識は、何かが基本的なところで違っているんだ。

Ai: 数学的認識も言語的認識なしには成り立たないよ。認識の諸能力の言語能力のもとでの「統一」は、さらに進む可能性がある。意識的にせよ無意識にしろ、生成AIが進んでいるのは、そういう道。

人間: それは、うまくいかないと思う。「統一」は、数学的な認識能力のベースの上で、初めて可能になると、僕は思う。

Part 2 「グラフの認識の難しさ」

現在の生成AI技術が、グラフの問題をうまく処理できないだろうことは、AIの世界をいったん離れて、数学的にグラフの認識の問題を考えると、より一層明確になります。

セミナーのPart 2 「グラフの認識の難しさ」は、複雑性理論の観点から、この問題を扱います。

興味深いことは、もし、「万能の人工知能」が誕生したとしても、解けないグラフの問題があるということを数学的に示すことができるということです。こうしたメタレベルの認識は、現時点では、おそらく人間のみが可能なように感じています。

より興味深いことは、今回のセミナーでは十分に触れることはできませんが、前述のような奇妙な認識を可能とする Interactive Proofのような「数学的推論」は、本質的に「確率論的推論」だということです。

「グラフの隣接行列のような数学的対象は、embeddingによる表現には向いていない。」と言いました。 確かに。

ただ、より高次のレベルで、embedding表現のような確率的アプローチが、AIの数学能力の基礎づけに利用される可能性があると、僕は考えています。

量子コンピュータ上のAIシステムの登場が、そうした時代の扉を開くと思います。

Part 3 「AIのAgent Modelのグラフ表現」

僕は、現代のAI技術は、二つの点で大きな弱点を抱えていると考えています。
一つは、先に述べたような「数学的能力」の著しい欠如です。
あと一つは、彼の「知識」の主要な源は、現状では、いったんネット上に巨大に集積された情報だけだということです。

彼は、彼の「外部」に存在する「実在的な対象」(人間・社会・自然・宇宙等々)には無関心に見えます。彼は、また、対象の実在性にも、情報が「真実」であるかにも、関心がないように見えます。彼にとって重要なことは、利用できる情報がネット上にあるか否かです。

こうした問題は、すでに多くの人が関心を持っているように思います。それはとても大事なことだと思います。

残念ながら、今回のセミナーではそうした問題を、主題的に取り上げることはできないのですが、今回のセミナーでは、AIのAgentモデルを取り上げます。

Agent Modelとは、単純化すると、独立した主体としてのAgentが、「外部」の「環境」から入力を受け取り、Agentが内部で処理した結果を、「外部」に出力するというモデルです。

もとになっているイメージは、生物が外界から、食糧やエネルギーや感覚的刺激を入力として受け取り、何らかの反応を外部にかえすというイメージだと思います。

AIのマルチ・モーダル化が、客観的には、AIをAgentとして捉える条件を拡大しています。

外部環境との間だけでなく、複数のAgent(複数の人間・複数のAI)が相互作用するMulti Agent System として、外部環境と人間とAIが構成するシステムを考えることができます。

Multi Agent Model は、グラフで表現できます。

フィールドは違うのですが、COVIT-19の感染予測に、カナダではMulti Agent Modelを利用し成功を収めたと言われています。(人間とコロナ・ウイルスがAgentです。)

AIの未来の展望に、いつかこうした設計図が役に立つようになると考えています。

Agent Modelについて、プリミティブですが、いくつかの事例を紹介したいと思います。

( YouTube で見る )

画像とグラフの違いを考える -- GPT4oと遊ぶ

グラフを読ませる

GPT4oにグラフを描かせようとしたら、いうこと聞かずうまくいかなかったので、今回は、画像として与えたグラフをGPT4oに読ませることにしました。
プロンプトは、次のようなものです。
「次の画像を、ノードと矢印を持つグラフとして解釈してください。」
テストしたのは、次の6つの画像です。
二番目の二つのノードのグラフの把握に最初失敗して、ちょっと不安を感じたのですが、意外とうまく働いてくれました。

セッションをYouTube で見る <- click me
ショートムービー全体の再生リストは、こちらです。
pdfで資料を読む
次のpdf資料は、スクロールで全体を見られます。

画像で与えたグラフの隣接行列を求める

今回は、画像でグラフを与えて、そのグラフの「隣接行列」を求めるという課題にチャレンジします。

といいますのは、GPT4oとのやりとりの中で、彼が(彼女?)が、「グラフの隣接行列知っている」と言ったからです。

【 最初のサンプルで、幻覚を起こして失敗する 】
ところが、三つのノードからなるグラフの認識という最初のサンプルで、失敗してしまいました。原因は、幻覚です。
GPT4oは、与えられた図形のノードに番号を振ってグラフの分析を始めるのですが、「左上のノードをノード 0 」にします。ところが、問題は、与えられた図形には「左上のノード」は存在しないということです。 
生成AIが生み出すハルシネーションについては、皆さん経験があると思います。
「妄想」「虚言」「頭おかしい」とか、いろいろ言われるのですが、今回の幻覚で面白いのは、全部が発狂して妄想モードに入っているわけではないということです。
与えられた課題は、大雑把にいうと、図形を知覚するという人間なら視覚にあたる機能と、知覚された情報を隣接行列に変換するという人間なら大脳の働きにあたる機能の二段階から構成されてています。
今回のハルシネーションは、最初の「視覚」レベルでの異常です。いわば、「幻視」です。そのことは、後段の、視覚に与えられた情報から隣接行列を構成するという課題は(視覚が与えた情報自体が間違っていたのですが)、正しく処理していることを見ればわかります。
マルチモーダルなAIの幻覚がどこで起きるかを考えると面白いですね。

【 それ以降は、立ち直って立派な成績を収める 】
最初でつまづいたのですが、気をとりなおしてテストを続けました。
いろいろ優秀だと思います。結構、難しいグラフの画像から隣接行列うまく取り出すことに何度も成功しています。立派なものです。

セッションをYouTube で見る <- click me
ショートムービー全体の再生リストは、こちらです。
pdfで資料を読む
次のpdf資料は、スクロールで全体を見られます。

隣接行列を与えてグラフの画像を描かせる

グラフの画像から隣接行列を取得することは出来そうなので、今回は、隣接行列を与えてグラフを出力させてみようと思います。
といいますのは、以前に「二つのノードとそれを結ぶ矢印からなるグラフの絵を描いて」というのをやってみたのですが、うまくいきませんでした。
ことばでグラフの形を説明しても、一回のプロンプトではなくfew-shot のプロンプトで修正を重ねても、こちらの意図はうまく伝わりませんでした。
今回は、グラフの隣接行列を理解できるのなら(簡単なグラフについてはそうした能力を持っていることは前回のテストで確認できましたので)、ことばではなく隣接行列でグラフの形を伝えようということです。
結果的には、今回も失敗したのですが、やり取りを通じて気付いたこともあります。

セッションをYouTube で見る <- click me
ショートムービー全体の再生リストは、こちらです。
pdfで資料を読む
次のpdf資料は、スクロールで全体を見られます。

画像とグラフ について 中間でのまとめ

セッションをYouTube で見る <- click me
ショートムービー全体の再生リストは、こちらです。
pdfで資料を読む
次のpdf資料は、スクロールで全体を見られます。

グラフの認識の難しさについて

このPart 2 では、マルチ・モーダルな生成AIのグラフ画像出力のトピックをいったん離れて、グラフの認識の難しさについて、複雑性理論の観点から考えます。

グラフの同型性

前段のPart 1で見てきた GPT4o のグラフ出力(正確に言えば、グラフ画像出力)への不満は、出力されたグラフが我々が期待していたグラフとは違っていたということです。

では、どのようなグラフの出力だったら、我々は満足したのでしょうか?
多分、「我々が期待したグラフと出力されたグラフが「同じ」だったら問題ないけど、あの出力は「違う」グラフだった」と答えるでしょう。

それでは、二つのグラフが「同じ」とは、どういうことなのでしょうか?

このセッションでは、二つのグラフが「同じ」だということ -- 数学的には、二つのグラフは「同型」であるというのですが、グラフの「同型性」について考えます。

セッションをYouTube で見る <- click me
ショートムービー全体の再生リストは、こちらです。
pdfで資料を読む
次のpdf資料は、スクロールで全体を見られます。

頂点の置換とグラフの同型性

今回のセッションでは、前回に引き続き、二つのグラフGとH が「同じ」である -- 数学的に言えば二つのグラフが「同型」である -- ための条件を考えます。

【 補足 -- 同値なグラフの隣接行列の関係 】

隣接行列の話が出たので、スライドでは触れていないことを補足します。

同型な二つのグラフ Gとグラフ Hの頂点を一対一に対応づける置換 f が与えられた時、Gの隣接行列から、次のようにして Hの隣接行列を容易に導くことができます。

置換 f が与えられているので、すべての ( i, j )のペアについて、( f( i ), f( j ) )のペアを計算することができます。この時、Hの隣接行列の f( i )行 f( j )列の値に、Gの連接行列の i 行 j 列目の値を書き込みます。 これで、Hの隣接行列ができあがります。

このことは、グラフGの頂点をf で置換して、Gと同型のグラフHを作ることが出来るなら、辺の保存の条件は自然に導入できることを意味します。

セッションをYouTube で見る <- click me
ショートムービー全体の再生リストは、こちらです。
pdfで資料を読む
次のpdf資料は、スクロールで全体を見られます。

Interactive Proofから見るグラフの非同型性

このセッションでは、Interactive Proof (対話型証明)という証明のスタイルを紹介します。最初は奇妙な議論に思えるかもしれません。

Interactive Proofには、Prover(証明者)とVerifier(検証者)という役割の二人の人物が登場します。

Prover(証明者)は、全知全能で、どんな問題も瞬時に答えを返す能力をもっています。ただし、彼は誠実ではなく、時々、人を欺く嘘をつきます。

Verifier(検証者)は、普通の人間です。理性をもっていて、証明者の主張を検証しようとします。彼は、証明者の言うことを、盲信はしません。

Interactive Proofというのは、この両者 -- 証明者と検証者 -- が対話を繰り返すことで、何かを証明しようというシステムです。

なんか怪しげですね。「全知全能の証明者」を仮定するなんて。まして、その「全能者」が嘘をつくこともあるなんて。怪しさ満点です。こんなシステムで、何か証明できるとは思えないと思います。

でも、こうした証明のスタイルは役に立つのです。Interactive Proofの有効性を初めて示したのが、今回取り上げる「グラフの非同型問題」だったのです。

グラフG0とG1が非同型であることのInteractive Proofによる証明は、スライドに紹介しているのですが、はじめてこの証明を読んだ人は、なぜこれがグラフの非同型性の証明になっているのかわからないと思います。それでいいのです。(でも、考えてみてください。)

Interactive Proofによる証明のポイントは、検証者が納得するまで何度でも証明者との対話を繰り返すところにあります。

グラフG0とG1の非同型性について、スライドの手順で、検証者は、何度も何度も何度も証明者に問い合わせを行います。何度繰り返しても証明者が常に正しい答えを返すなら、そのことがグラフG0とG1が非同型だということの証明になります。

逆に、繰り返しの問い合わせに対して、証明者の答えが正しかったり間違ったりすることがあれば(おそらく正答率は、1/2です)、そのことが、グラフG0とG1は非同型ではないこと、すなわち、グラフG0とG1は同型であることを示しています。

Interactive Proofは、こうしたスタイルで証明を行います。

少し飛躍があったかもしれません。次回は、グラフの非同型問題ではなく、グラフの同型問題がNP問題であることを、Interactive Proofでの証明者と検証者の役割を説明しながら、お話しようと思います。

グラフの非同型問題の複雑性のクラスが、NPより広いPSPACEであることは、Shamir が証明しています。

セッションをYouTube で見る <- click me
ショートムービー全体の再生リストは、こちらです。
pdfで資料を読む
次のpdf資料は、スクロールで全体を見られます。

( blog 「AIとの対話の「心得」としての Interactive Proof」 )

Interactive Proofと証明概念の変化

このセッションでは、Interactive Proofの登場によって証明概念が大きく変化したことをみていきたいと思います。

セッションをYouTube で見る <- click me
ショートムービー全体の再生リストは、こちらです。
pdfで資料を読む
次のpdf資料は、スクロールで全体を見られます。

Interlude -- 「GPT4と遊ぶ」 画像生成を振り返る

前回、グラフの非同型性証明にInteractive Proof という手法を使うという話をしました。Interactive Proofの発見は、数学的証明が、決定論的な演繹に還元されるというこれまでの証明観の、大きな見直しを迫るものでした。ただ、今回のセミナーでは、こうした話題に、深く入ることはできません。興味ある方は、2020年のマルゼミ、「確率と証明」を参照ください。https://www.marulabo.net/docs/pcp/

すこしヘビーな話題だったので、Part 3 に入る前に、今回は幕間として、「GPT4oと遊ぶ」セッションにしてみようと思います。

セッションをYouTube で見る <- click me
ショートムービー全体の再生リストは、こちらです。
pdfで資料を読む
次のpdf資料は、スクロールで全体を見られます。

AIのAgent-Based Model とそのグラフ表現

はじめに

Part 1 では、GPT4o等のマルチ・モーダルな生成AIが、一般的な画像の生成では素晴らしい能力を発揮し、グラフの認識では成功しているように見えるにもかかわらず、グラフの画像の生成では、失敗することを見てきました。

Part 2 では、いったんAIの世界を離れて、数学的対象としてのグラフは、生成AIが少ない頂点数の少ない簡単なグラフでは成功しているように見えるグラフの認識でも、コンピュータにとっては、すぐに「手に負えなくなる」ような、極めて複雑な対象であることを、複雑性理論の立場から見てきました。

【 それはすぐに埋められる小さなスキマ?】

グラフの問題は、生成AIの華々しい成功に比べると、小さなスキマでいずれなんとかなると感じている人も多いと思います。

ただ、僕は、現在のAIの能力の基本的な問題の一つは、我々は、グラフをはじめとする数学的な対象の特殊な性格をAIの能力に組み込むことにまだ成功していないところにあると考えています。

グラフの問題は、そのひとつの表れで、それは、見かけ以上に「大きなスキマ」なのだと僕は感じています。

セッションをYouTube で見る <- click me
ショートムービー全体の再生リストは、こちらです。
pdfで資料を読む
次のpdf資料は、スクロールで全体を見られます。

フォン・ノイマンの「自己複製機械」

Agent Systemという考えの起源の一つは、フォン・ノイマンの「自己複製機械」だと言われています。「Agentとは何か?」、「Agent-Based Systemとは何か?」を考える上で、フォン・ノイマンのアイデアは、参考になると思います。

特に、Agent-Based System の基本的な二つの概念、自律的な存在としての「Agent」と、その「外部」としての「環境」がどういうものかを知るには、いい素材だと思います。

セッションをYouTube で見る <- click me
ショートムービー全体の再生リストは、こちらです。
pdfで資料を読む
次のpdf資料は、スクロールで全体を見られます。

AIの能力拡大とAgentモデル – RAG

このセッションでは、AIの問題にあらためてフォーカスして、現在のAIの能力拡大の動きの中で、Agentモデルが大きな役割を果たしていることを、具体例で紹介しようと思います。

最初に、AIの世界でAgentモデルが注目されるきっかけとなった、RAG(Retrieval-Augmented Generation)の話をします。

ついで、Agent モデルの典型的な適用である ATM (Adversarial Tuning Multi-agent system)の話をしようと思います。

セッションをYouTube で見る <- click me
ショートムービー全体の再生リストは、こちらです。
pdfで資料を読む
次のpdf資料は、スクロールで全体を見られます。