A rendezett patch elmélete

Eredeti T-1 feladat: Stabilitási szűrő — teljes ráta-torzítás specifikáció Probléma: Shannon ráta-torzítás elmélete megköveteli a következőket: egy X forrást, egy reprodukciós ábécét és egy d(x, \hat{x}) torzításfüggvényt. A preprint hivatkozik az R_{pred}(D) mennyiségre anélkül, hogy megadná ezt a három elemet az OPT szubsztrátumára vonatkozóan. Eredmény: Az OPT ráta-torzítási problémájának teljes (\mathcal{X}, \hat{\mathcal{X}}, P_X, d) specifikációja.

Ez a revízió megkülönbözteti a többletentropiát a statisztikai komplexitástól, bizonyítja a prediktív-KL azonosságot véges horizont esetén, bizonyítja az általános alsó korlátot: R_{T,h}(D)\ge E_{T,h}-D, és megad egy egzakt egyenlőségi kritériumot arra az esetre, amikor ez az alsó korlát elérhető. C_{\max} továbbra is empirikus paraméter marad, nem pedig a ráta-torzítás formalizmusából levezetett mennyiség.
Lezárási állapot: RÉSZBEN MEGOLDVA. A négyes specifikáció, a prediktív-KL azonosság és az általános alsó korlát, R_{T,h}(D) \geq E_{T,h}(\nu) - D, megállapítást nyert, egy egzakt egyenlőségi kritériummal együtt. A korábbi általános zárt alakú állítás, miszerint R(D) = C_\mu - D, visszavonásra került; a helyes eredmény az alsó korlát. C_{\max} továbbra is empirikus paraméter marad, nem pedig a ráta-torzítás formalizmusából levezetett mennyiség.

§0. A megfogalmazás szintje

Munkamegfogalmazás. Rögzítsük, hogy T,h<\infty. Legyen X:=X_{1:T} a múltbeli blokk, és Y:=X_{T+1:T+h} a jövőbe tekintő blokk egy rögzített számítható, stacionárius ergodikus \nu\in\mathcal M mérték mellett. Definiáljuk a véges horizontú prediktív információt: E_{T,h}(\nu):=I(X;Y). Amennyiben a végtelen horizontú határérték létezik, definiáljuk a többletentrópiát: E_\nu := I(\overleftarrow X;\overrightarrow X). Ha S a teljes \epsilon-gép kauzális állapotát jelöli, definiáljuk a statisztikai komplexitást: C_{\mu,\nu}:=H(S). Ezek különböző mennyiségek. A jelen függelékben a véges horizontú ráta-torzítási probléma megfogalmazása E_{T,h} alapján történik, nem pedig C_{\mu,\nu} szerint. A Solomonoff-féle \xi mérték itt kizárólag meta-prior súlyozásként jelenik meg (preprint, 1. egyenlet): az egyes R(D) görbéket minden egyes \nu mértékre külön számítjuk. Azok az eredmények, amelyekhez a teljes \xi keverék szükséges, külön kerülnek megfogalmazásra.

§1. A teljes négyes specifikáció

1.1 X forrás és P_X eloszlás

Rögzítsünk egy kiszámítható stationárius ergodikus mértéket, \nu \in \mathcal{M}, a \{0,1\}^\infty téren. A forrás a \nu szerint eloszló (X_t)_{t \ge 1} folyamat. A meta-prior szerepében a preprint (1) egyenletéből vett \xi minden ilyen \nu-t w_\nu \approx 2^{-K(\nu)} súllyal lát el. Egy rögzített \mathcal{M}-beli elemre P_X = \nu-t írunk. Az alábbi eredmények mértékenként, azaz minden egyes \nu-ra alkalmazhatók; a Solomonoff-kapcsolat a §4 dominancia-korlátján keresztül lép be.

1.2 Reprodukciós ábécé \hat{X}

Rögzített T,h mellett definiáljunk egy véges horizontú prediktív ekvivalenciarelációt a múltbeli blokkokon: x \sim_h x' \iff \nu(Y\in A\mid X=x)=\nu(Y\in A\mid X=x') \quad\text{minden mérhető }A\subseteq\{0,1\}^h\text{ halmazra.} Legyen S_h az X ekvivalenciaosztálya a \sim_h szerint. Ekkor S_h a minimális elégséges statisztika Y előrejelzésére X alapján a h horizonton.

A teljes \epsilon-gép kauzális állapota, S, a végtelen horizontú objektum, amelyet a félig végtelen múltakra és a teljes jövőre való áttéréssel kapunk. Ez a függelék a véges horizontú levezetésekhez S_h-t használja, és S-t a teljes kauzálisállapot-határérték számára tartja fenn.

Kiszámíthatósági státusz. Általános számítható \nu esetén ez a függelék nem állítja a prediktívállapot-partíció pontos kiszámíthatóságát. Idealizált mérhető objektumként kezeli. A pontos kiszámíthatóságot csak kifejezetten azonosított részosztályokra, például véges memóriájú folyamatokra állítja.

1.3 Torzításfüggvény d_h(x, z)

A torzításfüggvény a KL-prediktív divergencia: d_h(x,z):=D_{\mathrm{KL}}\!\big(P_\nu(Y\mid X=x)\,\|\,P_\nu(Y\mid Z=z)\big). Itt Z egy reprezentációs változó, amelyet egy kódoló állít elő: p(z\mid x). Amikor Z=S_h, ez az egzakt prediktívállapot-torzítás; amikor Z durvítás vagy sztochasztikus kód, akkor P_\nu(Y\mid Z=z) az indukált prediktív törvény.

Teljes négyes

§2. Az R_{T,h}(D) levezetése a négyes alatt

Az 1. § négyesére vonatkozó ráta-torzítás függvény:

R_{T,h}(D) = \min_{p(z|x) : \mathbb{E}[d_h(X,Z)] \le D} I(X ; Z)

2.1 A KL-torzítás azonossága

Legyen X:=X_{1:T}, Y:=X_{T+1:T+h}, és legyen Z bármely reprezentáció, amelyet egy p(z\mid x) enkóder állít elő. Mivel Z-X-Y egy Markov-lánc, \mathbb E[d_h(X,Z)] = \mathbb E\!\left[D_{\mathrm{KL}}(P(Y\mid X)\|P(Y\mid Z))\right] = H(Y\mid Z)-H(Y\mid X) = I(X;Y\mid Z). Ezzel ekvivalensen, \mathbb E[d_h(X,Z)] = I(X;Y)-I(Z;Y)=E_{T,h}(\nu)-I(Z;Y). Ezért a torzítási megszorítás \mathbb E[d_h(X,Z)]\le D ekvivalens azzal, hogy I(Z;Y)\ge E_{T,h}(\nu)-D.

2.2 Az információs szűk keresztmetszet újrafogalmazása

A torzítási korlát az elfogadható enkódolók terét azokra korlátozza, amelyekre teljesül, hogy \mathbb{E}[d_h(X,Z)] \le D. Ez pontosan annak felel meg, hogy I(Z;Y) alulról korlátos, ami a megszorított információs szűk keresztmetszet problémáját adja. Mivel az elérhető tartomány, \{(I(Z;Y), I(X;Z))\}, a szokásos időmegosztási érvek mellett konvex, erős dualitás áll fenn. Ez lehetővé teszi a pontos újrafogalmazást az információs szűk keresztmetszet Lagrange-függvényével (Tishby, Pereira & Bialek 1999 [28]): \mathcal{L}[p(z|x)] = I(X ; Z) - \beta \cdot I(Z ; Y) ahol a \beta Lagrange-szorzót D határozza meg. Az IB Lagrange-függvény a tömörítési ráta és a prediktív hűség közötti Pareto-határvonalat rajzolja ki.

2.3 Főtétel: általános alsó korlát és az egyenlőség kritériuma

Megadjuk a ráta-torzítás függvény korlátját:

Állítás (általános alsó korlát és az egyenlőség kritériuma).
Tetszőleges p(z\mid x) kódolóra legyen D:=\mathbb E[d_h(X,Z)]. Ekkor I(X;Z)=E_{T,h}(\nu)-D+I(X;Z\mid Y). Következésképpen R_{T,h}(D)\ge E_{T,h}(\nu)-D. Kompakt véges reprodukciós ábécék esetén, ahol a folytonosság garantálja, hogy a kódolók feletti infimum felvett, egy adott D torzításnál akkor és csak akkor áll fenn egyenlőség, ha létezik olyan kódoló, amely ezt a torzítást eléri, és amelyre I(X;Z\mid Y)=0. Determinisztikus kódolókra Z=g(X) ez ekvivalens azzal, hogy H(Z\mid Y)=0.

Zérus torzításnál a minimális elégséges statisztika S_h teljesíti, hogy R_{T,h}(0)=I(X;S_h)=H(S_h). Vegyük észre, hogy ez a H(S_h) zérus-torzítási ráta általában szigorúan a E_{T,h} alsó korlát fölött helyezkedik el. A különbség a nemnegatív rés H(S_h) - E_{T,h} = H(S_h|Y). Fizikai értelemben ez a rés a múltban tárolt strukturális „tárolt információt” reprezentálja, amelyet a jövőablak önmagában nem képes visszanyerni. Az, hogy zérus torzításnál egyenlőség álljon fenn (H(S_h|Y)=0), erősen degenerált eset, amely összetett folyamatokra generikusan hamis.

A teljes kauzálisállapot-határban R(0)=C_{\mu,\nu}=H(S). Ez csak speciális esetekben egyenlő E_\nu-val; általában E_\nu < C_{\mu,\nu}.

2.4 Viselkedés durvább reprodukciós ábécék esetén

Bármely determinisztikus durvításra, Z=g(S_h), I(X;Z)=I(Z;Y)+I(X;Z\mid Y)=E_{T,h}(\nu)-D+I(X;Z\mid Y)\ge E_{T,h}(\nu)-D. A nemnegatív lazasági tag, I(X;Z\mid Y), csak akkor tűnik el, ha a durvított reprezentáció visszanyerhető a jövőbeli ablakból, Y-ból. Következésképpen a durvább ábécék általában olyan ráta-torzítás görbéket eredményeznek, amelyek szigorúan az E_{T,h}-D egyenes fölött helyezkednek el. Ez az egyenes univerzális alsó korlát, nem pedig egy általánosan elérhető burkológörbe. Minden gyakorlatban számítható kodek a kauzális állapotok véges memóriájú közelítését használja, ezért görbéje e korlát fölött fut.

2.5 Határértékelések

(Megjegyzés: a végtelen horizont határesetében a zérus rátájú pont az E_\nu torzításnál van, nem a C_{\mu,\nu} értéknél)

§3. C_{\max} — Jellemzés és korlátok

3.1 Végtelen horizontú konvergencialemma

A főtétel (§2.3) a véges (T, h) esetére megállapítja az R_{T,h}(D) \ge E_{T,h}(\nu) - D alsó korlátot. Most megmutatjuk, hogy ez kiterjeszthető a végtelen horizontú esetre.

Lemma (Végtelen horizontú kiterjesztés). Legyen \nu egy stationárius ergodikus mérték a \{0,1\}^\infty téren. Ekkor:

1. E_{T,h}(\nu) = I(X_{1:T}\,;\,X_{T+1:T+h}) nemcsökkenő mind T, mind h szerint (az adatfeldolgozási egyenlőtlenség miatt: stationaritás mellett a hosszabb blokkokra való feltételesítés nem csökkentheti a múlt és a jövő közötti kölcsönös információt).
2. Az E_\nu := \lim_{T,h \to \infty} E_{T,h}(\nu) határérték létezik (esetleg +\infty), a monoton konvergencia miatt.
3. Minden rögzített D \ge 0 esetén az R_{T,h}(D) sorozat nemcsökkenő T szerint (a hosszabb múltak nem csökkenthetik az optimális tömörítési rátát), és nemcsökkenő h szerint is. A h szerinti monotonitás bizonyításvázlata: A torzításfüggvény felbontható mint d_{h+1}(x, z) = D_{\mathrm{KL}}\!\left(P_\nu(\cdot \mid x) \,\|\, P_z(\cdot \mid z)\right) a jövő h+1 lépésére, amely a láncszabály segítségével írható fel így: d_h(x,z) + D_{\mathrm{KL}}\!\left(P_\nu(X_{T+h+1} \mid x, X_{T+1:T+h}) \,\|\, P_z(X_{T+h+1} \mid z, X_{T+1:T+h})\right). Mivel a második tag nemnegatív, pontonként d_{h+1} \geq d_h. Ezért a megszorításhalmaz \{P(z|x) : E[d_{h+1}] \leq D\} \subseteq \{P(z|x) : E[d_h] \leq D\}, és egy kisebb megengedett halmazon végzett minimalizálás nem csökkentheti a rátát: R_{T,h+1}(D) \geq R_{T,h}(D).
4. Következésképpen az R_\nu(D) := \lim_{T,h \to \infty} R_{T,h}(D) határérték létezik.

Mivel az R_{T,h}(D) \ge E_{T,h}(\nu) - D minden véges fokozatban fennáll, és mindkét oldal monoton módon konvergál, a korlát átvihető a határértékre:

R_\nu(D) \ge E_\nu - D

Ez az a végtelen horizontú alsó korlát, amelyre az alábbi T-1a és T-1c állítások hivatkoznak. Megjegyzés: Azokra a folyamatokra, amelyeknél E_\nu = +\infty (pl. magas rendű de Bruijn-ciklusok esetén, amikor k \to \infty), a korlát triviálisan teljesül; az ilyen folyamatok bármely véges C_{\max} esetén ki vannak zárva a megfigyelő-kompatibilis O_{C_{\max},D_{\min}} halmazból.

3.2 M felosztása a Stabilitási szűrő által — T-1a propozíció

T-1a propozíció (nem triviális felosztás).
Rögzítsük az empirikus C_{\max}>0, \Delta t>0 és D_{\min}\ge0 értékeket. Definiáljuk: O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Ekkor mind O_{C_{\max},D_{\min}}, mind a komplementere nem üres.

Bizonyítás. A konstans folyamat eleme O_{C_{\max},D_{\min}}-nek, mert erre E_\nu=0 és R_\nu(D)=0.
A komplementerhez válasszunk egy k-adik rendű bináris de Bruijn-ciklus folyamatot: egy 2^k periódusú, egyenletes fázisú, stacionárius ergodikus bináris folyamatot, amelyben minden k hosszúságú szó pontosan egyszer jelenik meg ciklusonként. Erre a folyamatra E_\nu=C_{\mu,\nu}=k. Ezért R_\nu(D_{\min})\ge k-D_{\min}. Ha k>C_{\max}\Delta t + D_{\min}, akkor R_\nu(D_{\min})>C_{\max}\Delta t, tehát \nu\notin O_{C_{\max},D_{\min}}. \square

3.3 A C_{\max} definíciója/jellemzése — T-1b

T-1b definíció (empirikus sávszélességi paraméter).
A C_{\max} egy, a ráta–torzítás formalizmusán kívül eső empirikus tudatos-hozzáférési sávszélességi paraméterként értendő. Adott C_{\max} mellett definiáljuk a megfigyelő-kompatibilis osztályt: O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Ha egy külön meghatározott referenciaosztályt, \mathcal{O}_{ref}-et kívánunk összefoglalni, definiáljuk: C^{ref}_{max}:=\frac{1}{\Delta t}\sup_{\nu\in\mathcal{O}_{ref}}R_\nu(D_{\min}). Ez egy választott osztály összefoglaló statisztikája, nem pedig magának az osztálynak a definíciója.

3.4 A nem-emergencia korlátja — T-1c bizonyításvázlat

T-1c bizonyításvázlat (nincs véges univerzális korlát pusztán \xi-ből).
A Solomonoff univerzális félmértéke, \xi, minden számítható mértékhez \nu\in\mathcal M pozitív prior súlyt rendel. Az \mathcal M osztály tartalmaz stationárius ergodikus bináris folyamatokat tetszőlegesen nagy többletentropiával, E_\nu-val (például a fenti de Bruijn-családot). Mivel R_\nu(D_{\min})\ge E_\nu-D_{\min}, ezért nincs olyan véges, a teljes tartóra kiterjedő felső korlát R_\nu(D_{\min})-re, amely pusztán \xi-ből levezethető volna. Következésképpen bármely véges C_{\max} további empirikus vagy osztályszűkítő bemenetet igényel a puszta Solomonoff-prioron túl. \square

§4. Kapcsolat a Solomonoff-meta-priorral

Az 1. § négyese és a 2. § R(D)-levezetése mértékenként, azaz \nu-nként vannak megadva. A Solomonoff-kapcsolat — vagyis az, hogy a meta-prior \xi miként súlyozza a megfigyelő-kompatibilis streameket — strukturális megfelelés, nem pedig levezetés.

Bármely megfigyelő-kompatibilis \nu \in O_{C_{\max},D_{\min}} esetén a ráta-torzítási egyensúly biztosítja, hogy a tömörített stream z_{0:T} a Stabilitási szűrő által kiválasztott reprezentáció legyen. A Solomonoff-prior \xi ehhez a \nu-hoz w_\nu \approx 2^{-K(\nu)} súlyt rendel: az egyszerűbb (alacsonyabb K-jú) megfigyelő-kompatibilis folyamatok exponenciálisan valószínűbbek \xi alatt. Ez a takarékossági érv (T-4 függelék) formális kifejezése: a Stabilitási szűrő, \xi-n működve, a sávszélességen belül elférő legegyszerűbb kodeket választja ki.

A T-4b dominancia-korlátja közvetlenül alkalmazható: bármely számítható fizikai mértékre \nu, amelyre K(\nu) < \infty:

-\log \xi(y_{1:T}) \le -\log \nu(y_{1:T}) + K(\nu)

Ez biztosítja, hogy az OPT meta-priorja, \xi, soha ne rendeljen kisebb valószínűséget a megfigyelő-kompatibilis streamekhez, mint bármely rögzített számítható fizikai modell, legfeljebb a modell saját leíráshosszának, K(\nu)-nak erejéig.

§5. Az élménybeli bitkvantum h^\ast (az E-1 előzetese)

Adott C_{\max} egy empirikus választása és egy empirikus tudatos frissítési időablak, \Delta t, definiáljuk: h^*:=C_{\max}\Delta t. C_{\max}\approx 10 bit/s és \Delta t\in[50,80] ms esetén h^*\approx 0.5\text{–}0.8 bit tudatos pillanatonként.

Bármely stationárius ergodikus folyamat, \nu \in \mathcal{M}, amelyre teljesül, hogy E_{T,h}(\nu) - D_{\min} > h^\ast, jogszerűen Narratív szétesést vált ki. Ennek oka, hogy R_{T,h}(D_{\min}) \ge E_{T,h} - D_{\min} > h^\ast = C_{\max} \Delta t, ami explicit módon sérti a kompatibilitási kritériumot. Ez azonban az összeomlásnak elégséges feltétele, nem pedig szigorúan szükséges: mivel az alsó korlát ritkán éles (R_{T,h} > E_{T,h} - D_{\min} általában, lásd: §2.4), a folyamatok akkor is áteshetnek Narratív szétesésen, amikor E_{T,h} - D_{\min} \le h^\ast. Ez adja az E-1 kvantitatív előrejelzését; a \Delta t \in [40, 300] ms választására való érzékenységet az E-1 függeléke tárgyalja.

§6. Záró összefoglaló

T-1 teljesítendők — módosított státusz

1. A négyes egy véges horizontú prediktív beállításban van specifikálva.
2. A prediktív-KL azonosság helyesen van levezetve.
3. Az általános R(D)=C_\mu-D tételt a helyes alsó korlát váltja fel R_{T,h}(D)\ge E_{T,h}-D az I(X;Z\mid Y)=0 pontos egyenlőségi kritériummal együtt.
4. A zéró torzítású kódolást a minimális elégséges statisztika, S_h, jellemzi, és a teljes kauzálisállapot-határban R(0)=C_{\mu,\nu}.
5. A C_{\max} empirikusként van kezelve, nem belsőleg levezetettként.
6. A h^*=C_{\max}\Delta t empirikus parametrizáció, nem pedig a §2-ből következő tétel.

Ez a függelék az OPT projekt repozitóriumának részeként van karbantartva a theoretical_roadmap.pdf mellett.