Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: algorytmiczna informacja wzajemna

Sortuj według:

Ogranicz wyniki do:

Ergodic decomposition of excess entropy and conditional mutual information

Dębowski Ł.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

2006

Nr 993

1-34

The article discusses excess entropy defined as mutual information between the past and future of a stationary process. The central result is an ergodic decomposition: Excess entropy is the sum of self-information of shift-invariant sigma-field and the average of excess entropies for the ergodic components of the process. The result is derived using generalized conditional mutual information for fields of events, developed in the paper anew. Some corollary of the ergodic decomposition is that excess entropy is infinite for the class of processes with uncountably many ergodic components, called here uncountable description processes (UDP's). UDP's can be defined without the use of measure theory and the article argues for their potential utility in linguistics. Moreover, it is shown that finite-order excess entropies (some approximations of excess entropy) are dominated by the expected excess lengths of any universal code. Hence, universal codes may be used for rough estimation of excess entropy. Nevertheless, the excess code lengths diverge to infinity for almost every process with zero excess entropy, which is another corollary of the ergodic decomposition.

W artykule omówiono pojęcie entropii nadwyżkowej zdefiniowanej jako informacja wzajemna między przeszłością a przyszłością procesu stacjonarnego. Centralnym rezulatem jest rozkład ergodyczny entropii nadwyżkowej: Entropia nadwyżkowa równa jest sumie entropii sigma-ciała niezmienniczego i wartości oczekiwanej entropii nadwyżkowej losowej miary ergodycznej procesu. Rezultat ten wynika z własności uogólnionej warunkowej informacji wzajemnej, rozwiniętej w artykule w nowatorski sposób. Korzystając z otrzymanego rozkładu ergodycznego, udowodniono, że entropia nadwyżkowa jest nieskończona dla klasy procesów o nieprzeliczalnie wielu składowych ergodycznych, nazwanych procesami nieprzeliczalnego opisu (PNO). Pokazano, że PNO można zdefiniować bez użycia aparatu teoriomiarowego, i zaargumentowano za ich potencjalną użytecznością w lingwistyce. Ponadto udowodniono, że entropie nadwyżkowej skończonego rzędu (pewne przybliżenia entropii nadwyżkowej) są majoryzowane przez nadwyżkowe długości dowolnego kodu uniwersalnego. Zatem kody uniwersalne mogą służyć do zgrubnego szacowania entropii nadwyżkowej. Jednakże, z rozkładu ergodycznego wynika także, że nadwyżkowe długości kodów uniwersalnych rozbiegają do nieskończoności dla prawie każdego procesu o zerowej entropii nadwyżkowej.