Ordered Patch Theory

Izvorni zadatak T-1: Filtar stabilnosti — puna specifikacija teorije stope i distorzije Problem: Shannonova teorija stope i distorzije zahtijeva: izvor X, reprodukcijsku abecedu i funkciju distorzije d(x, \hat{x}). Preprint se poziva na R_{pred}(D), a da pritom ne specificira ta tri elementa za supstrat OPT-a. Isporuka: Potpuna specifikacija (\mathcal{X}, \hat{\mathcal{X}}, P_X, d) za problem stope i distorzije u OPT-u.

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

§0. Razina 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 fiksnom 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 na beskonačnom horizontu, definirajmo višak entropije E_\nu := I(\overleftarrow X;\overrightarrow X). Ako S označava puno kauzalno stanje \epsilon-stroja, definirajmo statističku složenost C_{\mu,\nu}:=H(S). To su različite veličine. Problem teorije stope i distorzije na konačnom horizontu u ovom dodatku formuliran je u terminima E_{T,h}, a ne C_{\mu,\nu}. Solomonoffova semimjera \xi pojavljuje se samo kao meta-priorno ponderiranje (preprint, jednadžba 1): pojedinačne krivulje R(D) računaju se za svaku mjeru \nu. Rezultati koji zahtijevaju punu mješavinu \xi izloženi su zasebno.

§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 jednadžbe (1) preprinta pridružuje svakoj takvoj \nu težinu w_\nu \approx 2^{-K(\nu)}. Pišemo P_X = \nu za fiksni član od \mathcal{M}. Svi rezultati u nastavku vrijede po mjeri \nu; Solomonoffova veza ulazi preko granice dominacije u §4.

1.2 Reprodukcijska abeceda \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 s obzirom na \sim_h. Tada je S_h minimalna dostatna statistika za predviđanje Y iz X na horizontu h.

Puno kauzalno stanje \epsilon-stroja S jest objekt beskonačnog horizonta dobiven prijelazom na polubeskonačne prošlosti i punu budućnost. Ovaj dodatak koristi S_h za izvode na konačnom horizontu, a S zadržava za puni granični slučaj kauzalnog stanja.

Status izračunljivosti. Za općenitu izračunljivu \nu, ovaj dodatak ne tvrdi egzaktivu izračunljivost particije prediktivnih stanja. Ona se tretira kao idealizirani mjerljivi objekt. Egzaktna izračunljivost tvrdi se samo za eksplicitno identificirane potklase, poput procesa s konačnom memorijom.

1.3 Funkcija distorzije d_h(x, z)

Funkcija distorzije jest 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 reprezentacijska varijabla koju proizvodi enkoder p(z\mid x). Kada je Z=S_h, to je egzaktna distorzija prediktivnog stanja; kada je Z ogrubljenje ili stohastički kod, P_\nu(Y\mid Z=z) je inducirani prediktivni zakon.

Potpuni četverac

§2. Izvod R_{T,h}(D) pod četvorkom

Funkcija stopa-distorzija 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}, a 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). Stoga je ograničenje distorzije \mathbb E[d_h(X,Z)]\le D ekvivalentno uvjetu 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 točno odgovara postavljanju donje granice na I(Z;Y), čime se dobiva problem uskog grla informacije s ograničenjem. Budući da je ostvarivo područje \{(I(Z;Y), I(X;Z))\} konveksno prema standardnim argumentima vremenskog dijeljenja, vrijedi jaka dualnost. To omogućuje 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 s D. IB Lagrangijan ocrtava Paretoovu frontu 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 bilo koji enkoder p(z\mid x), neka 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 jamči da je infimum po enkoderima dosegnut, jednakost pri zadanoj 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), to je ekvivalentno s H(Z\mid Y)=0.

Pri nultoj distorziji, minimalna dostatna statistika S_h postiže R_{T,h}(0)=I(X;S_h)=H(S_h). Primijetimo da ta 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 rekonstruirati. Jednakost pri nultoj distorziji (H(S_h|Y)=0) vrlo je degeneriran slučaj koji je generički netočan za složene procese.

U punom limitu kauzalnih stanja, R(0)=C_{\mu,\nu}=H(S). To 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 slobodnog prostora I(X;Z\mid Y) iščezava samo kada se ogrubljena reprezentacija može rekonstruirati iz budućeg prozora Y. Stoga grublji alfabeti općenito proizvode krivulje stopa-distorzija strogo iznad pravca E_{T,h}-D. Taj je pravac univerzalna donja granica, a ne generički ostvarena ovojnica. Svaki praktično izračunljiv kodek koristi aproksimaciju kauzalnih stanja s konačnom memorijom i stoga ima krivulju iznad te granice.

2.5 Granične evaluacije

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

§3. C_{\max} — Karakterizacija i granice

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 vrijedi:

1. E_{T,h}(\nu) = I(X_{1:T}\,;\,X_{T+1:T+h}) je neopadajuća u odnosu i na T i na h (prema nejednakosti obrade podataka: uvjetovanje na duljim 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 neopadajući u T (dulje prošlosti ne mogu smanjiti optimalnu stopu kompresije) i neopadajući u h. Skica dokaza monotonosti u h: Funkcija distorzije rastavlja se 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, vrijedi d_{h+1} \geq d_h točkasto. Stoga je 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 dopuštenim 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 u svakoj konačnoj fazi, a 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 pozivaju Propozicije T-1a i T-1c u nastavku. Napomena: Za procese s E_\nu = +\infty (npr. de Bruijnove cikluse visokog reda kada k \to \infty), granica je trivijalno zadovoljena; takvi su procesi isključeni iz skupa kompatibilnog s promatračem O_{C_{\max},D_{\min}} za svaki konačni C_{\max}.

3.2 Particija od M pomoću Filtra 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 odaberimo binarni proces de Bruijnova ciklusa reda k: stacionarni ergodički binarni proces perioda 2^k s uniformnom fazom, u kojem se svaka riječ duljine k pojavljuje točno jednom po ciklusu. Za taj proces vrijedi E_\nu=C_{\mu,\nu}=k. Stoga R_\nu(D_{\min})\ge k-D_{\min}. Odabirom k>C_{\max}\Delta t + D_{\min} dobiva se 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 propusnosti).
C_{\max} uzima se kao empirijski parametar propusnosti svjesnog pristupa, izvan formalizma stope i distorzije. Za zadani C_{\max} definira se s promatračem kompatibilna klasa 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}, definira se C^{ref}_{max}:=\frac{1}{\Delta t}\sup_{\nu\in\mathcal{O}_{ref}}R_\nu(D_{\min}). To je sažetna statistika odabrane klase, a ne definicija same klase.

3.4 Barijera ne-emergencije — skica dokaza T-1c

Skica dokaza T-1c (nema konačne univerzalne granice samo iz \xi).
Solomonoffova univerzalna semimjera \xi pridružuje 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 suvišnom entropijom E_\nu (na primjer, gore navedenu obitelj de Bruijnovih nizova). 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 vrijedila na cijelom nosaču i koja bi se mogla izvesti samo iz \xi. Svaki konačni C_{\max} stoga zahtijeva dodatni empirijski unos ili ograničenje klase povrh golog Solomonoffova apriora. \square

§4. Veza sa Solomonoffovim meta-priorom

Četvorka iz §1 i derivacija R(D) iz §2 formulirane su po mjeri \nu. Solomonoffova veza — način na koji meta-prior \xi ponderira tokove kompatibilne s promatračem — strukturna je korespondencija, a ne derivacija.

Za svaki \nu \in O_{C_{\max},D_{\min}} kompatibilan s promatračem, ravnoteža stope i distorzije osigurava da je komprimirani tok z_{0:T} reprezentacija odabrana Filtrom stabilnosti. Solomonoffov prior \xi toj mjeri \nu pridružuje težinu w_\nu \approx 2^{-K(\nu)}: jednostavniji (niži K) procesi kompatibilni s promatračem eksponencijalno su vjerojatniji pod \xi. To je formalni izraz argumenta parsimonije (Dodatak T-4): Filtar stabilnosti, djelujući na \xi, odabire najjednostavniji kodek koji se uklapa unutar propusnosti.

Granica dominacije iz T-4b primjenjuje se izravno: za svaku 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 vjerojatnost tokovima kompatibilnima s promatračem nego bilo koji fiksni izračunljivi model fizike, do na vlastitu duljinu opisa modela K(\nu).

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

Zadan empirijski odabir C_{\max} i empirijski prozor svjesnog ažuriranja \Delta t, definirajmo h^*:=C_{\max}\Delta t. Za C_{\max}\approx 10 bitova/s i \Delta t\in[50,80] ms, h^*\approx 0.5\text{–}0.8 bitova po svjesnom trenutku.

Svaki stacionarni ergodički proces \nu \in \mathcal{M} koji zadovoljava E_{T,h}(\nu) - D_{\min} > h^\ast legitimno će pokrenuti Narativni raspad. Razlog je to š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 dostatan uvjet za kolaps, a ne strogo nužan: budući da je donja ograda rijetko tijesna (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. Sažetak zaključka

T-1 isporuke — revidirani status

1. Četvorka je specificirana u prediktivnom okviru s konačnim horizontom.
2. Prediktivni-KL identitet ispravno je izveden.
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 točnim kriterijem jednakosti I(X;Z\mid Y)=0.
4. Kodiranje s nultom distorzijom karakterizirano je minimalnom dovoljnom statistikom S_h, a u punom limitu kauzalnog stanja vrijedi R(0)=C_{\mu,\nu}.
5. C_{\max} tretira se kao empirijski, a ne kao interno izveden.
6. h^*=C_{\max}\Delta t jest empirijska parametrizacija, a ne teorem iz §2.

Ovaj se dodatak održava kao dio repozitorija projekta OPT uz theoretical_roadmap.pdf.