推荐系统中的常用指标计算

算是给自己整理一下吧。主要是MF和FM的对比。

Toy Matrix#

假设有那么个用户数为6，物品数为5的大小为$6\times 5$的评分矩阵：

$$R=\begin{bmatrix} 4 & 0 & 5 & 1 & 0 \\ 3 & 5 & 1 & 0 & 0 \\ 2 & 5 & 0 & 0 & 2 \\ 0 & 0 & 0 & 5 & 4 \\ 1 & 5 & 5 & 0 & 0 \\ 0 & 0 & 4 & 4 & 3 \end{bmatrix}$$

空缺的评分用0填充。

评分预测#

MF模型#

这个是相对比较简单的，将MF的两个矩阵算一下点积，就能得到所有用户对所有物品的评分$\hat R$。

FM模型#

FM对输入数据$\bm x$（假设是行向量）的表示一般可以分为三部分：代表用户ID的one-hot向量$\bm{x}_u\in\mathbb{R}^6$，代表物品ID的one-hot向量$\bm{x}_i\in\mathbb{R}^5$，以及其他与该评分有关的上下文（context）特征向量$\bm{x}_c\in\mathbb{R}^c$（$c$为特征维度数）。即：$\bm x = [\bm x_u, \bm x_i, \bm x_c]$。

如果context是跟item挂钩的，即每个item下的所有评分都共享同一个context特征的话，事情就好办多了（至少这次跑的实验是这样的）。因此，FM的预测公式可以分解为与item相关以及与user相关两部分，跟MF模型相似。

原本计算FM的实现如下，$X$为行向量，$\bm w$为列向量，而$V$为$k\times(11+c)$的交叉项权重矩阵。

y_hat = w0 + X * w - sum((X .^ 2) * (V' .^ 2), 2) / 2 + sum((X * V') .^ 2, 2) / 2;

由于用户ID和物品ID都是one-hot向量，而context是跟item挂钩的，可以简化成：

y_hat = w0 + w(u) + w(i) + Xc(i) * wc - sum((Vu(u)' .^ 2) + (Vi(i)' .^ 2) + (Xc(i) .^ 2) * (Vc' .^ 2), 2) / 2 + sum((Vu(u)' + Vi(i)' + Xc(i) * Vc') .^ 2, 2) / 2

其中$u$和$i$是每条评分的用户和物品的ID。

然后跟MF一样，拆成与item挂钩的一部分：

linear_i = w_item + ctx * w_ctx; % [n_item, 1]
cross_i_pos = V_item' + ctx * V_ctx'; % [n_item, k]
cross_i_neg = V_item' .^ 2 + (ctx .^ 2) * (V_ctx' .^ 2); % [n_item, k]

ctx为n_item$\times c$的context特征矩阵。

以及跟user挂钩的另一部分：

linear_u = w_user; % [n_user, 1]
cross_u_pos = V_user'; % [n_user, k]
cross_u_neg = V_user' .^ 2; % [n_user, k]

最后对每个用户$u$的，预测公式如下：

y_hat = w0 + linear_u(u) + linear_i + sum(cross_u_pos(u) + cross_i_pos, 2)/2 - sum(cross_u_neg(u) + cross_i_neg, 2)/2; % [n_item, 1]

对用户没评过分的item，把itemID对应的位置置1，然后补上这个item的context特征进行预测就行了。

指标计算#

Precision@N#

N指的是推荐列表的长度。对推荐系统而言，前N个item的预测标签为1，而在后面的均为0。而对于ground truth标签，用户为其评过分则为1，否则为0。

For个example，假如$N=3$，推荐系统为第一个user生成的推荐列表为1，3，5，4，2。

item ID	预测	GT
1	1	1
3	1	1
5	1	0
4	0	1
2	0	0

因此TP=2，FP=1，Precision@3=TP/(TP+FP)=2/3=0.667。

实际上，计算可以简化为Pre@N=TP/N，TP为true positive的item数。代表的含义是前N个item列表中出现用户评过分的item的概率。

Recall@N#

跟上面类似，FN指的是出现在第N个item后面，用户有评过分的item数，如item 4。

因此，FN=1，Recall@3=TP/(TP+FN)=2/3=0.667。

实际上，计算也可以简化为Rec@N=TP/Np，Np为当前用户评过分的item个数。代表的含义是用户评过分的item出现在前N个item列表中的概率。这个数值是随N递增而单调递增的。

Average Precision#

这个指标综合评估Precision和Recall的质量，跟N无关。顾名思义，AP是对Precision求均值，而具体做法则是以recall为横坐标，precision为纵坐标，对precision求均值。人懒，原理就不解释了。

Normalized Discounted Cumulative Gain@N (NDCG@N)#

好像是这么拼来着吧？平时都直接喊的嗯滴希鸡。

推荐系统按照所有item预测的评分分数做个倒序排序，得到一个item列表：

item ID	评分$r$	折损因子$d$
1	4	log2(2)
3	5	log2(3)
5	0	log2(4)
4	1	log2(5)
2	0	log2(6)

Cumulative Gain，既然是cumulative，那自然就少不了sum嘛，CG@N=sum(2^r-1)，r按照生成item列表的顺序来。有些实现版本则是CG@N=sum(r)，没有取指数。

同样假设$N=3$，CG@3=(2^4-1)+(2^5-1)=46。

Discounted Cumulative Gain，多了个折损因子，DCG@N=CG@N/d。DCG@3=(2^4-1)/log2(2) + (2^5-1)/log2(3)=15+31/1.585=34.5588。

而Normalized则需要计算理想的DCG，即Ideal DCG（IDCG），它是按照评分倒序排的：

item ID	评分$r$	折损因子$d$
3	5	log2(2)
1	4	log2(3)
4	1	log2(4)
2	0	log2(5)
5	0	log2(6)

根据上表算DCG得到IDCG@3=DCG@3=(2^5-1)/log2(2) + (2^4-1)/log2(3) + (2^1-1)/log2(4)=31+15/1.585+1/2=40.9639。

最后的NDCG@N=DCG@N/IDCG@N=34.5588/40.9639=0.8436。

而某些论文中（这里就不点名是谁啦），NDCG的计算只考虑了用户评过分的物品，而未评过分的物品则不参与计算，因此实际计算NDCG时的列表如下（即去掉评分为0的item）：

item ID	评分$r$	折损因子$d$
1	4	log2(2)
3	5	log2(3)
4	1	log2(4)

计算IDCG时，是否去掉评分为0的item其实不影响结果，毕竟它们全排到最后面了嘛，求sum的时候都是0。

最后算出的DCG@3=15+31/1.585+1/2=35.0588。即NDCG@3=35.0588/40.9639=0.8558。用这种计算方法得出来的NDCG是偏高的，不过嘛，作者开心就好。