読者です 読者をやめる 読者になる 読者になる

コードネームは初話ユウ

自然言語処理でいろいろやってみる

cabochaソースを読む(4)係り受けレイヤ

いよいよ本丸の係り受け部分を見ていく。parse() は dep.cpp l.191から。

 

アルゴリズム自体は最初の回に紹介した論文に詳しく述べられている。parse()は100行に満たないので、論文と見比べながら読んでいけば大体わかると思うが、いくつかコメント:

l.207 build()は前処理。

l.245 estimate() が「src文節がdst文節に係るか?」を判定する。

ll.255-260 は、estimateが「係る」と判定したら、互いのA/B素性をコピーしあうところ。

 

build()の定義はl.51から。ll.79-83 各文節のfeatureを、頭文字によってstatic/gap/dyn_a/dyn_bに分類している(selectorでそのように頭文字をつけていた)。ll.93-100 kをはさむ全ての(i,j)ペアについて、kのgap featureを(i,j)に対応するgap[]エントリに入れている。j(j+1)/2+iって、三角行列か。

 

estimate()はl.109。ll.122-129 dist(文節間の距離)。1/2-5/6-の3種類しか分類してないのか。まあこれでも十分なのか。ll.132-140 static。src側は頭文字'f'、dst側は大文字'F'にしている。ll.152-168 dynamic。論文の動的素性のA,B,CがそれぞれA,a,Bに対応するようだ。

で l.176 で svm->classify() を呼んで係るか否かを判定。

 

もう少し具体的に素性の使われ方(計算)を知りたいので、classify()の中を見にいく。呼び元の形は

 classify(size, char** fp)

で、fsizeは出現した4種の素性の個数の合計。fpは、fp[0]="A:の", fp[1]="DIST:6-" のような感じで各素性が入っている。

 

svm->classify()の定義はsvm.cpp l.290にある。その中でまたオーバーライドされたclassify() (l.304)を呼ぶのだが…この中でDoubleArrayとかいろいろ使っていてかなり複雑で、ちょっと読んだだけではわからなかった。うーん、困った…

 

が、svm.cppの下の方にSVMTestというクラスがあり、こちらのclassify()は読みやすい(l.563, l.571)。SVMTestとは何かよくわからないが、svm.hのコメントを見ると "used only for debugging" とある。おそらく本チャンのSVMの方は秘術を尽くした高速化バージョンで、これのデバッグを、遅いが実装が単純(で間違いが少ない)SVMTestとの比較で行っていたのではないか、と推測。もしかして違ってるかもしれんが、いちおうそう思ってSVMTestを読み進める。

 

SVMTest::classify()は非常にシンプルで、Σ w[i]*kernel() を計算してるだけ。

kernel() は svm.cpp l.25 にあるが、引数がよくわからないので、先に SVMTest::open() (l.589)を見る。ファイル ifs を開いているが、おそらくmodelディレクトリのファイルだろう。dep.ipa.txtを見てみる。このファイルのフォーマットは、最初の回に紹介した Read Cabocha ページのpdf(2番め)に解説されている。l.40345までは素性。l.40347からdegree, biasで、その次からが各ベクトルとその重み。ここまで押さえた上でSVMTest::open()を見直すと、w_とx_がそれぞれ重みとベクトル(素性IDの並び)であることがわかる。

 

svm.cppに戻ってkernel()を見る。whileループがちょっとわかりづらいが、x1/x2がソートされた素性ID列なので、一致する素性の数を数えていることがわかる。0/1の変数のベクトルの内積(dot)をとってる、というか。返しているのは 

(1 + dot(x1,x2)) ^ deg

である。ちなみにdep.ipa.txtではdeg=2である。

 

以上でひととおりcabochaの係り受け判定の計算方法は大体わかったので、このシリーズはひとまず終了。