推薦システム実践入門「5.8 行列分解」を読む

はじめに

「推薦システム実践入門」という推薦システムに関する良書があり、特に行列分解に関する整理が大変わかりやすい印象でした。この記事では、書籍の内容を適宜補足をしながら内容をまとめていきます。

数式については転記が手間なのと、あまり引用が多くなってしまうこともよくないので、省略しています。興味がある方は、書籍の購入を検討いただければと思います。

    5.8 行列分解
        5.8.1 行列分解の概要
        5.8.2 特異値分解（SVD：Singular Value Decomposition）
        5.8.3 非負値行列分解（NMF：Non-negative Matrix Factorization）
        5.8.4 明示的な評価値に対する行列分解（MF：Matrix Factorization）
        5.8.5 暗黙的な評価値に対する行列分解（IMF：Implicit Matrix Factorization）
        5.8.6 BPR（Bayesian Personalized Ranking）
        5.8.7 FM（Factorization Machines）

5.8　行列分解

5.8.1 行列分解の概要

• 行列分解はモデルベース型の協調フィルタリングの手法の一つである
  • 一般的に、メモリベース型の協調フィルタリングに比べて、推薦の性能が良いことが知られている
• 行列分解という単語の意味について（memoにて後述）
• この章ではSVD, NMF, MF, IMF, BPR, FMについて説明する
• 行列分解の手法を実務で使う際に重要な観点。ライブラリを利用して行列分解を利用する際には、それらの取り扱いがどのようになっているかを理解した上で、適切なデータを入力して学習させること
  • 欠損値の取扱い
  • 評価値が明示的か暗黙的か
• まずは、評価値が明示的な場合の行列分解について見ていく
  • ユーザーが明示的に評価しているデータは質が高い

memo

行列分解の定義について記述があり素晴らしいです。

行列分解という単語が示す範囲は広く、文献によって行列分解という単語が指している手法が違うことがあります。推薦システムにおける行列分解は広義の意味で、評価値行列を低次元のユーザー因子行列とアイテム因子行列に分解することを指します。

「広義」の逆に狭義には何を指すのかがここでは読み取れませんでしたが、5.8.4の記述を見るに、狭義には5.8.4の手法を指しているという意図だと読み取りました。また、「推薦システムにおける」という限定がない場合に行列分解という単語が何を指すかについても補足が欲しいところです。単語の字面からはより一般的な意味がありそうです。

Claudeに質問すると以下のような回答が得られました。

行列分解とはなんですか？

行列分解とは、ある行列を複数の行列の積に分解することです。これは線形代数における重要な概念であり、様々な応用分野で用いられています。

主な行列分解の種類には以下のようなものがあります：

LU分解：行列をL（下三角行列）とU（上三角行列）の積に分解します。
QR分解：行列をQ（直交行列）とR（上三角行列）の積に分解します。
固有値分解：正方行列を、固有値を対角成分に持つ対角行列と、対応する固有ベクトルを列に持つ行列の積に分解します。
特異値分解（SVD）：任意の行列を、2つの直交行列とその間の対角行列（特異値を対角成分に持つ）の積に分解します。
行列分解は、連立一次方程式の解法、主成分分析（PCA）、コンピュータビジョン、機械学習など、様々な分野で応用されています。また、行列の性質を理解し、計算を効率化するためにも用いられます。

行列分解は線形代数の中でも重要な概念の一つであり、その理解は数学や関連分野において非常に有益です。

「行列を複数の行列の積に分解する」というシンプルな概念を指しているようです。英語表現も確認しておきます。

行列分解を英語で言うと？

行列分解は英語で "Matrix Decomposition" または "Matrix Factorization" と言います。

Matrix Factorizationという表現は5.8.4で扱われている手法も指すことがあるので、注意が必要そうということがわかりました。

行列分解の意味をまとめると、広義な方から順に以下のようになります。

1. 行列を複数の行列の積に分解すること
2. 推薦システムにおいて、評価値行列を低次元のユーザー因子行列とアイテム因子行列に分解すること
3. 5.8.4で紹介されている手法

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

• 単純な手法として、欠損している箇所に0または平均値を代入してSVDで次元を削減する方法
• scipyライブラリで実装できる
• スパースな行列ではほとんどの値が補完された値になってしまうため、（0で補完した場合は特に）　RMSEのような指標が悪くなる
  • 予測評価値の相対値には意味があるので、ランキング指標では性能が良くなる（ランダム予測比）
• 潜在因子数が高いほど予測精度が良くなるが、高すぎると過学習してしまう可能性があるため、一般的には数十〜数百の潜在因子数を設定する

MovieLens 10M Datasetでの評価

手法	RMSE	Precision@K	Recall@K
ランダム推薦	1.883	0.000	0.001
人気度（評価数の閾値:1）	1.082	0.000	0.000
人気度（評価数の閾値:100）	1.082	0.008	0.027
人気度（評価数の閾値:200）	1.082	0.013	0.042
アソシエーションルール（min_support:0.1）	-	0.011	0.036
アソシエーションルール（min_support:0.06）	-	0.015	0.048
SVD（欠損値の補完:0）	3.335	0.009	0.029
SVD（欠損値の補完:平均値)	1.046	0.013	0.043

memo

行列を行列の積に分解しようと思った時に、複数の方法がありそうに思いますが、SVDがなぜ推薦システムにおいて「単純な手法」として最初に扱われるのかは説明がありませんでした。他の文献（推薦システム: 統計的機械学習の理論と実践）などを確認したところ、SVDがm×nの行列に対して最良の低ランク近似を与えること（Eckart-Youngの最良近似定理）が、推薦システムの問題設定にあっているのだと思いました。

なお、画像に対して特異値分解を行う実験を特異値分解(SVD)による画像の低ランク近似という記事でしていますので、イメージを掴みたい方は合わせて読んでみてください。

推薦システムにおける行列分解では、シンプルな手法として特異値分解が紹介されることが多いように思います。なぜLU分解やQR分解ではなく、特異値分解なのでしょうか？どのような特徴が推薦システムと相性が良いのでしょうか？

推薦システムにおいて、特異値分解（SVD）が他の行列分解手法よりも好んで使われる主な理由は以下の通りです：

汎用性
SVDは、正方行列だけでなく、任意の形状の行列に対して適用できます。これは、ユーザー数とアイテム数が異なる評価行列を扱う推薦システムにとって重要な性質です。
一方、LU分解やQR分解は、主に正方行列に対して用いられる手法です。
次元削減の効果
SVDを用いると、元の行列を低ランクの行列で近似することができます。これは、ノイズの除去や過学習の防止につながります。
推薦システムでは、ユーザーとアイテムの潜在的な特徴を抽出することが重要ですが、SVDはこの目的に適しています。
LU分解やQR分解には、このような次元削減の効果はありません。
欠損値への対処
推薦システムでは、評価行列の多くの要素が欠損値（未評価）となります。SVDは、欠損値を含む行列に対しても適用可能です。
一方、LU分解やQR分解は、欠損値を含む行列に対して直接適用することが難しいです。
計算効率
SVDは、大規模な行列に対しても効率的に計算できるアルゴリズムが知られています。これは、大規模なデータセットを扱う推薦システムにとって重要な性質です。
LU分解やQR分解は、大規模な行列に対しては計算量が大きくなる傾向があります。
以上のような理由から、推薦システムにおいては、特異値分解（SVD）が他の行列分解手法よりも好んで使われています。ただし、SVDにも欠点（計算量の大きさや解釈性の低さなど）があるため、他の手法（NMFやPMFなど）が用いられることもあります。手法の選択は、データセットの性質や目的に応じて慎重に行う必要があります。

5.8.3 非負値行列分解（NMF：Non-negative Matrix Factorization）

• ユーザーとアイテムの各ベクトルの要素が0以上になるという制約を入れた
• 欠損値を0として穴埋めして適用する場合が多い
  • 欠損値を欠損したまま使う非負値行列分解もある
• スパースな明示的な評価値のデータに関しては、大規模なデータに対するライブラリの充実度合いや予測精度の観点で、SVDやNMFは避け、次節以降のアルゴリズムを使用するのがおすすめ

MovieLens 10M Datasetでの評価

手法	RMSE	Precision@K	Recall@K
ランダム推薦	1.883	0.000	0.001
人気度（評価数の閾値:1）	1.082	0.000	0.000
人気度（評価数の閾値:100）	1.082	0.008	0.027
人気度（評価数の閾値:200）	1.082	0.013	0.042
アソシエーションルール（min_support:0.1）	-	0.011	0.036
アソシエーションルール（min_support:0.06）	-	0.015	0.048
SVD（欠損値の補完:0）	3.335	0.009	0.029
SVD（欠損値の補完:平均値)	1.046	0.013	0.043
NMF（欠損値の補完:0）	3.340	0.010	0.032
NMF（欠損値の補完:平均値)	1.045	0.012	0.040

memo

• 欠損値補完が必要
• 解析的には解けず、更新式を繰り返すことで解く（学習率のような概念はない）
  • 推薦システムなどに記載があります。

5.8.4 明示的な評価値に対する行列分解（MF：Matrix Factorization）

• 推薦システムの分野において、Matrix Factorizationは、SVDと異なり欠損値を穴埋めするようなことはなく、観測された評価値だけを使って行列分解する手法を指すことが多い。
• Netflix社が開催したコンペティションにおいて、MFを用いた手法が提案され、成果を残した
• 大規模なデータでも高速で計算ができる改良手法がいくも提案されており、SparkやBigQueryでも実装されている
• 一般的に非凸であり解析的に解くことは難しい
  • Alternating Least Square(ALS), Stochastic Gradient Descent(SGD)による手法が提案されている
• バイアスを考慮しておモデルも提案されている
• SurpriseライブラリではSVDという名前でMFが実装されている

MovieLens 10M Datasetでの評価

手法	RMSE	Precision@K	Recall@K
ランダム推薦	1.883	0.000	0.001
人気度（評価数の閾値:1）	1.082	0.000	0.000
人気度（評価数の閾値:100）	1.082	0.008	0.027
人気度（評価数の閾値:200）	1.082	0.013	0.042
アソシエーションルール（min_support:0.1）	-	0.011	0.036
アソシエーションルール（min_support:0.06）	-	0.015	0.048
SVD（欠損値の補完:0）	3.335	0.009	0.029
SVD（欠損値の補完:平均値)	1.046	0.013	0.043
NMF（欠損値の補完:0）	3.340	0.010	0.032
NMF（欠損値の補完:平均値)	1.045	0.012	0.040
MF（評価数の閾値:なし）	0.934	0.005	0.016
MF（評価数の閾値:300）	1.140	0.016	0.054

memo

https://cloud.google.com/bigquery/docs/reference/standard-sql/bigqueryml-syntax-create-matrix-factorization#feedback_type
BigQueryMLのMatrixFactorizationにおいてFEEDBACK_TYPE=EXPLICITを指定した場合に相当

5.8.5 暗黙的な評価値に対する行列分解（IMF：Implicit Matrix Factorization）

• Collaborative Filtering for Implicit Feedback Datasets
• 評価値が暗黙的な場合に用いる手法
• 明示的なデータセットをあえて暗黙的な評価値に変換して、暗黙的な評価値の手法を試すこともある
• 観測値を好意rとその好意の信頼度cに分解する
• 観測されていないものを負例とみなすことで学習している
• implicitライブラリに実装されている

MovieLens 10M Datasetでの評価

手法	RMSE	Precision@K	Recall@K
ランダム推薦	1.883	0.000	0.001
人気度（評価数の閾値:1）	1.082	0.000	0.000
人気度（評価数の閾値:100）	1.082	0.008	0.027
人気度（評価数の閾値:200）	1.082	0.013	0.042
アソシエーションルール（min_support:0.1）	-	0.011	0.036
アソシエーションルール（min_support:0.06）	-	0.015	0.048
SVD（欠損値の補完:0）	3.335	0.009	0.029
SVD（欠損値の補完:平均値)	1.046	0.013	0.043
NMF（欠損値の補完:0）	3.340	0.010	0.032
NMF（欠損値の補完:平均値)	1.045	0.012	0.040
MF（評価数の閾値:なし）	0.934	0.005	0.016
MF（評価数の閾値:300）	1.140	0.016	0.054
IMF	-	0.026	0.080

memo

https://cloud.google.com/bigquery/docs/reference/standard-sql/bigqueryml-syntax-create-matrix-factorization#feedback_type
BigQueryMLのMatrixFactorizationにおいてFEEDBACK_TYPE=IMPLICITを指定した場合に相当

5.8.6 BPR（Bayesian Personalized Ranking）

省略

5.8.7 FM（Factorization Machines）

省略