Blog
予約したもののインフォバーを手に入れられない海野です．
人間の高度な知的処理の一つが、推論処理です．今日はその推論を、述語論理と機械学習の組み合わせで模倣したMarkov Logic Networkという手法と、そのOSS実装であるAlchemyの紹介です．
鳥とはなんですか？という質問に対してどう答えるでしょうか．大雑把には、以下のように考えるでしょう．
鳥とは、空を飛ぶ動物です．
この回答に対して、「ペンギンは飛ばないよ」と反論する人がいるかも知れません．
鳥とは、くちばしを持った動物です．
すると、「カモノハシは鳥じゃないよ」と言われるでしょう．人間は初めて見た生き物が鳥かそうじゃないか判断するとき、どうしているのでしょうか．思うに、少数の規則（飛ぶかどうか．くちばしをもつか）から総合的に判断しているように思われます．人間の推論というのは概ね以下のような特徴を持っているのではないかと予想されます．
- 一般化された規則を持っている（「空を飛ぶ動物は鳥だ」）
- これらの推論で物事を判断している（「つばめは空を飛ぶ、つばめは動物だ」よって「つばめは鳥だ」）
- しかし、その推論規則は非常にソフトで、必ずしも全て成立しない（「ペンギンは空を飛ばない、しかしくちばしがある、羽がある」よって、やっぱり「ペンギンは鳥」な気がする）
前置きが長くなりました．こうしたソフトな推論を模倣した手法が、今日紹介したかったMarkov Logic Network (Markov Logicとも）です．Markov Logic自体の論文は、2005年前後に集中的に出ています．
“Markov Logic Networks”, Matthew Richardson, Pedro Domingos. Machine Learning, 62, 2006.
“Unifying Logical and Statistical AI”, Pedro Domingos, Stanley Kok, Hoifung Poon, Matthew Richardson, Parag Singla. AAAI 2006.
“Markov Logic: An Interface Layer for Artificial Intelligence”, Pedro Domingos, Daniel Lowd. Morgan and Claypool Publishers. 2009.
Markov Logicをひとことで言うと、ソフトな一階述語論理といえます．一階述語論理では記述した論理式を充足できるかに焦点が当てられました．しかし、先ほど書いたように、実問題を一階述語論理に当てはめて考えると、必ずしも全ての論理式を満たさないところに求める解があることが多いようです．そこで、なるべく満たす論理式の数が多くなるような、もっと言えばそれぞれの論理式に重みをおいて、満たさせない論理式の重みの総和が小さくなるように推論してあげる．これがMarkov Logicです．実際は、Markov Networkを形成して、確率が最大になるような割り当てを求めます．
別の見方をしてみましょう．Markov Networkは多数の確率変数の同時確率分布を記述するグラフィカルモデルです．しかし、一方でこのグラフィカルモデルを1から書くのは大変です．そこで、このグラフィカルモデルを簡単に記述するようなテンプレートが欲しくなります．このテンプレートとして一階述語論理を採用して、論理式を書くとグラフィカルモデルが生成されるのがMarkov Logicである、と見ることができます．
Markov Logicの面白いところは、一階述語論理による推論と、機械学習という2つの異なる人工知能研究の成果が、相補的にまじりあっているところにあります．述語論理のハードな制約がMarkov Networkにより緩和され、Markov Networkにおけるグラフィカルモデルの記述が述語論理によって容易になる、という具合です．最近は毎年のようにMarkov Logicを使った論文が発表されているところからも、その強力さと適用範囲の広さを物語っているでしょう．
Alchemy
今日は、このMarkov LogicのOSS実装であるAlchemyを使ってみます．AlchemyはWashington大学のグループによってメンテナンスされています．
試しに品詞タグ付けを作ってみました．チュートリアルが豊富なので、それを参照します．ファイル名はpos.mlnとします．
雰囲気だけ伝わるように、抜粋して説明します．Det(i)はi番目の単語の品詞が冠詞であることを示す述語です．同様に、名詞(Noun)、動詞(Verb)、形容詞(Adj)、前置詞(Prep)とします．述語論理では変数と論理式の間を述語によって橋渡しする必要があります．Succ(i, j)はiの次がjであることを示します．つまり、j = i + 1であることを示します．すると、例えば冠詞の次は名詞である、という規則は
Det(i) ^ Suc(i, j) => Noun(j)
と記述できます．^はandで、vがorです．Alchemyでは自由変数は全称量化子が付いているものとして解釈されます．文法は、北先生の「確率的言語モデル」のHMMの章から拝借しました．
さらに、各単語と品詞の対応を記述します．i番目の単語が”an”であることを、Token("an", i)と書くとします．すると、「i番目の単語が”an”のとき、i番目の品詞は冠詞である」は以下のように記述できます．
Token("an", i) => Det(i)
同様に、他の単語と品詞についても記述します．以上の制約は、いずれもソフトな制約です．満たしても満たさなくてもいいですが、満たさないとコストが発生します．実際のコストは学習データに基づいて決定されます．
このままだと、同じ単語に対して複数の品詞が割り当てられてしまうので、制約を加えます．i番目が冠詞なら、他ではない、という事を記述します．
Det(i) => !Noun(i) ^ !Adj(i) ^ !Verb(i) ^ !Prop(i).
という規則を、品詞の数だけ用意する必要があります．最後にピリオドをうつと、ハードな制約を記述することができます．ハードな制約はコストが無限大の制約だと思えばよいようです．全てハードな制約にすれば普通の一階述語論理の推論器として利用出来るでしょう．以上で、論理式の記述は終わりです．
正解データを作りましょう．正解データは先程の変数になっていた部分に、具体的な値をセットします．例えば、“time like an arrow”（時は矢が好き）という正解文は、
Token("time", 0)
Token("like", 1)
...
Noun(0)
Verb(1)
...
Succ(0, 1)
Succ(1, 2)
...
という風になります．正解文に無理があるのは小さいセットでやりたかったからなので気にしないでください．ファイル名は*.dbとするのが通例のようです．いくつか正解付きの文を食わせて学習します．学習は以下のようなコマンドで行います．
$ learnwts -d -i pos.mln -o pos-out.mln -t pos-train1.db,pos-train2.db,pos-train3.db -ne Noun,Verb,Det,Prep,Adj -multipleDatabases
各pos-trainX.dbが学習データで、出力がpos-out.mlnに生成されます．学習は非常に時間がかかります．たった3文だけなのに数十秒係りました．品詞タグ付け位簡単な処理だと、あまり恩恵を受けませんね．
pos-out.mlnをひらいてみると、例えば以下のように、先ほど書いた論理式の前に重みが書かれています．これが推論された重みです．
// -0.132592 Det(i) ^ Succ(i,j) => Noun(j)
-0.132592 !Succ(a1,a2) v !Det(a1) v Noun(a2)
できたpos-out.mlnを使って、実際に品詞付与するのは、inferコマンドを利用します．
$ infer -i pos-out.mln -r pos.result -e pos-test.db -q Noun,Det,Prep,Adj,Verb
実行結果はpos.resultに生成されます．入力のpos-test.dbの中身は “time flies like an arrow”です．先の学習用のdbファイルと違って、品詞情報がありません．出力は、pos.resultに生成されます．pos.resultには各単語の品詞の確率が記述されます．
Noun(0) 0.69898
Noun(1) 0.0760424
...
スコアの高いところだけ拾うと、Noun, Verb, Prep, Det, Nounと、正しく推論されました．スコアにばらつきが大きいですが、学習事例も少ないのでこんなもんでしょう．
最後に、何故この技術に着目しているかを書きます．データを自動で分類するような問題を解くときに、大きく分けてルールベースと機械学習の2つがあります．機械学習ベースの手法のほうが、メンテナンスコストや実行速度の点で望ましいのですが、必ずしも簡単にいかないことがあります．ひとつは、機械学習の手法は微調整が難しことです．お客様によってはどうしても間違ってはいけないケースや、既存のルールなどを持っている場合があります．Markov Logicならハードな制約として簡単に記述することができます．もうひとつの理由は、出力に制約があるケースです．単に多値分類するだけならいくらでも手法がありますが、出力に構造がある場合、とたんに問題が厄介になります．こうした要望にも柔軟に対応するための新しい手法が欲しくなります．
現状ではまだまだ速度も十分とは言えず、実際のビジネスに利用したこともありません．ただ、将来的にこうした技術が現在困難な様々な問題を解決する基盤になる可能性は十分あるのではないかと想像しています．
