Véges mintázatok információtartalma és entrópiája kombinatorikai szemszögből

Kivonat

Különböző típusú mintázatok információtartalmának és entrópiájának egységes, a hagyományos információ- és entrópiafogalmakkal kompatibilis kombinatorikai meghatározása, túllépve az ergodikus Markov-folyamatokra értelmezhető Shannon-információ korlátain. Különböző típusú véges mintázatok információtartalmát hasonlítjuk össze és ebből meghatározzuk az infromációmennyiség általános tulajdonságait, és ezek segítségével definiálunk Kolmogorov-komplexitás és a tömörítési algoritmusokon alapuló normalizált információbecslési módszereket. A kombinatorikai nézőpont alapján újradefiniáljuk az entrópia fogalmát a hagyományos entrópiával aszimptotikusan kompatibilis módon.

1. Bevezetés

Az anyag jellemzője a mintázata, amit tág értelemben értelmezünk, mint az elemi részek elrendeződését. Ez magába foglalja az egyes részek közötti kapcsolatokat is. A fizikai valóságban minden véges dimenziós mintázat valamilyen pontossággal modellezhető egy dimenziós véges sorozatként, ezért az információt és az entrópiát véges sorozatokkal (mintázatokkal) összefüggésben vizsgáljuk. Jelölje

X^{*}

a véges mintázatok halmazát, ahol

X

halmaz a mintázatok értékkészlete vagy más néven alaphalmaza. Egy adott

A \in X^{*}

A = (x_{1}, x_{2}, ..., x_{n})

mintázat esetén jelölje

n = | A |

a mintázat hosszát,

k = | X |

az értékkészlet elemszámát,

f (x)

x \in X

pedig az

x

elem előfordulási számát a mintázatban.

Az információ nem más, mint a bináris döntések száma [6], amellyel egy mintázat egyértelműen meghatározható, vagyis kombinatorikailag a döntések száma, amivel az adott mintázat kiválasztható az összes lehetséges mintázat és az üres mintázat közül. Az információ alapegysége a bináris döntés, amelynek

b i t

a mértékegysége. A gyakorlatban a a döntések száma csak egész számot vehet fel, de ha folytonos függvényt használunk, nem kapunk mindig egész értékeket, ami a döntések elméleti száma. A matematikai számítások egyszerűsítése érdekében a döntések számán a továbbiakban mindig az elméleti döntésszámot értjük. Ezért és más okokból is az információmennyiség meghatározása mindig közelítő meghatározás.

1. definíció Egy véges

A \in X^{*}

mintázat információja legyen a mintázat egyértelmű meghatározásához szükséges bináris döntések minimális száma, jelölése legyen

I (A)

, ahol

I : X^{*} \to R^{+}

függvény és

\begin{matrix} I (A) = m i n {n | A r e p r o d u k á l h a t ó (d_{1}, d_{2}, ..., d_{n}) e l e m i d ö n t é s s o r o z a t t a l} boxempty & (1) \end{matrix}

Ez a definíció általános, mivel nem függ semmilyen konkrét rendszertől, tisztán elméleti, mivel minden implicit információ explicit módon beépül, és filozófiailag kevéssé vitatható, mert a minimális döntések száma az információtartalom legáltalánosabb mértéke. Ugyanakkor a definícióban található fogalmak nincsenek pontosan meghatározva ahhoz, hogy a gyakorlatban vagy akár elméletben alkalmazható legyen: nem rögzítettük, mit nevezünk pontosan elemi döntésnek és reprodukálhatóságnak és az sem, hogy egy mintázat létrehozásának a leírását hogyan bontjuk elemi döntésekre.

A fenti információ definíció egy speciális esete a Kolmogorov-komplexitás [4], amely egy univerzális Turing-géppel határozza meg, hogy hány döntés szükséges a mintázatok leírásához:

2. definíció Legyen

U

egy rögzített univerzális Turing-gép. Ekkor egy véges

A \in X^{*}

mintázat Kolmogorov-komplexitása

I_{K} (A

) az alábbi módon adható meg:

\begin{matrix} I_{K} (A) = m i n ∣ B ∣ : U (B) = A & (2) \end{matrix}

ahol

∣ B ∣

a bináris program (bitsorozat) hosszát jelöli, és a minimumot azon

B

programok között keressük, amelyek bemenetként véve a

U

univerzális Turing-gépen pontosan

A

-t állítanak elő kimenetként.

boxempty

A Kolmogorov-komplexitás sajnos általánosságban nem kiszámítható [1]. Az információtartalom bizonyos határesetekben azonban nagyon pontosan, explicit módon meghatározható: ilyen például a számok, a konstans mintázatok az egyenletes eloszlású véletlen mintázatok és bizonyos jól meghatározott statisztikai jellemzőkkel rendelkező mintázatok, mint pl. az ergodikus Markov-folyamatokkal előállítható mintázatok.

Ha az információ meghatározásához elméleti és gyakorlati téren is pontosabb módszereket keresünk, mindenképpen érdemes először a határeseteket és az említett speciális eseteket vizsgálni.

2. Konstans mintázat információja

Konstans és véges

A \in {a}^{*}

mintázat esetén a mintázat egyes elemeinek a meghatározásához nincs szükség információra, mivel egyetlen elemet ismétlünk. Egyedül a mintázat hossza, azaz

n

hordoz információt, melynek meghatározásához maximum

⌈ l o g_{2} n ⌉

döntésre (információra) van szükség, mert minden döntés megfelezi a lehetőségeket. Az egyszerűség és a matematikai kezelhetőség kedvéért használjuk a

l o g_{2} n

elméleti közelítést.

Az egész számok információjából kiindulva bármilyen azonos elemekből álló mintázat információtartalma kiszámolható, ha az információt az összes lehetséges részmintázatból való kiválasztásként értelmezzük, beleértve a nulla hosszúságú mintázatot.

A mintázat elemeiből összerakható összes lehetséges mintázat számának logaritmusa adja a konkrét mintázat információtartalmát, ekkor az

A

mintázat információja:

\begin{matrix} I_{c o n s t} (A) = l o g_{2} (n + 1) & (3) \end{matrix}

n

helyett az

n + 1

azért praktikusabb, mert így az üres mintázat információtartalma is értelmezve van és figyelembe vesszük, hogy az üres mintázat, mint lehetőség is hordoz információt. Könnyű belátni, hogy a véges mintázatok közül a konstans mintázatok információtartalma a legalacsonyabb, mert a nem konstans mintázatokban a különböző elemek miatt több döntés szükséges a mintázat egyértelmű meghatározásához, ami növeli az információtartalmat.

Azért sem használjuk az

l o g_{2} (n)

képletet, mert akkor egységnyi hosszúságú mintázatok esetén a szubadditivitás nem teljesül. A szubadditivitás feltétele

I_{r a n d} (a b) \leq I_{r a n d} (a) + I_{r a n d} (b)

. Ha a

l o g_{2} n

képletet használnánk, akkor

n = 1

hosszúságú mintázatok konkatenációja esetén a szubadditivitás nem teljesülne:

l o g_{2} (2) ≰ l o g_{2} (1) + l o g_{2} (1)

. A

l o g_{2} (n + 1)

képlet esetén viszont a szubadditivitás minden

n \geq 0

esetén teljesül:

$n_{1}$	$n_{2}$	Szubadditivitás
$0$	$0$	$l o g_{2} 1 \leq l o g_{2} 1 + l o g_{2} 1$
$0$	$1$	$l o g_{2} 2 \leq l o g_{2} 1 + l o g_{2} 2$
$1$	$1$	$l o g_{2} 3 \leq l o g_{2} 2 + l o g_{2} 2$
$1$	$2$	$l o g_{2} 4 \leq l o g_{2} 2 + l o g_{2} 3$
$2$	$2$	$l o g_{2} 5 \leq l o g_{2} 3 + l o g_{2} 3$

Táblázat 2: A szubadditivitás teljesülése különbőző hosszúságú egyenletes eloszlású véletlen sorozatok esetén.

3. Egyenletes eloszlású véletlen mintázat információja

Az egyenletes eloszlású véges mintázat

A \in X^{*}

úgy állítható elő, hogy a mintázat minden eleme egy

l o g_{2} (k)

bites független döntés eredménye. Figyelembe véve, hogy az üres mintázatot is számolva

n + 1

különböző hosszúságú mintázat közül választhatunk, a mintázat információtartalma:

\begin{matrix} I_{r a n d} (A) = l o g_{2} \sum_{i = 0}^{n} k^{i} & (4) \end{matrix}

Ha a

k = 1

, vagyis az

A

konstans mintázat, akkor a képlet a konstans mintázat képletére egyszerűsíthető:

I_{r a n d} (A) = l o g_{2} \sum_{i = 0}^{n} 1^{i} = l o g_{2} (n + 1)

I_{r a n d} (A) = l o g_{2} (\sum_{i = 0}^{n} k^{i}) = l o g_{2} (\frac{k^{n + 1} - 1}{k - 1})

komplexitása

O (n \cdot l o g_{2} (k))

, tehát elegendően nagy

n

és

k

esetén

I_{r a n d} (A) \approx n \cdot l o g_{2} (k)

képlettel is számítható. A

n \cdot l o g_{2} (k)

képletet használva azonban a konstans mintázatok esetéhez hasonlóan nem teljesülne a szubadditivitás:

2 \cdot l o g_{2} (2) ≰ 1 \cdot l o g_{2} (1) + 1 \cdot l o g_{2} (1)

, és a konstans mintázatok esetén sem kapnánk megfelelő képletet.

4. Ergodikus Markov-folyamattal előállítható mintázat információja

Legyen

A \in X^{*}

mintázat, amely ergodikus Markov-folyamattal előállítható, és legyenek

f_{r e l} (x_{i}) = \frac{f (x_{i})}{n}

x_{i} \in X

i = 1, ..., k

az egyes értékek relatív gyakoriságai a mintázatban. Shannon eredeti

I_{S h a n n o n} (A) = \sum_{i = 1}^{k} f_{r e l} (x_{i}) l o g_{2} \frac{1}{f_{r e l} (x_{i})}

képlete [6] nem lenne kompatibilis az egyenletes eloszlású mintázatok és a konstans mintázatok képleteivel, azért módosítani kell. A mintázat információja Shannon képletét módosítva:

\begin{matrix} I_{m a r k} (A) = l o g_{2} \sum_{i = 0}^{n} \prod_{x \in X} f_{r e l} (x)^{- i \cdot f_{r e l} (x)} & (5) \end{matrix}

Ha a

k = 1

, vagyis az

A

konstans mintázat, azaz

f_{r e l} (x) = 1

x \in X

akkor a képlet a konstans mintázat képletére egyszerűsíthető:

I_{m a r k} (A) = l o g_{2} \sum_{i = 0}^{n} \prod_{x \in X} 1^{- i} = l o g_{2} (n + 1)

Egyenletes eloszlású folyamattal előállítható mintázat esetén, ahol

f_{r e l} (x_{i}) = \frac{1}{k}

x_{i} \in X

i = 1, ..., k

, vagyis az értékek relatív gyakoriságai azonosak, a képlet az egyenletes eloszlású mintázat információ képletére egyszerűsödik:

I_{m a r k} (A) = l o g_{2} \sum_{i = 0}^{n} \prod_{x \in X} (\frac{1}{k})^{- i \cdot \frac{1}{k}} = l o g_{2} \sum_{i = 0}^{n} \prod_{x \in X} k^{i \cdot \frac{1}{k}} = l o g_{2} \sum_{i = 0}^{n} k^{i}

Megmutatható, hogy

l i m_{n \to \infty} I_{m a r k} (A) = I_{S h a n n o n}

. Legyen

c = \prod_{x \in X} f_{r e l} (x)^{- f_{r e l} (x)}

. Ha

n \to \infty

, akkor

I_{m a r k} (A) = l o g_{2} \sum_{i = 0}^{n} c^{i} \approx l o g_{2} (\frac{c^{n + 1} - 1}{c - 1}) \approx n \cdot l o g_{2} c

. Ebből következik, hogy

I_{m a r k} (A) \approx n \cdot l o g_{2} \prod_{x \in X} f_{r e l} (x)^{- f_{r e l} (x)}

, ami a logaritmus tulajdonságai alapján a

I_{m a r k} (A) \approx n \cdot \sum_{x \in X} l o g_{2} (f_{r e l} (x)^{- f_{r e l} (x)})

alakra hozható, ami tovább alakítva

I_{m a r k} (A) \approx n \cdot \sum_{x \in X} f_{r e l} (x) \cdot l o g_{2} (\frac{1}{f_{r e l} (x)}) = I_{S h a n n o n} (A)

Az információmérési képlet átírható logaritmus segítségével

I_{m a r k} (A) = l o g_{2} (\sum_{i = 0}^{n} 2^{- i \sum_{x \in X} f_{r e l} (x) l o g_{2} f_{r e l} (x)})

alakba. Mivel a

- l o g_{2} x

függvény konvex, ezért alkalmazhatjuk a Jensen-egyenlőtlenséget:

\sum_{x \in X} f_{r e l} (x) l o g_{2} f_{r e l} (x) \leq l o g_{2} (\sum_{x \in X} f_{r e l} (x) \cdot 1)

, ami nem más, mint

\sum_{x \in X} f_{r e l} (x) l o g_{2} f_{r e l} (x) \leq 0

. Az egyenlőség akkor áll fenn, ha az összes

f_{r e l} (x)

azonos, azaz

f_{r e l} (x) = \frac{1}{k}, \forall x \in X

. Tehát az ergodikus Markov-folyamatokkal előállítható véges mintázatok információtartalma pontosan akkor maximális, ha minden érték azonos gyakorisággal fordul elő a mintázatban, és ebből következik, hogy az egyenletes eloszlású véletlen mintázatok rendelkeznek a maximális információmennyiséggel és az információtartalmuk

l o g_{2} \sum_{i = 0}^{n} k^{i}

Shannon az ergodikus Markov-folyamatokra határozta meg az információt [6], de fontos tudni, hogy a gyakorlatban a mintázatok jelentős része nem hozható létre ergodikus Markov-folyamattal, ezért Shannon képlete ezekben az esetekben nem használható információ- és entrópiamérésre. Az összes lehetséges véges mintázat között csak egy viszonylag kis rész az, amely ergodikus Markov-folyamattal létrehozható. Ennek oka, hogy az ergodikus Markov-folyamatok által generált mintázatoknak meg kell felelniük bizonyos statisztikai tulajdonságoknak és átmeneti valószínűségeknek. Shannon módszerénél általánosabb megoldást kínál Kolmogorov [4]. A Kolmogorov-komplexitás A Shannon-információval ellentétben minden létező véges mintázat esetén értelmezhető.

5. Általános mintázatok információtartalma

5..1 Az információ általános tulajdonságai

A speciális mintázatok információjából következtethetünk az információ általános tulajdonságaira. [3]. Könnyen belátható a következő állítás:

A random mintázat

I_{r a n d}

információtartalma a legnagyobb és a konstans mintázaté

I_{c o n s t}

a legkisebb. A Kolmogorov-komplexitás a Turing-gépekre épül, ezért nem minden esetben képes olyan rövid leírást adni egy véges mintázatra, amelyet Turing-gép nélkül, más módszerrel adhatnánk:

I_{K}

nagyon jól közelíti az információtartalmat, de lehet nála nagyobb. Az ergodikus Markov-sorozatokra optimalizált

I_{m a r k}

módosított Shannon-információ nem ergodikus és nem Markov-folyamatok esetén az információtartalmat felülbecsüli, és a kevésbé véletlenszerű mintázatok esetén magasabb értéket ad.

A normalizálás tulajdonsága következik a konstans mintázat

I_{c o n s t} (A) = l o g_{2} (n + 1)

és az egyenletes eloszlású véletlen mintázat

I_{r a n d} (A) = l o g_{2} \sum_{i = 0}^{n} k^{i}

információjából és az 1. állításból.

A szubadditivitás könnyen belátható a konstans mintázat esetén:

l o g_{2} (n + m + 1) \leq l o g_{2} (n + 1) + l o g_{2} (m + 1)

, ami átalakítva

l o g_{2} (n + m + 1) \leq l o g_{2} (n \cdot m + n + m + 1)

, ez minden esetben telesül. Ergodikus Markov-folyamatok esetén legyen

C = \prod_{x \in X} f_{r e l} (x)^{f (x)}

, ekkor az egyenlőtlenség

l o g_{2} \sum_{i = 0}^{n + m} C^{- i} \leq l o g_{2} \sum_{i = 0}^{n} C^{- i} + l o g_{2} \sum_{i = 0}^{m} C^{- i},

ami átalakítva

\sum_{i = 0}^{n + m} C^{- i} \leq (\sum_{i = 0}^{n} C^{- i}) (\sum_{i = 0}^{m} C^{- i})

. A jobb oldali összeget átalakítva

\sum_{i = 0}^{n + m} C^{- i} \leq \sum_{i = 0}^{n} \sum_{j = 0}^{m} C^{- (i + j)} = \sum_{i = 0}^{n + m} (\sum_{k, l; k + l = i} C^{- i})

. Minden k-hoz legalább egy

(k, l)

pár létezik, mely teljesíti a feltételeket. Ez azt jelenti, hogy a belső összegek legalább egyszer tartalmazzák a

C^{- k}

tagot, ezért az egyenlőtlenség teljesül.

A reverzibilitás azt jelenti, hogy mindegy, melyik oldalról kezdjük el olvasni a mintázatot, az nem befolyásolja az információtartalmát, ami triviális, mert a mintázatot az értelmező könnyedén megfordíthatja. A monotonitás szintén triviális a konstans mintázatok és az ergodikus Markov-folyamattal előállítható mintázatok esetén egyaránt.

Legyen

A^{r} = A A ... A

redundáns,

n r

hosszúságú mintázat. Ekkor

I_{c o n s t} (A^{r}) = l o g_{2} (n r + 1) = l o g_{2} (n + 1) + l o g_{2} r + l o g_{2} (\frac{n r + 1}{(n + 1) r})

. A

l o g_{2} (\frac{n r + 1}{(n + 1) r})

kifejezés értéke

n

és

r

növekedésével 0-hoz közelít, így korlátos, ezért mindig van olyan

c \in R_{0}

, hogy

| I (A^{r}) - (I (A) + l o g_{2} (r)) | < c

. Véletlenszerű és ergodikus Markov-folyamatok esetén és általános esetben is intuitív módon belátható az összefüggés.

5..2 Információ számítása Kolmogorov-komplexitás alapján

Az információ az 1. definícióban ismertetett általános meghatározása szorosan kapcsolódik a 2. definícióban meghatározott Kolmogorov-komplexitáshoz [4], amely egy adott univerzális gépen a mintázatokat előállító legrövidebb bináris programkódok hosszaként határozza meg a mintázatok információtartalmát.

A Kolmogorov-komplexitás esetén az univerzális gép rögzítése biztosítja, hogy a különböző mintázatok információja összehasonlítható legyen, az univerzális gépek eredményei között ugyanis lehet konstans eltérés. Az eltérések hosszabb mintázat esetén elhanyagolhatók, rövid mintázatoknál viszont jelentősek lehetnek. Az információ és a Kolmogorov-komplexitás közti kapcsolatot a

K (A) = I (A) + c

képlettel jellemezhetjük [2], ahol

c

K

kiszámításához használt univerzális gépre jellemző konstans érték. Mivel az

I_{m i n} (A)

minimális információt pontosan ismerjük, így a konstans eltérést kiküszöbölve meghatározható az információ Kolmogorov-komplexitás alapján történő mérése:

5..3 Információ számítása tömörítési algoritmus alapján

A Kolmogorov-komplexitás, vagyis az információ pontos meghatározása azonban általános mintázatok esetén elméletileg lehetetlen, csak közelíteni lehet, és erre a legjobbak a veszteségmentes tömörítési algoritmusok. [5] Az ezekkel tömörített mintázatok a nagy információsűrűség miatt közel véletlenszerűek. Ha a betömörített mintázat információtartalmát megmérjük véletlenszerű mintázatot feltételezve, akkor megkapjuk a közelítő információtartalmát az eredeti mintázatnak. A tömörítési algoritmusokra jellemző, hogy a tömörített kódba gyakran a kitömörítéshez szükséges algoritmust és más adatokat is beleírnak, ami kisebb mintázatok tömörítésekor arányaiban nagy többletinformációt jelent, ezért az eredményül kapott információt normálni kell.

A tömörítő függvényt az egyszerűség kedvéért úgy definiáltuk, hogy a tömörítetlen és a tömörített mintázatoknak azonos legyen az értékkészlete.

6. definíció Legyen

A \in X^{n}

tetszőleges mintázat,

C : X^{*} \to X^{*}

tetszőleges tömörítési algoritmus, akkor az

A

mintázat

C

tömörítési algoritmussal mért információja legyen:

I_{C} (A) = \frac{I_{m a x} C (A) - I_{m i n}^{C} (A)}{I_{m a x}^{C} (A) - I_{m i n}^{C} (A)} \cdot I_{m a x} (A) + I_{m i n} (A)

ahol

I_{m i n}^{C} (A) = {min}_{A \in X^{n}} I_{m a x} (C (A))

I_{m a x}^{C} (A) = {max}_{A \in X^{n}} I_{m a x} (C (A)) boxempty

I_{m i n}^{C}

és

I_{m a x}^{C}

meghatározása a definíció alapján a gyakorlatban látszólag körülményes, de ha figyelembe vesszük, hogy a tömörített mintázatok a nagy információsűrűség miatt közel véletlenszerűek, és ezért Markov-folyamattal jól modellezhetők, akkor alkalmazhatjuk a következő közelítést:

I_{m i n}^{C} (A) = I_{m a r k} (C (B))

I_{m a x}^{C} (A) = I_{m a r k} (C (D))

ahol

B \in X^{n}

tetszőleges konstans mintázat és

D \in X^{n}

tetszőleges egyenletes eloszlású véletlen mintázat.

image: 0_media_PROJECTS_Publik__ci__k_2024_-_V__ges_mi____s_entr__pi__ja_Magyar_kulonbseg_vizszintes.png

Ábra 1: Az ábrán különböző értékkészletű, 1000 karakter hosszúságú mintázatok (FÜGGELÉK I.) információértékeinek az összehasonlítása látható. M: a maximális információmennyiséget jelöli, ami az adott hosszúságú és adott értékkészletű mintázat esetében lehetséges. S: a mintázat módosított Shannon-információja. T: a mintázat GZip tömörítési algoritmussal mért információja. K: a mintázat közelítő Kolmogorov-komplexitása. A véletlen mintázat egy bizonyos fokú redundanciával rendelkező véletlen bináris mintázat, a struktúrált mintázat pedig egy 40x25 méretű bináris karaktermátrix, amelyen az 1-es szimbólumok koncentrikus körökben helyezkednek el. Látszik, hogy a Fibonacci-sorozat információtartalmát a látszólagos véletlenszerűsége miatt még a tömörítési algoritmus sem tudta meghatározni, míg a Kolmogorov-komplexitása alacsony információtartalmat mutat. Az angol szöveg és a véletlen mintázat esetén a Shannon-féle módszer és a tömörítési algoritmus egyaránt jó eredményt adott. A struktúrált szöveg esetén viszont a tömörítési algoritmus látványosan jobban közelíti a valós információtartalmat, mint a Shannon-féle képlet, amely a véletlenszerű mintázatokra lett kitalálva. (A használt algoritmuosok a FÜGGELÉK II-IV-ben olvashatók.)

A különböző információmérési módszerek különböző struktúrák esetén eltérő hatékonyságúak, ezért nagyobb pontosság érhető el, ha többféle módszerrel mért információ eredményeinek a minimumát vesszük.

6. Véges mintázatok entrópiája

Az entrópia az információval ellentétben a mintázatnak egy átlagos jellemzőjét jelenti, az egy elem meghatározásához szükséges átlagos információmennyiséget. A legtöbb esetben az entrópiát - tévesen - a Shannon-entrópiával azonosítják [7], amely ergodikus Markov-folyamatok esetén közelíti csak jól az elemenkénti átlagos információtartalmat. A Kolomogorov-komplexitásból számolt entrópia jobb közelítést ad és általánosabb, ezért az entrópiát célszerűbb az információtartalom alapján definiálni, ahol az információtartalom mérésének módszere nem meghatározott.

A \in X^{*}

konstans sorozat,

X = {a}

, és

()

jelöli az üres sorozatot, az entrópia az üres mintázatot is figyelembe véve, kombinatorikai szempontból a következő képpen értelmezhető:

Általánosságban az entrópiát ebben az értelmezésben az alábbi módon definiálhatjuk.

n + 1

a nevezőben lehetővé teszi a képlet üres mintázatokon való értelmezését. Konstans

A \in X^{*}

mintázat esetén, ha

| X | = 1

, az entrópia

H (A) = \frac{l o g_{2} (n + 1)}{n + 1}

, ami azt jelenti, hogy

n

növekedésével az entrópia aszimptotikusan közelít a nullához.

Ergodikus Markov-folyamatok esetén az entrópia n növekedésével a Shannon-entrópiához konvergál:

l i m_{n \to \infty} H_{C} (A) = H (A)

image: 1_media_PROJECTS_Publik__ci__k_2024_-_V__ges_mi_____pi__ja_Magyar_konstans_sorozat_entropiaja.png

Ábra 2: Konstans mintázat entrópiája

n

függvényében. Shannon eredeti jelforrásokra definiált entrópiaértelmezésével ez összhangban van. Hétköznapi értelmezésben ésszerű az a feltevés, hogy a jelforrás ha nem bocsát ki jelet, az nem meglepő, alapállapotnak tekinthető, ezért az entrópiája nulla. Ha kibocsát egyetlen jelet és elhallgat, az meglepetést okoz. Ha két azonos jelet bocsát ki, kicsit nagyobb a meglepetés, ha azonban a kibocsátott azonos jelek sorozata egyre hosszabb lesz, egyre kevésbé lesz érdekes.

7. Összefoglalás

Ez a tanulmány egységes szemléletet kínál a véges mintázatok információ- és entrópmértékeire, túlmutatva a hagyományos Shannon-megközelítésen. Az ergodikus Markov-folyamatokra épülő Shannon-entrópia és a Kolmogorov-komplexitás jellegű általánosabb eljárások összevetésével szélesebb perspektívát nyújt a különböző szerkezetű minták információtartalmának mérésében. Bemutatja a konstans, véletlen és Markov-folyamatok által generált minták információjának alapfogalmait, valamint olyan általános tulajdonságokat, mint a szubadditivitás és a redundancia. Míg a hagyományos módszerek gyakran pontatlan becsléseket adnak rövid minták esetén, ez a keret, kiegészítve gyakorlati, tömörítési technikákkal, nagyon rövid szekvenciákra is elfogadható eredményt szolgáltat, és hidat képez az elméleti megfontolások és a valós alkalmazások között. Az itt bemutatott egységes megközelítés tisztázza a különböző entrópiafogalmak alkalmazhatóságát különféle adatstruktúrák esetében, miközben világos példákkal, formális bizonyításokkal és újszerű felismerésekkel szolgál a matematikusok, informatikusok, illetve a magas szintű adat- és információelmélet iránt érdeklődők számára – akár a jól ismert, akár a kevésbé feltárt területeken.

Hivatkozások

1Gregory J. Chaitin, "On the Length of Programs for Computing Finite Binary Sequences", J. ACM 13, 4 (1966), pp. 547–569.

2Gregory J. Chaitin, "A Theory of Program Size Formally Identical to Information Theory", Journal of the ACM (JACM) 22, 3 (1974), pp. 329--340.

3Thomas M. Cover and Joy A. Thomas, Elements of Information Theory 2nd (Wiley-Interscience, 2006).

4A. N. Kolmogorov, "On tables of random numbers", Mathematical Reviews (1963).

5Ming Li and Paul Vitányi, An Introduction to Kolmogorov Complexity and Its Applications 2nd (Springer, 1997).

6Claude E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal (1948).

7Claude E. Shannon and Warren Weaver, The Mathematical Theory of Communication (University of Illinois Press, 1949).

Az 1. ábrán látható összehasonlításhoz használt 1000 karakter hosszúságú mintázatok.

Fibonacci-sorozat

0 1 2 3 5 8 1 3 2 1 3 4 5 5 8 9 1 4 4 2 3 3 3 7 7 6 1 0 9 8 7 1 5 9 7 2 5 8 4 4 1 8 1 6 7 6 5 1 0 9 4 6 1 7 7 1 1 2 8 6 5 7 4 6 3 6 8 7 5 0 2 5 1 2 1 3 9 3 1 9 6 4 1 8 3 1 7 8 1 1 5 1 4 2 2 9 8 3 2 0 4 0 1 3 4 6 2 6 9 2 1 7 8 3 0 9 3 5 2 4 5 7 8 5 7 0 2 8 8 7 9 2 2 7 4 6 5 1 4 9 3 0 3 5 2 2 4 1 5 7 8 1 7 3 9 0 8 8 1 6 9 6 3 2 4 5 9 8 6 1 0 2 3 3 4 1 5 5 1 6 5 5 8 0 1 4 1 2 6 7 9 1 4 2 9 6 4 3 3 4 9 4 4 3 7 7 0 1 4 0 8 7 3 3 1 1 3 4 9 0 3 1 7 0 1 8 3 6 3 1 1 9 0 3 2 9 7 1 2 1 5 0 7 3 4 8 0 7 5 2 6 9 7 6 7 7 7 8 7 4 2 0 4 9 1 2 5 8 6 2 6 9 0 2 5 2 0 3 6 5 0 1 1 0 7 4 3 2 9 5 1 2 8 0 0 9 9 5 3 3 1 6 2 9 1 1 7 3 8 6 2 6 7 5 7 1 2 7 2 1 3 9 5 8 3 8 6 2 4 4 5 2 2 5 8 5 1 4 3 3 7 1 7 3 6 5 4 3 5 2 9 6 1 6 2 5 9 1 2 8 6 7 2 9 8 7 9 9 5 6 7 2 2 0 2 6 0 4 1 1 5 4 8 0 0 8 7 5 5 9 2 0 2 5 0 4 7 3 0 7 8 1 9 6 1 4 0 5 2 7 3 9 5 3 7 8 8 1 6 5 5 7 4 7 0 3 1 9 8 4 2 1 0 6 1 0 2 0 9 8 5 7 7 2 3 1 7 1 6 7 6 8 0 1 7 7 5 6 5 2 7 7 7 7 8 9 0 0 3 5 2 8 8 4 4 9 4 5 5 7 0 2 1 2 8 5 3 7 2 7 2 3 4 6 0 2 4 8 1 4 1 1 1 7 6 6 9 0 3 0 4 6 0 9 9 4 1 9 0 3 9 2 4 9 0 7 0 9 1 3 5 3 0 8 0 6 1 5 2 1 1 7 0 1 2 9 4 9 8 4 5 4 0 1 1 8 7 9 2 6 4 8 0 6 5 1 5 5 3 3 0 4 9 3 9 3 1 3 0 4 9 6 9 5 4 4 9 2 8 6 5 7 2 1 1 1 4 8 5 0 7 7 9 7 8 0 5 0 3 4 1 6 4 5 4 6 2 2 9 0 6 7 0 7 5 5 2 7 9 3 9 7 0 0 8 8 4 7 5 7 8 9 4 4 3 9 4 3 2 3 7 9 1 4 6 4 1 4 4 7 2 3 3 4 0 2 4 6 7 6 2 2 1 2 3 4 1 6 7 2 8 3 4 8 4 6 7 6 8 5 3 7 8 8 9 0 6 2 3 7 3 1 4 3 9 0 6 6 1 3 0 5 7 9 0 7 2 1 6 1 1 5 9 1 9 9 1 9 4 8 5 3 0 9 4 7 5 5 4 9 7 1 6 0 5 0 0 6 4 3 8 1 6 3 6 7 0 8 8 2 5 9 6 9 5 4 9 6 9 1 1 1 2 2 5 8 5 4 2 0 1 9 6 1 4 0 7 2 7 4 8 9 6 7 3 6 7 9 8 9 1 6 3 7 6 3 8 6 1 2 2 5 8 1 1 0 0 0 8 7 7 7 8 3 6 6 1 0 1 9 3 1 1 7 7 9 9 7 9 4 1 6 0 0 4 7 1 4 1 8 9 2 8 8 0 0 6 7 1 9 4 3 7 0 8 1 6 1 2 0 4 6 6 0 0 4 6 6 1 0 3 7 5 5 3 0 3 0 9 7 5 4 0 1 1 3 8 0 4 7 4 6 3 4 6 4 2 9 1 2 2 0 0 1 6 0 4 1 5 1 2 1 8 7 6 7 3 8 1 9 7 4 0 2 7 4 2 1 9 8 6 8 2 2 3 1 6 7 3 1 9 4 0 4 3 4 6 3 4 9 9 0 0 9 9 9 0 5 5 1 6 8 0 7 0 8 8 5 4 8 5 8 3 2 3 0 7 2 8 3 6 2 1 1 4 3 4 8 9 8

John Muir (/mjʊər/ MURE; April 21, 1838 – December 24, 1914),[1] also known as "John of the Mountains" and "Father of the National Parks",[2] was a Scottish-born American[3][4]: 42 naturalist, author, environmental philosopher, botanist, zoologist, glaciologist, and early advocate for the preservation of wilderness in the United States. His books, letters and essays describing his adventures in nature, especially in the Sierra Nevada, have been read by millions. His activism helped to preserve the Yosemite Valley and Sequoia National Park, and his example has served as an inspiration for the preservation of many other wilderness areas. The Sierra Club, which he co-founded, is a prominent American conservation organization. In his later life, Muir devoted most of his time to his wife and the preservation of the Western forests. As part of the campaign to make Yosemite a national park, Muir published two landmark articles on wilderness preservation in The Century Magazine, "The Treasure

Véletlen sorozat

1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1

Struktúrált sorozat

Minimális és maximális információmennyiség algoritmusai.

public class MaxInfo{

	public double maxInfo(Collection values){ 
		if (values == null) { 
			return 0; 
		}
		if (values.isEmpty()) 
		{ 
			return 0; 
		} 
		if (values.size() == 1) {
			return 1; 
		} 
		Set atomicSet = new HashSet<>(values); 
		int k = atomicSet.size();
		int n = values.size();
		double v = n * Math.log(k) / Math.log(2);
		if (v > 500) {
			return v;
		} 
		if (k == 1) {
			return Math.log(n + 1) / Math.log(2); 
		}
		return Math.log(
			(Math.pow(k, n + 1) - 1) / (k - 1)) / Math.log(2);
	}

}

Mintázat módosított Shannon-információjának algoritmusa.

public class ModifiedShannonInfo{

	public double modifiedShannonInfo(Collection values) {
		if (values == null || values.isEmpty()) {
	    	return 0;
		}
		if (values.size() == 1) {
			return 1;
		}
		Map<Object, Double> map = new HashMap<>();      
		for (Object x : values) {
			Double frequency = map.get(x);
			if (frequency == null) {
				map.put(x, 1.0);
			} else {
				map.put(x, frequency + 1);
			}
		}
		int n = values.size();
		if (n > 100) {
			return shannonInfo.value(values);
		}
		if (map.size() == 1) {
			return Math.log(n + 1) / Math.log(2);
		}
		for (Object x : map.keySet()) {
			map.put(x, map.get(x) / n);
		}
		double info = 0;
		for (int i = 0; i < n; i++) {
			double p = 1;
			for (Object x : map.keySet()) {
				double f = map.get(x);
				p *= Math.pow(f, -i * f);
			}
			info += p;
		}
		return Math.log(info) / Math.log(2);
	}

}

Mintázat mintázat GZip tömörítési algoritmussal mért információjának algoritmusa.

public class GZipInfo{

	private final MinInfo minInfo = new MinInfo();
	private final MaxInfo maxInfo = new MaxInfo();

	public double gZipInfo(Collection values) {
		if (input == null || input.size() <= 1) {
		return 0;
		}
	
		byte[] values = ObjectUtils.serialize(input);
	
		double gzipInfo = ArrayUtils.toGZIP(values).length * 8;
	
		double min = minInfo.minInfo(input);
		double max = maxInfo.maxInfo(input);
	
		double minGzipInfo = ArrayUtils.toGZIP(
			new byte[values.length]).length * 8;
		double maxGzipInfo = ArrayUtils.toGZIP(
			generateRandomByteArray(values)).length * 8;
	
		if (originalMax == originalMin) {
			return (newMin + newMax) / 2;
		}
	
		return newMin + ((gzipInfo - minGzipInfo) 
			/ (maxGzipInfo - minGzipInfo)) * (max - min);
	}

}

$n$	Mintázat	Entrópia
$0$	$()$	$l o g_{2} (1)$
$1$	$() (a)$	$l o g_{2} (2) / 2$
$2$	$() (a) (a)$	$l o g_{2} (3) / 3$