The Bethe and Sinkhorn approximations of the pattern maximum likelihood estimate and their connections to the Valiant-Valiant estimate
The Bethe and Sinkhorn approximations of the pattern maximum likelihood estimate and their connections to the Valiant-Valiant estimate
复制标题
DOI：
10.1109/ita.2014.6804280
复制
发表时间：
2014-04
期刊：
影响因子：
--
通讯作者：
P. Vontobel
中科院分区：
文献类型：
--
作者：
P. Vontobel
为了估计源的分布直方图，Orlitsky及其同事提出了模式最大似然（PML）估计，即应该选择具有最大可能性产生所观察符号序列的模式的分布直方图。可以证明，找到PML估计值相当于找到使某个非负矩阵的积和最大化的分布直方图。然而，在一般情况下，这个优化问题似乎是棘手的，所以必须计算合适的近似的PML估计。在本文中，我们讨论了各种有效的PML估计近似算法，沿着它们的连接到分布直方图的Valiant-Valiant估计。这些连接是通过将近似双随机矩阵与Valiant-Valiant估计相关联，并将此近似双随机矩阵与PML估计及其近似的自由能描述中出现的双随机矩阵进行比较来建立的。
For estimating a source's distribution histogram, Orlitsky and co-workers have proposed the pattern maximum likelihood (PML) estimate, which says that one should choose the distribution histogram that has the largest likelihood of producing the pattern of the observed symbol sequence. It can be shown that finding the PML estimate is equivalent to finding the distribution histogram that maximizes the permanent of a certain non-negative matrix. However, in general this optimization problem appears to be intractable and so one has to compute suitable approximations of the PML estimate. In this paper, we discuss various efficient PML estimate approximation algorithms, along with their connections to the Valiant-Valiant estimate of the distribution histogram. These connections are established by associating an approximately doubly stochastic matrix with the Valiant-Valiant estimate and comparing this approximately doubly stochastic matrix with the doubly stochastic matrices that appear in the free energy descriptions of the PML estimate and its approximations.