第２回 NIPS+読み会・関西 発表資料 山本

Coevolutionary Latent Feature Processes for Continuous-Time User-Item Interactions NIPS+読み会・関西 2016-12-26 Yasuo Yamamoto 1

自己紹介 山本 康生 (Yasuo Yamamoto) 所属：データ＆サイエンス サイエンス本部＠大阪オフィス 担当：広告サイエンス 経歴： • 今年の８月からYahoo! JAPANに在籍 • 京阪奈地区で研究開発(NICT, ATRなど） • KaggleでTop10%入賞とか Airbnb(143rd/1462)、HomeDept(85th/2125) 2

Table of Contents Motivation Experimental details Highlight data Summary 3

Motivation

著者について About Authors ジョージア工科大学のLe Songさん研究室 • Yichen Wangさん • Nan Duさん • Rakshit Trivediさん 5

• http://www.cc.gatech.edu/~lsong/
• http://www.cc.gatech.edu/~ywang/

レコメンデーションの課題 for Recommendation 最適なサービス・アイテムを 最適なタイミングで 最適なユーザに提案する 6

今回のタイトル Today’s Title Coevolutionary Latent Feature Processes for Continuous-Time User-Item Interactions 7

大事なところ Topics Coevolutionary Latent Feature Processes for Continuous-Time User-Item Interactions 8

共進化とは？ Coevolution？ Coevolution / koh-ev-uh-loo-shuh/ 意味：“共進化” 9 (weblioより）

ユーザとアイテムが共進化する例 Example 4 1 教育について議論する政治スレッド 政治スレッド 3 2 教育に関心がある ユーザが集まる 教育について議論が活発化 スポーツ・スレッドなど 5 10 政治に関心がなくなった ユーザが移動

本研究の課題 Subjects • 利用者とアイテムは共進化する • 利用者の行動時間はぞれぞれに異なる • 利用者の興味関心は行動に表れる • 利用者・アイテム行列の最適化 11

本研究の提案 Proposals 提案：Coevolutinary Latent Feature Process • 利用者とアイテムは共進化する • 利用者の行動時間はぞれぞれに異なる • 利用者の興味関心は行動に表れる 提案：A novel low rank space sharing constrains • 12 利用者・アイテム行列の最適化

Experimental Detail

イベントの定義 Event Representation Given 𝒖 users and 𝒊 items All of user’s history events: 𝚻= {𝒆𝒌 } 𝒆𝒌 = (𝒖𝒌, 𝒊𝒌 , 𝒕𝒌 , 𝒒𝒌 ) 𝒖𝒌 : user feature 𝒊𝒌 : item feature 𝒕𝒌 : time 𝒒𝒌 : interaction feature 14

ユーザ潜在変数 A user‘s latent feature (item->user): どのアイテムとインタラクションしたかで決まる 15

アイテム潜在変数 A item‘s latent feature (user->item): どのユーザからインタラクションされたかで決まる 16

点過程について Background on Temporal Point Process {𝒕𝒊 } with 𝒕 ∈ 𝑹+ イベントの時間 𝑵(𝒕): 𝒕までに観測したイベント件数 𝝀(𝒕): 条件付き強度関数(intensity function)  これまでに起こったイベントによって決まる、次イベントの確率モデル  強度関数は興味関心のモデルとして使われる 𝒕, 𝒕 + 𝒅𝒕 : An event in small window 𝚻 𝐭 : The history 𝝀 𝒕 𝒅𝒕 ≔ ℙ 𝒆𝒗𝒆𝒏𝒕 𝒊𝒏 𝒕, 𝒕 + 𝒅𝒕 𝚻(𝒕)} = 𝔼 {𝒅𝑵 𝒕 |𝚻 𝐭 } In a small window of size dt, i.e., 𝒅𝑵 𝒕 ∈ {𝟎, 𝟏} 17

点過程モデル Representation of a simple point process 18 Ioane Muni Toke, An Introduction to Hawkes Processes with Applications to Finance

強度関数 Intensity Function Hawkes Processを強度関数𝝀(𝒕)として使う 𝒆𝒙𝒑(−𝝎𝒕) : an exponential triggering kernel 𝝁: baseline intensity independent of the history (𝝁 ≥ 𝟎) The kernel 𝓚𝝎 and the weight 𝜶 (𝜶 ≥ 𝟎) depend on the history 19

１次元ホークス型モデル Hawkes Process: Sample path of 1D-Hawkes Process 20 Ioane Muni Toke, An Introduction to Hawkes Processes with Applications to Finance

潜在変数過程 Latent Feature Process ユーザ潜在変数 𝑼𝒖 (𝒕) ∈ 𝑹𝑲 𝒘𝒊𝒕𝒉 𝒊𝒏 𝒂 𝒖𝒔𝒆𝒓 𝒖, 𝒘𝒊𝒕𝒉 𝒊𝒏 𝒂𝒏 𝒆𝒗𝒆𝒏𝒕𝒔 𝑲 インタラクション強度の平均 アイテム強度の平均 アイテム潜在変数 𝒊𝒊 (𝒕) ∈ 𝑹𝑲 𝐰𝐢𝐭𝐡 𝐢𝐧 𝐚 𝐢𝐭𝐞𝐦 𝐢, 𝒘𝒊𝒕𝒉 𝒊𝒏 𝒂𝒏 𝒆𝒗𝒆𝒕𝒏𝒔 𝑲 インタラクション強度の平均 21 ユーザ強度の平均

高次元パラメータ The high-dimensional feature A, B, C and D 𝐴, 𝐵, 𝐶, 𝐷 ∈ 𝑅𝐾×𝐷 (𝑤𝑖𝑡ℎ 𝑖𝑛 𝑎 𝐷 𝑓𝑒𝑎𝑡𝑢𝑟𝑒𝑠) ユーザ潜在変数 𝑼𝒖 (𝒕) ∈ 𝑹𝑲 𝒘𝒊𝒕𝒉 𝒊𝒏 𝒂 𝒖𝒔𝒆𝒓 𝒖, 𝒘𝒊𝒕𝒉 𝒊𝒏 𝒂𝒏 𝒆𝒗𝒆𝒏𝒕𝒔 𝑲 未知のパラメータA, B アイテム潜在変数 𝒊𝒊 (𝒕) ∈ 𝑹𝑲 𝐰𝐢𝐭𝐡 𝐢𝐧 𝐚 𝐢𝐭𝐞𝐦 𝐢, 𝒘𝒊𝒕𝒉 𝒊𝒏 𝒂𝒏 𝒆𝒗𝒆𝒕𝒏𝒔 𝑲 未知のパラメータC, D 22

ベース属性 Drift of base features ユーザ潜在変数 𝑼𝒖 (𝒕) ∈ 𝑹𝑲 𝒘𝒊𝒕𝒉 𝒊𝒏 𝒂 𝒖𝒔𝒆𝒓 𝒖, 𝒘𝒊𝒕𝒉 𝒊𝒏 𝒂𝒏 𝒆𝒗𝒆𝒏𝒕𝒔 𝑲 𝜙𝑢 (𝑡)：ユーザの自己プロフィールなど アイテム潜在変数 𝒊𝒊 (𝒕) ∈ 𝑹𝑲 𝐰𝐢𝐭𝐡 𝐢𝐧 𝐚 𝐢𝐭𝐞𝐦 𝐢, 𝒘𝒊𝒕𝒉 𝒊𝒏 𝒂𝒏 𝒆𝒗𝒆𝒕𝒏𝒔 𝑲 𝜙𝑖 (𝑡)：アイテムのカテゴリや説明など 23

ホークス型モデルの効果 Evolution with Hawkes interaction feature averaging processes User’s and item’s features can evolve and be influenced by the characteristics of their interactions. … We choose the exponential kernel 𝓚𝝎 𝒕 = 𝒆𝒙𝒑(−𝝎𝒕) to reduce the influence of each past event. In other words, only the most recent interaction events will have bigger influences. 24

共進化とホースク型モデル平均 Coevolution with Hawkes feature averaging process ある時刻𝒕𝒌 のユーザ潜在変数𝑼𝒖 (𝒕𝒌 ) とアイテム潜在変数 𝒊𝒊 (𝒕𝒌 )を、𝐈𝐈と定義して(1), (2)を展開する 25

共進化とホースク型モデル平均 Coevolution with Hawkes feature averaging process ある時刻𝒕𝒌 のユーザ潜在変数𝑼𝒖 (𝒕𝒌 )とアイテム潜在変数 𝒊𝒊 (𝒕𝒌 )を、 𝐈𝐈と定義して(1), (2)を展開する あるユーザuの ユーザ潜在変数 26 ユーザ強度 * ユーザ base drift ユーザ強度 * インタラクション強度 ユーザ強度 * アイテム base drift ユーザ強度 * インタラクション強度

共進化とホースク型モデル平均 Coevolution with Hawkes feature averaging process 外的要因と内的要因を一つのモデルとして定義 base driftに従った外的要因 27 インタラクションに従った内的要因

点過程ユーザ・アイテム・インタラクション User-Item Interactions as Temporal Point Processes ユーザ・アイテムの強度関数 (𝜼𝒖,𝒊 ): ユーザ潜在変数とアイテム潜在変数の内積 𝜼= base preference matrix 何を使うべきか書かれていないが利点は、 • インタラクションの異質性を軽減する • ユーザの長期的な趣向を確保する • short-term preferenceが瞬間的な特徴に左右される • 強度関数の正の値を保証する 28

パラメータ推定 Parameter Estimation イベントの集合𝚻、時間幅 [𝟎, 𝚻) のとき 最尤推定でパラメータを推定 負の対数尤度 ℓ The objective function is non-convex in variables {A, B, C, D} due to the inner product term in (3) 29

凸目的関数 Convex Objective Function 式(3)は、𝑼𝒖 (𝒕) には𝑪, 𝑫が含まれ、𝒊𝒊 (𝒕)には𝑨, 𝑩が含まれる 30

凸目的関数 Convex Objective Function 式(3)を展開すると、内積項から𝓧が表れる この𝓧を 𝑿𝒊 として式(3)を強度関数𝚲 𝐭 = 𝝀𝒖,𝒊 (𝒕) に 書き換える 𝑿𝒊 の係数𝒙𝒊 (𝒕) は算出が可能 強度関数𝚲は𝑿𝒊 に対して凸 31

低ランク行列 The row rank space sharing 𝑿を左右対象のブロック行列にする 𝑨⊺ などが共通空間が存在するので低ランクにすることが可能 低ランクどうしの内積は低ランクとなる 𝑿の核型ノルム(nuclear norm)を最小限に抑えることで、すべて の低ランクの空間共有の制約が保証される。 32

目的関数 Objective function 新しい変数Xを用いた最小化すべき目的関数 ℓ: 対数尤度関数(4) ∥・∥𝑭 : フロベニウスノルム(Frobenius norm) 𝜶, 𝜷, 𝜸 : 制約のトレード・オフを調整する 目的関数から求まったパラメータを用いて強度関数𝚲(𝐭)算出して予 測問題を解く 33

最小化アルゴリム Generalized Conditional Gradient Algorithm • 最新の一般化された条件付き勾配アルゴリズム [9] • 𝟏 収束は𝑂( 𝒕 + 𝟏 ) 𝒕𝟐 を保証 (tはイテレーション回数） 𝟏 𝑂( ) で収束 𝒕𝟐 • 核ノルム制約が存在しない場合、 • 非負数制約が存在しない場合、 𝑂( )で収束 • １イテレーションは𝑂(𝒎𝒏𝒌) 𝐦ユーザ数、𝒏アイテム数、𝒌イベント 𝟏 𝒕 数/ユーザ・アイテム 34 [9] N. Du, Y. Wang, N. He, and L. Song. Time sensitive recommendation from recurrent user activities. In NIPS, 2015.

Highlight Data

予測と評価 Predictions and metrics a. アイテム・レコメンデーション • ある時刻tにおけるユーザの生存確率Sui(t)を算出 • Sui(t)を昇順に並べてアイテムをレコメンド • 評価はMean Average Rank(MAR) b. 時刻予測 36 • 次イベントの確率密度f(t)を算出 • 評価はMean Absolute Error(MAE)

比較 competitors • TimeSVD++: the classic matrix factoraization • FIP: a static low rank latent factor model • STIC: a semi-hidden markov model (時刻予測のみ） • Poisson Tensor: Poisson Regression • Dynamic Poisson: the Poisson factorization with a Kalman filter（アイテム・レコメンドのみ） • 37 Low Rank Hawkes: a Hawkes Process based model epock based models

人工データでの性能評価と結果 Experiments on Synthetic Data and Results 1,000ユーザ 1,000アイテム 10,000イベント を生成 38

実世界データでの性能評価 Experiments on Real-World Data • IPTV: TVストリーミング・サービス • 7,100ユーザ視聴履歴、436プログラム、2,392,010イベント、 1,420映像属性 • Reddit: 掲示板サイト • • 2014年１月〜、1,000ユーザ、1,403グループ、10,000イベント Yelp:ローカルビジネスレビューサイト • 2004年10月〜2015年12月、100ユーザ、17,213ビジネス、約 95,000レビュー 39

実世界データの属性 Features 40 Item base feature User base feature Interaction feature IPTV 1,420 movie features N/A N/A Reddit N/A N/A Comment (bag-of-words) Yelp Business description N/A Review (bag-of-words)

実世界データでの結果 Results - IPTV 41

実世界データでの結果 Results - Reddit 42

実世界データでの結果 Results - Yelp 43 LOW RANK HAWKES might be good at differentiating the rank of intensity better than COEVOLVE . However, it may not be able to learn the actual value of the intensity function accurately. Hence our method has the order of magnitude improvement in the time prediction task.

実世界データでのユーザの時間的遷移 Time-varying in IPTV and Reddit 44 AppleがSamsung に勝訴したとき

Summary

まとめ Conclusion • ユーザ・アイテムの潜在変数の共進化を効率よくモデリング • 大規模なデータセットに対しても優れた予測精度を達成 • 将来的にはソーシャル・グラフの動的モデリングやQ&Aサイトの ユーザ行動の理解などに応用する 46