これなーに
LightSANsのメモ。
論文：Lighter and Better: Low-Rank Decomposed Self-Attention Networks for Next-Item Recommendation
学会：Association for Computing Machinery(2021)
筆者：Xinyan Fan et al.
概要
詳細
1. 論文概要
Self-Attention Networks（SANs）はアクションの順序を考慮した推薦システムに非常に多く適用されているが、以下の制約により限界がある。
(1) セルフアテンションにおいて、二次関数的に処理が複雑になることとOver-parameterization(パラメータに対して十分な学習データが存在しないような状況)に対する脆弱性。
(2) 位置エンコーディングによる順序性の利用の困難さ。
本論文では、これらの問題を克服するための低ランク分解セルフアテンションネットワーク（LightSANs）を提案する。
特に、ユーザーの履歴内のアイテムを少数の一定の潜在空間に射影することで、アイテムと関心の間の相互作用を利用して文脈に応じた表現を生成するLow Ranked decomposerd self-attentionを導入した。
これは、時間と空間の観点から、ユーザーのアクション履歴の長さを線形的にスケーリングできるため、オーバーフィットに対して効果的である。
さらに、アイテム間の順序関係をより正確にモデル化するdecoupled position encodingを導入した。
LightSANsを3つの実データセットで検証し、精度と効率の両方の面で他の手法よりも優秀であった。
2. 導入
時系列を考慮したレコメンドシステムはECサイトやMovie配信サイトにおいて、近年注目があがっている。
これに対し、RNNやCNNを用いた様々な手法が考案されてきた。
特に近年、Self-Attention Network(SANs)がより有望な方法として注目を集めている。
SANsは、ユーザーの過去の行動を全て用いて、ユーザーの興味を推定する。
しかし、SANsの代表であるSASRecやBert4Recは以下の2つの弱点が存在する。
1) 過去のアクションの全てが必要であり、膨大なデータが必要となる。 そのため、計算コストが非常に大きくなる。
また、Over-parameterizationになりやすい。
アイテムのアクションはロングテールになりやすく、多くのアイテムは十分なアクション数に足りず、学習において十分に考慮されないケースが多い。
2) 通常のSANsは、アイテムのエンべディングと位置のエンべディングを足して利用されるが、近年の研究では絶対的な位置を利用することがあまり意味をなさないという指摘がある。
よって、この位置エンべディングの利用はノイズを増加させてしまうと考えられる。
LinformerらやRerformerらがSANsの改良を試みており、これらのアプローチはSANsの効果を直接向上させることを目的としている。
しかし、ユーザーの行動の特性に対する改善ではなく、上記の課題を直接解決するものではない。
本論では、ユーザー履歴に対しLow-Rank Decomposed Self-Attention Networksを活用して高速化を図る新しい手法LightSANsを提案する。
具体的には、ユーザーの履歴に含まれるアイテムの大部分は、k（小さい定数）以下の潜在的な興味でカテゴライズできると仮定する。
「潜在的な興味」とは、特定のアイテムグループに対するユーザーの好みを表すもので、本研究ではユーザーのアイテムの埋め込みのシーケンスから生成されるベクトルである。
この性質に基づき、低ランク分解セルフアテンションを導入する。
ユーザーのアクション履歴をkの潜在的な興味空間に射影し、各アイテムk個の潜在的な興味間の相互作用を持つものとして扱う。
これにより、SANsの時間と空間の複雑さは、ユーザーのアクション履歴の長さに関して線形となります。
同時に、アイテム同士の直接的な相互作用を避けることで、Over-parameterizationに対して堅牢にする。
一方で、提案するdecoupled position encodingによって位置エンべディングを作成することで、アクションしたアイテム同士の位置関係をモデルに取り入れる。
これはノイズの多い相関を排除することができるため、意味のあるユーザーの順序のパターンの把握ができる。
我々の主な貢献は以下。
- 2つの利点を持つLightSANsの提案。
(1) low-rank decomposerd self-attentionを利用した、これまでのSANsよりも文脈を考慮した効率的かつ正確性の高いモデルの作成。
(2) decoupled position encodingを利用することでのアイテムの順序性の更なる活用。
- 実際のデータセットで、他の手法よりも効果的で効率的であることの実験。
2. APPROACH
本節では、次のアクションが発生するアイテムの推薦に焦点を当てる。
ユーザー:uのアクションの履歴が以下として与えられるとする。
この時、t+1のアイテムを予測したい。
我々は、この予測に対し、精度向上と効率的な手法の発見を目的とする。
具体的には、アイテムの関連性の正確なモデリングのため、low-rank decomposed self-attentionと、およびアイテムの順序関係の明示的なモデリングのためのdecoupled position encodingを活用するLightSANsを提案する。
図1にLightSANsの全体的なフレームワークを示す。
詳細は次の節で説明する。
図1: LightSANsのフレームワーク
2.1 Low-Rank Decomposed Self-Attention
アクション履歴の文脈を把握するために利用する。
アクション履歴をk個の潜在空間に写像するものであり、潜在空間上の相互作用でアクション履歴の文脈を把握する。
これにより計算の複雑さを、O(n2)[アイテム数 * アイテム数]からO(n*k)[アイテム数 * k次元]に削減し、Over-parameterizationの課題を軽減します。
2.1.1 アイテムを潜在空間に集約する
我々はユーザーのアクション履歴であるアイテムを少量のk個の潜在空間に集約することができると仮定している。
そこで、学習可能な
という写像関数を提案する。
これは、過去のアクションしたアイテムを潜在空間に集約するためのものである。
アイテムのエンべディング行列をH ∈ Rn×d[n: アイテム数, d: 次元数]入力に、
へと変換する計算を実施する。
ここで、θはk*d次元の学習可能なパラメータである。
次に、分布Dを使用して入力アイテムの埋め込み行列を集約し、潜在空間の表現行列
を計算する。
※： Hがnd次元で、これをH~のkd次元に変換したいので、nk次元のDを転置してHと内積を取ることで、kd次元にしている。Dは上の式を当て嵌め。
まず、f(H)により、H(n *d次元)が低次元のH~(k * d次元)に変換される。
これにより、行列のサイズを落とすことができる。
さらに、H~の潜在空間に集約することは、式2に従って、アイテムの順序に反映されるユーザーの全体的な好みを捉えるため、直接的に全てのアイテムを利用するよりも効果的である。(学習可能なパラメータを通って潜在空間に写像されているため、次のアクションを予想しやすい集約になっている。)
この結果、出現頻度の低いアイテムに関連するアテンションの重みの考慮が減り、Over-parameterizationの問題を軽減して、より正確なレコメンドが可能になる。
この方法でのアイテムの潜在空間への集約は、Linformer [16] の低ランク線形マッピングに似ている。
しかし、2つの違いがある。
まず、パラメータθの次元数が我々はk *d次元であるのに対し、Linformerらはn * k次元で扱っている。
nはアイテムの数であるため可変であり、これは様々なパターンに対応するのが困難であると考える。
次に、アイテムの潜在空間への集約は、Linformerは直接の線形変換で実施しているが、我々はアイテムと潜在的興味の間の学習可能な関連性の分布を通じて、アイテムを潜在的興味の空間に投影する。
アイテムを潜在空間に写像することは単純な線形変換では困難であり、学習可能なパラメータでの写像がより効果的である。
2.1.2 アイテムから潜在空間への相互作用
過去のアクションXを、W_q, W_k, W_v(Rd * d)を用いて、3つの行列 Q, K, V（Rn * d）に変換する。
これをlow-rank decomposed self-attentionの入力とする。
KとV(n *d)は通常のmulti-head attentionでK~とV~(k * d)に以下を用いて変換する。
ここで、hはmulti-attentionのheadの数、iはheadのIDを指す。
{S1~ 〜 Sh~}は最終的にeS として連結され、文脈に応じた表現となる。
このmulti-head attentionの層を利用することで、アイテムと文脈の相互作用の取得が可能である。
※ ここマジで理解できない。。。
これにより、self-attentionの複雑さは、O(n2)からO(n×k) に削減でき、「アイテムがk個のどの潜在空間に作用するか」にだけに注力できる。
Linformerらは、同じようなアプローチをしているが、パラメータが n * k次元であり、アイテムの長さが可変であるnの値を利用しているため過去のアイテム長が異なる場合に対応するのが困難である。
(nを多めに取って、固定化してしまえば良いのでは？？)
また、他の研究でもn * k次元で扱うことを狙うものもあるが、長いシーケンスに対する実行コストは依然として膨大という課題が依然として残っている。
2.2 Decoupled Position Encoding
従来のSANsでのレコメンドは、アイテムのエンべディングと位置のエンべディングを足し上げて利用する。
そのため、i番目のアイテムとj番目のアイテムの関係性は、
となり、
に展開される。
アイテムと位置の情報は、E * PとP * Eで表現されるが、これは非常に単純な計算で時系列性を捉えるには少し心許ない。
これに対し本論では、Decoupled Position Encodingを導入し、アイテムのエンべディングと位置のエンべディングを独立して利用する以下で扱う。
ここで、f()は「2.1.1 アイテムを潜在空間に集約する」に出てくる式で、A~は、「#### 2.1.2 アイテムから潜在空間への相互作用」に出てくる式で計算するアテンション機構である。
また、EWはアイテムのエンべディングを指しており、アイテムと位置のアテンション機構の両方にかかる。
（なぜ位置情報側にアイテムのエンべディングが使われているかというと、位置関係にはアイテムの情報が影響を与えるからだと考えられる。例えば連ドラの試聴とかはアイテム情報があると推論しやすいよね。）
この式から、アイテムのアテンション機構と位置のアテンション機構が分離されており、独立して扱うため、従来のアイテムと位置の行列を足した上でのアテンションよりも位置情報をより詳細に利用できる。
また、位置に関するAttentionの重みは、一度計算するとユーザーやアイテムに関係なく再利用できるため、計算コストが非常に低くて済むため、モデルのトレーニングやテストが効率的に行える。
2.3 Prediction Layer And Loss Function
Transformer同様、各Self-Attention層の後に、非線形性を持たせるために全結合のフィードフォワードネットワークを適用して予測する。
入力はS~で結果がF~となる。
1番目からt番目のアイテムを入力に、各アイテムのアクション確率を以下で計算することで、t+1番目のアクションアイテムを予測する。
最終的に実際の正解データと比較することで、Lossを計算する。
gはGround Truthで、Iは全アイテム数を指す。
3. 実験
3.1 実験設定
3.1.1 データセットと実験の概要
Yelp, Amazon Books, ML-1Mの3つのデータセットで実験した。
各データセットの概要は以下である。
先行研究にならい、leave-one-outでデータを学習と検証に分割し、HIT@KとNDCG@Kで評価した。
テストデータの各ユーザーで全アイテムを推論し、そのTOP KでHITとNDCGを評価する。
また、比較対象の他のアルゴリズムはRecBoleを用いて実験している。
LightSANsのコードは、RecBoleに実装してオープンソースにしている。
3.1.2 ベースラインモデル
二種類のベースラインを比較対象とした。
(1) general sequential recommendation: Pop/GRU4Rec/NARM/SASRec/Bert4Rec
(2) effecient Transfoemers: Synthesizer/LinTrans/Linformer/Performer
(2)の一部を紹介する。
Linformerは、線形写像を使用して、キー(K)と値(V)の長さの次元をnからkに削減する。
しかし、アイテム長nを固定する必要があるため、入力数を制限する必要がありこの長さをかえる場合に再度学習する必要があるのが課題である。
Synthesizerは、2つのランダムに初期化された低ランク行列のを用いて合成する重みを利用する。
また、Performerは、FAVOR+アプローチを使用して、フルスケールの注意カーネルを近似する。
※不明。。。
この二つは、LightSANsがアイテムの長さnを削減することに対し、中間層での次元数dを削減することを狙っている。
Linear Transformerは、自己注意のカーネルベースの定式化と、行列積の結合的な性質を使用して、Attentionの重みを計算する。
これは計算の複雑さをO(n2)からO(n * d)に削減でき、nがdよりも十分大きい場合に複雑さの軽減の恩恵を大きく受けることができる。
3.2 結果
3.2.1 効果の評価
以下が全体の結果である。
(2)の方が(1)よりも全体的に結果がよい。
LightSANsとLightSANs-ape(Absolute Position Encodingで、Decoupled Position Encodingを用いていない場合との比較用)は、他手法と比較して良い結果となっており、Low Rankの有用性を示している。
また、LightSANsとLightSANs-apeの比較では、LightSANsの方が良い結果となっており、Decoupled Position Encodingの有用性を示している。
GRU4RecとNARMは、PopとFPMCよりもよく、NNの利用が効果的であることがわかる。
NARMはGRU4Recよりもよく、Attention機構が効果的であることがわかる。
3.2.2 効率の評価
効率性の評価は、SASRecとLightSANsの比較で実施する。
平等に評価するため、SASRec/LightSANs/LightSANs-apeのパラメータ数を揃えている。
GFLOPsから、LightSANsがSASRecよりも高速に計算できている。特にML-1Mデータセットで2倍近い効率性となっている。
LightSANsとapeの比較では、apeの方が早い。ここは、位置エンコーディングの正確性による精度とのトレードオフとなっている。
さらに、メモリの利用量も比較した。
Sequenceの数とbatchサイズを変えながら、メモリ利用量を確認している。
SASRecとそれ以外だと、Sequence数とbatch_sizeの増加に大きな差異があり、計算量の軽減が大きな影響を与えていることがわかる。
3.3 パフォーマンスにおける詳細な確認
本節での結果を以下に示す。
Decoupled position encodingの効果
位置エンコーディングなし、絶対位置エンコーディング、相対位置エンコーディングと提案手法を比較する。
位置エンコーディングなしは、大きく精度が劣化しており、絶対と相対位置エンコーディングも提案手法の方が全体的に良くなっている。
ここから、位置エンコーディングの重要性と、Decoupled position encodingの効果が確認できた。
アイテムの潜在空間への写像(low-rank decomposed self-attention)の効果
Low-rankの箇所を取り除いた場合と、SVDを用いた場合を比較しても、LightSANsの結果がよく、low-rank decomposed self-attentionの効果が確認できた。
4. 結論
本論ではLightSANsを提案した。
他のSANsの手法と比較して、精度と効率性の良いアルゴリズムであることが確認できた。
今後は、入力アイテム数が1000を超えるような場合でのテストなどをしていく予定。
また、userのモデルを用いた改良などもしていきたい。
以上。
Low-Rankで扱うとノイズを除去れるので、本質的に必要なデータでの予測ができて精度が上がるんだと思われる。
