Teorija uređenog patcha

Originalni zadatak T-1: Filter stabilnosti — puna specifikacija teorije odnosa stopa-distorzija Problem: Šenonova teorija odnosa stopa-distorzija zahteva: izvor X, alfabet reprodukcije i funkciju distorzije d(x, \hat{x}). Preprint se poziva na R_{pred}(D), a da pritom ne specificira ova tri elementa za supstrat OPT-a. Isporuka: Potpuna specifikacija (\mathcal{X}, \hat{\mathcal{X}}, P_X, d) za OPT-ov problem odnosa stopa-distorzija.

Ova revizija razlikuje višak entropije od statističke kompleksnosti, dokazuje identitet prediktivnog-KL pri konačnom horizontu, dokazuje opštu donju granicu R_{T,h}(D)\ge E_{T,h}-D, i navodi tačan kriterijum jednakosti za slučaj kada se ta donja granica dostiže. C_{\max} ostaje empirijski parametar, a ne veličina izvedena iz formalizma odnosa stopa-distorzija.
Status zatvaranja: DELIMIČNO RAZREŠENO. Specifikacija četvorke, identitet prediktivnog-KL i opšta donja granica R_{T,h}(D) \geq E_{T,h}(\nu) - D su uspostavljeni, uz tačan kriterijum jednakosti. Ranija generička tvrdnja o zatvorenoj formi 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 odnosa stopa-distorzija.

§0. Nivo formulacije

Radna formulacija. Fiksirajmo T,h<\infty. Neka X:=X_{1:T} označava blok prošlosti, a Y:=X_{T+1:T+h} blok budućeg predviđanja pri fiksiranoj izračunljivoj stacionarnoj ergodičkoj meri \nu\in\mathcal M. Definišimo prediktivnu informaciju na konačnom horizontu E_{T,h}(\nu):=I(X;Y). Kada postoji granica za beskonačni horizont, definišimo višak entropije E_\nu := I(\overleftarrow X;\overrightarrow X). Ako S označava puno kauzalno stanje \epsilon-mašine, definišimo statističku kompleksnost C_{\mu,\nu}:=H(S). To su različite veličine. Problem stope-distorzije na konačnom horizontu u ovom dodatku formulisan je u terminima E_{T,h}, a ne C_{\mu,\nu}. Solomonovljeva univerzalna semimera \xi ulazi samo kao meta-priorno ponderisanje (preprint, jednačina 1): pojedinačne krive R(D) računaju se za svaku meru \nu. Rezultati koji zahtevaju punu mešavinu \xi izloženi su odvojeno.

§1. Potpuna specifikacija četvorke

1.1 Izvor X i distribucija P_X

Fiksirajmo izračunljivu stacionarnu ergodičku meru \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 dodeljuje težinu svakoj takvoj \nu kao w_\nu \approx 2^{-K(\nu)}. Pišemo P_X = \nu za fiksirani član od \mathcal{M}. Svi rezultati u nastavku važe po meri \nu; Solomonovljeva veza ulazi kroz granicu dominacije u §4.

1.2 Reprodukcioni alfabet \hat{X}

Za fiksirane T,h, definišemo relaciju prediktivne ekvivalencije na blokovima prošlosti sa konačnim horizontom: x \sim_h x' \iff \nu(Y\in A\mid X=x)=\nu(Y\in A\mid X=x') \quad\text{za sve merljive }A\subseteq\{0,1\}^h. Neka je S_h klasa ekvivalencije od X u odnosu na \sim_h. Tada je S_h minimalna dovoljna statistika za predviđanje Y na osnovu X pri horizontu h.

Puno kauzalno stanje \epsilon-mašine, S, jeste objekat beskonačnog horizonta koji se dobija prelaskom 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štu izračunljivu \nu, ovaj dodatak ne tvrdi egzaktну izračunljivost particije prediktivnih stanja. Ona se tretira kao idealizovani merljivi objekat. Egzaktna izračunljivost tvrdi se samo za eksplicitno identifikovane potklase, kao što su procesi sa 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). Ovde je Z reprezentaciona promenljiva 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 indukovani prediktivni zakon.

Potpuna četvorka

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

Funkcija odnosa 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}, i neka je Z bilo koja reprezentacija proizvedena enkoderom p(z\mid x). Pošto 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 informacionog uskog grla

Ograničenje distorzije sužava prostor dozvoljenih 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 problem informacionog uskog grla sa ograničenjem. Pošto je dostižni region \{(I(Z;Y), I(X;Z))\} konveksan pod standardnim argumentima vremenskog deljenja, važi jaka dualnost. To omogućava egzaktnu reformulaciju pomoću Lagranžijana informacionog uskog grla (Tishby, Pereira & Bialek 1999 [28]): \mathcal{L}[p(z|x)] = I(X ; Z) - \beta \cdot I(Z ; Y) gde je Lagranžov multiplikator \beta određen sa D. IB Lagranžijan prati Paretoovu granicu između stope kompresije i prediktivne vernosti.

2.3 Glavna teorema: opšta donja granica i kriterijum jednakosti

Uspostavljamo ograničenje za funkciju stopa-distorzija:

Propozicija (opšta donja granica i kriterijum jednakosti).
Za svaki enkoder p(z\mid x), neka je D:=\mathbb E[d_h(X,Z)]. Tada važi I(X;Z)=E_{T,h}(\nu)-D+I(X;Z\mid Y). Sledstveno, R_{T,h}(D)\ge E_{T,h}(\nu)-D. Za kompaktne konačne reprodukcione alfabete, gde kontinuitet garantuje da se infimum nad enkoderima dostiže, jednakost pri datoj distorziji D važi ako i samo ako postoji enkoder koji postiže tu distorziju sa 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). Treba primetiti da ova stopa nulte distorzije H(S_h) u opštem slučaju 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 „uskladištenu informaciju“ u prošlosti koju sam budući prozor ne uspeva da rekonstruiše. Jednakost pri nultoj distorziji (H(S_h|Y)=0) jeste visoko degenerisan 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; uopšteno važi E_\nu < C_{\mu,\nu}.

2.4 Ponašanje za grublje reprodukcione alfabete

Za svako determinističko ogrubljavanje 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 slobode I(X;Z\mid Y) iščezava samo kada se ogrubljena reprezentacija može rekonstruisati iz budućeg prozora Y. Otuda grublji alfabeti uopšteno 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 omotačnica. Svaki praktično izračunljiv кодек koristi aproksimaciju kauzalnih stanja sa 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

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

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

1. E_{T,h}(\nu) = I(X_{1:T}\,;\,X_{T+1:T+h}) je neopadajuća i u T i u h (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 +\infty) po monotonoj konvergenciji.
3. Za svako fiksno D \ge 0, niz R_{T,h}(D) je neopadajući u T (duže prošlosti ne mogu smanjiti optimalnu stopu kompresije) i neopadajući u h. Skica dokaza za monotonost u h: Funkcija distorzije se razlaže 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). Pošto je drugi član nenegativan, sledi da je d_{h+1} \geq d_h tačkasto. 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 preko manjeg dopustivog skupa ne može smanjiti stopu: R_{T,h+1}(D) \geq R_{T,h}(D).
4. Dakle, R_\nu(D) := \lim_{T,h \to \infty} R_{T,h}(D) postoji.

Pošto R_{T,h}(D) \ge E_{T,h}(\nu) - D važi na svakom konačnom stupnju, a obe strane konvergiraju monotono, granica se prenosi na limes:

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

Ovo je donja granica na beskonačnom horizontu na koju se pozivaju Propozicije T-1a i T-1c u nastavku. Napomena: Za procese sa E_\nu = +\infty (npr. de Bruijnovim ciklusima visokog reda kada k \to \infty), granica je trivijalno zadovoljena; takvi procesi su isključeni iz skupa kompatibilnog sa posmatračem O_{C_{\max},D_{\min}} za svako konačno C_{\max}.

3.2 Particija skupa 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. Definišimo 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 za njega važi E_\nu=0 i R_\nu(D)=0.
Za komplement, izaberimo binarni de Bruijnov ciklički proces reda k: stacionaran ergodički binarni proces perioda 2^k sa uniformnom fazom, u kojem se svaka reč 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 svesnog pristupa, spoljašnji u odnosu na formalizam stope-distorzije. Za dato C_{\max}, definiše se klasa kompatibilna sa posmatrač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}, definiše se C^{ref}_{max}:=\frac{1}{\Delta t}\sup_{\nu\in\mathcal{O}_{ref}}R_\nu(D_{\min}). Ovo je sumarna statistika izabrane 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).
Solomonovljeva univerzalna semimera \xi dodeljuje pozitivnu apriornu težinu svakoj izračunljivoj meri \nu\in\mathcal M. Klasa \mathcal M sadrži stacionarne ergodičke binarne procese sa proizvoljno velikom suvišnom entropijom E_\nu (na primer, gore navedenu de Bruijnovu familiju). Pošto važi R_\nu(D_{\min})\ge E_\nu-D_{\min}, ne postoji konačna gornja granica na celokupnom nosaču za R_\nu(D_{\min}) koja bi se mogla izvesti samo iz \xi. Prema tome, svaki konačni C_{\max} zahteva dodatni empirijski unos ili ulaz koji ograničava klasu, povrh golog Solomonovljevog priora. \square

§4. Veza sa Solomonovljevim meta-priorom

Četvorka iz §1 i izvođenje R(D) iz §2 formulisani su po meri \nu. Solomonovljeva veza — način na koji meta-prior \xi dodeljuje težine sa posmatračem kompatibilnim tokovima — predstavlja strukturnu korespondenciju, a ne izvođenje.

Za svaku sa posmatračem kompatibilnu \nu \in O_{C_{\max},D_{\min}}, ravnoteža stope i distorzije obezbeđuje da je kompresovani tok z_{0:T} reprezentacija koju bira Filter stabilnosti. Solomonovljev prior \xi dodeljuje ovoj \nu težinu w_\nu \approx 2^{-K(\nu)}: jednostavniji (niži K) sa posmatračem kompatibilni procesi eksponencijalno su verovatniji pod \xi. To je formalni izraz argumenta parsimonije (Dodatak T-4): Filter stabilnosti, delujući nad \xi, bira najjednostavniji kodek koji se uklapa u propusni opseg.

Granica dominacije iz T-4b primenjuje se neposredno: za svaku izračunljivu fizikalnu meru \nu sa K(\nu) < \infty:

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

Time se obezbeđuje da OPT meta-prior \xi nikada ne dodeljuje manju verovatnoću sa posmatračem kompatibilnim tokovima nego bilo koji fiksni izračunljivi model fizike, do na sopstvenu dužinu opisa modela K(\nu).

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

Za empirijski izbor C_{\max} i empirijski prozor svesnog ažuriranja \Delta t, definišimo 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 svesnom trenutku.

Svaki stacionarni ergodički proces \nu \in \mathcal{M} koji zadovoljava E_{T,h}(\nu) - D_{\min} > h^\ast zakonito će aktivirati 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 narušava kriterijum kompatibilnosti. Međutim, ovo je dovoljan uslov za kolaps, a ne strogo nužan: pošto je donja granica retko zategnuta (R_{T,h} > E_{T,h} - D_{\min} generički prema §2.4), procesi mogu ući u Narativni raspad čak i kada E_{T,h} - D_{\min} \le h^\ast. Ovo daje kvantitativno predviđanje za E-1; osetljivost na izbor \Delta t \in [40, 300] ms razmatra se u dodatku za E-1.

§6. Sažetak zatvaranja

T-1 isporuke — revidirani status

1. Četvorka je specificirana u prediktivnom okruženju sa konačnim horizontom.
2. Identitet prediktivnog KL-a izveden je korektno.
3. Generička teorema R(D)=C_\mu-D zamenjena je ispravnom donjom granicom R_{T,h}(D)\ge E_{T,h}-D zajedno sa tačnim kriterijumom jednakosti I(X;Z\mid Y)=0.
4. Kodiranje bez distorzije karakterisano je minimalnom dovoljnom statistikom S_h, a u punom limitu kauzalnog stanja važi 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 teorema iz §2.

Ovaj dodatak se održava kao deo OPT projektnog repozitorijuma, uporedo sa theoretical_roadmap.pdf.