Kenningin um raðaðan patch (OPT)

Upprunalegt verkefni T-1: Stöðugleikasía — full forskrift fyrir hraða-brenglunarfræði Vandamál: Hraða-brenglunarfræði Shannons krefst: uppsprettu X, endurgerðarstafrófs og brenglunarfalls d(x, \hat{x}). Forprentið vísar til R_{pred}(D) án þess að skilgreina þessa þrjá þætti fyrir hvarfefni OPT. Afhending: Fullkomin forskrift (\mathcal{X}, \hat{\mathcal{X}}, P_X, d) fyrir hraða-brenglunarverkefni OPT.

Í þessari endurskoðun er gerður skýr greinarmunur á umframóreiðu og tölfræðilegum margbreytileika, sannað er forspár-KL-samsemdin á endanlegum sjóndeildarhring, sönnuð er almenna neðri markið R_{T,h}(D)\ge E_{T,h}-D, og sett er fram nákvæmt jafngildisskilyrði fyrir því hvenær því neðra marki er náð. C_{\max} er áfram reynslubundin stika fremur en stærð sem leidd er af hraða-brenglunarformalismanum.
Lokunarstaða: LEYST AÐ HLUTA. Fjórundarskilgreiningin, forspár-KL-samsemdin og almenna neðri markið R_{T,h}(D) \geq E_{T,h}(\nu) - D hafa verið staðfest ásamt nákvæmu jafngildisskilyrði. Fyrri almenna fullyrðingin í lokuðu formi R(D) = C_\mu - D hefur verið dregin til baka; rétta niðurstaðan er neðra markið. C_{\max} er áfram reynslubundin stika fremur en stærð sem leidd er af hraða-brenglunarformalismanum.

§0. Framsetningarstig

Vinnuskilgreining. Festum T,h<\infty. Látum X:=X_{1:T} tákna liðna blokk og Y:=X_{T+1:T+h} framtíðarforspárblokk undir föstu reiknanlegu kyrrstæðu ergódísku máli \nu\in\mathcal M. Skilgreinum forspárupplýsingar á endanlegum sjóndeildarhring E_{T,h}(\nu):=I(X;Y). Þegar markgildi fyrir óendanlegan sjóndeildarhring er til, skilgreinum umframóreiðu E_\nu := I(\overleftarrow X;\overrightarrow X). Ef S táknar fullt orsakaástand \epsilon-vélarinnar, skilgreinum tölfræðilega flækjustigið C_{\mu,\nu}:=H(S). Þetta eru aðgreindar stærðir. Endanlega sjóndeildarhrings-vandamálið um hraða-brenglun í þessum viðauka er sett fram með tilliti til E_{T,h}, en ekki C_{\mu,\nu}. Algild hálfmæling Solomonoffs \xi kemur aðeins inn sem metavægi fordreifingar (forprentun, jafna 1): einstakar R(D)-ferlar eru reiknaðir fyrir hvert mál \nu. Niðurstöður sem krefjast fullrar blöndunnar \xi eru settar fram sérstaklega.

§1. Fullkomin skilgreining fjórundarinnar

1.1 Uppruni X og dreifingin P_X

Festum reiknanlega kyrrstæða ergódíska mælingu \nu \in \mathcal{M} á \{0,1\}^\infty. Uppruninn er ferlið (X_t)_{t \ge 1} sem dreifist samkvæmt \nu. Fyrir hlutverk metafordreifingar vegur \xi úr jöfnu (1) í preprinti hvert slíkt \nu með w_\nu \approx 2^{-K(\nu)}. Við skrifum P_X = \nu fyrir fastan þátt í \mathcal{M}. Allar niðurstöður hér að neðan gilda fyrir hverja mælingu \nu; tengingin við Solomonoff kemur inn í gegnum yfirráðamörkin í §4.

1.2 Endurmyndunarstafróf \hat{X}

Fyrir föst T,h skilgreinum við forspárjafngildisvensl með endanlegum sjóndeildarhring á fortíðarblokkum: x \sim_h x' \iff \nu(Y\in A\mid X=x)=\nu(Y\in A\mid X=x') \quad\text{fyrir öll mælanleg }A\subseteq\{0,1\}^h. Látum S_h tákna jafngildisflokk X undir \sim_h. Þá er S_h minnsta nægilega tölfræðistærðin til að spá fyrir um Y út frá X við sjóndeildarhring h.

Fulla orsakaástand \epsilon-vélarinnar, S, er óendanlegs sjóndeildarhrings hlutur sem fæst þegar farið er yfir í hálfóendanlega fortíð og alla framtíðina. Í þessum viðauka er S_h notað fyrir afleiðingar með endanlegum sjóndeildarhring, en S er frátekið fyrir fullt markgildi orsakaástandsins.

Reiknanleikastaða. Fyrir almennt reiknanlegt \nu er því ekki haldið fram í þessum viðauka að skiptingin í forspárástand sé nákvæmlega reiknanleg. Hún er meðhöndluð sem hugsjónuð mælanleg stærð. Nákvæmur reiknanleiki er aðeins staðhæfður fyrir skýrt afmarkaða undirflokka, svo sem ferli með endanlegt minni.

1.3 Brenglunarfall d_h(x, z)

Brenglunarfallið er KL-forspárfrávikið: d_h(x,z):=D_{\mathrm{KL}}\!\big(P_\nu(Y\mid X=x)\,\|\,P_\nu(Y\mid Z=z)\big). Hér er Z framsetningarbreyta sem verður til með kóðara p(z\mid x). Þegar Z=S_h er þetta nákvæm brenglun forspárástands; þegar Z er grófun eða slembikóði er P_\nu(Y\mid Z=z) afleidda forspárlögmálið.

Fullkomin fjórund

§2. Afleiðsla R_{T,h}(D) undir fjórundinni

Rate-distortion-fallið fyrir fjórundina í §1 er:

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

2.1 KL-brenglunarsamsemdin

Látum X:=X_{1:T}, Y:=X_{T+1:T+h}, og látum Z vera hvaða framsetningu sem er framleidda af kóðara p(z\mid x). Þar sem Z-X-Y er Markov-keðja, \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). Jafngilt, \mathbb E[d_h(X,Z)] = I(X;Y)-I(Z;Y)=E_{T,h}(\nu)-I(Z;Y). Því er brenglunarskilyrðið \mathbb E[d_h(X,Z)]\le D jafngilt I(Z;Y)\ge E_{T,h}(\nu)-D.

2.2 Endurframsetning upplýsingahálsins

Bjögunarskilyrðið takmarkar rúm leyfilegra kóðara við þá sem fullnægja \mathbb{E}[d_h(X,Z)] \le D. Þetta samsvarar nákvæmlega því að setja neðri mörk á I(Z;Y) og gefur þannig hið skorðaða verkefni upplýsingahálsins. Þar sem framkvæmanlega svæðið \{(I(Z;Y), I(X;Z))\} er kúpt samkvæmt stöðluðum rökum um tímaskiptingu, gildir sterk tvíund. Þetta gerir kleift nákvæma endurframsetningu með Lagrange-falli upplýsingahálsins (Tishby, Pereira & Bialek 1999 [28]): \mathcal{L}[p(z|x)] = I(X ; Z) - \beta \cdot I(Z ; Y) þar sem Lagrange-margfaldarinn \beta ræðst af D. IB-Lagrange-fallið rekur Pareto-jaðarinn milli þjöppunarhraða og forspártryggðar.

2.3 Meginsetning: Almenn neðri mörk og jafngildisskilyrði

Við setjum fram mörkin fyrir rate-distortion-fallið:

Setning (almenn neðri mörk og jafngildisskilyrði).
Fyrir hvaða kóðara sem er p(z\mid x), látum D:=\mathbb E[d_h(X,Z)]. Þá gildir I(X;Z)=E_{T,h}(\nu)-D+I(X;Z\mid Y). Þar af leiðandi, R_{T,h}(D)\ge E_{T,h}(\nu)-D. Fyrir þéttar endurgerðarstafrófsgerðir með endanlegum fjölda staka, þar sem samfelldni tryggir að infimum yfir kóðurum næst, gildir jafngildi við gefna bjögun D þá og því aðeins að til sé kóðari sem nær þeirri bjögun með I(X;Z\mid Y)=0. Fyrir ákvörðuð kóðunarkort Z=g(X) er þetta jafngilt H(Z\mid Y)=0.

Við núllbjögun nær minnsta nægjanlega tölfræðistærðin S_h R_{T,h}(0)=I(X;S_h)=H(S_h). Athugið að þetta núllbjögunarhraðagildi H(S_h) liggur almennt strangt ofan við neðri mörkin E_{T,h}. Mismunurinn er hið óneikvæða bil H(S_h) - E_{T,h} = H(S_h|Y). Þetta bil táknar eðlisfræðilega formbundnar „geymdar upplýsingar“ í fortíðinni sem framtíðarglugginn einn og sér nær ekki að endurheimta. Að jafngildi haldist við núllbjögun (H(S_h|Y)=0) er mjög úrkynjað tilvik sem er almennt ósatt fyrir flókin ferli.

Í fullum orsakaástandamörkum, R(0)=C_{\mu,\nu}=H(S). Þetta er aðeins jafnt E_\nu í sérstökum tilvikum; almennt gildir E_\nu < C_{\mu,\nu}.

2.4 Hegðun fyrir grófari endurmyndunarstafróf

Fyrir sérhverja ákvarðaða grófun 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. Óneikvæða slakaliðurinn I(X;Z\mid Y) hverfur einungis þegar hægt er að endurheimta grófuðu framsetninguna úr framtíðarglugganum Y. Því leiða grófari stafróf almennt til hraða-brenglunarferla sem liggja strangt ofan við línuna E_{T,h}-D. Línan er algilt neðra mark, en ekki almennt umslag sem næst í framkvæmd. Sérhver kóðari sem er reiknanlegur í reynd notar nálgun á orsakaástandi með endanlegu minni og hefur því feril sem liggur ofan við þessi mörk.

2.5 Jaðarmat

(Athugið: Í markgildinu fyrir óendanlegan sjóndeildarhring er núllhraðapunkturinn við bjögunina E_\nu, ekki við C_{\mu,\nu})

§3. C_{\max} — Eðlisgreining og þröskuldar

3.1 Samleitnilemma fyrir óendanlegan sjóndeildarhring

Meginsetningin (§2.3) setur fram neðri mörkin R_{T,h}(D) \ge E_{T,h}(\nu) - D fyrir endanleg (T, h). Nú sýnum við að þetta nær einnig til tilviks með óendanlegum sjóndeildarhring.

Lemma (útvíkkun á óendanlegan sjóndeildarhring). Látum \nu vera stöðuga ergódíska mælingu á \{0,1\}^\infty. Þá gildir:

1. E_{T,h}(\nu) = I(X_{1:T}\,;\,X_{T+1:T+h}) er ekki minnkandi í bæði T og h (samkvæmt gagnavinnslujöfnunni: skilyrðing á lengri blokkum getur ekki minnkað gagnkvæmar upplýsingar milli fortíðar og framtíðar undir stöðugleika).
2. Markgildið E_\nu := \lim_{T,h \to \infty} E_{T,h}(\nu) er til (hugsanlega +\infty) samkvæmt einhæfri samleitni.
3. Fyrir sérhvert fast D \ge 0 er runan R_{T,h}(D) ekki minnkandi í T (lengri fortíð getur ekki lækkað besta mögulega þjöppunarhraða) og ekki minnkandi í h. Sönnunardrög fyrir einhæfni í h: Bjögunarfallið sundrast sem d_{h+1}(x, z) = D_{\mathrm{KL}}\!\left(P_\nu(\cdot \mid x) \,\|\, P_z(\cdot \mid z)\right) yfir h+1 framtíðarskref, og má skrifa það með keðjureglunni sem 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). Þar sem seinni liðurinn er ekki neikvæður, gildir punktvíst að d_{h+1} \geq d_h. Því er skorðusafnið \{P(z|x) : E[d_{h+1}] \leq D\} \subseteq \{P(z|x) : E[d_h] \leq D\}, og lágmörkun yfir minna framkvæmanlegu mengi getur ekki lækkað hraðann: R_{T,h+1}(D) \geq R_{T,h}(D).
4. Því er R_\nu(D) := \lim_{T,h \to \infty} R_{T,h}(D) til.

Þar sem R_{T,h}(D) \ge E_{T,h}(\nu) - D gildir á hverju endanlegu stigi, og báðar hliðar stefna einhæft að markgildi, flyst skorðan yfir á markgildið:

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

Þetta eru neðri mörkin fyrir óendanlegan sjóndeildarhring sem vísað er til í setningum T-1a og T-1c hér að neðan. Athugið: Fyrir ferli með E_\nu = +\infty (t.d. de Bruijn-hringi af hárri gráðu þegar k \to \infty), er skorðan sjálfkrafa uppfyllt; slík ferli eru útilokuð úr mengi athuganda-samhæfra plástra O_{C_{\max},D_{\min}} fyrir sérhvert endanlegt C_{\max}.

3.2 Skipting M með Stöðugleikasíu — Setning T-1a

Setning T-1a (óþýðingarmikil skipting).
Festum reynslubundið C_{\max}>0, \Delta t>0 og D_{\min}\ge0. Skilgreinum O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Þá eru bæði O_{C_{\max},D_{\min}} og fyllimengi þess ekki tóm.

Sönnun. Fasti ferillinn liggur í O_{C_{\max},D_{\min}} vegna þess að hann hefur E_\nu=0 og R_\nu(D)=0.
Fyrir fyllimengið veljum við tvígildan de Bruijn-hringferilsferil af stigi k: stöðugt ergódískt tvígilt ferli með lotu 2^k og jafndreifðum fasa, þar sem hvert orð af lengd k kemur fyrir nákvæmlega einu sinni í hverri lotu. Fyrir þetta ferli gildir E_\nu=C_{\mu,\nu}=k. Því fæst R_\nu(D_{\min})\ge k-D_{\min}. Með því að velja k>C_{\max}\Delta t + D_{\min} fæst R_\nu(D_{\min})>C_{\max}\Delta t, svo \nu\notin O_{C_{\max},D_{\min}}. \square

3.3 Skilgreining/einkenning á C_{\max} — T-1b

Skilgreining T-1b (reynslubundin bandbreiddarbreyta).
C_{\max} er tekið sem reynslubundin bandbreiddarbreyta fyrir meðvitaðan aðgang sem er ytri gagnvart rate-distortion-formalíseringunni. Gefið C_{\max}, skilgreinum við flokkinn sem er samrýmanlegur athuganda O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Ef ætlunin er að draga saman sérstaklega skilgreindan viðmiðunarflokk \mathcal{O}_{ref}, skilgreinum við C^{ref}_{max}:=\frac{1}{\Delta t}\sup_{\nu\in\mathcal{O}_{ref}}R_\nu(D_{\min}). Þetta er samantektarstærð fyrir valinn flokk, en ekki skilgreining á flokknum sjálfum.

3.4 Hindrunin gegn ekki-tilkomu — Sönnunardrög T-1c

Sönnunardrög T-1c (engin endanleg algild efri mörk frá \xi einu saman).
Algild hálfmæling Solomonoffs \xi úthlutar jákvæðu forvægisgildi til sérhvers reiknanlegs mælis \nu\in\mathcal M. Flokkurinn \mathcal M inniheldur stöðug kyrrstæð tvígild ferli með handahófskennt mikla umframóreiðu E_\nu (til dæmis de Bruijn-fjölskylduna hér að ofan). Þar sem R_\nu(D_{\min})\ge E_\nu-D_{\min}, eru engin endanleg efri mörk sem gilda yfir allan stuðninginn á R_\nu(D_{\min}) afleiðanleg af \xi einu saman. Sérhver endanleg C_{\max} krefst því viðbótar að reynslugögnum eða inntaki sem þrengir flokkinn umfram hinn bera Solomonoff-forvigta. \square

§4. Tengsl við Solomonoff-meta-forgengið

Fjórundin í §1 og R(D)-afleiðslan í §2 eru sett fram fyrir hvert mæli \nu. Tengingin við Solomonoff — hvernig meta-forgengið \xi vegur strauma sem eru samrýmanlegir athuganda — er formgerðarsamsvörun fremur en afleiðsla.

Fyrir sérhvert \nu \in O_{C_{\max},D_{\min}} sem er samrýmanlegt athuganda tryggir jafnvægi hraða og bjögunar að þjappaði straumurinn z_{0:T} sé það framsetningarform sem Stöðugleikasían velur. Solomonoff-forgengið \xi úthlutar þessu \nu væginu w_\nu \approx 2^{-K(\nu)}: einfaldari (lægra K) ferli sem eru samrýmanleg athuganda eru veldisvísislega líklegri undir \xi. Þetta er formleg framsetning á röksemdinni um sparneytni (Viðauki T-4): Stöðugleikasían, sem verkar á \xi, velur einfaldasta kóðarann sem fellur innan bandbreiddarinnar.

Yfirráðamörkin úr T-4b eiga hér beint við: fyrir sérhvern reiknanlegan eðlisfræðilegan mæli \nu með K(\nu) < \infty:

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

Þetta tryggir að OPT-meta-forgengið \xi úthluti aldrei lægri líkum til strauma sem eru samrýmanlegir athuganda en nokkurt fast reiknanlegt líkan af eðlisfræði, að viðbættri eigin lýsingarlengd líkansins K(\nu).

§5. Upplifunarbitaskammturinn h^\ast (forsmekkur að E-1)

Gefið reynslubundið val á C_{\max} og reynslubundinn meðvitaðan uppfærsluglugga \Delta t, skilgreinum h^*:=C_{\max}\Delta t. Fyrir C_{\max}\approx 10 bita/s og \Delta t\in[50,80] ms, h^*\approx 0.5\text{–}0.8 bita á hvert meðvitað augnablik.

Sérhvert stöðugt ergódískt ferli \nu \in \mathcal{M} sem uppfyllir E_{T,h}(\nu) - D_{\min} > h^\ast mun með réttmætum hætti kalla fram Frásagnarhrun. Ástæðan er sú að R_{T,h}(D_{\min}) \ge E_{T,h} - D_{\min} > h^\ast = C_{\max} \Delta t, sem brýtur með skýrum hætti gegn samhæfniviðmiðinu. Þetta er þó nægjanlegt skilyrði fyrir hruni, en ekki stranglega nauðsynlegt: þar sem neðri mörkin eru sjaldan þröng (R_{T,h} > E_{T,h} - D_{\min} almennt samkvæmt §2.4), geta ferli farið í Frásagnarhrun jafnvel þegar E_{T,h} - D_{\min} \le h^\ast. Þetta veitir megindlega spá fyrir E-1; næmnin gagnvart vali á \Delta t \in [40, 300] ms er rædd í viðauka E-1.

§6. Samantekt um lokun

Afhendingaratriði T-1 — endurskoðuð staða

1. Fjórundin er skilgreind innan forspárumhverfis með endanlegum sjóndeildarhring.
2. Forspár-KL-samsemdin er leidd rétt af.
3. Almenna setningin R(D)=C_\mu-D er skipt út fyrir rétt neðra mark R_{T,h}(D)\ge E_{T,h}-D ásamt nákvæmu jafngildisskilyrði I(X;Z\mid Y)=0.
4. Núllbjögunarkóðun er lýst með lágmarks nægilegri tölfræði S_h, og í fullum markatilviksmarka orsakaástands gildir R(0)=C_{\mu,\nu}.
5. C_{\max} er meðhöndlað sem reynslubundið, ekki sem eitthvað sem er leitt af innan kerfisins.
6. h^*=C_{\max}\Delta t er reynslubundin stikun, ekki setning úr §2.

Þessum viðauka er viðhaldið sem hluta af OPT-verkefnageymslunni samhliða theoretical_roadmap.pdf.