无敌的Log-Likelihood Ratio(1)——LLR的计算方式

Log Likelihood Ratio的计算公式和代码实现以及相关的原理性的东西。希望和大家一起讨论，一起进步。

寻沂

17407人浏览 · 2020-07-27 17:30:28

寻沂 · 2020-07-27 17:30:28 发布

文章目录

Ted\; Dunning

在

《Accurate\; Methods\; for\; the\; Statistics\; of\; Surprise\; and\; Coincidence》

中介绍了

Log-Likehood\; Ratio

在文本计算中的基本使用。

L L R

因为实现简单、有效并且具有大规模数据上的可扩展性，能够被很好的使用到工业系统中。因此基于

L L R

的相似度度量广泛应用在推荐系统等多种应用当中。
在这篇Blog中，我们忽略

《Accurate\; Methods\; for\; the\; Statistics\; of\; Surprise\; and\; Coincidence》

中对

L L R

过多的冗余描述，主要集中的去关注

L L R

的计算方式和现有的一些简单有效的代码实现。
本篇博客的组织方式如下。在章节1中，以最简单的方式讨论了

Log-Likelihood\; Ratio

相似度的计算方式，在章节2中讨论了

Log-Likelihood\; Ratio

的具体的代码实现，以及一些可以现用的相似度计算工具。

1. LLR的计算方式

在计算两个事件(例如推荐系统中的点击行为)的 $L L R$ 值来做相似度衡量的时候，我们通过两个事件的计数来计算事件之间的相似度。接下来我们以推荐系统中物品相似度的计算为例来介绍 $L L R$ 的计算方式。
有两个物品分别为物品 $i$ 和物品 $j$ 。对应事件计数的简单形式化描述如下：
$k_{11}$ ：表示同时浏览了物品 $i$ 和物品 $j$ 的用户。
$k_{12}$ ：表示浏览了物品 $i$ ，但是没有浏览物品 $j$ 的用户。
$k_{21}$ ：表示浏览了物品 $j$ ，但是没有浏览物品 $i$ 的用户。
$k_{22}$ ：表示没有浏览物品 $i$ ，并且没有浏览物品 $j$ 的用户。
根据上述，我们可以得到如下的一个表格:

事件	浏览 $Item\;i$	没有浏览 $Item\;i$
浏览 $Item\; j$	$k_{11}$	$k_{21}$
没有浏览 $Item\;j$	$k_{12}$	$k_{22}$

$Item\; i$ 和 $Item\;j$ 的 $L L R$ 计算公式如下：
$S=2\times (H_m - H_c - H_r)$
其中：
$H_m$ 表示上述矩阵的矩阵熵，总体的计算公式如下：
$H_m = - (\frac{k_{11}}{N}\;log(\frac{k_{11}}{N}) + \frac{k_{12}}{N}\;log(\frac{k_{12}}{N}) + \frac{k_{21}}{N}\;log(\frac{k_{21}}{N}) + \frac{k_{22}}{N}\;log(\frac{k_{22}}{N}))$
$H_r$ 表示每行相加计算得到的信息熵，相关的具体计算公式如下：
$H_r = -(\frac{k_{11} + k_{12}}{N}\; log(\frac{k_{11}+k_{12}}{N}) +\frac{k_{21} + k_{22}}{N}log(\frac{k_{21} + k_{22}}{N}))$
$H_c$ 表示矩阵的每一列相加计算得到的信息熵，相关的具体计算公式如下：
$H_c=-(\frac{k_{11} + k_{21}}{N}\; log(\frac{k_{11}+k_{21}}{N}) +\frac{k_{21} + k_{22}}{N}log(\frac{k_{21} + k_{22}}{N}))$

其中 $N=k_{11} + k_{12} + k_{21} + k_{22}$

2. LLR的代码实现

在 $M a h o u t$ 的 $m a t h$ 库中定义了 $L o g L i k e l i h o o d$ 类，实现了 $L L R$ 的计算，其中具体的计算代码在下面给出。

$r o w E n t r o p y$ 的计算方式如下

private static double xLogX(long x) {
    return x == 0 ? 0.0 : x * Math.log(x);
  }

private static double entropy(long a, long b) {
    return xLogX(a + b) - xLogX(a) - xLogX(b);
  }

其中 $a=k_{11} + k_{12}$ 并且 $b=k_{21} + k_{22}$ ，综合得到
$\times log\;(N) - (k_{11} + k_{12}) \times log\;(k_{11} + k_{12}) -(k_{21} + k_{22} )\times log\;(k_{21} + k_{22})) \\ \;\\ = -((k_{11}+k_{12})\times log\;(N)-(k_{11} + k_{12}) \times log\;(k_{11} + k_{12}) + (k_{21} + k_{22}) \times log\;(N) - (k_{21} + k_{22} )\times log\;(k_{21} + k_{22})) \\ \;\\ =-((k_{11} + k_{12}) \times(log(N)-log(k_{11}+k_{12})) + (k_{21} + k_{22}) \times(log(N)-log(k_{21}+k_{22})))\\ \;\\ =(k_{11} +k_{12}) \times(log\;\frac{k_{11} + k_{12}}{N}) + (k_{21} + k_{22}) \times(log\;\frac{k_{21} + k_{22}}{N}) = - H_r \times N$

同样的 $c o l E n t r o p y$ 的计算方式如下:
$(k_{11} +k_{21}) \times(log\;\frac{k_{11} + k_{21}}{N}) + (k_{12} + k_{22}) \times(log\;\frac{k_{12} + k_{22}}{N}) = -H_c \times N$

$m a t r i x E n t r o p y$ 的计算方式

private static double entropy(long a, long b, long c, long d) {
    return xLogX(a + b + c + d) - xLogX(a) - xLogX(b) - xLogX(c) - xLogX(d);
  }

$N\times log\;(N) - k_{11}\;log(k_{11}) -k_{12}\;log(k_{12}) - k_{21}\;log\;(k_{21}) - k_{22}\;log(k_{22}) \\ \;\\ = - (k_{11}\times log\;(\frac{k_{11}}{N})+k_{12}\times log\;(\frac{k_{12}}{N}) + k_{21}\times log\;(\frac{k_{21}}{N})) + k_{21}\times log\;(\frac{k_{21}}{N})) \times N$

最终相似度 $S$ 的计算结果

public static double logLikelihoodRatio(long k11, long k12, long k21, long k22) {
    Preconditions.checkArgument(k11 >= 0 && k12 >= 0 && k21 >= 0 && k22 >= 0);
    // note that we have counts here, not probabilities, and that the entropy is not normalized.
    double rowEntropy = entropy(k11 + k12, k21 + k22);
    double columnEntropy = entropy(k11 + k21, k12 + k22);
    double matrixEntropy = entropy(k11, k12, k21, k22);
    if (rowEntropy + columnEntropy < matrixEntropy) {
      // round off error
      return 0.0;
    }
    return 2.0 * (rowEntropy + columnEntropy - matrixEntropy);
  }