EncoderDecoder で日英翻訳をしてみた (その4)

前回は Attention 付きの EncoderDecoder モデルを紹介した。

今回は、モデルではなく、予測時のアルゴリズムを変えて精度向上を目指してみる。

前回までの翻訳アルゴリズム

モデルがすでに得られているとする。 前回までは、このモデルを使って、翻訳元の文を以下のように翻訳していた。

  1. 翻訳元の文を reverse する。
  2. 翻訳元の文の各単語を Encoder に入力する。
  3. Decoder に EOS を入力し、翻訳先の文の最初の単語を得る。
  4. Decoder にその単語を入力し、翻訳先の文の2番目の単語を得る。
  5. これを繰り返し、EOS が得られたら終了。得られた単語列を返す。

しかし、Decoder が完璧ならこの方法で完璧な訳文が得られるが、現実には Decoder はそこまで完璧ではない。 途中で最適でない単語が得られてしまう場合もある。 なので、先頭から順に単語を greedy に選んでいくのではなく、文全体として最も尤もらしい単語列になっているものを選びたい。

ビームサーチ

最尤推定を行って訳文を作りたい。

文の単語数の最大値を仮に30とすると、文の候補は、語彙数を V として O(V30) 通りある。 文の候補を全探索して最も尤度が高い文を探すということは計算量的にできない。 そこで、ビームサーチを行う。

ビームサーチは、基本的には幅優先探索と同じく、1ステップ目の候補をまず探索し、次に2ステップ目の候補を探索し、…と探索を進めていく。 ただし、幅優先探索と異なり、各ステップで出現した候補の中から、何らかの基準で上位B個を選び、このB個だけを次のステップで利用する。 この B を ビーム幅 と呼ぶ。

今回の問題において、各候補は (それまでの出力系列, LSTMの隠れ状態) からなる組である。 また、スコアには、負の対数尤度を用いる。 (スコアが小さいほど偉い)

B=3 の場合にこのビームサーチを図示すると以下のようになる。

f:id:nojima718:20171017031604p:plain

実装

実装は以下のようになった。_translate_one_word は前回紹介したメソッドと同じ。

ちゃんとしたヒープじゃなくて普通の list を使っていたり、np.log の計算を一個ずつやっていたりと色々と非効率なのですが、ご容赦ください。

def translate_with_beam_search(
        self, sentence: np.ndarray, max_length: int = 30, beam_width=3) -> List[int]:

    with chainer.no_backprop_mode(), chainer.using_config('train', False):
        sentence = sentence[::-1]

        embedded_xs = self._embed_input(sentence)
        hidden_states, cell_states, attentions = self._encoder(None, None, [embedded_xs])

        heaps = [[] for _ in range(max_length + 1)]
 
       # (score, translation, hidden_states, cell_states)
        heaps[0].append((0, [EOS], hidden_states, cell_states))

        solution = []
        solution_score = 1e8

        for i in range(max_length):
            heaps[i] = sorted(heaps[i], key=lambda t: t[0])[:beam_width]

            for score, translation, i_hidden_states, i_cell_states in heaps[i]:
                wid = translation[-1]
                output, new_hidden_states, new_cell_states = \
                    self._translate_one_word(wid, i_hidden_states, i_cell_states, attentions)

                for next_wid in np.argsort(output.data)[::-1]:
                    if output.data[next_wid] < 1e-6:
                        break
                    next_score = score - np.log(output.data[next_wid])
                    if next_score > solution_score:
                        break
                    next_translation = translation + [next_wid]
                    next_item = (next_score, next_translation, new_hidden_states, new_cell_states)

                    if next_wid == EOS:
                        if next_score < solution_score:
                            solution = translation[1:]  # [1:] drops first EOS
                            solution_score = next_score
                    else:
                        heaps[i + 1].append(next_item)

        return solution

実験結果

Greedy が元々の手法で、Beam が今回紹介したビームサーチを使った手法。 ビーム幅は 3 にした。

モデルが同じでも探索手法をビームサーチにすることによって精度が向上した。

Model Search BLEU
ED Greedy 0.1256
ED Beam 0.1474
ED+Atn Greedy 0.1578
ED+Atn Beam 0.1778

また、これら4つの手法によってテストセットの例文300個を訳した結果を Gist に上げておいた。

https://gist.github.com/nojima/5ff782954d0a63c2ce3a4ceff726e0e0

まとめ

EncoderDecoder を使って日英翻訳を行った。 文法の知識は一切プログラム的には与えていないが、自分の予想よりも遥かによい訳を作れており、とても驚いた。

一方、モデルを学習するのに一週間ぐらいかかった。 そろそろ GPU で学習できる環境を整えたいなぁと思ったりした。