MMR算法的实现原理

开发架构二三事 2020-11-14

2662

本文译自：http://www.cs.bilkent.edu.tr/~canf/CS533/hwSpring14/eightMinPresentations/handoutMMR.pdf

写在前面的话

MMR算法目的是减少排序结果的冗余，同时保证结果的相关性。最早应用于文本摘要提取和信息检索等领域。一般用于在找出用户与商品的相关性之后，依据商品间的相似性对商品列表的多样性进行处理。在推荐场景下体现在，给用户推荐相关商品的同时，保证推荐结果的多样性，即排序结果存在着相关性与多样性的权衡。通过阅读本文你能明白该算法的实现细节。

MMR

MMR的全称为最大边缘相关模型（Maximal Marginal Relevance）。在MMR模型中，同时将相关性和多样性进行衡量。因此，可以方便的调节相关性和多样性的权重来满足偏向“需要相似的内容”或者偏向“需要不同方面的内容”的要求。它的数学公式如下：

其中R是输入的列表，Di是集合R的成员，S是当前返回的结果集。Sim1(Di,Q)可以是协同过滤算法出来的相关度，也可以是其他算法模型预测出来的相关度。Sim2(Di,Dj)可以是余弦相似度、海明距离等可以度量的算法计算出来的值，它内部迭带的是Di和Dj，其中Dj是S的成员。步骤为外层对R列表进行迭代，计算Sim1(Di,Q)的值，内层对S列表进行迭代计算Sim2(Di,Dj)的值，然后对R列表进行排序后的结果取最大值，得到的i对应的元素Di就是我们本次迭代需要的值，我们可以将Di从R列表中删除并加入到S列表中，然后进行下一次的迭代。

内层对列表S进行迭代，先计算Di与S集合中的每个元素Dj之间的相似度取出最大值，然后外层与Sim1(Di,Q)按上面进行计算。

假设我们有一个包含5个文档di的数据库和一个查询q，给定一个对称的相似度度量，我们计算相似度值如下。提前假设用户设定的λ的值为０.5：

S是一个对称矩阵。

第一次迭代

目前我们的结果集S是空的。因此，方程的后半部分，即S内的最大成对相似度，将为零。第一次迭代时，MMR方程简化为:

MMR = arg max (Sim (di, q))

d1与q相似度最大，因此我们取其加入到S中，现在S = {d1}

第二次迭代

由于S = {d1}，求S中某元素到给定di的最大距离就是sim(d1,di)。

对于d2:

sim(d1, d2) = 0.11
sim (d2, q) = 0.90
然后　MMR = λ0.90 – (1-λ)0.11 = 0.395

同样，d3, 4, 5的MMR值分别为0.135，-0.35和0.19。由于d2具有最大的MMR，我们将其添加到S中，此时S = {d1, d2}。

第三次迭代

这次S = {d1, d2}。我们应该找到max。对于方程的第二部分，为sim (di, d1)和sim (di, d2)。

对于d3：

max{sim (d1, d3), sim (d2, d3)} =
max {0.23, 0.29} = 0.29
sim (d3, q) = 0.50
MMR = 0.5*0.5 - 0.5*0.29 = 0.105

同理，其他MMR的值计算为:

d4: -0.35, d5: 0.06

d3的MMR最大，因此S = {d1, d2, d3}。

如果我们完全没有多样性（λ=1)，那么我们的S将是{d1, d2, d5}。注意，不同情况的总体两两相似度为：

sim (d1, d2) + sim(d1, d3) + sim (d2, d3) = 0.63

而非多样性版本的总两两相似度为0.87。我们有效地使结果集中的项之间的差异更大。还要注意，查询的总相似度已经从2.44减少到2.31。为了多样性，我们牺牲了一些准确性。

附MMR的java实现

    /**
     * 迭代
     *
     * @param R
     * @param matrix
     * @param topNum
     * @param lambda
     * @return
     */
    static List<ClassIdScore> iterator(LinkedList<ClassIdScore> R, double[][] matrix, int topNum, double lambda) {
        AtomicInteger counter = new AtomicInteger(0);
        Stopwatch stopwatch = Stopwatch.createStarted();
        List<ClassIdScore> S = new ArrayList(topNum);
        while (S.size() < topNum && R.size() > 0) {
            double maxMMR = 0d;
            ClassIdScore maxClassIdScore = R.get(0);
            // 进行迭代
            for (int i = 0; i < R.size(); i++) {
                ClassIdScore di = R.get(i);
                double maxSim2 = 0d;


                for (int j = 0; j < S.size(); j++) {
                    counter.getAndIncrement();
                    ClassIdScore dj = S.get(j);
                    double sim2Score = matrix[di.getIndex()][dj.getIndex()];
                    if (j == 0) {
                        maxSim2 = sim2Score;
                    }
                    if (sim2Score > maxSim2) {
                        maxSim2 = sim2Score;
                    }
                }
                // 计算MMR
                double mmr = lambda * di.score - (1 - lambda) * maxSim2;
                if (i == 0) {
                    maxMMR = mmr;
                }
                if (mmr > maxMMR) {
                    maxMMR = mmr;
//                    System.out.println("第" + i + "次-----------------mmr:" + mmr + "   " + JSONObject.toJSONString(di));
                    maxClassIdScore = di;
                }
            }
            R.remove(maxClassIdScore);
            S.add(maxClassIdScore);
        }
        stopwatch.stop();
//        System.out.println("－－－－删除耗时:" + removeMills + "   迭代耗时：" + stopwatch.elapsed(TimeUnit.MILLISECONDS) + "  迭代次数为：" + counter.get());
        return S;
    }

数据库

文章转载自开发架构二三事，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。