Teorija uređenog patcha

Izvorni zadatak T-1: Filter stabilnosti — puna specifikacija teorije stope i distorzije Problem: Shannonova teorija stope i distorzije zahtijeva: izvor X, alfabet reprodukcije i funkciju distorzije d(x, \hat{x}). Preprint se poziva na R_{pred}(D) bez specificiranja ova tri elementa za OPT-ov supstrat. Isporuka: Potpuna specifikacija (\mathcal{X}, \hat{\mathcal{X}}, P_X, d) za OPT-ov problem stope i distorzije.

Ova revizija razlikuje višak entropije od statističke kompleksnosti, dokazuje identitet prediktivnog-KL pri konačnom horizontu, dokazuje opću donju granicu R_{T,h}(D)\ge E_{T,h}-D, i navodi tačan kriterij jednakosti za slučaj kada se ta donja granica dostiže. C_{\max} ostaje empirijski parametar, a ne veličina izvedena iz formalizma stope i distorzije.
Status zatvaranja: DJELIMIČNO RIJEŠENO. Specifikacija četvorke, identitet prediktivnog-KL i opća donja granica R_{T,h}(D) \geq E_{T,h}(\nu) - D su uspostavljeni, uz tačan kriterij jednakosti. Ranija generička tvrdnja o zatvorenom obliku R(D) = C_\mu - D je povučena; ispravan rezultat je donja granica. C_{\max} ostaje empirijski parametar, a ne veličina izvedena iz formalizma stope i distorzije.

§0. Nivo formulacije

Radna formulacija. Fiksirajmo T,h<\infty. Neka X:=X_{1:T} označava prošli blok, a Y:=X_{T+1:T+h} budući blok unaprijednog pogleda pod fiksiranom izračunljivom stacionarnom ergodičkom mjerom \nu\in\mathcal M. Definirajmo prediktivnu informaciju na konačnom horizontu E_{T,h}(\nu):=I(X;Y). Kada postoji granica za beskonačni horizont, definirajmo višak entropije E_\nu := I(\overleftarrow X;\overrightarrow X). Ako S označava puno kauzalno stanje \epsilon-mašine, definirajmo statističku složenost C_{\mu,\nu}:=H(S). To su različite veličine. Problem stope-distorzije na konačnom horizontu u ovom dodatku formuliran je u terminima E_{T,h}, a ne C_{\mu,\nu}. Solomonoffova univerzalna semimjera \xi ulazi samo kao meta-priorno ponderiranje (preprint, jednačina 1): pojedinačne krive R(D) računaju se za svaku mjeru \nu. Rezultati koji zahtijevaju punu mješavinu \xi navedeni su odvojeno.

§1. Potpuna specifikacija četvorke

1.1 Izvor X i distribucija P_X

Fiksirajmo izračunljivu stacionarnu ergodičku mjeru \nu \in \mathcal{M} na \{0,1\}^\infty. Izvor je proces (X_t)_{t \ge 1} distribuiran prema \nu. Za ulogu meta-priora, \xi iz jednačine (1) preprinta ponderira svaki takav \nu s w_\nu \approx 2^{-K(\nu)}. Pišemo P_X = \nu za fiksni član od \mathcal{M}. Svi rezultati ispod primjenjuju se po mjeri \nu; Solomonoffova veza ulazi kroz granicu dominacije u §4.

1.2 Reprodukcijski alfabet \hat{X}

Za fiksne T,h, definirajmo relaciju prediktivne ekvivalencije konačnog horizonta na prošlim blokovima: x \sim_h x' \iff \nu(Y\in A\mid X=x)=\nu(Y\in A\mid X=x') \quad\text{za sve mjerljive }A\subseteq\{0,1\}^h. Neka je S_h klasa ekvivalencije od X pod \sim_h. Tada je S_h minimalna dovoljna statistika za predviđanje Y iz X na horizontu h.

Puno kauzalno stanje \epsilon-mašine S jeste objekt beskonačnog horizonta koji se dobija kada se pređe na polubeskonačne prošlosti i punu budućnost. Ovaj dodatak koristi S_h za izvođenja na konačnom horizontu, a S zadržava za puni granični slučaj kauzalnog stanja.

Status izračunljivosti. Za opću izračunljivu \nu, ovaj dodatak ne tvrdi tačnu izračunljivost particije prediktivnih stanja. Ona se tretira kao idealizirani mjerljivi objekt. Tačna izračunljivost tvrdi se samo za eksplicitno identificirane potklase, kao što su procesi s konačnom memorijom.

1.3 Funkcija distorzije d_h(x, z)

Funkcija distorzije je KL prediktivna divergencija: d_h(x,z):=D_{\mathrm{KL}}\!\big(P_\nu(Y\mid X=x)\,\|\,P_\nu(Y\mid Z=z)\big). Ovdje je Z varijabla reprezentacije koju proizvodi enkoder p(z\mid x). Kada je Z=S_h, to je egzaktna distorzija prediktivnog stanja; kada je Z grubljenje ili stohastički kod, P_\nu(Y\mid Z=z) je inducirani prediktivni zakon.

Potpuna četvorka

§2. Izvođenje R_{T,h}(D) pod četvorkom

Funkcija stope-distorzije za četvorku iz §1 glasi:

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

2.1 KL identitet distorzije

Neka je X:=X_{1:T}, Y:=X_{T+1:T+h}, i neka je Z bilo koja reprezentacija proizvedena enkoderom p(z\mid x). Budući da je Z-X-Y Markovljev lanac, \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). Ekvivalentno, \mathbb E[d_h(X,Z)] = I(X;Y)-I(Z;Y)=E_{T,h}(\nu)-I(Z;Y). Prema tome, ograničenje distorzije \mathbb E[d_h(X,Z)]\le D ekvivalentno je sa I(Z;Y)\ge E_{T,h}(\nu)-D.

2.2 Reformulacija uskog grla informacije

Ograničenje distorzije sužava prostor dopuštenih enkodera na one koji zadovoljavaju \mathbb{E}[d_h(X,Z)] \le D. To tačno odgovara postavljanju donje granice na I(Z;Y), čime se dobija ograničeni problem uskog grla informacije. Budući da je dostižna regija \{(I(Z;Y), I(X;Z))\} konveksna prema standardnim argumentima vremenskog dijeljenja, vrijedi jaka dualnost. To omogućava egzaktnu reformulaciju pomoću Lagrangijana uskog grla informacije (Tishby, Pereira & Bialek 1999 [28]): \mathcal{L}[p(z|x)] = I(X ; Z) - \beta \cdot I(Z ; Y) pri čemu je Lagrangeov multiplikator \beta određen sa D. IB Lagrangijan prati Paretoovu granicu između stope kompresije i prediktivne vjernosti.

2.3 Glavni teorem: opća donja granica i kriterij jednakosti

Uspostavljamo granicu za funkciju stopa–distorzija:

Propozicija (opća donja granica i kriterij jednakosti).
Za svaki enkoder p(z\mid x), neka je D:=\mathbb E[d_h(X,Z)]. Tada I(X;Z)=E_{T,h}(\nu)-D+I(X;Z\mid Y). Posljedično, R_{T,h}(D)\ge E_{T,h}(\nu)-D. Za kompaktne konačne reprodukcijske alfabete, gdje kontinuitet garantira da je infimum po enkoderima dostignut, jednakost pri datoj distorziji D vrijedi ako i samo ako postoji enkoder koji postiže tu distorziju uz I(X;Z\mid Y)=0. Za determinističke enkodere Z=g(X), ovo je ekvivalentno sa H(Z\mid Y)=0.

Pri nultoj distorziji, minimalna dovoljna statistika S_h postiže R_{T,h}(0)=I(X;S_h)=H(S_h). Imajte na umu da ova stopa nulte distorzije H(S_h) općenito leži strogo iznad donje granice E_{T,h}. Razlika je nenegativni jaz H(S_h) - E_{T,h} = H(S_h|Y). Taj jaz fizički predstavlja strukturnu „pohranjenu informaciju“ u prošlosti koju sam budući prozor ne uspijeva oporaviti. Jednakost pri nultoj distorziji (H(S_h|Y)=0) predstavlja izrazito degeneriran slučaj koji je generički netačan za složene procese.

U punoj granici kauzalnih stanja, R(0)=C_{\mu,\nu}=H(S). Ovo je jednako E_\nu samo u posebnim slučajevima; općenito vrijedi E_\nu < C_{\mu,\nu}.

2.4 Ponašanje za grublje reprodukcijske alfabete

Za svako determinističko ogrubljivanje 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. Nenegativni član rezerve I(X;Z\mid Y) iščezava samo kada se ogrubljena reprezentacija može rekonstruirati iz budućeg prozora Y. Stoga grublji alfabeti u pravilu proizvode krive stopa-distorzija koje leže strogo iznad prave E_{T,h}-D. Ta prava je univerzalna donja granica, a ne generički ostvariva ovojnica. Svaki praktično izračunljiv kodek koristi aproksimaciju kauzalnih stanja s konačnom memorijom i stoga ima krivu iznad ove granice.

2.5 Granične evaluacije

(Napomena: U granici beskonačnog horizonta, tačka nulte stope nalazi se pri distorziji E_\nu, a ne pri C_{\mu,\nu})

§3. C_{\max} — karakterizacija i barijere

3.1 Lema konvergencije na beskonačnom horizontu

Glavni teorem (§2.3) uspostavlja donju granicu R_{T,h}(D) \ge E_{T,h}(\nu) - D za konačne (T, h). Sada pokazujemo da se to proširuje na postavku beskonačnog horizonta.

Lema (proširenje na beskonačni horizont). Neka je \nu stacionarna ergodička mjera na \{0,1\}^\infty. Tada:

1. E_{T,h}(\nu) = I(X_{1:T}\,;\,X_{T+1:T+h}) je nerastuća ni u T ni u h, odnosno monotono raste u oba parametra (po nejednakosti obrade podataka: uslovljavanje na dužim blokovima ne može smanjiti uzajamnu informaciju između prošlosti i budućnosti pod stacionarnošću).
2. Granica E_\nu := \lim_{T,h \to \infty} E_{T,h}(\nu) postoji (moguće i +\infty) po monotonoj konvergenciji.
3. Za svaki fiksni D \ge 0, niz R_{T,h}(D) je nerastući ni u T ni u h, odnosno monotono raste u T (duže prošlosti ne mogu smanjiti optimalnu stopu kompresije) i monotono raste u h. Skica dokaza monotonosti u h: Funkcija distorzije se dekomponira kao d_{h+1}(x, z) = D_{\mathrm{KL}}\!\left(P_\nu(\cdot \mid x) \,\|\, P_z(\cdot \mid z)\right) preko h+1 budućih koraka, što se pravilom lanca može zapisati kao 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). Budući da je drugi član nenegativan, tačkasto vrijedi d_{h+1} \geq d_h. Prema tome, skup ograničenja \{P(z|x) : E[d_{h+1}] \leq D\} \subseteq \{P(z|x) : E[d_h] \leq D\}, a minimizacija nad manjim dopustivim skupom ne može smanjiti stopu: R_{T,h+1}(D) \geq R_{T,h}(D).
4. Prema tome, R_\nu(D) := \lim_{T,h \to \infty} R_{T,h}(D) postoji.

Budući da R_{T,h}(D) \ge E_{T,h}(\nu) - D vrijedi na svakoj konačnoj etapi, i da obje strane konvergiraju monotono, granica se prenosi na limes:

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

To je donja granica na beskonačnom horizontu na koju se poziva u Propozicijama T-1a i T-1c u nastavku. Napomena: Za procese s E_\nu = +\infty (npr. de Bruijnovi ciklusi visokog reda kada k \to \infty), granica je trivijalno zadovoljena; takvi procesi su isključeni iz skupa kompatibilnog s promatračem O_{C_{\max},D_{\min}} za svaki konačni C_{\max}.

3.2 Particija M pomoću Filtera stabilnosti — Propozicija T-1a

Propozicija T-1a (netrivijalna particija).
Fiksirajmo empirijske C_{\max}>0, \Delta t>0 i D_{\min}\ge0. Definirajmo O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Tada su i O_{C_{\max},D_{\min}} i njegov komplement neprazni.

Dokaz. Konstantni proces pripada skupu O_{C_{\max},D_{\min}} jer ima E_\nu=0 i R_\nu(D)=0.
Za komplement, izaberimo binarni de Bruijnov ciklički proces reda k: stacionarni ergodički binarni proces perioda 2^k s uniformnom fazom, u kojem se svaka riječ dužine k pojavljuje tačno jednom po ciklusu. Za ovaj proces, E_\nu=C_{\mu,\nu}=k. Otuda R_\nu(D_{\min})\ge k-D_{\min}. Izborom k>C_{\max}\Delta t + D_{\min} dobijamo R_\nu(D_{\min})>C_{\max}\Delta t, pa \nu\notin O_{C_{\max},D_{\min}}. \square

3.3 Definicija/karakterizacija C_{\max} — T-1b

Definicija T-1b (empirijski parametar propusnog opsega).
C_{\max} se uzima kao empirijski parametar propusnog opsega svjesnog pristupa, van formalizma stope-distorzije. Za dato C_{\max}, definirajmo klasu kompatibilnu s promatračem O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Ako se želi sažeti zasebno specificirana referentna klasa \mathcal{O}_{ref}, definirajmo C^{ref}_{max}:=\frac{1}{\Delta t}\sup_{\nu\in\mathcal{O}_{ref}}R_\nu(D_{\min}). Ovo je sumarna statistika odabrane klase, a ne definicija same klase.

3.4 Barijera ne-izranjanja — Skica dokaza T-1c

Skica dokaza T-1c (nema konačne univerzalne granice samo iz \xi).
Solomonoffova univerzalna semimjera \xi dodjeljuje pozitivnu apriornu težinu svakoj izračunljivoj mjeri \nu\in\mathcal M. Klasa \mathcal M sadrži stacionarne ergodičke binarne procese s proizvoljno velikom viškom entropije E_\nu (na primjer, gore navedenu de Bruijnovu familiju). Budući da R_\nu(D_{\min})\ge E_\nu-D_{\min}, ne postoji konačna gornja granica na R_\nu(D_{\min}) koja bi važila na cijeloj podršci i koja se može izvesti samo iz \xi. Stoga svaki konačni C_{\max} zahtijeva dodatni empirijski unos ili ulaz koji ograničava klasu, povrh golog Solomonoffovog apriora. \square

§4. Veza sa Solomonoffovim meta-priorom

Četvorka iz §1 i izvođenje R(D) iz §2 formulirani su po mjeri \nu. Solomonoffova veza — način na koji meta-prior \xi ponderira s promatračem kompatibilne tokove — predstavlja strukturnu korespondenciju, a ne izvođenje.

Za bilo koju s promatračem kompatibilnu \nu \in O_{C_{\max},D_{\min}}, ravnoteža stope i distorzije osigurava da je komprimirani tok z_{0:T} reprezentacija koju odabire Filter stabilnosti. Solomonoffov prior \xi toj \nu dodjeljuje težinu w_\nu \approx 2^{-K(\nu)}: jednostavniji (niži K) s promatračem kompatibilni procesi eksponencijalno su vjerovatniji pod \xi. To je formalni izraz argumenta parsimonije (Dodatak T-4): Filter stabilnosti, djelujući nad \xi, odabire najjednostavniji kodek koji se uklapa unutar propusnog opsega.

Granica dominacije iz T-4b primjenjuje se neposredno: za bilo koju izračunljivu fizikalnu mjeru \nu s K(\nu) < \infty:

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

To osigurava da OPT meta-prior \xi nikada ne dodjeljuje manju vjerovatnoću s promatračem kompatibilnim tokovima nego bilo koji fiksni izračunljivi model fizike, do na vlastitu dužinu opisa modela K(\nu).

§5. Iskustveni bit-kvant h^\ast (Pregled E-1)

S obzirom na empirijski izbor C_{\max} i empirijski svjesni prozor ažuriranja \Delta t, definirajmo h^*:=C_{\max}\Delta t. Za C_{\max}\approx 10 bita/s i \Delta t\in[50,80] ms, h^*\approx 0.5\text{–}0.8 bita po svjesnom trenutku.

Svaki stacionarni ergodički proces \nu \in \mathcal{M} koji zadovoljava E_{T,h}(\nu) - D_{\min} > h^\ast legitimno će aktivirati Narativni raspad. To je zato što R_{T,h}(D_{\min}) \ge E_{T,h} - D_{\min} > h^\ast = C_{\max} \Delta t, čime se eksplicitno krši kriterij kompatibilnosti. Međutim, to je dovoljan uslov za kolaps, a ne strogo nužan: budući da je donja granica rijetko oštra (R_{T,h} > E_{T,h} - D_{\min} generički prema §2.4), procesi mogu proći kroz Narativni raspad čak i kada je E_{T,h} - D_{\min} \le h^\ast. To daje kvantitativno predviđanje za E-1; osjetljivost na izbor \Delta t \in [40, 300] ms razmatra se u dodatku za E-1.

§6. Završni sažetak

T-1 isporuke — revidirani status

1. Četvorka je specificirana u okviru prediktivnog okruženja s konačnim horizontom.
2. Prediktivni-KL identitet izveden je ispravno.
3. Generički teorem R(D)=C_\mu-D zamijenjen je ispravnom donjom granicom R_{T,h}(D)\ge E_{T,h}-D zajedno s tačnim kriterijem jednakosti I(X;Z\mid Y)=0.
4. Kodiranje bez distorzije karakterizirano je minimalnom dovoljnom statistikom S_h, a u punoj granici kauzalnog stanja vrijedi R(0)=C_{\mu,\nu}.
5. C_{\max} se tretira kao empirijski, a ne kao interno izveden.
6. h^*=C_{\max}\Delta t je empirijska parametrizacija, a ne teorem iz §2.

Ovaj dodatak održava se kao dio OPT projektnog repozitorija, uporedo s theoretical_roadmap.pdf.