Efficient computation of the relative entropy of probabilistic automata

Corinna Cortes, Mehryar Mohri, Ashish Rastogi, Michael D. Riley

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 denned 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.

Original languageEnglish (US)
Title of host publicationLATIN 2006
Subtitle of host publicationTheoretical Informatics - 7th Latin American Symposium, Proceedings
Number of pages14
StatePublished - 2006
EventLATIN 2006: Theoretical Informatics - 7th Latin American Symposium - Valdivia, Chile
Duration: Mar 20 2006Mar 24 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3887 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


OtherLATIN 2006: Theoretical Informatics - 7th Latin American Symposium

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Efficient computation of the relative entropy of probabilistic automata'. Together they form a unique fingerprint.

Cite this