Computation of Universal Objects for Distributions Over Co-Trees

Henrik Densing Petersen; Flemming Topsøe

doi:10.1109/tit.2012.2210477

Computation of Universal Objects for Distributions Over Co-Trees

Henrik Densing Petersen, Flemming Topsøe

Institut for Matematiske Fag

1 Citationer (Scopus)

Abstract

For an ordered set, consider the model of distributions P for which an element that precedes another element is considered the more significant one in the sense that the implication a ≤ b⇒ P(a) ≥ P(b) holds. It will be shown that if the ordered set is a finite co-tree, then the universal predictor for the model or, equivalently, the corresponding universal code, can be determined exactly via an algorithm of low complexity. Natural relations to problems on the computation of capacity and on the determination of information projections are established. More surprisingly, a direct connection to a problem of isotone regression also appears possible.

Originalsprog	Engelsk
Tidsskrift	I E E E Transactions on Information Theory
Vol/bind	58
Udgave nummer	12
Sider (fra-til)	7021-7035
ISSN	0018-9448
DOI	https://doi.org/10.1109/tit.2012.2210477
Status	Udgivet - 2012

Adgang til dokumentet

10.1109/tit.2012.2210477

Citationsformater

@article{efe915bb6cb14224b2f0930d6b01b446,

title = "Computation of Universal Objects for Distributions Over Co-Trees",

abstract = "For an ordered set, consider the model of distributions P for which an element that precedes another element is considered the more significant one in the sense that the implication a ≤ b⇒ P(a) ≥ P(b) holds. It will be shown that if the ordered set is a finite co-tree, then the universal predictor for the model or, equivalently, the corresponding universal code, can be determined exactly via an algorithm of low complexity. Natural relations to problems on the computation of capacity and on the determination of information projections are established. More surprisingly, a direct connection to a problem of isotone regression also appears possible.",

author = "Petersen, {Henrik Densing} and Flemming Tops{\o}e",

year = "2012",

doi = "10.1109/tit.2012.2210477",

language = "English",

volume = "58",

pages = "7021--7035",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers",

number = "12",

}

TY - JOUR

T1 - Computation of Universal Objects for Distributions Over Co-Trees

AU - Petersen, Henrik Densing

AU - Topsøe, Flemming

PY - 2012

Y1 - 2012

N2 - For an ordered set, consider the model of distributions P for which an element that precedes another element is considered the more significant one in the sense that the implication a ≤ b⇒ P(a) ≥ P(b) holds. It will be shown that if the ordered set is a finite co-tree, then the universal predictor for the model or, equivalently, the corresponding universal code, can be determined exactly via an algorithm of low complexity. Natural relations to problems on the computation of capacity and on the determination of information projections are established. More surprisingly, a direct connection to a problem of isotone regression also appears possible.

AB - For an ordered set, consider the model of distributions P for which an element that precedes another element is considered the more significant one in the sense that the implication a ≤ b⇒ P(a) ≥ P(b) holds. It will be shown that if the ordered set is a finite co-tree, then the universal predictor for the model or, equivalently, the corresponding universal code, can be determined exactly via an algorithm of low complexity. Natural relations to problems on the computation of capacity and on the determination of information projections are established. More surprisingly, a direct connection to a problem of isotone regression also appears possible.

U2 - 10.1109/tit.2012.2210477

DO - 10.1109/tit.2012.2210477

M3 - Journal article

SN - 0018-9448

VL - 58

SP - 7021

EP - 7035

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 12

ER -