<   2016年 03月 ( 8 )   > この月の画像一覧

自然数と全単射が作れる集合

無限集合のうちで自然数と全単射をつくることができる集合の特徴はどのようなものだろうか。偶数の集合は自然数と全単射をつくることができる。2,4,6,.. と偶数を並べていって2nまで並べたとすると2n 以下の偶数の個数は有限であるそれに自然数を対応付けると2n以下の偶数とn以下の自然数の全単射ができる。n は任意なのでどんなに大きな n についても偶数と自然数の全単射はできる。n が無限大の時のことを考えるのは無意味なので、これで、すべての偶数と自然数との全単射が存在すると考えても問題ない。

自然数のペア (n, m) の集合も自然数と全単射を作ることができる。まず (1,1) を先頭に並べ 1 と対応させる。次に (2, m) または (n, 2) のペア (2,1), (2,2) ,(1,2) をとり (1,1) のうしろに並べて自然数の 2, 3, 4, と対応させる。さらに (3, m) または (n, 3) のペア (3,1), (3,2), (3,3), (2,3), (1,3) を今までの要素の列の後ろにならべこれを 5,6,7,8,9 と対応させる。これを繰り返していけばペア (n, m) の要素をもれなく自然数に対応させることができる。

自然数のトリプル (k1, k2, k3) やn-組 (k1, k2, ... , kn) についても上のペアと同じような操作で自然数との全単射をつくることができる。

しかし、自然数の無限個の組 (k1, k2, ... ) ではこの方法は使えない。(1,1,.. ) の隣の点を見つけることができないからだ。隣の点さえ見つかれば上のような方法で自然数と対応づけることができるかもしれないが、無限個の組ではこの組を無限次元平面の一点としてあらわすことができない。

自然数の無限個の組は自然数との全単射を作ることができないのだ。

自然数と全単射を作れる無限集合の要素は、有限次元平面の離散点として表現できるが、無限次元の離散点はそれを並べるためのアルゴリズムが存在しないようだ。

[PR]
by tnomura9 | 2016-03-31 18:33 | 考えるということ | Comments(0)

実数の1点とは何か

自然数がその部分集合である偶数と全単射を作ることができるとはどういうことだろうか。それは任意の自然数にはただ一つの偶数が対応し、任意の偶数にはただ一つの自然数が対応するということである。これは自然数の任意の要素 n に対し、任意の偶数が 2n であらわすことができるので、自然数と偶数の間の全単射が成立することがわかる。

この方法で大切なのは任意の自然数を選び出した時、その数は確定的な数であるということだ。すなわち n はそれ以外の全ての自然数と異なっていると言うことができる。この事情は偶数の場合も同じである。自然数の集合と偶数の集合との全単射は、自然数の集合の任意の確定した数から、偶数の集合の確定した数への写像だ。自然数も偶数も無限の要素を持つが、自然数の無限大から偶数の要素への写像は考えることができない。

それでは実数と自然数との全単射はどうして不可能なのだろうか。そこで任意の0以上1未満の実数の配列に自然数を対応できたと仮定する。ここで、実数が順序集合であることから、これを整列することができる。当然実数の0にはある自然数が対応している。実数がすべて自然数と対応付けられているとすれば0に対応する自然数の隣の自然数がなければならない。それでは0の隣の実数に対応する自然数を求めることができるだろうか。

整列した実数の配列は全ての実数からなっている。したがって、実数の連続性から、任意の相異なる実数の間には必ずある実数が存在するはずだ。そうであれば、0の隣の実数を求めることはできないことがわかる。なぜなら、0の隣の数 a があったとすると、その間にb という実数が存在しなくてはならない。それは0の隣の数が a であるという仮定に反する。0の隣の実数を求めることができなければ、それに対応する対応する自然数を特定することは不可能になる。このため、実数と自然数の全単射を見つけることはできない。

つまり、自然数と全単射を作るための実数の一点というものは存在しないのだ。一点が存在しなければ全単射を定義することは不可能なのである。

しかし実数が一点でないとすると、実数から実数への関数も不可能になる。それは直感にも反するし、実数関数が使えなければ不便だ。

これは実数は一点ではないが、実数に最も近い有限小数に無限小 x を加えたものが実数の一点の存在範囲であると考えることで解決できる。有限小数と有限小数の関数は定義することができるから、実数の一点からの写像の値は、有限小数に不確定要素 y を加えたものがその値となる。また、有限小数の小数点下の桁数が増えるほど、誤差である無限小の範囲も減少する。要するにコンピュータのプログラムがやっている方法だ。

実数の一点とは、常に不確定要素である誤差を含んでいるため、確定することができず自然数との全単射ができないのだ。

追記

上の議論は実数の稠密性によって実数の隣の数がないことを利用して、自然数との全単射がないことを証明しようとしたが、残念ながらこれは誤りだ。なぜなら実数と同じように稠密な有理数は自然数と全単射を作ることができるからだ。

自然数と偶数は値が小さい順に端から並べていけば互いの全単射を作ることができるが、有理数は、稠密性のために小さい順に端から並べていくということはできない。有理数の場合も実数と同じようにすぐ隣の数というものがないからだ。

それにもかかわらず有理数は自然数との全単射を作ることができる。それは有理数が既約の分母と分子という自然数のペアでその一点を表すことができるからだ。自然数のペアは二次元平面の点として表現できる。それは (0,0) を起点として順に網羅的に点をたどっていくアルゴリズムを見つけることができる。自然数との全単射はそのアルゴリズムが保証する。

このように、有理数の場合は稠密性のために小さい順に並べるというやり方では網羅的に列挙することができないが、有理数を自然数のペアとして表現することで、網羅的に並べるアルゴリズムが得られる。

しかし、実数の場合は、稠密という性質に加えて完備性がある。実数と自然数との全単射が作れない理由はこの完備性の性質によるものだろう。完備性によって、実数の点は自然数の無限次元のタプルとして表すことができるが、実数を表す自然数の無限次元のタプルでは、実数の一点を誤差なく確定することができない。無限の個数の自然数で特定される実数はいつまでたってもある誤差を持った値であり、一点として確定できないからだ。実数を自然数のタプルで表現すると、その表現はいつまでたっても複数の点を含む可能性をなくすことができない。つまり実数と自然数との対応は、いつまでたっても多対1の対応しか作ることができない。

このように実数の完備性(連続性)によって、実数と自然数の対応は多対1の関係しか作ることができないため、全単射を作ることができないのだ。有理数と自然数の対応は1対1であるが、実数と自然数の対応は、無限対1の対応になってしまう。それは実数の一点というものが常に無限の点を抱えていることを示している。

[PR]
by tnomura9 | 2016-03-29 08:05 | 考えるということ | Comments(0)

単語の力

意味ネットワークは色々な方式があるようだが、意味をネットワークとして扱うという意味では大きな違いはない。しかし、これはコンピュータが理解出来る形で意味を表現するという意図のため、機械語のようなものだ。要素的すぎて、人間の思考活動にそのまま転用するには粒度が小さすぎる。

意味ネットワークのアイディアを人間の思考活動に利用するための適切な粒度は、おそらく単語だろう。文章の中の単語に注目して、その単語から連想される背景知識が自分の中にどれくらい多く記憶されているかどうかを反省してみるのだ。

この操作のツールとしては、マインドマップを利用するのが便利だろう。マップの中心に単語を書き、それに関連して連想できる言葉や図形や文章をできるだけ書き出していくのだ。その数が少ない時はウェブや書籍を調べて追加していく。

この単語に関連する知識の量が多ければ多いほど豊富な知識を自分が所持しており、また、柔軟にその単語を活用できる力があることを知ることができる。この操作は実際には頭の中で瞬時に行われないと、文章を読み進めていくことができないのだが、文章が理解できないと感じた時には、自分の単語の力を明示的に調べることによってどこに問題があるのかを知ることができる。

自分が持っている知識の深さと柔軟性は、自分の持つ単語の力によって決まってくるのだ。

[PR]
by tnomura9 | 2016-03-28 01:29 | 考えるということ | Comments(0)

意味ネットワーク

セマンティック・ウェブ関連の文書を読んでみたが、RDF、OWL、オントロジー、記述論理などのどの用語の説明を読んでも全く意味が掴めなかった。そこで、ウェブの記事を手当たり次第に読んでいるうちに、これらの技術が、ウェブの文書の意味情報を拾い上げようとする試みだということではないかという印象を持った。

HTMLのハイパーリンクをたどると別のHTML文書を検索することができるが、これは単に一つの文字情報から次の文字情報へのリンクがあることを示しているにすぎない。HTML文書の意味やリンクの意味は人間が文書を読んで理解しないと分からない。セマンティック・ウェブの試みはこの文書の意味の解釈をコンピュータにやらせようという試みのようだ。意味の理解を機械にさせることができれば、翻訳や、文書の要約や、データマイニングなどを自動化できる。

しかし、コンピュータに文書の意味を理解させようとしても、意味をコンピュータに理解させるためのデータタイプをどうするかを決めないといけない。コンピュータはデータを処理できるだけなので、意味は処理されるデータに表される。コンピュータが意味を理解するわけではないが、コンピュータが意味を表すデータを処理したアウトプットを人間が見た時に、コンピュータが意味を理解しているように見えれば実用上は十分だからだ。

意味を表すデータ型は、人工知能の研究の中から発展してきたらしい。主なものに、フレームと意味ネットワーク (semantic network) があるようだ。このうちセマンティック・ウェブに採用されているのは意味ネットワークだと思われる。

意味ネットワークとは一言でいうと、概念をノードとし、一つの概念と別の概念との間を結ぶエッジからなるグラフだ。概念は concept, エッジは property という述語で表されるようだ。

この意味ネットワークのグラフは全体で一つの知識を表している。例えば、この文書の単語をノードとするネットワークを作ることができるが、それだけでは、意味のネットワークにはならない。この文書に書かれていない基礎知識や、日本語の意味のネットワークが加わった膨大なネットワークがつまり、この文書の意味になる。

意味ネットワークのグラフのサイズはかなり大きなものになるが、文書の意味をこのようなグラフとして捉えることによって、機械がこれを処理することができるようになる。機械が処理できるということは、プログラムを組むことによって、意味による検索や、自動翻訳、自動要約ができるようになるということだ。

次に問題となるのは、この意味ネットワークのグラフをどのように記述するかということだ。図解でグラフィカルに表示するのは人間にとっては分かりやすいが、機械は苦手だ。また、グラフィカルな表示もノードの数が膨大になると人間にも理解不能になる。

意味ネットワークのグラフを記述する一番わかりやすい方法は、ノードとエッジとノードの三つ組 (triple) で要素的なグラフを記述することだ。これらの要素的なグラフを表す三つ組を多数集めることによって、全体のグラフを表すことができる。

このような三つ組の要素は、<概念, 属性, 概念> という構成になっている。これは文の主語、述語、目的語に対応する。例えば、犬は動物に属するという文の意味は <dog, is-a, animal> という三つ組で表すことができる。

属性は is-a のような集合の包含関係以外にもいろいろなものが考えられる。例えば「犬には足がある」という場合、<dog, has, leg> のような三つ組が考えられるが、別に dog が leg に包含されるわけではない。

このように、概念とは何かとか属性にはどのようなものがあるかなどの細かい議論は文書の著者によって様々なので、独学では混乱してしまう。概念を犬や動物のような集合に限ったほうがいいのか、「走る」のような集合にできないものをノードにすべきか、エッジにすべきかなど研究者によって様々な感じがした。

むしろ、概念に対して集合という枠を嵌めないほうがいいのかもしれない。とはいえ、知識ネットワークに論理を適用する際には、集合を表す概念の重要性は明らかだ。そうであれば、概念や属性が何かという議論には深入りせず、意味ネットワークとは概念というノードと属性というエッジからなるグラフであって、その実体的な意味は、意味を扱うプログラムによって決められると考えたほうがいいのかもしれない。

概念や属性の実体が何であれ、意味ネットワークをノードとエッジからなるグラフと捉えることによって、データの構造が簡明になって、それを操作するプログラムの作り方がわかりやすくなる。

例えば、親子関係のデータベースを Haskell のタプルで作ってみる。

Prelude> let pac = [("John", "son", "Mike"), ("John", "son", "Kent"), ("Mary", "daughter", "Jill")]


このデータベースから John の息子だけを取り出すには、次のようにすればいい。


Prelude> let clild (_,_,x) = x

Prelude> let isChild (x, y, _) = if x == "John" && y == "son" then True else False

Prelude> map child $ filter isChild pac

["Mike","Kent"]


あまりいい例ではないかもしれないが、意味ネットワークを三つ組 (triple) の集合で表すことによって、意味の情報処理をコンピュータにやらせることができることがわかる。


Haskell の例では意味ネットワークの三つ組をタプルで表したが、セマンチィック・ウェブの RDF の場合は xml で記述している。全世界のセマンティック・ウェブからのデータを取り出せるように標準化してあるため、その記述は複雑になるが、意味ネットワークを3つ組で表現するという基本的なアイディアをつかんでいれば、迷路に入り込むことはない。

[PR]
by tnomura9 | 2016-03-24 02:03 | 考えるということ | Comments(0)

メリッサ国吉

ブラジル出身の天才少女歌手。今は12歳になって日本で修行中。

歌いだしでぶっ飛んだ。

瀬戸の花嫁をうたうブラジル人女の子

今、ブラジルが面白い。

ステージの合間の振る舞いが性格の可愛さを感じさせる。

作曲家、鈴木淳氏に師事しているらしい。幸運も味方につけていそう。

鈴木氏のブログの特集記事が面白かった。『僕の愛した歌たち

演歌に対するイメージが変わってしまった。

正式なデビューはまだだそうだが、イベントなどでは歌っている。

お台場 2015 メリッサ クニヨシ (Melissa Kuniyosi) 7曲



[PR]
by tnomura9 | 2016-03-09 19:53 | ボーカロイド | Comments(0)

山下ヤスミン

ブラジルの天才少女歌手、山下ヤスミン


素晴らしい。10 歳の奇跡。




今年 (2016年) は12歳になった。背丈も伸びて大人っぽくなっている。医学部を目指して頑張っているらしい。両親がしっかりサポートしているのだろう。しかし、大人に成長した時の歌も聴きたい気がする。


追記

彼女の歌は明らかに指導者の力量を反映している。演歌が日本で瀕死の状態にあるのは原因があるだろう。日本の風土と歌に普遍性がないからとは言えないのではないか。ブラジル演歌という新しい風をもっと研究すべきだろう。

追記その2

7曲全曲アルバムで聴きたい時



[PR]
by tnomura9 | 2016-03-06 08:08 | ボーカロイド | Comments(0)

白と黒のとびら

川添愛著『白と黒のとびら』を読了した。オートマトン、正規言語、文脈自由言語、チョムスキー階層、停止性問題が見事にファンタジーになっていた。ゲド戦記を彷彿とさせるちゃんとしたファンタジーなので(ゲド戦記や指輪物語ほどのダークサイドはないが)、あまり予備知識がなくても楽しめる。

しかも、オートマトン理論を俯瞰するのには便利な本だ。理論の体系の意図が分かるような気がした。理論を生き生きとしたイメージで理解できるのは楽しい。数学者の頭の中もファンタジーではないかもしれないが理論についての生き生きとしたイメージでできているのではないかと思わせられた。

この本の設定で面白いと思ったのは、文字列の文字が黒丸と白丸だけだったことだ。つまり文字種が 0 と 1 だけなので、文字列はビット文字列になる。文字種がいくつあっても結局はビット列に変換できるので、純粋にオートマトンの性質を見るのにはビット列で考えるのが便利だ。

また、有限オートマトンとプッシュダウンオートマトンの違いが物語のモデルでよく分かった。このモデルだと anbn という文字列は文脈自由文法でないと受容しないことがよくわかる。さらに、形式文法の非終端記号を引換券に例えてあったのが、イメージが作りやすくて面白かった。その他、後半の反復補題や手作業の構文解析にも意表をつかれた。

とにかくオートマトンの用語をまったく使わなくてもイメージだけでその性質を記述できている。

とは言え、この本は本流のファンタジー小説に仕上がっている。付録の解説のオートマトンの説明を読んでも魔法書を読んでいるような気分になっていたほどだ。

[PR]
by tnomura9 | 2016-03-03 14:01 | 考えるということ | Comments(0)

「正規表現」は誤訳?

正規表現は regular expression の訳だ。Wikipedia には、
正規表現とは文字列の集合を一つの文字で表現する方法のひとつである。... まれに正規式と表現されることもある。
とある。たとえば、/a*b/ という正規表現は b, ab, aab, aaab, ... という0回以上の a の繰り返しのあとに b がつくすべての文字列を表している。/a*b/ は特定の文字列ではなく、文字列の集合を表している。/a/ の場合もこれがあらわすのは {a} という文字列1個だけの集合なのだ。/ab/ のように ab と文字を並べている場合もこれは集合 {a} の要素と集合 {b} の要素のすべての連結からなる集合 {ab} を表している。この正規表現に対応する文字列の集合が正規言語だ。

これはまた、/ab/ の ab は {a} . {b} という正規言語どうしが連接演算 . で結合されたものと見ることができる。つまり、正規表現 /ab/ は正規言語 /a/ と正規言語 /b/ の連接演算の式であるとみることができる。この式 /ab/ があらわすものもやはり正規言語 {ab} だから、正規言語の集合は連接演算について閉じている。

正規表現に現れる正規言語の演算はこの連接演算以外に、選択演算 | と クリーネ閉包を作る(クリーネ)スター演算子 * がある。クリーネ閉包とは、ある演算の繰り返しが生成する文字列の集合である。例えば文字列の集合 {"ab", "c"} のクリーネ閉包は次のようになる。

{"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}

これらの連接、選択、クリーネ閉包の演算はすべて正規言語の集合について閉じているので、これは正規言語の集合の代数を構成する。

いずれにせよ、/[+-][0-9][0-9]*/ という正規表現は、こういう書き方をしてよければ、{+, -} . {0, 1, 2, .., 9} . {0, 1, 2, .., 9}* という正規言語の演算の「式」になっている。この意味では regular expression の訳としては「正規表現」よりもまれにしか使われない「正規式」のほうが適切であることが分かる。expression は「表現」ではなくて「式」の意味で使われている。

regular expression の「正規表現」という訳は、「正規式」という訳に比べて正規表現の意味を的確に表していないような気がする。しかし、文字列のパターンを表すという意味での「正規式」の使い方が普及したので「正規表現」の訳語のほうが圧倒的に使われているのだろう。

[PR]
by tnomura9 | 2016-03-01 18:15 | JavaScript | Comments(0)