推薦のアルゴリズムを調べた - 機械学習 Memo φ(・ω・ )

はじめに

基本的な推薦のアルゴリズムについて勉強しました。

「推薦システム: 統計的機械学習の理論と実践」を参考に、一部ピックアップして、要点を記載しました。

Pythonで実装する場合、使えそうなライブラリも一緒に記載しています。

www.kyoritsu-pub.co.jp

はじめに
推薦のタスク
古典的手法
探索と活用
推薦システムの評価
ランク学習
Dataset
おわり

古典的手法

bag-of-words

アイテム素性ベクトルを構成するためにbag-of-wordsベクトル空間モデルを使用。各単語を次元として扱う。
このベクトル空間に写像する方法。

バイナリ表現

単語の有無を0,1で表現

TF

単語の出現率

$\textrm{tf}(t,d) = \dfrac{n_{t,d}}{\sum_{k \in d}n_{k,d}}$

$n_{t,d}$ : 単語 t の文書 d 内での出現回数

TF - IDF

文書中に含まれる単語の重要度を表す。
まず IDF 逆文書頻度を以下とする。

$\textrm{idf}(t) = \log{\dfrac{N}{df(t)}}$

$N$ : 全文書数
$df(t)$ : ある単語 t が出現する文書の数

TF-IDF は以下であわらされる。

$\textrm{tf-idf}(t, d) = tf(t, d) \cdot idf(t)$

sklearn.feature_extraction.text.TfidfVectorizer — scikit-learn 0.21.3 documentation

次元削減

bag-of-wordsの表現は、次元が大きくなってスパースネスになってしまう。
それを抑える代表的な方法。

類義語拡張

類義語を加えてスパース性に対応
日本語 Wordnet
SudachiDict/synonyms.md at develop · WorksApplications/SudachiDict · GitHub

素性選択

過剰に出現率が高い/低い単語は無視する

特異値分解

行列Xを以下のように分解して、σiが重要度を表すので、重要の低いものを削除してしまう。

$X = (\boldsymbol{u}_1, \boldsymbol{u}_2, \cdots, \boldsymbol{u}_n) \begin{pmatrix} \sigma_1 & & & \\ & \sigma_2 & & \\ & & \ddots & \\ & & & \sigma_n \end{pmatrix} \begin{pmatrix} \boldsymbol{v}_1^{\mathrm{T}} \\ \boldsymbol{v}_2^{\mathrm{T}} \\ \vdots \\ \boldsymbol{v}_n^{\mathrm{T}} \end{pmatrix}$

numpy.linalg.svd — NumPy v1.17 Manual

ランダム射影

距離関係を保ったまま次元削減する。

sklearn.random_projection.SparseRandomProjection — scikit-learn 0.21.3 documentation

トピックモデル

文章からトピックを推定する。
LDAモデルが単語を生成する仕組みを学習するもの。

トピック分布

文章が各トピックに属する確率

トピック分布を以下のようにあわらす
$\Theta_{d} = \{ \theta_{(d, 0)}, \theta_{(d, 1)}, \dots, \theta_{(d, k)} \}$

ベクトルの和が 1 であるシンプレックス。

例 )
$\Theta_{d} = \{ 0.3, 0.2, \dots, 0.1 \}$

トピック0 がゲームなら、ゲームに属する確率は0.3
トピック1 が教育　なら、教育に属する確率は0.2
トピックk が IT　　なら、IT に属する確率は0.1

潜在トピック

文章 d の各単語 0~n に対して、それぞれ潜在トピックが存在しており、それはトピック分布から生成される。

$Z = \{z_{(d, 0)}, z_{(d, 1)}, \dots, z_{(d, n)} \}$

単語の生起確率

トピックk における、各単語 0~n の生起確率が存在し、各単語の潜在トピックとそのトピックの単語出現率から実際の単語が生成される。

$\Phi_{k} = \{ \phi_{(k, 0)}, \phi_{(k, 1)}, \dots, \phi_{(k, n)} \}$

トピック分布は、全トピック数の次元のベクトルをパラメータにもつ、ディリクレ分布から生成される。

単語の生起確率も、全単語数の次元のベクトルをパラメータにもつ、ディリクレ分布から生成される。

そのパラメータを変分近似またはギブスサンプリングで推定するらしいが....パラメータ推定の部分の理解は省略。

gensim: models.ldamodel – Latent Dirichlet Allocation

協調フィルタリング

アイテムの評価行動が似ている2人のユーザは嗜好が似ていると言える。ユーザ i に類似する他のユーザの集合を得て、アイテムを好む程度を予測する。

ユーザ間の類似度に基づいた手法

ユーザ i と似ているユーザがアイテム j に与えた評価を元に、ユーザ i がまだ評価していないアイテム j のレイティング(スコア)を以下のように表す。

$s_{ij} = \bar{y_{i}} + \dfrac{ \sum_{l \in T } w(i,l)(y_{lj} - \bar{y_{l}} )}{ \sum_{l \in T} |w(i,j)|}$

$\bar{y_{i}}$ : ユーザ i の平均レイティング
$y_{l j}$ : ユーザ l のアイテム j に対すレイティング
$T$ : ユーザ i に似ていて、アイテム j を評価したユーザの集合
$w(i,l)$ : ユーザ i がアイテム j を評価する時のユーザ j に対する重み

重み $w(i,l)$ を一般的には以下のユーザ間の類似度 $sim_{(i, l)}$ で表す。

ユーザ間の類似度

ユーザ i とユーザ l の類似度。

$sim_{(i, l)} = \dfrac{ \sum_{l \in J_{il} } (y_{ij} - \bar{y_{i}} ) (y_{lj} - \bar{y_{l}} )}{ \sqrt{\sum_{j \in J_{il}} (y_{ij} - \bar{y_{i}} )^2} \sqrt{\sum_{j \in J_{il}} (y_{lj} - \bar{y_{l}} )^2}}$

$J_{i,l}$ : ユーザ i とユーザ l の両方に評価されたアイテムの集合

アイテム間の類似度に基づいた手法

アイテム j と似ているアイテムに与えられた評価を元に、ユーザ i がまだ評価していないアイテム j のレイティング(スコア)を以下のように表す。

$s_{ij} = \bar{y_{i}} + \dfrac{ \sum_{l \in J } w(i,l)(y_{lj} - \bar{y_{l}} )}{ \sum_{l \in J} |w(i,j)|}$

$J$ : ユーザ i によって評価されたアイテム j と似ているアイテムの集合

探索と活用

多腕バンディット

複数のスロットマシーンで各マシーンの当たりが出る確率がわからない状況で、腕を選択する試行を繰り返し報酬を最大にする課題。

探索と活用のトレードオフ問題に対する、いくつかのアプローチがある。

ベイジアンアプローチやミニマックスアプローチがあるが、実践でよく使われる、ヒューリスティックなバンディット戦略を記載。

$\varepsilon$ - グリーディ

$\varepsilon$ の確率で探索をし、 $1 - \varepsilon$ で活用(報酬確率の推定値が最大となる選択)をする。
過度の探索をさせないために時間の経過と共に、 $\varepsilon$ を減少させる。
例えば、今の時点で腕を引いた総数 $n$ に対して、 $\varepsilon_{n} = min \{ 1, \frac{\delta}{n} \}$ とする。

SoftMax

腕を探索する確率を以下のようにする方法。 $\tau$ はハイパーパラメータ。良さそうな腕を多く探索できるが、分散を考慮できていない。

$\dfrac{e^{\hat{p_i}/\tau}}{\sum_{j} e^{\hat{p_j}/\tau}}$

$\hat{p_i}$ : 腕 i から得られた報酬の標本平均

Thompson Sampling

スロットマシーンごとにベータ分布を以下のように定めて乱数を発生させて、その値が大きかったマシーンを引く。

$Be(\alpha + 1, \beta + 1)$

$\alpha$ : そのマシーンで当たりがでた回数
$\beta$ : そのマシーンでハズレがでた回数

Most-Popular推薦

ポジティブなレスポンスを最大化させるため、全てのユーザに最も人気のあるアイテムを推薦する方法。ユーザの個別化は行わない。

ただし、昼間のデータを使って、夜間の人気アイテムを推定するようなケースだとバイアスがかかる可能性があるため、カルマンフィルタや単純指数加重移動平均などを使ってバイアスを取り除く必要がある。

個別化推薦

ユーザを荒いセグメントに分類して、各セグメントに対してMost-Popular推薦を適応する。セグメントを特定するために決定木やクラスタリングを使う。

ランク学習

ランク学習は素性ベクトルからアイテムのスコアリストへの写像を学習。

その写像を
$F(x) = (f(x_1), f(x_2), f(x_3), \dots, f(x_n))$

とし、教師データは以下のように表す

$\mathcal{L} = \{ l_1, l_2, \dots ,l_n \}$

Pointwise approach

1つのアイテムに対して、ランキングのどの位置かを予測するアプローチ。

損失関数の例

$L'(F(x), y) = \sum_{k=1}^{i}(f(x_i)-l_i)^2$

Pairwise approach

2つのアイテムに対して、どっちの方がランキングが上かを予測するアプローチ。

損失関数の例

$L'(F(x), y) = \sum_{s=1}^{n-1}\sum_{i=1, l_i < l_s}^{n} \phi (f(x_s)-f(x_i))$

$\phi$ はヒンジ関数や指数関数など。

Listwise approach

複数のアイテムに対して、それぞれのアイテムがランキングではどの位置かを予測するアプローチ。ランキング全体としての良さを求めている。

損失関数の例

$L'(F(x), y) = \sum_{s=1}^{n-1}(-f(x_{y(s)}) + ln( \sum_{i=s}^{n} exp(f(x_{y(i)})))$

$y(i)$ は i 番目にランクづけされたオブジェクトをさす

RankNet

NNを利用したPairwise approach。

$f$ をモデルとし、２つのアイテム $x_i$ 、 $x_j$ のスコアを $f(x_i) = s_i$ 、 $f(x_j) = s_j$ とする。
アイテム $x_i$ の方が $x_j$ よりランクが高いことを、 $x_i\triangleright{x_j}$ と書く。

$x_i\triangleright{x_j}$ となる確率を以下のように定める。

$P_{ij} = \dfrac{1}{1+ exp(-( f(x_i) - f(x_j)))}$

損失関数はクロスエントロピーとし、勾配降下法で最適化する。

$C_{ij} = -\bar{P}_{ij} \log P_{ij} -(1-\bar{P}_{ij}) \log (1-P_{ij})$

$\bar{P}_{ij}$ は真の確率で、以下のように定める。

$\bar{P}_{ij}= \begin{cases} 1 & \text{if ${x_i} \triangleright {x_j}$} \\ 0 & \text{if ${x_j} \triangleright {x_i}$} \\ 1/2 & \text{otherwise} \end{cases}$