类卷积表达式的高效计算

Question

令 i=1...m 的 p(z_i | x_i) 为一些概率，其中 x_i 和 z_i 在 {0,1} 中。我想有效地计算以下内容：

对于所有 z_1...z_m。

我知道可以使用 FFT 在 O(m * 2^m) 中有效地计算卷积。有没有一种方法可以计算 ν(z_1, ..., z_m) 具有类似的计算复杂度？

具体来说，p(z_i | x_i) 不依赖于 i，如下所示：

我尝试使用与 FFT 计算卷积类似的方法来加速计算，但我无法使其成功运行。

Answer 1

假设

μ(x1,..,xm)

是计算这些变量平均值的函数，实际上可以大大简化计算。首先，请注意，对于 x_k 的每个可能分配，您将在两个概率

1/2

和

1-q

，或

1/2

和

q

之间交替。说

m=3

和

z_1=z_2=z_3=1

。如果没有

μ(...)

，我们可以写：

ν(z_1, z_2, z_3) = (1/2 + q) * (1/2 + q) * (1/2 + q)

这种因式分解可以让我们节省大量的计算量。为了将此方法扩展到 μ 的情况，请注意，我们可以将该因子拉到乘积前面，将其提高到

m

次方。这让我们更接近了，所以现在如果我们可以将上面简洁乘积的类似和分组，这样我们就可以将每个乘以正确的

μ(...)^m

因子，我们就可以完成。

我们做到这一点的方法是引入一个人工变量，

y

。让

y

的每个幂代表另一个

x_i=1

。也就是说，对于

z_i=1

和

x_i=1

，我们有

y/2

，对于

z_i=1

，

x_i=0

我们有

q

，和以前一样。这使得我们之前的产品：

(y/2 + q) ^ 3 = q^3 + 3*q^2*y/2 + 3*q*y^2/4 + y^3/8 

您会看到多项式的系数是之前乘积的部分和，按

x_i=1

项的计数组织。这使我们能够计算每一项的平均值，乘以系数，然后求和。说得更明确一点：

ν(z_1, z_2, z_3) = (0/3)^3 * (q^3) + (1/3)^3 * (3*q^2/2) + (2/3)^3 * (3*q/4) + (3/3)^3 * (1/8)

所以，如果您有

z_1=1

、

z_2=0

、

z_3=1

，请执行以下操作：

ν(1, 0, 1) => P(y) = (y/2 + q) * (y/2 + 1 - q) * (y/2 + q)

然后使用 FFT 将每一项相乘（首先组合最小阶项，依次累加）以获得完整的表达式。获得系数后，像以前一样根据每一项的顺序、乘法和总和计算

μ(...)^m

。

总而言之，这将使您进行

O(n log^2(n))

时间评估，时间由重复的 FFT 主导以获得完整的多项式

P(y)

。