algorithm - 我不明白如何实现的概率(指数？)推理公式

Question

我正在尝试从一篇学术论文中实现一个真相发现算法。它是一种流式算法，可以实时推断真相和源质量。如果有人有兴趣阅读本文，请在此处了解更多详细信息:http://dl.acm.org/citation.cfm?id=2661892

我的问题是我不理解算法中的公式，或者准确地说是其中一个公式的符号，我在用 R 或 Python 实现它时遇到了困难。它似乎是某种指数公式，但我在数学书籍中没有找到任何相关内容。也不确定半无穷大符号。我假设它意味着成比例，但这意味着赋值，还是什么？任何指针将不胜感激。

Answer 1

(你真的应该在数学或计算机科学上发帖；你试图理解算法本身，而不是算法的实现。一个很大的缺点是 Stack Overflow 不允许 LaTeX，所以请原谅那些难以阅读的东西下面。)

为了能够使用“成比例”符号\propto，您需要考虑到表达式的左侧是概率。

您可以使用以下内容作为\propto 的“定义”:

P(X = x)\propto f(x) <=> P(X = x) = f(x)/(\sum_{x'} f(x'))

也就是说，当用随机变量 X 的所有值 x' 的 f(x') 之和归一化时，P(X = x) 与 f(x) 成正比。

例如，如果一个瓮中装有 10 个蓝色球和 20 个红色球，则抽到给定颜色球的概率与该颜色球的数量成正比。由于概率之和需要为 1，这意味着按以下方式对其进行归一化:

P(颜色=蓝色)\propto 10

P(颜色 = 红色)\propto 20

P(颜色 = 蓝色) = 10/(10 + 20) = 1/3

P(颜色 = 红色)= 20/(10 + 20) = 2/3。

现在，在您正在使用的论文中，他们对随机变量及其值使用了非常紧凑的符号\nu^t_{i,v,j}。在不知道论文其余部分的情况下，我猜测\nu^t_{i,v,j} 代表 P(R^t_{i,j} = v)，即索引 t、i 和j 表示正在讨论的是哪个随机变量 R^t_{i,j} (他们没有在那里明确命名随机变量，所以为了清楚起见，我只是在这里使用名称 R)，而索引 v 代表 该随机变量的值。但是，您最好在索引 v 代表值的假设下检查我是否正确。

如果这个假设是正确的，那么这个表达式意味着

\nu^t_{i,v,j} = f(v)/sum_v' f(v')

其中 f 代表表达式的右侧。

自然地，更有效的计算方式是，对于每个 t、i、j，为每个值 v 计算 f(v) 并将其存储在以 v 为索引的数组中，边计算边累加它们的总和，然后然后简单地将数组中的每个值除以最终总和。