📖

O'REILLYの「推薦システム実践入門」を読んでのまとめ①

2023/12/02に公開

機械学習

まとめ

概要

直近で推薦システムに関連したトピックを扱う予定があり、体系的な知識を求めて O'REILLY の推薦システム実践入門を読みました。

当たり前ですが、この記事を読むよりも、本を読む方が遥かに意味があります。本記事は、私が後で本の内容を振り返るのに役立つ事を目的として、本の内容で特に気になったトピックやアルゴリズムの詳細について、まとめ的な観点で紹介したいと思います。

感想

「実践入門」とある通り、アルゴリズム特化の内容ではなく、システムを作成する上での全体的な流れや注意点について詳細に書かれていました。取り上げられている例も、動画・音楽・商品販売など一般的なものは網羅されており、さらに各場合における推薦の目的や方法などが説明されています。

アルゴリズムに関しても、推薦システム本来の基礎的な要素からブレークダウンされて説明がなされており、旧来のアルゴリズムから深層学習までのアルゴリズムが網羅されているため、この一冊で体系的な知識の習得が可能ではないでしょうか。といっても私自身は推薦システム初学者になるので、体系的かどうかというのは、自身の勝手な満足度によるものです。ネット記事をぱらぱらとかいつまんで読むより、この一冊を読み理解する事を強くお勧めします。

推薦システム

ここでは、推薦システムの概要に関する事で、重要だと思った項目を取り上げます。

検索システムとの違い

本に書かれてある表^[1]を引用します。

内容	検索システム	推薦システム
ユーザーがあらかじめお目当てのアイテムを把握しているか	把握していることが多い	把握していないことも多い
キーワード（クエリ）入力	入力あり	入力なし
関連アイテムの推測の仕方	入力された検索キーワードからユーザーの意図を推測	ユーザーのプロフィールやユーザーの過去の行動から推測
ユーザーの姿勢	能動的	受動的
パーソナライズ	しないことが多いが、近年ではパーソナライズするサービスも増えている	することが多い

少し混乱した箇所でもありますが、「キーワードの有無」というのが検索システムとの重要な線引きの要素かもしれません。例えば、画像検索などは特徴量のK近傍的な手法で類似画像を検索していると思われますが、後述する内容ベースフィルタリング等の内部的な処理と似ていると思ったからです。特徴ベクトルのコサイン類似度等で似たアイテムは検索できます。

検索システムと推薦システムは、あくまでシステムとしての目的の違いであり、内部で使用されているアルゴリズムとはレイヤーが違うという事で理解しました。

内容ベースフィルタリングと協調ベースフィルタリング

推薦システムに使われるアルゴリズムは以下に大別できると書かれています。

推薦アルゴリズムの分類^[4]

内容ベースフィルタリングとは、推薦されるユーザーのプロファイルや行動履歴とアイテムの内容を考慮して推薦を行う事です。例えば、SFアニメが好きな人に、ファンタジーアニメやSF映画を推薦する事です。

逆に協調フィルタリングとは、行動履歴から他のユーザーと類似性を見出しアイテムを推薦します。例えば、趣向が似ている別のユーザが見つかった場合、そのユーザが高評価をつけたアイテムを同様に推薦します。アイテムの具体的な属性情報などを利用しないのが協調フィルタリングの特徴です。

メモリベースとモデルベースというのは、予測の実行方法の違いによるものです。ある推薦の時点でそれまでに貯まった全てのデータを考慮して推薦されるのがメモリベース、ある時点で最適化されたパラメータ（モデル）を使って推薦を行うのがモデルベースといった内容になります。

定義は重要ですが、個人的には「このアルゴリズムは協調フィルタリングだ」といったカテゴライズに強くこだわる必要は無いのかなと思います。言葉としては知っておく必要はあると思いますが。

重要な視点

推薦システムを作成する上での重要な（と思った）視点をピックアップします。

KPI

Key Performance Indicator ( KPI ) の策定が大事です。たとえば YouTube では、「ユーザーのトータル視聴時間」を KPI としているようです。

データのバイアス

あらゆるデータについてバイアスを考慮する必要がありますが、推薦システムで扱うデータはバイアスが顕著かもしれません。人気な商品は多くの人によって手にとられますが、それが既にバイアスとなります。ランダムに選出された商品を評価するというのは、数少ないでしょう。

Amazonの5つ星の評価のデータには、各星の評価値が均等に存在するのではなく、5つ星が多いというバイアスがあります。それは、商品に対して特別な思いがある人が評価をつけやすいという傾向があるためです。^[5]

コールドスタート問題

ユーザーやアイテムに関する情報が少なければどんな推薦をして良いか迷います。コールドスタート問題とは、新規ユーザーや新規アイテムについて適切に推薦を行うことが難しいという問題です。^[7]

後述するバンディッドアルゴリズムなど、情報収集のための効率的な探索という事を考慮する必要があります。

関連アルゴリズム

本の中で紹介されていたアルゴリズムに関して、本記事でも補足し、自分なりの観点でまとめたいと思います。本の中に神のごとき表^[8]があったので引用させていただきます。

アルゴリズム名	概要	予測精度	計算速度（大規模データで計算）	コールドスタート問題への対応
ランダム推薦	ランダムにアイテムを推薦する。ベースラインとして利用されることがある	x	◎	○
統計情報や特定のルールに基づく推薦（人気度推薦など）	ベースラインとしてよく利用される	x	◎	○
アソシエーションルール	シンプルな計算方法で、SQL でも実装が可能なため、昔から幅広く活用されている	○	○	x
ユーザー間型メモリベース法協調フィルタリング	同上	○	○	x
回帰モデル	回帰問題として推薦タスクを定式化して、種々の機械学習手法を適用する	○	○	○
SVD（特異値分解）	シンプルな行列分解手法	△	△	x
NMF（非負値行列分解）	非負という制約を加えた行列分解手法	△	△	x
MF（Matrix Factorization）	Netflix のコンペで好成績を収めた行列分解手法	○	○	x
IMF（Implicit Matrix Factorization）	暗黙的評価値に対応した行列分解手法	○	○	x
BPR（Bayesian Personalized Ranking）	暗黙的評価値に対応したランキングを考慮した行列分解手法	○	○	x
FM（Factorization Machines）	評価値以外にもアイテムやユーザーの情報を加味することが可能な手法	○	○	○
LDA（コンテンツベース）	アイテムのコンテンツ情報にトピックモデルを適用して推薦する手法	△	△	○
LDA（協調フィルタリング）	ユーザーの行動履歴にトピックモデルを適用して推薦する手法	○	△	x
word2vec（コンテンツベース）	アイテムのコンテンツ情報に word2vec を適用して推薦する手法	△	○	○
item2vec（協調フィルタリング）	ユーザーの行動履歴に word2vec を適用して推薦する手法	○	○	x
深層学習	深層学習の推薦手法	○	△	○

以下では、一部説明不要な箇所を除いて、いくつか紹介します。

統計情報や特定のルールに基づく推薦

アソシエーションルール

協調フィルタリングの一種で、その例として以下が取り上げられています。

アソシエーションルールの有名な話で「おむつとビール†4」というものがあります。とあるスーパーで購買履歴をアソシエーション分析したところ、おむつを買う男性はビールを買う傾向があることがわかり、おむつの近くにビールを置いたら売上が上がったというものです。^[9]

内容ベースフィルタリングだけでは決して関連しなさそうなアイテムの組み合わせであり、そういった発見を行う事が協調フィルタリングの目的とも言えます。

例えば以下の購買履歴データテーブルを想定します。

	アイテムA	アイテムB	アイテムC	アイテムD	アイテムE	アイテムF
ユーザー1	1	1	1	0	1	1
ユーザー2	1	1	0	0	1	0
ユーザー3	1	0	1	0	0	0
ユーザー4	1	0	0	0	1	1
ユーザー5	1	0	0	0	0	0
ユーザー6	0	0	0	1	0	1

アソシエーションルールにはいくつかの指標があるので、それぞれについて具体的に計算します。

支持度: support

全データの中に対する、各アイテムの出現頻度を表します。
$support(A)=(Aの出現回数)/(全データ数)=5/6 \\ support(B)=(Bの出現回数)/(全データ数)=2/6 \\ support(C)=(Cの出現回数)/(全データ数)=2/6 \\ support(A\ \&\ B)=(AとBの同時出現回数)/(全データ数)=2/6 \\ ...$
確信度: confidence

「Aが出現した時のB( $A => B$ )」といった、あるアイテムがある時の別のアイテムの出現頻度を表します。
$confidence(A => B)=(AとBの同時出現回数)/(Aの出現回数)=2/5 \\ confidence(E => A)=(EとAの同時出現回数)/(Eの出現回数)=3/3 \\ confidence(D => A)=(DとAの同時出現回数)/(Dの出現回数)=0/1 \\ ...$
数値だけの意味を言えば、confidence(E => A)=1 というのは、Eを買う人はAを必ず買っている、という事になりますし、confidence(D => A)=0 というのは、Dを買う人はAを必ず買わない、となります。

確信度は、支持度を使って表す事が可能です。
$confidence((A\ \&\ B)=>(C\ \&\ D))=support(A\ \&\ B\ \&\ C\ \&\ D)/support(A\ \&\ B)$
リフト値: lift

リフト値は、アイテム同士がどのくらい相関していそうか、を表します。
$lift(A => B)=support(A\ \&\ B)/(support(A) \times support(B)) \\=0.33/(0.833 \times 0.33)=1.2$
1.2 という値はほんの少し相関していると言えます。

全く相関していないというリスト値は 1 です。例えば、あるアイテムXとアイテムYがそれぞれ50%と20%の確率でユーザーが購入したとします。完全にランダムで購入された場合、同時に購入される確率は、0.5x0.2=0.1 となります。この元でリフト値を計算してみると
$lift(X => Y)=0.1 / (0.5 \times 0.2)=1.0$
となります。また、アイテムAとBのセットとアイテムCのリスト値といった計算できます。
$lift((A\ \&\ B) => C)=support(A\ \&\ B\ \&\ C)/(support(A\ \&\ B) \times support(C)) \\ =0.166 / (0.33 \times 0.33)=1.5$

アプリオリアルゴリズム（ Apriori Algorithm ）

アソシエーションルールについて、アイテムの数が多くなればその値を計算するのに時間がかかります。例えばアイテム数が10では、アイテムX=>Yのリフト値は 10C2=45、アイテムX&Y=>Zは 10C3 x 3C2 =120 x 3(X,Y,Zの組の中に X&Y=>Z, X&Z=>Y, Y&Z=>X の組がある) となります。アイテム数が20の場合、アイテムX=>Yのリフト値は 20C2=190 の組があり、アイテム数が2倍で相関値の計算回数は4倍になります。

このように、全部の計算をしていたのでは計算回数が指数的に増加しますので、効率的なアルゴリズムで計算を省略する必要があります。そこで使われるのが Apriori アルゴリズムです。こちらの資料を参考にしました。

以下は Apriori アルゴリズムの基本的な流れです。最小の組み合わせ数 $k=1$ から任意の組み合わせ数 $k=K$ までループし、それぞれのループで支持度を計算し、閾値によってフィルターします。k=k+1 の計算で、k個の集合に無い要素は計算しない事で効率化しています。

Apriori アルゴリズムの計算の流れ

では、association_rules の中身がどうなっているかというと、Apriori アルゴリズムのアプトプットをインプットとして、各集合内の組み合わせでアソシエーションルールを計算しています。

association_rules で行われている計算

例えば、{A,B,C=>D,E,F} のようなアソシエーションルールを計算する場合は、k=6 までの Apriori の出力が必要です。しかしながら、{A&B&C&D&E&F}のような集合は条件が厳しいので支持率は低くなりそうです。 Apriori の設定閾値よりも支持度が低い場合は当然出力に含まれないので、その後の確信度やリフト値も計算できなくなります。

こういったアルゴリズムの特性を把握した上で使用する事が重要に思います。

ユーザー間型メモリベース法協調フィルタリング

本ではピアソンの相関係数が紹介されていました。

ピアソンの相関係数^[10]

関数内の引数 $u$ と $v$ はそれぞれユーザ1の特徴量とユーザ2になります。例えば以下のデータです。

	アイテムA	アイテムB	アイテムC	アイテムD	アイテムE	アイテムF
ユーザー1	1	1	1	0	1	1
ユーザー2	1	1	0	0	1	0

行列分解

推薦システムにおける行列分解は広義の意味で、評価値行列を低次元のユーザー因子行列とアイテム因子行列に分解することを指します^[11]

行列分解の概念図^[12]

以下では、代表的なSVD、NMF、MF、IMF、BPR、FMの行列分解の手法を説明します。

特異値分解:（SVD：Singular Value Decomposition）

特異値分解を図示してみました。記号はSVDの証明を参考にしています。

本を参考にすると、評価値行列Rを次のように $P$ 、 $S$ 、 $Q$ に分解します。上図と照らし合わせると、 $P$ が $V$ , $S$ が $\Lambda$ , $Q$ が $U$ と対応します。

R=PSQ^T=PS^{1/2}S^{1/2}Q^T=\hat{P}\hat{Q}^T

この $\hat{P}$ をユーザの行列、 $\hat{Q}$ をアイテムの行列として説明がされていますが、これらがユーザやアイテムの特徴量を表すベクトルかというと、少しニュアンスが違うと思われます。

SVDを使った推薦のアルゴリズムの流れは、まず、評価値行列をSVDで行列分解します。

次に、再度 $P$ , $S$ , $Q$ を用いて評価値行列を再構成します。これは、もとの評価値行列を次元削減したもの（いくつかの基底ベクトルで表したもの）に相当します。

最後に、テストデータを読み込みます。あるユーザとあるアイテムに対して評価を行いますが、この時、それらユーザやアイテムのどちらかが、訓練時の評価値行列に含まれない場合は計算できないので無視します。

あるユーザとあるアイテムが訓練時の評価値行列に含まれる場合のみ（かつ訓練時にはそれが見未評価の場合）、再構成した評価値行列を参照し、値が大きければ推薦する、といった流れです。

詳細な解説は避けますが、SVDは単にアイテム次元を削減しているだけです（PCAとの関係性）。SVDの証明を見るに、 $v_i$ と $u_i$ の関係性は次のように

v_i=\cfrac{1}{\sigma_i}Ru_i

となっています。 $R$ の特徴量に対する $u_i$ 基底ベクトルの射影に過ぎません。そのため、「ユーザー因子行列とアイテム因子行列に分解する」という趣旨とは、少し違うように感じました。

非負値行列分解（NMF：Nonnegative Matrix Factorization）

SVDの（おそらく）基底ベクトル成分が全て正の値をとるように制限を加えたものです。SVDの派生であるため割愛します。

MF：Matrix Factorization

MF では、SVD とは異なり、評価値行列Rをユーザー因子行列Pとアイテム因子行列Qに分解し、各行列のパラメータを最適化問題として計算します。

MF では、欠損値を補完する必要はありません。何故なら、損失関数 $L$ 内で考慮される値は、正解データの実数値が入っている箇所だけだからです（ $R^+$ 内での足し上げ）。損失関数 $L$ の第２項はパラメータの大きさに対しての正則化項になります。これがある事で、パラメータの肥大化が防げます。

仮に SGD ( Stochastic Gradient Desce ) で行う場合、 $p_{11}$ の項について計算してみましょう。SGD では各パラメータで微分して少量ずつパラメータを更新していきますので、 $p_{11}$ が関連する項を抜き出します。

\cfrac{\partial L}{\partial p_{11}}=\sum_{i=1}^n\left(-2r_{1i}q_{i1}+2p_{11}q_{i1}^2+2\lambda p_{11}\right) ※但しr_{1i}が実数値の箇所のみ

パラメータの微分が計算できたら、次のように $\alpha$ 倍ずつパラメータ更新します。

p_{11}+\alpha \cfrac{\partial L}{\partial p_{11}} \rightarrow p_{11}

IMF：Implicit Matrix Factorization

MF の派生アルゴリズムになります。ここで「Implicit」は「暗黙的」を意味しますが、先に明示的と暗黙的について説明しておきます。明示的というのは、レビューの点数などが明示的に評価した値になります。逆に暗黙的というのは、詳細ページのクリックや動画の視聴など、明示的には評価していない行動履歴を指します。

本の中で紹介されている IMF の例では、動画の視聴についてです。ここで、明示的評価値である「レビューの星の数」に加えて、暗黙的評価値として「何回動画を見たかどうか」という行動履歴が変数 $r_{ui}$ として加えられます。

\overline{r_{ui}}\ \begin{dcases} 1 &(r_{ui}>0) \\ 0 &(r_{ui}=0) \end{dcases}

さらに信頼度なるものを定義します。

c_{ui}=1+\alpha r_{ui}

これらを元に、次の損失関数が定義されており、それを同様に最小化するようにパラメータを求めます。

BPR（Bayesian Personalized Ranking）

こちらも MF の派生のようなアルゴリズムです。BPRでは、（ユーザー $u$ 、暗黙的に評価したアイテム $i$ 、未観測なアイテム $j$ ）の3つのデータをもとに、学習していきます。次の目的関数を最大化するように、パラメータを学習します。

左辺の $\sigma$ はシグモイド関数で、0～1の値をとります。左辺は大きくしたいと考えますので、 $\sigma(x)$ が1になるように目指します。 $p_u^T q_i$ を大きくし $p_u^T q_j$ を小さくします。つまり、ユーザー $u$ のベクトルとアイテム $i$ のベクトルを近づけ、ユーザー $u$ のベクトルとアイテム $j$ のベクトルを遠ざけるように学習します。

FM（Factorization Machines）

FM では、上のアルゴリズムで使用していた評価値行列を使用しません。その集計前のデータ、生のトランザクションデータを使います。どちらかというとこちらの方が、機械学習っぽく馴染みがありますね。

Factorization Machines のデータ構造※一部加筆^[13]

FM はロジスティック回帰に二次の相互作用を足したバージョンです。ただそれだけだと、二次の項のパラメータは特徴量次元数を $n$ とすると、 $n(n-1)/2$ の数になりますが、各特徴量に $r$ 次元のベクトルを用意する事で、 $n^2$ に比例するパラメータ数を抑えています。

予測値は上図の式を用いて計算しますが、通常損失関数はRMSEを使うようです。

途中まで

記事自体は、ここまで本の半分程度について自分なりに触れた、という状況ですが、発展的なトピックについても勉強しておきたいので、後二回ほど別の記事を書くと思います。次回は、トピックモデルや Word2vec を使った内容ベースフィルタリングや協調フィルタリングについてと、推薦システムの評価に使われる指標についてなどなど書く予定です。

本の内容をまとめていると、いかに自分の理解に不明瞭な箇所があるのかというのに気づかされますし、まだまだ理解していない箇所も多いです。例えば BPR などは理論的背景もあると思われますが、その理解をすっとばして、最終的な損失関数の気持ちしか理解していません。結局はそういった理解度でしか記事を書いていませんので、温かい目で見ていただけると幸いです。

間違い等あればコメントに書いていただけると嬉しいです。

続き

脚注

推薦システム実践入門 P11 ↩︎
推薦システム実践入門 P8 ↩︎
推薦システム実践入門 P8 ↩︎
推薦システム実践入門 P60 図4-1 ↩︎
推薦システム実践入門 P23 ↩︎
推薦システム実践入門 P55 ↩︎
推薦システム実践入門 P75 ↩︎
推薦システム実践入門 P88-89 表5-1 各推薦アルゴリズムの比較 ↩︎
推薦システム実践入門 P110 ↩︎
推薦システム実践入門 P118 ↩︎
推薦システム実践入門 P126 ↩︎
推薦システム実践入門 P127 図5-12 行列分解の概念図 ↩︎
推薦システム実践入門 P127 図5-16 Factorization Machines のデータ構造 ↩︎