Evaluation of recommender/recommendation Systems

 Note những thứ cần chú ý khi thực hiện evaluation cho hệ thống RS

Tham khảo các tài liệu

• Evaluating recommender systems [Zaier, Z. et al, 2008]
• Evaluation of recommender systems- A new approach [F.H. del Olmo et al., 2008]
• Evaluating recommender systems [Joost de Wit., 2008]
• A survey of accuracy evaluation metrics of recommendation tasks [Gunawardana, A. & Shani, G., 2009], Microsoft Research
• Beyond accuracy: evaluating recommender systems by coverage and serendipity [Ge M., 2010]
• Dimensions and metrics for evaluating recommendation systems [Avazpour, I. et al., 2014]
• Evaluation of recommender systems [Radek Pel´anek, 2015]
• Information and recommender systems, Wiley, ISBN: 978-1-84821-754-6, [Elsa Negre, 2015]

Trên Quora
https://www.quora.com/How-do-you-measure-and-evaluate-the-quality-of-recommendation-engines

Đo lường tính chính xác (performance measures)

Đánh giá hệ thống RS là việc quan trọng để xác định các thuật toán lựa chọn là hiệu quả và phù hợp với tập dữ liệu. Việc thực hiện có thể thông qua 2 dạng thực nghiệm/thí nghiệm (experimental research) vs. nghiên cứu bằng cách quan sát (non-experimental/observational research).

Non-experimental/observational research có thể tiến hành thông qua:

• Surveys/questionnaire
• Case studies
• Focus group

Phần sau chỉ focus vào experimental research.

Giả lập hành vi người dùng (simulating user behavior)

Để đánh giá thuật toán offline cần thực hiện giả lập quá trình online mà hệ thống thực hiện ra gợi ý cho tới khi người dùng sử dụng dự đoán (hay cách người dùng thực sự sử dụng recommendation). Việc này thường thực hiện bằng cách sử dụng dữ liệu quá khứ của người dùng và giấu đi một phần dữ liệu để giả lập người dùng sẽ thực hiện rate item như thế nào.

Việc sử dụng dữ liệu quá khứ ngầm giả định sở thích của user không phụ thuộc nhiều vào hệ thống RS. Có nghĩa cách người dùng thao tác với item không cần thông qua danh sách RS. Trong trường hợp chỉ đánh giá việc user thao tác thông qua danh sách recommendation list không thỏa mãn giả định này.

Trường hợp chỉ đánh giá chỉ thông recommendation list sẽ thực hiện online và sử dụng các metric như Click Through Rate (CTR). Nếu chỉ xem xét việc user chọn xem từ recommendation list sẽ có hạn chế quan trọng nhất là:

• Phải thực hiện theo dõi user behavior trước khi đánh giá
• Mỗi lần thay đổi RS phải thực hiện theo dõi lại và không thể dùng dữ liệu quá khứ do RS ảnh hưởng tới hành vi user.

Hold-out

Là một phương pháp thực hiện chia dataset thành 2 phần gọi là training set và test set. Những phần này có thể có tỷ lệ khác nhau. Việc thực hiện được tiến hành bằng cách chọn ngẫu nhiên một vài rating từ tất cả (hoặc một số) user. Phương pháp này còn gọi là leave-k-out.

Trong một số nghiên cứu, tỷ lệ này thường được chọn là 80% và 20%. Ví dụ dữ liệu người dùng truy cập movies trong 6 tháng sẽ được chia thành 2 phần:

• Một phần 5 tháng dùng để chạy recommendation
• Và data trong 1 tháng còn lại được dùng để đánh giá hệ thống.

Đôi khi tỷ lệ này được chạy từ 0.2 đến 0.95 với bước nhảy là 0.05 để tính toán cho từng trường hợp trước khi chạy trung bình để cho ra kết quả cuối cùng.

Leave-one-out

Là trường hợp của leave-k-out với k = 1. Với phương pháp này, một active user sẽ để lại một rated item. Kỹ thuật này có một số nhược điểm ví dụ như overfitting và có độ tính toán phức tạp

Overfitting có thể do training set size quá nhỏ hay/hoặc model quá phức tạp.

K-fold

Một biến thể khác của hold-out là m-fold cross-validation hay k-fold cross-validation. Với phương pháp này dataset được chia thành m fold (m phần) không chồng lấp. Với mỗi lượt một fold được chọn làm test set trong khi các fold khác dùng làm training set. Kỹ thuật này được cho là phù hợp để đánh giá hệ thống có người sử dụng mới.

Đo lường

Các chỉ số về độ chính xác theo thống kê (statistical accuracy metrics)

Đối với hệ thống dùng explicit feedback (hay rating) việc đánh giá RS có thể thực hiện sử dụng các metric liên quan đến thống kê. Hai cách đo lường sai số (độ đo sai số – error metrics) thường được sử dụng là Mean Absolute Error (MSE, tạm dịch sai số tuyệt đối trung bình) và Root Mean Squared Error (RMSE, tạm dịch sai số bình phương trung bình [căn] quân phương hay sai số quân phương).

Đây cũng là hai metric thông dụng nhất được sử dụng khi đo lường độ chính xác của dự đoán. Ví dụ hệ thống phát sinh $\hat{r}_{ui}$ là một dự đoán rating cho test set $\mathcal{T}$ của một cặp user-item ($u$, $i$) thực sự có rating là $r_{ui}$.

RMSE giữa giá trị dự đoán và giá trị thực tế là:

$RMSE=\sqrt{\dfrac{1}{\left|\mathcal{T}\right|}\displaystyle\sum_{(u,i)\in\mathcal{T}}{({\hat{r}}_{ui}-r_{ui})}^2}$

trong khi đó

$MAE=\sqrt{\dfrac{1}{\left|\mathcal{T}\right|}\displaystyle\sum_{(u,i)\in\mathcal{T}}\left|{\hat{r}}_{ui}-r_{ui}\right|}$

Tuy nhiên đo lường sai số thông thường không thích hợp lắm với trường hợp dataset dạng binary nhị phân.

Khi so sánh với MAE, RMSE bất lợi hơn khi gặp những sai số lớn.

Ví dụ 1 hệ thống với 4 rating ẩn, RMSE sẽ ưu tiên hệ thống sai 2 point (khoảng cách lỗi là 2) trong 3 lần rating và 0 (rating đúng) hơn hệ thống cho sai 3 point và đúng trong 3 trường hợp còn lại.

Normalized RMSE (NRMSE) và Normalized MAE (NMAE) là hai phiên bản của RMSE và MAE khi được chuẩn hóa bằng khoảng cách rating (ví dụ $r_{max}-r_{min}$).

$NRMSE=\dfrac{RMSE}{r_{max}-r_{min}}$
và
$NMAE=\dfrac{MAE}{r_{max}-r_{min}}$

Average RMSE và Average MAE là điều chỉnh để dùng với test set không cân bằng. Ví dụ nếu trong test set có mặt hàng phân bố không đều. Nếu có một error thu được từ mặt hàng phổ biến thì với cách tính thông thường lỗi này sẽ ảnh hưởng nặng nề lên chỉ số. Thay vì vậy sẽ tính RMSE hay MAE riêng lẻ cho từng item và sau đó lấy trung bình. Tương tự như vậy RMSE và MAE có thể tính riêng lẻ cho từng user nếu test set có dấu hiệu phân bố người dùng không đều.

Trong một số ứng dụng ngữ nghĩa của rating không chỉ đơn thuần tác động vào sai số bằng độ lớn của chính nó. Trong một số trường hợp $d(\hat{r},r)$ nên được biến đổi theo 1 cách phù hợp hơn là lấy bình phương của hiệu số hay trị tuyệt đối.

Ví dụ trong 1 số ứng dụng với 3 mức “thích”, “trung lập” và “không thích” thì việc giới thiệu một movie chẳng hạn mà người dùng không thích thì tồi tệ hơn việc không đề xuất. Trong trường hợp này một quy tắc như $d(3,1) = 5$, $d(2,1) = 3$, $d(3,2) = 3$, $d(1,2) = 1$, $d(2,3) = 1$, và $d(1,3) = 2$ sẽ cho kết quả hợp lý hơn.

Phản hồi ngầm định (implicit feedback context)

Đối với hệ thống RS dựa trên implicit feedback, việc đánh giá hệ thống có ngữ cảnh tương tự ngữ cảnh của hệ thống truy vấn thông tin (information retrieval) hay ngữ cảnh phân lớp (classification context). Một trong những cách thực hiện là sử dụng các metric liên quan đến precision và recall.

Precision & recall

Đối với ngữ cảnh hệ thống truy vấn thông tin

$precision=\dfrac{\left|RET\cap R E L\right|}{\left|RET\right|}$

và

$recall=\dfrac{\left|RET\cap R E L\right|}{\left|REL\right|}$

Đối với ngữ cảnh phân lớp

$precision=\dfrac{tp}{tp+fp}$

và

$recall=\dfrac{tp}{tp+fn}$

RET hay retrieved documents là kết quả do hệ thống xuất ra đối với một query cụ thể. REL hay relevant documents là danh sách tất cả các tài liệu có liên quan (trong trường hợp RS có thể ví dụ là danh sách item mà user có thao tác).

Thông thường precision lấy n kết quả đầu tiên của RET hay còn gọi là precision at n hay P@n với giả định user chỉ xem xét n kết quả đầu tiên.

Ví dụ trong trường hợp recommendation cho movies

$precision=\dfrac{\left|good\ movies\ recommended\right|}{\left|all\ recommendations\right|}$

F-measure

Một metric kết hợp giữa precision và recall có thể sử dụng là F-measure hay balanced F-score thông thường sử dụng là F1. Công thức $F_\beta$

$F_\beta=\left(1+\beta^2\right)·\dfrac{precision· recall}{β2·precision+recall}$

Các metric khác

Các metric khác có thể sử dụng như Receiver Operating Characteristics (ROC)

Ranking/list recommendation

Rank score

Rank score là mở rộng của recall để đo lường tính chính xác về vị trí một item trong danh sách.

$rankscore=\dfrac{{rankscore}_p}{{rankscore}_{max}}$

Trong đó:

• ${rankscore}_p=\displaystyle\sum_{i\in h}2^{-\frac{rank\left(i\right)-1}{\alpha}}$

• ${rankscore}_{max}=\displaystyle\sum_{i=1}^{\left|T\right|}2^{-\frac{i-1}{\alpha}}$

Trong đó:

• h là tập item được gợi ý đúng (hits)
• rank là vị trí position/rank của item
• T là tập hợp các item cần quan tâm
• α ranking half life một exponential reduction factor (hệ số giảm rank)

Ví dụ: $\left|T\right| = 3$, ranking half life α=2

Rank	Hit?
1
2	✓
3	✓
4	✓
5

${rankscore}_{p}=\dfrac{1}{2^\frac{2-1}{2}}+\frac{1}{2^\frac{3-1}{2}}+\frac{1}{2^\frac{4-1}{2}}=1.56$

${rankscore}_{max}=\dfrac{1}{2^\frac{1-1}{2}}+\frac{1}{2^\frac{2-1}{2}}+\frac{1}{2^\frac{3-1}{2}}=2.21$

$rankscore=\dfrac{{rankscore}_p}{{rankscore}_{max}}\approx0.71$

Liftindex

Giả định ranked list được chia làm 10 phần bằng nhau gọi là các deciles (mỗi phần đại diện 1/10 mẫu) với

$\displaystyle\sum_{i=1}^{10}S_i=\left|h\right|$

gọi là linear reduction factor với h là tập hợp correct hits.

$liftindex= \begin{cases} \dfrac{1 {\times} S_1+0.9 {\times} S_2+{\dots}+0.1 {\times} S_{10}}{\sum_{i=1}^{10}S_i} &\text{:nếu } \left|h\right| > 0 \\ 0 \end{cases}$

Rank	Hit?
1
2	✓
3	✓
4	✓
5

$liftindex=\dfrac{0.8\times1+0.6\times1+0.4\times1}{3}=0.6$

Discounted cumulative gain (DCG)

${DCG}_{pos}={rel}_1+\displaystyle\sum_{i=2}^{pos}\dfrac{{rel}_i}{\log_2{i}}$

với

• pos là vị trí cần tính từ 1 để tích lũy độ liên quan (relevance).
• ${rel}_i$ độ liên quan của gợi ý (recommendation) tại vị trí i.

Idealized discounted cumulative gain (IDCG) là giá trị maximum possible (ideal) của DCG

${IDCG}_{pos}={rel}_1+\displaystyle\sum_{i=2}^{\left|h\right|-1}\dfrac{{rel}_i}{\log_2{i}}$

Normalized discounted cumulative gain (NDCG)

${NDCG}_{pos}=\dfrac{{DCG}_{pos}}{{IDCG}_{pos}}$

Ví dụ: n = 5

Rank	Hit?
1
2	✓
3	✓
4	✓
5

${DCG}_5=\dfrac{1}{\log_2{2}}+\dfrac{1}{\log_2{3}}+\frac{1}{\log_2{4}}=2.13$

${IDCG}_5=1+\dfrac{1}{\log_2{2}}+\dfrac{1}{\log_2{3}}=2.63$

${NDCG}_{pos}=\dfrac{{DCG}_{pos}}{{IDCG}_{pos}}\approx0.81$

Biểu diễn DCG dạng khác (xem thêm tại Kaggle)

${DCG}_k=\displaystyle\sum_{i=1}^{k}\dfrac{2^{{rel}_i}-1}{\log_2{(i+1)}}$

Average precision (AP)

Độ chính xác trung bình (AP) là precision metric có xếp hạng thực hiện điều chỉnh nhấn mạnh các item được dự đoán đúng có thứ tự sắp xếp cao (high ranked).

$ap@n=\displaystyle\sum_{k=1}^{n}{P(k)/\min(m,n)}$

Nếu mẫu số (denominator) bằng zero thì kết quả là zero (xem thêm tại Kaggle).

Ví dụ: n = 5

Rank	Hit?
1
2	✓
3	✓
4	✓
5

$AP=\left(\dfrac{1}{2}+\dfrac{2}{3}+\dfrac{3}{4}\right)·13≈0.639$

Trường hợp dự đoán chính xác (hit) có vị trí đầu tiên thì score sẽ cao hơn

Rank	Hit?
1	✓
2
3
4	✓
5	✓

$AP=\left(\dfrac{1}{1}+\dfrac{2}{4}+\dfrac{3}{5}\right)·13=0.7$

Mean Average Precision

Thực hiện tính trung bình AP cho N user

$MAP@n=\displaystyle\sum_{i=1}^{N}{ap@n_i/N}$

Các metric khác

Các metric khác có thể sử dụng như sử dụng tương quan xếp hạng Spearman’s rank correlation, Kendall rank correlation.