Korrastatud patch’i teooria

Algne ülesanne T-1: Stabiilsusfilter — täielik määra-moonutuse spetsifikatsioon Probleem: Shannoni määra-moonutuse teooria nõuab: allikat X, rekonstruktsioonialfabeeti ja moonutusfunktsiooni d(x, \hat{x}). Eeltrükk kasutab suurust R_{pred}(D), täpsustamata OPT substraadi jaoks neid kolme elementi. Väljund: OPT määra-moonutuse probleemi täielik (\mathcal{X}, \hat{\mathcal{X}}, P_X, d) spetsifikatsioon.

Käesolev redaktsioon eristab liigentroopiat statistilisest keerukusest, tõestab prediktiivse-KL identsuse lõpliku horisondi korral, tõestab üldise alampiiri R_{T,h}(D)\ge E_{T,h}-D ning sõnastab täpse võrdsuskriteeriumi juhuks, mil see alampiir saavutatakse. C_{\max} jääb empiiriliseks parameetriks, mitte määra-moonutuse formalismist tuletatud suuruseks.
Lahendusstaatus: OSALISELT LAHENDATUD. Nelikspetsifikatsioon, prediktiivse-KL identsus ja üldine alampiir R_{T,h}(D) \geq E_{T,h}(\nu) - D on kehtestatud koos täpse võrdsuskriteeriumiga. Varasem üldine suletud kuju väide R(D) = C_\mu - D on tagasi võetud; korrektne tulemus on alampiir. C_{\max} jääb empiiriliseks parameetriks, mitte määra-moonutuse formalismist tuletatud suuruseks.

§0. Formulatsiooni tase

Tööformulatsioon. Fikseerime T,h<\infty. Olgu X:=X_{1:T} minevikublokk ja Y:=X_{T+1:T+h} tuleviku ettevaateblokk fikseeritud arvutatava statsionaarse ergoodilise mõõdu \nu\in\mathcal M korral. Defineerime lõpliku horisondiga prediktiivse informatsiooni E_{T,h}(\nu):=I(X;Y). Kui lõpmatu horisondi piirväärtus eksisteerib, defineerime liigentroopia E_\nu := I(\overleftarrow X;\overrightarrow X). Kui S tähistab täielikku \epsilon-masina põhjuslikku seisundit, defineerime statistilise keerukuse C_{\mu,\nu}:=H(S). Need on erinevad suurused. Käesoleva lisa lõpliku horisondiga määr-moonutuse probleem on formuleeritud E_{T,h}, mitte C_{\mu,\nu} kaudu. Solomonoffi mõõt \xi siseneb üksnes meta-eeljaotuse kaaluna (eeltrüki võrrand 1): individuaalsed R(D) kõverad arvutatakse iga mõõdu \nu jaoks eraldi. Tulemused, mis nõuavad täielikku segu \xi, esitatakse eraldi.

§1. Täielik nelikspetsifikatsioon

1.1 Allikas X ja jaotus P_X

Fikseerime arvutatava statsionaarse ergoodilise mõõdu \nu \in \mathcal{M} hulgal \{0,1\}^\infty. Allikas on protsess (X_t)_{t \ge 1}, mis on jaotunud vastavalt mõõdule \nu. Metaeeljaotuse rollis kaalub eeltrüki võrrandi (1) \xi iga sellist \nu kaaluga w_\nu \approx 2^{-K(\nu)}. Kirjutame P_X = \nu fikseeritud elemendi jaoks hulgast \mathcal{M}. Kõik allpool toodud tulemused kehtivad iga mõõdu \nu kohta eraldi; Solomonoffi seos siseneb §4 domineerimispiiri kaudu.

1.2 Reproduktsiooni tähestik \hat{X}

Fikseeritud T,h korral defineerime minevikuplokkidel lõpliku horisondiga prediktiivse ekvivalentsusseose: x \sim_h x' \iff \nu(Y\in A\mid X=x)=\nu(Y\in A\mid X=x') \quad\text{kõigi mõõdetavate }A\subseteq\{0,1\}^h\text{ korral.} Olgu S_h suuruse X ekvivalentsiklass seose \sim_h järgi. Siis on S_h minimaalne piisav statistika Y ennustamiseks X põhjal horisondil h.

Täielik \epsilon-masina põhjuslik seisund S on lõpmatu horisondiga objekt, mis saadakse, kui minnakse üle poollõpmatutele minevikutele ja täielikule tulevikule. Käesolev lisa kasutab lõpliku horisondi tuletustes S_h ning reserveerib S täieliku põhjusliku seisundi piirjuhu jaoks.

Arvutatavuse staatus. Üldise arvutatava \nu korral ei väida käesolev lisa prediktiivse seisundijaotuse täpset arvutatavust. Seda käsitletakse idealiseeritud mõõdetava objektina. Täpne arvutatavus väidetakse üksnes selgesõnaliselt määratletud alamklasside, näiteks lõpliku mäluga protsesside, puhul.

1.3 Moonutusfunktsioon d_h(x, z)

Moonutusfunktsioon on KL-prediktiivne divergents: d_h(x,z):=D_{\mathrm{KL}}\!\big(P_\nu(Y\mid X=x)\,\|\,P_\nu(Y\mid Z=z)\big). Siin on Z representatsioonimuutuja, mille toodab enkooder p(z\mid x). Kui Z=S_h, on see täpne prediktiivse seisundi moonutus; kui Z on jämedustus või stohhastiline kood, siis P_\nu(Y\mid Z=z) on sellest indutseeritud prediktiivne seadus.

Täielik nelik

§2. R_{T,h}(D) tuletus neliku korral

§1 neliku rate-distortion-funktsioon on:

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

2.1 KL-moonutuse identsus

Olgu X:=X_{1:T}, Y:=X_{T+1:T+h} ja olgu Z suvaline esitus, mille toodab kodeerija p(z\mid x). Kuna Z-X-Y on Markovi ahel, \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). Ekvivalentselt, \mathbb E[d_h(X,Z)] = I(X;Y)-I(Z;Y)=E_{T,h}(\nu)-I(Z;Y). Seega on moonutuspiirang \mathbb E[d_h(X,Z)]\le D ekvivalentne tingimusega I(Z;Y)\ge E_{T,h}(\nu)-D.

2.2 Informatsioonilise pudelikaela ümberformuleering

Moonutuspiirang kitsendab lubatavate enkooderite ruumi nendeni, mis rahuldavad tingimust \mathbb{E}[d_h(X,Z)] \le D. See vastab täpselt sellele, et I(Z;Y) on altpoolt piiratud, andes kitsendatud Informatsioonilise Pudelikaela probleemi. Kuna saavutatav piirkond \{(I(Z;Y), I(X;Z))\} on standardsete ajajaotuse argumentide alusel kumer, kehtib tugev duaalsus. See võimaldab täpset ümberformuleeringut Informatsioonilise Pudelikaela Lagrangiaani abil (Tishby, Pereira & Bialek 1999 [28]): \mathcal{L}[p(z|x)] = I(X ; Z) - \beta \cdot I(Z ; Y) kus Lagrange’i kordaja \beta on määratud D poolt. IB Lagrangiaan jälgib pakkemäära ja prediktiivse truuduse vahelise Pareto rindejoone kulgu.

2.3 Põhiteoreem: üldine alampiir ja võrdsuse kriteerium

Kehtestame määra-moonutuse funktsiooni jaoks järgmise piiri:

Propositsioon (üldine alampiir ja võrdsuse kriteerium).
Iga kodeerija p(z\mid x) korral olgu D:=\mathbb E[d_h(X,Z)]. Siis I(X;Z)=E_{T,h}(\nu)-D+I(X;Z\mid Y). Järelikult R_{T,h}(D)\ge E_{T,h}(\nu)-D. Kompaktsete lõplike reproduktsioonialfabeetide korral, kus pidevus tagab, et infimum kodeerijate üle saavutatakse, kehtib võrdsus antud moonutuse D juures parajasti siis ja ainult siis, kui leidub seda moonutust saavutav kodeerija, mille korral I(X;Z\mid Y)=0. Deterministlike kodeerijate Z=g(X) puhul on see ekvivalentne tingimusega H(Z\mid Y)=0.

Nullmoonutuse korral saavutab minimaalne piisav statistika S_h R_{T,h}(0)=I(X;S_h)=H(S_h). Pange tähele, et see nullmoonutuse määr H(S_h) asub üldjuhul rangelt allpiirist E_{T,h} kõrgemal. Erinevus on mittenegatiivne lõhe H(S_h) - E_{T,h} = H(S_h|Y). Füüsikaliselt esindab see lõhe minevikus talletatud struktuurset „salvestatud informatsiooni“, mida tulevikuaken üksi ei suuda taastada. Võrdsuse kehtimine nullmoonutuse korral (H(S_h|Y)=0) on tugevalt degenereerunud juhtum, mis on keerukate protsesside puhul üldiselt väär.

Täieliku kausaalse seisundi piirjuhul R(0)=C_{\mu,\nu}=H(S). See võrdub E_\nu-ga ainult erijuhtudel; üldiselt kehtib E_\nu < C_{\mu,\nu}.

2.4 Käitumine jämedamate reproduktsioonialfabeetide korral

Iga deterministliku jämedustamise Z=g(S_h) korral 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. mittenegatiivne lõtkuterm I(X;Z\mid Y) kaob üksnes siis, kui jämedustatud representatsioon on tulevikuaknast Y taastatav. Seega annavad jämedamad alfabeedid üldjuhul määr-moonutuse kõverad, mis paiknevad rangelt sirgest E_{T,h}-D kõrgemal. See sirge on universaalne alampiir, mitte üldiselt saavutatav ümbris. Iga praktiliselt arvutatav koodek kasutab põhjuslike seisundite lõpliku mäluga lähendust ning seetõttu paikneb selle kõver sellest piirist kõrgemal.

2.5 Piirihinnangud

(Märkus: lõpmatu horisondi piiril asub nullmäära punkt moonutuse E_\nu juures, mitte C_{\mu,\nu} juures)

§3. C_{\max} — iseloomustus ja barjäärid

3.1 Lõpmatu horisondi koondumise lemma

Peateoreem (§2.3) kehtestab lõplike (T, h) korral alumise piiri R_{T,h}(D) \ge E_{T,h}(\nu) - D. Nüüd näitame, et see laieneb lõpmatu horisondi seadistusele.

Lemma (lõpmatu horisondi laiendus). Olgu \nu statsionaarne ergoodiline mõõt hulgal \{0,1\}^\infty. Siis:

1. E_{T,h}(\nu) = I(X_{1:T}\,;\,X_{T+1:T+h}) on mittelangav nii T kui ka h suhtes (andmetöötluse võrratuse tõttu: pikematele plokkidele tingimine ei saa statsionaarsuse korral vähendada mineviku ja tuleviku vahelist vastastikust informatsiooni).
2. Piirväärtus E_\nu := \lim_{T,h \to \infty} E_{T,h}(\nu) eksisteerib (võimalik, et +\infty) monotoonse koondumise tõttu.
3. Iga fikseeritud D \ge 0 korral on jada R_{T,h}(D) mittelangav T suhtes (pikem minevik ei saa vähendada optimaalset pakkemäära) ning mittelangav h suhtes. Monotoonsuse tõestuse visand h suhtes: moonutusfunktsioon laguneb kujule d_{h+1}(x, z) = D_{\mathrm{KL}}\!\left(P_\nu(\cdot \mid x) \,\|\, P_z(\cdot \mid z)\right) üle h+1 tulevikusammu, mida saab ahelreegli abil kirjutada kujul 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). Kuna teine liige on mittenegatiivne, siis d_{h+1} \geq d_h punktiviisiliselt. Seega kitsendite hulk \{P(z|x) : E[d_{h+1}] \leq D\} \subseteq \{P(z|x) : E[d_h] \leq D\}, ning väiksema lubatud hulga üle minimeerimine ei saa määra vähendada: R_{T,h+1}(D) \geq R_{T,h}(D).
4. Seega eksisteerib R_\nu(D) := \lim_{T,h \to \infty} R_{T,h}(D).

Kuna R_{T,h}(D) \ge E_{T,h}(\nu) - D kehtib igas lõplikus astmes ning mõlemad pooled koonduvad monotoonselt, kandub piirang üle piirväärtusele:

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

See on lõpmatu horisondi alumine piir, millele viidatakse allpool propositsioonides T-1a ja T-1c. Märkus: protsesside korral, mille puhul E_\nu = +\infty (nt kõrget järku de Bruijni tsüklid, kui k \to \infty), on piirang triviaalselt täidetud; sellised protsessid on välistatud vaatlejaga ühilduvast hulgast O_{C_{\max},D_{\min}} iga lõpliku C_{\max} korral.

3.2 M jaotus Stabiilsusfiltri järgi — Propositsioon T-1a

Propositsioon T-1a (mittetriviaalne jaotus).
Fikseerime empiirilised suurused C_{\max}>0, \Delta t>0 ja D_{\min}\ge0. Defineerime O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Siis on nii O_{C_{\max},D_{\min}} kui ka selle täiend mittetühjad.

Tõestus. Konstantne protsess kuulub hulka O_{C_{\max},D_{\min}}, sest sellel on E_\nu=0 ja R_\nu(D)=0.
Täiendi jaoks valime järku k binaarse de Bruijni tsükli protsessi: statsionaarse ergoodilise binaarse protsessi perioodiga 2^k ühtlase faasijaotusega, milles iga pikkusega k sõna esineb igas tsüklis täpselt üks kord. Selle protsessi korral E_\nu=C_{\mu,\nu}=k. Seega R_\nu(D_{\min})\ge k-D_{\min}. Valides k>C_{\max}\Delta t + D_{\min}, saame R_\nu(D_{\min})>C_{\max}\Delta t, seega \nu\notin O_{C_{\max},D_{\min}}. \square

3.3 C_{\max} definitsioon/iseloomustus — T-1b

Definitsioon T-1b (empiiriline teadvusliku ligipääsu ribalaiuse parameeter).
C_{\max} võetakse empiirilise teadvusliku ligipääsu ribalaiuse parameetrina, mis on määra-moonutuse formalismist väline. Antud C_{\max} korral defineeritakse vaatlejaga ühilduv klass O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Kui soovitakse kokku võtta eraldi määratletud referentsklassi \mathcal{O}_{ref}, defineeritakse C^{ref}_{max}:=\frac{1}{\Delta t}\sup_{\nu\in\mathcal{O}_{ref}}R_\nu(D_{\min}). See on valitud klassi kokkuvõtlik statistiline näitaja, mitte klassi enda definitsioon.

3.4 Mitte-esilekerkimise barjäär — tõestuse visand T-1c

Tõestuse visand T-1c (puudub lõplik universaalne ülempiir üksnes \xi põhjal).
Solomonoffi poolmõõt \xi omistab igale arvutatavale mõõdule \nu\in\mathcal M positiivse aprioorse kaalu. Klass \mathcal M sisaldab statsionaarseid ergoodilisi binaarprotsesse meelevaldselt suure liigentroopiaga E_\nu (näiteks ülal toodud de Bruijni perekond). Kuna R_\nu(D_{\min})\ge E_\nu-D_{\min}, siis ei ole olemas ühtki lõplikku kogu toele kehtivat ülempiiri suurusele R_\nu(D_{\min}), mida saaks tuletada üksnes \xi põhjal. Seega nõuab iga lõplik C_{\max} lisaks paljale Solomonoffi aprioorsele jaotusele täiendavat empiirilist sisendit või klassi piiravat eeldust. \square

§4. Seos Solomonoffi meta-prioriga

§1 nelik ja §2 R(D)-tuletus on esitatud mõõdu \nu kaupa. Solomonoffi seos — see, kuidas meta-prior \xi kaalub vaatlejaga ühilduvaid vooge — on tuletuse asemel struktuurne vastavus.

Iga vaatlejaga ühilduva \nu \in O_{C_{\max},D_{\min}} korral tagab määra-moonutuse tasakaal, et kokkupakitud voog z_{0:T} on Stabiilsusfiltri valitud representatsioon. Solomonoffi prior \xi omistab sellele \nu-le kaalu w_\nu \approx 2^{-K(\nu)}: lihtsamad (madalama K-ga) vaatlejaga ühilduvad protsessid on \xi all eksponentsiaalselt tõenäolisemad. See on säästlikkuse argumendi (Lisa T-4) formaalne väljendus: Stabiilsusfilter, toimides \xi peal, valib kõige lihtsama koodeki, mis mahub ribalaiuse piiresse.

T-4b dominantsuspiir kehtib otseselt: iga arvutatava füüsikamõõdu \nu korral, mille puhul K(\nu) < \infty:

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

See tagab, et OPT meta-prior \xi ei omista vaatlejaga ühilduvatele voogudele kunagi väiksemat tõenäosust kui ükski fikseeritud arvutatav füüsikamudel, kuni mudeli enda kirjelduspikkuseni K(\nu).

§5. Kogemuslik bitikvant h^\ast (E-1 eelvaade)

Antud empiirilise valiku C_{\max} ja empiirilise teadvusliku uuendusakna \Delta t korral defineerime h^*:=C_{\max}\Delta t. Kui C_{\max}\approx 10 bitti/s ja \Delta t\in[50,80] ms, siis h^*\approx 0.5\text{–}0.8 bitti teadvusliku hetke kohta.

Iga statsionaarne ergoodiline protsess \nu \in \mathcal{M}, mis rahuldab tingimust E_{T,h}(\nu) - D_{\min} > h^\ast, käivitab õiguspäraselt Narratiivi lagunemise. Põhjus on selles, et R_{T,h}(D_{\min}) \ge E_{T,h} - D_{\min} > h^\ast = C_{\max} \Delta t, mis rikub otsesõnu ühilduvuskriteeriumi. See on siiski kollapsi jaoks piisav, mitte rangelt vajalik tingimus: kuna alampiir on harva täpne (R_{T,h} > E_{T,h} - D_{\min} üldjuhul vastavalt §2.4-le), võivad protsessid läbida Narratiivi lagunemise ka siis, kui E_{T,h} - D_{\min} \le h^\ast. See annab E-1 jaoks kvantitatiivse ennustuse; tundlikkust valiku \Delta t \in [40, 300] ms suhtes käsitletakse E-1 lisas.

§6. Kokkuvõttev sulgemine

T-1 tulemused — muudetud staatus

1. Nelik on määratletud lõpliku horisondiga prediktiivses seades.
2. Prediktiivse-KL identiteet on korrektselt tuletatud.
3. Üldine teoreem R(D)=C_\mu-D on asendatud korrektse alampiiriga R_{T,h}(D)\ge E_{T,h}-D koos täpse võrdsuse kriteeriumiga I(X;Z\mid Y)=0.
4. Nullmoonutusega kodeerimist iseloomustab minimaalne piisav statistika S_h, ning täieliku põhjusliku seisundi piiril kehtib R(0)=C_{\mu,\nu}.
5. C_{\max} käsitletakse empiirilisena, mitte sisemiselt tuletatuna.
6. h^*=C_{\max}\Delta t on empiiriline parametriseerimine, mitte §2 teoreem.

See lisa hoitakse OPT projekti repositooriumi osana koos failiga theoretical_roadmap.pdf.