Sakārtotā patch teorija

Sākotnējais uzdevums T-1: Stabilitātes filtrs — pilna ātruma–kropļojuma specifikācija Problēma: Šenona ātruma–kropļojuma teorija prasa: avotu X, reprodukcijas alfabētu un kropļojuma funkciju d(x, \hat{x}). Preprintā tiek izmantots R_{pred}(D), nenorādot šos trīs elementus OPT substrātam. Sagaidāmais rezultāts: Pilnīga (\mathcal{X}, \hat{\mathcal{X}}, P_X, d) specifikācija OPT ātruma–kropļojuma problēmai.

Šajā redakcijā tiek nošķirta pārmērīgā entropija no statistiskās sarežģītības, pierādīta prediktīvā-KL identitāte pie galīga horizonta, pierādīta vispārīgā apakšējā robeža R_{T,h}(D)\ge E_{T,h}-D, un formulēts precīzs vienādības kritērijs gadījumam, kad šī apakšējā robeža tiek sasniegta. C_{\max} paliek empīrisks parametrs, nevis lielums, kas atvasināts no ātruma–kropļojuma formālisma.
Slēguma statuss: DAĻĒJI ATRISINĀTS. Ir noteikta četrinieka specifikācija, prediktīvā-KL identitāte un vispārīgā apakšējā robeža R_{T,h}(D) \geq E_{T,h}(\nu) - D ar precīzu vienādības kritēriju. Iepriekšējais vispārīgais slēgtās formas apgalvojums R(D) = C_\mu - D ir atsaukts; korektais rezultāts ir apakšējā robeža. C_{\max} paliek empīrisks parametrs, nevis lielums, kas atvasināts no ātruma–kropļojuma formālisma.

§0. Formulējuma līmenis

Darba formulējums. Fiksēsim T,h<\infty. Lai X:=X_{1:T} apzīmē pagātnes bloku un Y:=X_{T+1:T+h} — nākotnes ieskata bloku pie fiksēta aprēķināma stacionāra ergodiska mēra \nu\in\mathcal M. Definēsim galīga horizonta prediktīvo informāciju E_{T,h}(\nu):=I(X;Y). Ja eksistē bezgalīga horizonta robeža, definēsim lieko entropiju E_\nu := I(\overleftarrow X;\overrightarrow X). Ja S apzīmē pilno \epsilon-mašīnas cēloņstāvokli, definēsim statistisko sarežģītību C_{\mu,\nu}:=H(S). Tie ir atšķirīgi lielumi. Šajā pielikumā galīga horizonta ātruma–kropļojuma problēma ir formulēta, izmantojot E_{T,h}, nevis C_{\mu,\nu}. Solomonofa mērs \xi parādās tikai kā meta-priorais svērums (preprinta 1. vienādojums): individuālās R(D) līknes tiek aprēķinātas katram mēram \nu. Rezultāti, kuriem nepieciešams pilnais maisījums \xi, ir izklāstīti atsevišķi.

§1. Pilnīgā četru elementu specifikācija

1.1 Avots X un sadalījums P_X

Fiksēsim aprēķināmu stacionāru ergodisku mēru \nu \in \mathcal{M} uz \{0,1\}^\infty. Avots ir process (X_t)_{t \ge 1}, kas sadalīts saskaņā ar \nu. Meta-priora lomā \xi no preprinta vienādojuma (1) sver katru šādu \nu ar w_\nu \approx 2^{-K(\nu)}. Rakstām P_X = \nu fiksētam elementam no \mathcal{M}. Visi tālāk minētie rezultāti attiecas uz katru mēru \nu atsevišķi; Solomonofa saikne ienāk caur dominances robežu §4.

1.2 Reprodukcijas alfabēts \hat{X}

Fiksētiem T,h definējam galīga horizonta prediktīvās ekvivalences relāciju pagātnes blokiem: x \sim_h x' \iff \nu(Y\in A\mid X=x)=\nu(Y\in A\mid X=x') \quad\text{visām izmērāmām }A\subseteq\{0,1\}^h. Lai S_h ir X ekvivalences klase attiecībā pret \sim_h. Tad S_h ir minimālā pietiekamā statistika, lai horizontā h prognozētu Y no X.

Pilnais \epsilon-mašīnas cēloņstāvoklis S ir bezgalīga horizonta objekts, ko iegūst, pārejot uz pusbezgalīgām pagātnēm un pilno nākotni. Šajā pielikumā galīga horizonta izvedumiem tiek lietots S_h, bet S ir rezervēts pilnā cēloņstāvokļa robežgadījumam.

Aprēķināmības statuss. Vispārīgam aprēķināmam \nu šis pielikums neapgalvo prediktīvā stāvokļa sadalījuma precīzu aprēķināmību. Tas tiek aplūkots kā idealizēts izmērāms objekts. Precīza aprēķināmība tiek apgalvota tikai skaidri identificētām apakšklasēm, piemēram, procesiem ar galīgu atmiņu.

1.3 Kropļojuma funkcija d_h(x, z)

Kropļojuma funkcija ir KL prediktīvā diverģence: d_h(x,z):=D_{\mathrm{KL}}\!\big(P_\nu(Y\mid X=x)\,\|\,P_\nu(Y\mid Z=z)\big). Šeit Z ir reprezentācijas mainīgais, ko rada kodētājs p(z\mid x). Kad Z=S_h, tas ir precīzs prediktīvā stāvokļa kropļojums; kad Z ir rupjinājums vai stohastisks kods, P_\nu(Y\mid Z=z) ir inducētais prediktīvais likums.

Pilns četrinieks

§2. R_{T,h}(D) izvedums četrotņa ietvarā

Ātruma-kropļojuma funkcija §1 četrotņam ir:

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

2.1 KL kropļojuma identitāte

Lai X:=X_{1:T}, Y:=X_{T+1:T+h}, un lai Z būtu jebkura reprezentācija, ko rada kodētājs p(z\mid x). Tā kā Z-X-Y ir Markova ķēde, \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). Ekvivalenti, \mathbb E[d_h(X,Z)] = I(X;Y)-I(Z;Y)=E_{T,h}(\nu)-I(Z;Y). Tādēļ kropļojuma ierobežojums \mathbb E[d_h(X,Z)]\le D ir ekvivalents ar I(Z;Y)\ge E_{T,h}(\nu)-D.

2.2 Informācijas šaurās vietas pārformulējums

Distorsijas ierobežojums sašaurina pieļaujamo kodētāju telpu līdz tiem, kas apmierina \mathbb{E}[d_h(X,Z)] \le D. Tas precīzi atbilst I(Z;Y) ierobežošanai no apakšas, tādējādi iegūstot ierobežoto Informācijas šaurās vietas problēmu. Tā kā sasniedzamais apgabals \{(I(Z;Y), I(X;Z))\} ir konvekss saskaņā ar standarta laika dalīšanas argumentiem, ir spēkā stiprā dualitāte. Tas ļauj veikt precīzu pārformulējumu, izmantojot Informācijas šaurās vietas Lagranžiānu (Tishby, Pereira & Bialek 1999 [28]): \mathcal{L}[p(z|x)] = I(X ; Z) - \beta \cdot I(Z ; Y) kur Lagranža reizinātāju \beta nosaka D. IB Lagranžiāns izseko kompresijas ātruma un prediktīvās uzticamības Pareto robežu.

2.3 Galvenā teorēma: vispārīgā apakšējā robeža un vienādības kritērijs

Mēs nosakām robežu ātruma–kropļojuma funkcijai:

Propozīcija (vispārīgā apakšējā robeža un vienādības kritērijs).
Jebkuram kodētājam p(z\mid x) definēsim D:=\mathbb E[d_h(X,Z)]. Tad I(X;Z)=E_{T,h}(\nu)-D+I(X;Z\mid Y). Tādējādi R_{T,h}(D)\ge E_{T,h}(\nu)-D. Kompaktiem galīgiem reprodukcijas alfabētiem, kuros nepārtrauktība garantē, ka infimums pār kodētājiem tiek sasniegts, vienādība pie dotā kropļojuma D ir spēkā tad un tikai tad, ja eksistē kodētājs, kas sasniedz šo kropļojumu un kam I(X;Z\mid Y)=0. Deterministiskiem kodētājiem Z=g(X) tas ir ekvivalenti nosacījumam H(Z\mid Y)=0.

Pie nulles kropļojuma minimālā pietiekamā statistika S_h sasniedz R_{T,h}(0)=I(X;S_h)=H(S_h). Ņemiet vērā, ka šis nulles kropļojuma ātrums H(S_h) vispārīgajā gadījumā atrodas stingri virs apakšējās robežas E_{T,h}. Starpība ir nenegatīvā sprauga H(S_h) - E_{T,h} = H(S_h|Y). Fizikāli šī sprauga reprezentē strukturālu “uzglabāto informāciju” pagātnē, ko nākotnes logs viens pats nespēj atgūt. Vienādība pie nulles kropļojuma (H(S_h|Y)=0) ir izteikti deģenerēts gadījums, kas sarežģītiem procesiem tipiski nav spēkā.

Pilnajā cēloņstāvokļu robežgadījumā, R(0)=C_{\mu,\nu}=H(S). Tas sakrīt ar E_\nu tikai īpašos gadījumos; vispārīgajā gadījumā E_\nu < C_{\mu,\nu}.

2.4 Uzvedība rupjākām reprodukcijas alfabētām

Jebkurai deterministiskai rupjināšanai 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. Nenegatīvais rezerves loceklis I(X;Z\mid Y) izzūd tikai tad, ja rupjināto reprezentāciju var atgūt no nākotnes loga Y. Tādēļ rupjākas alfabētas vispārīgā gadījumā rada ātruma-kropļojuma līknes, kas atrodas stingri virs līnijas E_{T,h}-D. Šī līnija ir universāla apakšējā robeža, nevis vispārīgs sasniedzamais aptvērums. Jebkurš praktiski aprēķināms kodeks izmanto galīgas atmiņas aproksimāciju cēloņstāvokļiem, un tādēļ tam atbilstošā līkne atrodas virs šīs robežas.

2.5 Robežnovērtējumi

(Piezīme: bezgalīga horizonta robežā nulles ātruma punkts atrodas pie kropļojuma E_\nu, nevis pie C_{\mu,\nu})

§3. C_{\max} — Raksturojums un barjeras

3.1 Bezgalīga horizonta konverģences lemma

Galvenā teorēma (§2.3) nosaka apakšējo robežu R_{T,h}(D) \ge E_{T,h}(\nu) - D galīgam (T, h). Tagad parādīsim, ka tas paplašinās uz bezgalīga horizonta gadījumu.

Lemma (bezgalīga horizonta paplašinājums). Lai \nu ir stacionārs ergodisks mērs uz \{0,1\}^\infty. Tad:

1. E_{T,h}(\nu) = I(X_{1:T}\,;\,X_{T+1:T+h}) ir nedilstošs gan attiecībā pret T, gan pret h (pēc datu apstrādes nevienādības: nosacīšana uz garākiem blokiem nevar samazināt savstarpējo informāciju starp pagātni un nākotni stacionaritātes apstākļos).
2. Robeža E_\nu := \lim_{T,h \to \infty} E_{T,h}(\nu) eksistē (iespējams, +\infty) pēc monotonās konverģences.
3. Katram fiksētam D \ge 0 virkne R_{T,h}(D) ir nedilstoša attiecībā pret T (garākas pagātnes nevar samazināt optimālo saspiešanas ātrumu) un nedilstoša attiecībā pret h. Monotonitātes attiecībā pret h pierādījuma skice: Distorsijas funkcija sadalās kā d_{h+1}(x, z) = D_{\mathrm{KL}}\!\left(P_\nu(\cdot \mid x) \,\|\, P_z(\cdot \mid z)\right) pār h+1 nākotnes soļiem, ko, izmantojot ķēdes likumu, var pierakstīt kā 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). Tā kā otrais loceklis ir nenegatīvs, punktveidā ir spēkā d_{h+1} \geq d_h. Tādēļ ierobežojumu kopa \{P(z|x) : E[d_{h+1}] \leq D\} \subseteq \{P(z|x) : E[d_h] \leq D\}, un minimizācija pār mazāku pieļaujamo kopu nevar samazināt ātrumu: R_{T,h+1}(D) \geq R_{T,h}(D).
4. Tādēļ R_\nu(D) := \lim_{T,h \to \infty} R_{T,h}(D) eksistē.

Tā kā R_{T,h}(D) \ge E_{T,h}(\nu) - D ir spēkā katrā galīgā stadijā un abas puses konverģē monotoni, robeža pāriet uz limitu:

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

Šī ir bezgalīga horizonta apakšējā robeža, uz kuru atsaucas tālāk dotās Propozīcijas T-1a un T-1c. Piezīme: Procesiem ar E_\nu = +\infty (piemēram, augstas kārtas de Bruijna cikliem, kad k \to \infty) robeža ir triviāli izpildīta; šādi procesi tiek izslēgti no ar novērotāju saderīgās kopas O_{C_{\max},D_{\min}} jebkuram galīgam C_{\max}.

3.2 M sadalījums ar Stabilitātes filtru — Propozīcija T-1a

Propozīcija T-1a (netriviāls sadalījums).
Fiksēsim empīriskos C_{\max}>0, \Delta t>0 un D_{\min}\ge0. Definējam O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Tad gan O_{C_{\max},D_{\min}}, gan tā papildinājums ir netukši.

Pierādījums. Konstantais process pieder pie O_{C_{\max},D_{\min}}, jo tam ir E_\nu=0 un R_\nu(D)=0.
Papildinājumam izvēlamies bināru de Breina cikla procesu ar kārtu k: stacionāru ergodisku bināru procesu ar periodu 2^k un vienmērīgu fāzi, kurā katrs garuma k vārds ciklā parādās tieši vienu reizi. Šim procesam E_\nu=C_{\mu,\nu}=k. Tātad R_\nu(D_{\min})\ge k-D_{\min}. Izvēloties k>C_{\max}\Delta t + D_{\min}, iegūstam R_\nu(D_{\min})>C_{\max}\Delta t, tātad \nu\notin O_{C_{\max},D_{\min}}. \square

3.3 C_{\max} definīcija/raksturojums — T-1b

Definīcija T-1b (empīrisks apziņas piekļuves joslas platuma parametrs).
C_{\max} tiek pieņemts kā empīrisks apziņas piekļuves joslas platuma parametrs, kas ir ārējs attiecībā pret ātruma-kropļojuma formālismu. Dots C_{\max}, definē novērotājam saderīgo klasi O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Ja vēlas apkopot atsevišķi specifikētu references klasi \mathcal{O}_{ref}, definē C^{ref}_{max}:=\frac{1}{\Delta t}\sup_{\nu\in\mathcal{O}_{ref}}R_\nu(D_{\min}). Šī ir izvēlētas klases kopsavilkuma statistika, nevis pašas klases definīcija.

3.4 Ne-emergences barjera — pierādījuma skice T-1c

Pierādījuma skice T-1c (nav galīgas universālas robežas tikai no \xi).
Solomonofa universālais pusmērs \xi piešķir pozitīvu aprioro svaru katram aprēķināmam mēram \nu\in\mathcal M. Klase \mathcal M satur stacionārus ergodiskus binārus procesus ar patvaļīgi lielu lieko entropiju E_\nu (piemēram, iepriekš minēto de Bruijna saimi). Tā kā R_\nu(D_{\min})\ge E_\nu-D_{\min}, no \xi vien nav atvasināma nekāda galīga, visam atbalstam kopīga augšējā robeža uz R_\nu(D_{\min}). Tādēļ jebkuram galīgam C_{\max} ir nepieciešams papildu empīrisks ievads vai klasi ierobežojoši pieņēmumi ārpus kailās Solomonofa apriorās sadales. \square

§4. Saikne ar Solomonofa meta-prioru

§1 četrotne un §2 R(D) izvedums ir formulēti katram mēram \nu atsevišķi. Solomonofa saikne — tas, kā meta-priors \xi piešķir svarus ar novērotāju saderīgām plūsmām — ir strukturāla atbilstība, nevis izvedums.

Jebkuram ar novērotāju saderīgam \nu \in O_{C_{\max},D_{\min}} ātruma-kropļojuma līdzsvars nodrošina, ka saspiestā plūsma z_{0:T} ir Stabilitātes filtra atlasītā reprezentācija. Solomonofa priors \xi piešķir šim \nu svaru w_\nu \approx 2^{-K(\nu)}: vienkāršāki (ar mazāku K) ar novērotāju saderīgi procesi zem \xi ir eksponenciāli ticamāki. Tā ir formāla parsimonijas argumenta izteiksme (Pielikums T-4): Stabilitātes filtrs, darbojoties uz \xi, atlasa vienkāršāko kodeku, kas iekļaujas joslas platumā.

Dominances robeža no T-4b ir piemērojama tieši: jebkuram aprēķināmam fizikas mēram \nu ar K(\nu) < \infty:

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

Tas nodrošina, ka OPT meta-priors \xi nekad nepiešķir ar novērotāju saderīgām plūsmām mazāku varbūtību nekā jebkurš fiksēts aprēķināms fizikas modelis, līdz paša modeļa apraksta garumam K(\nu).

§5. Pieredzes bita kvants h^\ast (E-1 priekšskatījums)

Pie dotas empīriskas C_{\max} izvēles un empīriska apzinātas atjaunināšanās loga \Delta t definējam h^*:=C_{\max}\Delta t. Ja C_{\max}\approx 10 biti/s un \Delta t\in[50,80] ms, h^*\approx 0.5\text{–}0.8 biti uz vienu apzinātu momentu.

Jebkurš stacionārs ergodisks process \nu \in \mathcal{M}, kas apmierina nosacījumu E_{T,h}(\nu) - D_{\min} > h^\ast, likumsakarīgi izraisīs Narativa sabrukumu. Iemesls ir tāds, ka R_{T,h}(D_{\min}) \ge E_{T,h} - D_{\min} > h^\ast = C_{\max} \Delta t, tādējādi tieši pārkāpjot saderības kritēriju. Tomēr tas ir pietiekams sabrukuma nosacījums, nevis stingri nepieciešams: tā kā apakšējā robeža reti ir saspringta (R_{T,h} > E_{T,h} - D_{\min} vispārīgā gadījumā, kā norādīts §2.4), procesi var piedzīvot Narativa sabrukumu arī tad, ja E_{T,h} - D_{\min} \le h^\ast. Tas sniedz kvantitatīvu prognozi E-1; jutība pret \Delta t \in [40, 300] ms izvēli ir aplūkota E-1 pielikumā.

§6. Noslēguma kopsavilkums

T-1 rezultāti — pārskatītais statuss

1. Četrinieks ir specifikēts galīga horizonta prediktīvā iestatījumā.
2. Prediktīvā-KL identitāte ir korekti atvasināta.
3. Vispārīgā teorēma R(D)=C_\mu-D ir aizstāta ar korekto apakšējo robežu R_{T,h}(D)\ge E_{T,h}-D kopā ar precīzu vienādības kritēriju I(X;Z\mid Y)=0.
4. Nulles-distorsijas kodēšana ir raksturota ar minimālo pietiekamo statistiku S_h, un pilnajā cēloņstāvokļu robežgadījumā R(0)=C_{\mu,\nu}.
5. C_{\max} tiek traktēts kā empīrisks, nevis iekšēji atvasināts.
6. h^*=C_{\max}\Delta t ir empīriska parametrizācija, nevis teorēma no §2.

Šis pielikums tiek uzturēts kā daļa no OPT projekta repozitorija līdzās theoretical_roadmap.pdf.