行列分解によるレコメンドを整理する #1~特異値分解によるレコメンド~

# 0.はじめに
　この記事は、機械学習によるレコメンド手法の基礎について、私が理解しやすいと考えた順序・考え方で整理しなおすものになります。対象としては「データ分析や機械学習の基本手法を理解しているものの、レコメンドに関しては未経験である」という人を想定しています。
　今回は、特異値分解によるレコメンドの手法を元に、行列分解によるレコメンドの基本を整理します。レコメンドの基本的な用語・概念、および行列の演算は既知のものとして説明しています。なお、レコメンドの用語・基礎概念などの入門内容は別記事にまとめたので、よろしければご覧ください。

https://qiita.com/yo_fuji/items/f1c9d5bf715eb69a2e5d

# 1.レコメンド手法の確認とタスクの定義
　レコメンドの手法は、大きく分けて「内容ベースフィルタリング」と「協調フィルタリング」があります。後者の協調フィルタリングは、ユーザの行動履歴、および評価値行列を用いてレコメンドする手法です（この辺りの用語についても、ぜひ上述したURLの記事を参考にしていただきたいです）。
　評価値行列とは、簡単に言えば以下のような形式のデータのことを指します。

|user_id/item_id| 1| 2| 3| 4| 5|
|---|---|---|---|---|---|
| 1| 0.0| 4.0|4.5|NaN| NaN|
| 2| 3.5| 2.0|5.0| 2.5| 5.0|
| 3| 2.5| 4.0|0.5| 2.5| 4.0|
| 4| 1.0| 3.5|2.5| 3.5| 2.5|
| 5| 4.0| 4.5|0.5| 1.5| 3.0|
| 6| 3.0| 4.5|3.5| 2.0| 1.0|

各ユーザがどのアイテム（商品、映画など）に対して行動（購入、視聴、評価）したかをまとめた行列です。例えば、上の評価値行列のアイテムが「映画」だとすると、「ユーザ2」は映画1には3.5点、映画2には2.0点、...と評価したことを表しています。NaNは、そのユーザがそのアイテムに対しまだ行動した履歴がないことを表しています。ここで言えは「ユーザ1」は映画4と映画5に対しまだ評価を付けていない（ひいては視聴していない）ことになります。
　レコメンドでは、このNaNになっているアイテム4、アイテム5に着目し、「ユーザ1におすすめするなら、アイテム4とアイテム5のどちらを優先的におすすめするべきか？」というタスクを考えます。より具体的に言えば「より高い評価を付けそうなアイテムはどちらか？」というタスクであり、機械学習に落とし込めば<b>「ユーザ1がアイテム4、アイテム5に対してつける評価値を予測する」</b>、または<b>「アイテム4、アイテム5に序列をつける」</b>というタスクとなります。

# 2.「行列分解」という手法について
　セクション1で定義したタスクに対応した手法のうち、評価値行列のみでモデルを作成できる方法の1つが<b>「行列分解」</b>と呼ばれる手法です。行列分解の思想は、「ユーザの特徴とアイテムの特徴の組み合わせで評価値が決まる」というものです（私はそう捉えています）。
　具体的には、各ユーザの特徴を捉えた<b>「ユーザ因子行列」</b>と各アイテムの特徴を捉えた<b>「アイテム因子行列」</b>を定義し、その積で評価値行列を定義しようとする方法です。

![行列分解の思想.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2959513/661f6e8a-ab05-bff5-5809-ee5161bea0d5.jpeg)



この「ユーザ因子行列」と「アイテム因子行列」を完全に求めることができれば、どのユーザのどのアイテムに対しての評価値も汎用的に算出（予測）できるということになります。

# 3.特異値分解によるユーザ・アイテム因子行列の導出
　どのような方法でユーザ・アイテム因子行列を導出するかについて整理します。

### 3-1.特異値分解
　解析的な行列分解の手法として<b>「特異値分解」</b>というものがあります。特異値分解を理解するためには、前提として「1.行列の演算（積、転置など）」、「2.行列式」、「3.固有値分解」の理解が必要であると思われます。本記事では特異値分解の計算方法については触れませんので、詳細について末尾に掲載したおすすめ記事などをご参照ください。

　特異値分解は、ある行列を3つの行列に分解できる手法です。固有値分解を知っている方向けの説明をすると、固有値分解は正方行列（行数と列数が同じ行列）のみにしか対応していない手法ですが、特異値分解は行数と列数が異なる行列にも対応しています。例えば、
```math
\left(
\begin{matrix} 
2 & 1 & 1 \\ 
1 & 1 & 2 
\end{matrix}
\right)
```
という行列について、以下のような行列分解が可能です。
![特異値分解＿０.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2959513/1a2a92ff-55bd-aa42-8b6a-880ac6d0a3da.jpeg)

1つ目の行列（P）は元の行列と同じ行数の正方行列、2つ目の行列（Σ）は元の行列と同じ行・列数の行列、3つ目の行列（Q）は元の行列と同じ列数の正方行列になります。

### 3-2.評価値行列の特異値分解
　セクション1で示した評価値行列を特異値分解すると、以下のようになります（欠損値は0で補完しました）。

![特異値分解.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2959513/370e2342-c1a9-1904-032c-723da965ca22.jpeg)

レコメンドにおいては上図のPとΣを先にかけ算し、PΣ × Qの形式で表すことが多いため、ここでもそのように表します。

![特異値分解_レコメンド０.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2959513/60e3cae3-11c8-6507-d9bf-db7a04d96329.jpeg)

　さて、PΣはユーザ数(6)×5の行列、Qは5×アイテム数(5)になっており、図がセクション2で示した「評価値行列 = ユーザ因子行列 × アイテム因子行列」の形になったことが分かると思います。

![特異値分解_レコメンド色付き.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2959513/d4657aa6-5c09-91db-226c-e38f48b5dd5f.jpeg)



つまり、<b>評価値行列を特異値分解することで、ユーザ因子行列とアイテム因子行列を求めることができる</b>、ということになります。実際にユーザ2のアイテム2（評価値行列の2行2列）の評価値をユーザ・アイテム因子行列から計算してみると、

```math
\left (
\begin{matrix}
-7.816 & -0.114 & -3.312 & -0.652 & 0.087
\end{matrix}
\right )
・ 
\left (
\begin{matrix}
-0.581 \\
0.170 \\
0.746 \\
0.116 \\
0.251 \\
\end{matrix}
\right )
\\
```
```math
\begin{align}
& = \{ \,\,\, (-7.816)*(-0.581) + (-0.114)*(0.170) + (-3.312)*(0.746) \\
& \,\,\,\,\,\,\,\, + (-0.652)*(0.116) + 0.087*0.251 \, \} \\
& = 1.9971690 \\
& ≒ 2.00
\end{align}
```
となり、元の評価値（2.0）を再現できることが分かります（※表示の都合で数値を四捨五入しているため値がずれていますが、厳密に計算すれば理論上は完全に一致します）。

# 4.「因子」について
### 4-1.「因子」とは何を指しているのか？
　ここまで何の断りもなく言及している<b>「因子(factor)」</b>について簡単に説明します。セクション3-2末尾の図においては、ユーザ因子行列の「列」およびアイテム因子行列の「行」が「因子」にあたります。今回の行列分解では、ユーザ・アイテム因子行列において、因子が5つ生じているということになります。
　「因子」は、ユーザ・アイテムの特徴を表している"何か"です。この"何か"は、人間にとって解釈しやすいものである場合もありますが、人間には解釈できない数値である場合がほとんどです。とにかく、複数（今回で言うと5個）集まって、各ユーザやアイテムを表現している値です。

### 4-2.因子数の調整
　ユーザ・アイテム因子行列において重要な性質として、<b>「必ずしもすべての因子を使わずとも評価値の再現ができる」</b>という点があります。重要な因子をいくつか（例えば上から3つ）ピックアップして計算しても、ある程度元の評価値を近似できます（主成分分析を行うようなイメージです）。また、計算の観点からも、因子数を減らしても評価値行列を再現できることが分かります。行列では「m\*k行列 × k\*n行列」を計算すると「m\*n行列」になり、計算結果の行列の形式はkの値に依存しません。ここで言うとkは因子数にあたるため、計算上でも因子数と関係なく元の評価値行列の形式を再現できます。

### 4-3.因子削減による近似計算
　因子数を減らせることを説明しましたが、少ない因子で計算した評価値は当然ながら元の評価値行列の値から乖離します。以下は、前セクションで計算したユーザ2のアイテム2について、因子を3つにして計算した結果です。
```math
\left (
\begin{matrix}
-7.816 & -0.114 & -3.312
\end{matrix}
\right )
・ 
\left (
\begin{matrix}
-0.581 \\
0.170 \\
0.746 \\
\end{matrix}
\right )
\\
```

```math
\begin{align}
& = \{ \,\,\, (-7.816)*(-0.581) + (-0.114)*(0.170) + (-3.312)*(0.746)  \, \} \\
& = 2.0509640 \\
& ≒ 2.05
\end{align}
```

元の値(2.0)を近似できているものの、多少乖離がある（0.05）ことが分かります（今回はかなり正確な近似となりましたが、近似の正確性は、データの性質や元の因子数からどれだけ削減するかなどによって大きく変わります）。

　正確性をある程度犠牲にしたおかげで、計算量・メモリ使用率を抑えることができます。実際のレコメンドにおいては、ユーザ数・アイテム数が数百万単位であることが多いです。アイテム数は事前に優先度の高いものに絞るなどしてある程度限定することができますが、例えば100万ユーザ×100アイテムというデータであった場合、各因子行列のセルの数で考えると、ユーザ因子行列は100万×100で1億、アイテム因子行列は100×100で1万の値を扱うことになります（特異値分解では、最大因子数はユーザ数・アイテム数のうちの小さい方になるため、この場合の因子数は100になります）。因子数を10に削減すると、ユーザ因子行列が1,000万、アイテム因子行列が1,000まで減少し、保持する値が少なくなることが分かると思います。

# 5.特異値分解のレコメンドへの適用
　ここまでで整理した特異値分解の結果を、レコメンドにおいてどのように適用できるかを整理します。

### 5-1.予測
　セクション3-2の例で示したように、予測したいユーザ・アイテムの組み合わせに対応するベクトルの内積を求めれば、そのユーザ・アイテムの組み合わせの評価値を予測できます。ただし、ここで不可解なことが起きていることに気が付くと思います。

　第1に、予測対象であったはずのNaN値（ユーザ1のアイテム4, アイテム5）は、0で補完してしまっています。これは、特異値分解という手法の都合上必要な処理ですが、「予測したかった値を0で補完する必要がある」という予測タスクを解く上で致命的な矛盾が生じています。

　第2に、NaN以外の評価値（例えばセクション3-2で計算したユーザ2のアイテム2など）についてはかなり正確な予測ができそうですが、それらの評価値はそもそも値が分かっているものなので、わざわざ予測して求める必要がありません。

　以上のように、特異値分解による行列分解は、<b>未観測（NaN値）の評価値を予測するというタスクを解くことに向いていません</b>。NaN値に対する予測値の算出自体は可能なのですが、行列分解前に0で補完しているという都合上、的外れな値が算出されます。

### 5-2.序列付け
　一般的な機械学習モデルに慣れている人からすると、「予測タスクが実質的に解けないのであれば、利用価値がないのでは？」という疑問が浮かぶと思います。しかしながら、レコメンドにおいては、予測が正確であることよりも<b>ユーザが好む順番にアイテムを並べることが重要</b>である場合が多いです。以下の例で簡単に説明します。

|アイテム|実際の評価値|レコメンド①の予測|レコメンド②の予測|
|---|---|---|---|
|A| 4.5| 4.5|5.0|
|B| 4.0| 3.5| 3.5|
|C| 3.5| 4.0| 3.0|
|D| 2.0| 2.0| 2.0|
|E| 1.0| 1.0| 1.5|

例において、レコメンド①とレコメンド②はどちらの方がすぐれたレコメンドと言えるでしょうか？評価値の2乗誤差平均を求めれば、レコメンド①の方が小さいです（①は0.10、②は0.40）。一方、「予測評価値の高い順に上から3つレコメンドする」という場合を考えると、レコメンドしたアイテムにユーザがつけてくれる評価値の合計は、レコメンド②の方が大きいです（①はA+B+D=10.5、②はA+B+C=12.0）。このように、「ユーザが好む順番にアイテムを並べること」を重要視する状況では予測タスクに不向きである手法も十分利用価値があり、すなわち特異値分解にも利用価値があります。

　以下では、ユーザ1におけるアイテム4・5の"評価値"（実際の評価値とはかけ離れた値ですが）を算出しています。因子数を5にすると元の評価値行列がほぼ完全に再現されてどちらも0になってしまうため、因子数を3にして算出しています。
```math
\begin{align}
& アイテム4 \\
& \{ (-4.296)*(-0.334) + 4.056*(-0.198) + 0.82*(-0.108)\, \} \\
& = 0.5432160 \\
\\
& アイテム5 \\	
& \{ (-4.296)*(-0.445) + 4.056*(-0.498) + 0.82*(-0.447)\, \} \\
& = -0.4747080 \\
\end{align}
```
上記の計算結果に基づけは、「ユーザ1にはアイテム4$>$アイテム5という序列でレコメンドするのがよい」ということが分かりました。

　この序列については、評価値のNaNを0で補完して計算しているからと言って、全く的外れの序列というわけではありません。なぜなら、ユーザ・アイテム因子行列を用いた計算では、ユーザ1の他のアイテムについての評価値や、アイテム4・5に対する他のユーザからの評価値も考慮されおり、上記の計算ではそれらの情報も踏まえて「仮にユーザ1がアイテム4・5を評価した場合」の"評価値"を算出していると言えるからです。一般的に、ランダムレコメンドや人気順レコメンドよりは、このように特異値分解に基づいて序列をつけたレコメンドの方が性能が良くなることが多いとされています（もちろんデータの性質に依存します）。

# 6.まとめ
　以上、計6セクションを通し、レコメンドにおける行列分解の考え方を整理しました。欠損値を0で補完するため予測タスクには向かないものの、アイテムに序列をつけるタスクに対しては利用価値があるということを説明しました。しかしながら、未観測なだけで本来は高評価を付けるかもしれないアイテムの評価値を0で補完してしまうことが、バイアスを生んでいることは否定できません。そこで、特異値分解のアイデアをベースにした<b>「Matrix Factorization」</b>という手法を使うことで、欠損値補完なしにユーザ・アイテム因子行列を求めることができ、さらにそこから未観測アイテム（欠損値）の評価値を予測することができます。次回はMatrix Factorizationについて整理します。


次の記事：<a href=https://qiita.com/yo_fuji/items/52f10469a65e54b2ccf2>行列分解によるレコメンドを整理する #2~Matorix Factorizationによるレコメンド~</a>

# 参考文献
風間正弘・飯塚洸二郎・松村裕也 (2022) 『推薦システム実践入門―――仕事で使える導入ガイド』,オライリー・ジャパン
CodeZine 『推薦システム初心者におすすめの手法「行列分解」とは？ ～特異値分解からCB2CF法によるコールドスタート問題解決まで～ 』https://codezine.jp/article/detail/14280 (2023年2月2日最終閲覧)

# おすすめ記事
1.行列の積について

https://www.headboost.jp/what-is-matrix-multiplication/

説明が平易な言葉でまとめられており、立体イメージなどもあって非常にわかりやすいです。前提知識が不足していても、関連記事のURLを踏んでいけば基礎概念は理解できると思います。

これ以外にも、<a href="https://www.headboost.jp/">HEADBOOST</a>内のベクトルや行列についての記事は、各概念の意味にまで言及しており、計算方法しかわかっていなかった私としては個人的には非常に勉強になりました。
ぜひ他の記事もご覧になってみてください（見つかりづらいですが、検索バーは右上にあります）。


2.行列式の計算

https://www.headboost.jp/definition-of-determinant/

同じくHEADBOOSTの記事です。多くの参考書だと計算方法に終始してしまいがちですが、計算の意味にまで言及しており、非常に勉強になりました。

3.固有値分解の意味

https://www.headboost.jp/matrix-eigenvalues/

同じくHEADBOOSTの記事です。「なぜ行列式を使うのか」についても言及されています。

4.固有値分解の公式・練習問題

https://www.geisya.or.jp/~mwm48961/linear_algebra/eigenvalue2.htm

「高校数学の基本問題」というサイトの一ページです。公式や練習問題などがついており、高校の教科書のような作りになっております。
固有値分解以外にも、統計関連のページなども豊富です。

5.特異値分解について

https://nisshingeppo.com/ai/singular-value-decomposition/

こちらの記事が非常にわかりやすくまとめてあります。