Teoria uporządkowanego patcha

Oryginalne zadanie T-1: Filtr stabilności — pełna specyfikacja teorii szybkości-zniekształcenia Problem: Teoria szybkości-zniekształcenia Shannona wymaga: źródła X, alfabetu rekonstrukcji oraz funkcji zniekształcenia d(x, \hat{x}). Preprint przywołuje R_{pred}(D) bez określenia tych trzech elementów dla substratu OPT. Rezultat: Pełna specyfikacja (\mathcal{X}, \hat{\mathcal{X}}, P_X, d) dla problemu szybkości-zniekształcenia w OPT.

W tej rewizji odróżnia się entropię nadmiarową od złożoności statystycznej, dowodzi tożsamości predictive-KL przy skończonym horyzoncie, dowodzi ogólnego dolnego ograniczenia R_{T,h}(D)\ge E_{T,h}-D oraz podaje ścisłe kryterium równości określające, kiedy to dolne ograniczenie jest osiągane. C_{\max} pozostaje parametrem empirycznym, a nie wielkością wyprowadzoną z formalizmu teorii szybkości-zniekształcenia.
Status domknięcia: CZĘŚCIOWO ROZWIĄZANE. Ustanowiono specyfikację czwórki, tożsamość predictive-KL oraz ogólne dolne ograniczenie R_{T,h}(D) \geq E_{T,h}(\nu) - D wraz ze ścisłym kryterium równości. Wcześniejsze ogólne twierdzenie o postaci zamkniętej R(D) = C_\mu - D zostało wycofane; poprawnym wynikiem jest dolne ograniczenie. C_{\max} pozostaje parametrem empirycznym, a nie wielkością wyprowadzoną z formalizmu teorii szybkości-zniekształcenia.

§0. Poziom sformułowania

Sformułowanie robocze. Ustalmy T,h<\infty. Niech X:=X_{1:T} oznacza blok przeszły, a Y:=X_{T+1:T+h} — blok przyszłego wyprzedzenia przy ustalonej obliczalnej stacjonarnej ergodycznej mierze \nu\in\mathcal M. Zdefiniujmy informację predykcyjną dla skończonego horyzontu E_{T,h}(\nu):=I(X;Y). Gdy istnieje granica dla nieskończonego horyzontu, definiujemy entropię nadmiarową E_\nu := I(\overleftarrow X;\overrightarrow X). Jeśli S oznacza pełny stan przyczynowy maszyny \epsilon, definiujemy złożoność statystyczną C_{\mu,\nu}:=H(S). Są to wielkości odrębne. Problem szybkości-zniekształcenia dla skończonego horyzontu w niniejszym aneksie jest sformułowany w kategoriach E_{T,h}, a nie C_{\mu,\nu}. Miara Solomonoffa \xi pojawia się wyłącznie jako meta-priorowe ważenie (preprint, równ. 1): poszczególne krzywe R(D) oblicza się osobno dla każdej miary \nu. Wyniki wymagające pełnej mieszaniny \xi podano oddzielnie.

§1. Pełna specyfikacja czwórki uporządkowanej

1.1 Źródło X i rozkład P_X

Ustalmy obliczalną stacjonarną ergodyczną miarę \nu \in \mathcal{M} na \{0,1\}^\infty. Źródłem jest proces (X_t)_{t \ge 1} o rozkładzie zgodnym z \nu. W roli meta-prioru, \xi z równania (1) preprintu waży każdą taką \nu przez w_\nu \approx 2^{-K(\nu)}. Piszemy P_X = \nu dla ustalonego elementu \mathcal{M}. Wszystkie poniższe wyniki stosują się do każdej miary \nu z osobna; związek z Solomonoffem wchodzi poprzez ograniczenie dominacji w §4.

1.2 Alfabet reprodukcji \hat{X}

Dla ustalonych T,h zdefiniujmy relację równoważności predykcyjnej o skończonym horyzoncie na blokach przeszłości: x \sim_h x' \iff \nu(Y\in A\mid X=x)=\nu(Y\in A\mid X=x') \quad\text{dla wszystkich mierzalnych }A\subseteq\{0,1\}^h. Niech S_h będzie klasą równoważności zmiennej X względem \sim_h. Wówczas S_h jest minimalną statystyką dostateczną do przewidywania Y na podstawie X przy horyzoncie h.

Pełny stan przyczynowy \epsilon-maszyny S jest obiektem o nieskończonym horyzoncie, otrzymywanym przy przejściu do półnieskończonych przeszłości i pełnej przyszłości. W niniejszym aneksie używa się S_h dla wyprowadzeń o skończonym horyzoncie, a symbol S rezerwuje się dla pełnej granicy stanu przyczynowego.

Status obliczalności. Dla ogólnej obliczalnej \nu niniejszy aneks nie rości sobie pretensji do ścisłej obliczalności podziału na stany predykcyjne. Traktuje się go jako wyidealizowany obiekt mierzalny. Ścisłą obliczalność stwierdza się wyłącznie dla jawnie wskazanych podklas, takich jak procesy o skończonej pamięci.

1.3 Funkcja zniekształcenia d_h(x, z)

Funkcją zniekształcenia jest predykcyjna dywergencja KL: d_h(x,z):=D_{\mathrm{KL}}\!\big(P_\nu(Y\mid X=x)\,\|\,P_\nu(Y\mid Z=z)\big). Tutaj Z jest zmienną reprezentacji wytwarzaną przez enkoder p(z\mid x). Gdy Z=S_h, jest to dokładne zniekształcenie stanu predykcyjnego; gdy Z jest zgrubieniem lub kodem stochastycznym, P_\nu(Y\mid Z=z) jest indukowanym prawem predykcyjnym.

Pełna czwórka uporządkowana

§2. Wyprowadzenie R_{T,h}(D) w ramach czwórki

Funkcja szybkość-zniekształcenie dla czwórki z §1 ma postać:

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

2.1 Tożsamość zniekształcenia KL

Niech X:=X_{1:T}, Y:=X_{T+1:T+h}, a Z będzie dowolną reprezentacją wytworzoną przez enkoder p(z\mid x). Ponieważ Z-X-Y jest łańcuchem Markowa, \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). Równoważnie, \mathbb E[d_h(X,Z)] = I(X;Y)-I(Z;Y)=E_{T,h}(\nu)-I(Z;Y). Zatem ograniczenie zniekształcenia \mathbb E[d_h(X,Z)]\le D jest równoważne I(Z;Y)\ge E_{T,h}(\nu)-D.

2.2 Reformulacja w kategoriach Information Bottleneck

Ograniczenie zniekształcenia zawęża przestrzeń dopuszczalnych enkoderów do tych, które spełniają warunek \mathbb{E}[d_h(X,Z)] \le D. Odpowiada to dokładnie ograniczeniu dolnemu na I(Z;Y), co daje problem Information Bottleneck z ograniczeniem. Ponieważ obszar osiągalny \{(I(Z;Y), I(X;Z))\} jest wypukły na mocy standardowych argumentów opartych na współdzieleniu czasu, zachodzi silna dualność. Umożliwia to ścisłą reformulację z użyciem lagranżjanu Information Bottleneck (Tishby, Pereira & Bialek 1999 [28]): \mathcal{L}[p(z|x)] = I(X ; Z) - \beta \cdot I(Z ; Y) przy czym mnożnik Lagrange’a \beta jest wyznaczony przez D. Lagranżjan IB wyznacza granicę Pareto między stopniem kompresji a wiernością predykcyjną.

2.3 Twierdzenie główne: ogólne ograniczenie dolne i kryterium równości

Ustalamy ograniczenie dla funkcji szybkość-zniekształcenie:

Propozycja (ogólne ograniczenie dolne i kryterium równości).
Dla dowolnego kodera p(z\mid x) niech D:=\mathbb E[d_h(X,Z)]. Wówczas I(X;Z)=E_{T,h}(\nu)-D+I(X;Z\mid Y). W konsekwencji R_{T,h}(D)\ge E_{T,h}(\nu)-D. Dla zwartych skończonych alfabetów rekonstrukcji, gdzie ciągłość gwarantuje, że infimum po koderach jest osiągane, równość przy danym zniekształceniu D zachodzi wtedy i tylko wtedy, gdy istnieje koder osiągający to zniekształcenie z I(X;Z\mid Y)=0. Dla koderów deterministycznych Z=g(X) jest to równoważne warunkowi H(Z\mid Y)=0.

Przy zerowym zniekształceniu minimalna statystyka wystarczająca S_h osiąga R_{T,h}(0)=I(X;S_h)=H(S_h). Zauważmy, że ta szybkość przy zerowym zniekształceniu H(S_h) leży na ogół ściśle powyżej dolnego ograniczenia E_{T,h}. Różnicę stanowi nieujemna luka H(S_h) - E_{T,h} = H(S_h|Y). Fizycznie luka ta reprezentuje strukturalnie „przechowywaną informację” w przeszłości, której samo okno przyszłości nie potrafi odzyskać. Równość przy zerowym zniekształceniu (H(S_h|Y)=0) jest przypadkiem wysoce zdegenerowanym i dla złożonych procesów jest na ogół fałszywa.

W pełnej granicy stanów przyczynowych R(0)=C_{\mu,\nu}=H(S). Jest to równe E_\nu tylko w szczególnych przypadkach; ogólnie E_\nu < C_{\mu,\nu}.

2.4 Zachowanie dla bardziej zgrubnych alfabetów reprodukcji

Dla każdego deterministycznego zgrubienia 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. Nieujemny składnik luzu I(X;Z\mid Y) zanika wyłącznie wtedy, gdy zgrubiona reprezentacja jest odtwarzalna z przyszłego okna Y. Stąd bardziej zgrubne alfabety na ogół wytwarzają krzywe szybkość-zniekształcenie leżące ściśle powyżej prostej E_{T,h}-D. Ta prosta stanowi uniwersalne ograniczenie dolne, a nie ogólną osiągalną obwiednię. Każdy praktycznie obliczalny kodek wykorzystuje aproksymację stanów przyczynowych o skończonej pamięci i dlatego ma krzywą położoną powyżej tego ograniczenia.

2.5 Oceny graniczne

(Uwaga: W granicy nieskończonego horyzontu punkt zerowej szybkości znajduje się przy zniekształceniu E_\nu, a nie przy C_{\mu,\nu})

§3. C_{\max} — Charakterystyka i bariery

3.1 Lemat zbieżności dla nieskończonego horyzontu

Twierdzenie główne (§2.3) ustanawia dolne ograniczenie R_{T,h}(D) \ge E_{T,h}(\nu) - D dla skończonych (T, h). Pokażemy teraz, że rozszerza się ono na ustawienie nieskończonego horyzontu.

Lemat (rozszerzenie na nieskończony horyzont). Niech \nu będzie stacjonarną ergodyczną miarą na \{0,1\}^\infty. Wówczas:

1. E_{T,h}(\nu) = I(X_{1:T}\,;\,X_{T+1:T+h}) jest niemalejące zarówno względem T, jak i h (na mocy nierówności przetwarzania danych: warunkowanie na dłuższych blokach nie może zmniejszać informacji wzajemnej między przeszłością a przyszłością przy stacjonarności).
2. Granica E_\nu := \lim_{T,h \to \infty} E_{T,h}(\nu) istnieje (być może równa +\infty) na mocy zbieżności monotonicznej.
3. Dla każdego ustalonego D \ge 0 ciąg R_{T,h}(D) jest niemalejący względem T (dłuższe przeszłości nie mogą zmniejszać optymalnej szybkości kompresji) oraz niemalejący względem h. Szkic dowodu monotoniczności względem h: Funkcja zniekształcenia rozkłada się jako d_{h+1}(x, z) = D_{\mathrm{KL}}\!\left(P_\nu(\cdot \mid x) \,\|\, P_z(\cdot \mid z)\right) na przestrzeni h+1 przyszłych kroków, co można zapisać, korzystając z reguły łańcuchowej, jako 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). Ponieważ drugi składnik jest nieujemny, punktowo zachodzi d_{h+1} \geq d_h. Zatem zbiór ograniczeń \{P(z|x) : E[d_{h+1}] \leq D\} \subseteq \{P(z|x) : E[d_h] \leq D\}, a minimalizacja po mniejszym zbiorze dopuszczalnym nie może zmniejszyć szybkości: R_{T,h+1}(D) \geq R_{T,h}(D).
4. W konsekwencji istnieje R_\nu(D) := \lim_{T,h \to \infty} R_{T,h}(D).

Ponieważ R_{T,h}(D) \ge E_{T,h}(\nu) - D zachodzi na każdym skończonym etapie, a obie strony zbiegają monotonicznie, ograniczenie przechodzi do granicy:

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

Jest to dolne ograniczenie dla nieskończonego horyzontu, do którego odwołują się poniżej Propozycje T-1a i T-1c. Uwaga: Dla procesów z E_\nu = +\infty (np. cykli de Bruijna wysokiego rzędu przy k \to \infty) ograniczenie jest spełnione w sposób trywialny; takie procesy są wykluczone ze zbioru zgodnego z obserwatorem O_{C_{\max},D_{\min}} dla każdego skończonego C_{\max}.

3.2 Podział M przez Filtr stabilności — Teza T-1a

Teza T-1a (nietrywialny podział).
Ustalmy empiryczne C_{\max}>0, \Delta t>0 oraz D_{\min}\ge0. Zdefiniujmy O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Wówczas zarówno O_{C_{\max},D_{\min}}, jak i jego dopełnienie są niepuste.

Dowód. Proces stały należy do O_{C_{\max},D_{\min}}, ponieważ ma E_\nu=0 oraz R_\nu(D)=0.
Dla dopełnienia wybierzmy binarny proces cyklu de Bruijna rzędu k: stacjonarny ergodyczny proces binarny o okresie 2^k z jednorodnie rozłożoną fazą, w którym każde słowo długości k pojawia się dokładnie raz na cykl. Dla tego procesu E_\nu=C_{\mu,\nu}=k. Stąd R_\nu(D_{\min})\ge k-D_{\min}. Wybierając k>C_{\max}\Delta t + D_{\min}, otrzymujemy R_\nu(D_{\min})>C_{\max}\Delta t, a więc \nu\notin O_{C_{\max},D_{\min}}. \square

3.3 Definicja/charakterystyka C_{\max} — T-1b

Definicja T-1b (empiryczny parametr przepustowości).
C_{\max} jest przyjmowane jako empiryczny parametr przepustowości dostępu świadomościowego, zewnętrzny wobec formalizmu szybkość-zniekształcenie. Przy danym C_{\max} definiujemy klasę zgodną z obserwatorem O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Jeśli chce się podsumować osobno określoną klasę odniesienia \mathcal{O}_{ref}, definiujemy C^{ref}_{max}:=\frac{1}{\Delta t}\sup_{\nu\in\mathcal{O}_{ref}}R_\nu(D_{\min}). Jest to statystyka podsumowująca wybraną klasę, a nie definicja samej klasy.

3.4 Bariera nie-wyłaniania — szkic dowodu T-1c

Szkic dowodu T-1c (brak skończonego uniwersalnego ograniczenia wynikającego z samej \xi).
Uniwersalna półmiara Solomonoffa \xi przypisuje dodatnią wagę a priori każdej obliczalnej mierze \nu\in\mathcal M. Klasa \mathcal M zawiera stacjonarne ergodyczne procesy binarne o dowolnie dużej entropii nadmiarowej E_\nu (na przykład rodzinę de Bruijna opisaną wyżej). Ponieważ R_\nu(D_{\min})\ge E_\nu-D_{\min}, nie istnieje żadne skończone, globalne dla całego nośnika ograniczenie górne na R_\nu(D_{\min}), które dałoby się wyprowadzić z samej \xi. Każde skończone C_{\max} wymaga zatem dodatkowego wkładu empirycznego albo dodatkowych ograniczeń na klasę, wykraczających poza czysty prior Solomonoffa. \square

§4. Związek z meta-priorem Solomonoffa

Czwórka z §1 oraz wyprowadzenie R(D) z §2 są sformułowane dla każdej miary \nu z osobna. Związek z Solomonoffem — to, w jaki sposób meta-prior \xi waży strumienie zgodne z obserwatorem — ma charakter korespondencji strukturalnej, a nie wyprowadzenia.

Dla dowolnej miary \nu \in O_{C_{\max},D_{\min}} zgodnej z obserwatorem równowaga szybkość-zniekształcenie zapewnia, że skompresowany strumień z_{0:T} jest reprezentacją wybraną przez Filtr stabilności. Prior Solomonoffa \xi przypisuje tej \nu wagę w_\nu \approx 2^{-K(\nu)}: prostsze (o niższym K) procesy zgodne z obserwatorem są pod \xi wykładniczo bardziej prawdopodobne. Jest to formalny wyraz argumentu z oszczędności ontologicznej (Aneks T-4): Filtr stabilności, działając na \xi, wybiera najprostszy kodek mieszczący się w granicach przepustowości.

Ograniczenie dominacji z T-4b stosuje się bezpośrednio: dla dowolnej obliczalnej miary fizycznej \nu o K(\nu) < \infty:

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

Zapewnia to, że meta-prior OPT \xi nigdy nie przypisuje strumieniom zgodnym z obserwatorem niższego prawdopodobieństwa niż jakikolwiek ustalony obliczalny model fizyczny, z dokładnością do własnej długości opisu modelu K(\nu).

§5. Doświadczalny kwant bitowy h^\ast (zapowiedź E-1)

Przy danym empirycznym wyborze C_{\max} oraz empirycznym oknie świadomej aktualizacji \Delta t zdefiniujmy h^*:=C_{\max}\Delta t. Dla C_{\max}\approx 10 bitów/s oraz \Delta t\in[50,80] ms, h^*\approx 0.5\text{–}0.8 bita na świadomy moment.

Każdy stacjonarny proces ergodyczny \nu \in \mathcal{M} spełniający warunek E_{T,h}(\nu) - D_{\min} > h^\ast będzie w sensie formalnym uruchamiał Rozpad narracyjny. Dzieje się tak dlatego, że R_{T,h}(D_{\min}) \ge E_{T,h} - D_{\min} > h^\ast = C_{\max} \Delta t, co wprost narusza kryterium kompatybilności. Jest to jednak warunek wystarczający dla załamania, a nie warunek ściśle konieczny: ponieważ dolne ograniczenie rzadko jest ostre (R_{T,h} > E_{T,h} - D_{\min} jest przypadkiem ogólnym zgodnie z §2.4), procesy mogą ulegać Rozpadowi narracyjnemu nawet wtedy, gdy E_{T,h} - D_{\min} \le h^\ast. Dostarcza to ilościowej predykcji dla E-1; wrażliwość na wybór \Delta t \in [40, 300] ms omówiono w aneksie do E-1.

§6. Podsumowanie zamknięcia

Rezultaty T-1 — Zrewidowany status

1. Czwórka uporządkowana została określona w predykcyjnym ustawieniu o skończonym horyzoncie.
2. Tożsamość predykcyjno-KL została poprawnie wyprowadzona.
3. Ogólne twierdzenie R(D)=C_\mu-D zostaje zastąpione poprawnym ograniczeniem dolnym R_{T,h}(D)\ge E_{T,h}-D wraz z dokładnym kryterium równości I(X;Z\mid Y)=0.
4. Kodowanie o zerowym zniekształceniu zostaje scharakteryzowane przez minimalną statystykę dostateczną S_h, a w granicy pełnego stanu przyczynowego R(0)=C_{\mu,\nu}.
5. C_{\max} jest traktowane jako wielkość empiryczna, a nie wyprowadzana wewnętrznie.
6. h^*=C_{\max}\Delta t jest parametryzacją empiryczną, a nie twierdzeniem z §2.

Ten aneks jest utrzymywany jako część repozytorium projektu OPT obok theoretical_roadmap.pdf.