ICFPC 2018 に参加しました

ICFPC 2018 にチーム「銀閣寺GOLD」として参加しました。 メンバーは以下の4人です。

また、チームのリポジトリhttps://github.com/seikichi/icfpc2018 にあります。

問題

今年の問題は小さなロボットたちを操って3Dプリンタ的な作業を行うことです。

R×R×Rの三次元の空間があって、その中に "nanobot" というロボットが配置されています。 ロボットは各ターンに移動したり分裂したり voxel を埋めたりできます。 ロボットをうまく操って、与えられた3Dモデルをプロットしてください。 ただし毎ターン、エネルギーが消費されていきます。 消費されるエネルギーをできるだけ小さくしてください。

プロットしている間、プロット済みの voxel が宙に浮いた状態になってしまってはいけません。 しかし、エネルギーを大量に消費することで High Harmonics 状態 (voxel が宙に浮いてもよい状態) にすることができます。

0日目

去年の ICFPC のブログに「C++ は飽きたので来年は Rust で」って軽い気持ちで書いたら、本当に Rust を使うことになってしまいました。 Rust は The Book を読んで AtCoder の問題を何問か Rust で解いたことがある程度の経験しかありません。 チームのメンバーも大体同じようなレベルでした。 こんな状態で ICFPC ができるのかと結構不安でしたが、当たって砕けろみたいな気持ちで ICFPC に突入しました。

1日目

深夜1時に ICFPC スタート。 問題を読んで役割分担を決めました。 この時点で深夜2時か3時ぐらいだったので就寝。

11時に起床。cosくんとペアプロすることになりました。 まずはトレースファイル(ロボットのコマンド列を並べたバイナリファイル)を出力できるようにライブラリを作り始めました。

このときたぶん初めて Rust でユニットテストを書いたんですが、#[test] でテスト関数を書いて cargo test するだけでテストが動くのに感動しました。 C++ の時代はまず gtest を用意して心のこもった Makefile を書かないとテストできませんでした。

トレースファイルのエンコーダーを作った後はコマンド群の挙動をシミュレートするシミュレータを作ってました。 シミュレータはコマンドを実行して状態を更新したり各ロボットの動きが不正じゃないかをチェックしたりするプログラムです。

シミュレータがチェックすべきものの中に「各 voxel が grounded かどうか」というものがあります。 毎ターンすべての voxel を舐めて grounded かどうかを調べていると滅茶苦茶遅そうなので、grounded 判定は UnionFind で連結成分を管理しておく方針でやることにしました。

「これ、2日目に Full な voxel を Void にできるコマンドが追加されたりしたら崩壊するよね…?」
「ははは、まさかね…」

一方、seikichi-qwerty 班がロボットをグリッド状に分裂させて、それぞれで並列にモデルを構築していく AI を作っていました。 ライトニングにはこれを提出。

↓ GridFissionAI の様子(ライトニング用じゃなくて Full 用なので並列度が違うけど動作はほぼ同じ)

f:id:nojima718:20180730002149g:plain

2日目

Void, GFill, GVoid コマンドが追加されました。 Void は full だった voxel を void にできるコマンドです。 見事にフラグが回収されて絶望が深い。

また、これまではモデルを構築する問題だけでしたが、構築済みのモデルを完全に削除する disassemble 問題と、構築済みのモデルから別のモデルを構築する reassemble 問題が追加されました。

とりあえず、reassemble 問題は disassemble 問題と assemble 問題をそれぞれ解いてくっつけると解けるので、まずはその方針を実装することに。

また、ライトニングに提出した AI は Harmonics が常に High の状態だったので、まずは Harmonics が Low で十分な問題は Low で解けるようにしようということで、

  1. Harmonics を Low のままにして問題を解いていく
  2. シミュレータで voxel が宙に浮いているか調べる
  3. 宙に浮いていたら Harmonics を High にする
  4. プロットしていって再び grounded になったら Harmonics を Low にする

というロジックを入れました(AI班が)。

自分は追加されたコマンドをシミュレータに実装し、崩壊した grounded の判定をナイーブなアルゴリズムで直したりしてました。 しかし、ナイーブな grounded 判定アルゴリズムは遅すぎて大きいサイズの問題が全然終わらないことが判明。 仕方がないので、Void、GVoid が来ない限りは UnionFind で効率的に判定、Void、GVoid が来たら全部再計算という方針にしつつ、典型的な Void では再計算を避けるために以下のヒューリスティックを実装しました。

Void の対象の voxel について、以下が成り立つとき、再計算は不要。

  • その真上が void かつ、
  • その真下が full かつ、
  • その周囲4つの voxel すべてについて「それが void または その真下が full」

3日目

qwerty さんが二次元 GVoid を使ってモデルを disassemble する AI を作ってました。

f:id:nojima718:20180730005450g:plain

また、cos くんが grounded である状態を保つように BFS で良い経路で voxel を埋めていく AI を作ってました。 ロボット同士がぶつからないように移動させるのがすごく大変だったようです。

f:id:nojima718:20180730010417g:plain

また、seikichi くんが grounded を維持しやすいように支柱を立てつつ GridFissionAI っぽいことをし、最後に支柱を消す AI を作ってました。 動きが楽しい。

f:id:nojima718:20180730021147g:plain

自分は GFill を使って assemble していく AI を作ろうとしました。 今回自分はずっとシミュレータをやっていたので、3日目で初めて AI に取り掛かったのですが、予想以上に難しい。 AI を分裂させたり、お互いにぶつからないように移動させたりといった、ぱっと見そんなに難しそうに見えない作業が普通に大変で、かなり手間取りました。 結局、コンテストの時間内に GFill AI を完成させることはできませんでした。

そしていよいよラスト1時間。 AWS で 72 コアマシンを借りて並列で AI をぶん回します。 複数個の AI があるので、すべての AI で各問題を解いて、最もエネルギー消費量が少ない解を提出するようにします。

流石に1時間もあれば余裕で提出できるだろうと思っていましたが、AI の計算が意外と終わらなかったり、途中で VM がディスクフルになって計算をやり直すはめになったりして、結局 zip を提出できたのは終了3分前でした。 めっちゃハラハラした……。

所感

  • Keep

    • Rust は最高でした。
      lifetimeとかでハマるかと思ってたけどそんなことはなく、むしろコンパイラのメッセージが超親切だし cargo が便利だし、実行速度・コンパイル速度共に申し分ありませんでした。 また、4人のメンバーの環境が Windows, WSL, Linux, Mac と見事にバラバラであったにもかかわらず、全くそれを意識することなく開発できました。

    • カンバンは便利でした。
      今年初めて GitHub の project 機能を使ってみました。 毎年三日目ぐらいになると、何をやっていいのかわからない、他の人が何をやっているのかわからない、という状況になっていましたが、今年は状況が把握しやすかったです。

  • Problem & Try

    • AI とシミュレータのインテグレーションがあまり上手くいきませんでした。 本来であれば、シミュレータが実装した関数を AI の実装に再利用できるべきですが、シミュレータのインターフェイスが微妙で AI とシミュレータの間で実装がかなり重複してしまいました。 重複を減らせれば AI をもっといっぱい書けたのではないかと思います。

      もうちょっと早くインテグレーションが上手くできないことに気付いていれば何とか対応できたと思うので、次からは1日目の後半ぐらいには AI とシミュレータをくっつけてみるべきだと感じました。

    • 三日目で、GFill AI に5~6時間ぐらい費やしましたが結局完成しませんでした。もうちょっと早く見限って提出準備の自動化など、インフラ的な作業をやっておくべきでした。

結果

9位だったようです。 初めてのトップ10入りです。嬉しい!

BCC/BPFでシステムコールとかをいい感じにトレースする

この記事は KMC Advent Calendar 2017 の7日目の記事です。 昨日の記事は id:dnek さんの Unityで漢字パズルアプリを作ったよ(Android/iOS) でした。

シンプルだけどこだわって作っている感じがしてすごくよいですね。 (自分の作ったゲームはゲーム性へのこだわりが足りなくて微妙なのしかないので)

さて、今日はインフラ的なレイヤーの話をします。

自由にメトリクスを取りたい!!

パフォーマンスの改善や障害対応を行うために、「fsync のレイテンシの分布が知りたい」「dentry cache のヒット率が知りたい」「IOオペレーションのサイズの分布が知りたい」といった、OS の低レイヤーの情報を集めたくなることがあります。 top, vmstat, sar などのコマンドを使ってメトリクスを得るのが普通ですが、OS が予め用意したメトリクスしか見ることができず、必ずしも知りたい情報が得られるとは限りません。

例えば、dentry cache は /proc/sys/fs/dentry-state を見るとどれぐらい使われているかは分かるんですが、ヒット率が何%ぐらいかは全然わかりません。

こういうときに自分で自由に kernel 内の情報を収集できれば便利です。

そんなあなたに BCC

最近の Linux では kprobes と BPF を使ってカーネル内関数をトレースすることができます。 BCC は、kprobes と BPF を wrap して PythonC言語で便利にトレースプログラムを書けるようにしたものです。

BCC の雰囲気をつかむためには Examples 眺めてみるのがおすすめです。 「そんな情報取れるの!?」ってレベルで色々トレースしています。

例えば、biosnoop はブロックデバイスIOのレイテンシや、そのIOを発生させたプロセスのPIDなどを表示するプログラムです。 動かしてみるとこんな感じになります:

$ sudo /usr/share/bcc/tools/biosnoop
[sudo] password for nojima:
TIME(s)        COMM           PID    DISK    T  SECTOR    BYTES   LAT(ms)
0.000000000    prometheus     33872  sda     W  120713576 12288      0.48
0.002180000    jbd2/sda2-8    362    sda     W  60254856  524288     1.65
0.002844000    jbd2/sda2-8    362    sda     W  60255880  299008     2.31
0.041397000    jbd2/sda2-8    362    sda     W  60256464  4096       0.29
1.804266000    ?              0              R  -1        8          0.15
2.638785000    kworker/u480:1 55782  sda     W  13633792  4096       2.34
2.638831000    kworker/u480:1 55782  sda     W  1050648   8192       2.40
2.638857000    kworker/u480:1 55782  sda     W  1059752   106496     2.42
2.638892000    kworker/u480:1 55782  sda     W  22022984  16384      2.45
2.638914000    kworker/u480:1 55782  sda     W  22022952  4096       2.47
2.638945000    kworker/u480:1 55782  sda     W  22023120  12288      2.49
2.638990000    kworker/u480:1 55782  sda     W  22023160  16384      2.54

prometheus が何か書き込んでいることが見て取れます。

また、ext4distext4 へのオペレーションのレイテンシの分布を出力するプログラムです。 手元のVMで走らせてみると↓のようになりました。 この環境では fsync のレイテンシには2つの山があり、速い方だと 0.1ms~0.5ミリ秒程度、遅い方だと 30ms~130ms 程度だということがわかります。

$ sudo /usr/share/bcc/tools/ext4dist
Tracing ext4 operation latency... Hit Ctrl-C to end.
(中略)
operation = 'fsync'
     usecs               : count     distribution
         0 -> 1          : 1        |                                        |
         2 -> 3          : 0        |                                        |
         4 -> 7          : 0        |                                        |
         8 -> 15         : 0        |                                        |
        16 -> 31         : 0        |                                        |
        32 -> 63         : 0        |                                        |
        64 -> 127        : 0        |                                        |
       128 -> 255        : 177      |*******                                 |
       256 -> 511        : 98       |****                                    |
       512 -> 1023       : 1        |                                        |
      1024 -> 2047       : 1        |                                        |
      2048 -> 4095       : 2        |                                        |
      4096 -> 8191       : 5        |                                        |
      8192 -> 16383      : 3        |                                        |
     16384 -> 32767      : 20       |                                        |
     32768 -> 65535      : 870      |************************************    |
     65536 -> 131071     : 947      |****************************************|
    131072 -> 262143     : 60       |**                                      |
    262144 -> 524287     : 5        |                                        |
    524288 -> 1048575    : 3        |                                        |

他にも色々な例があるので、眺めてみると面白いと思います。

正直、example だけで十分な場合もかなり多いとは思いますが、BCC のメリットは何と言っても自分でカーネルの内部にハンドラをアタッチして自由に情報を取れることです。 この記事では、BCCで簡単なトレーシングプログラムの書き方を紹介します。

インストール方法

公式の INSTALL.md を参照してください。

Hello World in BCC

BPF で sync コマンドを打つたびに Hello, World! と表示するプログラムを書いてみます。 まず、以下の内容で hello.py を作成します。

from bcc import BPF

BPF_PROGRAM = r'''
#include <uapi/linux/ptrace.h>

int kprobe__sys_sync(struct pt_regs *ctx) {
    bpf_trace_printk("Hello, World!\n");
    return 0;
}
'''

bpf = BPF(text=BPF_PROGRAM)
bpf.trace_print()

次に、hello.py を root ユーザーで実行し、別の端末で sync コマンドを打ちます。 すると sync するたびに Hello, World! が出力されることが確認できると思います。 こんな感じ:

$ sudo python hello.py
           <...>-141094 [001] d... 5759646.157609: : Hello, World!
           <...>-141099 [000] d... 5759647.607684: : Hello, World!
           <...>-141104 [001] d... 5759648.419520: : Hello, World!

kprobe__関数名 という名前の関数を定義すると、その名前のカーネル関数にハンドラを仕掛けることができます。 上の例では kprobe__sys_sync という名前の関数を定義しているため、sys_sync が呼ばれる直前にこの関数が kprobe によって呼び出されます。

また、kretprobe__関数名 という名前の関数を定義すると、その関数から戻るタイミングにハンドラを仕掛けることができます。 次の例で使います。

また、Python 側から bpf.attach_kprobe(), bpf.attach_kretprobe() を読んでハンドラを設定する方法もあります。 詳しくはリファレンスを参照してください。

sync の時間を測る

次にもう少し実用的(?)な例を見てみましょう。次のプログラムは sys_sync の時間を計測し、print するものです。

from bcc import BPF

BPF_PROGRAM = r'''
#include <uapi/linux/ptrace.h>

BPF_HASH(start_at, u32, u64);

int kprobe__sys_sync(struct pt_regs *ctx) {
    u32 pid = (u32)bpf_get_current_pid_tgid();

    u64 ts = bpf_ktime_get_ns();
    start_at.update(&pid, &ts);

    return 0;
}

int kretprobe__sys_sync(struct pt_regs *ctx) {
    u32 pid = (u32)bpf_get_current_pid_tgid();

    u64 *p = start_at.lookup(&pid);
    if (!p)
        return 0;
    u64 ts_start = *p;
    u64 ts_end = bpf_ktime_get_ns();
    u64 delta = ts_end - ts_start;

    bpf_trace_printk("sync called: delta=%u\n", delta);

    start_at.delete(&pid);

    return 0;
}
'''

bpf = BPF(text=BPF_PROGRAM)
bpf.trace_print()

実行するとこんな感じになります。(別の端末で sync を打って下さい)

$ sudo python sync.py
           <...>-140474 [000] d... 5757530.462204: : sync called: delta=228816861
           <...>-140479 [000] d... 5757531.890676: : sync called: delta=58180443
           <...>-140484 [000] d... 5757532.781428: : sync called: delta=50627725
           <...>-140489 [000] d... 5757534.292865: : sync called: delta=58540044
  • 実行時間を計測するには、関数が呼ばれたタイミングと戻るタイミングでそれぞれタイムスタンプを取得し、その差を計算する必要があります。 そのため、kprobe__sys_synckretprobe__sys_sync を定義して、両方のタイミングでフックが呼ばれるようにしています。
  • 関数が呼ばれたタイミングで取得したタイムスタンプを戻るタイミングで呼ばれるハンドラに引き渡すためにハッシュ表を使っています。
    • ハッシュ表は BPF_HASH マクロを使って定義します。第一引数が変数名、第二引数が key の型、第三引数が value の型です。
  • bpf_get_current_pid_tgid() は PID と TGID を両方返す関数です。下位32ビットが PID で、上位32ビットが TGID です。
    • ややこしいんですが、ユーザーランドでよく PID と呼ばれている ID はここで言う TGID で、Thread ID と呼ばれているものがここでいう PID です。
  • bpf_ktime_get_ns() は現在のタイムスタンプを返します。

read のレイテンシの分布を出力する

以下のプログラムは2秒毎にファイルへの read のレイテンシの分布を出力します。

from bcc import BPF
import time

BPF_PROGRAM = r'''
#include <uapi/linux/ptrace.h>

BPF_HASH(start_at, u32, u64);
BPF_HISTOGRAM(dist, u32);

int kprobe__generic_file_read_iter(struct pt_regs *ctx) {
    u32 pid = (u32)bpf_get_current_pid_tgid();

    u64 ts = bpf_ktime_get_ns();
    start_at.update(&pid, &ts);

    return 0;
}

int kretprobe__generic_file_read_iter(struct pt_regs *ctx) {
    u32 pid = (u32)bpf_get_current_pid_tgid();

    u64 *p = start_at.lookup(&pid);
    if (!p)
        return 0;
    u64 ts_start = *p;
    u64 ts_end = bpf_ktime_get_ns();
    u64 delta = ts_end - ts_start;

    u32 key = bpf_log2l(delta);
    dist.increment(key);

    start_at.delete(&pid);
    return 0;
}
'''

bpf = BPF(text=BPF_PROGRAM)
while True:
    time.sleep(2)
    table = bpf['dist']
    table.print_log2_hist()
    table.clear()

実行するとこんな感じになります。

$ sudo python read.py
     value               : count     distribution
         0 -> 1          : 0        |                                        |
         2 -> 3          : 0        |                                        |
         4 -> 7          : 0        |                                        |
         8 -> 15         : 0        |                                        |
        16 -> 31         : 0        |                                        |
        32 -> 63         : 0        |                                        |
        64 -> 127        : 0        |                                        |
       128 -> 255        : 0        |                                        |
       256 -> 511        : 0        |                                        |
       512 -> 1023       : 6        |****************************************|
      1024 -> 2047       : 1        |******                                  |
      2048 -> 4095       : 6        |****************************************|
      4096 -> 8191       : 1        |******                                  |
      8192 -> 16383      : 2        |*************                           |
     value               : count     distribution
         0 -> 1          : 0        |                                        |
         2 -> 3          : 0        |                                        |
         4 -> 7          : 0        |                                        |
         8 -> 15         : 0        |                                        |
        16 -> 31         : 0        |                                        |
        32 -> 63         : 0        |                                        |
        64 -> 127        : 0        |                                        |
       128 -> 255        : 0        |                                        |
       256 -> 511        : 0        |                                        |
       512 -> 1023       : 0        |                                        |
      1024 -> 2047       : 0        |                                        |
      2048 -> 4095       : 0        |                                        |
      4096 -> 8191       : 0        |                                        |
      8192 -> 16383      : 1        |****************************************|

BPF_HISTOGRAM(dist, u32); というのがキモで、分布を保存するためのテーブルを作成し、レイテンシをカウントしています。

Python側からは bpf['テーブル名'] でこのテーブルにアクセスできます。 print_log2_hist() は分布をいい感じに print してくれる便利メソッドです。

テーブルには Python のディクショナリみたいにアクセスすることもできます。 例えば、以下の例はテーブルの内容をタブ区切りで一行で出力しています。

# 分布をタブ区切りで出力する
table = bpf['dist']
for k, v in sorted(table.items(), key=lambda x: x[0].value):
    sys.stdout.write("\t" + str(2 ** k.value) + ":" + str(v.value))
sys.stdout.write("\n")

まとめ

BCC で基本的なトレースを行うプログラムを紹介しました。 もっと知りたい人は公式の example を読んだり、reference guide を読みましょう。

さて、KMC Advent Calendar 2017 の次は aokabit さんです!!どんな記事か楽しみですね!!

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

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" を表すヒンジロスパラメータ
  • ユーザーがそのメールを一定時間内に見なかった場合、重みは更新しない。

その他

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