揭开神秘的算法是什么 (揭开神秘的算法奥秘-探索斯奇拉姆排序)

在2023年结束的国际学术会议AIBT2023上，Ratidar Technologies LLC宣读了一篇基于公平性的排序学习算法，并且获得了该会议的最佳本文报告奖。该算法的名字是斯奇拉姆排序（Skellam Rank），充分利用了统计学中的原理，结合了Pairwise Ranking和矩阵分解，同时解决了推荐系统中的准确率和公平性的问题。因为推荐系统中的排序学习的原创算法很少，加上斯奇拉姆排序算法的性能优异，所以在会议上获得了研究奖项。

下面我们来介绍斯奇拉姆算法的基本原理：首先回忆一下泊松分布，泊松分布的参数的计算公式如下：

![泊松分布公式](

两个泊松变量的差值是斯奇拉姆分布，函数叫做第一类贝塞尔函数。有了这些最基本的统计学中的概念，下面让我们来构建一个Pairwise Ranking的排序学习推荐系统吧！我们首先认为用户给物品的打分是个泊松分布的概念。也就是说，用户物品评分值服从以下概率分布：

![用户物品评分概率分布公式](

之所以我们可以把用户给物品打分的过程描述为泊松过程，是因为用户物品评分存在马太效应，也就是说评分越高的用户，打分的人越多，以至于我们可以用某个物品的评分的人的数量来近似该物品的评分的分布。给某个物品打分的人数服从什么随机过程呢？自然而然的，我们就会想到泊松过程。因为用户给物品打分的概率和该物品有多少人打分的概率相近，我们自然也就可以用泊松过程来近似用户给物品打分的这一过程了。我们下面把泊松过程的参数用样本数据的统计量替代，得到下面的公式：

![泊松分布参数公式](

我们下面定义Pairwise Ranking的最大似然函数公式。所谓Pairwise Ranking指的是我们利用最大似然函数求解模型参数，使得模型能够最大程度保持数据样本中已知的排序对的关系：

![Pairwise Ranking的最大似然函数公式](

因为公式中的R是泊松分布，所以它们的差值，就是斯奇拉姆分布，也就是说：

![斯奇拉姆分布公式](

其中变量E是按照如下方式定义的：

![变量E定义公式](

我们把斯奇拉姆分布的公式带入最大似然函数的损失函数L，得到了如下公式：

![损失函数公式](

在公式中出现的用户评分值R，我们利用矩阵分解的方式进行求解。将矩阵分解中的参数用户特征向量U和物品特征向量V作为待求解变量：

![矩阵分解参数公式](

这里我们先回顾一下矩阵分解的概念。矩阵分解的概念是在2010年左右的时候提出的推荐系统算法，该算法可以说是历史上最成功的推荐系统算法之一。时至今日，仍然有大量的推荐系统公司利用矩阵分解算法作为线上系统的baseline，而时下大热的经典推荐算法DeepFM中的重要组件Factorization Machine，也是推荐系统算法中的矩阵分解算法后续的改进版本，和矩阵分解有千丝万缕的联系。矩阵分解算法有个里程碑本文，是2007年的Probabilistic Matrix Factorization，作者利用统计学习模型对矩阵分解这个线性代数中的概念重新建模，使得矩阵分解第一次有了扎实的数学理论基础。矩阵分解的基本概念，是利用向量的点乘，在对用户评分矩阵进行降维的同时高效的预测未知的用户评分。矩阵分解的损失函数如下：

![矩阵分解损失函数公式](

矩阵分解算法有许多的变种，比如上海交大提出的SVDFeature，把向量U和V用线性组合的形式进行建模，使得矩阵分解的问题变成了特征工程的问题。SVDFeature也是矩阵分解领域的里程碑本文。矩阵分解可以被应用在Pairwise Ranking中用以取代未知的用户评分，从而达到建模的目的，经典的应用案例包括Bayesian Pairwise Ranking中的BPR-MF算法，而斯奇拉姆排序算法就是借鉴了同样的思路。

我们用随机梯度下降对斯奇拉姆排序算法进行求解。因为随机梯度下降在求解过程中，可以对损失函数进行大量的简化从而达到求解的目的，我们的损失函数变成了下面的公式：

![损失函数公式2](

利用随机梯度下降对未知参数U和V进行求解，我们得到了迭代公式如下：

![迭代公式1](

对于未知参数变量V的求解类似，我们有如下公式：

![迭代公式2](

整个算法的流程，我们用如下的伪代码进行展示：

“`pythonfunction SkellamRank(data): initialize U, V repeat until convergence: for each (i, j, k) in data: compute R, E based on U, V compute loss function L based on R, E update U, V using stochastic gradient descent return U, V“`