はじめに
ScalaMatsuri 2016で「ScalaとSparkによる日本語テキストマイニング」を聞いて面白そうだったので、まずは日本語形態素解析エンジンkuromojiを触ってみることにしました。
といっても形態素解析するだけなら、ただ単にkuromojiを呼びだすだけなので、もうちょっと賢そうなことをしたいなぁと思っていたところ、「kuromoji.js使って構文解析した」という記事を読みました。
確率自由文脈文法による構文解析……これは何だか凄そうです！
自由文脈文法って何だか聞き覚えあるなと思っていたら、そうそうプログラミング言語でも親しみのあるBNF（バッカス・ナウア記法）で記述できる文法のことでした。まぁ単純な置換ルールによる再帰的な文法のことですね。その置換ルールに確率を付けたのが確率自由文脈文法、と。
「文脈自由文法の話」というスライドがとても分かりやすかったです。
構文解析結果
今回は構文木の推定だけ行って、学習はしていません。
元記事と同じ構文木が得られたので、たぶん合っていると思います。
S 0.2 (8.00e-04)
|
+- 名詞句 1.0 (1.00e-01)
| |
| +- 名詞 1.0 (1.00e-01)
| | |
| | +- 形容詞 0.1 (1.00e-01)
| | | |
| | | +- 名詞 - 隣
| | | |
| | | `- 助詞 - の
| | |
| | `- 名詞 - 客
| |
| `- 助詞 - は
|
`- 動詞 0.5 (4.00e-02)
|
+- 名詞 1.0 (8.00e-02)
| |
| +- 形容詞 0.4 (8.00e-02)
| | |
| | +- 副詞 - よく
| | |
| | `- 形容詞 0.2 (2.00e-01)
| | |
| | +- 名詞 - 柿
| | |
| | `- 動詞 - 食う
| |
| `- 名詞 - 客
|
`- 助動詞 - だ
実装
とりあえず置換ルールのクラスを定義します。
case class Rule(left: String, right1: String, right2: String, prob: Double)
構文木の各ノードは、置換ルールもしくは形態素、そして部分木の確率を持っていれば良さそうです。
case class PcfgNode(label: Either[Rule, Token], prob: Double)
構文木の型は、scalazのTreeを利用してTree[PcfgNode]とします。
あとは構文木を推定する関数です。元記事で使われているCYK法と内側外側アルゴリズム……はちゃんと勉強したほうが良さそうなので……とりあえずシンプルな再帰関数で実装してみます。
いちおう計算効率にも配慮して、メモ化してみました。といってもscalazのMemoを噛ませているだけです。scalaz便利。
def calcPcfgTree: ((Seq[Token], Seq[Rule], String)) => Option[Tree[PcfgNode]] =
Memo.mutableHashMapMemo { case (inputs: Seq[Token], rules: Seq[Rule], target: String) =>
inputs.size match {
case 0 =>
None
case 1 =>
if (inputs.head.getPartOfSpeechLevel1 == target) {
Some(PcfgNode(Right(inputs.head), 1.0).leaf)
} else {
None
}
case size =>
val trees =
for {
rule <- rules if rule.left == target
i <- Range(1, size)
child1 <- calcPcfgTree(inputs.take(i), rules, rule.right1)
child2 <- calcPcfgTree(inputs.takeRight(size - i), rules, rule.right2)
} yield {
val rootProb = rule.prob * child1.rootLabel.prob * child2.rootLabel.prob
PcfgNode(Left(rule), rootProb).node(child1, child2)
}
trees.reduceOption(Ordering.by((_: Tree[PcfgNode]).rootLabel.prob).max)
}
}
やりたい気持ちをそのままコードに落とせた気がします。
Scalaのfor文は、複雑なデータ変換もネストを深くせずに書けるのでいいですね。
あとは構文木をprintすればお終いです。
ノードのshow関数を実装すれば、あとはscalazが木っぽく整形してくれます。
implicit val showPcfgNode = Show.show { node: PcfgNode =>
node.label match {
case Left(rule) => f"${rule.left} ${rule.prob} (${node.prob}%.2e)"
case Right(token) => f"${token.getPartOfSpeechLevel1} - ${token.getBaseForm}"
}
}
for (r <- result) println(r.drawTree)
今後の課題
自然言語処理なにそれおいしいの状態でも、なんちゃって構文解析はできることが分かりました。敷居思ったより高くない？
いずれ適当な文章をスクレイピングして、適当な自然言語処理をして、適当にドヤ顔することを夢見つつ、まずは何かしらの教科書読みます。たぶん……。
全コード
import com.atilika.kuromoji.ipadic.{Token, Tokenizer}
import scala.collection.JavaConverters._
import scalaz.Scalaz.ToTreeOps
import scalaz.{Memo, Show, Tree}
case class Rule(left: String, right1: String, right2: String, prob: Double)
case class PcfgNode(label: Either[Rule, Token], prob: Double)
object Main extends App {
val rules = Seq(
Rule("S", "名詞句", "形容詞", 0.5),
Rule("S", "名詞句", "名詞", 0.3),
Rule("S", "名詞句", "動詞", 0.2),
Rule("名詞", "形容詞", "名詞", 1),
Rule("名詞句", "名詞", "助詞", 1),
Rule("形容詞", "名詞", "助詞", 0.1),
Rule("形容詞", "名詞", "動詞", 0.2),
Rule("形容詞", "副詞", "形容詞", 0.4),
Rule("形容詞", "副詞", "形容詞", 0.3),
Rule("動詞", "副詞", "動詞句", 0.5),
Rule("動詞", "名詞", "助動詞", 0.5)
)
val tokenizer = new Tokenizer()
val tokens = tokenizer.tokenize("隣の客はよく柿食う客だ").asScala.toVector
val result = calcPcfgTree(tokens, rules, "S")
implicit val showPcfgNode = Show.show { node: PcfgNode =>
node.label match {
case Left(rule) => f"${rule.left} ${rule.prob} (${node.prob}%.2e)"
case Right(token) => f"${token.getPartOfSpeechLevel1} - ${token.getBaseForm}"
}
}
for (r <- result) println(r.drawTree)
def calcPcfgTree: ((Seq[Token], Seq[Rule], String)) => Option[Tree[PcfgNode]] =
Memo.mutableHashMapMemo { case (inputs: Seq[Token], rules: Seq[Rule], target: String) =>
inputs.size match {
case 0 =>
None
case 1 =>
if (inputs.head.getPartOfSpeechLevel1 == target) {
Some(PcfgNode(Right(inputs.head), 1.0).leaf)
} else {
None
}
case size =>
val trees =
for {
rule <- rules if rule.left == target
i <- Range(1, size)
child1 <- calcPcfgTree(inputs.take(i), rules, rule.right1)
child2 <- calcPcfgTree(inputs.takeRight(size - i), rules, rule.right2)
} yield {
val rootProb = rule.prob * child1.rootLabel.prob * child2.rootLabel.prob
PcfgNode(Left(rule), rootProb).node(child1, child2)
}
trees.reduceOption(Ordering.by((_: Tree[PcfgNode]).rootLabel.prob).max)
}
}
}
name := "pcfg"
version := "0.0.0"
scalaVersion := "2.11.7"
libraryDependencies ++= Seq(
"com.atilika.kuromoji" % "kuromoji-ipadic" % "0.9.0",
"org.scalaz" %% "scalaz-core" % "7.2.1"
)
sbt.version=0.13.11