“易处理”分布是什么意思？

Question

例如，在生成对抗网络中，我们经常听说推理很容易，因为给定潜在变量 z 的 x 的条件分布是“易于处理的”。
另外，我在某处读到，玻尔兹曼机和变分自动编码器用于后验分布不易处理的情况，因此需要应用某种近似。
谁能告诉我“易处理”的严格定义是什么意思？或者有人可以在我上面给出的任何示例中解释一下，在这种情况下，“易处理”到底意味着什么？

Answer 1

首先，我们来定义一下什么是易处理问题和难处理问题（参考： http: //www.cs.ucc.ie/~dgb/courses/toc/handout29.pdf）。

可处理问题：可以通过多项式时间算法解决的问题。上限是多项式。

棘手问题：多项式时间算法无法解决的问题。下限是指数的。

从这个角度来看，易处理分布的定义是需要多项式时间来计算该分布在任何给定点的概率。

如果一个分布是封闭式表达式，则该分布的概率绝对可以在多项式时间内计算出来，这在学术界意味着该分布是易于处理的。棘手的分布需要等于或大于指数时间，这通常意味着利用现有的计算资源，我们永远无法用相对“短”的时间计算给定点的概率（任何比多项式时间长的时间都是长的...... ）。