エイエイレトリック

なぐりがき

ngram言語モデルについてまとめる (add-one)

nlp ngram language model

サイコロ本 (統計的自然言語処理の基礎) で確率的言語モデル(ngram言語モデル) のバリエーションについて少し勉強したので、実装して比較してみます。

ngram言語モデル

長さnの単語列 s = w_1, w_2, ..., w_t において以下のように定義される確率 P(s)を推定するモデルのこと。 以下のように定義される。

\displaystyle{ P(s) = \prod_{i=1}^t P(w_i |w_1, ...., w_{i-1}) }

ここで、 P(w_i |w_1, ...., w_{i-1}) は条件付き確率。 1単語目から i-1 単語目までが w_1, ...., w_{i-1} である事象において、i単語目の単語が w_i である確率を指す。

実際はマルコフ性を考慮し、1単語目から i-1 単語目ではなく、後ろn-1単語だけで推定することが多い。

\displaystyle{ P(s) = \prod_{i=1}^t P(w_i |w_1, ...., w_{i-1}) \approx \prod_{i=1}^t P(w_i |w_{i-n+1}, ...., w_{i-1}) }

このnがngramモデルのnにあたる。 n=2 なら bigram model, n=3 なら trigram modelになる。（n=1のときは語順を考慮しない）

数式右辺の P(\cdot)は単語もしくは単語列の出現確率のため、頻度 C(\cdot)に基づいて算出できる。

n=2のときは、

\displaystyle{ P(w _ {i-1},w _ i) = \frac{C(w _ {i-1},w _ i)}{N} }

(Nは学習データの単語数)なので、条件付き確率は以下になる。

\displaystyle{ P(w_i |w_{i-1})= \frac{C(w_{i-1},w_i)}{C(w_{i-1})} }

これがngram言語モデルのベースとなる最尤推定 (Maximam likelihood)モデル。

スムージング

単純な最尤推定だとデータスパースネスを考慮できない。頻度が0 (未知語) の場合、 P(s)も0になってしまう。

考慮する手法が ディスカウント(discounting) , スムージング(smoothing, 平滑化) 。

ディスカウントは低頻度に対して確率を分けるため、それ以外の確率を割引くところから名付けられたらしい。 個人的にはスムージングの方が一般的だと思う。

さまざま提案されているので今回は簡単な手法を試してみる。

1-加算 (add-one)

P(w_i |w_{i-1}) について、分母と分子それぞれに1足す方法。

\displaystyle{ P(w_{i} |w_{i-1})= \frac{C(w_{i-1},w_{i})+ 1 }{C(w_{i-1})+ 1 } }

Lidstoneの法則

1だと大きすぎるのでいい感じの値 \lambda を設定する方法。

\displaystyle{ P(w_{i} |w_{i-1})= \frac{C(w_{i-1},w_{i})+ \lambda }{C(w_{i-1})+ \lambda } }

特にうまくいく \lambda = 1/2 の場合を 期待尤度推定 (expected likehood estimation: ELE) と呼ぶ。 （らしいが、古い手法だからか調べてもあまり参考文献が出てこない。）

実装

google colab 上で動かしてみる。

まとめたnotebookは URL にアップロードしました。

torchtext_ngram.ipynb · GitHub

前処理

データ

のちのちpytorchのモデルと比較したいので、torchtext のデータセットを活用する。

今回は torchtext.datasets.WikiText2 を利用。

元データは The WikiText Long Term Dependency Language Modeling Dataset。

The WikiText language modeling dataset is a collection of over 100 million tokens extracted from the set of verified Good and Featured articles on Wikipedia.

とある通り、Wikipediaデータ。 論文 ([1609.07843] Pointer Sentinel Mixture Models) を読む限り、前処理で出現回数が3回未満のvocabは <unk> に置き換えているようです。

tokenizer

pytorchのtutorial Text classification with the torchtext library — PyTorch Tutorials 1.11.0+cu102 documentation に従って、tokenizerとvocabを設定する。

tokenizer は torchtext のget_tokenizer を使う。spacyを通すこともできるが、シンプルな normalize だけ行う "basic_english" を指定。

tokenizer = get_tokenizer('basic_english')
vocab

build-vocab-from-iterator で語彙設定もしてしまう。

tokenizerで単語ごと分割したデータを渡すことで vocab を設定する。

vocab.set_default_index(vocab['<unk>']) とすれば、 <unk> 以外の未知語も <unk> 扱いにできる。

train_iter = torchtext.datasets.WikiText2(split='train')
vocab = build_vocab_from_iterator(map(tokenizer, train_iter), specials=['<unk>'])

vocab.set_default_index(vocab['<unk>'])

count ngram

前処理が終わったところで、ngramデータを構築する。

簡単な頻度データしか使わないのでpure pythonで実装。unigram と bigramをカウントしていく。

文頭と文末に <bos> と <eos> を設定しカウントする場合もあるが、テキストをそのままカウントする。

train_iter = torchtext.datasets.WikiText2(split='train')

# unigram と bigram を取得する
unigram_counts = defaultdict(int)
bigram_counts = defaultdict(int)

for t in train_iter:
  tokens = text2index(t)
  for t in iter_ngram(tokens, 1):
    unigram_counts[t[0]]  +=1

  for t in iter_ngram(tokens, 2):
    bigram_counts[tuple(t)] +=1

エントロピーを算出

エントロピーを計算。対数尤度を単語数 (N_T) で割った値。

\displaystyle{ H = \frac{1}{N_T}\sum_{i=1} - \log_2 P_{model}(t_i) }

ただし

  • テストデータ T \in (t_0, t_1, ..., t_{l_T})
  • P_{model}(t_i) はデータ t_i に対する model の出力
  • テストデータの合計単語数 N_T

ngram言語モデルは

\displaystyle{ P_{model}(t_i) = \prod P(w_i |w_1, ...., w_{i-1}) }

なので、

\displaystyle{ \log_2 P_{model}(t_i) = \sum \log_2 P(w_i |w_1, ...., w_{i-1}) }

と変形でき、総和の総和でエントロピーを計算できる。

def get_probability(w1, w2, param=0):
  """ P(w_2 | w_1) を求める
  C(w1, w2) + param  / C(w1)  + param
  """
  return  float(bigram_counts.get((w1,w2), 0) + param) / (unigram_counts.get(w1,0) + param)

def get_entropy(lambda_param=0):
  # 単語数 N_T
  word_sum = 0
  # 対数尤度
  h = 0
  test_iter =  torchtext.datasets.WikiText2(split='test')
  for t in test_iter:
      tokens = text2index(t)
      word_sum += len(tokens)
      for i in range(1, len(tokens)-1):
        p = get_probability(
            tokens[i-1], tokens[i], param=lambda_param
            )
        h +=  -math.log2(p)

  print(f"word_sum: {word_sum}\nentropy: {h/word_sum}")

add-one(Laplace) と ELE(Lidstone) で比較してみる。

add-one

>> get_entropy(1)

word_sum: 241859
entropy: 6.399829746902186

ELE

>> get_entropy(1/2)
word_sum: 241859
entropy: 6.646151077249645

微妙な差とはいえ、add-oneよりいい結果になるはずのELEのほうがエントロピーが高くなってしまった。

なぜだろう……。どこかミスしているかもしれない。

カバレッジも計算しようかと思ったが、train データに <unk> があるので厳密には算出できない気がする。

おわりに

今回は簡単なngram言語モデルを実装してみた。

ちなみに深層学習モデルの流行で、言語モデルといえばNLPのイメージがすっかり定着しているが、音声認識 (speech recognition) でも使われていることを久々に思い出した。

他のスムージング手法についても実装してみたいと思います。

参考資料