在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是各个概率密度函数的FFT的乘积.因此,转换每个PDF,将转换后的PDF相乘,然后执行逆变换.您需要将每个输入PDF用零填充到适当的长度,以避免环绕效果.

这应该是相当有效的:如果你有mPDF,每个包含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(和它的逆numpy.fft.irfft),它利用了输入是真实的事实来产生更紧凑的变换数组.您也可以通过rows用零填充数组来获得一些速度,以便总列数最适合执行FFT.这里"最佳"的定义将取决于FFT实现,但例如,2的幂将是良好的目标.最后,rows如果所有输入数组具有相同的长度,则在创建时可以进行一些明显的简化.但是我会把这些潜在的改进留给你.