• はじめに
• 論文の概要
• 課題
• IPS を用いたペアワイズロスの最適化
• PROPENSITY RATIO SCORING
• Propensity-weighted Negative Samples
• Propensity Ratio Scoring
• 実験結果
• まとめ

はじめに

DROBE では趣味志向が多岐にわたるファッションアイテムをお客様に提案するために機械学習を積極的に活用しています。その中でもユーザーとアイテムのマッチ度を推定するレコメンドエンジンはサービスに欠かせない存在です。

しかしながら、一般的にレコメンドにはその使われ方やデータの収集方法などによって様々なバイアスが発生してしまう事がわかっています。(代表的なバイアスとしてはポジションバイアスと呼ばれるアイテムの表示位置によってクリックされやすいアイテムとそうでないアイテムが発生してしまう、といったものがあります)

この記事ではクリックなどの暗黙的なフィードバック (Implicit Feedback) を使って学習する Learning to Rank (LTR) におけるバイアス除去の方法を提案している論文 Unbiased Learning to Rank via Propensity Ratio Scoring の解説を行います。(ちなみに DROBE には明示的なフィードバックも大量にあり、ここでの考え方を参考に独自の拡張を行なっていく必要がありそうだと考えています)

論文の概要

この論文は、クリックなどの暗黙的なフィードバックを使って学習する LTR において、クリックされていないデータの中に実はユーザーに好まれるアイテムが入っている可能性がある、という問題を解決するための考え方を提案してくれています。

具外的には、すでに多くの論文で議論されている Inverse Propensity Scoring (IPS) を使った手法を拡張し、Propensity Ratio Scoring (PRS) という概念によって、クリックされていないデータの取り扱いに関する新しい考え方を提案しています。

原文 PDF リンク

arxiv.org

arxiv.org

課題

クリックデータを使ってランキングを推定する LTR を開発する事を考えます。(ここではクリックを、ユーザーがそのアイテムを好むといった意図を直接反映するものでは無いため、暗示的なフィードバックと呼びます)

クリックで構成される暗黙的フィードバックデータは 4 つの種類に分解が出来、クリックデータとして観測されるのはユーザーが好んでおり (Relevant) かつユーザーに観測された (Observed) 場合のみというのが一般的です。

LTR で一般的な手法であるペアワイズ損失を使う場合に、クリックされていない (Unclicked) データを教師データの負例として使ってしまうと、本来は正例として扱うべきデータであるクリックされていないが ユーザーが好むアイテムのデータを負例として扱ってしまうといった事があり得てしまいます。

教師データで本来正例とするべきものを負例として使ってしまうとデータの数が増えても性能が想定よりも上がらないといった事が発生するため、手元にクリックデータしか無いといった状況の中で教師データの中に潜むバイアスについて正しく理解し適切にバイアスを除去するのは非常に大切であると言えます。

IPS を用いたペアワイズロスの最適化

論文ではまず暗黙的フィードバックから得られるモデルで作成したランキングのメトリクスを最適化する事を考えます。

クリックデータなどの暗黙的フィードバックしか得られていない状況においてはユーザーが好んでいて、かつユーザーに観測されているデータだけが観測されます。このセットアップにおいてペアワイズ損失を定義するにはいくつか方法があり、Unbiased LambdaMART: An Unbiased Pairwise Learning-to-Rank Algorithm や BPR: Bayesian Personalized Ranking from Implicit Feedback を踏まえると以下のように定義できると記載されています。 (これは一般的な IPS を考慮した LTR のメトリックとして考えて良いと思います)

$x_i$ = クリックされたアイテム

$x_j$ = クリックされなかったアイテム

$O_p(x_i)$ = アイテム $x_i$ がユーザーに観測されたかどうか (1 は観測された、0 は観測されていない)

$C_p(x_j)$ = アイテム $x_j$がユーザーにクリックされたかどうか

$\delta(x_i, x_j|\pi_q)$ = レコメンド $\pi_q$ が与えられた状態での $x_i$と $x_j$ のペアワイズ損失

$P(O_q(x_i) = 1 | \hat{\pi}_q)$ = Click が Log された時のランキング $\hat{\pi}_q$ において $x_i$ が観測される確率

この式には一つ課題があり、それはユーザーに観測されてはいないが、ユーザーが好むであろうアイテムが教師データの負例として採用されてしまうという事です。(xj はクリックされていないデータ全てなので)

本来ペアワイズ損失を使った LTR というのはユーザーが好むアイテムと、好まないアイテムを比較した結果を損失として使ってランキング学習を行うものですが、観測されていないだけで実際にはユーザーが好むであろうアイテムと観測されていてユーザーが好むとわかっているデータを比較してしまう事に問題があるという事のようです。

この事は実際に実験的には確かめられているとの事で、論文中に図による説明があります。

この図は Yahoo や WEB10K 等のオープンなデータに対して、ペアワイズ損失の計算を

1. Click データを正例、それ以外全てを負例
2. Click データを正例、Unclick データを負例
3. Click データを正例、Unclick の中でも Irerevant なデータを負例

それぞれに対して行った際の NDCG を表しています。この結果はクリックされていないデータの中でも本当にユーザーが好まないデータだけを負例として使う事で性能の向上が見込めるという事を示しています。

PROPENSITY RATIO SCORING

こういった課題への対策として、クリックされていないが実際にはユーザーには好まれるアイテムの影響を取り除くための手法として Propensity ratio scoring という手法が提案されています。

Propensity-weighted Negative Samples

論文ではまずデータの持つ意味について整理しつつ解くべき問題を定義し直しています。

ユーザーに観測されているにも関わらずクリックされなかったアイテムは、クリックされなかったアイテムの中でもユーザーに好まれていないアイテムと言えます。これを踏まえると、クリックされなかったアイテムの中で実際にユーザーに好まれていないアイテムを見つけるタスクは、クリックされなかったアイテムの中でユーザーに観測されたアイテムを見つけるタスク、と置き換える事ができます。

実際にあるアイテムがユーザーに観測されたかどうかという事はログには残せていない場合がほとんどですが、観測された可能性が高いかどうかという事は傾向スコアなどから推測できるので、ロス計算の期待値という意味においては傾向スコア等を用いる事でクリックされておらず、かつユーザーに観測されていないデータのみを負例として使った場合と同等の結果を得る事ができます。

以下の式でそれを証明しています。

式 (8) において $\Omega(X_j|\pi_q)$ は $X_j$ に対するペアワイズロスを含む任意のロスを表現しています。式の最後の変形は、ユーザーに観測されていてかつクリックされていないアイテムはユーザーに好まれない ($O_q(X_j) = 1 \land C_q(X_j) = 0$ の時は $r_q(X_j) = 0$) という前提のもと行われています。

論文中では、クリックされていないアイテムの重み付けのための考え方を Propensity-weighted Negative Sample (PNS) と呼んでいます。ここでの直感的な理解としては、Propensity score が高く (観測された可能性が高い) かつクリックされていないアイテムは、ユーザーに好まれない可能性が高い、ということになると思います。

Propensity Ratio Scoring

PNS によって真にユーザーに好まれないアイテムを推定できるようになるので、期待値においては クリックされていないけど実際にはユーザーに好まれそうなアイテムの影響を取り除く事が可能になります。

あるデータを観測する確率が、あるデータを観測する確率に影響を与えない (クリックデータの場合は例えば観測確率は表示位置の関数であって、独立である) という状況においては PNS と IPS はお互いに干渉をしないので、IPS と NPS を同時に考慮するという事が可能になります。

この式はペアワイズロスに対して、正例の Propensity Score と負例の Propensity Score の比を掛けていると理解できます

これを使ってメトリックの期待値を計算すると、以下のように観測されていないが実際にはユーザーに好まれそうなアイテムの影響を排除した形にできる事が確認できます。

この式で一つ考慮すべきな点としては、ユーザーに観測されておらずかつユーザーに好まれなそうなアイテムの影響も排除してしまっている事ですが、ランキングのメトリックはユーザーに好まれるアイテムに対して定義されるので、負例に紛れ込んだ実はユーザーに好まれそうなアイテムに対してのみ考えて、ユーザーに好まれそうなアイテム内でのバイアスを除去出来れば良いと考えられるそうです。(この辺りの考えかたは実際にはレコメンドモデルの使い方などに依存しそうだなと思いました)

実験結果

PRS はどのようなペアワイズロスを用いた LTR アルゴリズムにも適用可能で、論文では複数のアルゴリズムに対して PRS を適用して結果を比較しています。

結果は、PRS は全てのデータセットにおいて Naive (IPS も PRS も使っていない) algorithm と IPS よりも良い結果が得られるとの事です。

X軸がクリックされたデータ数を表していて、値が大きいほど巨大なデータセットを使っていると考えられます。Naive な手法では、各種バイアスの影響があるためデータセットが巨大になってもその恩恵を受けられずにパフォーマンスはほぼ横ばいになってしまっていますが、IPS ではデータセットが大きくなるにつれて性能が良くなる事が確認出来ます。 (ここではクリックデータのポジションバイアスを除去できているのでデータ点数と性能が比例していると考えて良いと思います)

PRS ではさらにデータセット内の Unobserved なデータの影響を排除しているので、IPS よりもさらにデータ点数の増加による性能向上ができていると考えられます。

まとめ

ペアワイズ損失におけるバイアス除去の方法を提案してくれている Unbiased Learning to Rank via Propensity Ratio Scoring という論文の解説をしました。

論文中には、ここでは言及していないクリックバイアスをどう考えるかなども細かく書いてあり、実際のアプリケーションに適用を考えている方は一読をおすすめします。

DROBE は、暗黙的なフィードバックのみならず明示的なフィードバックも大量に保持しているので若干考え方は変わると考えていますが、こういった論文を読み解きつつさらにレコメンドの精度を上げていくといった事を行なっています。