イベント / EVENT

2019年度 第3回 Q&A

第3回 2019年11月7日(木)

理論計算機科学入門 有限と無限のあいだ
-数学的理論から、AI・自動運転-

蓮尾 一郎

講演当日に頂いたご質問への回答(全22件)

※回答が可能な質問のみ掲載しています。

数学基礎論とはどんな分野ですか。どうして応用数学の一分野なのですか?

歴史が長い分野であり、専門家でない私が答えるのはおこがましいのですが。。。 私の好きな答えは次のようなものです: 「数学者の営為(=証明を書くこと)自体を対象として、これを数学的にモデリングして解析する(=定義して定理を述べてこれを証明する)数学の一分野」。
数学的理論の外にある現象(=数学者の営為)を解析しようとする点で、応用数学の一分野だと私は思っています。同時に、基礎論がゆらぐと数学全体がゆらぐという意味で、数学全体の基盤とも言えます。この2面性が、メタ言及(数学者の数学的研究)の面白いところです。

数学基礎論が応用数学?

Q1 のような2面性があります。実際のところ、数学基礎論を応用数学と思っている人はあまり多くないと思いますが、計算機科学(特に自動証明など)をやっていると「応用だなあ」と実感することもしばしばです。

今のAIが微分可能な評価関数の最適解を求める「多様体」をベースにする体系と考えるならば、離散グラフをベースにする旧AI(論理系、ルールベース)との関係を結ぐ理論は何を使えば良いでしょうか。(最近ではグラフCNN等も使われますが、これをシンボルグランディングの手がかりと考えて良いのか悪いのか?)

これは難しい問題です! グラフCNNも一つの答えだと思います。私達の研究チームも具体的な答えに対する個別の答えをいくつか出しているところですが、これらがある程度出揃ったところで再検討することで、一般的な枠組みが見えてくるのではないでしょうか。研究はまだまだこれからです。

メタ的な質問になりますが、今回のように理論的な(テクニカルな)講演を、非専門家の方々にする際に気を付けていること、分かりやすくするためのコツ等はありますか。

私は上手でないのでえらそうなことは言えませんが。。。 聴衆のみなさんの顔色を(いい意味で)うかがうのが重要と思います。伝わっているときは目の輝きが違いますもんね。あと、わかりやすい例や逸話、整理の仕方、切り口をいくつか作ろうと気をつけています。すみません、えらそうに語りました。

オートマトンの「メモリ」が何なのか分かりませんでした。定義ありました?

定義ありませんでした! するどい!
「過去に起こったことを記録するための記憶装置」というインフォーマルな意味で「メモリ」と言いました。オートマトンにおいては、読んだ文字を次々忘れてしまうため、「今どの状態にいるか」が過去に対する唯一の手がかりです。「状態 q1 にいるということは、これまで読んだ文字列は aab ということはないはずだな。。。なぜなら、aab を読んだら状態 q2 に行くはずだからな。。。」という感じです。

テキストP61 統計的(機械学習)というのと、P68 オートマトンは余代数として抽象化 という点について、代数と統計との関連性についてよくわかりませんでした。(代数はきっちりと定義された 誤差なし(?) ものであるというイメージがあるため。)

確かに統計と代数はノリがだいぶ違うのですが、いろいろな関連性がありえます。非常におおざっぱに言うと、何かを記号列で表現した時点ですでに代数をやっているとも言えます。
余代数については、Bart Jacobs の教科書「Introduction to Coalgebra: Towards Mathematics of States and Observation」がおすすめです。草稿は著者のウェブページからダウンロードもできます。

オートマトンのMの包含の一番上の数字が0でなくて1の場合はどうでしょうか。(すなわち1が三連続すると非受理に戻る) 「L(M)⊆L(M´)」? また、このようなオートマトンは安定動作しますか?不規則振動のような動き?

右端の状態で 1 を読んだときに、行き先が複数ありえる、ということですよね。こうなると、講演では扱わなかった「非決定性オートマトン」になり、包含関係を確かめるのがだいぶ難しくなります。(具体的には: 材料3で「オートマトンの決定化」が必要になる。) しかし、非決定性オートマトンが悪いということは別になくて、実際の応用で使うのは非決定性オートマトンが多いです。

有限オートマトンで素数を生成するアルゴリズムを実装することができれば、包含関係を解くことによって素数の予想問題(ex.リーマン予想)が正しいか否かを解決することができるように思います。有限オートマトンに限らず、アルゴリズムをメタ的に表現する手法で数学の予想を解くような試みは成されているのでしょうか?それがメタ数学なのでしょうか?

おお、すばらしい! これをやろうとしてできたのがチューリング機械で、「なんでも解けるような万能な機械はないぞ」ということに関連するのがゲーデルの不完全性定理です。(注: ゲーデルの不完全性定理について語ることは可燃性が高いので、解像度の低い言い方になっています。)
ちなみに、有限オートマトンでは素数かどうかを判断することはできません。やっぱり有限性のくびきが効いてきます(講演でやったような論法で、不可能性が証明できます)。チューリング機械なら素数かどうか判断可能です。

空判定で、状態がSn+1=Sn(増えなくなる)状態になるのは、どのような状態でしょうか?状態は有限個ですが、入力回数は無限回数可能(つまり、L(M)のことですが・・・)だと思うのですが、受理状態と非受理状態のみ考えるということでしょうか?

始状態からはじめて、遷移(矢印)を辿っていくことで、到達可能な状態を数え上げていきます(手元の袋に入れていくイメージ)。新しい到達可能状態が見つからなくなったら(=袋に新しい状態が入らなくなったら)終わりなのですが、仮にこの操作に終わりがなかったら、見たことのない状態が次々見つかり続けることになりますよね。そうすると、そもそも状態が無限個あることになってしまいます。
数式で書いたほうがわかりやすいような。。。ちなみに、厳密に証明しようとすると、本当にむずかしいのは上で「新しい到達可能状態が見つからなくなったら終わり」と言っている部分です。

包含関係が3つの材料でなぜ解けるのか?いくつの材料であれば解けるのかをどうやって調べるか?

お見せした3つの材料で解けるのはご説明したとおりなのですが、他に解き方がないかというとそんなことはありません。たとえばよく知られているのは模倣関係を探す方法で、うまくいくとずっと速く包含関係の証拠を見つけてくれます。(トレードオフとしては、包含関係が成り立つのに証拠を見つけ損なうこともある)

P62 ソフトウェア品質保証は想定外の事には対応できないという結論でよろしいですか。

いやいやいや、「想定外のことには対応できない手法も少なくないが、対応できるようにがんばっていきます」というのが結論です。

問題に対して、証明できないと結論が出たとき、証明できるように問題を変更するためには、どのような考え方があるのでしょうか?

ぼんやりした答えになりますが、「本当にやりたいこと」「応用上必要なこと」に対して、いつの間にか、よりハードルの高い数学的問題を設定してしまっていることが往々にしてあります。そういうときは、手元の(途中までうまくいったがそこで止まった)証明と、本当にやりたいことを突き合わせて、設定した数学的問題を修正します。

ソースプログラムの内部に無限ループが存在しているかどうかを判定することは可能でしょうか。また、具体的にその場所を特定できるでしょうか。

おお! これはプログラムの停止問題というよく知られた問題で、典型的な決定不能問題(プログラムで解けない問題)です。解けないことの証明は対角線論法(自己言及+否定的ツイスト)で行うのですが、アイデアは「仮に停止問題を解くプログラム P があるとして、P に P 自身を解析させたらどうなるの?」というものです(ここに否定的ツイストを加える)。

理論計算機科学の方法を使って、法律の体系に矛盾がないか判別することはできないか。また、任意の法体系で裁定できる事象と、そうでない事象を調べることはできないか。

法律への応用は多数研究があって、たとえば NII では佐藤健先生が取り組んでいらっしゃいます。論理的に解析すると矛盾や曖昧さがどんどん出てきますが。。。

今後、社会の中で、「自動化」やAIで障害が発生した時(例:自動運転車の事故)
①アルゴリズムの不具合(いわゆるバグ)による想定外の事象発生
②データ(学習)の不十分さによる想定外の事象発生(アルゴリズムは正常)
のどちらか、判別できるのでしょうか。(デバッグ可能か)

これはまさに私達が取り組んでいる課題です。端的な答えは「おっしゃるような判別(すなわち問題の追跡)ができるようにシステムを作るべき」となります。問題の追跡が可能でありながら、性能を損なわず設計コストもあまり上がらないような、うまいシステム設計法を研究しているところです。個人的には、ニューラルネットワークなどの統計的機械学習ユニットを論理的レイヤーで包んであげることがカギだと思っています。

ニューラルネットワークを利用した技術の安全性評価について、今後も知りたいです。(もし情報発信をされているのであれば、どのようにしたら情報を取得できるかわかればうれしいです)

文部科学省の2020年度戦略目標の一つとして「信頼されるAI」というのが立ちました。これをもとに多数の取り組みが開始されるものと思います。「信頼されるAI 戦略目標」などと検索してみてください。私達のプロジェクトウェブページ http://group-mmm。org/eratommsd ももちろんご覧くださいね。

言語反転で要素数が有限→無限 になることはないのでしょうか?

要素数とおっしゃっているのはオートマトンの状態数のことだと理解しました。そうすると、無限になることはありません(正確に言うと、言語を反転させても、それに対応する有限オートマトンを構成できる)。これが「正規言語のクラスは言語の反転について閉じている」という性質です。実際、ご説明した手順を踏めば有限オートマトンができますよね。
「言語の反転について閉じている」という性質は特別なものです。たとえば、もう少し機能を加えてパワフルに(=表現能力を高く)したオートマトンの種類としてプッシュダウンオートマトンというものがありますが、プッシュダウンオートマトンの言語を反転させると、対応するプッシュダウンオートマトンが存在するとは限りません。この事実は「文脈自由言語のクラスは言語の反転について閉じていない」と表現されます。

AIでできる問題とできない問題は区別する論理はありますか?

うーん、チューリングマシンとちがって、「AI とはなにか」という定義はないので、なかなかむずかしいと思います。「2層のニューラルネットワークでできるかできないか」というふうに具体化すれば研究の対象になります(そしてよく研究されている)。が、統計的機械学習においては特に、「理論的に可能である」ことと「現実的な時間とデータ量で実現できる」ことの間には大きなギャップがあります。

流体などのように連続的なものには活用できるのか。

一義的には、オートマトン理論は連続量が現れた時点でアウトです(連続量 → とれる状態が無限通り → 有限性に立脚した議論が崩壊)。ですが時間と確率という特定の連続量に対しては、線形代数を使ってうまく有限の抽象化が可能であり、豊かなオートマトン理論があります。前者は timed automaton、後者は probabilistic model checking というのがキーワードです。
。。。というのが「オートマトン理論に流体を加える」という話ですが(そしてそれはおそらくむずかしい)、「流体の位相幾何的構造をオートマトンっぽい有限グラフで表現する」という話ならばあります(たとえば [Sakajo、 Sawamura & Yokoyama、 Fluid Dynamics Research、 2014])。

仏教の「空」等の基本概念を理論計算機科学で論じたり、証明したりできないか?大乗仏教完成者の龍樹等の教説は、きわめて論理的で数学的に証明できそうに見える。

論理学は数学・計算機科学・哲学の間にある領域ですが、哲学畑の論理学者であれば何かよい答えをお持ちなのかもしれません。。。

先生ご自身では理論一般論と応用のどちらがおもしろいですか。

ご質問ありがとうございます。もちろん、両方です。特に、応用に突っ込んでいってこそ一般論の発展がある、と思っています。応用数学の心意気、です。

shimin 2019-qa_3 page4353

注目コンテンツ / SPECIAL