+3

[Paper explained] NISER: Normalized Item and Session Representations to Handle Popularity Bias

Mayfest2023 ContentCreator

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 SS là một tập các session và II là tập gồm mm item mà ta quan sát được từ SS. Trong mỗi session sSs \in S, các click event được sắp xếp theo thứ tự thời gian s=(is,1,is,2,...,is,l)s=(i_{s,1},i_{s,2},...,i_{s,l}), trong đó, is,jIi_{s,j} \in I với j=1...lj=1...l là vị trí của item trong session ss. Một session ss có thể được mô hình hoá dưới dạng một đồ thị Gs=(Vs,Es)G_s = (V_s,E_s). Mỗi item is,jVsi_{s,j} \in V_s là một node trong đồ thị. Cạnh (is,j,is,j+1)Esi_{s,j},i_{s,j+1}) \in E_s là cạnh có hướng biểu diễn trình tự click từ is,ji_{s,j} đến is,j+1i_{s,j+1}. Cho một session ss, nhiệm vụ của Session-based Recommendation là phải dự đoán item is,l+1i_{s,l+1} mà người dùng có thể bằng cách tính toán một vector y^s,l+1\hat{\bold{y}}_{s,l+1} gồm mm-chiều tương ứng với mm item trong II. Sau khi tính toán xong, KK item có điểm số cao nhất sẽ được lấy để tạo một danh sách top-KK các item được recommend. Giả sử ta có II là tập hợp các video trên YouTube và một session ss có các item is,ji_{s,j} là một vài video nhạc Pop. Khi đó, trong vector y^s,l+1\hat{y}_{s,l+1} của session ss 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 ii sẽ được biểu diễn bằng một embedding vector gồm dd-chiều. Với mm item, ta có ma trận I=[i1,i2,...,im]TRm×dI=[i_1, i_2,...,i_m]^T \in \R^{m \times d} cần phải train. Với một session ss có danh sách item Is=[is,1,is,2,...,is,l]TRl×dI_s = [i_{s,1},i_{s,2},...,i_{s,l}]^T \in \R^{l \times d}, vector embedding của session ss sẽ được tính như sau: s=f(Is;θ)s=f(I_s;\theta) với θ\theta là tham số của hàm ff. Trong bài báo này, mục tiêu của tác giả là tính được ss sao cho gần với embedding is,l+1i_{s,l+1} của target item ik=is,l+1i_k=i_{s,l+1} với k=arg maxjijTsk=\text{arg max}_j i_j^T s với j=1...mj=1...m, tức là kk là chỉ số của vector iji_j sát với ss nhất thông qua phép dot product.

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

pk(s)=y^k=exp(ikTs)j=1mexp(ijTs)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(y^)=j=1myjlog(y^)L(\hat{\bold{y}})=-\sum_{j=1}^m\bold{y}_j \text{log}(\hat{\bold{y}})

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

3. Chuẩn hoá embedding

image.png

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 L2L_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ừ đó θ\thetaII 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.

image.png

Điều này là do softmax loss cố gắng học iki_k sao cho norm ik2||i_k||_2 cao để phép inner product ikTs=ik2s2cosαi_k^Ts=||i_k||_2||s||_2cos\alpha cho ra giá trị y^k\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 i~k=ikik2\tilde{i}_k=\frac{i_k}{||i_k||_2} và từ đó lấy được item embedding matrix đã normalize I~S\tilde{I}_S. Khi đó, session embedding sẽ trở thành s=f(I~S;θ)s=f(\tilde{I}_S;\theta) và cũng được normalize thành s~\tilde{s}.

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

y^k=exp(σi~kTs~)j=1mexp(σi~jTs~)\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 i~kTs~[1,1]\tilde{i}_k^T \tilde{s} \in [-1,1].

4. NISER

image.png

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 ss sẽ được biểu diễn bằng một đồ thị GsG_s. Ta sẽ có hai ma trận liền kề AsinRl,lA^{\text{in}}_s \in \R^{l,l}AsoutRl,lA^{\text{out}}_s \in \R^{l,l} tương ứng với cạnh vào và ra trong đồ thị GsG_s. Mạng GNN sẽ nhận AsinA^{\text{in}}_s, AsoutA^{\text{out}}_s và item embedding đã normalize I~s\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:

[i~s,1τ,i~s,2τ,...,i~s,lτ]=G(Asin,Asout,I~s;θg)[\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 θg\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:

image.png

với As,j:in,As,j:outR1×lA_{s,j:}^{\text{in}},A_{s,j:}^{\text{out}} \in \R^{1 \times l} là hàng thứ jj của ma trận AsinA_s^{\text{in}}AsoutA_s^{\text{out}}. H1,H2Rd×dH_1, H_2 \in \R^{d \times d}, W()W_{(\cdot)}U()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 zs,jtz^t_{s,j} là update gate, rs,jtr^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 i~s,jτ,p=i~s,jτ+pj\tilde{i}_{s,j}^{\tau,p} = \tilde{i}_{s,j}^{\tau} + p_j với pjRdp_j \in \R^d là positional embedding vector tại vị trí jj lấy từ ma trận P=[p1,p2,...,pL]TRL×dP=[p_1, p_2, ..., p_L]^T \in \R^{L \times d}, LL 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 αj=qTsigmoid(W1i~s,lτ,p+W2i~s,jτ,p+c)\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,cRdq, c \in \R^d, W1,W2Rd×dW_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 ss' được tính s=j=1tαji~s,jτ,ps'=\sum_{j=1}^t \alpha_j \tilde{i}_{s,j}^{\tau, p}. Embedding session cuối cùng sẽ là s=W3[s;i~s,lτ,p]s=W_3[s';\tilde{i}_{s,l}^{\tau, p}] với W3Rd×2dW_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-KK 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-KK 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.

ARP=1SsSiLsϕ(i)K\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.

image.png

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^*).

image.png

Đố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.

image.png

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.

All rights reserved

Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí