MIND備忘録~Tmallが採用しているレコメンドアルゴリズム~

本日紹介する論文はこちら
[Multi-Interest Network with Dynamic Routing for Recommendation at Tmall](https://arxiv.org/abs/1904.08030)

## 0. 所感と概要
* 現在、主流のベクトル化Recallのアルゴリズムの1つとして、youtube DNNなどがある。しかし、ユーザーの興味を単一のEmbeddingとして表現するだけであり、ユーザーのさまざまな特徴付けるのに十分ではない。この論文は、ユーザーの興味を特徴付ける複数のEmbeddingを同時に生成するMINDを提案し、Recallフェーズを改善する。
* アリババのDINと比較してユーザーの行動をクラスタリングすることで、さらに改善した。(ユーザ行動のクラスタリングとあるが、本質的は商品特性のにソフトクラスタリング)
* 従来のアプローチでは，スパースなデータセットに対しては協調フィルタリング方式(CF)の性能が悪く，Matrix Factorizartion(MF)(協調フィルタリングにおいて次元削減を実現する手法)の計算量が多いという問題がありました。
* 一方、DNNアプローチユーザーの特性を低次元のベクトルで表現することに限界がある。多趣味なユーザーにおいては情報を失うことになる。
* DINのself attentionアプローチは、ターゲット製品ごとにattend to globel itemsができる。そして、最後にシグモイドをかけCTR(クリック率)を予測する。速度は遅いが、ランキングの精密ソートに適している。
* MINDの主なタスクはDINのそれとは異なり、MINDはユーザーベクトルを出力する役割を担っています。同じベクトル空間にユーザembeddingとアイテムembeddingが存在する。これにより、高速でおおよそのおすすめ商品の範囲を知ることができる。ランキングのざっくり選別するのに適している。
* dynamic routingが関心クラスタリングカプセルを出力した後、label-aware attetionで学習することでターゲットアイテムをinterest capsulesの線形モデルとして表すことができる。 Kは対象アイテム、QとVはinterest capsules。
* 特定のユーザー関心クラスタの数を動的に調整することができます。 レコメンデーションシステム環境では、ユーザの行動のシーケンスの長さが可変であるため、ユーザの行動の長さは必ずしも固定ではありません。dynamic routingを改善しfixed shared weightを使うことで、未知のアイテムもネットワーク入力として利用できるようになります。
* Airbnb real-time personalizationの手法と似ており、リアルタイムでマッチングを行うための現在の主流のアプローチは、基本的にはユーザーとアイテムのembeddingを同一ベクトル空間で学習する。その後、内積を使用して迅速に比較することが可能になる。また、ユーザーの行動の変化を反映させるために、ユーザembeddingの構造を入力することで可変長に対応が可能、もしくは最近N個の固定構造を取る。

## 1.背景
Tmallのレコメンデーションプロセスでは、RecallとRankingに分割されます。
![](https://i.imgur.com/fK1tYkz.png)


この論文は、Recallアルゴリズムに焦点を当ていまう。Recallフェーズの目標は、ユーザーの関心に密接に関連する何千もの製品候補セットを取得することです。Tmallシナリオでは、ユーザーは毎日何百もの商品とやり取りしており、ユーザーの興味は多様です。次の図に示すように、ユーザーごとに興味や関心が異なり、同じユーザーでもさまざまな興味を示します。
![](https://i.imgur.com/RkPZ0qM.png)


したがって、ユーザーの興味をモデル化することは非常に重要です。現在、Recallの主流のアルゴリズムは、協調フィルタリングとベクトル化Recallです。協調フィルタリングは、スパース性の問題に直面しています(全体のデータは大規模だが意味のあるデータはごく一部)。youtube dnnなどのベクトル化されたRecall方法は、ユーザーの興味を固定長のベクトルとして表現します。

ただし、Tmallシナリオでは、ユーザーの多様な利益のために、Embeddingの長さが十分な特性化機能を持つのに十分な長さでない限り、Embeddingではあんまり有効ではない。さらに、1つのEmbeddingのみが特定のヘッド効果を引き起こします。Recallの結果は、より人気のある分野の製品をレコメンドすることが多く、比較的ニッチなフィールドの製品の場合、レコメンド能力は不十分です。

上記の問題を解決する方法も非常に簡単で、複数のEmbeddingを作るだけ、この記事で紹介するMINDは、ユーザーの興味を表す複数のEmbeddingを生成し、Recallフェーズの効果を改善する。

## 2.MIND
### 2.1 Problem Formalization
Recallフェーズの目標は、ユーザーの要求ごとに、10億レベルの商品プールIからユーザーの関心を満たす数十万の商品候補セットを選択することです。各サンプル（Iu、Pu、F i）として表すことができます。

* Iu：ユーザuによって対話されたアイテムの集合を表す（ユーザ行動履歴）
* Pu：ユーザーuの基本的なプロフィールを表す(ユーザーの性別や年齢など)
* Fi：対象アイテム（アイテムIDやカテゴリIDなど）

次に、MINDのコアタスクは、ユーザー関連の機能を一連のユーザーの関心ベクトルに変換することです。(**MINDの特徴、同じベクトル空間にユーザembeddingとアイテムembeddingが存在する**)
$$　　
V_u = f_{user} (I_u, P_u ) \cdots (1)   
$$

$$
V_u =(\vec{v_u}^1,\cdots,\vec{v_u}^K)\in \mathbb{R}^{d×k}
$$

dは次元数を表す．Kは表現ベクトルの数。K = 1 の場合、YouTube DNN のように 1 つの表現ベクトルを使用します。


そして、対象アイテム表現ベクトルは$F_i$は次のようにEmbeddingで変換される。
 $$
 \vec{e_i} = f_{item}(F_i) \cdots (2)  
 $$
 
$$
\vec{e_i} \in \mathbb{R}^{d×1}
$$


ユーザーと商品のベクトル表現を取得した後、次のスコア式によってtopN商品候補セットが計算されます。
$$
f_{score}(V_u-\vec{e_i})  = \max_{1\leq k \leq K} \vec{e_i}^T\vec{v_u}^k
$$


MIND全体のフレームワークは次のとおりです。
![](https://i.imgur.com/YZcjUi7.png)


### 2.2 Embeddingレイヤー
上記のように、入力MINDは、3つの部分、ユーザプロフィール情報$P_u$、ユーザ行動情報$I_u$、及び対象アイテム$F_i$。各情報($P_u$,$I_u$,$F_i$)にはカテゴリ特性がそれぞれ含まれており、カテゴリ特性はEmbeddingに変換されます。ユーザプロフィール情報の部分では、$P_u$からのユーザID,年齢,性別などEmbeddingされたid特徴を結合し$\vec{p_u}$を作る。ユーザー行動$I_u$における製品とターゲット製品$F_i$について、製品ID、ブランドID、ストアIDなどがEmbeddingに変換された後、Global Average Poolingレイヤーを通過して、Embed Featuresを取得します。
$F_i$は$\vec{e_i}$、$I_u$は$E_u = {\vec{e_j},j\in I_u}$に変換される。

* PytorchによるEmbeddingの例

```python
import torch
import torch.nn as nn
import torch.nn.functional as F

# 各種ItemやID
send_idx = [1, 3, 2]

# num_embedding:埋め込み辞書のサイズ(send_idxのサイズ+1)
num_embedding = 4

# embedding_dim:各埋め込みベクトルのサイズ
embedding_dim = 3

embedding = nn.Embedding(num_embedding, embedding_dim)
input = torch.LongTensor(send_idx)

x = embedding(input).view(1, 3, 3)
''' 
tensor([[[ 1.8854,  0.4172,  0.1114],
         [ 2.0735,  0.6167, -0.0153],
         [ 0.0324,  0.9363, -1.1145]]], grad_fn=<ViewBackward>)
'''
# Global Average Pooling
F.avg_pool2d(x, kernel_size=(3,1))

'''
tensor([[[ 1.3304,  0.6567, -0.3395]]], grad_fn=<AvgPool2DBackward>)
'''
```
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/335356/f86af71b-e092-2c1e-36c8-eada143653ec.png)


### 2.3 Multi-Interest Extractor Layer
次は、Hitonによって提案されたカプセルネットワークを利用した最も重要なMulti-Interest Extractorレイヤーです。

* カプセルネットワークとは
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/335356/e7bb2f6c-1b5c-1d47-25dd-e69070cd1296.png)


カプセルネットワークは従来のニューラルネットワークに似ていることがわかります。従来のニューラルネットワークは、スカラーの束を入力し、最初にスカラーの束に重みを付けて合計し、非線形活性化関数を介してスカラー出力を取得します。カプセルネットワークの場合、ここでの入力は一連のベクトルです。最初に、このベクトルのグループがアフィン変換され、次に重み付けされて合計され、非線形の「スカッシュ」方程式によって変換されて、別のベクトルのグループの出力が得られます。 

* capsule   
 [論文](https://arxiv.org/abs/1710.09829)   
 [github](https://github.com/timomernick/pytorch-capsule)   
 [関連記事](https://www.slideshare.net/KazukiFujikawa/matrix-capsules-with-em-routing)   
 [関連論文1](https://www.cs.toronto.edu/~hinton/absps/transauto6.pdf)   
 [関連論文2](https://hci.iwr.uni-heidelberg.de/system/files/private/downloads/491388785/carsten_lueth_em_routing_slides.pdf)

CNN はプーリング層によって translation-invariance を獲得していますが、その代償として異なる特徴間の相対的な位置関係などを学習することが難しくなっています。CapsNet は CNN が抱えるこうした問題を解消するものとして提唱されました。

* Capsuleロジック
<img width="879" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/335356/5300dcd4-1c02-f291-0792-7b02ab1fb2b4.png">

```python
def __init__(self):
    # ランダムに重みを生成
    W = nn.Parameter(torch.randn(1, in_channels, num_units, unit_size, in_units))

def routing(self, x):
    # 入力を転置し, num_unitsに合わせてサイズ変更
    x = x.transpose(1, 2)
    x = torch.stack([x] * self.num_units, dim=2).unsqueeze(4)

    W = torch.cat([self.W] * batch_size, dim=0)

    # 各カプセルは自身の情報x,異なる重みWでアフィン変換をする u_hat = W*x
    u_hat = torch.matmul(W, x)

    # ロジック２行目 routing logitsをゼロに初期化
    b_ij = Variable(torch.zeros(1, self.in_channels, self.num_units, 1)).cuda()

    num_iterations = 3
    for iteration in range(num_iterations):
        # ロジック4行目 b_ijにsoftmaxをかける
        c_ij = F.softmax(b_ij)
        c_ij = torch.cat([c_ij] * batch_size, dim=0).unsqueeze(4)

        # ロジック5行目　S_j = ΣC_ij * u_hat
        s_j = (c_ij * u_hat).sum(dim=1, keepdim=True)

        # ロジック6行目 スカッシュ関数
        v_j = CapsuleLayer.squash(s_j)
        v_j1 = torch.cat([v_j] * self.in_channels, dim=1)

        # ロジック7行目 u_hat*v_j + b_ij
        u_vj1 = torch.matmul(u_hat.transpose(3, 4), v_j1).squeeze(4).mean(dim=0, keepdim=True)
        b_ij = b_ij + u_vj1

```


* スカッシュ関数

```python
def squash(s):
    mag_sq = torch.sum(s**2, dim=2, keepdim=True)
    mag = torch.sqrt(mag_sq)
    s = (mag_sq / (1.0 + mag_sq)) * (s / mag)
    return s
```

MINDのMulti-Interest Extractorレイヤーは、3つの主要な領域でカプセルネットワークとは異なります。

1. Shared bilinear mapping matrix   
 カプセルネットワークでは、各入力ベクトルと出力ベクトルの間に別々のアフィン行列を使います、MINDでは、アフィン行列は1つしかなく、すべてのベクトルは同じアフィン行列を使います。
$$
b_{ij} = \vec{u_j^T}S\vec{e_i}, i \in I_u,j \in (1,\cdots,K) \cdots (8)
$$
主な理由は、ユーザーの行動の長さが異なるためです。共有アフィン行列を使用すると、パラメーターを削減できる。また、変化にも対応しています。

2. Dynamic interest number
ユーザによって所有するカプセルの数が異なる場合があるため、異なるユーザー出力ベクトルKは、ユーザーの行動履歴の長さに基づいて適応的に計算されます。
$$
K_u' = max(1,min(K,log_2(|I_u|))) \cdots(9)
$$
上記はユーザーの行動履歴の長さに基づいて出力ベクトルKを計算される戦略は、関心の少ないユーザのために、コンピューティングとメモリのリソースを節約することができます

3. Randomly initialized routing logits
カプセルネットワークの重みの初期化は、ガウス分布$N(0,σ^2)$に基づいて初期化されます。K-Meansクラスタリングアルゴリズムの初期化を参考にしている。

次の図は、Multi-Interest Extractorレイヤー全体のプロセスです。
![](https://i.imgur.com/3umXIXn.png)

* 双線形写像行列Sの求め方は論文に記載れていない？

```python
def __init__(self):
    # 共通の双線形写像行列を使う ポイント１:Shared bilinear mapping matrix  
    S = torch.randn(1) * torch.ones((1, in_channels, num_units, unit_size, in_units))

def routing(self, x):
    # ロジック１行目 K_u',Kは指定可能(K=10,I_u=512)の場合K_uは9になる
    # ポイント２　Dynamic interest number 
    K_u = max(1,min(K,math.log2(I_u)))

    # ロジック２行目 routing logitsをガウス分布で初期化・・・ポイント３Randomly initialized routing logits
    b_ij = Variable(torch.empty(1, self.in_channels, self.num_units, 1).normal_(mean=0,std=1)).cuda()

    num_iterations = r
    for iteration in range(num_iterations):
        # ロジック4行目 b_ijにsoftmaxをかける
        w_ij = F.softmax(b_ij)
        w_ij = torch.cat([c_ij] * batch_size, dim=0).unsqueeze(4)

        # ロジック5行目　z_j_vec = Σw_ij * S * e_vec
        z_j_vec = (w_ij * S * e_vec).sum(dim=1, keepdim=True)

        # ロジック6行目 スカッシュ関数
        u_j_vec = CapsuleLayer.squash(z_j_vec)
        u_j_vec1 = torch.cat([u_j_vec] * self.in_channels, dim=1)

        # ロジック7行目 u_j_vec^T*S*e_vec + b_ij
        S_u_j_vec = torch.matmul(u_j_vec.transpose(3, 4), S)
        e_S_u1 = torch.matmul(S_u_j_vec, e_vec)
        b_ij = b_ij + e_S_u1


```

Multi-Interest Extractor Layerを介して、複数個のベクトル表現得られる。次に、各ベクトルはユーザープロフィールのEmbed Featureと結合される。2層の活性化関数ReLuを通過し、複数個のユーザ関心ベクトルを得られる。各関心ベクトルは、ユーザの関心の特定の側面を特徴づける。

### 2.4　ラベル対応アテンションレイヤー
前のステップでユーザ関心ベクトルが取得された後、ユーザごとに関心ベクトルの数が異なるため、Label-aware Attention Layerはこれらのベクトルに重み付けを行います（学習段階でのみ適用）。
![](https://i.imgur.com/n0wsCaC.png)


計算式は次のとおりです。
$$
\vec{v_u} = Attention(\vec{e_i},V_u,V_u) = V_usoftmax(pow(V_u^T\vec{e_i},p))
$$

```python
import torch.nn.functional as F

def attention(e_i,V_u):
    return torch.matmul(V_u,F.softmax(pow(torch.matmul(V_u.T,e_i),p)))
```

上の図のQはターゲット製品のEmbeddingに相当し、KとVはユーザーの関心ベクトルです。注目に値するのは、softmax中に、取得されたAttentionスコアが指数関数によってスケーリングされることです。pが0に近い場合（ベクトルの内積が1より大きいと想定する必要があります）、これはsoftmaxに対する平滑化効果であり、Attentionスコアのサイズは類似しています。p> 1で連続的に増加する場合、softmaxに対する処理はシャープな効果、最大の注意スコアを持つ関心ベクトル、sofamaxの後の対応する重みはますます大きくなります。このとき、一種の強いAttentionに似ています。つまり、最大のAttentionスコアを持つベクトルが直接選択されます。実験は、注意力が高い方が収束が早いことを発見しています。

### 2.5トレーニングとサービス
学習フェーズでは、Label-aware Attention Layerを介して取得したユーザーベクトルとターゲット製品のEmbeddingを使用して、ユーザーuと製品iの相互作用する確率を計算する（youtube DNNに似ている）。
$$
Pr(i|u) = Pr(\vec{e_i}|\vec{v_u})= {exp(\vec{v_u^T}\vec{e_i}) \over \sum_{j \in I}exp(\vec{v_u^T}\vec{e_j})}
$$

目的関数は次のとおりです。
$$
L = \sum_{(u,i)\in D}logPr(i|u)
$$


オンラインアプリケーションフェーズでは、ユーザーの複数個の関心ベクトルのみを計算する必要があり、各関心ベクトルは最近傍法（ローカルセンシティブハッシュLSHなど）を使用して最も類似した候補製品セットを取得します。同時に、ユーザーが新しいインタラクティブ動作を生成すると、MINDはユーザーの新しい関心ベクトルにリアルタイムで応答することもできます。

## 3.実験結果
次に、実験結果を見てください。

オフライン実験の場合、記事ではMINDモデルとBASEモデル（youtube DNNなど）が比較され、結果は次のようになります。
![](https://i.imgur.com/L1D0LiY.png)



オンライン実験では、比較のために、異なるレコメンドモデルがダウンストリームと同じランキングモデルを使用し、1週間以内に異なる実験グループのCTRを比較します。
![](https://i.imgur.com/uuHq4Aj.png)


ご覧のように、オンライン、オフラインであるかにかかわらず、MINDは良い結果を達成しています。

## 4.結論と今後の取り組み
本論文では、ニューラルネットワークの新しい構造、MINDを表現するために
10億人規模のユーザーとアイテムを含む電子商取引のレコメンデーションにおけるマッチング段階でのユーザーの多様な関心事を考慮している。

具体的には我々は，異なる動的ル多面性抽出器層作成し、ユーザーの多様な関心事を抽出しこれらの関心事はを使用して、新しいラベル認識型Attentionスキームで学習します。

オフラインを達成することを実証する実験が行われています。
公的なベンチマークで優れたパフォーマンスを発揮します。オンラインのCTRも
MINDの有効性と実現可能性を実証するために報告された

今後の作業については、2つの方向性を追求していきたいと考えています。
1つ目は行動時間などのユーザの行動シーケンスに関する情報をより多く取り入れることができるようにしたい。
2つ目の方向性は、動的ルーティングの初期化スキームを最適化することです。より良いユーザー表現を実現するためにK-means++の初期化スキームを参照しています。

参考記事:https://www.jianshu.com/p/5e339afbf2e7