Scalaで自然言語処理：組み合わせ範疇文法(Combinatory Categorial Grammar: CCG) パーサを作りかけてみた

ScalaでCCGパーサもどきを途中まで作ってみました。
この記事は前編です。後編は以下。
http://qiita.com/q-ikawa/items/233d877b9412bf3b1cd8

動機

自然言語処理というと、

• Pythonを使って
• 確率モデルでごにょごにょ（ベイジアンやNN含めた機械学習）

が「普通」なので、Python以外の言語を使って、確率モデル以外のことをしたかった、というのが動機です。Scalaを勉強中の身なのと、CCGが型付きラムダ計算に基づく文法理論ということでScalaで綺麗に書けるのではないか、と思いScalaでCCGパーサの実装に取り組みました。
（最低限の大枠はでき・・・たのと、個人的にいろいろと立て込んで、しばらく取り組める時間が空きそうなので、キリのいいタイミングでアウトプットしておこうという記事です。（完遂できていないことの言い訳です。））

CCGとは

CCGは文法理論の一つです。（自分でもちゃんとはわかっていないので）ざっくりとした説明ですが、形態素（単語）ごと（以下、ノード）に型付きのラムダ式を持っていて、それを2つずつ再帰的にくっつけていくと文の意味がわかるよ、というものです。

文章: Scala      is       fun.
　型: (NP)   (S\NP)/ADJ   ADJ

"/"と"\" は関数型のシグネチャで
A/B は「ひとつ右」のB型のノードをとってA型の値を返す関数。
A\B は「ひとつ左」のB型のノードをとってA型の値を返す関数。

この場合、まず is と fun がくっついて

(S\NP)/ADJ ADJ 
=> S\NP

"is fun"の型は S\NP となります。
次にScala と "is fun"がくっついて

NP S\NP 
=> S

となってS(文)が導出できます。
（ここでは型計算のみですが、同時に意味の計算が可能）

CCGにおける型

一個のノードの型は
・単純な型
・複合的な型
のどちらかからなり、複合的な型は、ある型を受け取ってある型を返す関数になっています。

<型> ::= <単純な型> | <複合的な型>
<複合的な型> ::= <型>/<型> | <型>\<型>　（A/Bは右、 A\Bは左に BをとってAを返す関数）
<単純な型> ::= e | t (eはエンティティ、tは真偽値変数)

したがってすべての型が 単純な型eとtの関数の組み合わせで表すことができます。
便宜的には先の例のように複合的な型のエイリアスとしてS、NPといった型も用いられます。

CCGでの形態素(単語)

CCGでは文は型をそれぞれ持ったノードの並びであると言えます。
先の英語の例では1単語 = 1ノードに対応していましたが、英語でも実際には色々なやり方があるようで、（ちゃんとわかっていないので、説明のレベルも中学生レベルに下がります）現在形/過去形とか三単元のsとかまでノードに分けることもあるようです。言語学の統語論・意味論などの分野ではそう言った細かいレベルで見ていった緻密な議論もされている一方、コンピュータの実用レベルでは英単語単位で扱われれていることが多いように思われます（英語だとスペース区切りで単語のパースがしやすいから、というのもあるのかと思います）。
日本語の文でも同様に、言語学的な分野では、（太郎）（が）（好き）（な）（花子）みたいな分け方をされていますが、言語処理では助詞までまとめて（太郎が）（好きな）（花子）とされていることが多いように見受けられます。
ただこの辺りはあまり（素人にわかる）日本語の説明などが見つけられなかったのでよくわかっていません。
が、単語ごとで切っても、文節区切りにしても、それぞれの辞書さえあれば同じ計算機構で意味解析ができるようです。(便利！)

ノードの計算規則

2つのノードの並びには計算規則が（適用できる場合が）あります。先の例で関数適用は暗に使っていましたが、

関数の適用 (X,Y,Zはいずれも型)
X    Y\X => Y
Y/X    X => Y
関数の合成
Y\X  Z\Y => Z\X
Z/Y  Y/X => Z/X
Substitution(定訳がわからなかった)
(X/Y)/Z Y/Z => X/Z 
(X/Y)\Z Y\Z => X\Z
Y\Z (X\Y)\Z => X\Z
Y/Z (X\Y)/Z => X/Z

といった変換が可能です。文献によっては他に幾つかの規則（上記をさらに一般化したようなもの）も見つかったのですが、日本語や英語をやる分には上記の規則で捉えられるようです（？）。

また、単一のノードに対してType Raisingという操作ができ

X => Y\(Y/X)
X => Y/(Y\X)

という型の変換ができます。

ノードの並びに対して、上記の変換を機械的に組み合わせ行うことで計算ができます。最後まで計算できない場合は、文法的な非文（ちゃんとした文章になっていない）となるようです。
また、ノード並びによっては、複数の計算順序をとることができ、その取る順番によって意味が変わることもあります。
これは「私は太郎のように泳げない」が

• 「（私は）（（（太郎の）（ように））（（泳げ）（ない））））」（→太郎は泳げない）
• 「（私は）（（（（太郎の）（ように））（泳げ））ない））」（→太郎は泳げる）

のどちらの意味でも解釈できる、と事象と対応しているようです。（個人的に一番感心しました！）

等位接続

英語の「and」とか日本語の「と」とか、「とか」とか、同じ型の並列するノードをくっ付けられる語があります。これを等位接続(coordination)といいます。
いろいろぐぐると、型と並列する位置付けで置かれていたり、それでもやっぱり型は上記の定義だったり、等位接続の理論的な位置付けがよくわかっていません。
前の文と後ろ文をとって文を返したり、前の名詞句と後ろの名詞句をとって名詞句を返したりできるので、型としてはS/S\SとかNP/NP\NPといった型をとります（NPは名詞句）。
言語学の歴史的には、CCGを導入することで等位接続をきれいに説明できるようになった（らしい）ので、CCGでも重要なものです。

これからパーサを作る上では、ノードからは型がわからない（I and you love him. のように名詞を結んでいるのか、I love you and you eat lunch.のように文を結んでいるのか、I eat and drink there. のように動詞を結んでいるのかわからない）ため、「この単語ならこの型だ！」ということができません（他の語も多義語などではそうですが、、、）。
したがって特別な考慮が必要です。（が今回未実装です。）

実装

なんとかCCGにおける型システムの話まで終わりました。ここまで言語学的な部分は自分でちゃんと理解できていないので、文章にすると適当なのが透け透けですね、、、恥さらしですが、、、閑話休題。

Scalaでとりあえず型システムを実装していきます。
型のtraitを用意して、先の各計算規則を書いていきます。

当初の想定では以下のようなクラスを用意して

理想.scala

class PrimitiveType extends Type
class ComplexType[A <: Type, B <: Type] extends Type

Scalaのパターンマッチングで型をマッチさせれば以下のような形でスマートにかける、

理想.scala

trait Type{
  // 関数適用
  def -->(target:Type) = (this,target)match{
    case (left:A <: Type , right: ComplexType[B<:ComplexType,A]) => ごにょごにょ
  }
}

と思ったのですが、実行時はジェネリクスの情報が残っていないので、そのようなマッチングはできませんでした。
そこで型ごとに一意となる文字列を作成し、等価判定を委譲することで型の判定を行うことにしました。
型のメソッドとして、上の計算規則を適用できるか、適用できる場合はSome(適用後の型)、適用できない場合はNoneを返すメソッドを作成しています。
また、Scalaではメソッド名の末尾を":"にすることで、後置記法によるメソッド呼び出しが可能になります。今回はノードの左右の並びが強い意味を持つので「(Scala <--: (is --> fun))」のような、直観的な並びでおいおいかけるように、後置記法も使って以下のようにしました。

CCG.scala

// 統語範疇を表すためのクラス  [-]はトレイト  [*] は具象型
// Type  [-]
// |  // プリミティブな型
// +- PrimitiveType [*] 
// |  // 複合的な型（関数）
// +- ComplexType [-]
// |  |  // 左のノードを引数にとって値を返す関数
// |  +- ComplexLeft *
// |  |  // 右のノードを引数にとって値を返す関数
// |  \- ComplexRight *
// | // 等位接続
// \- Coordination [*]
sealed trait Type {
  // 型（統語範疇）を一意に表す文字列
  val eigenString: String
  def equals(target: Type) = {
    eigenString == target.eigenString
  }

  // 右に引数をとって関数適用
  // X/Y Y => X
  def -->(target: Type) = (this, target) match {
    case (l: ComplexRight, r: Type) if l.right == r => Some(l.left)
    case _ => None
  }

  // 左に引数をとって関数適用
  // Y X\Y => X
  def <--:(target: Type) = (target, this) match {
    case (l: Type, r: ComplexLeft) if r.right == l => Some(r.left)
    case _                                         => None
  }

  // 右に関数をとって関数合成
  // X/Y Y/Z => X/Z
  def -+>(target: Type) = (this, target) match {
    case (l: ComplexRight, r: ComplexRight) if l.right == r.left => Some(ComplexRight(l.left, r.right))
    case _ => None
  }

  // 左に関数をとって関数合成できるかどうか
  // Y\Z X\Y => X\Z
  def <+-:(target: Type) = (target, this) match {
    case (l: ComplexLeft, r: ComplexLeft) if r.left == l.right => Some(ComplexLeft(r.left, l.right))
    case _ => None
  }

  // Forward Substitution
  // (X/Y)/Z Y/Z => X/Z 
  def -/>(target: Type) = (this, target) match {
    case (l: ComplexRight, r: ComplexRight) if l.right == r.right =>
      l.left match {
        case ll: ComplexRight if ll.right == r.left => Some(ComplexRight(ll.left, r.right))
        case _                                      => None
      }
    case _ => None
  }

  // Forward Crossing Substitution
  // (X/Y)\Z Y\Z => X\Z 
  def -\>(target: Type) = (this, target) match {
    case (l: ComplexLeft, r: ComplexLeft) if l.right == r.right =>
      l.left match {
        case ll: ComplexRight if ll.right == r.left => Some(ComplexLeft(ll.left, r.right))
        case _                                      => None
      }
    case _ => None
  }

  // Backward Substitution
  // Y\Z (X\Y)\Z => X\Z 
  def </-:(target: Type) = (target, this) match {
    case (l: ComplexLeft, r: ComplexLeft) if l.right == r.right =>
      r.left match {
        case rl: ComplexLeft if rl.right == l.left => Some(ComplexLeft(rl.left, l.right))
        case _                                     => None
      }
    case _ => None
  }

  // Backward Crossing Substitution
  // Y/Z (X\Y)/Z  => X/Z 
  def <\-:(target: Type) = (target, this) match {
    case (l: ComplexRight, r: ComplexRight) if l.right == r.right =>
      r.left match {
        case rl: ComplexLeft if rl.right == l.left => Some(ComplexRight(rl.left, l.right))
        case _                                     => None
      }
    case _ => None
  }

}

case class PrimitiveType(primitive: String) extends Type {
  val eigenString = primitive
}
sealed trait ComplexType extends Type {
  val left: Type
  val right: Type
}
case class ComplexLeft(left: Type, right: Type) extends ComplexType {
  val eigenString = s"(${left.eigenString})\\(${right.eigenString})"

}
case class ComplexRight(left: Type, right: Type) extends ComplexType {
  val eigenString = s"(${left.eigenString})/(${right.eigenString})"

}

case class Coordination() extends Type {
  val eigenString = s"φ";
}

ここまでの感想

• 基本的にはScalaは直観的に書けて、コード量も多くなく、素敵だと思いました。
• 関数合成は言語学の論文では、証明木の右側に B> (あるいは <B )みたいな書き方あったり、Substitutionは S> ( Sx> , <S , <Sx )みたいな書き方がされていて、メソッド名でも記号と英字の組み合わせができたら、それに即したもっとわかりやすいメソッド名が定義できたのに、とも思いました。(tokenizerのルールから変わるので無理でしょうけど)
• ジェネリクスのパターンマッチができればもっときれいに書けるのになー、と思いました。
  • ただこれについては、すごいプログラマの人ならすごいモナドとかを使っていい感じに型情報だけでマッチングできるのかもしれません。すごくないプログラマなので「Freeモナドとかを使えばなんとかなるんじゃないか」と根拠なく考えてみたけどダメでした。すごいプログラマの人、いい方法があれば教えてください。