问“可处理的”分布意味着什么？
EN

Stack Overflow用户

提问于 2017-05-06 12:03:56

回答 1查看 1.9K关注 0票数 6

例如，在生成性对抗性网络中，由于x给出的潜在变量z的条件分布是“可处理的”，我们经常听到这样的推论是容易的。

另外，我在某个地方读到，Boltzmann机器和变分自动编码器在后验分布不可处理的情况下使用，所以需要应用某种近似。

有人能告诉我什么是“可驯服”，在一个严格的定义吗？或者有人能在我上面给出的任何例子中解释，在这种情况下，什么是可驯服的意思？

发布于 2019-04-16 21:30:20

首先，让我们定义哪些是可处理的和难以处理的问题(参考：http://www.cs.ucc.ie/~dgb/courses/toc/handout29.pdf)。

可处理问题:用多项式时间算法求解的问题.上界是多项式。难以解决的问题:一个多项式时间算法无法解决的问题.下界是指数的。

从这个角度出发，可处理分布的一个定义是，在任何给定的点上计算这种分布的概率都需要多项式时间。

如果一个分布是一个封闭的表达式，这个分布的概率肯定可以用多项式时间来计算，在学术界，这意味着这个分布是可处理的。难以处理的分布等于或超过指数时间，这通常意味着，在现有的计算资源下，我们永远无法在相对“短”的时间内计算给定点上的概率(任何超过多项式时间的时间都是长的.)。

票数 3

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/43820240

复制

相似问题

问“可处理的”分布意味着什么？EN