学生エンジニアのMoriです。
今回は 言語モデルの一つ 1-gram言語モデル について書きたいと思います。

目次

言語モデルとは

wikipediaでの言語モデルの説明は以下のようなものです.

言語モデルとは,単語列に対する確率分布である.長さmの単語列が与えられたとき,単語列全体に対しての確率 サンプル画像 を与える.言語モデルを用いると異なるフレーズに対して相対的な尤度を求めることができるため,自然言語処理の分野で広く使われている.

簡単にいうと、任意の文を与えたとき、どのくらいの確率でその文が母集団となるデータの中に存在するかを表すためのモデルです.例えば、日常会話全体を母集団とするなら「いちご食べたい」と「いちご投げたい」のどちらが存在する確率の高い文章でしょうか?常識的に考えれば「いちご食べたい」の確率の方が高いですね.

N-gram言語モデルとは

単語数mの単語列が生起する確率

サンプル画像

は同時確率なので、確率の乗法定理より

サンプル画像

というように各単語の条件付き確率の積で表せます.しかし、このように求めるのはmが長くなるにつれ大変になっていきます.そこで、m番目の単語が生起する確率をm-N+1番目からm-1番目の条件付き確率の積で表すのがN-gram言語モデルの特徴です.
具体例(N=2)を挙げると,
「今日は晴れです」という単語列が生起する確率は(<s>,</s>は文頭・文末記号)

サンプル画像

と表せます.

1-gram言語モデルとは

N-gram言語モデルでは一般的に、頻度の低い単語列が入力として与えられると条件付き確率が0になり同時確率も0になってしまう問題(ゼロ頻度問題)があります.
これを避けるために、条件付き確率の条件とする前方の単語数を少なくすることで条件付き確率が0になりにくいようにします.
特に、1-gramモデルでは、その単語の生起確率を条件付き確率とします. サンプル画像

なお、生起確率は

サンプル画像

とします.ここで分子はその単語の頻度、分母は学習データに出て来る全単語の頻度の和です.
具体例を挙げると、

  • 今日は雨
  • 明日は曇り
  • 今日は晴れ

という3つの文が与えられた時、「今日」という単語が出現する確率は
全単語数が9、「今日」の頻度は2なので

サンプル画像

というように計算できます.
それでは早速実装に移りましょうと言いたいところですが、頻度の低い「単語列(単語の並び方)」によるゼロ頻度問題はある程度解決できましたが、頻度の低い「単語」(未知語)によるゼロ頻度問題はまだ残っています.さらに工夫を施すことによりこの問題を解決して行きましょう.

線形補間法とは

未知語によるゼロ頻度問題を解決するための一つの手法です.この他にも加算スムージングや未知語を無視する方法などがありますが、今回はこちらで実装していきたいと思います.
とりあえず、説明するより式を見てもらった方がわかりやすいと思うので、式を先に書きます.

サンプル画像

ここで補間係数は任意の単語が未知語でないような確率を、Nは未知語を含む全語彙数を表しています.
注目してほしい点は、右辺の値が

サンプル画像

で補正してあるので、未知語が来ても確率は0では無くなります.

実装

今回は学習用データを2分割して、一方で補間前の確率を求め、もう一方で対数尤度を最大化することにより補間係数を最適化していきます.

require 'open-uri'
require 'open_uri_redirections'
require 'nokogiri'
require 'natto'
require 'mecab'
require 'pp'
require 'json'

class OneGramModel
  
  N = 1000000
  
  def initialize
    @word_cnt_for_p_ml = {}
    @word_cnt_for_lambda = {}
    @lambda = 0
    get_stop_words
  end
  
  def get_stop_words
    @stop_words = []
    File.foreach('stop_words.txt') do |line|
      @stop_words << line.strip unless line.strip == ''
    end
  end
  
  def countup_word_cnt_for_p_ml(word)
    @word_cnt_for_p_ml[word] = 0 unless @word_cnt_for_p_ml.has_key?(word)
    @word_cnt_for_p_ml[word] += 1
  end
  
  def countup_word_cnt_for_lambda(word)
    @word_cnt_for_lambda[word] = 0 unless @word_cnt_for_lambda.has_key?(word)
    @word_cnt_for_lambda[word] += 1
  end
  
  def in_docs(word)
    if @word_cnt_for_p_ml.has_key?(word)
      @word_cnt_for_p_ml[word]
    else
      0
    end
  end
  
  def get_p_ml(word)
    in_docs(word).to_f/@word_cnt_for_p_ml.values.inject(0){|sum,e| sum += e }.to_f
  end
  
  def filter(surface, feature)
    ['名詞','形容詞','形容動詞'].include?(feature.split(',')[0]) && !@stop_words.include?(surface)
  end
  
  def get_prob(txt)
    log_prob = 0
    nm = Natto::MeCab.new
    nm.enum_parse(txt).each do |n|
      if !n.is_eos? && filter(n.surface, n.feature)
        log_prob += Math.log(@lambda * get_p_ml(n.surface) + (1-@lambda) / N)
      end
    end
    return Math.exp(log_prob)
  end
    
  
  def optimize_lambda
    learning_rate = 1e-6
    before_lambda = after_lambda = 0.84
    epoch = 0
    while true
      grad = 0
      before_lambda = after_lambda
      printf("epoch = %d, lambda = %.5f\n",epoch,after_lambda)
      @word_cnt_for_lambda.each do |word,cnt|
        p_ml = get_p_ml(word)
        grad += cnt * (N * p_ml - 1)/(N * before_lambda * p_ml + 1 - before_lambda)
      end
      after_lambda = grad * learning_rate + before_lambda
      epoch += 1
      if (after_lambda - before_lambda).abs < 1e-4
        @lambda = after_lambda
        return
      end
    end
  end
  
  def save
    File.open("p_ml_wc.json", 'w') do |file|
      JSON.dump(@word_cnt_for_p_ml, file)
    end
    File.open("lambda_wc.json", 'w') do |file|
      JSON.dump(@word_cnt_for_lambda, file)
    end
  end
  
  def load
    @word_cnt_for_p_ml = open('p_ml_wc.json', 'r') do |io|
      JSON.load(io)
    end
    @word_cnt_for_lambda = open('lambda_wc.json', 'r') do |io|
      JSON.load(io)
    end
  end
  
end


url = 'https://www.aozora.gr.jp/cards/000148/files/789_14547.html'
model = OneGramModel.new

puts "1.補間前確率と補間係数最適化用のコーパスを取得"
open(url) do |res|
  charset = res.charset
  html = res.read
  doc = Nokogiri::HTML.parse(html)
  doc.css('.midashi_anchor').remove
  txt = doc.css('.main_text').text
  txt.gsub!(/(.*?)/, '')
  nm = Natto::MeCab.new
  txt.split("\n").each_with_index do |line,idx|
    nm.enum_parse(line).each do |n|
      if !n.is_eos? && model.filter(n.surface, n.feature)
        case idx % 2
        when 0
          model.countup_word_cnt_for_p_ml(n.surface)
        when 1
          model.countup_word_cnt_for_lambda(n.surface)
        end
      end
    end
  end
end

puts "2.コーパスを保存"
model.save

puts "3.コーパスを読込"
model.load

puts "4.補間係数を最適化"
model.optimize_lambda

puts "\n5.テストデータから確率を推定\n"

puts test_text =  "吾輩は猫である"
printf("確率:%.5e\%\n",model.get_prob(test_text)*100)
puts test_text =  "恋は宇宙的な活力である"
printf("確率:%.5e\%\n",model.get_prob(test_text)*100)

puts test_text =  "吾輩は犬である"
printf("確率:%.5e\%\n",model.get_prob(test_text)*100)

結果

4.補間係数を最適化
epoch = 0, lambda = 0.84000
epoch = 1, lambda = 0.83945
epoch = 2, lambda = 0.83900
epoch = 3, lambda = 0.83861
epoch = 4, lambda = 0.83829
epoch = 5, lambda = 0.83802
epoch = 6, lambda = 0.83780
epoch = 7, lambda = 0.83761
epoch = 8, lambda = 0.83745
epoch = 9, lambda = 0.83731
epoch = 10, lambda = 0.83720

5.テストデータから確率を推定
吾輩は猫である
確率:3.94505e-03%
恋は宇宙的な活力である
確率:5.15099e-10%
吾輩は犬である
確率:3.08339e-04%

「吾輩は犬である」より「吾輩は猫である」の方が高いけど、本文中に出て来る「恋は宇宙的な活力である」の確率はあまり高くありませんでした(^◇^;)
頻度が高すぎる・低すぎる単語を削除するなどの前処理が足りないのとそもそも文章中の特徴的な単語列でないのが原因かと思います.

最後に

はじめはベイズ推定の記事を書きたかったのですが、書いていくうちにN-gramを実装して見たくなってしまい、最も簡単な1-gramから実装して見ました.1-gramのように単純ではないですが、2-gram、3-gramも似たような線形補間法で実装できるようなのでぜひやってみたいです!

参考文献・ページ

実装・執筆で大変参考になりました.
[1]自然言語処理プログラミング勉強会 1 – 1-gram 言語モデル
(2018-8-22時点)http://www.phontron.com/slides/nlp-programming-ja-01-unigramlm.pdf
[2]自然言語処理プログラミング勉強会 2 n-gram 言語モデル
(2018-8-22時点)http://www.phontron.com/slides/nlp-programming-ja-02-bigramlm.pdf
[3]Ngram言語モデルメモ – Negative/Positive Thinking
(2018-8-22時点)http://d.hatena.ne.jp/jetbead/20111031/1320078059
[4]ナイーブベイズを用いたテキスト分類 – 人工知能に関する断創録
(2018-8-22時点)http://aidiary.hatenablog.com/entry/20100613/1276389337