> For the complete documentation index, see [llms.txt](https://sisyphus.gitbook.io/project/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sisyphus.gitbook.io/project/machine-learning/recommendation.md).

# Recommendation

## Learn To Recommend

{% embed url="<https://zhuanlan.zhihu.com/p/52447211>" %}

### Binary classification recommendation system&#x20;

目前广泛使用的一些推荐算法，本质上还是二分类算法，类似于“点击率预估”。尽管线上效果还不错，但是距推荐系统的实际需求还有差距：

* 推荐系统中的“排序”任务关心的是相对顺序正确与否，而不是对“单个物料的点击概率”预测得是否精准。
* 二分类优化的loss只基于“预测分数”与“真实值”的差异，对“预测分数”可导，可用Gradient Descent优化之。而推荐系统中的很多业务指标，如NDCG, MAP，是基于“排序位置”的。**“预测分数”的微小变化，或者不足以改变顺序使metric不变，导数始终为0，或者改变排序而导致metric剧烈变化，不可导**，使得无法用Gradient Descent优化。

### Regression recommendation for User-item&#x20;

{% embed url="<https://karthkk.wordpress.com/2016/03/22/deep-learning-solution-for-netflix-prize/>" %}

```python
movie_count = 17771
user_count = 2649430
model_left = Sequential()
model_left.add(Embedding(movie_count, 60, input_length=1))
model_right = Sequential()
model_right.add(Embedding(user_count, 20, input_length=1))
model = Sequential()
model.add(Merge([model_left, model_right], mode='concat'))
model.add(Flatten())
model.add(Dense(64))
model.add(Activation('sigmoid'))
model.add(Dense(64))
model.add(Activation('sigmoid'))
model.add(Dense(64))
model.add(Activation('sigmoid'))
model.add(Dense(1))
model.compile(loss='mean_squared_error', optimizer='adadelta')
```

![](https://443921002-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGHUhl6VYqrZm4Re77O%2F-LUfsmjsMU4gp5FOg5ne%2F-LUgI45Fxy1ch_i0Dfvh%2FScreen%20Shot%202018-12-26%20at%2012.54.32%20PM.png?alt=media\&token=9d26c000-5fdf-4b86-adba-c424420c3b2a)

### Learn to recommend

用户输入一个query q，待排序的两篇文章Ui, Uj, si是模型给文章Ui打的分数，预测q与Ui的相关性，sj是模型给Uj打的分数，预测q与Uj的相关性。我们可以**预测将Ui排在Uj前的概率，从而将排序转化成一个二分类问题**, “Ui排在Uj前面”的概率定义如下（注意 ![\sigma](https://www.zhihu.com/equation?tex=%5Csigma) 是一个超参，不代表sigmoid函数）![](https://pic1.zhimg.com/80/v2-5e359bcf50bcd125261c20ddf5566168_hd.jpg)图1. 文章Ui排在Uj前的概率是si-sj的sigmoid函数

![\bar{P\_{ij}}](https://www.zhihu.com/equation?tex=%5Cbar%7BP_%7Bij%7D%7D) 定义为”Ui排在Uj前面”这个论述的真实性(ground truth)，1代表论述为真，0代表为假，0.5代表Ui与Uj位置应该相同。如下图所示，做一个简单的数据变换，用 ![S\_{ij}\in\[-1,0,1\]](https://www.zhihu.com/equation?tex=S_%7Bij%7D%5Cin%5B-1%2C0%2C1%5D) 来代表“Ui排在Uj前面”论述的真实性。从而我们可以定义binary cross entropy loss如下图2

![](https://pic4.zhimg.com/80/v2-2d51a9c1e811c888c909c0a94062ba87_hd.jpg)

我们再简化一下“训练集”的构成，因为如果一对儿文章“Ui排在Uj前”为真，那么”Uj排在Ui前”一定为假，导致冗余。所以，在训练集中，我们只需要保留所有 ![S\_{ij}](https://www.zhihu.com/equation?tex=S_%7Bij%7D) =1的训练样本。然后再让以上binary cross-entropy loss对”待优化变量 ![w\_k](https://www.zhihu.com/equation?tex=w_k) ”求导，则有图3

![](https://pic1.zhimg.com/80/v2-e3dfbaf5dd4b7bc05ab7572c35d792a4_hd.jpg)

注意上式中，“预测得分s对w”的导数![\frac{\partial{s\_i}}{\partial{w\_k}}](https://www.zhihu.com/equation?tex=%5Cfrac%7B%5Cpartial%7Bs_i%7D%7D%7B%5Cpartial%7Bw_k%7D%7D) 和![\frac{\partial{s\_j}}{\partial{w\_k}}](https://www.zhihu.com/equation?tex=%5Cfrac%7B%5Cpartial%7Bs_j%7D%7D%7B%5Cpartial%7Bw_k%7D%7D)，可以由NN来实现，也可以由GBDT来实现，属于“开箱即用”的成熟技术，就不用赘言了。在这里，我们关心的是![\frac{\partial{C}}{\partial{s\_i}}=-\frac{\partial{C}}{\partial{s\_j}}](https://www.zhihu.com/equation?tex=%5Cfrac%7B%5Cpartial%7BC%7D%7D%7B%5Cpartial%7Bs_i%7D%7D%3D-%5Cfrac%7B%5Cpartial%7BC%7D%7D%7B%5Cpartial%7Bs_j%7D%7D)，即**loss function对第i篇文章的预测得分的导数**，注意这里我们用 ![\lambda\_{ij}](https://www.zhihu.com/equation?tex=%5Clambda_%7Bij%7D) 来表示，这也就是LambdaRank, LambdaMART一系列算法名字的由来。

注意两点，

* 这里的![\lambda\_{ij}](https://www.zhihu.com/equation?tex=%5Clambda_%7Bij%7D)还是一个真的梯度，区别于下面要说的**为了优化某不可导指标而人为设计的梯度**。
* 以上binary loss function，**对“列表头部的排序正确性”与“列表尾部的排序正确性”一视同仁，实际上优化的是AUC**

而如果我们要优化**NDCG这样重点关注头部位置的指标**，正如前所述，**这些指标对单个文档的“预测得分”的微小变化，要么无动于衷，要么反应剧烈，即我们无法定义一个“既能优化NDCG，又对**![s\_i](https://www.zhihu.com/equation?tex=s_i) **连续可导”的loss**。那怎么办？

LambdaRank/LambdaMART的解决思路，简单而被证明有效：**既然无法定义一个符合要求的loss，那就不定义了，直接定义一个符合我们要求的梯度就行了。这个不经过loss，而被人为定义出来的梯度，就是所谓的Lambda梯度**。

那么优化NDCG需要怎样的Lambda梯度？很简单，

* 在上一轮迭代结束后，将候选文档/物料，按照上一轮迭代得到的预测分数从大到小排序
* 对\<Ui,Uj>这一对儿，如果还用binary cross entropy loss预测排序是否正确，其梯度定义和图3中一样

![](https://pic1.zhimg.com/80/v2-06f3ba477178885a14cf5b4eb9aa23ac_hd.jpg)图4. 不考虑优化指标，只考虑排序正确性时的Lambda梯度

* 将Ui,Uj的位置调换，计算NDCG的变化 ![\left| \Delta NDCG \right|](https://www.zhihu.com/equation?tex=%5Cleft%7C+%5CDelta+NDCG+%5Cright%7C) ，然后将![\left| \Delta NDCG \right|](https://www.zhihu.com/equation?tex=%5Cleft%7C+%5CDelta+NDCG+%5Cright%7C)乘到上一步得到的Lambda梯度上，就是**优化NDCG所需要的Lambda梯度**

![](https://pic1.zhimg.com/80/v2-f18690c3086fa8c310fc701e77076988_hd.jpg)

以上公式中![\left| \Delta NDCG \right|](https://www.zhihu.com/equation?tex=%5Cleft%7C+%5CDelta+NDCG+%5Cright%7C)，在TF-RANKING的代码中被称为**Lambda weight**。优化不同的指标，将会定义不同的Lambda weight。

### Learn to recommend four essentials

综上所述，我们可以看到，实现一个Learning-To-Rank算法，有4个重点：

* **样本如何组织**。显而易见，排序只对“**同一个query下的候选文档**”或“**同一个推荐session下的候选商品**”才有意义。所以，与普通二分类不同，**LTR训练集有一个分组的概念，同一个组内的候选物料才能匹配成对，相互比较**。
* **打分**。本来很简单的一个步骤，**将query-doc, user-item的特征喂进模型，模型的输出就是我们需要的分数，预测query-doc, user-item的相关程度**。但是TF-Ranking却使用了所谓的**Groupwise Scoring Function（GSF）**，给一个候选物料 ![item\_i](http://www.zhihu.com/equation?tex=item_i) 打分时，要把它与其他候选物料编组，并且要考虑![item\_i](http://www.zhihu.com/equation?tex=item_i)在组内的不同位置上，然后给这一组同时打分。我觉得是一个**华而不实、得不偿失**的功能。
* **定义loss**。Learning-To-Rank有pointwise/pairwise/listwise三种定义loss的方式。Pointwise与普通的ctr预估无异，上面的例子介绍的就是pairwise, listwise以后找个机会再介绍。不同的loss定义方式，再结合优化不同指标而定义的不同lambda weight，可以衍化出更多种算法。
* **Lambda Weight**。如前所述，根据需要优化的指标(NDCG/MAP/MRR)的不同，需要定义不同的lambda weight，乘在 ![\frac{\partial{C}}{\partial{s\_i}}](http://www.zhihu.com/equation?tex=%5Cfrac%7B%5Cpartial%7BC%7D%7D%7B%5Cpartial%7Bs_i%7D%7D) 的前面

### Binary classification VS. Score based ranking system (LTR)

* LTR比目前常用的预测点击/转化的二分类算法，更加符合推荐系统的实际需求
* 我经常使用 lightgbm, xgboost 来进行LTR，但是 GBDT 天生只擅长处理稠密特征，而“稀疏特征”才是推荐、搜索领域中的“一等公民”。TF-Ranking 基于 TensorFlow，可以充分利用 **embedding, crossing, hashing** 等手段来处理“稀疏特征”。
* TF-Ranking 是一个框架，可以接入任意一种算法来计算 query-doc, user-item 之间的相关性，也可以在 pointwise/pairwise/listwise 这三大类 loss function 中方便切换。这使我们可以轻松尝试多种组合，比如基于 wide & deep 的 pairwise LTR，基于deepfm 的 listwise LTR。
* TF-Ranking 是基于 TensorFlow Estimator 框架实现的，自动具备了分布式训练、部署的能力，可以应对海量数据集。

![](https://443921002-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGHUhl6VYqrZm4Re77O%2F-LUid5fGZQV8Rl9N-z2j%2F-LUilPhvBqQ20Pa0pftV%2FScreen%20Shot%202018-12-27%20at%2012.26.09%20AM.png?alt=media\&token=5842e658-5f84-4c9c-bc72-d3d758887719)

## Metric for recommendation system

### MAP (Mean Average Precision)

> **The "Mean" in MAP**[¶](http://sdsawtelle.github.io/blog/output/mean-average-precision-MAP-for-recommender-systems.html#The-%22Mean%22-in-MAP)
>
> OK that was Average Precision, which applies to a single data point (like a single user). What about MAP\@N? All that remains is to average the AP\@N metric over all your |U||U|users. Yes, an average of an average.
>
> $$
> MAP\@N=1|U|∑u=1|U|(AP\@N)u=1|U|∑u=1|U|1m∑k=1NPu(k)⋅relu(k)
> $$

{% embed url="<http://sdsawtelle.github.io/blog/output/mean-average-precision-MAP-for-recommender-systems.html>" %}

### NDCG series

CG（Cumulative Gain)

DCG (Discounted Cumulative Gain)

NDCG (Normalized Discounted Cumulative Gain)

{% embed url="<http://sofasofa.io/forum_main_post.php?postid=1002561>" %}