“易于处理”的分布是什么意思?

机器算法验证 推理 变分贝叶斯
2022-02-11 04:13:11

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

3个回答

就我最好的记忆而言,我从未在统计文本中遇到过正式的定义,但我认为您可以从一些上下文阅读中将其拼接在一起。从贝叶斯数据分析开始,p。261:

贝叶斯计算围绕两个步骤进行:计算后验分布和计算后验预测分布到目前为止,我们已经考虑了可以以封闭形式进行分析计算的示例[.]p(θ|y)p(y^|y)

障碍通常是边际似然,即贝叶斯规则右侧的分母,它可能涉及无法解析表达的积分。对于更多信息,我认为您会发现 wiki 关于封闭式表达式的文章对上下文很有帮助(强调我的):

在数学中,封闭式表达式是可以在有限数量的操作中计算的数学表达式。它可能包含常数、变量、某些“众所周知的”运算(例如,+ − × ÷)和函数(例如,n 次方根、指数、对数、三角函数和反双曲函数),但通常没有限制。封闭式表达式中允许的操作和函数集可能随作者和上下文而变化

如果问题可以用封闭式表达式来解决,则称这些问题是易处理的

如果您继续阅读,您将看到一个表达式类别表,并且“解析表达式”包括几个涉及指数族分布的归一化常数的表达式。例如,gamma 分布中的 gamma 函数,以及 von-Mises Fisher 中的 Bessel 函数。

意思是,我们愿意至少将这些纳入我们对“易处理性”的定义。(可能还有其他分布涉及归类为“分析表达式”的操作类别;我承认我不熟悉。)

除了 Sean Easter 的回答,我将尝试从计算成本的角度阐明一些观点。

首先,让我们定义什么是易处理和难处理的问题(参考:http ://www.cs.ucc.ie/~dgb/courses/toc/handout29.pdf )。

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

棘手问题:不能用多项式时间算法解决的问题。下界是指数的。

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

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

如果可以在线性时间内计算出任何由它引起的边际概率,则称该分布为易处理的