Sequences of Sets (KDD 2018) 読んだ - 糞糞糞ネット弁慶

KDD 2018 | Sequences of Sets
好きな研究者が何人かいて，タイトルで気になった論文の著者がその人だとちょっとうれしくなる．Cornell University の Jon M. Kleinberg や Google の Ravi Kumar ， Stanford の Jure Leskovec は気になって定期的に著者のページを見に行っている．Facebook の Lars Backstrom は久しく論文を書かなくなってしまったので悲しい．
今回の論文は Ravi Kumar が Co-Author に入っている．

集合 (set) の系列 (sequence) についてモデリングする．論文中では

ある人物が送信したメールそれぞれの宛先を時系列でソートしたもの
Stack exchange において投稿された質問に付与されたタグをユーザごとに集めてソートしたもの
センサーから得られた人の接触データ
共著関係

を対象に分析・観察を行い，集合の系列の推定モデル Correlated Repeated Unions (CRU) model を提案している．

データの観察

集合は繰り返す．多くの集合は系列において繰り返し現れるし，全く同じものだけでなく上位集合 (superset) や部分集合 (subset) も現れる
- 系列を前から見ていった時にある集合 (と完全に同じもの | と全く要素がかぶらない集合 | の部分集合 | 上位集合) ががそれより前に現れた比率を見ると集合が繰り返して現れていることがわかる
集合の要素は相関する．二つ組，三つ組の組み合わせは相関を持って現れる
- 全集合から全ての二つ組，三つ組を数え上げるとそれらがランダムに出現する個数より多い
古いものより新しいものに類似した集合が出現する
- ある集合と，それより k 個前に現れた集合との Jaccard 係数の平均を見ると， k を大きくするほど低下する．つまり近ければ近いほど集合間の類似性は高い

CRU モデル

これらを踏まえて集合系列のモデルを提案する．
しかしここまで読むとこのモデル，系列 $S_1,\cdots,S_n$ が観測されている状態で $S_k$ までを用いて $S_{k+1}$ がどのように生成されるかをモデル化している (機械学習的な外挿を行うモデルではなく，物理のように現象を理解するためのモデルのようなニュアンス)．本来想定していたのは $S_n$ までが与えられた状態で $S_{n+1}$ を推定するモデルだったのでちょっと肩透かし．
パラメータとして長さ $n$ であるいくつ前の集合を重視してサンプリングするかの $w$ と集合内からサンプリングを行うための $p$ を持つ．また， $S_{n+1}$ の要素数も (なぜか) わかっているとする．こういう仮定のおかげで将来予測ができない．
CRU モデルの論文の説明を Python のコードで書いた．大雑把な言い方としては

過去の系列をさかのぼってどの集合から要素をサンプリングするかを選ぶ
選んだ集合から要素をサンプリングする
これが一定の大きさになるまで繰り返す

という動きをする．

# S_i の重み付き抽出に必要
from numpy.random import choice

# 長さ k の 集合の系列 S を受け取って次の繰り返し集合 R を出力するモデル
def CRU(r, w, p, S):
    R = set()
    k = len(S)
    while True:
        if len(R) == r:
            return R

        # S_i を重み w_{k + 1 - i} で抽出
        # w は重みなのでサンプリング用の確率に変換する
        p_s = [w[k + 1 - i] for i in range(k + 1)]
        p_s = [x / sum(p_s) for x in p_s]
        S_i = choice(S, p=p_s)

        # S_i から各要素を確率 p でサンプリング
        T = set()
        for s in S_i:
            if random.random() <= p:
                T.add(s)

        # この時の n は系列の「全長」 (未来の分まで含める)
        if len(R | T) > n:
            while len(R) < n:
                # T から一様に要素をサンプリング
                y = choice(T)
                R.add(y)
                T.remove(y)
        else:
            R = R | T

パラメータ推定

推定したいのはいくつ前の集合を重要視してサンプリングするかのパラメータ $w$ (論文冒頭にて要素内からのサンプリングパラメータ $p$ はグリッドサーチしたと言及がある)．尤度の式を作ることができればパラメータの推定はできるはず．しかし集合が生成される尤度とはどういう形でしょうか．僕はすぐには思い浮かばない．
3.2 を真面目に読んでいないけれど，方針としては出力される $R$ の部分集合すべてについてそれが生成される確率を求めてやればいい，という理解でいる．これ以上はこの論文を再実装したくなった時に読み返す．