はじめに

こんにちは、MediaAds ML Teamに所属している飯塚(@zr_4) です。以前書いたブログ*1をベースに変更を加えた論文がRecSys 2019 *2 に通りました(ヤッター)。

埋め込みベースの推薦は、近年最も成功を収めた推薦手法の一つです。埋め込みベースの推薦を行っている多くの大企業では、精度良くアイテムやユーザーを表現するため、数百次元のベクトルを使用しています。それによって、莫大な計算リソースを日々消費していることと思います。またリアルタイムにベクトルの演算を行うために検索システムを自作している企業も少なくないと思います*3。負荷の大きさから、特定のロジックの実装に踏み込めないケースも多々あるかと思います。

一方で近年、埋め込みの空間に双曲空間を用いることで、階層構造、木構造、Directed Acyclic Graph (DAG) が低次元のベクトルで表現できることが明らかになってきました。この技術を用いることで、低負荷かつ高精度な推薦システムが実現できるのではないかと密かに期待を寄せていました。しかし、推薦システムへの適用事例はまだまだ少ないのが現状です。本稿では、双曲空間を用いた推薦システムへの第一歩として、ユークリッド空間でのword2vecを用いた推薦と精度を比較しながらその実用性を検証することを目的とします。

双曲空間とは

双曲空間についての素晴らしい日本語の解説*4 や、最新の研究動向の解説 *5はすでにあるため、ここでは簡単に紹介します。

距離関数

集合 $\mathbb{X}$ を考えます。距離関数 $d$ とは、 $\forall x, y, z \in \mathbb{X}$ に対して以下の3つの性質を満たす関数のことです。

Symmetry: $d(x, y) = d(y, x)$
Separation: $d(x, y) = 0$ if and only if $x = y$
Triangle inequality: $d(x, z) \leq d(x, y) + d(y, z)$

性質

ポアンカレ空間の距離関数は、周縁部に向かうに連れて指数的に距離が大きくなるように設計されています。ここで不意に二分木を考えてみます。二分木は木が深くなるにつれて、そのノード数が指数的に増えていきます。双曲空間では、木のような階層的構造を持つデータに対して相性がよく、効率的な埋め込みが行えます。 *6

双曲空間のモデル

双曲空間のなかにもいくつか有名なモデルがいくつかあります。

モデル	集合	距離関数
Poincare	$\{ x \in \mathbb{R}^n \mid \left\lVert x \right\Vert \lt 1 \}$	$cosh^{-1}(1 + \frac{1}{2} \lambda_x \lambda_y \left\lVert x - y \right\Vert ^2$ )
Lorentz	$\{x \in \mathbb{R}^{n+1} \mid \langle x, x \rangle _{ \mathcal{L} } = -1, x_0 > 0 \}$	$cosh^{-1}(- \langle x, y \rangle _{ \mathcal{L} } )$

where $\lambda_x = \frac{2}{(1-\left\lVert x \right\Vert ^2)}$ and $\langle x, y \rangle _ { \mathcal{L} } = -x_0 y_0 + \sum_{i=1}^n x_i y_i$

実験

概要

双曲空間の埋め込みは様々な種類が提案されています。ここでは近年のブームの火付け役になったポアンカレエンベディング *7 を用います。実装はgensim*8を用いました。実験の順序としては、まずポアンカレエンベディングの学習過程と学習結果の定性評価を行いました。次に、実験に用いたデータセットが、双曲空間での学習に適切なデータセットであるかを事前に評価した結果を示します。最後にユーグリッド空間でのword2vec(skip-gram)との精度の比較を行った結果を示します。

本実験ではユーザーのセッション履歴を用いて、ユーザーが次にアクションを起こすアイテムを予測する Next Event Prediction Task *9 を解きました。例えば、あるユーザーが[item1, item2, ... , itemN-1, itemN] を時系列でアイテムにアクションを起こしていたら、[(item1, item2), (item2, item3), ... , (itemN-1,itemN)]をポアンカレエンベディングの入力とします。

定性評価

グノシーのセッションログをサンプリングし、埋め込みのベクトルを2次元として学習した際の、埋め込み表現の学習過程は以下のようになりました。

f:id:zer4:20190708120426g:plain — poincare_training_visualization

各ノードが各ニュース記事にあたり、各エッジが親子関係を示しています。双曲空間では、円の周囲ほど空間が広がっているため、学習によって周囲に記事が集まっていっていく様子が見て取れます。 gensimの実装では、正則化により周囲にノードが集結しすぎないような工夫がなされているため、ある程度の数のノードが中心付近に残っていることもわかります。ポアンカレエンベディングを実装する際は、このように各ノードを可視化することがデバックに有用だそうです。

次に獲得したアイテムの埋込表現を用いて、グノシーのあるニュース記事に対するニュース記事の類似度が高い上位5記事のタイトルをいくつか並べてみます。権利の関係から記事タイトルから特定のワードを抽出した形式で表にします。

元記事	「ええやん」「するで！」「ワイ」「ほーん」
rank 1	「親不孝者」「www」「ワイ」
rank 2	「飲み会」「俺の」「散々」「会社」「バイト」
rank 3	「リビング」「・・・・」「幽霊」「助けてくれ」
rank 4	「助けてくれ」「結果・・・」「いただきます」
rank 5	「飯を作る」「画像あり」「飯」

2chのまとめ記事に対してはまとめ記事が類似度の上位に来ています。

元記事	「決定」「尊敬」「ミニアルバム」「リリース」「上白石萌音」
rank 1	「ドレス」「宇野実彩子」「シングル」「美」「オフショット」
rank 2	「幸せ」「母の日」「辻希美」「同情」
rank 3	「指原莉乃」「卒業」
rank 4	「丸山穂高」「ヒロミ」「炎上」「悪」
rank 5	「離婚」「鈴木紗理奈」「告白」「喧嘩」

エンタメの記事に対しては、エンタメの記事が類似度の上位に来ています。

元記事	「2020年」「日産」「GT-R」「GT-R」「モデル」「発表」
rank 1	「ヴィッツ」「プリウス」「トヨタ」「新車」
rank 2	「テールランプ」「LED」「メリット」「デメリット」
rank 3	「パサート」「トヨタ」「カムリ」「タイヤ」「パフォーマンス」
rank 4	「スポーツカー」「日産」「GT-R」「次期型」「単独開発」
rank 5	「起業」「飲食」「IT系」

車の記事に関しては、テクノロジー系の記事が上位に来ています。

以上の可視化によって、学習が正しく行えている雰囲気を定性的に確認しました。

定量評価

定量評価では、グノシーのデータセットと30Music *10 のデータセットを用います。

双曲空間での埋め込みは、階層構造を持つデータに対して効率よく埋め込めるという性質が有りました。しかし、上記の定性評価に用いたデータは単なるセッションデータであるため、明示的な階層構造がなく、また特別な前処理は行っていません。それにもかかわらず、なぜ学習が行えているかを説明するために、グノシーのセッションデータをグラフとみなした際のノードごとの次数を可視化します。横軸が、グラフの次数で、縦軸がその次数を持つノードの数です。

f:id:zer4:20190708135455p:plain — gunosyの次数分布

f:id:zer4:20190708135513p:plain — 30Musicの次数分布

このグラフは次数がべき分布に従っているように見えます。このようなグラフは、スケールフリー性を持つグラフです。スケールフリー性を満たすグラフはいたるところに存在しています。例えば今回のように、アイテム間の人気に偏りがあるケースです。スケールフリー性を満たすグラフは、実は階層構造をもつグラフと同様の性質を持っています*11。そのため、今回のデータセットが双曲空間での学習に適したデータセットであったといえます（より正確には、cluster coefficientに対する線形フィッティングを調べると良さそうです）。

次に、ユークリッド空間でのword2vec(skip gram negative sampling: 以下SGNS)との精度の比較を行います。 SGNSでは、セッションデータ[item1, item2, ... , itemN-1, itemN]をそのまま入力し、window sizeに応じて学習させます。 SGNSは、ハイパパラメータにwindow size, negative sample数, size(次元数)があります。評価の指標はHitRate@10を用いました。 window size = [3, 5, 7, 100], negative sample=[5, 10, 20] としてgrid searchしてHR@10が最も高いものを以下の表に示します。sizeは次元数です。baselineは人気順に10個アイテムを返すものとしました。

グノシー

HR@10	size=5	size=50	size=100
baseline	0.11399	0.11399	0.11399
SGNS (w, n)	0.17344 (3, 10)	0.20192 (100, 20)	0.17965 (100, 20)
poincare (n)	0.23164 (20)	0.24646 (20)	0.24430 (20)

30Music

HR@10	size=5	size=50	size=100
baseline	0.00112	0.00112	0.00112
SGNS (w, n)	0.01981 (5, 20)	0.02427 (3, 20)	0.02430 (3, 5)
poincare (n)	0.08082 (20)	0.09453 (20)	0.09552 (10)

考察

両データセットについて、ポアンカレエンベディングはSGNSよりも精度が上回っていることが分かります。特にポアンカレエンベディングの5次元の学習結果が、SGNSの50次元100次元の結果よりも精度が良い結果が得られています。これは、平坦なユークリッド空間での学習に対して、双曲空間では人気の階層を考慮した学習が行えているのが理由ではないかと思います。

実運用に向けて

パーソナライズ

今回の実験では、各アイテムを入力に用いましたがユーザーとアイテムのペアを入力にすることで、ユーザーのベクトルも獲得できます *12。例えば、user1のアクション[item1, item2, ..., itemN]に対しては[(user1, item1),(user1, item2), ..., (user1, itemN)]を入力にすることでuser1のベクトルが得られます。

モデル更新

実運用する際は、モデルの更新が必要になるかと思いますが、gensimではversion 3.8.0以降で以下のようにモデルの差分更新が行えます。

from gensim.models.poincare import PoincareModel
# train a new model from initial data
initial_relations = [('kangaroo', 'marsupial'), ('kangaroo', 'mammal')]
model = PoincareModel(initial_relations, negative=1)
model.train(epochs=50)

# online training: update the vocabulary and continue training
online_relations = [('striped_skunk', 'mammal')]
model.build_vocab(online_relations, update=True)
model.train(epochs=50)

このモデルの差分更新パートの実装は私がコミットしました。

New #Gensim release 3.8.0:
* Online learning for Poincaré embeddings
* BM25 more scalable
* Downloading of pre-trained models & corpora works offline too

Release notes: https://t.co/l8TIfFfJkC
Enjoy! 🙏
— Gensim (@gensim_py) 2019年7月8日

github.com

まとめ

今回は、近年注目されている双曲空間での学習を推薦ドメインに適用し、定性・定量的な実験を行いました。結果として、ユークリッド空間のword2vecの学習よりも双曲空間での学習のほうが、低次元・高次元ともに高精度を達成することを確認しました。双曲空間の埋め込みは、ベクトルの低次元化によるシステム面でのメリットはもとより、すでに導入されているロジックの精緻化にも役立つ可能性があるのではないでしょうか。今後は最新のセッションベース推薦手法との比較を行っていく予定です。またgensimのポアンカレモデルの高速化も行っていきたいです。