Python 中概率密度函数的更快卷积

Question

假设需要计算一般数量的离散概率密度函数的卷积。对于下面的示例，有四种分布，它们具有指定概率的值 0、1、2：

import numpy as np
pdfs = np.array([[0.6,0.3,0.1],[0.5,0.4,0.1],[0.3,0.7,0.0],[1.0,0.0,0.0]])

卷积可以这样找到：

pdf = pdfs[0]        
for i in range(1,pdfs.shape[0]):
    pdf = np.convolve(pdfs[i], pdf)

看到 0,1,...,8 的概率由

给出

array([ 0.09 ,  0.327,  0.342,  0.182,  0.052,  0.007,  0.   ,  0.   ,  0.   ])

这部分是我代码中的瓶颈，似乎必须有一些可用的东西来矢量化这个操作。有没有人有让它更快的建议？

或者，您可以使用的解决方案

pdf1 = np.array([[0.6,0.3,0.1],[0.5,0.4,0.1]])
pdf2 = np.array([[0.3,0.7,0.0],[1.0,0.0,0.0]])
convolve(pd1,pd2)

并得到成对卷积

 array([[ 0.18,  0.51,  0.24,  0.07,  0.  ], 
        [ 0.5,  0.4,  0.1,  0. ,  0. ]])

也会有很大帮助。

Answer 1

您可以使用快速傅里叶变换 (FFT) 有效地计算所有 PDF 的卷积：关键事实是 FFT of the convolution 是各个概率密度函数的 FFT 的乘积。所以对每个PDF进行变换，将变换后的PDF相乘，然后进行逆变换。您需要用零填充每个输入 PDF 以达到适当的长度，以避免回绕的影响。

这应该相当有效：如果您有 m 个 PDF，每个包含 n 个条目，那么使用此方法计算卷积的时间应该增加为 (m^2)n log(mn)。时间主要由 FFT 控制，我们正在有效地计算 m + 1 个独立的 FFT（m 个正向变换和一个反向变换），每个 FFT 的长度不大于 mn 个数组。但一如既往，如果你想要真正的时间，你应该分析。

这是一些代码：

import numpy.fft

def convolve_many(arrays):
    """
    Convolve a list of 1d float arrays together, using FFTs.
    The arrays need not have the same length, but each array should
    have length at least 1.

    """
    result_length = 1 + sum((len(array) - 1) for array in arrays)

    # Copy each array into a 2d array of the appropriate shape.
    rows = numpy.zeros((len(arrays), result_length))
    for i, array in enumerate(arrays):
        rows[i, :len(array)] = array

    # Transform, take the product, and do the inverse transform
    # to get the convolution.
    fft_of_rows = numpy.fft.fft(rows)
    fft_of_convolution = fft_of_rows.prod(axis=0)
    convolution = numpy.fft.ifft(fft_of_convolution)

    # Assuming real inputs, the imaginary part of the output can
    # be ignored.
    return convolution.real

将此应用于您的示例，这是我得到的结果：

>>> convolve_many([[0.6, 0.3, 0.1], [0.5, 0.4, 0.1], [0.3, 0.7], [1.0]])
array([ 0.09 ,  0.327,  0.342,  0.182,  0.052,  0.007])

这是基本思想。如果你想调整它，你也可以看看 numpy.fft.rfft (and its inverse, numpy.fft.irfft)，它利用输入是真实的这一事实来产生更紧凑的转换数组。您还可以通过用零填充 rows 数组来提高速度，以便列的总数最适合执行 FFT。这里 "optimal" 的定义将取决于 FFT 实现，但例如，2 的幂将是很好的目标。最后，如果所有输入数组的长度都相同，则在创建 rows 时可以进行一些明显的简化。但我会将这些潜在的增强功能留给您。

Python 中概率密度函数的更快卷积

Faster convolution of probability density functions in Python

python

numpy

vectorization

convolution

probability-density