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 が今回紹介したビームサーチを使った手法。 モデルが同じでも探索手法をビームサーチにすることによって精度が向上した。

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 で学習できる環境を整えたいなぁと思ったりした。

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

前回からの続き。

Chainer を用いて、Attention つきの EncoderDecoder を実装する。

モデルの実装

まずはモデルのコンストラクタ。 前回と同じく、LSTM の実装には NStepLSTM を使った。

class EncoderDecoder(Chain):
    def __init__(self, input_dimension: int, output_dimension: int, hidden_dimension: int):
        super().__init__()
        with super().init_scope():
            self._embed_input = L.EmbedID(input_dimension, hidden_dimension)
            self._embed_output = L.EmbedID(output_dimension, hidden_dimension)

            self._encoder = L.NStepLSTM(
                n_layers=1,
                in_size=hidden_dimension,
                out_size=hidden_dimension,
                dropout=0.1)
            self._decoder = L.NStepLSTM(
                n_layers=1,
                in_size=hidden_dimension,
                out_size=hidden_dimension,
                dropout=0.1)

            # 前回の図で言うところの W_C
            self._context_layer = L.Linear(2 * hidden_dimension, hidden_dimension)

            # 前回の図で言うところの W_D
            self._extract_output = L.Linear(hidden_dimension, output_dimension)

次に順伝播を行うメソッド __call__ は、以下のような実装になった。 前回とほとんど同じだが、self._encoder() の3番目の出力を attentions という名前で保存していること、それを使って self._calculate_attention_layer_output を呼び出しているところが異なっている。

    def __call__(self, xs: List[Variable], ys: List[Variable]) -> Variable:
        batch_size = len(xs)
        xs = [x[::-1] for x in xs]

        eos = np.array([EOS], dtype=np.int32)
        ys_in = [F.concat((eos, y), axis=0) for y in ys]
        ys_out = [F.concat((y, eos), axis=0) for y in ys]

        embedded_xs = [self._embed_input(x) for x in xs]
        embedded_ys = [self._embed_output(y) for y in ys_in]

        hidden_states, cell_states, attentions = \
            self._encoder(None, None, embedded_xs)

        _, _, embedded_outputs = \
            self._decoder(hidden_states, cell_states, embedded_ys)

        loss = 0
        for embedded_output, y, attention in zip(embedded_outputs, ys_out, attentions):
            output = self._calculate_attention_layer_output(embedded_output, attention)
            loss += F.softmax_cross_entropy(output, y)
        loss /= batch_size

        return loss

_calculate_attention_layer_output の実装は以下のようになった。 前回説明した数式をそのまま計算しているだけだが、 T_y個の出力全てをバッチ的に計算しているため、ちょっとややこしい。 (前回の図では文脈ベクトルを計算するところまでしか attention layer に含めていなかったが、この関数は attention なしのモデルとコードを共有する都合上、 W_D の出力まで計算するように実装してある)

    def _calculate_attention_layer_output(
            self, embedded_output: Variable, attention: Variable) -> Variable:
        inner_prod = F.matmul(embedded_output, attention, transb=True)
        weights = F.softmax(inner_prod)
        contexts = F.matmul(weights, attention)
        concatenated = F.concat((contexts, embedded_output))
        new_embedded_output = F.tanh(self._context_layer(concatenated))
        return self._extract_output(new_embedded_output)

学習の実装

学習は素の EncoderDecoder と全く同じコードになった。 愚直にミニバッチを実装するだけ。

def train(dataset: DataSet, n_epoch: int = 20):
    model = EncoderDecoder(
        input_dimension=dataset.ja_vocabulary.size,
        output_dimension=dataset.en_vocabulary.size,
        hidden_dimension=512)

    optimizer = optimizers.Adam()
    optimizer.setup(model)

    batch_size = 128

    for epoch in range(n_epoch):
        shuffled = np.random.permutation(dataset.n_sentences)

        for i in range(0, dataset.n_sentences, batch_size):
            logger.info("Epoch {}: Mini-Batch {}".format(epoch, i))

            indices = shuffled[i:i+batch_size]
            xs = [Variable(dataset.ja_sentences[j]) for j in indices]
            ys = [Variable(dataset.en_sentences[j]) for j in indices]

            model.cleargrads()
            loss = model(xs, ys)
            loss.backward()
            optimizer.update()

        yield model, epoch

翻訳

その1でモデルの実装と学習の部分のみ紹介して、学習したモデルで翻訳するコードを紹介し忘れていたので、ここで紹介する。

単語列 sentence を翻訳するメソッド translate() は以下のように書ける。 _translate_one_word は後で説明する。

class EncoderDecoder(Chain):
    ...

    def translate(self, sentence: np.ndarray, max_length: int = 30) -> 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])

            wid = EOS
            result = []

            for i in range(max_length):
                output, hidden_states, cell_states = \
                    self._translate_one_word(wid, hidden_states, cell_states, attentions)

                wid = np.argmax(output.data)
                if wid == EOS:
                    break
                result.append(wid)

            return result

Encoderは学習時と全く同じ計算を行う。 Deocder は、入力に一個前の Decoder が出力した確率最大の単語を使うところが学習時と異なる。

chainer.using_config('train', False) によって NStepLSTM の dropout を無効にしておかないといけないことに注意。

_translate_one_word の実装は以下の通り:

    def _translate_one_word(self, wid, hidden_states, cell_states, attentions):
        y = np.array([wid], dtype=np.int32)
        embedded_y = self._embed_output(y)
        hidden_states, cell_states, embedded_outputs = \
            self._decoder(hidden_states, cell_states, [embedded_y])

        output = self._calculate_attention_layer_output(embedded_outputs[0], attentions[0])
        output = F.softmax(output)

        return output[0], hidden_states, cell_states

学習時とロジックはほぼ同じ。 学習時は softmax_cross_entropy で loss を計算していたが、翻訳のときは loss を計算するのではなく、softmax をそのまま返す。

実験結果

中間層の次元を512次元として、その1で作成した訓練セット(157,154文)に対して、学習を行った。

8 Epoch 学習させたモデルに対してテストセットの20文を入力してみると以下のようになった。 JAEN がテストセットに入っている例文であり、ED が素の EncoderDecoder モデルの出力、ED+Atn が今回説明した Attention 付き EncoderDecoder の出力である。 モデル名に続く数値は、その文に対する BLEU スコアを表す。

JA    : ----- : 昼食 会 に 1 0 人 を 招待 し た 。
EN    : ----- : We asked ten people to the luncheon .
ED    : 0.000 : A few people to have lunch up the other .
ED+Atn: 0.000 : We invited ten people at the meeting .

JA    : ----- : 彼女 の 言葉づかい に は 誤り が 多い 。
EN    : ----- : Her grammar is bad .
ED    : 0.000 : She has a lot of errors .
ED+Atn: 0.000 : There are many mistakes in her speech .

JA    : ----- : その 文書 に は その 戦い が 1 7 0 0 年 に 起こっ た と 記録 さ れ て いる 。
EN    : ----- : The document records that the war broke out in 1700 .
ED    : 0.000 : The admission is reported by the total disorder in the year round the year .
ED+Atn: 0.000 : The statue was set in a panic in the world about 10 years ago .

JA    : ----- : はるか その 島 が 見え ます 。
EN    : ----- : You can see the island in the distance .
ED    : 1.000 : You can see the island in the distance .
ED+Atn: 0.000 : The island is able to see the island .

JA    : ----- : 昨日 は 一 日 中 英単語 を 暗記 し た 。
EN    : ----- : I learned English words by heart all day yesterday .
ED    : 0.000 : Yesterday the day was forty yesterday .
ED+Atn: 0.000 : I learned English the English words all day .

JA    : ----- : 第 二 の 問題 を 取り上げ ましょ う 。
EN    : ----- : Let 's take up the second problem , shall we ?
ED    : 0.000 : Let 's discuss the problem together .
ED+Atn: 0.000 : Let 's take two second hand .

JA    : ----- : トム は 空港 へ 向かう 途中 だ 。
EN    : ----- : Tom is on his way to the airport .
ED    : 0.597 : Tom is on the way to the airport .
ED+Atn: 0.525 : Tom is the way to the airport .

JA    : ----- : 私 たち は それ を 実行 不可能 と おもっ た こと が ない 。
EN    : ----- : We never thought of it as impossible to carry out .
ED    : 0.000 : We never have never seen a word .
ED+Atn: 0.000 : We 've got to feel nothing but practice .

JA    : ----- : あと で わかっ た こと だ が 、 彼 は 親切 な 男 だっ た 。
EN    : ----- : He was a kind man , as I later discovered .
ED    : 0.000 : I was lucky , but he was kind of man .
ED+Atn: 0.000 : What was he said , he was a kind of man to see a man .

JA    : ----- : 人々 は より 多く の 自由 と 平等 を 求める 。
EN    : ----- : People pursue more freedom and equality .
ED    : 0.000 : People often compare with them one another .
ED+Atn: 0.000 : People equal most more liberty than more .

JA    : ----- : 私 は 決して あなた 失望 さ せ ませ ん 。
EN    : ----- : I 'll never let you down .
ED    : 1.000 : I 'll never let you down .
ED+Atn: 1.000 : I 'll never let you down .

JA    : ----- : 彼 は とっつき やすい 人 だ 。
EN    : ----- : He is a friendly person .
ED    : 0.000 : He is a man of virtue .
ED+Atn: 1.000 : He is a friendly person .

JA    : ----- : その 少女 は 雇主 の 金 を もっ て 逃げ た 。
EN    : ----- : The girl made off with her employer 's money .
ED    : 0.000 : The little girl saved her money .
ED+Atn: 0.000 : The girl ran into a top of the game .

JA    : ----- : 試験 中 は なかなか 大変 だっ た 。
EN    : ----- : It was tough going during the exams .
ED    : 0.000 : I was very hard during the test .
ED+Atn: 0.000 : The test was very pretty .

JA    : ----- : 変 な こと を する から 頭 を 診 て もらい なさい よ 。
EN    : ----- : You should have your head examined .
ED    : 0.000 : Do n't ignore your head down .
ED+Atn: 0.000 : Ask your hair on explaining things .

JA    : ----- : 今月 の 終わり に 私 の 事務所 に 来 なさい 。
EN    : ----- : Come to my office at the end of this month .
ED    : 0.000 : Come to the end of the end of the month .
ED+Atn: 0.588 : Come to my close to the end of this month .

JA    : ----- : あなた 同様 私 は 興奮 など し て い ない 。
EN    : ----- : I am no more excited than you are .
ED    : 0.000 : I am all excited !
ED+Atn: 0.000 : I am not excited any more excitement .

JA    : ----- : 今日 は 独立 記念 日 です 。
EN    : ----- : Today is Independence Day .
ED    : 0.000 : Today is the day of an expert .
ED+Atn: 0.000 : It is a long day , is a lovely day .

JA    : ----- : この 原則 は 子供 に のみ 適用 さ れる 。
EN    : ----- : This general rule refers only to children .
ED    : 0.000 : This classroom is designed to be a large copy of this .
ED+Atn: 0.000 : This rule applies to children .

JA    : ----- : その 事故 は 私 が くる 前 に 起こっ た 。
EN    : ----- : The accident happened previous to my arrival .
ED    : 0.000 : The accident took place before me .
ED+Atn: 0.000 : The accident happened prior to me .

素のモデルよりも訳が改善しているものもあるが、悪化したものもある。 自分の主観的には素のモデルよりも訳が全体的に改善しているように思えた。

また、同じ単語を複数回訳出してしまう傾向が素の EncoderDecoder よりも強まっているように見える。 Luong 2015 にあるように、input feeding を行えばましになるのかもしれない。

定量的評価

テストセットに対する BLEU スコアの平均値を、素の EncoderDecoder と Attention 付き EncoderDecoder それぞれで評価した。 また、それぞれのモデルの Epoch 4, 8, 20 のスコアをそれぞれ求め、比較した。

モデル エポック BLEU
ED 4 0.1143
ED 8 0.1256
ED 20 0.1190
ED+Atn 4 0.1519
ED+Atn 8 0.1578
ED+Atn 20 0.1508

Attention を付け加えることによって、結果がかなり改善していることがわかる。

素の EncoderDecoder のときと同様、Attention付きの EncoderDecoder でも Epoch 20 の時に BLEU が下がっている。 正則化が足りていないのかもしれない。

まとめ

Attention を付け加えることによって EncoderDeocder の精度を向上させることができた。

次回は、翻訳時にビームサーチを行い、精度の向上を目指す。

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

前回 は基本となる EncoderDecoder を紹介した。 この記事では、Attentionと呼ばれるテクニックを紹介する。

Attention

EncoderDecoder では、Encoder から Decoder に渡されるのは、ひとつの固定長ベクトルだけだった。 入力系列がどんなに長かったとしても、Decoderは、この固定長のベクトルのみから出力系列を構築する必要がある。 いくら LSTM の性能がよいとはいえ、このアーキテクチャで長い入力系列を扱うのは無理があるように思える。

この課題に対処するために、Decoder が、入力情報をより直接的に利用する Attention と呼ばれる手法を導入する。 Attention には様々なバリアントが存在するが、ここでは Luong 2015 で提案された、input feeding なしの global attention model を説明する。 (オリジナルの attention よりも実装が簡単なので)

このモデルを図示すると以下のようになる。

f:id:nojima718:20171016224714p:plain

Decoder や Attention Layer を全部書いていると図がカオスになるので、Decoder と Attention Layer に関しては t番目のユニットだけを図示した。

このモデルにおける t番目のDecoderユニットの出力は、以下のように決まる:

 t 番目のユニットの LSTM の出力を  {\bf h}_t とする。 各 i ( i = 1, \ldots, T_x) について、 i 番目の \mathrm{LSTM}_E の出力  {\bf \bar{h}}_i {\bf h}_t から重み  \alpha_i^{(t)} を計算する。

{ \displaystyle
  \alpha_i^{(t)} = \frac{                   \exp( {\bf h}_t, {\bf \bar{h}}_i    ) }
                        { \sum_{i'=1}^{T_x} \exp( {\bf h}_t, {\bf \bar{h}}_{i'} ) }
}

 {\bf \bar{h}_i} \alpha_i^{(t)} を使って、文脈ベクトル  {\bf c}_t を以下の式で定める。

{ \displaystyle
  {\bf c}_t = \sum_{i=1}^{T_x} \alpha_{i}^{(t)} {\bf \bar{h}}_i
}

そして、 {\bf h}_t {\bf c}_t を連結したベクトルに対して、 W_C \tanh W_D \mathrm{softmax} を順に適用したものが Decoder の出力となる。 (隠れユニットの次元を  V_H、出力言語の語彙を  V_D としたとき、 W_C 2 V_H から  V_H へ次元を落とす線形レイヤーであり、 W_D V_H から  V_D へ次元を上げる線形レイヤーである)

実装

hatenablog では、コードフェンスと数式を同じページに書くと、一部の数式の表示がバグることがわかったので、実装の説明は次のページで行う。

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

Chainer による実践深層学習』の8章を読みながら色々試してみた。

EncoderDecoder

EncoderDecoder は、機械翻訳などの、系列が入力され系列が出力されるような問題を扱うモデル。 seq2seq とも呼ばれるらしい。

以下のような好ましい性質を備えている:

  • 入力された系列の長さと、出力する系列の長さが異なっていてもよい
    • 日本語から英語への翻訳を考えると、一般に、日本語の文に含まれる単語数と英語の文に含まれる単語数は異なる。
  • 入力と出力の対応関係が自明じゃなくていい
    • 例えば、日本語と英語では語順が異なるので簡単な対応付けができない。

EncoderDecoder は以下のようなニューラルネットワークになっている。

f:id:nojima718:20171010012354p:plain

緑色の点線で囲われた部分が Encoder で、オレンジ色の点線で囲われた部分が Decoder。

Encoder には入力系列  x_1, \ldots, x_{T_x} を入力する( T_x は入力系列の長さ)。 Encoder に入力された単語は Embed レイヤー (単語IDを受け取る linear layer) を通って LSTM に入力される。 LSTM は一個前の LSTM から来た隠れ状態と現在の単語を受け取って、次の隠れ状態を出力する。

Decoder 側の LSTM は、「次の単語」を出力するように学習する。 Decoder の最初の LSTM は、入力として EOS (を embed したベクトル) と、Encoder から渡された隠れ状態を受け取り、出力系列の最初の単語を出力するように学習する。 次の LSTM はその隠れ状態と出力系列の最初の単語を受け取り、出力系列の2番目の単語を出力するように学習する。 最後の LSTM は EOS を出力するように学習する。 ( W_D は embed された単語ベクトルを元の次元に引き戻すための線形レイヤー)

予測時は、Encoder に入力系列を入れ、Decoder の最初のユニットに EOS を入れると、出力系列の最初の単語が得られる。 この単語を Decoder の2番目のユニットに入れると2番目の単語が得られる。 以下同様に EOS が出力されるまでこれを繰り返すと出力系列全体が得られる。

こんなんで翻訳なんてできるわけないだろ!!と言いたくなるような、冗談みたいな仕組みだが、これである程度翻訳できてしまうので恐ろしい。

データセットの用意

データの入手

日英の対訳データは tatoeba.org から入手した。 tatoeba.org は大量の対訳データが Creative Commons の下で配布されており、とても素晴らしい。 しかも、例文の内容が教科書的で、とても機械学習で使いやすいものになっている。

このサイトの ダウンロード ページから「例文」と「リンク」をダウンロードした。 例文ファイルは、ID, 言語名, 例文が並んだ形式となっており、リンクはリンク元IDとリンク先ID が並んだ形式となっている。 リンクでつながっている例文同士が、互いに対訳関係にある例文だ。

データの整形

機械学習で利用しやすいように、日本語の文と英語の文の対訳ペアのリストをまず作成した。 これにより 196,443 個の対訳ペアが得られた。

次に、文を単語の列に分解した。

日本語の文の分割には MeCab を使った。辞書は素の ipadic を使った。 日本語文の平均単語数は 11.5 単語だった。

英語の文は splitre で雑に分割することもできるが、can't とか U.S. みたいな不規則なクオートやらピリオドやらの扱いが面倒だったので、 OpenNLP の TokenizerME サブコマンドを使った。 TokenizerME に渡すモデルは http://opennlp.sourceforge.net/models-1.5/ にある en-token.bin を使った。 英語文の平均単語数は 9.2 単語だった。

訓練セットとテストセットに分割

データセットの対訳ペアの8割(157,154 個)を訓練セットに割り当てた。 残った2割から訓練用データに含まれる日本語文と同じ日本語文を持つ対訳ペア 5509 個を削除し、残った対訳ペア 33,780 個をテストセットとした。

モデルの実装

Chainer には NStepLSTM という LSTM が連なったようなネットワークを表す Link が用意されているので、以下のように簡単にモデルを記述できる。

class EncoderDecoder(Chain):
    def __init__(self, input_dimension: int, output_dimension: int, hidden_dimension: int):
        super().__init__()

        with super().init_scope():
            self._embed_input = L.EmbedID(input_dimension, hidden_dimension)
            self._embed_output = L.EmbedID(output_dimension, hidden_dimension)

            self._encoder = L.NStepLSTM(
                n_layers=1,
                in_size=hidden_dimension,
                out_size=hidden_dimension,
                dropout=0.1)
            self._decoder = L.NStepLSTM(
                n_layers=1,
                in_size=hidden_dimension,
                out_size=hidden_dimension,
                dropout=0.1)

            # Embed の逆を行う行列を表す良い名前がほしい。
            self._extract_output = L.Linear(hidden_dimension, output_dimension)

    def __call__(self, xs: List[Variable], ys: List[Variable]) -> Variable:
        batch_size = len(xs)
        xs = [x[::-1] for x in xs]

        eos = np.array([EOS], dtype=np.int32)
        ys_in = [F.concat((eos, y), axis=0) for y in ys]
        ys_out = [F.concat((y, eos), axis=0) for y in ys]

        embedded_xs = [self._embed_input(x) for x in xs]
        embedded_ys = [self._embed_output(y) for y in ys_in]

        hidden_states, cell_states, _ = self._encoder(None, None, embedded_xs)
        _, _, embedded_outputs = self._decoder(hidden_states, cell_states, embedded_ys)

        loss = 0
        for embedded_output, y in zip(embedded_outputs, ys_out):
            output = self._extract_output(embedded_output)
            loss += F.softmax_cross_entropy(output, y)
        loss /= batch_size

        return loss

__call__ が上でごちゃごちゃ書いていた学習アルゴリズムの実装。 引数である xs や ys は、ミニバッチのために、単一の Variable じゃなくて List[Variable] を受け取るようになっている。

学習

学習はいつもどおりミニバッチでぐるぐる回すだけ。 DataSet は自分で定義した型で、日英の対訳データと語彙集合をまとめて保持しているオブジェクト。 学習の途中でモデルを保存できるように、1エポック終わるたびにモデルを yield するようにしている。

def train(dataset: DataSet, n_epoch: int = 20):
    model = EncoderDecoder(
        input_dimension=dataset.ja_vocabulary.size,
        output_dimension=dataset.en_vocabulary.size,
        hidden_dimension=512)

    optimizer = optimizers.Adam()
    optimizer.setup(model)

    batch_size = 128

    for epoch in range(n_epoch):
        shuffled = np.random.permutation(dataset.n_sentences)

        for i in range(0, dataset.n_sentences, batch_size):
            logger.info("Epoch {}: Mini-Batch {}".format(epoch, i))

            indices = shuffled[i:i+batch_size]
            xs = [Variable(dataset.ja_sentences[j]) for j in indices]
            ys = [Variable(dataset.en_sentences[j]) for j in indices]

            model.cleargrads()
            loss = model(xs, ys)
            loss.backward()
            optimizer.update()

        yield model, epoch

実験結果

中間層の次元を 512 に設定し、上で作成した訓練セットを使って 20 エポック学習させてみた。 出来上がったモデルにテストセットの例文を20個適当に食わせてみると以下のような出力になった。 (JAEN がテストセットに入っている例文で、Output がモデルの出力)

    JA: 昼食 会 に 1 0 人 を 招待 し た 。
    EN: We asked ten people to the luncheon .
Output: A one invited ten people to the meeting .

    JA: 彼女 の 言葉づかい に は 誤り が 多い 。
    EN: Her grammar is bad .
Output: Her heart 's beating wildly .

    JA: その 文書 に は その 戦い が 1 7 0 0 年 に 起こっ た と 記録 さ れ て いる 。
    EN: The document records that the war broke out in 1700 .
Output: The document was $ with 500 years when the battle was due to the stock .

    JA: はるか その 島 が 見え ます 。
    EN: You can see the island in the distance .
Output: You can see the picture on the island .

    JA: 昨日 は 一 日 中 英単語 を 暗記 し た 。
    EN: I learned English words by heart all day yesterday .
Output: The whole day passed the day off yesterday and broke out .

    JA: 第 二 の 問題 を 取り上げ ましょ う 。
    EN: Let 's take up the second problem , shall we ?
Output: Let 's discuss the problem with two .

    JA: トム は 空港 へ 向かう 途中 だ 。
    EN: Tom is on his way to the airport .
Output: Tom 's going to the airport in a minute .

    JA: 私 たち は それ を 実行 不可能 と おもっ た こと が ない 。
    EN: We never thought of it as impossible to carry out .
Output: We have never thought of it .

    JA: あと で わかっ た こと だ が 、 彼 は 親切 な 男 だっ た 。
    EN: He was a kind man , as I later discovered .
Output: He had been alone , I knew to be a serious man .

    JA: 人々 は より 多く の 自由 と 平等 を 求める 。
    EN: People pursue more freedom and equality .
Output: People deal for freedom as handsome as freedom .

    JA: 私 は 決して あなた 失望 さ せ ませ ん 。
    EN: I 'll never let you down .
Output: I 'll never let you down .

    JA: 彼 は とっつき やすい 人 だ 。
    EN: He is a friendly person .
Output: He is easy to get a big shot .

    JA: その 少女 は 雇主 の 金 を もっ て 逃げ た 。
    EN: The girl made off with her employer 's money .
Output: The little girl had her money for her .

    JA: 試験 中 は なかなか 大変 だっ た 。
    EN: It was tough going during the exams .
Output: I should n't have much grade in the examination .

    JA: 変 な こと を する から 頭 を 診 て もらい なさい よ 。
    EN: You should have your head examined .
Output: Have a hard of mind if you ca n't remember me .

    JA: 今月 の 終わり に 私 の 事務所 に 来 なさい 。
    EN: Come to my office at the end of this month .
Output: You should come to my office on the end of this month .

    JA: あなた 同様 私 は 興奮 など し て い ない 。
    EN: I am no more excited than you are .
Output: I am excited !

    JA: 今日 は 独立 記念 日 です 。
    EN: Today is Independence Day .
Output: It 's no use as a market for the children .

    JA: この 原則 は 子供 に のみ 適用 さ れる 。
    EN: This general rule refers only to children .
Output: This classroom is not at a firm as a child .

    JA: その 事故 は 私 が くる 前 に 起こっ た 。
    EN: The accident happened previous to my arrival .
Output: The accident happened before I arrived .

完璧に訳せている文はそんなに多くはないが、思った以上にちゃんと「英文」になっていて、文法ミスがほどんどない。 EncoderDecoder のアルゴリズムには文法の知識が全く入っていないにも関わらず。

また、たった512次元のベクトルに全情報を突っ込んでいるにも関わらず、元の意味が復元できている場合がそれなりに多い。 直感的には全然うまく行きそうにないモデルなのに、こんな割合で成功しているのが恐ろしい。

機械学習の結果でここまで感動したのは久しぶりだった。

Epoch 20 以外の翻訳結果は Gist に書いた: https://gist.github.com/nojima/186bf4ebf51c6be32d45e6cf9e680c3e

定量的評価

BLEU を使って翻訳結果を評価した。 本当は全エポックのモデルを評価して変化を見たかったんだけど、あまりにも時間がかかるので 4, 8, 20 番目のエポックの結果だけを評価した。

Epoch BLEU
4 0.1143
8 0.1256
20 0.1190

うっすら感じていたんだけど、やっぱり途中から過学習して結果が悪くなってる。 もうちょっと強く正規化したほうがよさそう。

次回予告

Attention を実装したので、それについて書きたい。 また、予測時に greedy に単語を選んでいくのではなくてビームサーチを使って単語を選ぶアルゴリズムを実装したので、それも書きたい。

書いた。

Gmail の優先トレイの論文を読んだ

最近、会社のグループウェアの通知がやたらと多い。 人によっては全ての通知を見ているらしいんだけど、自分の場合は自分宛て通知はみるけど、それ以外の通知は一部しか読んでない。 どうせ一部しか読まないのであれば、できるだけ価値のある通知を読みたいので、通知の中から読む価値の高い上位n件をフィルタしてくれるプログラムを書きたい。

そういうわけで、偉大な先駆者である Gmail の優先トレイのアルゴリズムに関する論文『The Learning Behind Gmail Priority Inbox』を読んでみた。

Gmail 優先トレイ

  • 優先トレイは、ユーザーごとの統計モデルを用いて、メールを重要度でランキングすることにより、information overload を軽減する試みである。
  • チャレンジ:

    • メールの重要度をユーザーの明示的なラベリングなしに推定する
    • 非定常的かつノイジーな訓練データを扱える訓練手法を探す
    • 訓練データの要件を減らすモデルを作る
    • per-user かつテラバイト級のデータを保存・処理する
    • 分散かつ障害耐性を備えた予測プログラムを書く
  • 考え方は Gmail のスパム検出と共通するものが多いが、何を重要と見做すかがユーザーによって大きく異なるため、重要度のランキングはスパム検出よりも困難であり、高度なパーソナライゼーションが要求される。

素性

  • Gmail では数百もの素性を使っているが、それらは少数のカテゴリに分類できる。
  • Social features
    • 送信者と受信者の間のインタラクションの度合いに基づく素性
    • 例: その人が送ったメールのうち、その受信者によって読まれたメールの割合
  • Content features
    • 受信者がそのメールに対して行うアクションに強く相関するヘッダや recent term に基づく素性
    • 例: サブジェクトに含まれるある recent term の割合
    • (recent term に限定しているのは何でなんだろう?)
  • Thread features
    • その時点において、そのユーザーがそのスレッドに対して行ったインタラクションに基づく素性
    • 例: そのユーザーがあるスレッドを始めたか否か
  • Label features
    • ユーザーがメールにフィルタを用いて付与したラベルに基づく素性

重要度

ユーザーとメールが与えられたときに、そのユーザーがそのメールを見てから T 秒以内にアクション(開く、返事を書く、アーカイブする等)を起こす確率を、重要度として用いる。

モデル

  • ロジスティック回帰モデルを用いる。
  • パーソナライズされたユーザーモデルを学習するためのデータは少ないため、グローバルモデルとユーザーモデルの対数オッズの和を使って予測を行う。
  • メールの重要度を表す確率 p を以下の式でモデル化する。
{ \displaystyle
  \begin{align*}
    s &= \sum_{i=1}^n f_i g_i + \sum_{i=1}^{n+k} f_i w_i \\
    p &= \frac{1}{1 + \exp(-s)}
  \end{align*}
}
  • ただし
    •  n はグローバルモデルの素性の数
    •  k はグローバルモデルに存在しない、ユーザーモデル固有の素性の数
    •  \vec{f} は素性ベクトル
    •  \vec{g} はグローバルモデルの重みベクトル
    •  \vec{w} はユーザーモデルの重みベクトル
  • 重みベクトルは、passive-aggressive を使って更新する。
    • 訓練集合に含まれる大量のノイズに耐えるため、PA-II regression variant を用いた。
  • 各メールは、グローバルモデルの更新するために1回利用され、そのメールの受信者のユーザーモデルを更新するためにもう1回利用される。
  • i番目のユーザーモデルの重みは以下の式で更新される。
{ \displaystyle
  \begin{align*}
    w_i^{(t+1)} &= w_i^{(t)} + f_i \frac{\mathrm{sign}(e) \max\{0, |e| - \epsilon\}}{|| \vec{f} ||^2 + \frac{1}{2C}} \\
    e &= \begin{cases}
       1 - p^{(t)} & ユーザーがアクションした場合 \\
       -p^{(t)}    & そうでない場合
    \end{cases}
  \end{align*}
}
  • ( f_i が掛けてあるけど、本当にあってるの?)
  • ただし
    •  C は "aggressiveness" を表すパラメータ
    •  \epsilon は "passiveness" を表すヒンジロスパラメータ
  • ユーザーがそのメールを一定時間内に見なかった場合、重みは更新しない。

その他

大規模な学習を行うテクニックが色々書いてあるが、略。

git の pager を設定する

git grepgit log などのコマンドを実行したとき、デフォルトでは less がページャーとして使われる。 git log の場合はデフォルトの設定で特に困っていないが、git grep で出力が数行しかない場合にページャーが表示されるのはちょっと鬱陶しい。 git --no-pager grep とすればページャーなしで実行できるが、いちいちこのオプションを指定するのは面倒くさい。

これらのコマンドで利用されるページャーgit config で設定できる。 そこで、以下のように設定した。

git config --global core.pager "less -R -F -X"

less の各オプションは以下のような意図で指定した:

  • -R: 色を変更する制御文字をそのまま出力する。
  • -F: ファイル全体が一画面に収まる場合、less を自動的に終了する。
  • -X: less の終了時に画面をクリアしない。

このように設定すると、git grep の結果が一画面に収まる場合はページャーなしの場合と同じように出力され、一画面に収まらない場合は less で結果を見ることができる。

Noise-contrastive estimation の雑なメモ

word2vec のモデルの説明で、以下の尤度関数の最大化を行いたいが、分母にある正規化項の計算が重すぎてこのままでは計算できないという話があった。

{ \displaystyle
    \mathcal{L} = \prod_t \prod_{c \in c_t} p( c \mid w_t ) = \prod_t \prod_{c \in c_t} \frac{\exp( \vec{v}_c \cdot \vec{v}_{w_t} )}{\sum_{w' \in V} \exp( \vec{v}_{w'} \cdot \vec{v}_{w_t} )}
}

word2vec では、この尤度関数を直接最大化するのではなく、正例とノイズとを区別する2クラス分類問題の新たに考え、この問題の誤差関数を最小化することでパラメータを求めていた。 しかし普通に考えると、位置tのコンテキストの条件付き確率分布の尤度最大化と、観測データとノイズの2クラス分類問題は全く別の問題のように見える。

Chainer本では前者の問題を解くのと後者の問題を解くのとは「本質的に同じ」と書いてあった。 これらの本質的に同じとはどういうことなのか疑問に思ったので、negative sampling の元ネタらしい Noise-contrastive estimation の論文を読んでみた。

Noise-contrastive estimation: A new estimation principle for unnormalized statistical models

問題

ベクトル  {\bf x} \in \mathbb{R}^n が未知の確率分布  p_d({\bf x}) に従うとする。 この分布を、パラメータ  \alpha を持つ確率分布  p_m({\bf x}; \alpha) でモデル化し、尤度を最大化することでパラメータ  \alpha を決定することを考える。

確率分布は正規化されていなければならない。 つまり、定義域全体に渡る積分が1にならなければならない。

正規化されていない分布  p^0_m({\bf x}; \alpha) があるとき、正規化制約を満たすためには以下のように  p_m({\bf x}; \alpha) を定義すればよい。

{ \displaystyle
    p_m({\bf x}; \alpha) = \frac{p^0_m({\bf x}; \alpha)}{Z(\alpha)}, \ \ \ Z(\alpha) = \int p^0_m({\bf u}; \alpha) d{\bf u}
}

しかし、 Z(\alpha) が解析的に解けることはめったにないし、(word2vec の場合のように)数値的に計算するのもコストが高すぎて困難である場合が多い。 したがって、 Z(\alpha) を計算することなく、尤度を最大化する  \alpha を求めたい。

Noise-contrastive estimation

 Z(\alpha) を計算するのではなく、新たなモデルパラメータとしてモデルに組み込むことを考える。 つまり  p_m を以下のように再定義する。

{ \displaystyle
    p_m({\bf x}; \alpha, Z) = \frac{p^0_m({\bf x}; \alpha)}{Z}
}

 Z をパラメータにしてしまったので、この分布は  Z の値をうまく決めないと正規化されない。 このため、この分布の尤度を目的関数として最大化を行うことはできない。 なぜなら、 Z を小さくすれば尤度をいくらでも大きくできるからだ。

Noise-contrastive estimation では、観測されたデータである  {\bf x} と、人工的に作ったノイズ  {\bf y} \sim p_n をロジスティック回帰で識別する問題を代わりに考える。

 p_nノイズ分布 と呼ばれる分布であり、サンプリングすることができる分布であれば自由に選んでよいらしい。 ただし、 p_d が非ゼロである点では  p_n も非ゼロであることが望ましい。 さらに言うと、 p_d にできるだけ近い分布を選ぶのがよいらしい。

 X = ({\bf x}_1, \dots, {\bf x}_T)を観測データとし、 Y = ({\bf y}_1, \dots, {\bf y}_T) をノイズ分布  p_n からサンプルしたデータとする。 このとき、NCE において最大化すべき目的関数(ロジスティック回帰の尤度関数)は以下のように与えられる。

{ \displaystyle
    \mathcal{L}(\alpha, Z) = \sum_{t=1}^T \left\{
        \log \left[ h({\bf x}_t; \alpha, Z) \right] +
        \log \left[ 1 - h({\bf y}_t; \alpha, Z) \right]
    \right\}
}

ただし、 h({\bf u}; \alpha, Z) は、  \sigma(v)シグモイド関数として、以下のように書ける関数。

{ \displaystyle
    h({\bf u}; \alpha, Z) = \sigma\left( \log p_m({\bf u}; \alpha, Z) - \log p_n({\bf u}) \right)
}

つまり、 p_m p_n の対数尤度比をシグモイドに突っ込んだのが  h

いろいろ条件を仮定すると、この目的関数を最大化するパラメータを  (\alpha^{*}, Z^{*}) としたとき、 \alpha^{*} は元々の問題の尤度関数を最大化する  \alpha と一致し、 Z p^0_m を正しく正規化する値になる ことが示せるらしい。すごい。

まとめ

ということで、「本質的に同じ」というのは「どっちの問題を解いても同じモデルパラメータが得られる」という意味らしい。 ただし、negative sampling は NCE をベースとしているけど異なる手法なので、negative sampling で本当に同じパラメータが得られるのかはよくわからない。 後で調べたい。