Compact Representation of Uncertainty in Clustering
Compact Representation of Uncertainty in Clustering
复制标题
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Craig S. Greenberg;Nicholas Monath;Ari Kobren;Patrick Flaherty;A. Mcgregor;A. McCallum
中科院分区：
文献类型：
--
作者：
Craig S. Greenberg;Nicholas Monath;Ari Kobren;Patrick Flaherty;A. Mcgregor;A. McCallum
对于许多经典的结构化预测问题，可以使用众所周知的算法和数据结构（例如前向-后向及其在马尔可夫模型中对应的精确概率分布的网格）有效地计算因变量的概率分布。然而，据我们所知，之前没有研究研究聚类上精确分布的有效表示。本文提出了动态规划推理过程的定义和证明，该过程精确地计算分区函数、簇的边际概率和 MAP 聚类。这些精确的解决方案所花费的时间和空间与 N 的小得多的幂集成正比，而不是第 N 个贝尔数。事实上，我们将 Kohonen 和 Corander (2016) 针对该问题引入的算法的时间复杂度提高了 N 倍。虽然仍然很大，但这个先前未知的结果本身在智力上很有趣，为重要的现实世界小数据应用（例如医学）提供了可行的精确推理，并为稀疏网格近似提供了天然的垫脚石，从而实现了进一步的可扩展性（我们也探索）。在实验中，我们证明了我们的方法在分析癌症治疗中使用的真实基因表达数据方面优于近似方法。
For many classic structured prediction problems, probability distributions over the dependent variables can be efficiently computed using widely-known algorithms and data structures (such as forward-backward, and its corresponding trellis for exact probability distributions in Markov models). However, we know of no previous work studying efficient representations of exact distributions over clusterings. This paper presents definitions and proofs for a dynamic-programming inference procedure that computes the partition function, the marginal probability of a cluster, and the MAP clustering---all exactly. Rather than the Nth Bell number, these exact solutions take time and space proportional to the substantially smaller powerset of N. Indeed, we improve upon the time complexity of the algorithm introduced by Kohonen and Corander (2016) for this problem by a factor of N. While still large, this previously unknown result is intellectually interesting in its own right, makes feasible exact inference for important real-world small data applications (such as medicine), and provides a natural stepping stone towards sparse-trellis approximations that enable further scalability (which we also explore). In experiments, we demonstrate the superiority of our approach over approximate methods in analyzing real-world gene expression data used in cancer treatment.