kentsu.dat

何かその時の興味でいろいろする人。最近はScala使ってる。

n-gramとマルコフ連鎖の理論と実装、もちろんScalaを使って。

対話システムを作りたかった

対話システムという名の対話botを作っているがいきなり深層学習はハードルが高すぎたから人工無能から始めることにした。

この記事の流れ

今回の記事は次のように進んでいく。

と、まぁほとんどがアルゴリズム的な話になりそう。

n-gramとは

n-gramとは形態素解析のように辞書を使って文章を品詞分解していくのではなく「文字単位で文章を分割していく」手法のこと。
なので、形態素解析のように辞書を必要とするわけではない。

またn-gramのnが何を指すかというとn文字で分割するという意味である。


1-gramは1文字ずつ分割する。
2-gramは2文字ずつ分割する。
3-gramは3文字ずつ分割する。

みたいに。

実際には次のように分割していく。

文章:今日は雨のようだ。
条件:n = 2とする

分割:
今日
日は
は雨
雨の
のよ
よう
うだ
だ。

ただここで問題なのがnが小さすぎるとその自然言語にもよるが不適切な結果を生むことに成る。

文章:東京都庁
条件:n = 2

分割:
東京
京都
都庁

n-gramを使って文字列分割を行うと本来想定している最適解とは異なる場合がある。
今回で言えば、「東京都庁」という意味を持つのに本来の意味とかけ離れた「京都」が出てしまうなど。

そこで日本語の文章を分割するときはn=3を想定するっぽい。
簡単故にこれを実際の会話で使う文章生成に使うと割と精度が下がる。

n-gramのサンプル

今回は、「青空文庫」さんから夏目漱石の「こころ」をお借りしました。
事前にutf-8にしてあれこれ邪魔な記述を抜かして使用します。

これに対してn = 3の時のn-gram、つまりtri-gramで分割しました。

ソースコードは次の通り。

import scala.io.Source
import scala.io.BufferedSource
import scala.collection.mutable.Map

object Ngram{

  //3文字ずつ分割していく
  private [this] val n:Int = 3

    
  def main(args:Array[String]):Unit = {
      
      //文字列とその出現頻度を格納
      var ngramMap:Map[String,Int] = Map[String,Int]()
      

      //ファイルを読み込む
      val source = Source.fromFile("kokoro.dat","utf-8")

      //1行ずつ読み込む
      val lines:Iterator[String] = source.getLines

      //ngramで分割し格納
      for(line <- lines){

        var tmp_line:String = line

        while(tmp_line.length >= this.n){
          
          var subString:String = tmp_line.take(this.n)

          //切り出した文字列が今までに出てないなら追加
          //出現しているなら出現回数の更新
          if(!ngramMap.contains(subString)){
            ngramMap += (subString -> 1)
          }else{
            var count:Int = ngramMap(subString) + 1
            ngramMap.update(subString, count)
          }
          
          //先頭文字の除去
          tmp_line = tmp_line.tail
        }

      }

      val result_key:Iterable[String] = ngramMap.keys
      for(key <- result_key){
        println(s"${key} ${ngramMap(key)}")
      }
            
  }

}


これをコンパイルして次のように実行する。

$ scala Ngram | sort -r -nk2 | head

そうすると、よく使われる部分文字列ベスト10が切り出せた。

部分文字列 出現回数
した。 1464
ました 1026
った。 856
です。 789
のです 776
かった 593
たので 562
なかっ 470
ってい 397
奥さん 386

語尾とか接続詞的なあれこれは頻度高いのわかるが「奥さん」…。

マルコフ連鎖とは

マルコフ連鎖とは、ある事象がその直近の事象のみに影響を受けて確率的に変化するという考えかた。
これにはマルコフ性という、次に起こる事象が過去に起きた事象の影響を受けないという性質がなければならない。

もっと言えば、マルコフ性を備えた確率過程のことをマルコフ過程といい、その中でも状態空間が連続ではなく離散的である場合を特にマルコフ連鎖という。

身近な例を上げるなら、すごろくや人生ゲームといったものが一種のマルコフ連鎖の例と言える。

今回はこれを自然言語処理、特にn-gramで分割したものに対して適用する。

n-gramマルコフ連鎖を使った文章生成

本来は確率を使ってどうこうするけど、Scalaでそれをやってしまうと処理速度的に心配なので次に出てくる文字列をひたすら追加しそこからランダムで選択することにした。

それが次のコード

import scala.io.{Source,BufferedSource}
import scala.collection.mutable.{Map,ArrayBuffer}
import scala.util.Random

object Markov{

  //tri-gramを想定
  private [this] val n:Int = 3

  def main(args:Array[String]):Unit = {

    //ngramの分割結果と次に続く文字列を格納する
    var ngramMap:Map[String,ArrayBuffer[String]] 
      = Map[String,ArrayBuffer[String]]()

    //ファイルから一行ずつ読み込む
    val source:BufferedSource = Source.fromFile("kokoro.dat","utf-8")
    val lines:Iterator[String] = source.getLines


    //ngramで分割
    for(line <- lines){

      var tmp_line:String = line
      var split_str:String = tmp_line.take(this.n)

      //先頭文字列だけ独立して追加
      if(!ngramMap.contains(tmp_line.take(this.n)))
         ngramMap += ( split_str -> ArrayBuffer.empty[String] )

      tmp_line = tmp_line.tail

      while(tmp_line.length >= this.n){
        
        var ngramArray:ArrayBuffer[String] = ngramMap(split_str)
        ngramArray += tmp_line.take(this.n)
        ngramMap.update(split_str,ngramArray)
        
        if( !ngramMap.contains(tmp_line.take(this.n)) )
          ngramMap += (tmp_line.take(this.n) -> ArrayBuffer.empty[String])

        split_str = tmp_line.take(this.n)
        tmp_line = tmp_line.tail
      }
    }


    //先頭文字列選択を行う
    val rnd:Random = new Random
    var result_str:String = ngramMap.keys.toList(rnd.nextInt(ngramMap.size)) 

    var tmp_str:String = result_str
    while(!result_str.contains("。")){
      var next_wordArray:ArrayBuffer[String] = ngramMap(tmp_str)
      tmp_str = next_wordArray(rnd.nextInt(next_wordArray.size))
      result_str += tmp_str.last
    }


    println(result_str)

  }
}

これを実行することによって得たいくつかの文章は次の通り
ひどい文もできていたので比較的ましなものを選択した。

叔父だの叔母だの、その性質としてよかった。
耳に異様な調子をもっと底の方に沈んだ心を大事そうに聞いた。
端書を受けない事はできないかと疑ってみました。
かも彼らは、退屈のために箒で背中を向けた。
今東京へ出て来たといって褒めるのですから、私には分りませんでした。
生と異なる点を明白に述べなければ純白でなくっちゃなるまですでに妻を迎えたらしい。
父に万事をやっ付けて離さない悠長な田舎にありませんでした。
思うかと、奥さんをどうしてもいいました
酸にも聞こえる試しはまるで頼りにするのは定めていた私が、それは迷惑そうな顔をちょっと顔だけ向け直して来て、いつの間にか暮れて春になりました。
まだ起きているのであった。

ngramだと単語が意味を持たないので、計算コストは低いけど出来上がる文が時折変な文になってしまう。
マルコフ連鎖を採用しているのも原因の一つであるけど。


対話botへの応用

これをどう対話botに応用するかといえば、今回はngramとマルコフ連鎖を使ったわけだがそれを例にするなら
ngramで分割する対象データをtwitterfacebookといった比較的人が会話で使う構造をしているものにするといったことが考えられる。
文章生成に関してはこのままマルコフ連鎖で生成できる。

自分が発話した内容に関してもngramを用いてどんどんデータを追加していくとなおさら面白いかもしれない。