9/28 マルレク「計算複雑性理論入門」　コンテンツ公開の詳細

【 9/28 マルレク「計算複雑性理論入門」概要 】

今回のセミナーは、前回8月のセミナーと基本的な議論は連続しています。それは、コンピュータとAI技術の次の未来を展望するうえで、人間の二つの基本的能力である「言語能力」と「数学的能力」の「統合」の課題が重要だという議論です。

そうした立場から、前回のセミナー「コンピュータと数学 -- TuringからVoevodskyまで」では、コンピュータにはそもそも「数学的能力」が備わっているのではという問題意識を述べてきました。

そこでは、コンピュータの持つ数学的能力の(再)発見の突破口となった「計算 ＝ 証明 = プログラミング」という認識の成立の場所である「型の理論」を取り上げ、実際にコンピュータによる証明の例を紹介しててきました。

今回のセミナー「計算複雑性理論入門 -- Turingマシンから量子コンピュータまで」では、こうした論点をさらに深める上で、計算科学の代表的な数学理論である「計算複雑性理論」に注目しようと思います。


【 9/28 マルレク「計算複雑性理論入門」講演ビデオと講演資料のURLです 】

セミナーは3つのパートに分かれています。個別にも全体を通してもアクセスできます。

--------------------------
全体を通して見る
--------------------------

　●  「計算複雑性理論入門」セミナーの講演ビデオ全体の再生リストのURLです。
　　　全体を通して再生することができます。
https://www.youtube.com/playlist?list=PLQIrJ0f9gMcOpIJC2zXYFkMmOORiA15C7

　●  講演資料全体を一つのpdfファイルにまとめたものはこちらです。

　　　「計算複雑性理論入門 」講演資料
https://drive.google.com/file/d/1OwmBSa0kfa1X4jpELlX0p2_6JfYYlNLG/view?usp=sharing

--------------------------
　パートごとに見る
--------------------------

　●  Part 1 計算可能性理論と計算複雑性理論

　　　講演ビデオURL :
https://youtu.be/iLTZWNBojho?list=PLQIrJ0f9gMcOpIJC2zXYFkMmOORiA15C7

　　　講演資料 pdf :
https://drive.google.com/file/d/1OeSJFVa7-Iay1d8oY6yZ9KINE9536SAZ/view?usp=sharing

　●  　Part 2 計算複雑性の基本的階層

　　　講演ビデオURL :
https://youtu.be/_PUy8iOi8yA?list=PLQIrJ0f9gMcOpIJC2zXYFkMmOORiA15C7

　　　講演資料 pdf :
https://drive.google.com/file/d/1Om_mHw5jAGfz6LCheyQk7peibLUCQZw_/view?usp=sharing

　●  Part 3 コンピュータによる数学的証明の実例

　　　講演ビデオURL :
https://youtu.be/0ketdcTmkro?list=PLQIrJ0f9gMcOpIJC2zXYFkMmOORiA15C7

　　　講演資料 pdf :
https://drive.google.com/file/d/1P9JBumpAdODgJZ4_Ol1lq3s7MT_DmRFU/view?usp=sharing

-----------------------------

今回のセミナーのまとめページはこちらです。

「計算複雑性理論入門 」
https://www.marulabo.net/docs/computer-math2/

セミナーに向けたショートムービーの再生リストはこちらです。ご利用ください。
https://www.youtube.com/playlist?list=PLQIrJ0f9gMcMT7vxO1dVD00bhzEVLFsBB

---------------------------

コメント

コメントを投稿

このブログの人気の投稿

初めにことばありき

旧約の「創世記」の「光よあれ」は、ビッグバンを思わせて、物理学者はちょっと萌えるかもしれないのだが、新約の「ヨハネによる福音書」には、言語学者が喜びそうなフレーズがある。 「初めに言があった。言は神と共にあった。言は神であった。」 僕が知っていたのは、「はじめにことばありき」という訳だったのだが。この口語訳での「言」は、英訳だとこうなっている。 "In the beginning was the Word, and the Word was with God, and the Word was God." 「言」= "Word" である。はじめにあったのは、Wordであって、Language ではない。だから、新しい口語訳では、普段、あまり馴染みない「言」という訳語を使ったのかも。「初めに語があった」では、なんかしまらないんだろうな。（僕は、「はじめにことばありき」というフレーズの方が好きだ。） ちなみに、「ヨハネによる福音書」は、英語では、"Gospel of John" という。「ジョンのゴスペル」である。でも、そう日本語に訳してしまうと、ジョン・レノンがバラードではなく、ゴスペルを歌っているようで、まずいんだろうな。 「ことば」・「言」・"Word" と訳されている、元々の言葉を調べてみると面白い。 キリスト教のオーソドックスな原典であるラテン語訳聖書では、この部分は、こうなる。 "In principio erat Verbum, et Verbum erat apud Deum, et Deus erat Verbum" 「イン・プリンキピオー・エラト・ウェルブム」 英訳 Word のラテン語の原語は、Verbum である。この単語、英語に直訳すれば、Verbである。「初めに、動詞があった。」　言語学の「従属性文法 (Dependency Grammar) 」理論の人たち、喜びそう。 もっとも、英語のVerbは、元々は、動詞というより広く言葉全体をさしてたらしい。そのことは、「ノンバーバル・コミュニケーション (Non-Verbal Communication) 」というのが、動詞を使わないコミュニケーション...
続きを読む

宇宙の終わりと黒色矮星

イメージ
【宇宙の終わりと黒色矮星】 図のようなストーリーで、「宇宙の終わりとエントロピー」という投稿を準備していたのだが、いろいろ雑念が湧いて気がすすまなくなる。その理由は別稿で。 この図は、「閉じられた部屋でのガスの拡散」というわかりやすいモデルで理解されるエントロピーの増大の法則が、あるフェーズから、宇宙規模でみれば、「全ての物質のブラックホールへの吸収・収斂」として現れると言うことを主張している。最初、ペンローズのこの話を読んだときには、目からウロコだった。 このストーリーにはもっと先がある。最近のシミュレーションでは、指数関数的に膨張する宇宙では、巨大なブラックホールに捕捉されるのは、宇宙全体の物質の10%程度だという。恒星起源のブラックホールは 10^67 年で、銀河系中心の巨大ブラックホールも 10^99年で、ホーキング放射で「蒸発」し姿を消す。 ブラックホールに捕捉されなかった宇宙の残りの90%の物質は、元それが属した銀河系から孤立したまま星の一生の進化を続ける。太陽の1.2倍程度の質量を持つ星は「白色矮星」になるのだが、「白色矮星」は 10^17年で「黒色矮星」に変わる。 「黒色矮星」は、現代の「宇宙の終末論」では、もっとも注目されている天体なのだが、それはまだ観測されていないと言う。というのも、この天体は光を出さないからだ。「黒色矮星」の中心は、最も安定な原子である鉄の「結晶」でできていて、温度は絶対零度近くに冷却されている。 「黒色矮星」は、とても長生きする天体である。陽子崩壊がおきるなら、黒色矮星の寿命は 10^32年程度だが、もし陽子が安定しているとすれば、太陽の 1.24倍程度の質量を持つ「黒色矮星」は、10^1600年後に突然崩壊して超新星爆発を起こす。もっと軽い、太陽の1.16倍程度の質量を持つ「黒色矮星」は、10^32000 年後（！）に超新星爆発を起こす。 このシナリオによれば、宇宙は、とてつもなく長い長い退屈な時間をかけて、その死を迎える。「黒色矮星」の超新星爆発は、宇宙の死を飾る最後の打ち上げ花火である。その後には、宇宙には何も起こらない。 この記事は、ジョン・バエズの "Black Dwarf Supernovae" を基にしたものだ。https://johncarlosbaez.wordpress.com/202...
続きを読む

Google翻訳での日本語の点数の低さについて

イメージ
Google翻訳は、なかなかスゴイのだが、他の欧米系の言語での翻訳と比べると、日本語の翻訳精度は、かなり低い。 この表は、Google翻訳の「Zero-Shot論文」の、ある意味「目玉」の結果の一つである。 機械翻訳のシステムを、ドイツ語 -> 英語、フランス語 -> 英語 というように、一対一の言語の組み合わせで別々のシステムで訓練させるより、{ ドイツ語、フランス語} -> 英語 のように、一つのシステムで同時に複数の言語（この場合は二つの言語）の一つの言語（この場合は、英語）への翻訳を訓練した方が翻訳精度が上がるという、驚くべきものである。 人間で言えば、日本語の英語への翻訳をもっとうまくやりたいなら、韓国語から英語への翻訳も、同時に学習する方がいいということ。 このメリットを説明する可能性のある仮説の1つは、モデルがより多くの英語データをターゲット側に持ち、ソース言語が同じ言語ファミリに属していること。それで、モデルは有用な一般化を学んでいると思われる。 こうした 発見は、とても興味深いものだが、ここでは、別のことに注目しよう。 ここでの翻訳精度の改善は、BLEUのスコアで、+0.05〜+0.79の改善である。（表の赤い枠の部分。） ただ、日本語 -> 英語の翻訳精度は高いスコアで 23.87で、フランス -> 英語の 36.77と比べるとずいぶん低い。この表の中では、最低だ。実験で最高得点をたたき出している ポルトガル語 -> 英語の 45.19と比べると、半分程度だ。 実は、このポルトガル語の高得点も、僕には不思議に見える。WMTのコーパスでは、英語・フランス語のパラレル・データが3,600万ペアで、英語・ドイツ語のペア500万と比べても圧倒的に多い。ポルトガル語の高得点は、Google内部のコーパスを使ったものだが、アメリカなら、英語・スペイン語のデータは多いと予想できるのだが、英語・ポルトガル語のデータが、それ以上に多いとは思えない。でも、スペイン語 -> 英語より、ポルトガル語 -> 英語の方が、ずっと成績がいいのだ。 きっとGoogle翻訳は、英訳に関して言えば、日本語とは相性が悪く、ポルトガル語とはとても相性がいいのだ。なぜか？　僕にはわからない。 ...
続きを読む