Järjestetyn patchin teoria

Alkuperäinen tehtävä T-1: Stabiilisuussuodatin — täydellinen rate-distortion-määrittely Ongelma: Shannonin rate-distortion-teoria edellyttää: lähdettä X, rekonstruoitujen arvojen aakkostoa sekä vääristymäfunktiota d(x, \hat{x}). Preprintissä vedotaan suureeseen R_{pred}(D) täsmentämättä näitä kolmea elementtiä OPT:n substraatille. Toimitettava: Täydellinen määritys (\mathcal{X}, \hat{\mathcal{X}}, P_X, d) OPT:n rate-distortion-ongelmalle.

Tässä revisiossa erotetaan ylimääräinen entropia ja tilastollinen kompleksisuus toisistaan, todistetaan prediktiivinen-KL-identiteetti äärellisellä horisontilla, todistetaan yleinen alaraja R_{T,h}(D)\ge E_{T,h}-D, ja esitetään täsmällinen yhtäsuuruuskriteeri sille, milloin tämä alaraja saavutetaan. C_{\max} pysyy empiirisenä parametrina eikä rate-distortion-formalismista johdettuna suureena.
Ratkaisutila: OSITTAIN RATKAISTU. Nelikon määritys, prediktiivinen-KL-identiteetti ja yleinen alaraja R_{T,h}(D) \geq E_{T,h}(\nu) - D on vahvistettu täsmällisen yhtäsuuruuskriteerin kanssa. Aiempi yleinen suljetun muodon väite R(D) = C_\mu - D on peruttu; oikea tulos on alaraja. C_{\max} pysyy empiirisenä parametrina eikä rate-distortion-formalismista johdettuna suureena.

§0. Muotoilun taso

Työmuotoilu. Kiinnitetään T,h<\infty. Olkoon X:=X_{1:T} menneisyyden lohko ja Y:=X_{T+1:T+h} tulevaisuuteen katsova lohko kiinteän laskettavan stationaarisen ergodisen mitan \nu\in\mathcal M alaisuudessa. Määritellään äärellisen horisontin prediktiivinen informaatio E_{T,h}(\nu):=I(X;Y). Kun äärettömän horisontin raja-arvo on olemassa, määritellään ylimääräisentropia E_\nu := I(\overleftarrow X;\overrightarrow X). Jos S merkitsee täydellistä \epsilon-koneen kausaalitilaa, määritellään tilastollinen kompleksisuus C_{\mu,\nu}:=H(S). Nämä ovat erillisiä suureita. Tämän liitteen äärellisen horisontin nopeus-vääristymäongelma esitetään suureen E_{T,h}, ei C_{\mu,\nu}, avulla. Solomonoffin universaali puolimitta \xi tulee mukaan vain metapriorin painotuksena (preprintin yhtälö 1): yksittäiset R(D)-käyrät lasketaan kullekin mitalle \nu erikseen. Tulokset, jotka edellyttävät koko seosta \xi, esitetään erikseen.

§1. Täydellinen nelikon spesifikaatio

1.1 Lähde X ja jakauma P_X

Kiinnitetään laskettava stationaarinen ergodinen mitta \nu \in \mathcal{M} joukossa \{0,1\}^\infty. Lähde on prosessi (X_t)_{t \ge 1}, joka jakautuu mitan \nu mukaisesti. Metapriorin roolissa preprintin yhtälön (1) \xi painottaa kutakin tällaista \nu:ta painolla w_\nu \approx 2^{-K(\nu)}. Kirjoitamme P_X = \nu kiinteälle jäsenelle joukosta \mathcal{M}. Kaikki alla olevat tulokset pätevät mittakohtaisesti kullekin \nu:lle; Solomonoff-yhteys tulee mukaan §4:n dominanssirajan kautta.

1.2 Reproduktioalfabetti \hat{X}

Kiinnitetyillä T,h määritellään äärellisen horisontin prediktiivinen ekvivalenssirelaatio menneisyyden lohkoille: x \sim_h x' \iff \nu(Y\in A\mid X=x)=\nu(Y\in A\mid X=x') \quad\text{kaikilla mitallisilla }A\subseteq\{0,1\}^h. Olkoon S_h muuttujan X ekvivalenssiluokka relaation \sim_h suhteen. Tällöin S_h on minimaalinen riittävä tunnusluku Y:n ennustamiseksi X:stä horisontilla h.

Täysi \epsilon-koneen kausaalitila S on äärettömän horisontin olio, joka saadaan siirtymällä puoliäärettömiin menneisyyksiin ja koko tulevaisuuteen. Tässä liitteessä käytetään S_h:ta äärellisen horisontin johtamisissa ja varataan S täydelle kausaalitilan raja-arvolle.

Laskettavuusstatus. Yleiselle laskettavalle \nu:lle tämä liite ei väitä prediktiivisen tilajaon olevan täsmällisesti laskettavissa. Sitä käsitellään idealisoituna mitallisena oliona. Täsmällinen laskettavuus väitetään vain eksplisiittisesti yksilöidyille alaluokille, kuten äärellisen muistin prosesseille.

1.3 Vääristymäfunktio d_h(x, z)

Vääristymäfunktio on KL-prediktiivinen divergenssi: d_h(x,z):=D_{\mathrm{KL}}\!\big(P_\nu(Y\mid X=x)\,\|\,P_\nu(Y\mid Z=z)\big). Tässä Z on representaatiomuuttuja, jonka kooderi tuottaa muodossa p(z\mid x). Kun Z=S_h, kyseessä on tarkka prediktiivisen tilan vääristymä; kun Z on karkeistus tai stokastinen koodi, P_\nu(Y\mid Z=z) on indusoitu prediktiivinen laki.

Täydellinen nelikko

§2. R_{T,h}(D):n johtaminen nelikon alla

§1:n nelikon rate-distortion-funktio on:

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

2.1 KL-vääristymäidentiteetti

Olkoon X:=X_{1:T}, Y:=X_{T+1:T+h}, ja olkoon Z mikä tahansa esitys, jonka kooderi tuottaa muodossa p(z\mid x). Koska Z-X-Y on Markov-ketju, \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). Ekvivalentisti, \mathbb E[d_h(X,Z)] = I(X;Y)-I(Z;Y)=E_{T,h}(\nu)-I(Z;Y). Siksi vääristymärajoite \mathbb E[d_h(X,Z)]\le D on ekvivalentti ehdon kanssa I(Z;Y)\ge E_{T,h}(\nu)-D.

2.2 Informaatiokapeikon uudelleenmuotoilu

Vääristymärajoite rajoittaa sallittujen enkooderien avaruuden niihin, jotka toteuttavat ehdon \mathbb{E}[d_h(X,Z)] \le D. Tämä vastaa täsmälleen sitä, että I(Z;Y) rajataan alhaalta, jolloin saadaan rajoitettu Informaatiokapeikko-ongelma. Koska saavutettava alue \{(I(Z;Y), I(X;Z))\} on konveksi tavanomaisten aikajakamisargumenttien nojalla, vahva duaalisuus pätee. Tämä mahdollistaa tarkan uudelleenmuotoilun käyttäen Informaatiokapeikon Lagrange-funktiota (Tishby, Pereira & Bialek 1999 [28]): \mathcal{L}[p(z|x)] = I(X ; Z) - \beta \cdot I(Z ; Y) missä Lagrangen kerroin \beta määräytyy D:n perusteella. IB:n Lagrange-funktio jäljittää pakkautumisnopeuden ja prediktiivisen uskollisuuden välisen Pareto-reunan.

2.3 Päälause: yleinen alaraja ja yhtäsuuruuskriteeri

Johdamme raja-arvon nopeus-vääristymäfunktiolle:

Propositio (yleinen alaraja ja yhtäsuuruuskriteeri).
Olkoon mille tahansa kooderille p(z\mid x) D:=\mathbb E[d_h(X,Z)]. Tällöin I(X;Z)=E_{T,h}(\nu)-D+I(X;Z\mid Y). Tästä seuraa, että R_{T,h}(D)\ge E_{T,h}(\nu)-D. Kompakteille äärellisille rekonstruktioaakkostoille, joissa jatkuvuus takaa, että kooderien yli otettu infimum saavutetaan, yhtäsuuruus annetulla vääristymällä D pätee täsmälleen silloin, kun on olemassa kyseisen vääristymän saavuttava kooderi, jolle I(X;Z\mid Y)=0. Deterministisille koodereille Z=g(X) tämä on ekvivalenttia ehdon H(Z\mid Y)=0 kanssa.

Nollavääristymässä minimaalinen riittävä statistiikka S_h saavuttaa R_{T,h}(0)=I(X;S_h)=H(S_h). Huomaa, että tämä nollavääristymän nopeus H(S_h) sijaitsee yleisesti ottaen aidosti alarajan E_{T,h} yläpuolella. Erotus on epänegatiivinen kuilu H(S_h) - E_{T,h} = H(S_h|Y). Fysikaalisesti tämä kuilu edustaa menneisyyteen varastoitunutta rakenteellista informaatiota, jota tulevaisuusikkuna yksin ei kykene palauttamaan. Se, että yhtäsuuruus pätee nollavääristymässä (H(S_h|Y)=0), on vahvasti degeneroitunut tapaus, joka on geneerisesti epätosi monimutkaisille prosesseille.

Täydessä kausaalitilojen rajassa R(0)=C_{\mu,\nu}=H(S). Tämä on yhtä suuri kuin E_\nu vain erityistapauksissa; yleisesti pätee E_\nu < C_{\mu,\nu}.

2.4 Käyttäytyminen karkeammille reproduktioaakkostoille

Mille tahansa deterministiselle karkeistukselle 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. Epänegatiivinen löysyystermi I(X;Z\mid Y) häviää vain silloin, kun karkeistettu representaatio on palautettavissa tulevaisuusikkunasta Y. Siksi karkeammat aakkostot tuottavat yleensä nopeus-vääristymäkäyriä, jotka sijaitsevat aidosti suoran E_{T,h}-D yläpuolella. Tämä suora on universaali alaraja, ei yleisesti saavutettu verhokäyrä. Mikä tahansa käytännössä laskettavissa oleva koodekki käyttää kausaalitilojen äärellisen muistin approksimaatiota, ja sen käyrä sijaitsee siksi tämän rajan yläpuolella.

2.5 Raja-arvioinnit

(Huom.: äärettömän horisontin rajassa nollanopeuspiste sijaitsee vääristymässä E_\nu, ei kohdassa C_{\mu,\nu})

§3. C_{\max} — Luonnehdinta ja esteet

3.1 Äärettömän horisontin konvergenssilemma

Päälause (§2.3) asettaa alarajan R_{T,h}(D) \ge E_{T,h}(\nu) - D äärellisille (T, h)-arvoille. Osoitamme nyt, että tämä laajenee äärettömän horisontin asetelmaan.

Lemma (Äärettömän horisontin laajennus). Olkoon \nu stationaarinen ergodinen mitta joukossa \{0,1\}^\infty. Tällöin:

1. E_{T,h}(\nu) = I(X_{1:T}\,;\,X_{T+1:T+h}) on kasvamaton kumpaankin suuntaan sekä T:n että h:n suhteen (datankäsittelyepäyhtälön nojalla: ehdollistaminen pidemmillä lohkoilla ei voi pienentää menneisyyden ja tulevaisuuden välistä keskinäisinformaatiota stationaarisuuden vallitessa).
2. Raja-arvo E_\nu := \lim_{T,h \to \infty} E_{T,h}(\nu) on olemassa (mahdollisesti +\infty) monotonisen konvergenssin perusteella.
3. Jokaiselle kiinteälle D \ge 0 jono R_{T,h}(D) on kasvamaton T:n suhteen (pidemmät menneisyydet eivät voi pienentää optimaalista pakkausnopeutta) ja kasvamaton h:n suhteen. Todistushahmotelma monotonisuudelle h:n suhteen: Vääristymäfunktio hajoaa muotoon d_{h+1}(x, z) = D_{\mathrm{KL}}\!\left(P_\nu(\cdot \mid x) \,\|\, P_z(\cdot \mid z)\right) yli h+1 tulevan askeleen, mikä voidaan kirjoittaa ketjusäännön avulla muodossa 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). Koska toinen termi on epänegatiivinen, pätee pisteittäin d_{h+1} \geq d_h. Siksi rajoitejoukko \{P(z|x) : E[d_{h+1}] \leq D\} \subseteq \{P(z|x) : E[d_h] \leq D\}, eikä minimointi pienemmän sallittujen ratkaisujen joukon yli voi pienentää nopeutta: R_{T,h+1}(D) \geq R_{T,h}(D).
4. Siis R_\nu(D) := \lim_{T,h \to \infty} R_{T,h}(D) on olemassa.

Koska R_{T,h}(D) \ge E_{T,h}(\nu) - D pätee jokaisessa äärellisessä vaiheessa, ja molemmat puolet konvergoivat monotonisesti, alaraja siirtyy raja-arvoon:

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

Tämä on äärettömän horisontin alaraja, johon vedotaan alla olevissa propositioissa T-1a ja T-1c. Huomautus: Prosesseille, joilla E_\nu = +\infty (esim. korkean kertaluvun de Bruijnin syklit, kun k \to \infty), alaraja toteutuu triviaalisti; tällaiset prosessit suljetaan pois havaitsijayhteensopivasta joukosta O_{C_{\max},D_{\min}} kaikilla äärellisillä C_{\max}-arvoilla.

3.2 M:n ositus Stabiilisuussuodattimen avulla — Propositio T-1a

Propositio T-1a (ei-triviaali ositus).
Kiinnitetään empiiriset C_{\max}>0, \Delta t>0 ja D_{\min}\ge0. Määritellään O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Tällöin sekä O_{C_{\max},D_{\min}} että sen komplementti ovat epätyhjiä.

Todistus. Vakioinen prosessi kuuluu joukkoon O_{C_{\max},D_{\min}}, koska sillä on E_\nu=0 ja R_\nu(D)=0.
Komplementin osalta valitaan binäärinen de Bruijn -sykliprosessi kertalukua k: stationaarinen ergodinen binääriprosessi, jonka periodi on 2^k ja jolla on tasainen vaihejakautuma, jossa jokainen pituuden k sana esiintyy täsmälleen kerran sykliä kohti. Tälle prosessille E_\nu=C_{\mu,\nu}=k. Siispä R_\nu(D_{\min})\ge k-D_{\min}. Valitsemalla k>C_{\max}\Delta t + D_{\min} saadaan R_\nu(D_{\min})>C_{\max}\Delta t, joten \nu\notin O_{C_{\max},D_{\min}}. \square

3.3 C_{\max}:n määritelmä/karakterisointi — T-1b

Määritelmä T-1b (empiirinen kaistanleveysparametri).
C_{\max} otetaan empiiriseksi tietoisen pääsyn kaistanleveysparametriksi, joka on rate-distortion-formalismin ulkopuolinen. Annetulla C_{\max}:lla määritellään havaitsijayhteensopiva luokka O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Jos halutaan tiivistää erikseen määritelty viiteluokka \mathcal{O}_{ref}, määritellään C^{ref}_{max}:=\frac{1}{\Delta t}\sup_{\nu\in\mathcal{O}_{ref}}R_\nu(D_{\min}). Tämä on valitun luokan yhteenvetotunnusluku, ei itse luokan määritelmä.

3.4 Ei-emergenssin este — todistushahmotelma T-1c

Todistushahmotelma T-1c (ei äärellistä universaalia ylärajaa pelkästä \xi:stä).
Solomonoffin universaali puolimitta \xi antaa positiivisen prioritodennäköisyyspainon jokaiselle laskettavalle mitalle \nu\in\mathcal M. Luokka \mathcal M sisältää stationaarisia ergodisia binaariprosesseja, joilla on mielivaltaisen suuri ylimääräisentropia E_\nu (esimerkiksi yllä oleva de Bruijnin perhe). Koska R_\nu(D_{\min})\ge E_\nu-D_{\min}, ei ole olemassa mitään äärellistä, koko tuen kattavaa ylärajaa suureelle R_\nu(D_{\min}), joka olisi johdettavissa pelkästä \xi:stä. Mikä tahansa äärellinen C_{\max} edellyttää siis paljaan Solomonoff-priorin lisäksi lisäempiiristä syötettä tai luokkaa rajoittavaa oletusta. \square

§4. Yhteys Solomonoffin metaprioriin

§1:n nelikko ja §2:n R(D)-johdanto esitetään mittakohtaisesti \nu:lle. Solomonoff-yhteys — se, miten metapriori \xi painottaa havaitsijan kanssa yhteensopivia virtoja — on johtamisen sijasta rakenteellinen vastaavuus.

Millä tahansa havaitsijan kanssa yhteensopivalla \nu \in O_{C_{\max},D_{\min}}:lla nopeus-vääristymä-tasapaino varmistaa, että pakattu virta z_{0:T} on Stabiilisuussuodattimen valitsema representaatio. Solomonoffin priori \xi antaa tälle \nu:lle painon w_\nu \approx 2^{-K(\nu)}: yksinkertaisemmat (alemman K:n) havaitsijan kanssa yhteensopivat prosessit ovat \xi:n alla eksponentiaalisesti todennäköisempiä. Tämä on niukkuusargumentin (Liite T-4) formaali ilmaus: Stabiilisuussuodatin, joka toimii \xi:n päällä, valitsee yksinkertaisimman koodekin, joka mahtuu kaistanleveyden rajoihin.

T-4b:n dominanssiraja pätee suoraan: mille tahansa laskettavalle fysiikan mitalle \nu, jolle K(\nu) < \infty:

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

Tämä varmistaa, ettei OPT:n metapriori \xi koskaan anna havaitsijan kanssa yhteensopiville virroille pienempää todennäköisyyttä kuin mikään kiinteä laskettava fysiikan malli, paitsi mallin oman kuvauspituuden K(\nu) verran.

§5. Elämyksellinen bittikvantti h^\ast (E-1:n ennakkokatsaus)

Annetulla empiirisellä valinnalla C_{\max} ja empiirisellä tietoisen päivityksen aikaikkunalla \Delta t määritellään h^*:=C_{\max}\Delta t. Kun C_{\max}\approx 10 bittiä/s ja \Delta t\in[50,80] ms, h^*\approx 0.5\text{–}0.8 bittiä tietoista hetkeä kohti.

Mikä tahansa stationaarinen ergodinen prosessi \nu \in \mathcal{M}, joka toteuttaa ehdon E_{T,h}(\nu) - D_{\min} > h^\ast, laukaisee sääntöjen mukaan Narratiivisen hajoamisen. Tämä johtuu siitä, että R_{T,h}(D_{\min}) \ge E_{T,h} - D_{\min} > h^\ast = C_{\max} \Delta t, mikä rikkoo eksplisiittisesti yhteensopivuuskriteeriä. Tämä on kuitenkin romahdukselle riittävä ehto, ei aidosti välttämätön: koska alaraja on harvoin tiukka (R_{T,h} > E_{T,h} - D_{\min} yleisesti §2.4:n mukaan), prosessit voivat ajautua Narratiiviseen hajoamiseen myös silloin, kun E_{T,h} - D_{\min} \le h^\ast. Tämä antaa kvantitatiivisen ennusteen E-1:lle; herkkyyttä valinnalle \Delta t \in [40, 300] ms käsitellään E-1-liitteessä.

§6. Päätösyhteenveto

T-1:n tuotokset — tarkistettu tila

1. Nelikko on määritelty äärellisen horisontin prediktiivisessä asetelmassa.
2. Prediktiivinen KL-identiteetti johdetaan oikein.
3. Yleinen teoreema R(D)=C_\mu-D korvataan oikealla alarajalla R_{T,h}(D)\ge E_{T,h}-D sekä täsmällisellä yhtäsuuruuskriteerillä I(X;Z\mid Y)=0.
4. Nolladistorsion koodaus karakterisoidaan minimaalisella riittävällä tilastolla S_h, ja täydellisessä kausaalitilan rajassa R(0)=C_{\mu,\nu}.
5. C_{\max} käsitellään empiirisenä, ei sisäisesti johdettuna.
6. h^*=C_{\max}\Delta t on empiirinen parametrisaatio, ei §2:sta seuraava teoreema.

Tätä liitettä ylläpidetään osana OPT-projektin repositoriota theoretical_roadmap.pdf:n rinnalla.