Sutvarkyto patch teorija

Pradinė užduotis T-1: Stabilumo filtras — pilna greičio ir iškraipymo specifikacija Problema: Shannono greičio ir iškraipymo teorija reikalauja: šaltinio X, atkūrimo abėcėlės ir iškraipymo funkcijos d(x, \hat{x}). Preprinte remiamasi R_{pred}(D), tačiau šie trys elementai OPT substratui nėra apibrėžti. Pateiktinas rezultatas: pilna OPT greičio ir iškraipymo uždavinio specifikacija (\mathcal{X}, \hat{\mathcal{X}}, P_X, d).

Šioje redakcijoje atskiriama perteklinė entropija nuo statistinio kompleksiškumo, įrodoma predikcinė-KL tapatybė baigtiniame horizonte, įrodoma bendroji apatinė riba R_{T,h}(D)\ge E_{T,h}-D ir suformuluojamas tikslus lygybės kriterijus atvejui, kai ši apatinė riba pasiekiama. C_{\max} išlieka empirinis parametras, o ne dydis, išvedamas iš greičio ir iškraipymo formalizmo.
Užbaigtumo būsena: IŠ DALIES IŠSPRĘSTA. Nustatyta ketverto specifikacija, predikcinė-KL tapatybė ir bendroji apatinė riba R_{T,h}(D) \geq E_{T,h}(\nu) - D kartu su tiksliu lygybės kriterijumi. Ankstesnis bendrinis uždaros formos teiginys R(D) = C_\mu - D buvo atšauktas; teisingas rezultatas yra apatinė riba. C_{\max} išlieka empirinis parametras, o ne dydis, išvedamas iš greičio ir iškraipymo formalizmo.

§0. Formulavimo lygmuo

Darbinė formuluotė. Fiksuokime T,h<\infty. Tegul X:=X_{1:T} žymi praeities bloką, o Y:=X_{T+1:T+h} — būsimojo žvilgsnio į priekį bloką, esant fiksuotam apskaičiuojamam stacionariam ergodiniam matui \nu\in\mathcal M. Apibrėžkime baigtinio horizonto predikcinę informaciją E_{T,h}(\nu):=I(X;Y). Kai egzistuoja begalinio horizonto riba, apibrėžkime perteklinę entropiją E_\nu := I(\overleftarrow X;\overrightarrow X). Jei S žymi pilną \epsilon-mašinos priežastinę būseną, apibrėžkime statistinį kompleksiškumą C_{\mu,\nu}:=H(S). Tai yra skirtingi dydžiai. Šiame priede baigtinio horizonto greičio ir iškraipymo uždavinys formuluojamas remiantis E_{T,h}, o ne C_{\mu,\nu}. Solomonoffo matas \xi čia įtraukiamas tik kaip meta-priorinis svėrimas (preprinto 1 lygtis): individualios R(D) kreivės skaičiuojamos kiekvienam matui \nu. Rezultatai, kuriems reikalingas pilnas mišinys \xi, pateikiami atskirai.

§1. Pilna ketverto specifikacija

1.1 Šaltinis X ir skirstinys P_X

Fiksuokime apskaičiuojamą stacionarų ergodinį matą \nu \in \mathcal{M} ant \{0,1\}^\infty. Šaltinis yra procesas (X_t)_{t \ge 1}, paskirstytas pagal \nu. Meta-prioro vaidmeniui \xi iš preprinto lygties (1) kiekvieną tokį \nu pasveria svoriu w_\nu \approx 2^{-K(\nu)}. Rašome P_X = \nu fiksuotam \mathcal{M} nariui. Visi toliau pateikti rezultatai taikomi kiekvienam matui \nu; Solomonoffo sąsaja įvedama per dominavimo ribą §4.

1.2 Reprodukcijos abėcėlė \hat{X}

Esant fiksuotiems T,h, apibrėžkime baigtinio horizonto predikcinio ekvivalentiškumo sąryšį praeities blokams: x \sim_h x' \iff \nu(Y\in A\mid X=x)=\nu(Y\in A\mid X=x') \quad\text{visoms išmatuojamoms }A\subseteq\{0,1\}^h. Tegu S_h yra X ekvivalentiškumo klasė pagal \sim_h. Tuomet S_h yra minimali pakankamoji statistika, skirta prognozuoti Y iš X horizonte h.

Pilnoji \epsilon-mašinos priežastinė būsena S yra begalinio horizonto objektas, gaunamas pereinant prie pusiau begalinių praeičių ir pilnos ateities. Šiame priede baigtinio horizonto išvedimams naudojamas S_h, o S paliekamas pilnos priežastinės būsenos ribai.

Skaičiuojamumo statusas. Bendruoju skaičiuojamos \nu atveju šiame priede neteigiama, kad predikcinės būsenos skaidinys yra tiksliai skaičiuojamas. Jis traktuojamas kaip idealizuotas išmatuojamas objektas. Tikslus skaičiuojamumas teigiamas tik aiškiai identifikuotoms poklasėms, tokioms kaip baigtinės atminties procesai.

1.3 Iškraipymo funkcija d_h(x, z)

Iškraipymo funkcija yra KL predikcinė divergencija: d_h(x,z):=D_{\mathrm{KL}}\!\big(P_\nu(Y\mid X=x)\,\|\,P_\nu(Y\mid Z=z)\big). Čia Z yra reprezentacijos kintamasis, sukurtas koduoklio p(z\mid x). Kai Z=S_h, tai yra tikslus predikcinės būsenos iškraipymas; kai Z yra grubinimas arba stochastinis kodas, P_\nu(Y\mid Z=z) yra indukuotas predikcinis dėsnis.

Pilnas ketvertas

§2. R_{T,h}(D) išvedimas pagal ketvertą

Spartos-iškraipymo funkcija §1 apibrėžtam ketvertui yra:

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

2.1 KL iškraipymo tapatybė

Tegu X:=X_{1:T}, Y:=X_{T+1:T+h}, o Z tebūna bet kuri reprezentacija, sukurta koduoklio p(z\mid x). Kadangi Z-X-Y yra Markovo grandinė, \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). Lygiaverčiai, \mathbb E[d_h(X,Z)] = I(X;Y)-I(Z;Y)=E_{T,h}(\nu)-I(Z;Y). Todėl iškraipymo apribojimas \mathbb E[d_h(X,Z)]\le D yra ekvivalentiškas I(Z;Y)\ge E_{T,h}(\nu)-D.

2.2 Informacijos butelio kaklelio performulavimas

Iškraipymo apribojimas susiaurina leistinų koduotojų erdvę iki tų, kurie tenkina \mathbb{E}[d_h(X,Z)] \le D. Tai tiksliai atitinka apatinį I(Z;Y) apribojimą, taip gaunant apribotą Informacijos butelio kaklelio uždavinį. Kadangi pasiekiamoji sritis \{(I(Z;Y), I(X;Z))\} pagal standartinius laiko dalijimo argumentus yra iškili, galioja stiprus dualumas. Tai leidžia tiksliai performuluoti uždavinį naudojant Informacijos butelio kaklelio Lagranžianą (Tishby, Pereira & Bialek 1999 [28]): \mathcal{L}[p(z|x)] = I(X ; Z) - \beta \cdot I(Z ; Y) kur Lagranžo daugiklis \beta nustatomas pagal D. IB Lagranžianas apibrėžia Pareto ribą tarp glaudinimo spartos ir predikcinio tikslumo.

2.3 Pagrindinė teorema: bendroji apatinė riba ir lygybės kriterijus

Nustatome greičio–iškraipymo funkcijos ribą:

Teiginys (bendroji apatinė riba ir lygybės kriterijus).
Bet kuriam koduotojui p(z\mid x), tegu D:=\mathbb E[d_h(X,Z)]. Tada I(X;Z)=E_{T,h}(\nu)-D+I(X;Z\mid Y). Vadinasi, R_{T,h}(D)\ge E_{T,h}(\nu)-D. Kompaktiškoms baigtinėms atkūrimo alfabetų aibėms, kai tęstinumas garantuoja, kad infimumas pagal koduotojus yra pasiekiamas, lygybė esant duotajam iškraipymui D galioja tada ir tik tada, kai egzistuoja koduotojas, pasiekiantis tą iškraipymą ir tenkinantis I(X;Z\mid Y)=0. Deterministiniams koduotojams Z=g(X) tai ekvivalentiška sąlygai H(Z\mid Y)=0.

Esant nuliniam iškraipymui, minimalioji pakankamoji statistika S_h pasiekia R_{T,h}(0)=I(X;S_h)=H(S_h). Atkreipkite dėmesį, kad šis nulinio iškraipymo dažnis H(S_h) apskritai yra griežtai didesnis už apatinę ribą E_{T,h}. Skirtumas yra neneigiamas tarpas H(S_h) - E_{T,h} = H(S_h|Y). Fizikine prasme šis tarpas reiškia struktūrinę praeityje „saugomą informaciją“, kurios vien ateities langas nesugeba atkurti. Lygybė esant nuliniam iškraipymui (H(S_h|Y)=0) yra labai degeneruotas atvejis, kuris sudėtingiems procesams paprastai nėra teisingas.

Pilno priežastinių būsenų limito atveju, R(0)=C_{\mu,\nu}=H(S). Tai sutampa su E_\nu tik ypatingais atvejais; apskritai E_\nu < C_{\mu,\nu}.

2.4 Elgsena stambesnėms reprodukcijos abėcėlėms

Bet kuriam deterministiniam stambinimui 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. Neneigiamas laisvės narys I(X;Z\mid Y) išnyksta tik tada, kai sustambintas atvaizdavimas yra atkuriamas iš ateities lango Y. Todėl stambesnės abėcėlės paprastai sukuria greičio–iškraipymo kreives, esančias griežtai virš tiesės E_{T,h}-D. Ši tiesė yra universali apatinė riba, o ne bendrinis pasiekiamas apvalkalas. Bet kuris praktiškai apskaičiuojamas kodekas naudoja baigtinės atminties aproksimaciją priežastinėms būsenoms, todėl jo kreivė yra virš šios ribos.

2.5 Ribiniai įverčiai

(Pastaba: begalinio horizonto riboje nulinio dažnio taškas yra ties iškraipymu E_\nu, o ne ties C_{\mu,\nu})

§3. C_{\max} — Charakterizacija ir barjerai

3.1 Begalinio horizonto konvergencijos lema

Pagrindinė teorema (§2.3) nustato apatinę ribą R_{T,h}(D) \ge E_{T,h}(\nu) - D baigtiniams (T, h). Dabar parodysime, kad tai išsiplečia į begalinio horizonto atvejį.

Lema (begalinio horizonto išplėtimas). Tegul \nu yra stacionarus ergodinis matas ant \{0,1\}^\infty. Tada:

1. E_{T,h}(\nu) = I(X_{1:T}\,;\,X_{T+1:T+h}) yra nemažėjantis tiek pagal T, tiek pagal h (pagal duomenų apdorojimo nelygybę: sąlygojimas ilgesniais blokais negali sumažinti tarpusavio informacijos tarp praeities ir ateities esant stacionarumui).
2. Riba E_\nu := \lim_{T,h \to \infty} E_{T,h}(\nu) egzistuoja (galbūt +\infty) pagal monotonišką konvergenciją.
3. Kiekvienam fiksuotam D \ge 0, seka R_{T,h}(D) yra nemažėjanti pagal T (ilgesnės praeitys negali sumažinti optimalaus glaudinimo dažnio) ir nemažėjanti pagal h. Monotoniškumo pagal h įrodymo eskizas: iškraipymo funkcija išsiskaido kaip d_{h+1}(x, z) = D_{\mathrm{KL}}\!\left(P_\nu(\cdot \mid x) \,\|\, P_z(\cdot \mid z)\right) per h+1 būsimų žingsnių, ir pagal grandinės taisyklę gali būti užrašyta kaip 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). Kadangi antrasis narys yra neneigiamas, taigi taškiniu požiūriu d_{h+1} \geq d_h. Todėl apribojimų aibė \{P(z|x) : E[d_{h+1}] \leq D\} \subseteq \{P(z|x) : E[d_h] \leq D\}, o minimizavimas mažesnėje leistinų sprendinių aibėje negali sumažinti dažnio: R_{T,h+1}(D) \geq R_{T,h}(D).
4. Todėl R_\nu(D) := \lim_{T,h \to \infty} R_{T,h}(D) egzistuoja.

Kadangi R_{T,h}(D) \ge E_{T,h}(\nu) - D galioja kiekviename baigtiniame etape, o abi pusės konverguoja monotoniškai, riba persikelia į limitą:

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

Tai yra begalinio horizonto apatinė riba, kuria remiamasi toliau pateiktose Propozicijose T-1a ir T-1c. Pastaba: procesams, kuriems E_\nu = +\infty (pvz., aukštos eilės de Bruijno ciklams, kai k \to \infty), ši riba tenkinama trivialiai; tokie procesai neįtraukiami į su stebėtoju suderinamą aibę O_{C_{\max},D_{\min}} jokiam baigtiniam C_{\max}.

3.2 M skaidinys pagal Stabilumo filtrą — Teiginys T-1a

Teiginys T-1a (netrivialus skaidinys).
Fiksuokime empirinius C_{\max}>0, \Delta t>0 ir D_{\min}\ge0. Apibrėžkime O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Tuomet ir O_{C_{\max},D_{\min}}, ir jo papildinys yra netuščios aibės.

Įrodymas. Pastovusis procesas priklauso O_{C_{\max},D_{\min}}, nes jam galioja E_\nu=0 ir R_\nu(D)=0.
Papildiniui pasirinkime dvejetainį de Bruijno ciklo procesą eilės k: stacionarų ergodinį dvejetainį procesą, kurio periodas yra 2^k ir kurio fazė tolydiškai pasiskirsčiusi, o kiekvienas ilgio k žodis cikle pasirodo tiksliai vieną kartą. Šiam procesui E_\nu=C_{\mu,\nu}=k. Todėl R_\nu(D_{\min})\ge k-D_{\min}. Pasirinkus k>C_{\max}\Delta t + D_{\min}, gauname R_\nu(D_{\min})>C_{\max}\Delta t, taigi \nu\notin O_{C_{\max},D_{\min}}. \square

3.3 C_{\max} apibrėžimas / charakterizacija — T-1b

Apibrėžimas T-1b (empirinis sąmoningos prieigos pralaidumo parametras).
C_{\max} laikomas empiriniu sąmoningos prieigos pralaidumo parametru, išoriniu greičio–iškraipos formalizmui. Esant C_{\max}, apibrėžiama su stebėtoju suderinama klasė O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Jei norima apibendrinti atskirai nurodytą etaloninę klasę \mathcal{O}_{ref}, apibrėžiama C^{ref}_{max}:=\frac{1}{\Delta t}\sup_{\nu\in\mathcal{O}_{ref}}R_\nu(D_{\min}). Tai yra pasirinktos klasės apibendrinamoji statistika, o ne pačios klasės apibrėžimas.

3.4 Neiškilimo barjeras — įrodymo eskizas T-1c

Įrodymo eskizas T-1c (jokios baigtinės universalios ribos vien iš \xi).
Solomonoffo universalus pusmatis \xi kiekvienam apskaičiuojamam matui \nu\in\mathcal M priskiria teigiamą apriorinį svorį. Klasė \mathcal M apima stacionarius ergodinius dvejetainius procesus su savavališkai didele perteklinės entropijos verte E_\nu (pavyzdžiui, aukščiau pateiktą de Bruijno šeimą). Kadangi R_\nu(D_{\min})\ge E_\nu-D_{\min}, iš vien \xi neįmanoma išvesti jokios baigtinės visą atramą apimančios viršutinės ribos R_\nu(D_{\min}) atžvilgiu. Todėl bet kuri baigtinė C_{\max} reikšmė reikalauja papildomos empirinės informacijos arba klasę apribojančių prielaidų, peržengiančių grynąjį Solomonoffo apriorą. \square

§4. Ryšys su Solomonoffo meta-prioru

§1 ketvertas ir §2 pateikta R(D) išvestis formuluojami kiekvienam matui \nu. Solomonoffo ryšys — tai, kaip meta-prioras \xi suteikia svorius su stebėtoju suderinamiems srautams, — yra struktūrinė atitiktis, o ne išvestis.

Bet kuriam su stebėtoju suderinamam \nu \in O_{C_{\max},D_{\min}}, dažnio ir iškraipymo pusiausvyra užtikrina, kad suglaudintas srautas z_{0:T} yra Stabilumo filtro parinktas atvaizdavimas. Solomonoffo prioras \xi šiam \nu priskiria svorį w_\nu \approx 2^{-K(\nu)}: paprastesni (mažesnio K) su stebėtoju suderinami procesai pagal \xi yra eksponentiškai labiau tikėtini. Tai yra formalioji parsimoniškumo argumento (Priedas T-4) išraiška: Stabilumo filtras, veikdamas su \xi, parenka paprasčiausią kodeką, kuris telpa į pralaidumą.

Dominavimo riba iš T-4b taikoma tiesiogiai: bet kuriam apskaičiuojamam fizikos matui \nu, kuriam K(\nu) < \infty:

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

Tai užtikrina, kad OPT meta-prioras \xi su stebėtoju suderinamiems srautams niekada nepriskiria mažesnės tikimybės nei bet kuris fiksuotas apskaičiuojamas fizikos modelis, iki paties modelio aprašo ilgio K(\nu) tikslumo.

§5. Patyriminis bito kvantas h^\ast (E-1 peržiūra)

Pasirinkus empirinę C_{\max} reikšmę ir empirinį sąmoningo atnaujinimo langą \Delta t, apibrėžiame h^*:=C_{\max}\Delta t. Kai C_{\max}\approx 10 bitų/s ir \Delta t\in[50,80] ms, h^*\approx 0.5\text{–}0.8 bito vienam sąmoningam momentui.

Bet kuris stacionarus ergodinis procesas \nu \in \mathcal{M}, tenkinantis sąlygą E_{T,h}(\nu) - D_{\min} > h^\ast, teisėtai sužadins Naratyvo irimą. Taip yra todėl, kad R_{T,h}(D_{\min}) \ge E_{T,h} - D_{\min} > h^\ast = C_{\max} \Delta t, ir tai aiškiai pažeidžia suderinamumo kriterijų. Tačiau tai yra pakankama kolapso sąlyga, o ne griežtai būtina: kadangi apatinė riba retai būna tiksli (R_{T,h} > E_{T,h} - D_{\min} bendruoju atveju pagal §2.4), procesai gali patirti Naratyvo irimą net tada, kai E_{T,h} - D_{\min} \le h^\ast. Tai pateikia kiekybinę E-1 prognozę; jautrumas pasirinkimui \Delta t \in [40, 300] ms aptariamas E-1 priede.

§6. Užbaigimo santrauka

T-1 rezultatai — patikslinta būsena

1. Ketvertas yra apibrėžtas baigtinio horizonto predikcinėje aplinkoje.
2. Predikcinio-KL tapatybė išvedama korektiškai.
3. Bendroji teorema R(D)=C_\mu-D pakeičiama teisinga apatine riba R_{T,h}(D)\ge E_{T,h}-D kartu su tiksliu lygybės kriterijumi I(X;Z\mid Y)=0.
4. Nulinio iškraipymo kodavimas apibūdinamas minimaliąja pakankamąja statistika S_h, o pilnos priežastinės būsenos riboje R(0)=C_{\mu,\nu}.
5. C_{\max} traktuojamas kaip empirinis, o ne išvestas iš vidaus.
6. h^*=C_{\max}\Delta t yra empirinė parametrizacija, o ne §2 teorema.

Šis priedas palaikomas kaip OPT projekto saugyklos dalis greta theoretical_roadmap.pdf.