2017-10-10

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

machine_learning unique_ptr

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

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 単語だった。

英語の文は split や re で雑に分割することもできるが、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 は自分で定義した型で、日英の対訳データと語彙集合をまとめて保持しているオブジェクト。学習の途中でモデルを保存できるように、１エポック終わるたびにモデルを 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個適当に食わせてみると以下のような出力になった。 (JA と EN がテストセットに入っている例文で、Output がモデルの出力)

    JA: 昼食 会 に １ ０ 人 を 招待 し た 。
    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: その 文書 に は その 戦い が １ ７ ０ ０ 年 に 起こっ た と 記録 さ れ て いる 。
    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 に単語を選んでいくのではなくてビームサーチを使って単語を選ぶアルゴリズムを実装したので、それも書きたい。

→ 書いた。

2017-10-05

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

machine_learning

最近、会社のグループウェアの通知がやたらと多い。人によっては全ての通知を見ているらしいんだけど、自分の場合は自分宛て通知はみるけど、それ以外の通知は一部しか読んでない。どうせ一部しか読まないのであれば、できるだけ価値のある通知を読みたいので、通知の中から読む価値の高い上位 $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$ を以下の式でモデル化する。

ただし
- $n$ はグローバルモデルの素性の数
- $k$ はグローバルモデルに存在しない、ユーザーモデル固有の素性の数
- $\vec{f}$ は素性ベクトル
- $\vec{g}$ はグローバルモデルの重みベクトル
- $\vec{w}$ はユーザーモデルの重みベクトル
重みベクトルは、passive-aggressive を使って更新する。
- 訓練集合に含まれる大量のノイズに耐えるため、PA-II regression variant を用いた。
各メールは、グローバルモデルの更新するために１回利用され、そのメールの受信者のユーザーモデルを更新するためにもう１回利用される。
$i$ 番目のユーザーモデルの重みは以下の式で更新される。

( $f_i$ が掛けてあるけど、本当にあってるの？)
ただし
- $C$ は "aggressiveness" を表すパラメータ
- $\epsilon$ は "passiveness" を表すヒンジロスパラメータ
ユーザーがそのメールを一定時間内に見なかった場合、重みは更新しない。

その他

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

2017-09-12

git の pager を設定する

git grep や git 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 で結果を見ることができる。

2017-08-24

Noise-contrastive estimation の雑なメモ

machine_learning

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

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

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$ を決定することを考える。

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

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

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

Noise-contrastive estimation

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

$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 において最大化すべき目的関数(ロジスティック回帰の尤度関数)は以下のように与えられる。

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

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

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

まとめ

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

2017-08-22

Word2Vec メモその2

machine_learning chainer word2vec

昨日の記事の続き。

Word2Vec を Chainer で実装していく。完全なコードは以下の URL にある。

workspace/learning-chainer/word2vec at master · nojima/workspace · GitHub

model

誤差関数をネットワークとして表現すると下図のようになる。

f:id:nojima718:20170821234058p:plain

普通のニューラルネットワークと違って活性化関数はない。

$W$ と $W'$ が入力である単語の hot vector を低次元のベクトル表現に変換するための行列で、Chainer 本の図だと $W = W'$ になっている。今回の実験では、 $W$ と $W'$ が同じ行列の場合と違う行列の場合を両方試してみた。

$W = W'$ の方のモデルを Chainer のコードに落とすとこんな感じになる。

class Word2Vec(Chain):
    def __init__(self, n_vocabulary: int, n_units: int) -> None:
        super().__init__()
        with self.init_scope():
            self._embed = L.EmbedID(n_vocabulary, n_units)

    def __call__(self, x1: Variable, x2: Variable, t: Variable) -> Variable:
        output = self.forward(x1, x2)
        return F.sigmoid_cross_entropy(output, t)

    def forward(self, x1: Variable, x2: Variable) -> Variable:
        h1 = self._embed(x1)
        h2 = self._embed(x2)
        return F.sum(h1 * h2, axis=1)

（変数名をこれまでの説明と揃えるべきなんだけど、時間がなくて全然揃えれてないので、すみませんが雰囲気で読み替えてください）

L.EmbedID は one-hot ベクトルに最適化された線形レイヤーで、L.Linear よりも forward も backward も効率的に実装されている。L.EmbedID.__call__ は単語ベクトルじゃなくて単語IDを取ることに注意。

$W$ と $W'$ を異なる行列にする場合は L.EmbedID を２つ用意して使い分ければいい。

train

モデルを学習するためのコードを書いていく。

まずハイパーパラメータを保持しておくための型を定義する。

HyperParameters = namedtuple('HyperParameters', [
    'vocabulary_size',      # 語彙数
    'vector_dimension',     # 分散表現ベクトルの次元
    'window_size',          # ウィンドウの半径
    'n_negative_samples',   # １単語につきネガティブサンプルする単語の数
    'batch_size',           # １回のミニバッチで処理する単語数
    'n_epoch',              # 総エポック数
])

次に negative sampling で使うためのサンプラを作る。

Chainer には WalkerAlias という便利なサンプラがある。 WalkerAlias のコンストラクタに頻度の列を渡すと、その分布に従うサンプラが作れる。

def _make_sampler(dataset: DataSet) -> walker_alias.WalkerAlias:
    _, counts = np.unique(dataset.data, return_counts=True)
    counts = np.power(counts, 0.75)
    return walker_alias.WalkerAlias(counts)

（DataSet は、単語IDの列 data と語彙集合 vocabulary を保持する型）

次に、train 関数を定義する。普通にミニバッチで学習する。ここで出てくる _make_batch_set は訓練データを作る関数で、後で定義する。

def train(dataset: DataSet, params: HyperParameters) -> Word2Vec:

    model = Word2Vec(params.vocabulary_size, params.vector_dimension)

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

    sampler = _make_sampler(dataset)

    batch_size = params.batch_size
    n_epoch = params.n_epoch

    for epoch in range(n_epoch):
        indices = np.random.permutation(dataset.size)

        for i in range(0, dataset.size, batch_size):
            model.cleargrads()

            x1, x2, t = _make_batch_set(
                indices[i:i+batch_size], sampler, dataset, params)
            loss = model(x1, x2, t)
            loss.backward()
            optimizer.update()

    return model

後回しにしていた _make_batch_set の定義はこれ。昨日の記事で説明した方法にしたがって正例と負例を作って返す。

def _make_batch_set(
        indices: np.ndarray,
        sampler: walker_alias.WalkerAlias,
        dataset: DataSet,
        params: HyperParameters) -> Tuple[Variable, Variable, Variable]:

    window_size = params.window_size
    n_negative_samples = params.n_negative_samples

    x1, x2, t = [], [], []

    for index in indices:
        id1 = dataset.data[index]

        for i in range(-window_size, window_size+1):
            p = index + i
            if i == 0 or p < 0 or p >= dataset.size:
                continue
            id2 = dataset.data[p]
            x1.append(id1)
            x2.append(id2)
            t.append(1)
            for nid in sampler.sample(n_negative_samples):
                x1.append(id1)
                x2.append(nid)
                t.append(0)

    return (Variable(np.array(x1, dtype=np.int32)),
            Variable(np.array(x2, dtype=np.int32)),
            Variable(np.array(t,  dtype=np.int32)))

serialize/deserialize

枝葉だけど、モデルの保存と読み込みに結構嵌ったのでここにメモしておく。

モデルの保存は save_npz を使えば簡単にできる。しかし save_npz ではモデルパラメータのみが保存され、語彙数、ベクトルの次元、ウィンドウサイズなどのハイパーパラメータを保存することができない。これらのパラメータも一緒に保存したい場合は serializers.DictionarySerializer を使ってハイパーパラメータを追加でシリアライズすればいい。

def save_model(filename: str, model: Word2Vec, params: HyperParameters) -> None:
    serializer = serializers.DictionarySerializer()

    pickled_params = np.frombuffer(pickle.dumps(params), dtype=np.uint8)
    serializer("hyper_parameters", pickled_params)

    serializer["model"].save(model)

    np.savez_compressed(filename, **serializer.target)

モデルの読み込みも、保存のときと同様、 load_npz で一発でできるが、これだとモデルパラメータしかロードできない。よって、serializers.NpzDeserializer を使ってまずハイパーパラメータを復元し、それを使ってモデルを作り、そのモデルを使ってモデルパラメータを読み込む。

def load_model(filename: str) -> Tuple[Word2Vec, HyperParameters]:
    with np.load(filename) as f:
        deserializer = serializers.NpzDeserializer(f)

        pickled_params = deserializer("hyper_parameters", None)
        params = pickle.loads(pickled_params.tobytes())  # type: HyperParameters

        model = Word2Vec(params.vocabulary_size, params.vector_dimension)
        deserializer["model"].load(model)

        return model, params

実験

Chainer 本で使っていたデータセットである ptb.train.txt を使ってモデルを学習してみた。

ハイパーパラメータがいくつかあるので、以下のすべての組み合わせ(12通り)を使って学習を行った。

モデル: SingleMatrix( $W$ と $W'$ が等しいモデル), DoubleMatrix( $W$ と $W'$ が等しくないモデル)
ベクトルの次元: 50, 100, 200
ウィンドウサイズ: 3, 5

類義語

ベクトルのコサイン類似度を使って"意味"が近い単語をアドホックに調べてみる。（Search はコサイン類似度を使って似ている単語を探してくるヘルパークラス。名前が適当なのでもっといい名前がほしい。）

In [7]: model, params = load_model("./word2vec/results/word2vec_singlematrix_vd200_w5_ns5_bs100_epoch29.npz")

In [8]: s = Search(dataset.vocabulary, model)

In [9]: s.find_similar_words("ibm")
Out[9]: 
['ibm',
 'mainframes',
 'computer',
 'digital',
 'machine',
 'mainframe',
 'machines',
 'armonk',
 'software',
 'chips']

In [10]: s.find_similar_words("monday")
Out[10]: 
['monday',
 'late',
 'friday',
 'tuesday',
 'thursday',
 'wednesday',
 'sell-off',
 'opened',
 'close',
 'points']

In [11]: model, params = load_model("./word2vec/results/word2vec_doublematrix_vd200_w5_ns5_bs100_epoch29.npz")

In [12]: s = Search(dataset.vocabulary, model)

In [13]: s.find_similar_words("ibm")
Out[13]: 
['ibm',
 'digital',
 'mainframe',
 'armonk',
 'customers',
 'computer',
 'machine',
 'machines',
 'hewlett-packard',
 'computers']

In [14]: s.find_similar_words("monday")
Out[14]: 
['monday',
 'friday',
 'tuesday',
 'wednesday',
 'thursday',
 'advancers',
 'october',
 'quoted',
 'week',
 'trading']

一応それっぽい結果になったけど、これを見ただけだと上手く学習できているのかはいまいちわからない。

頻出語のプロット

f:id:nojima718:20170822022555p:plain

頻度が高い300単語のベクトルを t-SNE を使って２次元に落としてプロットした。モデルは SingleMatrix, ベクトル次元200, ウィンドウサイズ5 のものを使った。

ラベルが重なりまくっていてかなり微妙な図だが、よく見ると would, should, might などの助動詞が近くに固まってたり、after-before や up-down、buy-sell などの対義語のペアがいたりしておもしろい。

DoubleMatrix, ベクトル次元200, ウィンドウサイズ5だとこんな図になった。こっちはさらにラベルの重なりが激しくて見づらい。

f:id:nojima718:20170822104836p:plain

国と首都の関係をプロット

各モデルにおいて、国と首都のベクトルがどのように位置しているかを主成分分析を用いて２次元平面にプロットした。国と首都の相対位置がどのペアにおいてもだいたい似たベクトルになることを期待したが、残念ながらあまりそういう傾向は見られなかった。

f:id:nojima718:20170822010708p:plain

loss のプロット

エポックごとに各モデルのロスをプロットした。ロスの計算には ptb.test.txt (訓練に用いていないデータ)を用いた。

上の図がウィンドウサイズが3であるときの図で、下の図がウィンドウサイズが5であるときの図。

f:id:nojima718:20170822011025p:plain

SingleMatrix のモデルでは、ベクトルの次元にかかわらずほぼ同じロスに収束している。 DoubleMatrix のモデルでは、ベクトルの次元が小さいほど小さいロスに収束しているが、SingleMatrix よりもロスが大きい。

つまり、このデータセットにおいては SingleMatrix のほうがよいモデルと考えてよさそう。

学習の過程

国と首都のベクトルの関係が、ひとつのモデルの学習の過程でどのように変化していくかをプロットした。

f:id:nojima718:20170822011729p:plain

ロスのグラフでは epoch 9 ぐらいになると全然ロスが減ってなかったけど、この図だと epoch 12 ぐらいまではわりと変化が見られる。だから何だって言われたら何も言えないけど。

まとめ

Word2Vec を Chainer を使って実装してみた。

実験した範囲では本に書いてあったとおり、 $W = W'$ なモデルが良さそうだった。

Reference

2017-08-21

Word2Vec のメモその1

machine_learning chainer word2vec

Chainer 本を読みながら Word2Vec を Chainer で実装してみたので、その過程でわかったことをメモしておく。

注意: 素人なので完全に間違っているかもしれない。

Word2Vec

Word2Vec の目的は、各単語の 分散表現 を求めること。
- 単語の分散表現とは、単語の意味を低次元(100次元とか)の密な実ベクトルで表したもの。
Word2Vec では、分散表現を求めるために Continuous Bag-of-Words (CBOW) か、skip-gram が利用できる。Chainer 本では skip-gram のみが解説されていたため、この記事でも skip-gram のみを扱う。

skip-gram

skip-gram とは、雑に言うと、「ある単語が与えられたときに、その周囲に現れる単語を予測する」という問題を考え、これを精度よく答えられるように各単語の分散表現ベクトルを学習してくモデル。

入力されたコーパス上の位置 ${ t }$ からオフセット ${ b }$ 以内にある単語群 ${ w_{t-b}, \dots, w_{t-1}, w_{t+1}, \dots, w_{t+b} }$ を位置 ${ t }$ における文脈 ${ c_t }$ と定義する。文脈という言葉を使って上の問題を言い換えると「位置 ${ t }$ にある単語 ${ w_t }$ が与えられたとき、その文脈 ${ c_t }$ を予測する問題」となる。

文脈内の各単語の条件付き独立性を仮定して、 ${ p( c_t \mid w_t ) }$ を以下のようにモデル化する。

図で書くとこんな感じ（ $b=2$ のとき）

f:id:nojima718:20170821012826p:plain

さらに、 ${ p( c \mid w_t ) }$ を、 ${ c, w_t }$ の分散表現 ${ \vec{v}_c, \vec{v}_{w_t} }$ を使って、以下のように分散表現の内積のソフトマックスでモデル化する。（各単語の分散表現はパラメータであり、学習によって求める）

ただし、 $V$ は語彙集合。

……と本には書いてあるんだけど、自分が元論文を読んだ感じでは単語のベクトル表現は２種類 (入力用、出力用) があり、 ${ w_t }$ は入力用のベクトル表現(=分散表現)でベクトル化し、 ${ c }$ は出力用のベクトル表現でベクトル化しているように見えた。つまり、２種類のベクトル表現 ${ \vec{u}, \vec{v} }$ を使って以下のようにモデル化する。

どっちがいいのかよくわからなかったので、両方実装して実験してみたので結果については後述する。

いずれにしても、これで文脈の条件付き確率が定義できたので、コーパスの対数尤度が以下の式で計算できる。

ただし、 $T$ は訓練データのサイズ。

しかし、この尤度は ${ \log \sum_{w' \in V} \exp( \vec{v}_{w'} \cdot \vec{v}_{w_t} ) }$ の項があるため、学習のための計算コストが大きい。元論文では語彙のサイズが70万ぐらいで、分散表現の次元が300であるため、70万×300 = 2億1000万回の演算が一つの入力ごとに必要になる。入力データセットは、元論文の実験では300億単語あり、context size が 5 なので、1500億個の入力があることになる。よって、 $\mathcal{L}$ を計算するには 2億1000万×1500億=3150京回の演算が必要になる。スーパーコンピューターなら計算できるかもしれないけど、普通はこのサイズの計算は無理。

よって、モデルをちょっと変えて、もっと計算しやすいモデルを作る。

次の問題を考える。

「位置 $t$ の単語 $w_t$ と、以下のいずれかの単語 $c$ が与えられる。

正例: 位置 $t$ の文脈 $c_t$ に属する単語
負例: ランダムな単語

このとき、 $c$ が正例なのか負例なのかを判別せよ¹」

つまり、もともとの問題は与えられた単語の近傍の単語の確率分布を求めていたが、新しい問題は近傍の単語とノイズとを区別する２クラス分類問題になっている。

まず、確率変数 $D$ を導入して、答えが正例であるとき $D=1$ とし、負例であるとき $D=0$ とする。

$c$ と $w_t$ が与えられたときの $D$ の確率を以下の式でモデル化する。

ただし、 $\sigma(x)$ はシグモイド関数 ${ 1 / (1 + \exp(-x)) }$ 。

要するに、分散表現の内積が大きい単語同士は近傍に出現しやすいというモデルになっている。（ベクトルを２つ使うモデルだとちょっと違う解釈をしないといけない）

次にパラメータ(=分散表現)の学習のために誤差関数を作る。 Word2Vec ではクロスエントロピー誤差 $H(p, q) = -p \log q - (1-p) \log (1-q)$ を用いる。

訓練データ $(w_t, c, D)$ に対するこのモデルのクロスエントロピー誤差は以下の式で与えられる。

もともとの問題の対数尤度関数 $\mathcal{L}$ と違って語彙集合の上を走る和がないことに注目してほしい。

$E$ の形をよく見ると、ロジスティック回帰の対数尤度関数とほぼ同じ式になっている。なので、この手法は２クラス分類問題をロジスティック回帰を用いて解いていると言ってもいいのかもしれない。 (ロジスティック回帰の定義をよく知らないので間違ってるかも)

あとは訓練データを作れば学習できる。訓練データは後述する ノイズ分布 とハイパーパラメータ $k \in \mathbb{N}$ を用いて以下のように作る。

学習データ内の各位置について
- 位置の文脈内の各単語について
  - 正例 $(w_t, c, D=1)$ を訓練データに加える。
  - ノイズ分布から $k$ 個単語 $c'$ をサンプルし、それぞれの $c'$ に対して負例 $(w_t, c', D=0)$ を訓練データに加える。

ノイズ分布 は負例をサンプリングするための単語の確率分布で、Word2Vec では以下の分布を使うのが実験的によい結果を残しているらしい。

ただし、 $\mathrm{freq}(w)$ は、コーパスにおける単語 $w$ の頻度。

このように負例をサンプリングして学習する手法を negative sampling と呼ぶらしい。

実装と実験

これを Chainer で実装していろいろ実験してみたけど、今日は疲れたので明日の記事で。

Chainer 本の説明では「文脈上の単語 $c$ と (1) $w_t$ または (2) ランダムな単語が与えられて、(1) か (2) かを区別する」問題を解いており、ここで紹介した問題は解いていない。元の論文では、（自分の理解が正しいとすると）この記事で紹介したほうの問題を解いていると思う。↩

2017-08-12

ICFPC 2017 に参加した

C++

ICFPC 2017 にチーム「ゲームセンターYAGI」として参加しました。メンバーは以下の４人です。

リポジトリは https://github.com/seikichi/icfpc2017 です。

今年の問題

無向グラフが与えられます。このグラフの頂点は都市か鉱山のいずれかを表していて、辺は川を表しています。

このゲームの目的は、川の領有権を主張(claim)して、各鉱山をできるだけ多くの都市と(川によって)繋げることです。

各プレイヤーは自分のターンに以下のいずれかの行動を行います。

他人によって claim されていない川をひとつ claim する。
パスして「claimする権利」を１貯める。
溜まっている「claimする権利」を全て消費して、溜まっている権利数+1本の連続する川を claim する。

所定のターン数が経過するとゲームが終了し、各プレイヤーのスコアが以下のルールによって計算されます。スコアが最大であるプレイヤーが勝ちです。

全ての都市 S について、以下を計算して合計する。
- S からそのプレイヤーが claim した辺によって到達可能な各鉱山 M について、以下を計算して合計する。
  - M から S までの距離 (claim した辺以外も利用できるときの距離) の二乗

これ以外にも細かいルールが存在しますが、詳しくは問題文を参照してください。

タイムライン

1日目

21:00 コンテストスタート。コンテストサーバが落ちる。
21:08 問題文を入手する。
21:40 問題文を大体読み終えたので、実装に入る。
- １人がシミュレータを書いて、１人が CI を整備し、残りの２人が AI を書くという分担になった。
23:00 タイムアウト付きの spawn の実装に嵌まる。
- fread(buffer, 1, sizeof(buffer), file) と書くべきところを fread(buffer, sizeof(buffer), 1, file) と書いていたのが原因。悲しい。
00:04 ようやく spawn のテストが通る。ここからシミュレータの実装に入る。
- JSON をパースしたりダンプするのが面倒くさい。心を無視にして実装していく。
- シェルスクリプトで AI を作るとタイムアウトしたときに親プロセスしか殺されず、子プロセスが残る問題を見つける。プロセスグループを使って kill するように spawn を修正する。
03:30 セットアップフェイズまで実装完了。ライブラリの整備も進む。
03:40 寝る。
10:30 起きる。
11:20 シミュレータに GamePlay フェイズを実装。
11:30 昼飯を食べに行く。
15:00 Scoring フェイズを実装。これで一応シミュレータが完成。しかし、シミュレータを作っている間にプロトコルが破壊的に変更されていたので、これに対応しないといけない。
- 今までは入力を一個入れると出力が一個あるようなインターフェイスだったので、普通の spawn のインターフェイスで何とかなったんだけど、新しいインターフェイスでは、ハンドシェイクを先にやる仕様になったのでこれが使えなくなった。
- 破壊的に変更を "small change" って表現するのやめてほしい。
17:00 新しいプロトコルに対応するために spawn とシミュレータを書き直した。
20:00 貪欲AI (毎ターン、合法手の中からスコアが最大になるような手を選ぶ) を書いた。
21:00 貪欲AI に枝刈りを追加して高速化。lightning にはこれを提出した。

2日目

21:30 飯を食べに行く。鯖が美味しかった。
01:00 寝た。
11:00 起きた。寝すぎ。
12:00 昼飯を食べに行く。ラーメン。
14:00 鉱山に近づいていくAIを作った。
- 最も近い鉱山への距離 (他人が claim した辺は通れないとして考える) を最小化する手を選ぶ。
- 何をやっても鉱山に近づけない場合は貪欲AIにフォールバックする。
16:30 タイムアウトしそうになったら弱いAIにフォールバックする仕組みを作った。
- しかしこれはちゃんと動かないことが後になって判明する。
18:00 夕食を食べに行った気がする。

3日目

20:00 初手の選び方を改善した。
- できるだけ強い連結成分を選び、連結成分の中心に近い鉱山を選ぶ、というヒューリスティック。
- 連結成分の強さは、頂点数×鉱山数で表すことにした。
- 「連結成分の中心への近さ」は「その鉱山から他の都市への距離の和」で測ることにした。この和が小さいほど中心性が高い。
23:30 貪欲に次の手を選ぶ際に、到達したときにスコアが最大となる未達都市への距離を最小にするような手を優先するようにした。
- 今までは次の１手のスコアしか考慮していなかったので、将来的に遠くまで行けるパスがあっても軽視されることがあった。
仕事のため、自分の ICFPC ここで終了。

所感

今年は仕事のため月曜日は参加できませんでした。１日少ないとかなり短く感じます。 (普通なら有給休暇を取ればいいんだけど、今年は4週間ぐらい入院したので有給休暇をほとんど使い切ってしまっていたので)

１日目の最初の方はずっと spawn に嵌っていて、２日目もタイムアウトの実装で時間を使ってしまったので、ここらへんをライブラリで済ませられればもっと AI の実装に時間を使えた気がします。シミュレータは別に提出するプログラムじゃないので、もっと手を抜いて実装すべきだったのかも。

AI の出来はいつもどおりっていう感じです。そろそろもっと高度な探索とかをしたいなー。

あと、そろそろ C++ にも飽きてきたら別の言語が使いたい。来年は Rust で。