1. No category

Networked Bandits with Disjoint Linear Payoffs
渡辺 僚
情報理工学専攻 情報認識学研究室
KDD2014 論文紹介
渡辺 僚 (情報理工学専攻 情報認識学研究室)
Networked Bandits
KDD2014 論文紹介
1 / 13
モチベーシ ョ ン
し たいこ と ソ ーシ ャ ルネッ ト ワ ーク を 介し た宣伝で， 多く の評価を も
ら いたい．
単に多く の人に知っ て も ら う のではなく ， 見た人の評
価値の合計を 最大化し たい．
基本方針 バン ディ ッ ト 問題のフ レ ームワ ーク を 使う ．
「 やっ て みなき ゃ 分から ない」 タ イ プの問題で使われ
る フ レ ームワ ーク．
ポイ ン ト ユーザのコ ン テキ スト 情報を 使っ た報酬モ デルを 導入．
渡辺 僚 (情報理工学専攻 情報認識学研究室)
Networked Bandits
KDD2014 論文紹介
2 / 13
概要図
論文よ り 引用
リ ン ク やユーザ数が時間変化する ネッ ト ワ ーク を 想定．
ネッ ト ワ ーク の構造も 一切仮定し ない．
渡辺 僚 (情報理工学専攻 情報認識学研究室)
Networked Bandits
KDD2014 論文紹介
3 / 13
準備
Given
Unknown
略記など
Kt = {1, . . . , kt }: ユーザ集合．
Nt (a) ⊆ Kt : 時刻 t にユーザ a から の情報が拡散する
ユーザ集合（ a 自身を 含む） ．
xa,t ∈ Rd : 時刻 t に見せる 情報と ユーザ a と のコ ン テキ
スト 情報．
ya,t ∈ [0, 1]: ユーザ a がつける 評価値（ 確率変数） ．
ga,t =
X
ya,t
a∈Nt (a)
kxkV =
渡辺 僚 (情報理工学専攻 情報認識学研究室)
p
hx, V xi =
Networked Bandits
√
xT V x
KDD2014 論文紹介
4 / 13
目標
毎時刻一人のユーザ at ∈ Kt を 選び， at から 情報が拡散し たすべて の
ユーザがつけた評価の n 時刻合計
n
X
X
ya,t =
t=1 a∈Nt (at )
n
X
gat ,t
t=1
を 最大化する こ と が目標． 選択ア ルゴリ ズムの評価指標と し て は期待リ
¯ T の小さ さ を 採用する ．
グレ ッ ト R
Definition
¯ T を 以下で定義する ．
期待リ グレ ッ ト R
#
#
" T
" T
X
X
¯ T = max E
gat ,t
ga,t − E
R
a=1,...,k
渡辺 僚 (情報理工学専攻 情報認識学研究室)
t=1
Networked Bandits
t=1
KDD2014 論文紹介
5 / 13
評価値のモデル
評価値 ya,t の期待値について ， コ ン テキ スト xa,t と ユーザ固有の重みベ
ク ト ル wa ∈ Rd の線形モデルを 仮定．
E[ya,t | xa,t ] = xTa,t wa∗ + ǫa
ただし ， ǫa は R-sub-Gaussian である ．
Definition
確率変数 X が R-sub-Gaussian である と は，
2 2
λ R
λX
∀λ, E[e ] ≤ exp
2
が成立する こ と を いう ．
ǫa が R-sub-Gaussian であれば， E[ǫa ] = 0， V [ǫa ] ≤ R2 ， かつ
ǫa ∈ [−R, R] が成立する ．
渡辺 僚 (情報理工学専攻 情報認識学研究室)
Networked Bandits
KDD2014 論文紹介
6 / 13
wa の推定
時刻 t ま でに蓄積し た na (t) 個の履歴 (xa,1 , ya,1 ), . . . , (xa,na (t) , ya,na (t) ) か
ˆ a を 推定する ．
ら L2 -正則化回帰で w
ˆ a = (XaT Xa + λ)−1 Xa Ya
w
ただし




xa,1
ya,1




Xa =  ...  , Ya =  ...  , λ > 0
xa,na (t)
ya,na (t)
渡辺 僚 (情報理工学専攻 情報認識学研究室)
Networked Bandits
KDD2014 論文紹介
7 / 13
Self-normalized bound for vector-valued martingale
ˆ a を 中心と し た超楕円を う ま く 構成す る と ， そ
L2 -正則化回帰で求めた w
∗
の中に真値 w が入る 確率の下界を 抑え る こ と ができ る ．
Theorem
ˆ t につい
yt = xTt w ∗ + ǫt （ ǫt は R-sub-Gaussian） の L2 -正則化推定重み w
て ， 以下が成立．
Pr{w ∗ ∈ Ct } ≥ 1 − δ


s
¯ 1/2 

√
|
V
|
t
√
ˆ t − wkV¯t ≤ R 2 log
Ct = w ∈ Rd : kw
+S λ


δ dλ
ただし ，
V = λI +
t
X
n=1
渡辺 僚 (情報理工学専攻 情報認識学研究室)
xn ⊗ xn ,
Networked Bandits
S ≥ kwk2
KDD2014 論文紹介
8 / 13
ユーザ選択ア ルゴリ ズム
先ほど の定理に基づいて ， 時刻 t で選択する ユーザ at を 以下のよ う に決
定する ．
at = arg max Ba,t
a∈Kt
Ba,t =
X
a∈Nt (k)

xTk,t w
ˆ k + kxk,t kV¯ −1 R
渡辺 僚 (情報理工学専攻 情報認識学研究室)
t
s
Networked Bandits

¯ 1/2 √
|Vt |
√
2 log
+ S λ
δ dλ
KDD2014 論文紹介
9 / 13
¯ T の上界
期待リ グレ ッ ト R
Theorem
Networked bandits において ， K ≥ maxt≤T |Kt | と する ． こ のと き 期待リ
¯ T について 以下が成立．
グレ ッ ト R
q
T
1/2
¯
≥ 1−δ
Pr RT ≤ 2K 2βT (δ)T log |I + XX /λ|
ただし ，
 s
証明略．
βT (δ) = R
渡辺 僚 (情報理工学専攻 情報認識学研究室)
2 log
|I + XX T /λ|1/2
δ
Networked Bandits
√
2
+ S λ
KDD2014 論文紹介
10 / 13
実データ 実験: 準備
動的ネッ ト ワ ーク データ セッ ト Delicious Bookmarks (Del)
サイ ズ 1861 ユーザ， 7668 リ ン ク， 69226URL， 53388 タ グ
報酬 ユーザが URL を ブ ッ ク マーク に追加し たら 報酬 1， でなけ
れば 0．
前処理 コ ン テキ スト 情報の生成
1 タ グを 単語に分割．
2 TF-IDF ベク ト ルを 生成．
3 PCA で 16 次元に圧縮． d = 16．
構造変化 タ イ ムスタ ン プを 元に 14 区間に分割， 各区間で 1000 回推
薦． T = 14000．
渡辺 僚 (情報理工学専攻 情報認識学研究室)
Networked Bandits
KDD2014 論文紹介
11 / 13
実データ 実験: 結果
従来手法（ TraBandits） よ り も
よ い．
3ヶ 所の低く なっ て いる 部分（ 赤
枠） は構造変化が大き いのが原因
（ 著者談） ．
渡辺 僚 (情報理工学専攻 情報認識学研究室)
Networked Bandits
KDD2014 論文紹介
12 / 13
著者ら のま と め
複数のユーザから コ ン テキ スト 情報に基づいて 報酬が出力さ れる バ
ン ディ ッ ト 問題を 定式化し た．
そ の問題に対し ， ユーザ選択ア ルゴリ ズムを 考案， リ グレ ッ ト 上界
と 人工・ 実データ 実験で優位性を 示し た．
ネッ ト ワ ーク 構造に一切の仮定がない． 何ら かの仮定を 入れる と 性
能がよ く なる のではないか．
実際の情報拡散プロ セスはも っ と 複雑である ．
渡辺 僚 (情報理工学専攻 情報認識学研究室)
Networked Bandits
KDD2014 論文紹介
13 / 13