[KDD'24 Best Student Paper Award]Dataset Regeneration for Sequential Recommendationを読んだ

# Dataset Regeneration for Sequential Recommendation
Authours: Guy Aridor, Duarte Gonçalves, Ruoyan Kong, Daniel Kluver, Joseph A. Konstan
Paper Url: https://arxiv.org/abs/2405.11053
From: KDD'24(Best Student Paper Award)

# はじめに
SMNデータサイエンティストの鈴木です．
弊社の研究開発部門，a.i.lab内で"近年というかここ二年以内くらいで面白そうorインパクトあった研究調べて共有しようぜ"の会を開きました．
どうせならQiitaで紹介記事書いてアウトプットしちゃえばいいんじゃない？みたいな流れになったのでここに残します．

# どんな内容なの？
　従来Sequetial Recommendationの領域で成果を上げてきた手法は，例えばSASRecのようなDeep系であったり，CT4Recのように学習戦略に関して最適化するものであったりと，モデルそのものの改善によって高度な推薦を行おうというものでした．本論文ではこのコンセプトを**Model-centric paradigm**と呼称する一方，データの品質に関する問題が軽視され，過学習やエラーの増幅等の問題が発生すると述べています．そこで筆者らは下記図に示すようにデータから有用な知見を含むデータを再生成(Regenerate)し，その後各モデルに対し個別化(Personalize)する多段階の推薦フレームワークを提案しています．このとき，RegenerateとPersonalizeを行うモジュールはそれぞれ現在のデータから学習します．これを**Data-centric paradigm**と呼び，本文ではその具体的なアルゴリズムである**D**ataset **R**egeneration for **S**equential **R**ecommendation(**DR4SR**)とオフライン評価の結果について紹介しています．
(ちなみにDR4SRには個別化モジュールは含まれておらず，model-awareなバージョンはDR4SR+です)
　オフライン評価の結果，提案手法であるDR4SR/DR4SR+は推薦モデルの種類を問わず良いパフォーマンスを発揮できることを示しました．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/398379/770f27a3-2d11-4d8a-98ba-5c7916764eac.png)

# どのような手法か？
　提案手法は主に3つの機能に分かれています．
(Aは図中だと分割されていませんが本説明の効率上分けて記載します)
(A-1)データ再生成部の事前学習機構
(A-2)データ再生成部の本学習機構
(B)オリジナルデータシーケンスから複数パターンのデータを再生成する機構
(C)Model-Awareなデータを作成する機構
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/398379/8c00e022-d916-4ad5-8049-db3907916945.png)
順を追って説明します．
## (A-1)データ再生成部の事前準備(ラベル？の準備)
やりたいことは，あるデータシーケンスを入力すると有用なパターンが出力されるモデルを学習することです．
しかし本問題でラベルを用いることは出来ません．当然ですが本推薦システム学習時にリークが起こってしまうためです．なので自己教師あり学習で対応します．本手法ではデータセット内からルールベースで教師を作成してしまいます．以下の図が論文中に例として挙げられています．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/398379/44ce2261-9cd2-4aea-b430-dfb64418f2e8.png)
コンセプトとしては**複数データにまたがって頻繁に登場するシーケンスが有用である**と考えます．
今[1,2,3,4,5]と[1,2,3]がオリジナルのデータシーケンスとして与えられているとします．
考慮するシーケンス長の上限を3としたとき(本文中で言う$\alpha$)上図にあるように[1,2]や[2,3]，[1,2,3]といったパターンが共通で登場します．ここである閾値(本文中の$\beta$)を超えた回数登場した場合，有用なパターンであると定義します．この例だと[1,2,3,4,5]，[1,2,3]それぞれの有用パターンは全く同一になってしまうのですが，仮に[1,2,4,5]のようなデータシーケンスがあった場合その限りではありません．(例があまりよくない...かも...)
上図のようにあるユーザのデータシーケンス$s_u$に対し得られたパターン$p_i$のペアを$(s_u, p_i)$とし，$(s_u, p_i)$全体の集合を$\mathcal{X}_{pre}$と定義します．

## (A-2)データ再生成部の事前学習
　本問題にはラベルを用いることは出来ません．よって事故教師あり学習を行うためにA-1ではラベルにあたるパターンを収集しました．
よってA-2では得られたデータシーケンスから有用なパターンを出力するモデルを学習します．具体的にはTransformerベースのモデルを用いてオリジナルのデータシーケンスをEncode→Decodeし，A-1で抽出したパターンになるよう学習します．ここで用いるEncode→Decodeモデルは一般的なTransformerです．
　まずデータシーケンスをMulti-head self attention(MHSA)に突っ込んで，最後に全結合層(FFN)へ流します．ちなみに図中のEncoder部に相当します．
```math
H^{(l)} = \text{FFN}(\text{MHSA}(H^{(l-1)})) \tag{1}
```
(Multi-Head self attentionをMHSAって略すの初めて見たな...)
$H^{(l)}$はl層目の出力を表します．
その後以下の関数で損失を計算します．いわゆるCross Entropy Lossに近い(というか一緒？)形式です．
ちなみに以下の確率Pを出力する部分がdecoderなのですが，本文ではattention機構を使う等の指定がありません(多分，おそらく，きっと)．なので任意のモデルをここで用いることができるはずです．(でも結局Cross Attentionとかになりそう)
```math
L_{\text{recon}} = -\sum_{(s_u, p_i) \in \mathcal{X}_{\text{pre}}} \sum_{t=1}^{T} \log P(p_{it} | h^{(l)}_u, \hat{p}_{<t}) \tag{2}
```
ここで$t$はパターン$p_i$におけるアイテムの位置，$h^{(l)}_u$はオリジナルのデータシーケンスの分散表現，$\hat{p}{<t}$は$t$までに生成されたパターン，$p_it$はパターン$p_i$の位置$t$におけるアイテムを指します．
つまり[1,2,3,4]というオリジナルのデータシーケンスが与えられていて，パターンが[2,3,4]，$t-1=2$の時$p_it$が4となる確率が最も高く，それ以外のアイテムになる確率が最も低くなるようにモデルが学習されるということですね．しかしこれではモデルの学習は進みません．なぜならばあるオリジナルのデータシーケンス1つに対し，複数個のパターンが存在するので，それぞれが衝突するためです．よって**一つのデータシーケンスに対してEncoderが$K$個のEmbedding$(\in \mathbb{R}^{D}，$本文ではmemoryと表現$)$を出力する**ようモデルを拡張します．この工夫で$K$個のmemoryが複数パターンへの写像を記憶してくれると説明しています(あんまり納得感が無い...)．さらにDiversity Promotorという機構を追加します．この機構はパターン$p_i$に対しTransformer encoderをかけてEncodeし，その結果を全結合層に通してmemoryに対する確率値に変換するといった処理を行います．
```math
\pi=\text{Softmax}(\text{MLP}(\text{h}^{(l)}_{\text{pattern}}))) \tag{3}
```
ここで，$\text{h}^{(l)}_{\text{pattern}}$はパターンをtransformerでencodeしたベクトルを指します(lはそんなに気にしなくてよい？)．$\pi=[\pi_1,...,\pi_K\]$です．
最後に以下の式でmemoryの重みづけ和を取り，ソフトに用いるメモリを選択して後段のdecoderに渡します．
```math
\text{m}_{\text{final}} = \sum_{k=1}^{K} \pi_k \text{m}'_k \tag{4}
```

## (B)オリジナルデータシーケンスから複数パターンのデータを再生成する機構
　(A)よりデータを再生成する機構を学習しました．
しかし実用上では，上述のDiversity Promotorによる$\pi$をDecoderに用いることは出来ません．
なので**Encoderが出力する各memoryをそのままDecoderに入れます**．
各memoryはデータシーケンスから抽出された複数パターンの表現を記憶しているはずなのでよいよね，という考えだと認識しています．ここでdecodeにおいて二つの工夫(mode)を考えます．
##### 制限モード
- decodeを，入力シーケンスが包含するパターンに限定します
- これはある種の活用的decodeといえます
##### 一般化モード
- 制限モードとは対照的に，decodeパターンに制限は加えません
- これは探索的decodeといえます

以下に例を記載します．
例えば[1,2]と[2,6]というパターンがオリジナルのデータセットにあるとして，[1,2,3,4,5]をdecodeする際に，オリジナルには存在しない[1,2,6]というパターンにdecodeされる状況を許容する(一般化)かしない(制限)かといった話になります．
著者はこのバランスを$\gamma$というパラメータで制御すると述べています．
(なんかできる気がするけど具体的な式が思いつかない...)

## (C)Model-Awareなデータを作成する機構
　上述までの機構でデータシーケンスから複数のパターンを生成する準備は整いました．しかし生成されるパターンは実際に運用されるモデルと何ら関係性はありません．**そこで(C)ではDataset Personalizerなる機構を用意し，各モデルに対して個別化されたデータを抽出できるようDS4RSを拡張します**．これをDS4RS+と本文では呼称しています．具体的には，**モデル毎に各パターンに対して重みをつけ，重みが高いパターンに対しては大きく勾配が計算されるように損失関数を設計します**．数式で確認していきます．
　本文と紹介の順序は異なりますが，まずは以下の式を説明します．
```math
\mathcal{L}_{rec} = \sum^{|\mathcal{X'}|}_{i=1} \sum^{|p_i|}_{t=2}\text{w}_{i,t}\mathcal{L}_{next-item}(i,t) \tag{5} 
```
これは再生成したデータセット$\mathcal{X'}$を用いてモデルを学習するときの損失関数です．これは"あるパターン$i$の位置$t$に相当するアイテムをモデルが正しく推薦出来たか"を評価する式です．つまりパターンの数×パターン内のアイテム数個分$\mathcal{L}_{next-item}$が計算され，summationされた結果が評価値となります．ここで注目すべきは重み$\text{w}\_{i,t}$の存在です．**この重みにより学習に重要なパターンをモデル単位で動的に変化させることができます**．つまりあるモデルにとってはパターン[1,2,3,4]における3の学習を重視させたり，他方のモデルでは2の学習に注力する，といった具合です．ではこの重み$\text{w}$と損失$\mathcal{L}$の形を具体的に確認していきます．
　重み$\text{w}$はDataset Personalizerという機構で学習されます．
```math
\begin{align}
z &= g_\phi(\text{h}^{i}_{t}) \\
\hat{z} &= \text{Softmax}(z + G) / \tau \tag{6}\\
\text{w}_{i,t} &= \hat{z}_1
\end{align}
```
ここで$g_{\phi}$はMLP，$\text{h}^{i}\_{t}$はパターン$i$の位置$t$のアイテムにおけるターゲットモデルのEmbedding，$z\in \mathbb{R}^{2}$はロジット値，$G$はガンベル分布からサンプリングされたノイズ(モデルの頑健性を上げるため)，$\tau$は温度係数，$\hat{z}\_1$は$\hat{z}$の第一要素です．$\hat{z}$は2次元のロジットでsoftmaxを通っているため，$\text{w}_{i,t}$は確率値となります．ガンベルノイズや$\tau$は学習の安定性や未学習・過学習を抑制するための工夫ですね(deep系でよく入れるし恐らく)
　一方で損失は以下の形で表現されます．
 ```math
\mathcal{L}_{next-item}(i, t) = -\log(\sigma(\text{h}_{t-1}^{i} \cdot \text{v}_{t}^{i})) - \sum_{v_j \notin p_j }\log(1-\sigma(\text{h}_{t-1}^{i} \cdot \text{v}_{j})) \tag{7}
 ```
 ここで$\text{v}^{i}\_{t}$はモデルが出力したパターン$i$の位置$t$におけるアイテムEmbedding，$\text{v}_{j}$は正解ではないアイテムのEmbeddingです．(パターン中からランダムサンプル)．一項目は正例に対する損失，二項目は負例に対する損失をそれぞれ計算している部分になります．つまり"**一つ前時点のアイテムEmbeddingと，正解アイテムのEmbeddingが近づくように**"学習が進むと考えることができます．(逆もまた然り)
　sequential recommendationをこのような距離学習の枠組みでとらえる損失関数を見たことが無かったので，いろいろ疑問は浮かび上がってきますが個人的には興味深いです．最後のアイテムの情報さえあれば次に推薦するアイテムは予測できるってことを言っているのだと思いますが，それで十分なのかなぁ見たいな気持ちにはなります．(ただ学習と推論のコストがぐっと下がりますね)．あとこれ負例項にsummation入っているけど"randomly sample one negative item"って文中にあるから実質なくてもいいのかな？
　ここで目的関数(5)式をよく見るとあることに気づきます．**$\text{w}\_{i,t}$が小さくなれば目的関数の値自体はモデルの良しあしに依らず小さくできる**ということです．なので本問題は$\text{w}\_{i,t}$と目的関数全体の2レイヤーを同時に最適化します．
 (bi-level optimization，つまり2レベルさいてきかというらしい)

 # 評価の結果は？
　以下がメインの評価結果です．
主にpublicなデータセットを用いて(amazon review datasetとYelp，amazon review datasetからBeauty, Sports, Toysの3カテゴリを利用)複数モデルに対してDS4RS, DS4RS+を適用した結果を比較しています．モデルにはRNN系のGRU4Rec，Transformer系のSASRec，ノイズ除去系のFMLP，Graph系のGCE-GNN，対象学習系のCL4SRecを採用し，ベースラインとして同じくdata-centricな手法である∞-AEとMELTを採用しています．指標はRecall@10,20とnDCG@10,20です
 ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/398379/7999e72a-cdf2-4341-8726-0ce27f45fcad.png)
　結果を見るとDS4RSを導入することで少なくとも何もない状態よりは精度が有に向上し，ベースラインを上回るケースもかなり多いことが見て取れます．さらにDS4RS+に拡張することでより高精度な推薦が可能になることも示唆されています．この結果から筆者らはmodel-centricとdata-centricはそれぞれ相互に補完的に作用するため(各々で個別に精度向上が見られるため？的な？)sequential recommendationの進化がdata-centricな観点で今後加速する可能性があると結論付けています．

　他にも以下のような分析結果が掲載されていました．
 以下はregenerationとpersonalizerにより得られたデータセットからランダムに25シーケンス抽出したのち，**personalizerがその25データセットに対しアサインしたスコアをモデル毎に可視化した図**となっています．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/398379/20c4052f-f556-44aa-9292-84c35b216a28.png)
x軸が各シーケンスの長さで，y軸が抽出された25個のシーケンスidです．(一つ長い棒plotがありますがこれはシーケンス長が長いことを意味します)
これを見ると，各モデル毎に付与されたスコアは動的に変化し，特にGRU4Recでその分散が最も高いことがわかります．筆者によるとこれはAttention機構やFillter-enhancedなMLPが各アイテムの重要度をある程度学習してしまうからだそうです．つまりそのような機構を明示的に持たないGRU4Recではアイテムスコアの分散が大きくなるという理屈です．本機構をオプションとしてプラスしてやることで注意機構を後付けできるみたいな価値もあるのでしょうか．

# 所感
- ベストペーパーに選出されるだけあって扱うテーマが大きいというか，既存研究の焼き直しでは提案できないような内容に仕上がっており読んでいて面白かったです
    - 確かに"モデルよりもデータの方が大事だよね"とみんなが経験則的に感じている中で，必要な観点だなぁという納得感がある
    - ただ図が説明している内容/例が文中で説明されているアルゴリズムと異なっていたり，notationの統一が少し甘かったりと全体的に読解しづらいかなと思いました
- 一方で産業的な面から考えると，実用に耐えうるかは微妙？なのかなとも思ったり
    - リッチなモデルはいろいろと提案されてきているけど実運用しているシステムに乗せるのはリソース的な面でハードルが高いので結局シンプルなモデルに落ち着くみたいな話はよく聞く
    - 本手法においてもモデル学習以外にパターン抽出用の学習が必要なので時間的制約には引っ掛かりそうだなぁと
- こういったpaperがawardを受賞する背景を考えると，モデルそのものに対して何かしら工夫をするというよりかは，業界全体として新しい方向性を模索しているような空気を感じます
    - RecSysのBestPaperからもそんな雰囲気を感じるような

実装は以下　
- https://github.com/USTC-StarTeam/DR4SR