ARTS打卡 - 20191209~20191222
这个系列是
ARTS打卡计划， 什么是ARTS， 参看这里https://time.geekbang.org/column/article/85839
Algorithm
Review
http://net.pku.edu.cn/~cuibin/Papers/2015SIGMOD-tencentRec.pdf
let $x$ be a real-valued random variable whose range is $R$ (for the similarity score the range is one). Suppose we have made $n$ independent observations of this variable, and computed their mean $\hat{x}$. The Hoeffding bound states that, with probability $1-\delta$, the true mean of the variable is at most $\hat{x} + \epsilon$, where:
\[\epsilon=\sqrt{\frac{R^{2} \ln (1 / \delta)}{2 n}}\]In TencentRec, we take the similarity scores of an item pair at different time points as random variables. Let $t$ be the threshold of an item’s similar-items list, i.e., the minimum similarity score among the similar items $N^{k}\left(i_{p}\right)$. Given a desired $\delta$, the Hoeffding bound guarantees that the correct similarity score of the item pair is no more than t with probability $1−δ$, if $n$ updates have been seen at the moment and $\epsilon<t-\hat{x}$. In other words, after we observe some item pairs’ similarity update operations, we can prune the dissimilar item pairs, i.e., the items not able to be in $N^{k}\left(i_{p}\right)$.
简单翻译一下这段实时剪枝的算法。
前半段解释了如何用霍夫丁界构造快速决策树：
假设$x$是一个随机变量，范围为$R$(对于相似度来说，这个范围就是1)。
如果我们已经观测到了变量的$n$个独立实验，霍夫丁界指出， 在$1-\delta$的置信度下，变量$x$的真实均值最多是
$\hat{x} + \epsilon$ ,其中:
\[\epsilon=\sqrt{\frac{R^{2} \ln (1 / \delta)}{2 n}}\](也就是说， 随机变量真实值的上限是$\hat{x} + \epsilon$)。
下半段解释了推荐系统如何利用霍夫丁界构造的快速决策树来剪枝：
在TencentRec推荐系统中，我们把每个项目对在不同时间点计算出来的相似度分数看做是随机变量。假设$t$为一个项目的相似列表中分数的阈值，例如，$t$为相似列表$N^{k}\left(i_{p}\right)$中最小的相似分数。对于一个给定的期望$\delta$, 如果在某个时刻已经观测了一个项目对的$n$次更新(已经计算了$n$次相似度分数)，且$\epsilon<t-\hat{x}$,则霍夫丁界可以确保在$1-\delta$的置信度下，这个项目对的真实的相似度分数不会大于$t$。换句话说，我们在观测一些项目对的相似分数更新操作后，可以剪掉这些不相似的项目对，例如这些项目不可能在$N^{k}\left(i_{p}\right)$列表中（没有继续计算的必要了）。
加粗部分，可以简化为下面的推导式：
若 $\epsilon<t-\hat{x}$, 则由 $u\leq\hat{x}+\epsilon<\hat{x}+(t-\hat{x})=t$ ($u$指真实相似分)
霍夫丁界在机器学习，流计算处理中非常重要。
Tip
在计算向量$A$和向量$B$的余弦相似距离时，可以通过先分别归一化(转换为单位矩阵)，再计算归一化之后向量的点积来得到相同的结果。
从公式上也很容易看出两种计算方式是等价的：
\[\text { similarity }=\cos (\theta)=\frac{A \cdot B}{\|A\|\|B\|}=\frac{A}{\|A|}\cdot\frac{B}{\|B|}\]