Nếu đã dùng qua các trang web như YouTube, có thể bạn đã từng để ý rằng một khi các bạn đã click vào một video nào đó, hệ thống của YouTube sẽ tự động gợi ý các video liên quan ở autoplay list hay là trang homepage. Điều này là do YouTube, dùng một Recommendation System để tự động gợi ý các video có độ liên quan cao đến video bạn vừa xem kể cả khi bạn đã login hay chưa login tài khoản Google. Nếu bạn chưa login hoặc dùng tab ẩn danh để xem video, YouTube vẫn có thể suggest các video liên quan ở ngay trong session của browser bởi Recommendation System của YouTube cũng có thể hoạt động theo cơ chế session-based, tức là chỉ sử dụng thông tin của session hiện tại để đưa ra các gợi ý.

1. Định nghĩa bài toán Session-based Recommendation

Gọi $S$ là một tập các session và $I$ là tập gồm $m$ item mà ta quan sát được từ $S$. Trong mỗi session $s \in S$, các click event được sắp xếp theo thứ tự thời gian $s=(i_{s,1},i_{s,2},...,i_{s,l})$, trong đó, $i_{s,j} \in I$ với $j=1...l$ là vị trí của item trong session $s$. Một session $s$ có thể được mô hình hoá dưới dạng một đồ thị $G_s = (V_s,E_s)$. Mỗi item $i_{s,j} \in V_s$ là một node trong đồ thị. Cạnh ($i_{s,j},i_{s,j+1}) \in E_s$ là cạnh có hướng biểu diễn trình tự click từ $i_{s,j}$ đến $i_{s,j+1}$. Cho một session $s$, nhiệm vụ của Session-based Recommendation là phải dự đoán item $i_{s,l+1}$ mà người dùng có thể bằng cách tính toán một vector $\hat{\bold{y}}_{s,l+1}$ gồm $m$-chiều tương ứng với $m$ item trong $I$. Sau khi tính toán xong, $K$ item có điểm số cao nhất sẽ được lấy để tạo một danh sách top-$K$ các item được recommend. Giả sử ta có $I$ là tập hợp các video trên YouTube và một session $s$ có các item $i_{s,j}$ là một vài video nhạc Pop. Khi đó, trong vector $\hat{y}_{s,l+1}$ của session $s$ này, các video nhạc Pop sẽ có điểm số cao hơn so với các video nhạc Rock hoặc các video không phải là ca nhạc.

2. Học biểu diễn của item và session

Trong NISER, mỗi item $i$ sẽ được biểu diễn bằng một embedding vector gồm $d$-chiều. Với $m$ item, ta có ma trận $I=[i_1, i_2,...,i_m]^T \in \R^{m \times d}$ cần phải train. Với một session $s$ có danh sách item $I_s = [i_{s,1},i_{s,2},...,i_{s,l}]^T \in \R^{l \times d}$, vector embedding của session $s$ sẽ được tính như sau: $s=f(I_s;\theta)$ với $\theta$ là tham số của hàm $f$. Trong bài báo này, mục tiêu của tác giả là tính được $s$ sao cho gần với embedding $i_{s,l+1}$ của target item $i_k=i_{s,l+1}$ với $k=\text{arg max}_j i_j^T s$ với $j=1...m$, tức là $k$ là chỉ số của vector $i_j$ sát với $s$ nhất thông qua phép dot product.

Công thức để tính xác suất item tiếp theo là $i_k$ là:

$$p_k(s)=\hat{\bold{y}}_k=\frac{\text{exp}(i_k^T s)}{\sum_{j=1}^m\text{exp}(i_j^T s)}$$

Để tính $\theta$, ta có thể tối ưu hàm cross-entropy loss:

$$L(\hat{\bold{y}})=-\sum_{j=1}^m\bold{y}_j \text{log}(\hat{\bold{y}})$$

với $\bold{y}\in \{0,1\}^m$, $\bold{y}_k=1$ tương ứng với đúng target item $k$.

3. Chuẩn hoá embedding

Theo [2], các features khi train bằng softmax sẽ có dạng hình tia như hình trên. Từ đó, bài báo suy luận rằng: các target item dễ đoán thường sẽ có chuẩn $L_2$ lớn hơn. Ví dụ như các item được click khá nhiều sẽ thường được click thường xuyên, từ đó $\theta$ và $I$ sẽ được huấn luyện để recommend các item này thường xuyên hơn dẫn đến hiện tượng popularity bias, các item phổ biến được recommend thường xuyên hơn so với các item không phổ biến. Điều này khiến cho performance của model giảm khi mà popularity (độ phổ biến) của item giảm.

Điều này là do softmax loss cố gắng học $i_k$ sao cho norm $||i_k||_2$ cao để phép inner product $i_k^Ts=||i_k||_2||s||_2cos\alpha$ cho ra giá trị $\hat{y}_k$ cao. Để giải quyết tình trạng này, tác giả bài báo chuyển sang dùng cosine similarity để đo độ tương đồng giữa item và session embedding thay vì dùng inner product. Item embedding sẽ được normalize $\tilde{i}_k=\frac{i_k}{||i_k||_2}$ và từ đó lấy được item embedding matrix đã normalize $\tilde{I}_S$. Khi đó, session embedding sẽ trở thành $s=f(\tilde{I}_S;\theta)$ và cũng được normalize thành $\tilde{s}$.

Khi đó, score của item $i_k$ sẽ được trở thành:

$$\hat{\bold{y}}_k=\frac{\text{exp}(\sigma \tilde{i}_k^T \tilde{s})}{\sum_{j=1}^m\text{exp}(\sigma \tilde{i}_j^T \tilde{s})}$$

với $\tilde{i}_k^T \tilde{s} \in [-1,1]$.

4. NISER

Trong bài báo này, tác giả dùng Graph Neural Network (GNN) để học embedding của item và session. Một session $s$ sẽ được biểu diễn bằng một đồ thị $G_s$. Ta sẽ có hai ma trận liền kề $A^{\text{in}}_s \in \R^{l,l}$ và $A^{\text{out}}_s \in \R^{l,l}$ tương ứng với cạnh vào và ra trong đồ thị $G_s$. Mạng GNN sẽ nhận $A^{\text{in}}_s$, $A^{\text{out}}_s$ và item embedding đã normalize $\tilde{I}_s$ làm input và trả về một tập các embedding sau $\tau$ bước propogate thông tin trên graph:

$$[\tilde{i}_{s,1}^{\tau},\tilde{i}_{s,2}^{\tau},...,\tilde{i}_{s,l}^{\tau}]=G(A_s^{\text{in}},A_s^{\text{out}},\tilde{I}_s;\theta_g)$$

với $\theta_g$ là trọng số của hàm GNN G. Với mỗi node, embedding của nó sẽ được cập nhật bằng embedding của nó và embedding của hàng xóm $\tau$ lần theo các bước sau:

với $A_{s,j:}^{\text{in}},A_{s,j:}^{\text{out}} \in \R^{1 \times l}$ là hàng thứ $j$ của ma trận $A_s^{\text{in}}$ và $A_s^{\text{out}}$. $H_1, H_2 \in \R^{d \times d}$, $W_{(\cdot)}$ và $U_{(\cdot)}$ là các tham số cần train. $\sigma(\cdot)$ là hàm sigmoid và $\odot$ là phép nhân element-wise. Đây chính là Gated Recurrent Unit với $z^t_{s,j}$ là update gate, $r^t_{s,j}$ là reset gate.

Để cho model học được thông tin về thứ tự của item, tác giả bài báo cũng dùng thêm cả positional embedding để thêm vào mỗi item embedding, từ đó lấy được embedding của item có thông tin vị trí của nó trong session cũng như session embedding. Item embedding khi đi thêm thông tin positional sẽ trở thành $\tilde{i}_{s,j}^{\tau,p} = \tilde{i}_{s,j}^{\tau} + p_j$ với $p_j \in \R^d$ là positional embedding vector tại vị trí $j$ lấy từ ma trận $P=[p_1, p_2, ..., p_L]^T \in \R^{L \times d}$, $L$ là chiều dài tối đa của tất cả các input session.

Ngoài ra, từng item ở trong session cũng được tính soft-attention weight $\alpha_j = q^T \text{sigmoid}(W_1 \tilde{i}_{s,l}^{\tau, p} + W_2 \tilde{i}_{s,j}^{\tau, p} +c)$ với $q, c \in \R^d$, $W_1, W_2 \in \R^{d \times d}$. Sau đó, các weight này cũng được normalize bằng softmax và session embedding trung gian $s'$ được tính $s'=\sum_{j=1}^t \alpha_j \tilde{i}_{s,j}^{\tau, p}$. Embedding session cuối cùng sẽ là $s=W_3[s';\tilde{i}_{s,l}^{\tau, p}]$ với $W_3 \in \R^{d \times 2d}$.

5. Thí nghiệm

Có 3 metric đánh giá sẽ được dùng để đánh giá model trong bài báo này:

• Recall@K: tỉ lệ item cần xuất hiện có trong top-$K$ các item có score cao nhất.
• MRR@K (Mean Reciprocal Rank): trung bình rank của item cần xuất hiện đứng thứ bao nhiêu trong top-$K$ item có score cao nhất. Giá trị MRR lớn sẽ thể hiện là item cần xuất hiện có rank càng cao trong recommendation list.
• Average Recommendation Popularity: độ phổ biến trung bình của item được recommend trong mỗi list.

$$\text{ARP}=\frac{1}{|S|}\sum_{s \in S} \frac{\sum_{i \in L_s}\phi(i)}{K}$$

Các bộ dataset được dùng là Yoochoose, Diginetica và RetailRocket. Có 2 cách đánh giá trong bài báo này:

• Offline setting: chia bộ dataset thành train và test set, train model và đánh giá như thông thường.
• Online setting: giống với cách các live system hoạt động, model sẽ được retrain mỗi ngày bằng cách thêm các session của ngày hiện tại vào bộ train set trước đó và đánh giá trên dữ liệu của ngày tiếp theo.

Có thể thấy từ kết quả, so với mô hình GNN bình thường, NISER đã cải thiện được hiệu năng của model khi dự đoán các item có độ popularity thấp (biểu diễn bởi $\phi^*$).

Đối với online training, NISER cũng thực hiện tốt hơn mạng GNN thông thường ngay trong những ngày đầu chạy.

Ngoài ra, NISER cũng cho ra ARP thấp hơn GNN, nghĩa là popularity bias của NISER thấp hơn, các item có popularity thấp cũng được recommend nhiều hơn.

Kết luận

Như vậy, bài báo đã cho thấy được rằng bằng cách normalize item và session embedding, ta có thể giúp cho model tránh được việc recommend các item đã quá phổ biến, cải thiện hiệu năng của hệ thống Session-based Recommendation khi popularity của item thấp.

Tham khảo

1. Gupta, Priyanka, et al. "NISER: Normalized item and session representations to handle popularity bias." arXiv preprint arXiv:1909.04276 (2019).
2. Zheng, Yutong, Dipan K. Pal, and Marios Savvides. "Ring loss: Convex feature normalization for face recognition." Proceedings of the IEEE conference on computer vision and pattern recognition. 2018.