Teorie uspořádaného patche

Původní úkol T-1: Filtr stability — úplná specifikace teorie rychlost–zkreslení Problém: Shannonova teorie rychlost–zkreslení vyžaduje: zdroj X, reprodukční abecedu a funkci zkreslení d(x, \hat{x}). Preprint používá R_{pred}(D), aniž by pro substrát OPT specifikoval tyto tři prvky. Výstup: Úplná specifikace (\mathcal{X}, \hat{\mathcal{X}}, P_X, d) pro problém rychlost–zkreslení v OPT.

Tato revize rozlišuje nadbytečnou entropii od statistické komplexity, dokazuje identitu prediktivního KL pro konečný horizont, dokazuje obecnou dolní mez R_{T,h}(D)\ge E_{T,h}-D a uvádí přesné kritérium rovnosti pro případ, kdy je této dolní meze dosaženo. C_{\max} zůstává empirickým parametrem, nikoli veličinou odvozenou z formalismu rychlost–zkreslení.
Stav uzavření: ČÁSTEČNĚ VYŘEŠENO. Specifikace čtveřice, identita prediktivního KL a obecná dolní mez R_{T,h}(D) \geq E_{T,h}(\nu) - D jsou stanoveny spolu s přesným kritériem rovnosti. Dřívější obecné tvrzení o uzavřeném tvaru R(D) = C_\mu - D bylo staženo; správným výsledkem je dolní mez. C_{\max} zůstává empirickým parametrem, nikoli veličinou odvozenou z formalismu rychlost–zkreslení.

§0. Úroveň formulace

Pracovní formulace. Fixujme T,h<\infty. Nechť X:=X_{1:T} označuje minulý blok a Y:=X_{T+1:T+h} budoucí nahlížecí blok při pevně dané vyčíslitelné stacionární ergodické míře \nu\in\mathcal M. Definujme prediktivní informaci na konečném horizontu E_{T,h}(\nu):=I(X;Y). Existuje-li limita pro nekonečný horizont, definujme excesní entropii E_\nu := I(\overleftarrow X;\overrightarrow X). Označuje-li S úplný kauzální stav \epsilon-stroje, definujme statistickou komplexitu C_{\mu,\nu}:=H(S). Jde o navzájem odlišné veličiny. Úloha rate-distortion na konečném horizontu je v tomto dodatku formulována pomocí E_{T,h}, nikoli C_{\mu,\nu}. Solomonoffova semimíra \xi zde vstupuje pouze jako meta-priorní vážení (preprint, rovnice 1): jednotlivé křivky R(D) se počítají pro každou míru \nu zvlášť. Výsledky, které vyžadují plnou směs \xi, jsou uvedeny samostatně.

§1. Úplná specifikace čtveřice

1.1 Zdroj X a rozdělení P_X

Fixujme vyčíslitelnou stacionární ergodickou míru \nu \in \mathcal{M} na \{0,1\}^\infty. Zdrojem je proces (X_t)_{t \ge 1} rozdělený podle \nu. V roli meta-prioru váží \xi z rovnice (1) v preprintu každé takové \nu vahou w_\nu \approx 2^{-K(\nu)}. Pro pevný prvek \mathcal{M} píšeme P_X = \nu. Všechny níže uvedené výsledky platí po jednotlivých mírách \nu; Solomonoffova souvislost vstupuje prostřednictvím dominační meze v §4.

1.2 Reprodukční abeceda \hat{X}

Pro pevně dané T,h definujme na blocích minulosti relaci prediktivní ekvivalence s konečným horizontem: x \sim_h x' \iff \nu(Y\in A\mid X=x)=\nu(Y\in A\mid X=x') \quad\text{pro všechna měřitelná }A\subseteq\{0,1\}^h. Nechť S_h je třída ekvivalence proměnné X vzhledem k \sim_h. Pak je S_h minimální postačující statistikou pro predikci Y z X při horizontu h.

Úplný kauzální stav \epsilon-stroje S je objekt s nekonečným horizontem, získaný přechodem k polonekonečným minulostem a celé budoucnosti. Tento dodatek používá S_h pro odvození s konečným horizontem a symbol S vyhrazuje pro úplnou limitu kauzálního stavu.

Stav vyčíslitelnosti. Pro obecné vyčíslitelné \nu tento dodatek netvrdí přesnou vyčíslitelnost rozkladu na prediktivní stavy. Je chápán jako idealizovaný měřitelný objekt. Přesná vyčíslitelnost se předpokládá pouze pro explicitně určené podtřídy, jako jsou procesy s konečnou pamětí.

1.3 Funkce zkreslení d_h(x, z)

Funkce zkreslení je KL prediktivní divergence: d_h(x,z):=D_{\mathrm{KL}}\!\big(P_\nu(Y\mid X=x)\,\|\,P_\nu(Y\mid Z=z)\big). Zde je Z reprezentační proměnná produkovaná enkodérem p(z\mid x). Když Z=S_h, jde o přesné zkreslení prediktivního stavu; když je Z zhruběním nebo stochastickým kódem, P_\nu(Y\mid Z=z) je indukovaný prediktivní zákon.

Úplná čtveřice

§2. Odvození R_{T,h}(D) v rámci čtveřice

Funkce míry a zkreslení pro čtveřici z §1 je:

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

2.1 Identita KL zkreslení

Nechť X:=X_{1:T}, Y:=X_{T+1:T+h} a nechť Z je libovolná reprezentace vytvořená enkodérem p(z\mid x). Protože Z-X-Y je Markovův řetězec, \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). Ekvivalentně, \mathbb E[d_h(X,Z)] = I(X;Y)-I(Z;Y)=E_{T,h}(\nu)-I(Z;Y). Proto je omezení zkreslení \mathbb E[d_h(X,Z)]\le D ekvivalentní s I(Z;Y)\ge E_{T,h}(\nu)-D.

2.2 Reformulace informačního bottlenecku

Omezení zkreslení omezuje prostor přípustných enkodérů na ty, které splňují \mathbb{E}[d_h(X,Z)] \le D. To přesně odpovídá omezení I(Z;Y) zdola, čímž vzniká úloha Information Bottleneck s omezením. Protože dosažitelná oblast \{(I(Z;Y), I(X;Z))\} je za standardních argumentů časového sdílení konvexní, platí silná dualita. To umožňuje přesnou reformulaci pomocí Lagrangiánu Information Bottlenecku (Tishby, Pereira & Bialek 1999 [28]): \mathcal{L}[p(z|x)] = I(X ; Z) - \beta \cdot I(Z ; Y) kde je Lagrangeův multiplikátor \beta určen hodnotou D. IB Lagrangián sleduje Paretovu hranici mezi mírou komprese a prediktivní věrností.

2.3 Hlavní věta: obecná dolní mez a kritérium rovnosti

Stanovíme mez pro funkci rychlost-zkreslení:

Propozice (obecná dolní mez a kritérium rovnosti).
Pro libovolný kodér p(z\mid x) nechť D:=\mathbb E[d_h(X,Z)]. Potom I(X;Z)=E_{T,h}(\nu)-D+I(X;Z\mid Y). V důsledku toho R_{T,h}(D)\ge E_{T,h}(\nu)-D. Pro kompaktní konečné reprodukční abecedy, kde spojitost zaručuje, že infimum přes kodéry je dosaženo, platí rovnost při daném zkreslení D právě tehdy, když existuje kodér dosahující tohoto zkreslení s I(X;Z\mid Y)=0. Pro deterministické kodéry Z=g(X) je to ekvivalentní s H(Z\mid Y)=0.

Při nulovém zkreslení minimální postačující statistika S_h dosahuje R_{T,h}(0)=I(X;S_h)=H(S_h). Všimněte si, že tato rychlost při nulovém zkreslení H(S_h) obecně leží striktně nad dolní mezí E_{T,h}. Rozdíl tvoří nezáporná mezera H(S_h) - E_{T,h} = H(S_h|Y). Tato mezera fyzikálně reprezentuje strukturální „uloženou informaci“ v minulosti, kterou samotné budoucí okno nedokáže rekonstruovat. Rovnost při nulovém zkreslení (H(S_h|Y)=0) je vysoce degenerovaný případ, který je pro komplexní procesy genericky nepravdivý.

V úplném limitu kauzálních stavů, R(0)=C_{\mu,\nu}=H(S). To se rovná E_\nu jen ve zvláštních případech; obecně platí E_\nu < C_{\mu,\nu}.

2.4 Chování pro hrubší reprodukční abecedy

Pro libovolné deterministické zhrubení Z=g(S_h) platí, 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. Nezáporný člen vůle I(X;Z\mid Y) mizí pouze tehdy, když je zhrubená reprezentace rekonstruovatelná z budoucího okna Y. Hrubší abecedy proto obecně vytvářejí křivky rychlost–zkreslení ležící striktně nad přímkou E_{T,h}-D. Tato přímka je univerzální dolní mez, nikoli obecně dosažená obálka. Každý prakticky vypočitatelný kodek používá aproximaci kauzálních stavů s konečnou pamětí, a proto má křivku nad touto mezí.

2.5 Hraniční vyhodnocení

(Poznámka: V limitě nekonečného horizontu leží bod nulové míry při zkreslení E_\nu, nikoli při C_{\mu,\nu})

§3. C_{\max} — Charakterizace a bariéry

3.1 Lemma konvergence na nekonečném horizontu

Hlavní věta (§2.3) stanovuje dolní mez R_{T,h}(D) \ge E_{T,h}(\nu) - D pro konečné (T, h). Nyní ukážeme, že se tato mez rozšiřuje i na nastavení s nekonečným horizontem.

Lemma (rozšíření na nekonečný horizont). Nechť \nu je stacionární ergodická míra na \{0,1\}^\infty. Pak platí:

1. E_{T,h}(\nu) = I(X_{1:T}\,;\,X_{T+1:T+h}) je neklesající v obou proměnných T i h (díky nerovnosti zpracování informace: podmínění na delších blocích nemůže za stacionarity snížit vzájemnou informaci mezi minulostí a budoucností).
2. Limita E_\nu := \lim_{T,h \to \infty} E_{T,h}(\nu) existuje (případně je rovna +\infty) na základě monotónní konvergence.
3. Pro každé pevné D \ge 0 je posloupnost R_{T,h}(D) neklesající v T (delší minulosti nemohou snížit optimální kompresní míru) a neklesající v h. Náčrt důkazu monotónnosti v h: Funkce zkreslení se rozkládá jako d_{h+1}(x, z) = D_{\mathrm{KL}}\!\left(P_\nu(\cdot \mid x) \,\|\, P_z(\cdot \mid z)\right) přes h+1 budoucích kroků, což lze pomocí řetězového pravidla zapsat jako 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). Jelikož druhý člen je nezáporný, platí bodově d_{h+1} \geq d_h. Proto množina omezení \{P(z|x) : E[d_{h+1}] \leq D\} \subseteq \{P(z|x) : E[d_h] \leq D\} a minimalizace přes menší přípustnou množinu nemůže snížit míru: R_{T,h+1}(D) \geq R_{T,h}(D).
4. Tedy R_\nu(D) := \lim_{T,h \to \infty} R_{T,h}(D) existuje.

Protože R_{T,h}(D) \ge E_{T,h}(\nu) - D platí v každém konečném kroku a obě strany konvergují monotónně, přechází tato mez do limity:

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

To je dolní mez pro nekonečný horizont, na niž se níže odvolávají Propozice T-1a a T-1c. Poznámka: Pro procesy s E_\nu = +\infty (např. de Bruijnovy cykly vysokého řádu při k \to \infty) je tato mez triviálně splněna; takové procesy jsou vyloučeny z množiny kompatibilní s pozorovatelem O_{C_{\max},D_{\min}} pro jakékoli konečné C_{\max}.

3.2 Rozklad M pomocí Filtru stability — Tvrzení T-1a

Tvrzení T-1a (netriviální rozklad).
Fixujme empirické C_{\max}>0, \Delta t>0 a D_{\min}\ge0. Definujme O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Pak jsou jak O_{C_{\max},D_{\min}}, tak jeho doplněk neprázdné.

Důkaz. Konstantní proces leží v O_{C_{\max},D_{\min}}, protože má E_\nu=0 a R_\nu(D)=0.
Pro doplněk zvolme binární proces de Bruijnova cyklu řádu k: stacionární ergodický binární proces s periodou 2^k a rovnoměrnou fází, v němž se každé slovo délky k objeví právě jednou za cyklus. Pro tento proces platí E_\nu=C_{\mu,\nu}=k. Odtud R_\nu(D_{\min})\ge k-D_{\min}. Volbou k>C_{\max}\Delta t + D_{\min} dostaneme R_\nu(D_{\min})>C_{\max}\Delta t, takže \nu\notin O_{C_{\max},D_{\min}}. \square

3.3 Definice/charakterizace C_{\max} — T-1b

Definice T-1b (empirický parametr šířky pásma vědomého přístupu).
C_{\max} je chápáno jako empirický parametr šířky pásma vědomého přístupu, vnější vůči formalismu míry–zkreslení. Pro dané C_{\max} definujeme třídu kompatibilní s pozorovatelem O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Chceme-li shrnout samostatně specifikovanou referenční třídu \mathcal{O}_{ref}, definujeme C^{ref}_{max}:=\frac{1}{\Delta t}\sup_{\nu\in\mathcal{O}_{ref}}R_\nu(D_{\min}). Jde o souhrnnou statistiku zvolené třídy, nikoli o definici třídy samotné.

3.4 Bariéra ne-emergence — náčrt důkazu T-1c

Náčrt důkazu T-1c (žádná konečná univerzální mez pouze z \xi).
Solomonoffova univerzální semimíra \xi přiřazuje kladnou apriorní váhu každé spočetné míře \nu\in\mathcal M. Třída \mathcal M obsahuje stacionární ergodické binární procesy s libovolně velkou excesní entropií E_\nu (například výše uvedenou rodinu de Bruijnových posloupností). Protože R_\nu(D_{\min})\ge E_\nu-D_{\min}, neexistuje žádná konečná horní mez na R_\nu(D_{\min}) platná v celé podpoře, kterou by bylo možné odvodit pouze z \xi. Jakékoli konečné C_{\max} proto vyžaduje dodatečný empirický vstup nebo omezení třídy nad rámec holé Solomonoffovy apriorní míry. \square

§4. Vztah k Solomonoffovu meta-prioru

Čtveřice ze §1 a odvození R(D) ze §2 jsou formulovány pro každou jednotlivou míru \nu. Solomonoffovská souvislost — totiž jak meta-prior \xi váží streamy kompatibilní s pozorovatelem — je strukturální korespondencí, nikoli odvozením.

Pro libovolné \nu \in O_{C_{\max},D_{\min}} kompatibilní s pozorovatelem zajišťuje rovnováha mezi mírou a zkreslením, že komprimovaný stream z_{0:T} je reprezentací vybranou Filtrem stability. Solomonoffův prior \xi přiřazuje této \nu váhu w_\nu \approx 2^{-K(\nu)}: jednodušší (s nižším K) procesy kompatibilní s pozorovatelem jsou pod \xi exponenciálně pravděpodobnější. To je formální vyjádření argumentu parsimonie (Dodatek T-4): Filtr stability, působící na \xi, vybírá nejjednodušší kodek, který se vejde do šířky pásma.

Přímo se zde uplatní hranice dominance z T-4b: pro libovolnou vyčíslitelnou fyzikální míru \nu s K(\nu) < \infty:

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

To zajišťuje, že OPT meta-prior \xi nikdy nepřiřazuje streamům kompatibilním s pozorovatelem nižší pravděpodobnost než jakýkoli pevně daný vyčíslitelný model fyziky, až na délku popisu samotného modelu K(\nu).

§5. Experienciální bitové kvantum h^\ast (náhled na E-1)

Pro empiricky zvolenou hodnotu C_{\max} a empirické vědomé aktualizační okno \Delta t definujme h^*:=C_{\max}\Delta t. Pro C_{\max}\approx 10 bitů/s a \Delta t\in[50,80] ms platí h^*\approx 0.5\text{–}0.8 bitu na jeden vědomý okamžik.

Každý stacionární ergodický proces \nu \in \mathcal{M} splňující E_{T,h}(\nu) - D_{\min} > h^\ast právoplatně spustí Narativní rozpad. Důvod je ten, že R_{T,h}(D_{\min}) \ge E_{T,h} - D_{\min} > h^\ast = C_{\max} \Delta t, což explicitně porušuje kritérium kompatibility. Jde však o postačující podmínku kolapsu, nikoli o podmínku striktně nutnou: protože dolní mez je zřídka těsná (R_{T,h} > E_{T,h} - D_{\min} genericky podle §2.4), mohou procesy podstoupit Narativní rozpad i tehdy, když E_{T,h} - D_{\min} \le h^\ast. To poskytuje kvantitativní predikci pro E-1; citlivost na volbu \Delta t \in [40, 300] ms je rozebrána v dodatku k E-1.

§6. Shrnutí uzávěru

Výstupy T-1 — revidovaný stav

1. Čtveřice je specifikována v prediktivním nastavení s konečným horizontem.
2. Identita prediktivního KL je odvozena správně.
3. Obecná věta R(D)=C_\mu-D je nahrazena správnou dolní mezí R_{T,h}(D)\ge E_{T,h}-D spolu s přesným kritériem rovnosti I(X;Z\mid Y)=0.
4. Kódování s nulovým zkreslením je charakterizováno minimální postačující statistikou S_h a v limitě úplného kauzálního stavu platí R(0)=C_{\mu,\nu}.
5. C_{\max} je chápáno jako empirické, nikoli jako interně odvozené.
6. h^*=C_{\max}\Delta t je empirická parametrizace, nikoli věta z §2.

Tato příloha je udržována jako součást repozitáře projektu OPT spolu s theoretical_roadmap.pdf.