糞糞糞ネット弁慶

読んだ論文についてメモを書きます.趣味の話は http://repose.hatenablog.com

IRGAN (SIGIR 2017)→GraphGAN (AAAI 2018)→CFGAN (CIKM 2018) を読んで GAN による購買予測/協調フィルタリングを学ぶ

CFGAN (CIKM 2018) を読もうと思ったら「そもそも発想としては IRGAN (SIGIR 2017) と GraphGAN (AAAI 2018) が先にあって……」と触れられていたので順に読むことにする.
そもそもタイムラインで「CFGAN がはじめて商品推薦に GAN を使っていてすごい」という風潮で取り上げられていて,「2018年まで誰も思いついていないとかまさかそんな馬鹿な話があるわけないだろう」と思ったのがきっかけ.

結論から言うと

  • 商品推薦に GAN を用いるのは CFGAN が初出ではなく IRGAN が初出であり, GraphGAN でも実現している
  • CFGAN は IRGAN/GraphGAN における「真のデータを Generator がサンプリングしてしまうことで Discriminator が混乱して精度悪化を引き起こす」という問題に対して「離散的に点をサンプリングせずに連続なベクトルのサンプリングを行う」という方式を採用することで精度を改善した

この 2 点.

IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models (SIGIR 2017)

[1705.10513] IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models
SIGIR18 IRGAN Tutorial

概要

GAN で IR (Information Retrieval) を行う.IR は query q に対して関連がある document d を得るタスク.
読むまで「どのように Generator で document を生成するのだろうか」と思っていたらそういうわけではない.

  • Generator : query q から document d が生成される確率 p(d|q, r)
    • 真の確率 p_{\textrm{true}}(d|q, r) は学習データで与えられているとする (というより関連のある pair (q, d) が与えられている)
    • p_{\textrm{true}}(d|q, r) を模倣する p_{\theta}(d|q, r) を学習したい
  • Discriminator : query q に document d が関連がある場合に 1 を返すような識別的な関数 D(d|q) を学習したい
    • D(d|q)=\sigma(f_{\phi}(d, q))

の 2 つを用意して

J=\textrm{min}_{\theta} \textrm{max}_{\phi} \sum_{n=1}^N \mathbb{E}_{\sim p_{\textrm{true}}(d|q_n, r)} \log D(d|q_n) + \mathbb{E}_{d \sim p_{\theta}(d|q_n, r)} \log (1 - D(d|q_n))

を学習する.
\textrm{min}_{\theta} \textrm{max}_{\phi} の気持ちは

  • Discriminator は真に関連がある (q_n, d) pair に高いスコアを振り, Generator が提示してくる (q_n, d) pair に対して低いスコアを振るように頑張る
  • Generator は q_n に対してなるべく関連がありそうな d をサンプリングできるように頑張る
    • もう少し丁寧に書くと p_{\theta} (d|q, r)=\frac{\exp(g_{\theta}(q,d)/\tau)}{\sum_{j\in \mathcal{I}} \exp(g_{\theta}(q,d)/\tau)} という感じで g_{\theta} を学習する必要がある
  • Discriminator および Generator は pair (q, d) に対するなんらかの特徴ベクトルを受け取るニューラルネットワークで構築する
    • あとで実験を行いますが特に Generator を linear なモデルにすると予測精度が低いままになってしまう.馬鹿な Generator では Discriminator の役に立たない.

という状態.

学習においては Discriminator は普通に勾配を求める. Generator はサンプリングが関係するので policy gradient based reinforcement learning を使う.

自分の解釈

ナイーブに考えると関連がある pair を正例,関連が無い pair を負例として識別的に Discriminator のみを学習すればいいわけですが, query と document それぞれが非常に大量にあり,かつ,関連がある pair が非常に少ない時,まさか全組み合わせを使って負例を作るわけにはいかないし,そもそも「関連がある」わけではないペアがすべて「関連がない」わけではなく, unobserved だけれども 関連する pair も存在している.なので unlabeled なデータを使って Generator で効率的に識別面に近い負例を生成し, Discriminator の学習を補助している,という解釈でいる.

とはいえ Discriminator を Pre-train するという記述があってどうやって負例を作ったのかがわかっていない.実験の項を見ると関連度順に 0, 1, 2 とつけられたラベルと -1 の「関連度無し」というラベルについて 1 と 2 を関連するラベルとして,それ以外を unlabeled として扱っている.そもそもIRにおいて positive だけがある状態で学習する話がわかってない.情報系の素養が何もない.

実験

実験結果を見ると既存の手法を上回る精度を出している.
また,この枠組みは商品推薦にも使うことができる. IR タスクでは特徴ベクトルが与えられる状態でしたが query/document を user/item と読み替えて特徴ベクトルの代わりにそれぞれの latent vector (論文中では user/item matrix に対する matrix factorization) の内積を用いることで同じように実験ができる. Movielens と Netflix で実験して BPR (pairwise な loss を考えるやつ) を上回る精度を出している.よって少なくとも IRGAN によって GAN を用いた商品推薦が実現していることがわかる.

GraphGAN: Graph Representation Learning with Generative Adversarial Nets (AAAI 2018)

[1711.08267] GraphGAN: Graph Representation Learning with Generative Adversarial Nets
今度はグラフに対して GAN を行う.何を生成するかというと

  • Generator : vertex ( vertex ) v_c から vertex v に対して edge (枝) が存在する確率を返す関数 G(v|v_c; \theta_G)
    • 真の確率 p_{\textrm{true}}(v|v_c) は入力におけるグラフにて vertex ペア (v, v_c) 間に edge が存在しているかで表現されている
    • p_{\textrm{true}}(v|v_c) を模倣する G を学習したい
  • Discriminator : D(v,v_c;\theta_D) は vertex ペア (v, v_c) 間に edge が存在しているかを識別する関数であり,vertex 間に枝があるかを学習させる

といったように

  • Generator は edge がありそうな vertex pair を返す
  • Discriminator は真に edge が存在する vertex pair かどうかを返す

を繰り返す(馬鹿みたいに考えるとグラフを丸暗記すればいいわけですが後述するように vertex の embedding/latent vector内積で表現するのでそういうわけにはいかない).
vertex を query と document として考え, edge を relevant として考えると IRGAN と同じ枠組みであることがわかる.

IRGAN の時と同様に

  • Discriminator D(v, v_c) = \sigma(\mathbf{d}_v^T \mathbf{d}_{v_c}) として \mathbf{d}_v, \mathbf{d}_{v_c} を vertex ごとの k 次元の潜在表現pとして学習
  • Generator G(v|v_c) = \frac{\exp(\mathbf{g}_v^T \mathbf{g}_{v_c})}{\sum_{v \neq v_c} \exp(\mathbf{g}_v^T \mathbf{g}_{v_c})} として \mathbf{g}_v, \mathbf{g}_{v_c} を vertex ごとの k 次元の潜在表現として学習
    • この時,ナイーブに softmax を取るとグラフ構造を活かすことができないのでグラフ構造を反映して v_c から Breadth First Search で tree を作ってそこにおける path を使って確率を構成する graph softmax を導入する (eq 7が追えてないので詳細は後日ちゃんと読む)
    • さらに G からのサンプリングを効率的にするために online sampling strategy を導入する

とする.

実験

実験は link predicton, Node Classification,それと Recommendation をやる.当然 vertex を user と item とみなせば link prediction は recommendation として考えられるため行うことができる.

IRGAN / GraphGAN における素朴な疑問

ここまで IRGAN と GraphGAN を読んできて一点分からないことがある.
Generator は「真にありそうなもの」を提示し, Discriminator はそれを reject しなければならない.もし Generator が「学習データにおいて relevant がある / edge がある」ものを引き当てた場合, Discriminator はそれに対して低いスコアをつけなければならない.
論文中でも「 Generator が真に学習できていたらそれは p_{\textrm{true}} と区別がつかない」と書かれていてそれが理想なのだろうけど,しかし矛盾する事例を引き当てた場合は無視するのだろうか,もしくはそもそも引き当てることが少ないという前提なのだろうか,いう点が引っかかっていた.

CFGAN: A Generic Collaborative Filtering Framework based on Generative Adversarial Networks (CIKM 2018)

CFGAN: A Generic Collaborative Filtering Framework based on Generative Adversarial Networks

モチベーション

IRGAN と GraphGAN によって GAN による推薦が可能になったとはいえ,これらの手法は「要素を 1 つ離散的にサンプリングしてそれの真偽を問う」という手続きを取っているために問題がある.
なぜなら,真の要素を Generator がサンプリングしてしまった時, Discriminator は矛盾するラベル(同じ要素が true でもあり false でもある)を受け取って学習するために混乱してしまうからだ(思い浮かんだ疑問点で回収されて少しうれしい).
実際にこれがどの程度起こっているか実験で確かめる.両モデルで推薦タスクを解いてみると epoch を増やすにつれ Generator と Discriminator の精度は上がるが,ある一定の epoch を超えると突如として Discriminator の精度が異常に悪化し始めることがわかる.同時に, Generator が真のデータをサンプリングしてしまう確率が非常に高くなっていることがわかる.これはすなわち

  • 学習が進むことで Generator が賢くなって真の分布に近づく
  • それによって矛盾したデータを Discriminator が受け取る
  • Discriminator が混乱して精度が下がる
  • Generator に Discriminator からの信号が伝播しなくなり学習が止まる

という状態に陥っていることがわかる.

CFGAN

著者ら曰く, IRGAN/GraphGAN の問題点は Generator が離散的にサンプリングを行うことであるらしい.
そこで CFGAN では

  • Generator はユーザ u ごとに
    • u状態ベクトル \mathbf{c}_u とランダムノイズ \mathbf{z}^2 を入力として,商品数 n の次元を持つ購買ベクトル \hat{\mathbf{r}}_u を生成する
    • その後 u が購買していた商品 i の要素 e_{ui}=1 となるマスクベクトル \mathbf{e}_u と要素積を取る
      • これは既存の購買予測における「購買していた(学習対象の)要素に絞る」という観点と一致する
  • Discriminator は購買ベクトルが真であるか偽であるかを推定する
    • この時,入力には真の購買ベクトル(購買履歴) \mathbf{r}_u または Generator が生成した購買ベクトルをマスクしたもの \hat{\mathbf{r}}_u \odot \mathbf{e}_u とユーザの状態ベクトル \mathbf{c}_u とを連結したものを与える
    • Generator / Discriminator ともに適当なニューラルネットワークで学習する

として Generator を連続的にサンプリングする.
しかし, \mathbf{e}_u でマスクを取るならば全てについて \hat{\mathbf{r}}_{ui} = 1 となるような購買ベクトルを学習するのがもっとも単純な解であるが,それでは商品間の好みの関係が全く学習されない.
そこで,一部の購買していない商品をサンプリングし,それぞれ j について

  • zero-reconstruction regularization : \hat{\mathbf{x}}_u=\textrm{concat}(\hat{\mathbf{r}}_u \odot \mathbf{e}_u, \mathbf{c}_u) として \hat{\mathbf{x}}_{uj} を 0 に近づける項を目的関数に追加して学習させる
  • partial-masking : \mathbf{e}_u でマスクする時に \mathbf{e}_{uj}=1 として購買していない商品についても Discriminator に値を渡すことで学習させる

のという両方の工夫を行う.

実験

実験でSOTAという触れ込みで流れてきたけどこういう比較で SOTA を名乗っていいのかと思うような実験だった.そもそも movielens での現状の SOTA を並べて比較しているサイトがなかったり,皆がそれぞれの基準でデータのフィルタリングを行っているのでまともに比較ができないと思うのですが,140文字未満の論文ツイートだけ読んで論文を理解する人々に言ったところでどうしようもない話だった.
当初の疑問だった「矛盾したラベルはどうなのか」とう話は, CFGAN でも発生はしているがそれでも Discriminator はしっかり見分けていて学習がしっかり見分けている.これはベクトルをサンプリングしているからである(と著者は主張している).多分ですが目的関数を計算する時に矛盾する一点のみではなく矛盾するベクトルかどうかで取り扱っているので後者の方が緩いから,とかそういうことだと思う.

Graph Convolutional Neural Networks for Web-Scale Recommender Systems (KDD 2018) 読んだ

KDD 2018 | Graph Convolutional Neural Networks for Web-Scale Recommender Systems
著者に Jure Keskovec がいる.
Pinterest における推薦にて node の embedding を graph convolution で学習する推薦手法 PinSage を提案している.タイトルだけ読むとそのように思えるけれど,実際には Graph Convolutional Network で行われるような Graph Fourier変換にもとづく畳み込みを行っていない.この点を誤解しているまたはまともに読んでない人しかいないのではないかと思う (footnote 1 で however, the architecture we employ does not directly approximate a spectral graph convolution と言及もしている).

PinSage における Graph Convolution

Convolution

今,次のような関数を考える (論文中ではこの操作を Convolution と呼んでいる).論文中の Algorithm 1 の説明では hz が未定義の状態で登場していて完全に意味不明なので論文の主張に沿って正しいと思われるコードを書く.

# node u に対する畳込みを得る関数
# z_u  : u の現在の畳み込み表現
# z_neighbors : u の近傍ノードの畳み込み表現の集合
# alpha : 近傍ノードの重み
# Q, q : importance_pooling に渡す前のパラメタ
# W, w : 最後の ReLU に渡す前のパラメタ
def covolve(u, z_u, z_neighbors, alpha):
    n_u = importance_pooling(ReLU(Q * z_neighbors + q), alpha)
    z_u_new = ReLU(W * concat(z_u, n_u) + w)
    return normalize(z_u_new)

# vectors を element-wise に weights で重み付けして平均を取る pooling 関数
def importance_pooling(vectors, weights):
    i, j = vectors.shape
    ret = [ ]
    for dim in j:
        ret[dim] = np.mean(vectors[dim, pos] * weights[pos] for pos in range(i))

    return ret

何をやっているかというと,ある node u に対する embedding をその近傍にある node の embedding をまとめて pooling し,現在の embedding と concat した上で ReLU に通している.これを深さ K まで繰り返し適用する (論文中では k 回目の繰り返しにて得られる embedding を h^{(k)} と表現している).思ったよりシンプル.

ここだけ読むとシンプルな話でいいわけですが,論文冒頭では「 node u には visual や texual な feature が付与されている」「この手法ではそれら feature を使って embedding を学習する」と書いてある.しかし上記のコードにはそれら feature に対する言及がない."We start with input node features and then learn neural networks that transform and aggregate features over the graph to compute the node embeddings" と書いてはあるがその後の記述を読むと embedding のことを feature と呼んでいて正直に言って全く理解できない.
id:another16javac さんから「GraphSAGE [1706.02216] Inductive Representation Learning on Large Graphs が参考になる」というコメントをいただき読んだところ h^{0} を特徴量 x で初期化しているのでここで使うという話だった.そしてこの論文もよく読むと algorithm 2 で同様に h^{0}x で初期化していた.恥ずかしい.

細かいテクニック
  • Pixie で行ったように u から始まるランダムウォークによる訪問回数が上位の node を近傍として用いる.また,この時の訪問回数を重み \alpha として用いる. Pixie ではこの時のランダムウォークに用いる遷移行列を node の特徴量を謎の関数に通して重み付けしていたが,まさかこれが上記の疑問に相当する?
  • 学習はクエリ q と正例 i のペア (q, i) が与えられていると考え,負例のペアより正例のペアの embedding の内積が大きくなるように学習する.
  • またこの時,負例は negative sampling するわけですが uniform にやるとほとんど関係ない負例ばかり出てきて関数が収束しない.そこで q に似ているが正例ではない負例 を hard negative item として選ぶ.また,学習の際には epoch ごとに hard negative item を段階的に増やす curriculum training を行う.
  • 学習は MapReduce. d2.8xlarge のインスタンスを 378 台並べてクラスタを作る.

Graph の convolve は分かるけどどうやって特徴量を有効活用したのかわからない.

Sequences of Sets (KDD 2018) 読んだ

KDD 2018 | Sequences of Sets
好きな研究者が何人かいて,タイトルで気になった論文の著者がその人だとちょっとうれしくなる.Cornell University の Jon M. KleinbergGoogle の Ravi KumarStanford の 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 の部分集合すべてについてそれが生成される確率を求めてやればいい,という理解でいる.これ以上はこの論文を再実装したくなった時に読み返す.

Learning and Transferring IDs Representation in E-commerce (KDD 2018) 読んだ

KDD 2018 | Learning and Transferring IDs Representation in E-commerce
EC サイトにおける商品 (item) の埋め込み (embedding) を学習する.その際,商品につけられたメタデータをまとめて学習する.

基本方針

ユーザの商品閲覧行動にもとづいて skip-gram を学習する.すなわち,窓幅を C として

\frac{1}{N}\sum_{n=1}^{N}\sum_{-C \leq j \leq C}^{1 \leq n + j \leq N,\ j \neq 0} \log p(\textrm{item}_{n + j} | \textrm{item}_{n})

を学習する.この時

p(\textrm{item}_{j} | \textrm{item}_{i}) = \frac{\exp ({e^{\prime}_{j}}^{T} e_i)}{\sum_{d}^D \exp ({e^{\prime}_{d}}^{T} e_i)}

である.e^{\prime}\, em 次元の商品の埋め込みとして得られる.

商品と属性の埋め込み

ここで,商品には様々な属性が付与されていることを考える.論文では例として

  • ある「商品」(product,例えば iPhone X) は異なる店 (store) にて異なる商品 (item) として扱われている
  • 「商品」にはブランド (brand) が付与されている
  • 「商品」には階層的なカテゴリ構造 (cate-level1, cate-level2, cate-level3) が付与されている

としている.以降, item ID, product ID, store ID, brand ID, cate-lebel1 ID, cate-lebel2 ID, cate-lebel3 ID の 7 種類を考える (これ以上増やすことも可能).また,これを「属性」と呼ぶことにする.

今, K 種類の属性があり,\textrm{IDs}(\textrm{item}_i) = [\textrm{id}_1(\textrm{item}_i), \cdots, \textrm{id}_K(\textrm{item}_K)] とする.また \textrm{id}_1 を item ID とすると,次の式がこの論文の提案手法.

p(\textrm{IDs}(\textrm{item}_j) | \textrm{IDs}(\textrm{item}_i)) = \sigma (\sum_{k = 1}^K (w_{jk} e^{\prime}_{jk})^T(w_{ik} e_{ik})) \prod_{s=1}^S \sigma (-\sum_{k = 1}^K (w_{sk} e^{\prime}_{sk})^T(w_{ik} e_{ik}))

S は negative sampling における負例集合であり, e_{ik} は 商品i における属性 \textrm{ID} k ごとの埋め込み.属性ごとに埋め込みの次元長  m_k は変わる (この時点では全ての埋め込みは異なるものとして扱う).言ってしまえば,商品ごとの全属性の内積の総和を用いて商品の出現確率を計算する.w_{ik} = \frac{1}{V_{ik}} であり V_{ik}i の属性 k を持つ商品の個数.

更に,商品とその属性との関係も学習する.すなわち

p(\textrm{item}_i | \textrm{IDs}(\textrm{item}_i)) = \sigma (\sum_{k=2}^K w_{ik} e_{i1}^T M_k e_{ik})

とする.ここで M_k は商品 i の長さ m_1 の埋め込み e_{i1} を各属性 k の長さm_k 埋め込みに変換するための行列.ここでようやく商品と属性の埋め込みが同じものとして扱えるようになる.\sum のインデックスが k=2 から始まっているのが重要.

最終的な目的関数は

\frac{1}{N}\sum_{n=1}^{N} ( \sum_{-C \leq j \leq C}^{1 \leq n + j \leq N,\ j \neq 0} \log p(\textrm{item}_{n + j} | \textrm{item}_{n}) + \alpha \log p(\textrm{item}_n | \textrm{IDs}(\textrm{item}_n)) - \beta \sum_{k}^K ||M_k||_2)

とする.[tex\alpha]は商品自身の表現に対する重みのハイパーパラメータ,\betaM_k に対する L2 正則化のハイパーパラメータ.

ユーザの埋め込み

複雑な方法はあるけれど計算が簡単なので直近 T 個の商品の埋め込みの平均をユーザの埋め込みとする.

応用

類似商品の提示

あるユーザが直近で閲覧したいくつかの商品について埋め込みが類似する商品を列挙すればいい.

未知の商品に対する計算

未知の商品 i があるが属性が付与されているときにその商品の埋め込みが計算できる.

p(\textrm{item}_i | \textrm{IDs}(\textrm{item}_i)) = \sigma (\sum_{k=2}^K w_{ik} e_{i1}^T M_k e_{ik})

だったことを思い出すと \sigma は単調増加なので

p(\textrm{item}_i | \textrm{IDs}(\textrm{item}_i)) \propto \sum_{k=2}^K w_{ik} e_{i1}^T M_k e_{ik} = e_{i1}^T(\sum_{k=2}^K w_{ik}  M_k e_{ik})

となる.目的関数が十分に最適化されていれば p(\textrm{item}_i | \textrm{IDs}(\textrm{item}_i)) は 1 と考えられるので式変形をすれば

e_{i1} \approx \sum_{k=2}^K w_{ik} e_{ik}^T M_k^T

で値が得られる.

異なるドメインに対する転移

ここの記述が全く理解できていない.

という手続きが説明されているが,そもそもユーザの埋め込みが共有できるということは商品の体系も共通していなければならない.揃っているならばまとめて学習すればいい(ドメインの違いは属性として特徴量に持たせればいい)のではないか.論文中では Taobao を source , Hema を target としているがそもそも EC サイトとしての性質が大きく異なるのに共通で計算できているという話もよくわからない.
「cold-start なユーザに対する推薦」という話だとしても,クラスタにそのユーザを割り振る際に計算するユーザの埋め込みはどのようにして計算できているのか,という話が理解できない(そこが計算できているならばクラスタに割り振る処理は不要ではないか).

とここまで書いたところで 5.3 にて Since new users have ho historical records に気づくが,やはりどうやって新規ユーザの埋め込みを計算したのかが謎.致命的な何かを読み落としているとしか思えない.

Trajectory-driven Influential Billboard Placement (KDD 2018) 読んだ

KDD 2018 | Trajectory-driven Influential Billboard Placement

街頭広告をどのように選ぶかに取り組む。
問題設定としては

  • 緯度経度で構成される軌跡 (trajectory) t=\{p_1, \cdots, p_{|t|}\} の集合
  • 緯度軽度とコストで構成される街頭広告 (billboard)  b の集合
  • 総予算 L

が与えられ、

  • 軌跡 t のいずれかの点が街頭広告 b の半径 \lambda に入った時、確率 pr(b, t) で影響を受ける (influenced)
  • 街頭広告集合 S に対する軌跡 t への影響を 1-\prod_{b \in S} (1-pr(b, t)) とする

とするときに影響が最大になるように広告を選ぶ問題を解く。
方針としては「実データにおける多くの軌跡は短い領域の中に存在する」という観測にもとづき、同じ軌跡になるべくクラスタが被らないように街頭広告をクラスタリングして解く。

DP の話が出てきたので読むのを止めた。
こういう話結構昔からやられてそうだけど最適化の世界はよくわからない。詳しい人に解説してほしい。 (論文中では半径を考慮しなきゃいけないところが既存手法で対応していないらしい)

Customized Regression Model for Airbnb Dynamic Pricing (KDD 2018) 読んだ

KDD 2018 | Customized Regression Model for Airbnb Dynamic Pricing

民泊サービス Airbnb において, host (部屋を提供する人,ホスト) に対して「この値段で部屋を貸すと良い」と価格を提案する機能を実装するための技術.

  • 予約 (booking) が入るかどうかの予測を行う
  • その上で最適な価格を提示する

という二つの方法を取る.
この論文の貢献は以下の二つ.

  • 価格の決定方法を評価する指標を提案していること
  • その指標にもとづき価格を提示するモデルを学習する方法を考えたこと

なぜ需要の推定が難しいか

「価格を決定する」というのは非常に古典的な問題.一般的には需要関数を求めて面積が最大となるような価格 P を提案する.このとき,需要関数は価格のみの関数 F(P)である.
しかし, Airbnb では需要は価格だけではなく,時刻 t およびその物件を識別する ID id によって決まる F(P, t, id) である.それぞれの要因は次のような要素で構成される.

  • 時刻による違い
    • 季節性やイベントによって需要が異なる
    • 現在時刻と予約を予測したい時刻との差が短ければ短いほど予約されにくい (表示期間が短ければ短いほど予約されにくいという話?)
  • 物件による違い
    • すべての部屋がほぼ同じであるホテルとは異なり, Airbnb にある物件はすべて異なっている (一般的な物件に加え,城やツリーハウス,船がある).これだけでも需要が大きく変わってくる.
    • もし似たような物件に絞ったとしても,レビューが良いほうが需要が高いだろう
    • 近隣物件の需要が高まっているのなら,高評価の物件はより高い価格を提示しても利用率を下げることなく予約が入るだろう.

予約推定モデル

まずは予約されるかどうか推定するモデルを構築する.
特徴量には

  • 物件特徴量 : 物件の価格,部屋の種類,収容人数,ベッドルームやバスルームの数,アメニティ,場所,レビュー,過去の利用率,「今すぐ予約」が可能か,など
  • 時間的特徴量 : 季節性 (何月何日か,何曜日か),予約状況 (チェックインからチェックアウトまでの期間など),予測日から推定対象の日付までの差など
  • 需要・供給のダイナミクス : 近隣の予約可能な物件数,検索者数など

モデルは GBM を使う.ひとつの GBM を推定するのではなく,物件の密度に応じて区画を分け,adaptive sampling を行いながら別々の GBM を学習することで AUC がより良い値になった.

このモデルを需要関数代わりに使うとどうなるか

この予約推定モデルを価格の関数としてみなすことで需要関数として扱うことができる.この関数をそのまま使って収益最大化を A/B テストしてみたが失敗した.
この関数を需要関数としてそのまま使うことには以下の三つの問題があった.

  • データがスパースであること : データにおいて価格は大きく変化していない.たとえば 150 ドルの部屋に対して 50 ドル未満や 500 ドルを設定している人はいない.そのため,平均的な価格のデータばかり集まってしまう.
  • 物件がそれぞれユニークすぎること
  • 特徴量の依存性 : 予約推定モデルにおいて用いた特徴量のうち価格と相関を持つものがあるためうまく働かない.

価格提示モデル

最適な価格と提示価格の関係,オフラインでの評価指標

ここからがこの論文の一番おもしろいところ.
そもそも「最適な (optimal)価格」とは一体どういうことでしょうか.いま手元にあるデータには,「ある価格の物件に予約が入ったかどうか」しかわからず,このデータで学習をしてもただの「現状の価格推定モデル」が得られるだけです.「真に最適な価格」は神様しか知りません.
そこで,真に最適な価格 P_o が存在するとして,実際の価格 P とモデルによって提示する価格 P_{s} との関係を考えると以下のように整理できる.

  • もし物件が予約されて P_s < P だった場合,もしホストがモデルに従っていた場合には P_s - P 分だけ損をすることになる.なのので P_o \geq P でなければならない
  • もし物件が予約されずに P_s \geq P だった場合,もっと安ければより予約される確率が高まっただろう.よって P_o < P でなければならない.
  • もし物件が予約されて P_s \geq P だった場合,もしホストがモデルに従っていた場合 (値上げしていた場合) でも予約が入ったかどうかはわからない
  • もし物件が予約されずに P_s < P だった場合,ホストがモデルに従っていればより予約される確率が高かっただろう.しかし安すぎるとホストが損をしてしまう.

これらの関係を踏まえて,prec-recall の 表のように

  • a :  P_s \geq P かつ予約された
  • b :  P_s \geq P かつ予約されなかった
  • c :  P_s < P かつ予約された
  • d :  P_s < P かつ予約されなかった

として次の 5 つの指標を考える.これらの指標はオフラインでのモデルの評価に用いる.

  • Price Decrease Recall (PDR) : d / (b + d), 予約されなかった中で,安く提案できていた割合
  • Price Decrease Precision (PDP) : d / (c + d), 安く提案できていた中で,予約されなかった割合
  • Price Increase Recall (PIR) : a / (a + c), 予約された中で,高く提案できていた割合
  • Price Increase Precision (PIP) : a / (a + b), 高く提案できていた中で,予約された割合
  • Booking Regret (BR) :  \textrm{max}(0, \frac{P - P_{s}}{P}) の全予約での median

Price Decrease は「より安く提案できていたか」すなわち予約確率をより上げられていたかについて, Price Increase は「より高く提案できていたか」すなわちホストがより収益絵を得られたかについて考えている.
BR は提案によって収益が落ちていたであろう度合いを表している.
検証したところ,これらの指標の中での PDR と BR は実ビジネスでの指標と高い相関を持つことがわかった.特に,PDR は booking gain (予約数?)と相関を持ち,低い BR による価格提案はよりホストの収益を増加させていることがわかる.じゃあ PDR と BR だけを見て最適化すればいいかというとそういうわけにもいかない.なぜなら PDR と BR はトレードオフにあるからだ (安い価格を提案すると PDR は改善するが BR は悪化する).

モデル,目的関数

まず特徴量として

  • ホストによって設定された価格 P_i
  • 予約推定モデルによる確率 q_i
  • 予約推定モデルでは捉えきれなかった市場の需要を示す変数

を入れる.
ここで,目的関数として SVR での \epsilon- insensitive loss (ε許容誤差) のように幅を持たせた新しい損失を提案する.何度も言っているように,「最適な価格」というのを我々は知ることができないけれど,ビジネス的な観点から「最適な価格はこの範囲内に入るだろう」ということはわかるのでそれを損失関数に反映する.
目的関数は次の関数の最小化である.
\textrm{argmax}_{\theta} \sum_i (L(P_i, y_i) - f_{\theta}(x_i))^+ + (f_{\theta}(x_i) - U(P_i, y_i))^+
ここで y_i は i が予約されていたかどうかを示す二値変数, f_{\theta} は推定したいモデル,(x)^+ = \textrm{max}(0, x)
L, U はそれぞれ
L(P_i, y_i) = y_i \cdot P_i + (1 - y_i)\cdot c_1 P_i
U(P_i, y_i) = (1 - y_i) \cdot P_i + y_i\cdot c_2 P_i
とする.このとき  c_1 \in (0, 1),\ c_2 > 1 である定数.
これが何を意味しているかというと,

  • 予約されている時は価格の下限を P_i,上限を  c_2 P_i とし,その範囲内であれば損失を 0
  • 予約されていない時は価格の下限を c_1P_i,上限を  cP_i とし,その範囲内であれば損失を 0

という形の非対称な損失を考える.

需要に基づく価格設定

更に価格提示のためのモデルを考える.以下のような仮説を置く.

  • 同じ物件ならば予約確率と価格には相関がある.よって予約確率で価格を変化させる.
  • 予約予測モデルでは捉えられなかった需要の兆候が容易に反映できるようにする
  • 代表的な価格を中心にしてそこからの増加・減少分を学習する

これを踏まえ次のようなモデルを作る.
P_s = P \cdot V
V = 1 + \theta_{1} (q^{\varphi_{H}^{-qD}} - \theta_2),\ D > 0
V = 1 + \theta_{1} (q^{\varphi_{L}^{-(1-q)D}} - \theta_2),\ D \leq 0
P はホストによって設定された代表的な価格,qは予約確率,D は類似した物件で作ったクラスタにおける追加の特徴量から構築した需要の度合いを正規分布で正規化したもの.
\theta_1 は価格の増減をコントロールするパラメータ,theta_2P=P_s を出す時の微調整パラメータ.\theta_1,\ \theta_2が与えられるとこの関数は q に対して単調増加する.1 < \varphi_L < \varphi_H < 2 は定数.

学習

とはいえこれだけだと値が壊れるので
 l_1 \leq \theta_1 \leq \mu_1
 l_2 \leq \theta_2 \leq \mu_2
となるような制約を加える.
また,需要が乏しい物件には
a\theta_1 + b \leq \theta_2,\ (a > 0)
という制約を加える.
あとは SGD で学習.

PDR の話のあたり,「真の値が存在しない時にどういう数字を作れば改善してるかどうか考えられるか」の話が一番おもしろかった.気力が尽きたのでP_s = SV の話のあたりはよくわかってない (例えば additional な demand signal とは何か,とか).

声優統計コーパスのバランス文を男性が読み上げた音声ファイルが公開されました

声優統計コーパスのパラレルコーパスとして,東京大学猿渡研究室によるJSUT (Japanese speech corpus of Saruwatari-lab., University of Tokyo)がありました.
このたび,nico-opendata 音声読み上げデータセットDwango Media Village によって公開されました.
nico-opendata 音声読み上げデータセットDwango Media Village の男性研究員が声優統計コーパスのバランス文 100 文を読み上げた音声ファイルです.上記ページでは統計的声質変換に関するサーベイも記述されています.声質変換についてわかっていなかったので非常に参考になりました.
また,同研究員が音学シンポジウム2018で発表を行った「畳込みニューラルネットワークを用いた音響特徴量変換とスペクトログラム高精細化による声質変換」について,発表内容,ソースコード,および,統計的声質変換を実際に行ったデモ音声が公開されています.

せっかくなのでこれを機に様々な人々が思い思いの音声コーパスを公開する時代になると面白いと思います.