---
lang: ja-jp
tags: Survey
title: Learning models with BPR
---
# Learning models with BPR
ユーザのアイテムに対する隠れた選好を扱うモデルのクラスとして以下の２つを取り上げる。

- Matrix Factorization
- k-Nearest-Neigbor

いずれのモデルについても、予測値は各ユーザ・アイテムの組$\left( u, l \right)$についての実数$\hat{x}_{ul}$であることに注意する。

Bayesian Personalized Rankingでは、最適化問題は$\left( u, i, j \right) \in D_{S}$の組について定義されるので、予測器$\hat{x}_{uij}$を以下のように分解することから考える。

$$
\hat{x}_{uij} := \hat{x}_{ui} - \hat{x}_{uj}
$$

このような変換を行うことで、一般的な協調フィルタリングのモデルを当てはめることが可能になる。

同じモデルを予測器として利用していても、ランキング問題について最適化された基準においてモデルを最適化するため、より良いパフォーマンスが期待される。単一の$\hat{x}_{ul}$を回帰予測するのではなく、２つの予測の差$\hat{x}_{ui} - \hat{x}_{uj}$についての分類問題を解いていることになる。

## Learning

### w/ Matrix Factorization
$\hat{x}_{ui}$の問題設定は、$X : U \times I$の各成分を予測することに置き換えることができる。Matrix Factorizationでは、ターゲットとなる行列$X$を、より低次元の２つの行列$W : |U| \times k$と$H : |I| \times k$に分解する。

$$
\hat{X} := WH^{t}
$$

ここでの$k$は、近似の次元数を表現している。$w_{u}$行はユーザを表現する特徴量ベクトルとして解釈でき、$h_{i}$行はアイテムを表現する特徴量ベクトルとして解釈できる。したがって、予測の計算式は次のように書き下すことができる。

$$
\hat{x}_{ui} = \langle w_{u}, h_{i} \rangle
$$

Matrix Factorizationのモデルのパラメータは$\Theta = \left( W, H \right)$となる。モデルのパラメータは潜在変数としても捉えることができ、観測されていないユーザの選好やアイテムの属性をモデル化していると考えることができる。

一般に、$X$への$\hat{X}$の最小二乗法における最も良い近似はSinglar Value Decomposition (SVD)によって得られるとされている。しかし、機械学習のタスクにおいてはSVDは過学習しがちであり、それゆえに異なる行列分解の手法が提案されてきた。

ランキングのタスクにおいては、`BPR-Opt`の基準に対して最適化する方法として、`LearnBPR`を提案した。このフレームワークに基づいた場合の微分結果は次のようになる。

$$
\frac{\partial}{\partial \theta} \hat{x}_{u i j}=\left\{\begin{array}{ll}{\left(h_{i f}-h_{j f}\right)} & {\text { if } \theta=w_{u f}} \\ {w_{u f}} & {\text { if } \theta=h_{i f}} \\ {-w_{u f}} & {\text { if } \theta=h_{j f}} \\ {0} & {\text { else }}\end{array}\right.
$$

さらに、追加で３つの正則化のための定数を利用する。

- against ユーザの特徴量ベクトル : $\lambda_{W}$
- against アイテムの特徴量ベクトル :
- Positive Feedback $h_{if}$ : $\lambda_{H^{+}}$
- Negative Feedback $h_{jf}$ : $\lambda_{H^{-}}$

### Implementation

#### Sampler
Samplerはデータセットを抱え込み、Triple`(u, i, j)`をサンプリングすることに責任を負う。後続の論文で様々なサンプリングの改良が行なわれているらしく、モデルがサンプリング手法を抱え込まない実装にする。

##### 残課題
- Samplerをコンテキスト付きで呼び出せる実装にする
- つまり`with`を利用した呼出しを可能にする

# pylint: disable=invalid-name, too-many-arguments
from typing import Tuple
from typing_extensions import Protocol

import numpy as np


class BPRSampler(Protocol):

    @property
    def n_users(self) -> int:
        ...

    @property
    def n_items(self) -> int:
        ...

    def draw(self) -> Generator[Tuple[int, int, int], None, None]:
        ...


class SamplerMeta(ABC):

    @abstractmethod
    def draw(self) -> Generator[Tuple[int, int, int], None, None]:
        raise NotImplementedError


class SamplerBase(SamplerMeta):

    def __enter__(self):
        pass

    # see: https://docs.python.org/ja/3/reference/datamodel.html#object.__exit__
    # see: https://www.sejuku.net/blog/24672
    def __exit__(self):
        pass


class UniformSampler(SamplerBase):

    def __init__(self, data) -> None:
        pass

    def draw(self) -> Generator[Tuple[int, int, int], None, None]:
        pass


class BootstrapSampler(SamplerBase):

    def __init__(self, data) -> None:
        pass

    def draw(self) -> Generator[Tuple[int, int, int], None, None]:
        pass

#### Model
LearnBPRの枠組みに基づいて、SGDを利用したパラメータの更新を行う。

##### 残課題
- `is_converged`の判定条件をどうするか
- トレーニングデータに対しての当てはまりを見る場合には、データを抱え込む`BPRSampler`との依存が生まれる
- 以下の実装では、ScorerとしてMatrix Factorizationを利用しているが、論文ではAdaptive kNNによるモデルも紹介されているので、モデルをSampler同様差し込める形にしたい
- そのためには、パラメータに対する勾配の導出とそれらを利用した更新の抽象化が必要になる

from typing import Sequence, Type, Union

import numpy as np


class BayesianPersonalizedRanking:

    default_sampler_class = BootstrapSampler

    def __init__(
            self,
            nr: int,
            nc: int,
            k: int = 5,
            eta: float = 1e-2,
            l2_w: float = 1e-2,
            l2_hp: float = 1e-2,
            l2_hn: float = 1e-2,
            sampler_class: Optional[Type[BPRSampler]] = None,
        ) -> None:
        # Hyper Parameters
        self.k = k
        self.eta = eta
        self.l2_w = l2_w
        self.l2_hp = l2_hp
        self.l2_hn = l2_hn
        # Model Parameters
        self.W = np.asmatrix(np.random.normal(loc=0., scale=l2_w, size=(nr, k)))
        self.Hp = np.asmatrix(np.random.normal(loc=0., scale=l2_hp, size=(nc, k)))
        self.Hn = np.asmatrix(np.random.normal(loc=0., scale=l2_hn, size=(nc, k)))
        # Sampler
        self.sampler = self.default_sampler_class() if sampler_class is None else sampler_class()

    def fit(self, dataset, n_draws: int = 1000) -> None:
        """Fitting model parameters with LearnBPR framework.

        Args:
            dataset: A container of the dataset.
            n_draws: The maximum number of draws by the sampler.
        """
        # Validate the dataset
        assert self.sampler.n_users == self.W.shape[0]
        assert self.sampler.n_items == self.Hp.shape[0]

        # Model parameter fitting
        for t in range(n_draws):
            # Score
            # xui = scorer.score(u, i)
            # xuj = scorer.score(u, j)
            # x = xui - xuj
            u, i, j = sampler.draw()
            xui = np.dot(self.W[u], self.Hp[i].T)
            xuj = np.dot(self.W[u], self.Hn[j].T)
            x = xui - xuj

            # Update model parameters
            # 正則化経験損失最小化の枠組みでSGDを利用する場合には
            # モデルの出力に対する損失関数の勾配を渡せば、パラメータの最適化が実装できる
            ## Coef.
            s = np.exp(-x)
            coef = s / (1. + s)
            ## Nabla
            dw = np.multiply(coef, self.Hp[i] - self.Hn[j]) + np.multiply(self.l2_w, self.W[u])
            dhp = np.multiply(coef, self.W[u]) + np.multiply(self.l2_hp, self.Hp[i])
            dhn = np.multiply(coef, - self.W[u]) + np.multiply(self.l2_hn, self.Hn[j])
            ## Update
            self.W[u] += np.multiply(self.eta, dw)
            self.Hp[i] += np.multiply(self.eta, dhp)
            self.Hn[j] += np.multiply(self.eta, dhn)

            # Check if it converged
            is_converged = False  # TODO
            if is_converged:
                print(f'converged in {t+1} loops')
                break

    def predict(self, u: Union[int, Sequence[int]]) -> np.matrix:
        """Make predictions.

        Args:
            u: A user index or a sequence of users indices.
            i: An item index or a sequence of items indices.
        """
        pass

#### memo

def coef(x: T) -> T:
    s = np.exp(-x)
    return s / (1. + s)


class Model:
    def update_params(self, coef: Callable[[T], T]):
        # 普通にスコアを出す
        # coef関数を利用して損失に対する勾配を導出
        # 現時点でのパラメータの値を利用して更新する

### w/ Adaptive kNN
kNNは協調フィルタリングでよく利用される手法。ユーザ同士（あるいはアイテム同士）の「類似度」という指標が必要となる。

> ユーザ$u$に対するアイテム$i$の予測は、$i$とこれまでにユーザが閲覧したことがある（Positive Feedbackを与えているアイテム集合$I_{u}^{+}$）アイテムとの間の類似度に依存する。たいていの場合は、$I_{u}^{+}$のうち最も類似する$k$件のみを考慮するのが普通。