過去・現在・未来

【 7/31 マルレク「コンピュータ上のグラフ理論の進化」概要 】 現在のLLMベースのAIに数学的能力を統合したいというのが僕の大きな問題意識なのですが、まだまだ考えなければいけないことがたくさんあります。二つの能力の統合には、一定の時間が必要だと思います。 ただ、言語のモデルと数学のモデルとが統合されうるのであれば、両者はある共通の特徴を持っているはずです。そうした特徴は、カテゴリー論によって与えられると考えています。 当面、グラフとAgent モデルの二つを糸口にして、そうした共通の特徴を考えることから始めていきたいと思います。 【 7/31 マルレク「コンピュータ上のグラフ理論の進化」講演ビデオと講演資料のURLです 】 セミナーは4つのパートに分かれています。個別にも全体を通してもアクセスできます。 -------------------------- 全体を通して見る -------------------------- 　●  「コンピュータ上のグラフ理論の進化」セミナーの講演ビデオ全体の再生リストのURLです。全体を通して再生することができます。 https://www.youtube.com/playlist?list=PLQIrJ0f9gMcPxLEAjCXf9wYkOvMB0fHzf 　●  講演資料全体を一つのpdfファイルにまとめたものはこちらです。 「コンピュータ上のグラフ理論の進化 」講演資料 https://drive.google.com/file/d/1shyrgEV9aHyYet5MMXi3RtdNFX48pFxb/view?usp=sharing -------------------------- パートごとに見る -------------------------- 　●  Part 1  はじめに – 「AIとグラフ」連続セミナーの流れ 　　　講演ビデオURL : https://youtu.be/p5bRaHBnsTI?list=PLQIrJ0f9gMcPxLEAjCXf9wYkOvMB0fHzf 　　　講演資料 pdf : https://drive.google.com/file/d/1wdmxRfH-87-I8FQt_K0zHfgf9FhgbW4M/view?usp=sha...

【 6/29 マルレク「AIとグラフ」の概要 】 今回のセミナーでは、まず最初に、現在のマルチ・モーダルを指向するAI技術には、得意とする領域と不得意とする領域があることを、グラフの問題を通じて考えます。 セミナーの Part 1 「画像とグラフの違いを考える」 は、こうした実験と考察をまとめたものになります。 現在の生成AI技術が、グラフの問題をうまく処理できないだろうことは、AIの世界をいったん離れて、数学的にグラフの認識の問題を考えると、より一層明確になります。 セミナーのPart 2 「グラフの認識の難しさ」は、複雑性理論の観点から、この問題を扱います。 興味深いことは、もし、「万能の人工知能」が誕生したとしても、解けないグラフの問題があるということを数学的に示すことができるということです。こうしたメタレベルの認識は、現時点では、おそらく人間のみが可能なように感じています。 【 6/29 マルレク「AIとグラフ」講演ビデオと講演資料のURLです 】 セミナーは3つのパートに分かれています。個別にも全体を通してもアクセスできます。 -------------------------- 全体を通して見る -------------------------- 　●  「AIとグラフ」セミナーの講演ビデオ全体の再生リストのURLです。 全体を通して再生することができます。 https://www.youtube.com/playlist?list=PLQIrJ0f9gMcNh55bPi6AdHDHkfBmmK7mk ●  講演資料全体を一つのpdfファイルにまとめたものはこちらです。 「AIとグラフ 」講演資料 https://drive.google.com/file/d/1SHyd1ZN268E7ABJQAzS9RlRdzB6SczMk/view?usp=sharing -------------------------- パートごとに見る -------------------------- 　●  Part 1  画像とグラフの違いを考える 　　　講演ビデオURL : https://youtu.be/EVm_hiMP4-w?list=PLQIrJ0f9gMcNh55bPi6AdHDHkfBmmK7mk 　　　講演資料 ...

【 6月の マルレク「AIとグラフ」講演ビデオと講演資料を公開しました。 】 MaruLaboでは、定期的に以前行ったセミナーのコンテンツを公開しています。 今回公開したのは、2024年6月29日に開催したマルレク「AIとグラフ」のコンテンツです。 6月の マルレク「AIとグラフ」は、次のような構成をしています。 　　⚫️ Part 1 「画像とグラフの違いを考える」 　　⚫️ Part 2 「グラフの認識の難しさ」 　　⚫️ Part 3 「AIのAgent Model のグラフ表現 以下、それぞれのパートの概要を紹介し、あわせて、事後になりますが、それらについての自分のコメント（ ＊ に続く部分）を補足したいと思います。 【 Part 1 「画像とグラフの違いを考える」概要とコメント 】 このパートで扱っているのは、現在のマルチ・モーダルを指向するAI技術には、得意とする領域と不得意とする領域があるという問題です。 GPT4oのDall.E を用いたテキストからの画像生成能力は、素晴らしいものです。また、画像としてのグラフの認識は、時々、ハルシネーションを起こしますが、グラフのノードとエッジのラベルを理解し、グラフの隣接行列を構成できるほど高度です。 ただ、グラフの画像の出力に、Dall.Eは向いていません。出力されたグラフの画像は、彼が理解しているグラフの特徴を反映していないし、あるいは、反映させることができないように見えます。 ＊「画像」という同じ言葉で括られていても、我々が直接的に「見る世界」に存在する視覚に与えられる情報に基本的には還元される一般的な画像（写真や絵画のような）と、グラフの画像のように視覚情報を通じて与えられるにせよその背後にある数学的に規定されている特徴の抽出を必要とする数学的イメージとは、認識の対象として存在のありかたが異なります。Diffusion model にはそうした区別はありません。数学的対象は、視覚によって捉えられるわけではありません。 ＊ 画像生成技術の「成功」は、基本的には、Diffusion modelの成功によってもたらされたものです。ただ、実際のAIによる画像生成は、生成AIが得意とする言語情報を利用する能力（それは数学的な対象を認識する能力とは異なるものです）によって強く「補完」され、さらに、その生成は生成AIが...

【 Church-Turing Thesisの変化と量子情報理論 】 このセッションが、今回のセミナーに向けた最後のセッションになります。 このセッションでは、「計算可能性理論」から「計算複雑性理論」への発展を、 Church-Turing Thesisの変化・発展として振り返り、あわせてそれが現時点でどのように変化を続けているのかを見ていきたいと思います。 以下は、その大雑把な流れです。 【 1920年代 -- ヒルベルト・プログラム 】 ヒルベルトは、全ての数学的命題の真または偽を決定する方法が 存在すること、数学の形式化が矛盾を含まないことが証明しようと しました。 【 1930年代 -- ゲーデルの不完全性定理 】 ゲーデルは、真または偽を決定する方法が存在しない命題が 存在すること、また、数学の形式化が矛盾を含まないことの証明 が不可能であることを示しました。それはヒルベルトのプログラムが、 遂行できないことを意味しました。 【 1950年代 -- チャーチ＝チューリングのテーゼ 】 「証明可能＝計算可能」なものには限界があることは、1950年代 には、チャーチ=チューリングのテーゼとして定式化され、一般に 広く認められるようになりました。ただ、それは、我々の認識の「限界」と しては、非常に荒い、かつ、抽象的で原理的な限界を与えるもので しかありませんでした。 【 1970年代 -- 計算複雑性理論の登場 】 クック、レビン、カープらは、計算可能だが実際には手に負えない 計算である領域を精緻に分類しようとし、計算複雑性理論が生ま れます。 「難しい計算」が「易しい計算」には還元できないことを主張する 「P = NP ? 問題」は、現在も未解決です。 【 1980年代 --  チャーチ＝チューリング＝ドイッチェのテーゼ 】 ドイッチェは、ファインマンの自然をシミュレートする量子コンピュータというアイデアに刺激を受けて、計算は、物理的な過程として実現されると主張して、チャーチ=チューリングのテーゼを拡大しました。ただ、80年代は、まだ、量子コンピュータは物理学者の頭の中の概念としてしか存在していませんでした。 【 1990年代 -- 量子複雑性理論とショアのアルゴリズム 】 ベルンシュタインとバジラーニによって、量子複雑性の理論が登場し、BQPという新...

【 量子チューリングマシンとBQPクラス 】 1993年に、Bernstein と Vazirani は、これまでのTuringマシンの拡大である「量子Turingマシン」を新しく定義して、その上で複雑性理論を展開しました。 ここから始まったこの複雑性理論の新しい分野を「量子複雑性理論」と呼びます。量子複雑性理論は、現在の複雑性理論の中心分野です。 量子複雑性理論で最も基本的なクラスは、BQPです。それは、従来の複雑性理論での多項式時間で決定可能な複雑性のクラス P に相当するものです。 ただし、量子Turingマシンの特性として、その出力は古典的なTuringマシンのように常に確定した値を返すのではなく確率分布として与えられます。 BQPは、“Bounded error, Quantum, Polynomial time” の略です。 この Bounded error は、このマシンの出力の「誤り」が一定の確率（一般には 1/3 を使う）以下であることを表しています。 その点では、BQPは古典的な複雑性理論でのBPP (bounded-error probabilistic polynomial time)によく似ています。 【 量子コンピュータの理論的可能性をめぐって先行した議論 】 「量子コンピュータ」は、今から約40年前(1982年)のFeynmanの洞察を発端とします。彼の論文に刺激を受けて DeutschがChurch=Turing Thesis を拡大することを提案します(1985年)。その後、 Vaziraniが量子チューリングマシンを構成し、量子複雑性の基本的クラスBQPを提案します。(1993年) この間の理論展開は、目覚ましいものです。 こうした流れの頂点は、1994年のShorの、量子コンピュータによる素因数分解のアルゴリズムを発見です。 「量子コンピュータ」が広く注目され研究者が爆発的に増大します。 このセッションでは、これらの議論の概略を紹介したいと思います。スライドを参照ください。 【 Church = Turing テーゼの拡大 】 この間の議論で注目すべきことは、「計算可能性理論」のエッセンスとしての「Church = T uring テーゼ」の拡大の動きです。 古典的なChurch = Turing テーゼは、次のような...

【 確率的チューリングマシンとBPPクラス 】 #コンピュータと数学2 今回のセッションでは、「確率的チューリングマシン」と呼ばれるチューリングマシンの拡大の話をします。 「確率的チューリングマシン」の構成の仕方は、前回見た「非決定性チューリングマシン」の構成とよく似ています。 「確率的チューリングマシン」の振る舞いを説明する前に、「非決定性チューリングマシン」の振る舞いについて、少し補足しておこうと思います。 【 前回のセッションの補足 】 前回のセッションで、「非決定性チューリングマシン」の振る舞いを説明したblog記事で、「チューリングマシンの拡大では、新しい計算を定義することに意味がある」というような少し極端な議論を述べました。また、それに対して、一つの入力に対して実行のたびに異なる結果を返すような「計算」に意味はないという当然の意見も紹介しました。 ここで補足したいのは、「非決定性チューリングマシン」は、見かけほど無茶苦茶な計算を定義しているわけではないと言うことです。 次のことに注目してください。 一つには、「非決定性チューリングマシン」は、複数（それは膨大な数になるかもしれないのですが有限です）の並行に動作する「決定性チューリングマシン」でシミレート可能だということです。前回のセッションで見たように、「非決定性チューリングマシン」を、そのツリー構造の中で「決定性チューリングマシン」を表すパスを指定するテープを追加すれば、「決定性チューリングマシン」でシミュレートすることが可能です。 　 それが非決定論的に振る舞うように見えるのは、それが概念的には、無数の（有限個です）決定論的に振る舞うチューリングマシンの可能な全体を表現しているのに、我々が 見るのは、そのうちの一つのチューリングマシンの出力だけだからです。 【 非決定性チューリングマシンがある入力をaccept あるいは reject する条件 】 注目すべきもう一つのことは、先のことと関係しているのですが、「非決定性チューリングマシン」がある入力を「受理 (accept)」または「拒否 (reject)」する条件です。 大雑把に言えば、チューリングマシンがある入力を「accept」すると言うのは、その入力が表す命題が正しいと認めることで、「reject」すると言うのは、その入力が表す命題を正しく...

【 非決定性チューリングマシンとNPクラス 】 このセッションから新しいPart 「チューリングマシンの拡大と複雑性クラス」が始まります。 「計算可能性理論」のエッセンスは、「計算可能な計算はすべて、ある帰納的チューリングマシンによって実行されるものである」という「チャーチ=チューリングのテーゼ」です。 このテーゼによれば、「計算可能な計算」という数学的な性質は、「あるチューリングマシンによって実行されるもの」として、ある機械（チューリングマシン）の振る舞いと対応づけられることで定義されています。 興味深いことは、「計算可能な計算」という数学的な性質と機械の振る舞いを結びつけるこの「テーゼ」自身は、数学的な命題では無いことです。それは、人間の数学的認識の特徴について語っているのですが、数学的に証明されるような性質のものではありません。 「チャーチ=チューリングのテーゼ」自体を拡大することも可能です。実は、「量子コンピュータ」の登場は、そうした「テーゼ」の見直しと深い関係があります。それについては、このあとのセッションで見ていきたいと思います。 【 チューリングマシンの振る舞いを変える 】 このセッションでは、「テーゼ」の枠組みを大きく変えるのではなく、チューリングマシンの概念を拡大してその振る舞いを変えることを考えてみましょう。新しい数学的性質を定義するのが目的です。 　　「ある数学的性質 Lの計算とは、ある拡大された 　　チューリングマシンMで実行されるものである」 こんな感じなのですが、一つ問題があります。それは、「チューリングマシンの拡大」は、口で言うほど簡単ではないからです。 そもそもチューリングマシンは数学的には万能で、「帰納的チューリングマシン」ならは、計算結果が返る計算可能なものは、すでにすべてカバーしています。（「帰納的」という条件を外した、一般のチューリングマシンには、「停止」する保証はありません。） このセッションで行う、チューリングマシンの拡大は次のようなものです。 「普通のチューリングマシンは、一つの入力に対して一つの出力を返す」 「それがどうした」 「我々は、チューリングマシンを、一つの入力に対して複数の出力を返すように拡大する」 「そんなのチューリングマシンと言わない」 「だから、「拡大」だと言っているだろ」 「どうすんの？」 「普通の...