Efficient Methods for Lifted Inference with Aggregate Factors
Efficient Methods for Lifted Inference with Aggregate Factors
复制标题
利用聚合因素进行提升推理的有效方法
DOI：
10.1609/aaai.v25i1.8025
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
H. Bui
中科院分区：
文献类型：
--
作者：
Jaesik Choi;Rodrigo de Salvo Braz;H. Bui
概率关系模型中的聚合因子（即基于SUM、AVERAGE、AND等聚合函数的因子）可以简洁地表示大量关系随机变量之间的依赖关系。然而，对将 n 个 k 值随机变量聚合为 r 值结果随机变量的因子的命题推理是 O(r k 2n)。提升方法可以将其改善为一般情况下的 O(r nk) 和可交换关联聚合器的 O(r k log n) 。在本文中，我们提出 (a) 对于某些聚合运算（例如 AND、OR 和 SUM），当 k = 2 时，n 中的精确解常数；以及 (b) 时间复杂度常数为 n 的聚合因子推理的近似值。此近似推理涉及 k > 2 时某些操作的解析解。该近似基于以下事实：通常使用的聚合函数可以由 Rk 中的标准 (k –1)-单纯形中的线性约束表示，其中 k 是随机变量的可能值的数量。这甚至包括可交换但不可关联的聚合函数（例如，选择最频繁值的 MODE 运算符）。我们的算法需要以 k 为单位的多项式时间（对于二元变量只有 2），无论 r 和 n 是多少，并且误差随着 n 的增加而减小。因此，对于大多数应用（其中近似值就足够了），我们的算法是比现有算法更有效的解决方案。我们提出了支持这些主张的实验结果。我们还提出了（c）第三个贡献，它进一步优化了具有不同分布的多组随机变量的聚合。
Aggregate factors (that is, those based on aggregate functions such as SUM, AVERAGE, AND etc.) in probabilistic relational models can compactly represent dependencies among a large number of relational random variables. However, propositional inference on a factor aggregating n k-valued random variables into an r-valued result random variable is O(r k 2n). Lifted methods can ameliorate this to O(r nk) in general and O(r k log n) for commutative associative aggregators. In this paper, we propose (a) an exact solution constant in n when k = 2 for certain aggregate operations such as AND, OR and SUM, and (b) a close approximation for inference with aggregate factors with time complexity constant in n. This approximate inference involves an analytical solution for some operations when k > 2. The approximation is based on the fact that the typically used aggregate functions can be represented by linear constraints in the standard (k –1)-simplex in Rk where k is the number of possible values for random variables. This includes even aggregate functions that are commutative but not associative (e.g., the MODE operator that chooses the most frequent value). Our algorithm takes polynomial time in k (which is only 2 for binary variables) regardless of r and n, and the error decreases as n increases. Therefore, for most applications (in which a close approximation suffices) our algorithm is a much more efficient solution than existing algorithms. We present experimental results supporting these claims. We also present a (c) third contribution which further optimizes aggregations over multiple groups of random variables with distinct distributions.