Efficient Computation of the Relative Entropy of Probabilistic Automata
Efficient Computation of the Relative Entropy of Probabilistic Automata
复制标题
概率自动机相对熵的高效计算
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
M. Riley
中科院分区：
文献类型：
--
作者：
Corinna Cortes;M. Mohri;Ashish Rastogi;M. Riley
由确定性加权自动机表示的两个分布的相对熵的有效计算问题在许多机器学习问题中都会出现。我们证明了这个问题可以自然地表示为定义在适当半环上的相交自动机上的最短距离问题。我们描述了简单而高效的新算法来计算它，并报告了实验结果，证明了我们的算法在超大型加权自动机上的实用性。我们的算法适用于明确的加权自动机，这是一类严格包括确定性加权自动机的加权自动机。这些也是第一批将熵或相对熵的计算扩展到确定性加权自动机之外的算法。
The problem of the efficient computation of the relative entropy of two distributions represented by deterministic weighted automata arises in several machine learning problems. We show that this problem can be naturally formulated as a shortest-distance problem over an intersection automaton defined on an appropriate semiring. We describe simple and efficient novel algorithms for its computation and report the results of experiments demonstrating the practicality of our algorithms for very large weighted automata. Our algorithms apply to unambiguous weighted automata, a class of weighted automata that strictly includes deterministic weighted automata. These are also the first algorithms extending the computation of entropy or of relative entropy beyond the class of deterministic weighted automata.