日本語wikipediaをprologの二分木で処理するパフォーマンス

現在、日本語wikipediaの50%を二分木化したが、そのデータを使って、およそのパフォーマンスがわかってきた。この段階でのファイルサイズは、3.68Gバイト。つまり、もし全てのwikipedia本文を二分木化すると7Gバイトになるということだ。

これをswi-prologで読み込ませると(ルールファイルも読み込ませたが、こちらはサイズはとても小さい)、読み込みに約30分かかる。これは、前にも予想した通りだ。そうすると、swi-prologの実行プログラムのメモリ占有量が15Gバイトくらいになる。これは確かに大きい。私のMac Proは64ギガ積んでいるので、それから見ると余裕がまだあるのだが、大きいことは間違いない。

それで、例えば、「ロボット」という語を「は」という助詞付きで検索させると、次のような感じの結果を303行出力する。途中省略している。

1 ?- left(ロボット,は).
wiki_1_line_3385_2: ロボットは/いわゆる脳を持た関わらないにもずまるで/生きているかのように行動する//
wiki_1_line_28713_0: ロボットはそれまでのリアルロボットアニメのデザインとは一線を画した/斬新な/ものであった/
wiki_2_line_62217_1: ロボットはボートに4体の演奏人形が乗った/もので宮廷のパーティで池に浮かべて/音楽を演奏したと言われている/
4の演奏人形が乗った/もので宮廷のパーティで池に浮かべて/音楽を演奏したと言われている/
wiki_3_line_31429_2: ロボットは胸部から放つ/ビームのシグナルフラッシュ//
wiki_3_line_44126_0: ロボットは独自に/考案した/ものであると説明していた/
wiki_3_line_69544_0: ロボットは鉄神/てつじんと呼ばれサイズの大きい/順に/G~Aクラスの等級が付けられている/
G~Aの等級が付けられている/
・・・・・・
・・・・・・
・・・・・・
・・・・・・
wiki_508_line_38121_0: ロボットは補高部を取り除いた/構成となっている/
wiki_510_line_87051_1: ロボットはアッセイプレートを移動させたりサンプルおよび試薬を添加/混合/インキュベーションをしたりして最終的に検出のための場所に動かす/ことをする//
wiki_517_line_78404_1: ロボットはスーパー戦隊シリーズとしてはパワーレンジャーも含めても初の試みとなる//
wiki_526_line_43826_0: ロボットは2体/いて/青が太郎/赤が花子という/名前がつけられている/
2/いて/青が太郎/赤が花子という/名前がつけられている/
wiki_532_line_38273_2: ロボットは据え置き型が多かったがFetchは障害物などを避けながら自律的に移動できる/特徴がある//
wiki_532_line_38273_4: ロボットは長さが約60cm/7自由度を持ち/6kgまでの商品をピックアップ/可能//
7自由を持ち/6kgまでの商品をピックアップ/可能//
wiki_539_line_25554_0: ロボットは人間の腕に似た/働きをする/メカニカルアームの一種であり通常はプログラミング可能である//
wiki_539_line_25556_1: ロボットは溶接や組み立て中の部品の回転や設置などのいろいろな/タスクを行う//
wiki_539_line_25567_0: ロボットは使われてきた/

この303行を出力するのは約1分で、1秒あたり5行出力していることになり、検索は、超高速だ。

読み込んだ日本語wikipediaの二分木をswi-prologのqsave_programで保存する。保存は、数分しか狩らなかったと思う。ここだけは計っていない。何しろ、短時間で保存できたのだ。保存した結果のバイナリファイルは、2.5Gバイトだった。

これは、実行形式になっているので、そのまま(swi-prologを開始することなく)実行できる。コマンドを打って、prologのプロンプトが出るまで、40秒しかかからなかった!!超早い。巨大なデータも、一旦、バイナリ形式(swi-prologの内部表現形式)に変換して保存すると、超高速で実行可能な状況になるのだ。

十分実用範囲だ。

原点を確認する

春休みに入って時間も十分あったので、色々回り道をしてしまった。講義で、雑談に入ったら元に戻らないということがよくあるが、それと同じようなことが起きそうだった。

それで、改めて、何をやろうとしていたのかを確認しようと思った。

まず、12月の記事「短文の要約のアイデア」である。この記事の要点を再掲すると次のようになる。

「私が目標とするところからして、今、芸ロボットの到達点は50%くらいだと思っている。もし、短文要約が大きな問題なく、人と同じくらいのレベルでできるようになれば、この到達点は70%くらいまでいくだろう。・・・・ではどうすれば良いのか。一つ頭に浮かんでいるのが、要約対象が含む語の主要なものが含まれている、より短い文章の用例を探すことだ。ただ、全く同じ語については、あるかもしれないが、探すのが大変すぎる。・・・・そこで、言葉をグループ化する。例えば、りんごとバナナは、果物というグループに属するので、「デザートには〇〇が出た」という文章の〇〇には、等しく使える、置き換えられる。・・・・適用可能な言葉は、ある種の階層性を持っているのである。・・・・このグループ化、階層性を表現するために、類語辞典を使うことができる。類語辞典のコード番号を用いて、日本語ウィキペディアの全文章を用例化する。」

短文要約については、役に立ちそうな研究が極端に少なく、複数文章のよう役とは違って自然言語処理の高度な実践が必要になる。

そして次に、1月の記事「prologと自然言語解析」である。要点は次のようなものである。

「wikipediaのデータも、すべて、「論理的な言い換え」、「極端に複雑なトートロジー」である。これを表現するのにふさわしい言語は、論理型の言語だと思った。そして、prologに至った。・・・・wikipediaの 本文データのほとんどを、prologの宣言とルールに変換できないかというのが、今、考えていることの中心点である。」

この二つは似ているが、道は異なっている。第一のものは、単文要約という具体的な目的に沿って、手順も、用例を捉え、それを類語によって一般的にフォーム化するというところまで、具体的になっている。一方、第二の道は、知識をどう表現するかを課題にしている。コンセプトを語るのが目的になっている。

今、wikipediaデータがprologの宣言文となっている段階なので、それはある意味、どちらに向かうこともできるベースを作っているとも言える。

どちらにしても、prologに変換されたwikipediaのデータは膨大で、おそらく、全て完成して、swiprologに組み込めたとしても、組み込み自体に1時間かかるというものになるだろう。そして、クエリにもある程度時間がかかることが考えられ、その状況でどう実用化させるのかは不透明だ。

リストの中身を構造に関わらず順に出力するprolog

前の記事でごとカテゴリの再帰的構造を持ったリストから、語だけのリストを取り出すことを書いた。その取り出したリストも、構造化されているので、それらをベタに全て出力するprologを記述しようとした。

慣れないので、色々、試行錯誤したが結局次のような簡単な述語になった。

printlist(L) :- atom(L),write(L).
printlist(L) :- [H|[T]] = L,printlist(H),printlist(T),!.

最初のclauseで、それが単項だったらただ印刷するを定義しておいて。リストだった場合には、頭と尻尾を、自身を呼び出すだけのものである。

これで大体以下のような結果になる。

1 ?- [user].
|: printlist(L) :- atom(L),write(L).
|: printlist(L) :- [H|[T]] = L,printlist(H),printlist(T),!.
|: ^D
% user://1 compiled 0.00 sec, 2 clauses
true.

2 ?- printlist([a,[b,c]]).
abc
true.

3 ?- printlist([[a,b],c]).
abc
true.

4 ?- printlist([[a,b],[c,d]]).
abcd
true.

5 ?-  printlist([a,b]).
ab
true.

これだけの範囲では、予定通りの結果が出せている。

日本語wikipedia全本文の20%をprologの宣言文にした

本当は、日本語wikipedia全本文をprolog化するつもりで、終日macproを98%を超えるCPU使用率で動かしたのだが、途中で、なぜかjuman, knpサーバーとの接続に失敗したかとか言って、544ファイル中101ファイルを処理したところで止まってしまった。

20%くらいの達成率なのだが2晩かけた(笑)。70スレッドを立ち上げた。100スレッドでもいいかと思ったのだが、そうすると、macproが他に使えなくなってしまうので、少し控えた。

出力されたファイルは、14Gバイトあった。これをswi-prologで読み込んだら、なんと、12分30秒かかった。何よりも、swi-prologがそれだけのプログラムをくわえこむことができることに驚きだ。元のファイルは、テキストファイルなのだが、それをなんらかの内部形式のバイナリデータに書き換えているのだろう。swi-prologのメモリ占有は、5.4Gで済んでいる。MacProは、メモリを64G積んでいるので、余裕はあるのだが。

宣言文の行数は、3,291,151行である。この330万行に、prologの宣言文としてのエラーは一つもなかった。これも驚きである。全部を問題なく、swi-prologに組み込むことができたのである。

swi-prologには、全てを二分木として組み込んでいる。

語とカテゴリのリストから、語だけ取り出すprologのルール

前の記事で、語とカテゴリのリストのことを書いたが、このリストから語だけを全て取り出すprologのルールをほぼ1日かけて作成した。単純なはずなのだが、なかなかうまくいかなかった。また、prologというものに、完全に馴染んでいないからだと思う。普通のc, java, pythonなどと、プログラムの考え方が、全く異なっているのだから。

ルールは、次のようになる。 %で、始まる行はコメントである。

%% headがアトムの場合、tailから取り出したものと結合する
%% 特殊な二分木なので、tailに複雑に構造化されたリストはあり得ない
%% atomか[a,b]の形のものしか、tailの要素にはならないのだ
getlist([H|[T]],[H,H1]) :- atom(H),[H1|_] = T,!.
%% headがatomならば、それを取り出す
getlist([H|[_]],H) :- atom(H),!.
%% tailがatomの場合:その場合でも、headからは、必ず1個以上のatomが該当する
getlist([H|[T]],[Z,T]) :- atom(T),getlist(H,Z),!.
%% 残されたのは、headもtailもリストの場合
getlist([H|[T]],[X1, X2]) :- getlist(H,X1),getlist(T,X2).

これをswi-prologで。いくつかの場合に適応してみた例が以下のものである。

1 ?- [user]. 
|: getlist([H|[T]],[H,H1]) :- atom(H),[H1|_] = T,!.
|: getlist([H|[_]],H) :- atom(H),!.
|: getlist([H|[T]],[Z,T]) :- atom(T),getlist(H,Z),!.
|: getlist([H|[T]],[X1, X2]) :- getlist(H,X1),getlist(T,X2).
|: ^D
% user://1 compiled 0.00 sec, 4 clauses
true.

2 ?- getlist([a,b],X).
X = a.

3 ?- getlist([a,[b,c]],X).
X = [a, b].

4 ?- getlist([[[a,b],[c,d]],[e,f]],X). 
X = [[a, c], e].

5 ?- getlist([[a,b],[c,d]],X).
X = [a, c].

6 ?- getlist([[a,b],c],X).
X = [a, c].

7 ?- getlist([[[下, '場所-機能'], [人, 人]],[菓子, '人工物-食べ物']],X).
X = [[下, 人], 菓子].

8 ?- 

最初は、ルールを[user].で読み込ませているところで、2 以降が実行結果である。4でリストが二重になっているところが気になる他は、きちんと頭を取り出して、リストにしている。7は、前の記事での例を実行させたもので、カテゴリを除く語だけ取り出していることが理解できるだろう。

ただし、すべての場合を尽くしていないので、不都合が現れるかもしれない。

Juman, KNPのカテゴリ情報を加える

文章のprolog二分木化に際して、juman, knpが吐き出す語のカテゴリ情報を加えることにした。意味カテゴリにどんなものがつくかは、こちらが参考になる。ただ、juman++のものだが、jumanのものが見つからなかった。多分、同じようなものだろうと思う。

カテゴリがわかると、言葉の使い方に大きな力になる。カテゴリがばその言葉XXには、「XXに行く」という表現が成立するが、食べ物YYには「YYに行く」という表現は成り立たない。代わりに、「YYを食べる」は成り立つが、「XXを食べる」は、比喩としてしか成立しない。

逆にそれは、お笑いのボケ的には成立する。「XXを食べた」はボケであり、「そんなもの食べてうまいか!」というツッコミも成立する。

prologの宣言文(二分木)を作成するプログラムには少し手間取ったが、「羅生門」の一節は、例えば、次のような感じで変換される。

plsample(line0_7,
    node(だから,
        [],
        node(を,
            node(が,
                [[下, '場所-機能'], [人, 人]],
                [[雨, 抽象物], [やみ, 抽象物]]
            ),
            node(いたと,
                [待って, 待つ],
                node(よりも,
                    云う,
                    node(に,
                        [雨, 抽象物],
                        node(られた,
                            [ふりこめ, ふりこめる],
                            node(が,
                                [[下, '場所-機能'], [人, 人]],
                                node(に,
                                    node([],
                                        node(が,
                                            [行き, [所, '場所-施設']],
                                            なくて
                                        ),
                                        [途方, 抽象物]
                                    ),
                                    node(いたと,
                                        [くれて, くれる],
                                        node([],
                                            云う,
                                            node(が,
                                                方,
                                                node([],
                                                    適当である,
                                                    [ ]
                                                )
                                            )
                                        )
                                    )
                                )
                            )
                        )
                    )
                )
            )
        )
    )
).

例えば、6行目に、下人がある。jumanが下人を形態素解析で、下と人に分けてしまう。そこはそれとして問題だが、下は場所であり、人は人というカテゴリに属するという情報を、prologのリストにして組み込んでいる。

名詞にカテゴリが付与されている場合は、[下, '場所-機能']のように、その表示語とカテゴリが一対になったリストになる。この場合は、'-'が間に挟まれているので、prologがAtomとして正しく処理されるようにアポストロフィ「'」で囲んである。カテゴリを持っていなければ、表示後だけになる。一方、動詞は、[待って, 待つ],のように、表示語と原型が一対になっている。原形がなかったり、表示語と原形が同じ場合は、表示語だけになる。

例えば、「下人が雨やみを待っていた」をjumanを経由してknpにかけると、次のような結果(-simple) を出してくる。

# S-ID:1 KNP:4.19-CF1.1 DATE:2019/03/17 SCORE:-21.54059
* 2D <体言>
+ 1D <体言>
下 した 下 名詞 6 普通名詞 1 * 0 * 0 "代表表記:下/した 漢字読み:訓 カテゴリ:場所-機能" 
+ 4D <体言>
人 じん 人 名詞 6 普通名詞 1 * 0 * 0 "代表表記:人/じん 漢字読み:音 カテゴリ:人" 
が が が 助詞 9 格助詞 1 * 0 * 0 NIL 
* 2D <体言>
+ 3D <体言>
雨 あめ 雨 名詞 6 普通名詞 1 * 0 * 0 "代表表記:雨/あめ 漢字読み:訓 カテゴリ:抽象物" 
+ 4D <体言>
やみ やみ やみ 名詞 6 普通名詞 1 * 0 * 0 "代表表記:闇/やみ カテゴリ:抽象物" 
を を を 助詞 9 格助詞 1 * 0 * 0 NIL 
* -1D <用言:動>
+ -1D <用言:動><格解析結果:ガ/人;ヲ/やみ;ニ/-;デ/-;ヨリ/-;時間/-;ノ/->
待って まって 待つ 動詞 2 * 0 子音動詞タ行 6 タ系連用テ形 14 "代表表記:待つ/まつ" 
いた いた いる 接尾辞 14 動詞性接尾辞 7 母音動詞 1 タ形 10 "代表表記:いる/いる" 
EOS

ここで、*から始まるものを、私は「句 phrase」と定義している。したがって、複数の「語」が「句」を作り、複数の「句」が文章を作るということである。この文章を、prolog化すると次のようになる。

%% phrases: [ 0 r1 2 ] 
plsample(line0_0,
    node(を,
        node(が,
            [[下, '場所-機能'], [人, 人]],
            [[雨, 抽象物], [やみ, 抽象物]]
        ),
        node(いた,
            [待って, 待つ],
            [ ]
        )
    )
).

最初の文章は、prologのコメントでしかなくて、以下のものが第二句をルートフレーズとして、二分木が作成されたことを示している。(この辺りは以前の記事で詳細に解説したが、少し繰り返しの説明になっている。細かく知りたい場合は、過去の記事にあたっていただきたい)

ツリーで表すと次の画像のようになる。

最後の語は、ここでは、空リスト [ ]になっているが、必ずしも、そうなるわけではない。この辺も、過去の記事をいていただきたい。

少し過去を振り返る回り道をしたが、その理由は、句に注目していただきたかったからだ。ここでは、最初の句は、「下人が」になる。jumanは「下」と「人」と「が」という、三つの語でこの句を構成していると形態素解析した。最初に「下」という名詞で、[下, '場所-機能']というカテゴリとのペアのリストを作成して、さらに次に、「人」という語が来たので、[人, 人]というペアリストを作成して、それを前の[下, '場所-機能']と繋げたのであるが、これをprologで処理可能なように、それらをリストとして繋げて、[[下, '場所-機能'], [人, 人]]にした。これをリストにしないと、それらが二分木の左右の葉と解釈されて、次に来る右葉にとの関係で、エラーを引き起こしてしまう。

もし、語「下」にカテゴリがなかったら、これは、カテゴリを持たない単独語となり、次いの「人」が現れた時に、結局リストは、[下, [人, 人]]と構成されることになる。

もし[[下, '場所-機能'], [人, 人]]を作成した後に、同じ句内に別のもう一つの名刺とカテゴリがあって、[菓子, '人工物-食べ物']というリストを作ったら、これらは、

[[下, '場所-機能'], [人, 人],[菓子, '人工物-食べ物'] ]

という、それまでの中に、三つ目のリストとして組み込まれるのではなく、

[[[下, '場所-機能'], [人, 人]],[菓子, '人工物-食べ物']]

と、新たに、全体を囲むリストを作って、その中に収められる。どう違うのか?ちょっと、分かりにくいが、つまり、要素が上の場合のように三つになることはなく、一つのリストの中の要素は、リストか単独語の二つの要素しかないということである。結局これも二分木になっているのである。

図に描くと上のようになる。

swiprologで述語の入力

久しぶりに使ったら、swiprologを起動後に述語を入力する方法を忘れてしまっていたので、ここに記録しておく。

1 ?- [user].
|: jawiki(wiki_2_line_58616_1,node([],node(と,node(の,node(は,node([],node(や,node(で,一方,ソフトウェア階層),node(の,デバイス,node(と,プロトコル,[いった, いう]))),'論理レイヤー'),現行),'USB3.0'),共通で),node(では,'USB3.1Gen1モード',node(の,'5Gbps',node(と,'USB3.0',node([],同様に,node([],[使用, [でき, できる]],node(との,node(も,node(の,'Gen1モードGen2モード',いずれ),'USB3.0ハブデバイスケーブル'),node(性は,互換,node(れている,[保た, 保つ],node(ただしUSB3.0,[],node(下の,ハブ,node(は,機器,node(での,'5Gbps',node(と,転送,node([],なる,[ ])))))))))))))))).
|: ^D
% user://1 compiled 0.00 sec, 1 clauses
true.

2 ?-

日本語wikipedia全文prolog化に向けて

1月時点の日本語wikipediaのデータをxmlからテキスト化すると、10メガのファイルが544個できる。このうちの、一つをprolog化した。3時間くらいかかったと思う。swi-prologに読み込むのに数秒しかかからず、prolog上で検索させても、瞬間的に答えを出してくる。素晴らしい。

試したい方は、以下にデータを置いておきますので、ダウンロードしてみてください。
jawiki-1.zip
plologをインストールしたのち起動し、上記データを解凍して、スタートさせたprologで次のようにコマンドを打って、データと、ルールを組み込んでください。

?- ['jawiki-latest-pages-articles-001.swi','jawikirule.swi'].

例えば、?- left(言葉)とか?- left(ロボット)とか、適当にやってみてください。leftは、その言葉が他の言葉に能動的に働きかける場合、rightは、その言葉が、他の言葉を飾る場合の結果を出してきます。prologですから、セミコロンを入れると、次々に結果を拾ってきます。

ただ、これは、日本語wikipediaの1/544ののデータにすぎません。このまま544個全部をprolog化するのには、数ヶ月かかりそうだ(笑)。どうしたら早くできるのか、それが当面する課題だ。データを分割して、それぞれ別のスレッドで処理するという手はある。それでも10倍くらいのスピードになるだけだろう。それでも1週間、ぶっ続けで計算させる必要が出てくる。もう少し、速くしたい。

※その後、形態素解析、係り受け解析を、スレッド化に対応させることができる、上に書いた方向もうまくいかないことがわかった。

島崎藤村『夜明け前』の全文prolog化

文章をprolog化するというのは、文章をprologの宣言文として二分木に変換することを指している。このあたりのところの詳細は、これまでの記事をみていただくしかない。カテゴリのprologにぶら下がっている記事を参照していただきたい。

『夜明け前』は、かなりの長編である。幕末の木曽馬籠宿の名主、藤村の父親を想定した青山半蔵の人生を描いている。なぜ、この小説を選んだのか、私が高校の頃、夏、汗をかきながら必死で読んだ思い出の小説だからである。

なぜこんなことをやるのか。目指しているのは、日本語wikipedia全文をprologの宣言文に変換し。様々な形で検索できるように、そこにある「知識」を扱えるものにすることだ。そして、ロボットが、その概念的知識を使って、深みのある会話、さらには、自然なお笑いの会話をできるようにすることである。

最終目標に到達するための具体的なイメージは詰めきれていないが、当面、wikipediaのprolog化は、まずやってみようということである。が、その膨大なデータを本当に扱うことはできるのかは、最大の課題である。さしあたって、『夜明け前』をどの程度の速度で処理できるのかを見てみたかった。

青空文庫からダウンロードして、ルビを全て外したテキストは、2.4メガバイトだった。それをprologの宣言文に変換したら24.6メガ、10倍に膨らんだ。ただし、いろいろな余計な情報も出力しているので、実際には、もう少し絞れるだろうとは思う。swiprologで、これを読むこむのには、数秒しかかからなかった。十分早い、言葉を与えて、二分技を検索するのは、瞬く間に処理するので、十分早いことがわかった。

ただ、日本語wikipediaは、『夜明け前』の数百冊分はあるので、こんなスピードは実現できないのはわかっている。どこまで、手間がかかるかが知りたいところだ。

 

ベイズ分類器とニューラルネット

先の記事で、ピクセル相互の共分散を考慮したベイズ分類器にすると、MNISTで94%の正解率を実現できることを示した。この分類器は、ピクセル相互の独立分布を前提にしたNaive Bayes Classifier (単純ベイズ分類器)とは違う。MNISTの場合、28X28=784次元(ピクセル数)のベクトルが考慮されている。共分散マトリクスが使われるので、それらの相互関係が考慮されているところがすごいのである。

もちろん、全く共分散がないピクセル関係もある。また、特に、画像の端のピクセルなどは、そもそも1以上の値を持つことがないので、どの他のピクセルとも相関がゼロだったりする。pythonのscipy.statsライブラリの多変量正規分布の共分散マトリクスは、フルランクではなくてもいいので、こうしたゼロ相関に寛容である。

共分散マトリクスで全てのベクトル要素同士が関連しているというのは、ニューラルネットと構造はよく似ている。この全要素をつなげている共分散マトリクスは、分類されるべきパターン(概念)それぞれ一つずつあるので、例えばMNISTの識字の場合は10層のネットワークがあることになる。

学習によってこれらの共分散マトリクスが形成されるということは、ディープラーニングでウェイトの学習が行われるのと類似の機能である。

この共分散マトリクスを分析にすのは興味深い。やってみたい。