Theoretical Modeling of the Iterative Properties of User Discovery in a Collaborative Filtering Recommender System

タイトルにある論文を読んだので以下にメモを載せておきます。

これはRecysys 2020にアクセプトされた論文でざっと見た限り唯一の理論系論文のようでした。
理論系も気になるタイプの人間なので、真面目に読んでみたのですが、
端的に言うといろいろと気になる論文でした…

この論文の目的とContribution

原文を抜粋します。(目的は、目的と思しきところを抜粋しました)

• 目的
  We then present a theoretical definition of the
  notions of user discovery and blind spot and study their iterative behavior by deriving asymptotic bounds that govern several metrics
  that can quantify these notions.

• Contribution

• We present a theoretical study of the evolution of a recommender system’s feedback loop by looking at the asymptotic
  behavior of its components.

• We provide a theoretical bound on the human discovery resulting from interacting with a generic recommender system,
  under certain assumptions.

• We verify our theoretical results, empirically 1
  , using a semisynthetic dataset.

• We empirically study the limit of basic exploration approaches
  and their effectiveness in increasing human discovery

僕なりの理解で説明するとざっというとユーザーが推薦システムの元で興味があるアイテムをどの程度見つけられるかについて興味があり、確率論的な方法で漸近挙動を調べ、推薦システムの理論的な調査を行い、特に
一定の条件の元、人間の発見能力に対して理論的な限界を示した.また、その条件が妥当か確認するために実験でも検証しうまくいったということを主張していると思います。

この内容を見るにこれは、理論系の論文だと思います。

理論的な論文に対して考えるべきことは以下の2つだと思っています.

• 理論的に(数学的に)正しいか
• 理論的な結果が現実に即しているか

では、これらが現実的なのか、理論的に正しいのか実際に見ていきましょう.

biasについて

論文ではpreliminaryとして多数のbiasについて紹介していました。一旦ここでも説明しておきます。

• Diversity bias
  • 推薦システムで推薦されるアイテムの多様性が確保されない問題
  • filter bubble等の問題が引き起こされる
• Popularity Bias
• 人気のある商品が常に上位にレコメンドされる問題のこと
• 上との違いは,以下かなと思う.
  • 一定数の商品がレコメンドされないことと
  • 特定の商品が共通してレコメンドされることと
  • 言葉の問題なので、私は上の問題もpopularity biasと呼びそう.
• exposure bias
  • 新しいものを見たことによる影響を考慮する問題.
  • iterative biasの1ループに相当する
• iterative bias
  • 学習時と推薦時までの間に新しいものを見たことによる効果のこと

問題設定とNotation

実際の理論的な主張の前に問題の設定について述べておきます。

Definition(推薦システムの定義)
A recommender system in a collaborative filtering settingとは$(I,U, f_t,t)$の組であって, $\bullet$ I: item全体のなす集合 $\bullet$ $U$: ユーザーのなす集合 $\bullet$ $G$:アイテムグループの集合,$M:I \to G$, $G$はitemのgroup(カテゴリのようなもの)のなす集合 $\bullet$ $t \in \mathbb{Z}_{\ge 0}$ $\bullet$ $f_t: G \to I$:$t$回目の推薦を定義する写像.

注意
原文では$f_t$については以下のように記載されています.

• $f_t : G \to I$ is the selection function of the recommender
system which selects a fixed number of items to recommend
to a given user at iteration t

これについて私が感じた疑問を2つ記載しておきます.

• $f_t:G \to I$の場合,各グループに対して一つしかitemが選択されません.
  同じグループから複数個レコメンドされないという仮定が妥当かは全くわかりません.

• 何よりもこれはどういうレコメンドをしたいんでしょうか.
  以下の方針なのかなと思いましたが,あとのAssumptionを考えると$f_t(g)$はグループ$g$の元ではないようも見えます...

  1. レコメンドする対象となるグループを固定で何個か選択
  2. そのグループ内から何か一つを選ぶ

• 文章を読むと固定された個数のものが推薦されるということになっています.
  ただし,この個数の値やどのグループから推薦されるかは指定されていません
  恐らく機械学習なので何某かの最適化問題の解として定義することになるのかもしれませんが、それが推薦システムの定義に含まれていないのはかなり違和感があります.
  具体的には上の定義だと実際には推薦には1グループしか選択されないもの,100万グループされて意味不明になるものが区別されません.
  このあとの議論では必要ないかもしれませんが,定義として不誠実なものであると思っています.

以下用語をいくつか定義します.

• $Rec_t \subset G$:$t$回目のレコメンドされたグループ
• $Rel \subset G$ as the set of item groups that are relevant to a given user.
  • これはユーザーが(まだ認知していない)好きなグループ全体の想定
• $S_t \subset G$:見たもの
• $B_t:= S_t^c \cap Rel$をブラインドスポット
• Rel: 関係のあるもの(レコメンド対象?)
  • このサイズを減らしたい. $B_t:= S_t^c \cap Rel$
• $\Delta S_t:= |S_t| - |S_{t-1}| = |S_t \setminus S_{t-1}|$
  ($S_t$の定義より,$S_{t-1} \subset S_t$となるので.)
• $ \Delta B_t = |B_{t−1} | − |B_t|$
• user discovery: $\sum \Delta S_t$
  • アイテム(グループ)は有限なので十分大きい$n$を選べば$\sum \Delta S_t \le |S_n|$
  • $\Delta_n S := \frac{1}{n}\sum_{t=0}^n \Delta S_t$
    • これは$n \to \infty$の時,0に収束する.

Asuumption

理論解析をする上で以下の仮定を設定していました。僕の誤解が入るとまずいと思ったので、仮定は原文ままで、疑問点だけ記載する形にしています。

Assumption 3.1 (Vacuum Assumption).

Let $(I,U, f_t,t)$ be a recommender system, $S_t$ is the set of seen item groups and $Rec_t$ is the set of newly recommended item groups at iteration $t$. We assume that

$$
S_{t+1}=S_{t} \cup Rec_{t}
$$

Assumption 3.2 (Perfect Feedback Assumption).

Let $(I,U, f_t,t)$ be a recommender system and let M be the item-to-group mapping function, $S_{t−1}$ be the set of seen groups of items, and $Rec_t$ be the set of newly recommended groups of items at iteration t. We assume that

$$
Rec_{t}=M \circ f_{t}\left(S_{t-1}\right)
$$

Assumptiosn 3.3

Let $g_i, g_j \in G$ be two groups of items and let $d : G \times G \to \mathbb{R}$ be a distance measure between two sets in G. If
$d(g_i, S_{t−1}) ≤ d(g_j, S_{t−1})$ then we have
$P_f(g_j \in Rel) ≤ P_f(g_i \in Rel)$

注意
ここはあえて原文のままにしています.ではこれで気になる点を列挙します.

• Assumption 3.1

  • 上の注意で書いたことと被りますが,推薦システムに対して$Rec_t$が一意に定義されています.先程も書きましたが、上の推薦システムの定義には$Rec_t$が特定する手段がないので実際は$Rec_T$を定義に加える必要があるかと思います.

• Assumption 3.2

  • $t$に対する仮定が必要になると思います.
    例えば初めて来たユーザーは$S_0 = \emptyset$なので,
    (実際は$t=0$は初めてきた$t$を表さないかもしれんがい,どこかの$t$では現実の推薦システムでは$S_t = \emptyset$となるはず.)
    それに対して,Assumption3.2を仮定すると
    $Rec_t = \emptyset$となり,たった一つもレコメンドされない状況になり,Assumption 3.1から任意の$t$に対して$S_t = \emptyset$となります.
  • もし$|Rec_t|$が$t$に依存せず一致している場合,$|S_t|$は単調増加ですが,$f_t:G \to I$で,
    Assumption 3.2から$|M \circ f_t(S_{t-1})|$は一定.つまり$|S_t|$が一定でなければ,異なる$g_1, g_2 \in S_t$に対して,$M \circ f_t(g_1)=M \circ f_t(g_2)$を意味します.

• Assumption 3.3

  • distance measureの意味がよくわかりませんでした.いわゆる距離関数とした場合でも$d(g_i, S_{t-1})$は右が集合になっているので意味が特定しづらいです.典型的には$inf$で定義しますが,それで妥当と考える根拠が不明でした.
  • Assumptionで満たすべきdistance measureの条件がよくわかりませんでした.これは$d:G\times G \to \mathbb{R}$がdistance measureならどんなものでもよくて何か特別な一つのdistance measureに対して,条件を満たしていれば,$P_f(g_j \in Rel) \le P_f(g_i \in Rel)$を仮定していいんでしょうね...
  • $P_f$はProbability that an item from a given group will be recommendedだそうですが,これはあるアイテムをレコメンドする確率と読めます.今の設定では$f_t$は関数として定義されているので,1か0以外取り合えるんでしょうか?
  • $P_f(g_j \in Rel)$というNotationですが,$g_j$というグループからあるアイテムをレコメンドする確率なんですかね?一見$g_j$が$Rel$に入っている確率という意味かと思いました.

と大量の疑問をあげて、実際に彼らが証明したという定理を追っていきましょう.

Theorem

Lemma 3.4

Let $f$ be the generic selection function of a recommender system, $S^c_t$ be the complement of $S_t$, and $g_j \in G$ be a group of items. if $f$ satisfies Assumption 3.3 and $|St| > |Rec_t|$ then
$$
E\left(\left|\left\{g_{j} \in S_{t}^{c} \cap Rec_{t}\right\}\right|\right)=0
$$

証明をおう前に、結論に対する疑問をあげておきます.

疑問

• 期待値はどこで取っているのかよくわかりませんでした.
  証明を追う限り$g_j$が$Rec_t \cap S_t^c$に入っている確率という意味で$P(g_j \in Rec_t \cap S_t^c)$に対して期待値を数えているようでした....(違うことを願っているという意味でもあります)
  ちなみにこの場合だと確率分布が$t$ごとに変わるので$E_t$等にしてほしいものです...
• $|S_t| > |Rec_t|$の場合,$S_{t}^{c} \cap Rec_{t} = \emptyset$を示しているのではないでしょうか.有限事象で$||$は常に0以上かつ期待値が0ということは,各事象に対して確率が0であることを表します.よって,$P_f(g) = 0$となります.これはさらに言えば$Rec_t \subset S_t$となります.
• もし$|Rec_t|$が一定だったとした場合,$S_{t+1} = S_{t} \cup Rec_t$から$t \ge 1$で$|S_t| \ge |Rec_t|$となります.上と合わせると,$Rec_t \subset S_1$となります.($t$がいくつも値から取り始めているのか明記されてないので、もしかしたら$t=1$でないかもしれまえせんが、今の仮定は1回レコメンドしたらサチるという結論を述べています)

では実際に証明を追っていきましょう。

最初に全体の期待値に対する計算を行っており

Since we have a fixed set of recommendations, we have:
$$
E\left(\left|\left\{g_{j} \in G \cap Rec_{t}\right\}\right|\right)=|Rec|
$$
where $|Rec| = |Rec_t| ∀t$.

と書いています.

• この文章を見ると上の最後の疑問で述べていた仮定$|Rec_t|$が一定というものが仮定されているようです.

上の式から
$|S_t \cap Rec_{t}|+ |S_{t}^{c} \cap Rec_{t}| = |Rec_t| = |Rec|$より
$$
\left.E\left(\left|\left\{g_{j} \in\left(S_{t} \cap Rec_{t}\right)\right\}\right|\right)+E\left(\mid\left\{g_{j} \in S_{t}^{c} \cap Rec_{t}\right)\right\} \mid\right)=|Rec|
$$
となります.

$h_P:G \to {0, \ldots, |G|}$(え？これ0が入るの?全単射じゃなくなるけど?)をranking functionとする.
この時,

Considering the ordered statistics
$$
\left\{O_{(1)}, O_{(2)}, \ldots, O_{(|G|)}\right\}
$$
we get $h_P(g_j) = q$, where $O_{(q)} = P(g_j \in Rel)$

としましょう.

• この時数学的には$P(g_j \in Rel) = P(g_{j+1} \in Rel)$となることはあり得るし、実際的には同率で確率0はあり得るような気がしますが,確率が一致しないという前提でこの論文は議論しているようです...

レコメンドの方針から考えて,
$P(g_j \in Rec_t) $は

• $h(g_j) \le |Rec_t|$の時 1
• $h(g_j) > |Rec_t$|の時, 0

となるので,期待値を改めて計算すると

$$
|Rec_{t}|=\sum_{j=0}^{|S_{t}|} 1_{ (h\left(g_{j} \mid g_{j} \in S_t\right) \leq\left|Rec_{t}\right| )} +\sum_{i=0}^{\left|S_{t}^{c}\right|} 1_{\left(h\left(g_{i} \mid g_{i} \in S_{t}^{c}\right) \leq\left|Rec_{t}\right|\right)}
$$
となります.($S_t$が論文はタイポしてました)

でここから$h(g_i),h(g_j)$の関係を見ているのですが,
論文だと

and according to Assumption 3.3, we have
$$
h\left(g_{j} \mid g_{j} \in S_{t}\right) \leq h\left(g_{j} \mid g_{j} \in S_{t}^{c}\right)
$$

と書いています.Assumption3.3ではdistance measureをとるはずなんですが、一体何をとったんでしょうね...

おそらく何某かのdistaneを取り、その結果,
$g_j \in S_t, g_i \in S_{t}^c$の時$d(g_j, S_{t-1}) < d(g_i, S_{t-1})$なったのだと思います.感覚的には$S_t$の元の方が$S_{t-1}$に近いのはまぁそうかなとは思います.

そうすると確率で常に不等式が得られ,それは
$g_j \in S_t, g_i \in S_t^c$の時
$P(g_j \in Rel) \ge P(g_i \in Rel)$となります.
(いつの間にか論文のNotationも$P_f$ではなく,$P$になっています.こういうのはやめていただきたいものです...)

しかし,こうなったとしても,$h(g_j) \le h(g_i)$が言えるとは限りません...
例えば確率がお互い一致してる場合に順位の大小関係はついていません.

が一旦は一致していないとして考えます.

そうすると当然

$$
\max \left(h\left(g_{j} \mid g_{j} \in S_{t}\right)\right) \leq \min \left(h\left(g_{j} \mid g_{j} \in S_{t}^{c}\right)\right) \forall g_{j} \in G
$$
となります.
(不等式に等号が不要だと思いますが,論文にはついていたので...)
全くわかっていないんでしょうねぇ

$|Rec_t| < |S_t|$の場合,
当然全て$S_t$から選ばれるので,

$$
\left.E\left(\mid\left\{g_{j} \in S_{t}^{c} \cap Rec_{t}\right)\right\} \mid\right)=0
$$

となります.
これで一つ証明が終わりました.

では次の補題に行きましょう.

Lemma 3.5

By defining the measurable space (Ω,G), where Ω is the sample space of item groups, and if $E(|{g_j \in S_t^c \cap Rec_t}| = 0$; then $S_t$
is a filtration on $\Omega$ and the random process $|S_t|$ is a martingale defined in the filtered probability
space $(Ω, S, \mathbb{P})$, where $\mathbb{P}$ is a probability measure in (Ω,G).

ここでも改めて疑問を書いていきます.
証明をおうのも悲しくなってきたのでここでは証明もちゃんとおいません...

疑問:

• $G$が可測集合、特に$P(\Omega)$の部分集合のように書かれているが,これは単なるアイテムの集合で、そのような正当化ができるのだろうか?
• $S_t$がFilterationとなっているが,これも同様.
  • $G$が作る$\sigma$-加法族
  • $S_t$が生成する$\sigma$加法族という意味?
• Martingaleの条件が謎
  • 基本的に条件付き期待値に対する議論なのだが、証明すべき式が期待値同士の関係式になっている.$E\left(\mid S_{t+1} | S_{t}, S_{t-1}, \cdots, S_{0}\right)=E\left(\left|S_{t}\right|\right)$
  • 左は条件付き期待値(確率変数)で右は実数
  • 左も条件付き期待値の場合$|S_t|等でないとおかしいのでは?
• 証明としては,そこを示さないといけないのだが、今は期待値とっただけになっていて一番大事なポイントが証明されていない.
  期待値同士が一致していれば、元の確率変数が一致しているというめちゃくちゃな議論を使っている...

この論文の主定理と思える部分を考えましょう.

Theorem 3.6

Let $\Delta S_t = |S_{t+1} | − |S_t|$ be the martingale difference defined on the filtered space (Ω, S, P). We define the
average user discovery $\Delta_nS = \frac{1}{n} \sum_{t=0}^n \Delta S_t$
. Then, with probability 1 − δ, we have:

$\frac{1}{n} \sum_{t=0}^{n} \Delta S_{t} \leq \frac{\ln \left(\frac{1}{\delta}\right)|\operatorname{Rec}|^{2}}{2 n}$

この証明は

• Azuma-Hoeffding inequalityを使って不等式を変形
• あとは単純な計算

という形で証明することができます.

ただ,Azuma-Hoeffdingはマルチンゲールでないと適用できず、マルチンゲールであることの証明が間違っている中この定理にどれだけ価値があるのかは疑問なところです。

ちなみに
($S_0=\emptyset$とし、$n=0$の場合だけAssumption 3.2が正しくないとすると,Assumption3.1,3.2を使い

$|\Delta_nS| = \frac{1}{n} |Rec|$になります.

これに確率的な評価なんて必要なんですかね...
どうやろうとも今の条件だと,$|Rec|$を使ってboundできる中,一体何が必要なんでしょうか.

以降の章で実験を行っていますが,理論部分に焦点を当てたので、ここで話は終わりにしたいと思います。

まとめ

論文を真面目に読んでこの内容だとどうしてもつらいものがありますね。。。
この論文を読んで思ったことですが、以下となります...

• 論文の誤りが簡単にわかる論文すらアクセプトされているような査読状況はさすにが問題が…
• 論文の誤りが簡単にわからない論文でも同様に多数の誤りがあることが推察される.

バブルすぎて査読がおいついていないという話はよく聞きますが、この論文を読んで実感がわきました。

ちなみにもし僕が誤読してるところがあれば教えていただきたいです。僕が勘違いしてるだけの方がよほど嬉しい限りです。