Abstract hidden Markov models

a monadic account of quantitative information flow

Annabelle McIver, Carroll Morgan, Tahiry Rabehaja

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

18 Citations (Scopus)


Hidden Markov Models, HMM's, are mathematical models of Markov processes whose state is hidden but from which information can leak via channels. They are typically represented as 3-way joint probability distributions. We use HMM's as denotations of probabilistic hidden-state sequential programs, after recasting them as 'abstract' HMM's, i.e. Computations in the Giry monad D, and equipping them with a partial order of increasing security. However to encode the monadic type with hiding over state X we use DX→D2X rather than the conventional X→DX. We illustrate this construction with a very small Haskell prototype. We then present uncertainty measures as a generalisation of the extant diversity of probabilistic entropies, and we propose characteristic analytic properties for them. Based on that, we give a 'backwards', uncertainty-transformer semantics for HMM's, dual to the 'forwards' abstract HMM's. Finally, we discuss the Dalenius desideratum for statistical databases as an issue in semantic compositionality, and propose a means for taking it into account.

Original languageEnglish
Title of host publicationProceedings - 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015
Place of PublicationPicataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages12
ISBN (Electronic)9781479988754
ISBN (Print)9781479988471
Publication statusPublished - 31 Jul 2015
Event30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015 - Kyoto, Japan
Duration: 6 Jul 201510 Jul 2015

Publication series

NameAnnual Symposium on Logic in Computer Science
PublisherIEEE Computer Society
ISSN (Print)1043-6871


Other30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015

Fingerprint Dive into the research topics of 'Abstract hidden Markov models: a monadic account of quantitative information flow'. Together they form a unique fingerprint.

Cite this