コスト最小法によるViterbiアルゴリズムを実装してみた

前回は単語数最小法によるViterbiアルゴリズムを使って、「猫はうろうろ」を形態素解析しました。
www.yasuhisay.info
単語数最小法では、単語の品詞などは見ておらず、ただただ単語数を最小にするように動的計画法であるViterbiを動かしていきます。品詞を見ていないため、「家におくりました」は「家」、「におくり」、「ました」と間違って形態素解析されていました。

コスト最小法による形態素解析

そこで

ある単語がある品詞で登場するコスト
ある品詞 $t_1$ とある品詞 $t_2$ の接続するコスト

というコストの概念を導入します。

「ある単語がある品詞で登場するコスト」というのは、例えば

「まし」が助動詞で登場するコスト
「まし(増し)」が動詞で登場するコスト

というような感じで、単一の言葉でも、品詞が違う場合にはそのコストを区別するような考え方です。

一方、「ある品詞 $t_1$ とある品詞 $t_2$ の接続するコスト」というのは

「動詞」+「助動詞」はよくある組み合わせなので、コストは10
「名詞」+「助動詞」はほとんどありえない組み合わせなので、コストは10000

という感じのものです。

そして、これらのコストを分解した単語列に関して和を取ります。そして、この和を最小にするような切り方をViterbiアルゴリズムで探していく、ということをやります。これが今回やる「コスト最小法によるViterbiアルゴリズム」です。

これらのコストをどのように決定していくのか、という問題がありますがこれはテキストにおける頻度とその対数を考えることで導入することができます。しかし、これは次回以降やることにして、今回は与えられているということにします。

今回のものは品詞の接続コストのところで、2品詞の接続コストを見ていますが一般に3つ、4つ…と考えていくことができます。自然言語処理の講義では3つの品詞の接続コストを考える場合をきちんと説明しなさい、というようなのが課題になっていました。

プログラム

前回はクラスを特別に作らずやっていましたが、今回は

辞書の情報を関数に渡す際に引数が多くなりすぎた*1
単語に品詞の情報も付加させておかないとコスト最小のループがひどいことになった*2

などの理由で、ViterbiクラスとWordクラスを導入することにしました。

# -*- coding: utf-8 -*-

require "pp"

class String
  def japanse_length
    self.split(//u).length 
  end
end

class Word
  attr_reader :s
  attr_reader :pos
  attr_reader :length
  def initialize(s, pos)
    @s = s
    @pos = pos
    @length = @s.japanse_length
  end
  def to_s
    return "#{s}(#{pos})"
  end
end

class Viterbi
  attr_reader :l
  attr_reader :delta
  attr_reader :b
  attr_reader :con
  attr_reader :word
  def initialize(sl, dic, con, word)
    @sl = sl
    @dic = dic
    @con = con
    @word = word
    @l = @sl.japanse_length
    @delta = [[]]
    @b = [[]]
    @delta[0][0] = 0
    @b[0][0] = 0
  end

  def back_dic
    # キーで終わるようなハッシュを作る
    back_dictionary = Hash.new{|h,k| h[k] = []}
    @dic.each{|w|
      @word.each_key{|pair|
        if !pair[w].nil?
          back_dictionary[w.split(//u)[w.japanse_length-1]].push Word.new(w, pair[w])
        end
      }
    }
    return back_dictionary
  end

  def w(x, j)
    # 文字位置xで終わる単語のうちj番目の単語
    return back_dic[@sl.split(//u)[x-1]][j-1]
  end
  
  def t(x, j)
    # 文字位置xで終わる単語のうちj番目の単語の品詞
    return back_dic[@sl.split(//u)[x-1]][j-1].pos
  end

  def sharp_w(x)
    if x <= 0
      return 0
    else
      back_dic[@sl.split(//u)[x-1]].length
    end
  end

  def min_cost
    (1..l).each{|x| # xで終わる単語のループ
      puts "x, #{x} => #{sharp_w(x)}"
      if @delta[x-1].nil?
        @delta[x-1] = [0]
      end

      if @b[x-1].nil?
        @b[x-1] = [nil]
      end

      (1..sharp_w(x)).each{|i| # 文字位置xで終わるi番目の単語
        puts " w(#{x}, #{i}) #{w(x, i)}"
        y = x - w(x, i).length
        min = 1.0/0
        argmin = {}
        puts " 文字位置#{y}で終わる単語の数(#w(#{y}))は#{sharp_w(y)}です"
        
        if sharp_w(y) == 0
          @delta[x-1][i-1] = 0
          @b[x-1][i-1] = 0
          break
        end
        
        (1..sharp_w(y)).each{|j| # 文字位置yで終わるj番目の単語
              
          tmp_con = {}
          tmp_con[w(y, j).pos] = t(x, i)
          tmp_word = {}
          tmp_word[w(x, i).s] = t(x, i)

          puts "  「#{w(y, j)}」を採用した場合の最小コストは「#{@delta[y-1][j-1]}」です"
          puts "  #{@delta[y-1][j-1]} + #{@con[tmp_con]}  + #{@word[tmp_word]}"
          cost = @delta[y-1][j-1] + @con[tmp_con]  + @word[tmp_word]
          if min > cost
            puts "  update!! min #{cost}, argmin #{j} (previous cost #{min})"
            min = cost
            argmin[y] = j
          end
        }
        @delta[x-1][i-1] = min
        @b[x-1][i-1] = argmin
      }
    }
  end

  def back_track
    # leftのindexは講義資料に-1してある
    # bpのindexは講義資料に+1してある
    min = 1.0/0
    argmin = nil
    (1..sharp_w(l)).each{|i|
      if min > @delta[l-1][i-1]
        min = @delta[l-1][i-1]
        argmin = i
      end
    }

    bp = [argmin]
    w_prime = [w(@l, argmin)]
    left = [l - w(@l, argmin).length]
    bp.push @b[@l-1][argmin-1].values[0]
    m = @delta.length

    k = 1
    while true
      puts "k #{k}, w(#{left[k-1]}, #{bp[k]}) #{w(left[k-1], bp[k])}"
      puts " left[#{k-1}] #{left[k-1] - 1}, w_prime[#{k-1}] #{w_prime[k-1]}"
      w_prime.push w(left[k-1], bp[k])
      left[k] = left[k-1] - w_prime[k].length

      if left[k] != 0 # left(M) = 0となるうようなMを探している
        bp.push @b[left[k-1] - 1][bp[k] - 1].values[0] 
        print " bp "
        pp bp
        print " left "
        pp left
        puts " w_prime [#{w_prime.join(", ")}]"
      else
        break
      end
      k += 1
    end
    return w_prime
  end
end

sl = "家におくりました"
dic = ["家", "に", "おくり", "におくり", "まし", "ました", "た"]

con = {
  {"名詞" => "助詞"} => 30,
  {"名詞" => "名詞"} => 50,
  {"名詞" => "動詞"} => 200,
  {"名詞" => "助動詞"} => 10000,
  {"助詞" => "動詞"} => 10,
  {"助動詞" => "助動詞"} => 10,
  {"動詞" => "助動詞"} => 10,
  {"動詞" => "動詞"} => 100,
  {"動詞" => "名詞"} => 50,
}

word = {
  {"家" => "名詞"} => 0,
  {"に" => "助詞"} => 10,
  {"おくり" => "動詞"} => 100,
  {"におくり" => "名詞"} => 1000,
  {"ました" => "名詞"} => 100,
  {"まし" => "助動詞"} => 10,
  {"まし" => "動詞"} => 10,
  {"た" => "助動詞"} => 10
}

v = Viterbi.new(sl, dic, con, word)


puts "Viterbiクラスの構造は次のようになっています。"
v.back_dic.each_pair{|key, value|
  puts "#{key}, [#{value.join(", ")}]"
}

puts "=" * 70

(1..v.l).each{|x|
  (1..(v.sharp_w(x))).each{|i|
    puts "文字位置 #{x} で終わる単語のうち #{i} 番目の単語は「#{v.w(x, i)}」で、その品詞は「#{v.t(x, i)}」です。"
  }
}

puts "=" * 70

v.min_cost

puts "=" * 70

puts "Viterbiアルゴリズム後のdelta_x(i)は次のようになっています。"
pp v.delta
puts "Viterbiアルゴリズム後のB_x(i)は次のようになっています。"
pp v.b

puts "=" * 70
puts "バックトラックを開始します。"

result = ""
v.back_track.reverse.each{|w|
  result << w.to_s
}

puts "=" * 70

puts result

実行結果

こんな感じになりましたとさ。

/tmp% ruby min_cost.rb 
Viterbiクラスの構造は次のようになっています。
り, [おくり(動詞), におくり(名詞)]
た, [ました(名詞), た(助動詞)]
に, [に(助詞)]
家, [家(名詞)]
し, [まし(動詞), まし(助動詞)]
======================================================================
文字位置 1 で終わる単語のうち 1 番目の単語は「家(名詞)」で、その品詞は「名詞」です。
文字位置 2 で終わる単語のうち 1 番目の単語は「に(助詞)」で、その品詞は「助詞」です。
文字位置 5 で終わる単語のうち 1 番目の単語は「おくり(動詞)」で、その品詞は「動詞」です。
文字位置 5 で終わる単語のうち 2 番目の単語は「におくり(名詞)」で、その品詞は「名詞」です。
文字位置 7 で終わる単語のうち 1 番目の単語は「まし(動詞)」で、その品詞は「動詞」です。
文字位置 7 で終わる単語のうち 2 番目の単語は「まし(助動詞)」で、その品詞は「助動詞」です。
文字位置 8 で終わる単語のうち 1 番目の単語は「ました(名詞)」で、その品詞は「名詞」です。
文字位置 8 で終わる単語のうち 2 番目の単語は「た(助動詞)」で、その品詞は「助動詞」です。
======================================================================
x, 1 => 1
 w(1, 1) 家(名詞)
 文字位置0で終わる単語の数(#w(0))は0です
x, 2 => 1
 w(2, 1) に(助詞)
 文字位置1で終わる単語の数(#w(1))は1です
  「家(名詞)」を採用した場合の最小コストは「0」です
  0 + 30  + 10
  update!! min 40, argmin 1 (previous cost Infinity)
x, 3 => 0
x, 4 => 0
x, 5 => 2
 w(5, 1) おくり(動詞)
 文字位置2で終わる単語の数(#w(2))は1です
  「に(助詞)」を採用した場合の最小コストは「40」です
  40 + 10  + 100
  update!! min 150, argmin 1 (previous cost Infinity)
 w(5, 2) におくり(名詞)
 文字位置1で終わる単語の数(#w(1))は1です
  「家(名詞)」を採用した場合の最小コストは「0」です
  0 + 50  + 1000
  update!! min 1050, argmin 1 (previous cost Infinity)
x, 6 => 0
x, 7 => 2
 w(7, 1) まし(動詞)
 文字位置5で終わる単語の数(#w(5))は2です
  「おくり(動詞)」を採用した場合の最小コストは「150」です
  150 + 100  + 10
  update!! min 260, argmin 1 (previous cost Infinity)
  「におくり(名詞)」を採用した場合の最小コストは「1050」です
  1050 + 200  + 10
 w(7, 2) まし(助動詞)
 文字位置5で終わる単語の数(#w(5))は2です
  「おくり(動詞)」を採用した場合の最小コストは「150」です
  150 + 10  + 10
  update!! min 170, argmin 1 (previous cost Infinity)
  「におくり(名詞)」を採用した場合の最小コストは「1050」です
  1050 + 10000  + 10
x, 8 => 2
 w(8, 1) ました(名詞)
 文字位置5で終わる単語の数(#w(5))は2です
  「おくり(動詞)」を採用した場合の最小コストは「150」です
  150 + 50  + 100
  update!! min 300, argmin 1 (previous cost Infinity)
  「におくり(名詞)」を採用した場合の最小コストは「1050」です
  1050 + 50  + 100
 w(8, 2) た(助動詞)
 文字位置7で終わる単語の数(#w(7))は2です
  「まし(動詞)」を採用した場合の最小コストは「260」です
  260 + 10  + 10
  update!! min 280, argmin 1 (previous cost Infinity)
  「まし(助動詞)」を採用した場合の最小コストは「170」です
  170 + 10  + 10
  update!! min 190, argmin 2 (previous cost 280)
======================================================================
Viterbiアルゴリズム後のdelta_x(i)は次のようになっています。
[[0], [40], [0], [0], [150, 1050], [0], [260, 170], [300, 190]]
Viterbiアルゴリズム後のB_x(i)は次のようになっています。
[[0],
 [{1=>1}],
 [nil],
 [nil],
 [{2=>1}, {1=>1}],
 [nil],
 [{5=>1}, {5=>1}],
 [{5=>1}, {7=>2}]]
======================================================================
バックトラックを開始します。
k 1, w(7, 2) まし(助動詞)
 left[0] 6, w_prime[0] た(助動詞)
 bp [2, 2, 1]
 left [7, 5]
 w_prime [た(助動詞), まし(助動詞)]
k 2, w(5, 1) おくり(動詞)
 left[1] 4, w_prime[1] まし(助動詞)
 bp [2, 2, 1, 1]
 left [7, 5, 2]
 w_prime [た(助動詞), まし(助動詞), おくり(動詞)]
k 3, w(2, 1) に(助詞)
 left[2] 1, w_prime[2] おくり(動詞)
 bp [2, 2, 1, 1, 1]
 left [7, 5, 2, 1]
 w_prime [た(助動詞), まし(助動詞), おくり(動詞), に(助詞)]
k 4, w(1, 1) 家(名詞)
 left[3] 0, w_prime[3] に(助詞)
======================================================================
家(名詞)に(助詞)おくり(動詞)まし(助動詞)た(助動詞)