Item2Vec

embeddingを使って特徴量を生成したいなと思ってたところ、丁度いい論文を見つけたのでメモしておく。
Oren Barkan, Noam Koenigstein (2016). Item2Vec: Neural Item Embedding for Collaborative Filtering

概要

大量の文章から各単語のベクトル表現を獲得するWord2Vecを参考に、推薦システムなどにおけるアイテムのベクトル表現を獲得する。

Skip-gram

まずはWord2VecにおけるSkip-gramについて説明する。 $n$ 個の文が与えられるとして、$i$番目の文の $j$ 番目の単語を $w_{ij}$、文の長さを $L_i$ と書くことにする。また、ある単語の周辺の単語集合をコンテキストと呼ぶことにする。 単語は予め整数値のidに振り直されてるものとする。
Skip-gramとはある単語に注目した時に、その単語のコンテキストを推測するモデルのことを指す。 例えば She sells seashells by the seashore. という文において sell に注目した時、前後の単語である she、 sell を当てるようなタスクを行うことになる。
$w_{ij}$ の前後 $c$ 個の単語からなるコンテキストを $U_{ij}$ と書くことにする。
いま、$i$ 番目の文に注目したときに、コンテキストを当てることは以下の対数尤度を最大化することと等価であることが分かる。

$$ \frac{1}{L_i} \sum_{j=1}^{L_i} \sum_{w' \in U_{ij}} \log P(w' \mid w_{ij}) $$

元々の目標は各単語のベクトル表現を得ることだったので、注目する単語 $w$ に対応するベクトルを $u_{w} \in U \subset \mathbb{R}^{d}$、コンテキストの単語 $w'$ に対応するベクトルを $v_{w'} \in V \subset \mathbb{R}^{d}$ とし、 以下のモデルを採用する。

$$ P(w' \mid w) = \frac{\exp(u_{w}^{\top}v_{w'})}{\sum_{w{''} \in I_{W}}u_{w}^{\top}v_{w{''}}} $$

$I_{W}$ は単語の添字全体からなる集合である。
ここで、ある単語 $w$ のベクトルは、注目する単語として扱われる場合 $u_{w}$、コンテキストとして扱われる場合 $v_{w}$ となることに注意したい。 例えば $u_i$ と $v_i$ を区別しない場合、上の文章では she を表すベクトルと sell のベクトルの内積が $1$ に近づくことを要請することになる。しかし、she と sell は意味的には近いとは言えないので、これでは目的が果たせなそうである。
そもそもこの学習タスクで目指すことは

• she sells seashells.
• she purchases seashells.

という２つの文章があった場合、sell と purchase のコンテキストが同じであることからこの2つは近い意味の単語である、と推論することである。
ある単語 $w$ に注目したとき、 別の単語 $w'$ がコンテキストに現れるかどうかは $u_{w}^{\top} v_{w'}$ の大小で測れば良さそうであるというのがこのモデルの気持ちである。

negative sample

目的関数に現れるソフトマックス関数の分母では単語数 $\left| I_W\right| $ に比例する計算量がかかる。$I_W$ は 10⁵ 程度のオーダになるので、この計算を毎イテレーションを行うのは現実的でない。 そこでSkip-gramではこの分母の計算量を削減するため、上記の条件付き確率を以下の式で代用している。

$$ P(w' \mid w) = \mathrm{sigmoid}(u_{w}^{\top}v_{w'}) \prod_{l=1}^{N} \mathbb{E}_{w{''} \sim P_{n}}\left[ \mathrm{sigmoid}(u_{w}^{\top}v_{w{''}})\right] $$ ここで、$P_{n}(\cdot)$ は単語集合 $I_W$ 上の確率分布、$N$ は定数（論文中では $N=15$）である。

Word2VecからItem2Vecへ

Skip-gramをアイテムのembeddingの学習に適用する。
各ユーザ $i$ が選択/購入したアイテムのリストを $w_{ij}$ とすれば、

文 ↔ ユーザ
単語 ↔ アイテム

といったアナロジーが使えそうなことに気づく。 ここでItem2Vecの際、$w_{ij}$ が時系列順に並んでる訳ではなければコンテキスト $U_{ij}$ は $w_{ij}$ を除くユーザ $i$ が選択したアイテム全体としてもよいことに留意する。実際元論文ではコンテキストをアイテム全体として学習を行っている。

おわり

Item2Vecの説明といいつつほとんどSkip-gramの説明になってしまった。
Word2Vecの学習にはContinuous Bag of WordsとSkip-gramの2つがあるが、性能は後者の方が良いらしい。 Item2Vecのときは $U = V$ としても良い気がするが、論文中では特に言及されていない。