Hoeffding不等式剪枝方法

    在基于物品的协通过滤算法中，当用户历史行为数据有很多时，对计算会有很大挑战，对此可以使用剪枝对数据进行化简来达到减少计算量。
    不是每个物品对都需要进行增量计算。对于两个物品的相似度，每次更新都能够得到一个新的相似度，这个新的相似度可以看做是一个随机变量，那么这个随机变量就有一个期望值。一旦物品之间的相似度可以以较高的置信度确认，它已经在期望值附近小幅度波动，就没必要再去更新了。如果进一步确定是一个比较小的相似度，甚至可以之间去掉这个物品对，其相似度不再参与计算更新。
对于确定这个物品什么时候不用再更新就可以用到Hoeffding不等式。Hoeffding不等式又称为霍夫丁不等式。该不等式给出了随机变量的和与其期望值偏差的概率上限。
$$\hat{x}=\frac{1}{n}(x_1+....+x_n)$$
$$p(\hat{x}-E[\hat{x}\ge ϵ])\le e^{-2n{ϵ}^2}$$
    不等式中$\hat{x}$是随机变量X的n个样本的均值，$E[\hat{x}]$是随机变量X的期望值。Hoeffding不等式反应的是：随机变量的真实期望值不会超过$\hat{x}+ϵ$的概率是$1-\delta$，其中$ϵ$就是与真实相似度的误差，$ϵ$、$\delta$及n之间的关系是：
$$ϵ=\sqrt{\frac{ln(\frac{1}{\delta })}{2n}}$$
    Hoeffding不等式适用于有界的随机变量。$\hat{x}$在实时推荐系统中就是历次更新得到的相似度平均值，公式中的n是相似度的更新次数。这样一来，选定了$\delta$和$ϵ$之后就可以知道多少次后就能够逼近相似度期望值。假设$\delta =0.05$。
    那么有

与真实相似度误差	最少更新次数
0.1	150
0.05	600
0.01	14979

    有了上面的表那么在一个物品对的更新次数已经达到最少更新次数时，且满足相似度误差时就可以不用再更新了。

参考：推荐系统: 关键模块 陈开江