2017-10-05

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$ を以下の式でモデル化する。

ただし
- $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 で。

2017-03-04

Ubuntu 16.04 で pystan を動かす

MCMC サンプラー Stan を Python から呼び出すためのライブラリ pystan を使ってみようとしたら ABI 問題のせいでちょっと嵌ったのでここにメモしておく。

Anaconda3-4.3.0-Linux-x86_64 をインストールした。そして pystan を pip でインストールした。

pip install pystan

この状態で pystan を使ってみたところ、モデルをコンパイルするところで以下のようなエラーが出た。

>>> stanmodel = StanModel(file='model/model5-3.stan')
---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)
<ipython-input-5-4435d7d1dfc2> in <module>()
----> 1 stanmodel = StanModel(file='model/model5-3.stan')
      2 stanmodel

/home/nojima/anaconda3/lib/python3.6/site-packages/pystan/model.py in __init__(self, file, charset, model_name, model_code, stanc_ret, boost_lib, eigen_lib, verbose, obfuscate_model_name, extra_compile_args)
    313                 os.dup2(orig_stderr, sys.stderr.fileno())
    314 
--> 315         self.module = load_module(self.module_name, lib_dir)
    316         self.module_filename = os.path.basename(self.module.__file__)
    317         # once the module is in memory, we no longer need the file on disk

/home/nojima/anaconda3/lib/python3.6/site-packages/pystan/model.py in load_module(module_name, module_path)
     48         pyximport.install()
     49         sys.path.append(module_path)
---> 50         return __import__(module_name)
     51     else:
     52         import imp

ImportError: /tmp/tmppaa8t0sa/stanfit4anon_model_d6577da659c87ba489087107d1a725f1_1731976423115490565.cpython-36m-x86_64-linux-gnu.so: undefined symbol: _ZTVNSt7__cxx1118basic_stringstreamIcSt11char_traitsIcESaIcEEE

これは、最近 libstdc++ の ABI の変更があり、Ubuntu 16.04 デフォルトの gcc に同梱されている libstdc++ は新しい ABI のものだが、Anaconda に同梱されているライブラリは古い ABI を使っており、うまくリンクできないのが理由っぽい。

ということで、Anaconda が利用しているバージョンである gcc-4.8 をインストールする。幸いなことに Ubuntu 16.04 には gcc-4.8 パッケージが存在しているため、それを apt-get するだけでインストールできる。

sudo apt-get install gcc-4.8 g++-4.8

この方法でインストールした gcc は gcc-4.8 という名前で参照できる。gcc コマンドは依然として 5.4 であることに注意。

次に、Cython が gcc-4.8 をコンパイルに使うようにしなければならない。このためには CC 環境変数に gcc-4.8 を指定すればよいらしい。

するとうまくコンパイルできた。

In [1]: from pystan import StanModel

In [2]: import os

In [3]: os.environ['CC'] = 'gcc-4.8'

In [4]: stanmodel = StanModel(file='model/model5-3.stan')
INFO:pystan:COMPILING THE C++ CODE FOR MODEL anon_model_d6577da659c87ba489087107d1a725f1 NOW.

In [5]:

記念にトレースプロットを貼っておく。

f:id:nojima718:20170304173332p:plain