Go to Qiita Advent Calendar 2024 Top
LoginSignup
4
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@q-ikawa

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

Last updated at Posted at 2017-03-17

この記事は後編です。前編は以下。
http://qiita.com/q-ikawa/items/cf1bb593185333d88d66

意味計算

前編でノードの型と、適用できる計算規則をご紹介しました。
先の記事の通り型の演算だけで文章が一意に解釈可能となりうるか判断できますが、それだけではあまり嬉しくありません。
同時に型付ラムダ計算によって意味を計算することができます。一般的には述語論理で表現されることが多いのですが、ラムダ計算が出来ればなんでも大丈夫です。
計算規則の、「適用」はapply、「合成」はcompose、「substitution」はandThenに対応するのでメソッドを用意しておきます。
意味のクラスは先のノードの型と対応していて、ComplexLeft,ComplexRightの場合に必ずComplexMeaningクラスの意味に対応するようにし、ノードの型演算と同様に意味の演算もできるようにします。

Meaning.scala
trait Meaning {
  def apply(mean: Meaning): Meaning = {
    throw new Error("Unreachable")
  }
  def compose(mean: Meaning): Meaning = {
    throw new Error("Unreachable")
  }
  def andThen(mean: Meaning): Meaning = {
    throw new Error("Unreachable")
  }

  def getString: String
}

case class ComplexMeaning(mean: Meaning => Meaning) extends Meaning {
  val inner: Meaning => Meaning = mean

  override def apply(mean: Meaning): Meaning = {
    inner(mean)
  }
  override def compose(mean: Meaning): Meaning = {
    ComplexMeaning(z => inner(mean(z)))
  }
  override def andThen(mean: Meaning): Meaning = {
    ComplexMeaning(z => mean(inner(z)))
  }
  def getString = mean.toString()
}

// これは普通の名詞とかのイメージ。「ペン」とか、「りんご」とか
case class SimpleMeaning(label: String) extends Meaning {
  def getString = label
}

// 二項関係を表す意味。他動詞（私がりんごを「食べる」）などのイメージ
case class Relation(label: String, a: Meaning, b: Meaning) extends Meaning {
  def getString = s"${label} (${a.getString} ,${b.getString})"
}

// 述語を表す意味。形容詞や副詞や自動詞のイメージ
case class Predicate(label: String, a: Meaning) extends Meaning {
  def getString = s"${label} (${a.getString})"
}

意味と型を対応付ける

ノードトレイトを用意して、意味と型を関連付けます。
ノードトレイトはMeaningトレイトとTypeトレイトのインスタンスを持ちます。また、便宜的に（後で表示してやったね、ってするために）Stringのラベルももたせましょう。
そして型の計算規則で示したそれぞれの計算ができるものとします。（計算の中身はノードの種類によって変わるので委譲します）

Node(一部分).scala
sealed trait Node {
  val category: Type
  val mean: Meaning
  val label: String

  val applyNode: PartialFunction[Node, Node]
  def applyLeft(left: Node): Node = applyNode(left)
  def applyRight(right: Node): Node = applyNode(right)

  val compose: PartialFunction[Node, Node]
  def composeLeft(left: Node): Node = compose(left)
  def composeRight(right: Node): Node = compose(right)

  val substitution: PartialFunction[Node, Node]
  def substitutionLeft(left: Node): Node = substitution(left)
  def substitutionRight(right: Node): Node = substitution(right)
  def crossingSubstitutionLeft(left: Node): Node = substitution(left)
  def crossingSubstitutionRight(right: Node): Node = substitution(right)

}

型のところで記号名メソッドを使ったので、ここでも同様な矢印で表現できるようにして、一貫性を保ちます。
ノードの実装クラスは、ノードの型と対応します。それぞれの計算規則に対応するようにルールを書いて、意味計算もしてみましょう。
コンパニオンオブジェクトにファクトリを作っておけば、２ノードの計算ができるようになりました。
ついでに2つのノードが与えられた時に、いい感じの適用規則を拾ってきて適用してくれるreduceメソッドも作っておきます。

Node.scala
sealed trait Node {
  val category: Type
  val mean: Meaning
  val label: String

  val applyNode: PartialFunction[Node, Node]
  def applyLeft(left: Node): Node = applyNode(left)
  def applyRight(right: Node): Node = applyNode(right)

  val compose: PartialFunction[Node, Node]
  def composeLeft(left: Node): Node = compose(left)
  def composeRight(right: Node): Node = compose(right)

  val substitution: PartialFunction[Node, Node]
  def substitutionLeft(left: Node): Node = substitution(left)
  def substitutionRight(right: Node): Node = substitution(right)
  def crossingSubstitutionLeft(left: Node): Node = substitution(left)
  def crossingSubstitutionRight(right: Node): Node = substitution(right)

  def -->(right: Node): Node = applyRight(right)
  def <--:(left: Node): Node = applyLeft(left)
  def -+>(right: Node): Node = composeRight(right)
  def <+-:(left: Node): Node = composeLeft(left)
  def -/>(right: Node): Node = substitutionRight(right)
  def </-:(left: Node): Node = substitutionLeft(left)
  def -\>(right: Node): Node = crossingSubstitutionRight(right)
  def <\-:(left: Node): Node = crossingSubstitutionLeft(left)

  def ?-->(right: Node): Boolean = category --> right.category isDefined
  def ?<--:(left: Node): Boolean = left.category <--: category isDefined
  def ?-+>(right: Node): Boolean = category -+> right.category isDefined
  def ?<+-:(left: Node): Boolean = left.category <+-: category isDefined
  def ?-/>(right: Node): Boolean = category -/> right.category isDefined
  def ?</-:(left: Node): Boolean = left.category </-: category isDefined
  def ?-\>(right: Node): Boolean = category -\> right.category isDefined
  def ?<\-:(left: Node): Boolean = left.category <\-: category isDefined

}

case class PrimitiveNode(label: String, category: PrimitiveType, mean: Meaning) extends Node {
  val applyNode = Node.UndefindFunction
  val compose = Node.UndefindFunction
  val substitution = Node.UndefindFunction
}

case class ComplexNodeLeft(label: String, category: ComplexLeft, mean: Meaning) extends Node {
  val applyNode: PartialFunction[Node, Node] = {
    case x: Node if x.category <--: category isDefined => Node(s"(${x.label} <--: ${label})", x.category <--: category get, mean(x.mean))
  }
  val compose: PartialFunction[Node, Node] = {
    case x: Node if x.category <+-: category isDefined => Node(s"(${x.label} <+-: ${label})", x.category <+-: category get, ComplexMeaning(z => (mean compose x.mean)(z)))
  }
  val substitution: PartialFunction[Node, Node] = {
    case x: Node if x.category </-: category isDefined => Node(s"(${x.label} </-: ${label})", x.category </-: category get, ComplexMeaning(z => mean andThen x.mean (z)))
    case x: Node if category -\> x.category isDefined => Node(s"(${label} -\\> ${x.label})", category -\> x.category get, ComplexMeaning(z => mean andThen x.mean (z)))
  }
}

case class ComplexNodeRight(label: String, category: ComplexRight, mean: Meaning) extends Node {
  val applyNode: PartialFunction[Node, Node] = {
    case x: Node if category --> x.category isDefined => Node(s"(${label} --> ${x.label})", category --> x.category get, mean(x.mean))
  }
  val compose: PartialFunction[Node, Node] = {
    case x: Node if category -+> x.category isDefined => Node(s"(${label} -+> ${x.label})", category -+> x.category get, ComplexMeaning(z => (mean compose x.mean)(z)))
  }
  val substitution: PartialFunction[Node, Node] = {
    case x: Node if category -/> x.category isDefined => Node(s"(${label} -/> ${x.label})", category -/> x.category get, ComplexMeaning(z => mean andThen x.mean (z)))
    case x: Node if x.category <\-: category isDefined => Node(s"(${x.label} <\\-: ${label})", x.category <\-: category get, ComplexMeaning(z => mean andThen x.mean (z)))
  }
}

// 今回は等位接続は対象外にします。
case class CoordinationNode(label: String, category: Coordination, mean: Meaning) extends Node {
  val applyNode = Node.UndefindFunction
  val compose = Node.UndefindFunction
  val substitution = Node.UndefindFunction
}

object Node {

  // reduceの中身。見やすいようにPFで定義して、reduceでは .liftする
  // これが自然言語ごとに可能な操作・優先順位が異なる？
  // とりあえず頭から適用できるものを貪欲に当てはめてみる
  val _reduce_pf: PartialFunction[(Node, Node), Node] = {
    case (left, right) if left ?--> right  => left --> right
    case (left, right) if left ?-+> right  => left -+> right
    case (left, right) if left ?-/> right  => left -/> right
    case (left, right) if left ?-\> right  => left -\> right
    case (left, right) if left ?<--: right => left <--: right
    case (left, right) if left ?<+-: right => left <+-: right
    case (left, right) if left ?</-: right => left </-: right
    case (left, right) if left ?<\-: right => left <\-: right
  }
  // left と right の並びでreduceできるときは Some(結果Node) を返す
  // reduceできない場合は Noneを返す
  val reduce = _reduce_pf.lift

  val UndefindFunction: PartialFunction[Node, Node] = new PartialFunction[Node, Node] {
    def isDefinedAt(target: Node): Boolean = false
    def apply(target: Node): Node = null
  }
  // ファクトリメソッド
  def apply(label: String, category: Type, mean: Meaning): Node = {
    category match {
      case prim: PrimitiveType => PrimitiveNode(label, prim, mean)
      case left: ComplexLeft   => ComplexNodeLeft(label, left, mean)
      case right: ComplexRight => ComplexNodeRight(label, right, mean)
      case coord: Coordination => CoordinationNode(label, coord, mean)
    }
  }

}

ここまでで2つのノードの演算ができるようになりました。
実際にノードを作って計算してみると

bigdog.scala
val dog = PrimitiveNode("dog", PrimitiveType("NP"),SimpleMeaning("犬っころ") )
val big = ComplexNodeRight("big", ComplexRight(PrimitiveType("NP"), PrimitiveType("NP")), ComplexMeaning(a => Predicate("でかい", a)))

println(big --> dog) // -> PrimitiveNode((big --> dog),PrimitiveType(NP),Predicate(でかい,SimpleMeaning(犬っころ)))
println((big --> dog).mean.getString) // でかい (犬っころ)
    
println(Node.reduce(big, dog)) // Some(PrimitiveNode((big --> dog),PrimitiveType(NP),Predicate(でかい,SimpleMeaning(犬っころ))))
println(Node.reduce(big, dog).get.mean.getString) // でかい (犬っころ)

大きい犬が表現できました！
なんと意味を理解するコンピュータの完成です。低レベルですが、素人０からここまで作ると達成感があります。
ちなみに便宜的にdogをNP(名詞句), bigをNP/NP(名詞句をとって名詞句を返す)としていますが、ちゃんとやっている人から怒られます。（とりあえずは計算機構が実現できればいいので現時点ではざっくり）

3ノード以上の並びを計算できるようにする

いい感じでNode.reduceもお仕事してくれることが分かったので、あとは3以上のノードの並びでも処理できるように素敵な（いわゆる「僕の考えた最強の」）アルゴリズムを書いていきましょう。
とりあえず今回は頭から貪欲に見ていって、ルールが適用できる場合は適用していってしまいます。なので複数に意味解釈できる場合も一つの意味しか出てきません。
行ごとにコメントを入れたのでここはソースをそのまま貼り付けます。

NodeSeq.scala
class NodeSeq(val seq: Seq[Node]) {

  def parse(): Option[Node] = {

    // reduce from right recursive while reducible
    // a b c d とseqにある時に、
    // → a b reduce(c,d) 
    // → a reduce(b, reduce(c,d))
    // と再帰していく。reducibleである間、続ける。
    @tailrec
    def reduceFromRight(list: Seq[Node]): Seq[Node] = {
      list match {
        // if list has 2 elements or more, (ex ) Seq(a,b,c,d)
        // 要素が2以上あれば
        case init :+ left :+ right =>
          // reduce last 2 elements,
          // 後ろの2つをreduceして
          Node.reduce(left, right) match {
            // then recurse with Seq(a, b, reduce(c,d)).
            // 新しいリストに再帰させる
            case Some(x) => reduceFromRight(init :+ x)
            // return given list , if it was irreducible
            // 後ろの2つがreduceできない場合は、引数で与えられたリストをそのまま返す
            case None    => list
          }
        // if list has just 1 elements or empty, 
        // return given list. 
        case _ => list
      }
    }

    // left(left.size-1) が今回見たいノード
    // left(left.size-1) と left(left.size-2) から見始めて再帰的にleft をreduceしていく。
    // leftが既約になったら、rightの先頭をleftの末尾に足して、再帰して同じことを繰り返す
    // 最終的にrightを1つづつ全部取ってきて、leftに既約な式が出来上がる。
    @tailrec
    def parseInner(left: Seq[Node], right: Seq[Node]): Seq[Node] = {
      val reducedLeft = reduceFromRight(left)

      right match {
        case firstOfRight +: othersOfRight => parseInner(reducedLeft :+ firstOfRight, othersOfRight)
        case _                             => reducedLeft
      }
    }

    // parseInnerは呼ばれるたびにright.sizeがデクリメントされるので、right.size回(=seq.size)
    // reduceFromRightは、最大で(引数リスト長+1)回呼ばれる（(reduceできる回数+1)回）で
    // parseInnerの中では最大でも seq.size * 2 回。reduceの評価も最大で seq.size * 2回呼ばれる。
    // よって最悪計算量はO(n)で計算できる。
    parseInner(Nil, seq) match {
      case one +: Nil => Some(one)
      case _          => None
    }
  }

}

これでいい感じです。

MyApp.scala
object MyApp extends App {
  override def main(args: Array[String]) {
    val dogMean = SimpleMeaning("dog")
    val haveMean = ComplexMeaning(a => ComplexMeaning(b => Relation("have", b, a)))
    val bigMean = ComplexMeaning(a => Predicate("big", a))
    val penMean = SimpleMeaning("pen")

    val dog = PrimitiveNode("dog", PrimitiveType("NP"), dogMean)
    val have = ComplexNodeRight("have",
      //   (S\NP)/NP
      ComplexRight(
        ComplexLeft(
          PrimitiveType("S"),
          PrimitiveType("NP")),
        PrimitiveType("NP")), haveMean)
    val big = ComplexNodeRight("big", ComplexRight(PrimitiveType("NP"), PrimitiveType("NP")), bigMean)
    val pen = PrimitiveNode("pen", PrimitiveType("NP"), penMean)

    val ns = new NodeSeq(big :: dog :: have :: big :: big :: pen :: Nil)
    val node = ns.parse()

    println(node)
// -> Some(PrimitiveNode(((big --> dog) <--: (((have -+> big) -+> big) --> pen)),PrimitiveType(S),Relation(have,Predicate(big,SimpleMeaning(dog)),Predicate(big,Predicate(big,SimpleMeaning(pen))))))
    println(node.get.mean.getString)
// -> have (big (dog) ,big (big (pen))) 
  }
}

まとめ

こうして文章の意味を理解することができました！やったね。
意味計算のところを何らかのコマンドに置き換えれば、何かの操作をすることもできますし、意味の木から文章が生成できれば翻訳もできます。
今回のNodeインスタンス（型情報と意味）がセットになったものをレキシコンと言います。
レキシコンさえ用意すればどんな言語でもこれで意味理解ができるように・・・
というのは嘘です。。。

今回は多義語や曖昧語を扱っていないので、決定的なアルゴリズムでノードを組み合わせていますが、実際には一つのノードの型や意味を複数の中から見つけ出さなくてはならず、文章の意味が通るような計算規則の適用順序を探索して見つけていくような営みが必要となります。
（今回等位接続を扱っていないのも、探索を書くのを放棄したからです。等位接続は名詞と名詞をつなぐ時と、文を文をつなぐ時で型が異なるため、1語だけでは型が特定できません。）

そして結局その探索は、尤もらしいものを見つけ出す問題になり、ベイジアンやNNなどのアプローチが取られています。

今回扱ったCCGパーサはもっとちゃんとしたものが、英語 ∧ Python 実装は色々公開されていますのでご興味のある方は触っていただけると良いと思います。

感想

CCGを自分で勉強しながら、Scalaでパチパチ打っていきましたが、無駄なくやりたいことを書くことができてScalaは楽しかったです。Scalaは最高です。
今回CCGパーサとしては中途半端なものを作りましたが、この仕組みを応用すれば、より自然言語に近いDSLのようなものが作れそう、と思っています。
ちょっと面白そうなアプリケーションが作れそうなので、作ってみようと思いました。

4
5
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?