Teoria del Patch Ordinato

Compito originale T-1: Filtro di Stabilità — Specificazione completa rate-distortion Problema: la teoria rate-distortion di Shannon richiede: una sorgente X, un alfabeto di riproduzione e una funzione di distorsione d(x, \hat{x}). Il preprint richiama R_{pred}(D) senza specificare questi tre elementi per il substrato di OPT. Deliverable: una specificazione completa di (\mathcal{X}, \hat{\mathcal{X}}, P_X, d) per il problema rate-distortion di OPT.

Questa revisione distingue l’entropia in eccesso dalla complessità statistica, dimostra l’identità KL predittiva a orizzonte finito, dimostra il limite inferiore generale R_{T,h}(D)\ge E_{T,h}-D, ed enuncia un criterio esatto di uguaglianza per i casi in cui tale limite inferiore è raggiunto. C_{\max} rimane un parametro empirico piuttosto che una quantità derivata dal formalismo rate-distortion.
Stato di chiusura: PARZIALMENTE RISOLTO. La specificazione della quadrupla, l’identità KL predittiva e il limite inferiore generale R_{T,h}(D) \geq E_{T,h}(\nu) - D sono stabiliti con un criterio esatto di uguaglianza. La precedente affermazione generica in forma chiusa R(D) = C_\mu - D è stata ritirata; il risultato corretto è il limite inferiore. C_{\max} rimane un parametro empirico piuttosto che una quantità derivata dal formalismo rate-distortion.

§0. Livello di formulazione

Formulazione di lavoro. Fissati T,h<\infty. Sia X:=X_{1:T} il blocco passato e Y:=X_{T+1:T+h} il blocco futuro di anticipazione sotto una misura ergodica stazionaria calcolabile fissata \nu\in\mathcal M. Si definisce l’informazione predittiva a orizzonte finito E_{T,h}(\nu):=I(X;Y). Quando esiste il limite a orizzonte infinito, si definisce l’entropia in eccesso E_\nu := I(\overleftarrow X;\overrightarrow X). Se S denota lo stato causale completo della \epsilon-machine, si definisce la complessità statistica C_{\mu,\nu}:=H(S). Si tratta di quantità distinte. Il problema di rate-distortion a orizzonte finito in questa appendice è formulato in termini di E_{T,h}, non di C_{\mu,\nu}. La semimisura universale di Solomonoff \xi interviene solo come pesatura del meta-prior (preprint Eq. 1): le singole curve R(D) sono calcolate per ciascuna misura \nu. I risultati che richiedono la miscela completa \xi sono enunciati separatamente.

§1. La specificazione completa della quaterna

1.1 Sorgente X e distribuzione P_X

Fissiamo una misura ergodica stazionaria calcolabile \nu \in \mathcal{M} su \{0,1\}^\infty. La sorgente è il processo (X_t)_{t \ge 1} distribuito secondo \nu. Per il ruolo di meta-prior, \xi dall’Eq. (1) del preprint pesa ciascuna tale \nu con w_\nu \approx 2^{-K(\nu)}. Scriviamo P_X = \nu per un membro fissato di \mathcal{M}. Tutti i risultati seguenti si applicano misura per misura a \nu; la connessione con Solomonoff entra attraverso il vincolo di dominanza nel §4.

1.2 Alfabeto di Riproduzione \hat{X}

Per T,h fissati, definiamo una relazione di equivalenza predittiva a orizzonte finito sui blocchi passati: x \sim_h x' \iff \nu(Y\in A\mid X=x)=\nu(Y\in A\mid X=x') \quad\text{per ogni insieme misurabile }A\subseteq\{0,1\}^h. Sia S_h la classe di equivalenza di X rispetto a \sim_h. Allora S_h è la statistica sufficiente minimale per predire Y a partire da X all’orizzonte h.

Lo stato causale completo dell’\epsilon-machine, S, è l’oggetto a orizzonte infinito che si ottiene passando a passati semi-infiniti e al futuro completo. Questa appendice usa S_h per le derivazioni a orizzonte finito e riserva S al limite completo dello stato causale.

Stato di calcolabilità. Per una \nu calcolabile generale, questa appendice non rivendica la calcolabilità esatta della partizione degli stati predittivi. Essa viene trattata come un oggetto misurabile idealizzato. La calcolabilità esatta è affermata solo per sottoclassi esplicitamente identificate, come i processi a memoria finita.

1.3 Funzione di distorsione d_h(x, z)

La funzione di distorsione è la divergenza predittiva KL: d_h(x,z):=D_{\mathrm{KL}}\!\big(P_\nu(Y\mid X=x)\,\|\,P_\nu(Y\mid Z=z)\big). Qui Z è una variabile di rappresentazione prodotta da un codificatore p(z\mid x). Quando Z=S_h, questa è l’esatta distorsione dello stato predittivo; quando Z è un raffinamento grossolano o un codice stocastico, P_\nu(Y\mid Z=z) è la legge predittiva indotta.

Quaterna completa

§2. Derivazione di R_{T,h}(D) sotto la quadrupla

La funzione rate-distortion per la quadrupla del §1 è:

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

2.1 L’identità di distorsione KL

Siano X:=X_{1:T}, Y:=X_{T+1:T+h}, e sia Z una qualunque rappresentazione prodotta da un encoder p(z\mid x). Poiché Z-X-Y è una catena di Markov, \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). Equivalentemente, \mathbb E[d_h(X,Z)] = I(X;Y)-I(Z;Y)=E_{T,h}(\nu)-I(Z;Y). Pertanto il vincolo di distorsione \mathbb E[d_h(X,Z)]\le D è equivalente a I(Z;Y)\ge E_{T,h}(\nu)-D.

2.2 La riformulazione dell’Information Bottleneck

Il vincolo di distorsione restringe lo spazio degli encoder ammissibili a quelli che soddisfano \mathbb{E}[d_h(X,Z)] \le D. Ciò corrisponde precisamente a imporre un limite inferiore a I(Z;Y), ottenendo il problema vincolato dell’Information Bottleneck. Poiché la regione realizzabile \{(I(Z;Y), I(X;Z))\} è convessa secondo i consueti argomenti di time-sharing, vale la dualità forte. Questo consente una riformulazione esatta mediante la lagrangiana dell’Information Bottleneck (Tishby, Pereira & Bialek 1999 [28]): \mathcal{L}[p(z|x)] = I(X ; Z) - \beta \cdot I(Z ; Y) con il moltiplicatore di Lagrange \beta determinato da D. La lagrangiana IB traccia la frontiera di Pareto tra tasso di compressione e fedeltà predittiva.

2.3 Teorema principale: limite inferiore generale e criterio di uguaglianza

Stabiliamo il vincolo per la funzione rate-distortion:

Proposizione (limite inferiore generale e criterio di uguaglianza).
Per qualunque codificatore p(z\mid x), sia D:=\mathbb E[d_h(X,Z)]. Allora I(X;Z)=E_{T,h}(\nu)-D+I(X;Z\mid Y). Di conseguenza, R_{T,h}(D)\ge E_{T,h}(\nu)-D. Per alfabeti di riproduzione finiti e compatti, nei quali la continuità garantisce che l’infimum sui codificatori sia raggiunto, l’uguaglianza a una data distorsione D vale se e solo se esiste un codificatore che realizza tale distorsione con I(X;Z\mid Y)=0. Per codificatori deterministici Z=g(X), ciò è equivalente a H(Z\mid Y)=0.

A distorsione zero, la statistica sufficiente minimale S_h realizza R_{T,h}(0)=I(X;S_h)=H(S_h). Si noti che questo tasso a distorsione zero H(S_h) si colloca in generale strettamente al di sopra del limite inferiore E_{T,h}. La differenza è il divario non negativo H(S_h) - E_{T,h} = H(S_h|Y). Questo divario rappresenta fisicamente l’‘informazione immagazzinata’ strutturale nel passato che la sola finestra futura non riesce a recuperare. L’uguaglianza a distorsione zero (H(S_h|Y)=0) è un caso altamente degenere, genericamente falso per processi complessi.

Nel limite completo degli stati causali, R(0)=C_{\mu,\nu}=H(S). Questo è uguale a E_\nu solo in casi speciali; in generale E_\nu < C_{\mu,\nu}.

2.4 Comportamento per alfabeti di riproduzione più grossolani

Per qualunque grossolanizzazione deterministica 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. Il termine di slack non negativo I(X;Z\mid Y) si annulla solo quando la rappresentazione grossolanizzata è recuperabile dalla finestra futura Y. Di conseguenza, alfabeti più grossolani producono in generale curve tasso-distorsione strettamente al di sopra della retta E_{T,h}-D. La retta è un limite inferiore universale, non un inviluppo genericamente raggiunto. Qualsiasi codec praticamente calcolabile utilizza un’approssimazione a memoria finita degli stati causali e presenta pertanto una curva al di sopra di questo limite.

2.5 Valutazioni ai Limiti

(Nota: nel limite di orizzonte infinito, il punto a tasso zero si trova alla distorsione E_\nu, non a C_{\mu,\nu})

§3. C_{\max} — Caratterizzazione e barriere

3.1 Lemma di Convergenza all’Orizzonte Infinito

Il teorema principale (§2.3) stabilisce il limite inferiore R_{T,h}(D) \ge E_{T,h}(\nu) - D per (T, h) finiti. Mostriamo ora che questo si estende al caso a orizzonte infinito.

Lemma (estensione all’orizzonte infinito). Sia \nu una misura ergodica stazionaria su \{0,1\}^\infty. Allora:

1. E_{T,h}(\nu) = I(X_{1:T}\,;\,X_{T+1:T+h}) è non decrescente sia in T sia in h (per la disuguaglianza di elaborazione dei dati: condizionare su blocchi più lunghi non può diminuire l’informazione mutua tra passato e futuro sotto stazionarietà).
2. Il limite E_\nu := \lim_{T,h \to \infty} E_{T,h}(\nu) esiste (eventualmente +\infty) per convergenza monotona.
3. Per ogni D \ge 0 fissato, la successione R_{T,h}(D) è non decrescente in T (passati più lunghi non possono ridurre il tasso di compressione ottimale) e non decrescente in h. Schizzo della dimostrazione della monotonicità in h: La funzione di distorsione si decompone come d_{h+1}(x, z) = D_{\mathrm{KL}}\!\left(P_\nu(\cdot \mid x) \,\|\, P_z(\cdot \mid z)\right) su h+1 passi futuri, e può essere scritta, tramite la regola della catena, come 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). Poiché il secondo termine è non negativo, d_{h+1} \geq d_h puntualmente. Pertanto l’insieme dei vincoli \{P(z|x) : E[d_{h+1}] \leq D\} \subseteq \{P(z|x) : E[d_h] \leq D\}, e minimizzare su un insieme ammissibile più piccolo non può diminuire il tasso: R_{T,h+1}(D) \geq R_{T,h}(D).
4. Quindi R_\nu(D) := \lim_{T,h \to \infty} R_{T,h}(D) esiste.

Poiché R_{T,h}(D) \ge E_{T,h}(\nu) - D vale a ogni stadio finito, e poiché entrambi i lati convergono monotonicamente, il limite inferiore passa al limite:

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

Questo è il limite inferiore all’orizzonte infinito richiamato nelle Proposizioni T-1a e T-1c qui sotto. Nota: Per processi con E_\nu = +\infty (ad esempio, cicli di de Bruijn di ordine elevato quando k \to \infty), il limite inferiore è soddisfatto in modo banale; tali processi sono esclusi dall’insieme compatibile con l’osservatore O_{C_{\max},D_{\min}} per ogni C_{\max} finito.

3.2 Partizione di M mediante il Filtro di Stabilità — Proposizione T-1a

Proposizione T-1a (partizione non banale).
Fissati valori empirici C_{\max}>0, \Delta t>0 e D_{\min}\ge0, si definisca O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Allora sia O_{C_{\max},D_{\min}} sia il suo complemento sono non vuoti.

Dimostrazione. Il processo costante appartiene a O_{C_{\max},D_{\min}} perché ha E_\nu=0 e R_\nu(D)=0.
Per il complemento, si scelga un processo binario a ciclo di de Bruijn di ordine k: un processo binario stazionario ergodico di periodo 2^k con fase uniforme, nel quale ogni parola di lunghezza k compare esattamente una volta per ciclo. Per questo processo, E_\nu=C_{\mu,\nu}=k. Quindi R_\nu(D_{\min})\ge k-D_{\min}. Scegliendo k>C_{\max}\Delta t + D_{\min} si ottiene R_\nu(D_{\min})>C_{\max}\Delta t, dunque \nu\notin O_{C_{\max},D_{\min}}. \square

3.3 Definizione/Caratterizzazione di C_{\max} — T-1b

Definizione T-1b (parametro empirico di larghezza di banda).
C_{\max} è assunto come un parametro empirico della larghezza di banda dell’accesso cosciente, esterno al formalismo rate-distortion. Dato C_{\max}, si definisce la classe compatibile con l’osservatore O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Se si desidera riassumere una classe di riferimento \mathcal{O}_{ref} specificata separatamente, si definisce C^{ref}_{max}:=\frac{1}{\Delta t}\sup_{\nu\in\mathcal{O}_{ref}}R_\nu(D_{\min}). Questa è una statistica riassuntiva di una classe scelta, non la definizione della classe stessa.

3.4 La Barriera della Non-Emergenza — Schizzo della dimostrazione T-1c

Schizzo della dimostrazione T-1c (nessun limite universale finito da \xi soltanto).
La semimisura universale di Solomonoff \xi assegna un peso a priori positivo a ogni misura calcolabile \nu\in\mathcal M. La classe \mathcal M contiene processi binari stazionari ergodici con entropia in eccesso E_\nu arbitrariamente grande (per esempio, la famiglia de Bruijn sopra). Poiché R_\nu(D_{\min})\ge E_\nu-D_{\min}, non esiste alcun limite superiore finito, valido sull’intero supporto, per R_\nu(D_{\min}) derivabile da \xi soltanto. Qualsiasi C_{\max} finito richiede pertanto un apporto empirico aggiuntivo o una restrizione della classe, oltre il mero prior di Solomonoff. \square

§4. Connessione con il Meta-Prior di Solomonoff

La quadrupla del §1 e la derivazione di R(D) del §2 sono formulate per misura \nu. La connessione con Solomonoff — cioè il modo in cui il meta-prior \xi pesa i flussi compatibili con l’osservatore — è una corrispondenza strutturale piuttosto che una derivazione.

Per ogni \nu \in O_{C_{\max},D_{\min}} compatibile con l’osservatore, l’equilibrio rate-distortion garantisce che il flusso compresso z_{0:T} sia la rappresentazione selezionata dal Filtro di Stabilità. Il prior di Solomonoff \xi assegna a questa \nu un peso w_\nu \approx 2^{-K(\nu)}: i processi compatibili con l’osservatore più semplici (con K più basso) sono esponenzialmente più probabili sotto \xi. Questa è l’espressione formale dell’argomento di parsimonia (Appendice T-4): il Filtro di Stabilità, operando su \xi, seleziona il codec più semplice che rientra nella banda disponibile.

Il vincolo di dominanza di T-4b si applica direttamente: per ogni misura fisica computabile \nu con K(\nu) < \infty:

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

Ciò garantisce che il meta-prior OPT \xi non assegni mai ai flussi compatibili con l’osservatore una probabilità inferiore rispetto a qualunque modello fisico computabile fissato, salvo la lunghezza descrittiva del modello stesso K(\nu).

§5. Il Quanto di Bit Esperienziale h^\ast (Anteprima di E-1)

Dato un valore empirico di C_{\max} e una finestra empirica di aggiornamento cosciente \Delta t, si definisce h^*:=C_{\max}\Delta t. Per C_{\max}\approx 10 bit/s e \Delta t\in[50,80] ms, h^*\approx 0.5\text{–}0.8 bit per momento cosciente.

Qualsiasi processo ergodico stazionario \nu \in \mathcal{M} che soddisfi E_{T,h}(\nu) - D_{\min} > h^\ast attiverà legittimamente il Decadimento narrativo. Questo perché R_{T,h}(D_{\min}) \ge E_{T,h} - D_{\min} > h^\ast = C_{\max} \Delta t, violando esplicitamente il criterio di compatibilità. Tuttavia, questa è una condizione sufficiente per il collasso, non una condizione strettamente necessaria: poiché il limite inferiore è raramente stretto (R_{T,h} > E_{T,h} - D_{\min} genericamente secondo §2.4), i processi possono andare incontro a Decadimento narrativo anche quando E_{T,h} - D_{\min} \le h^\ast. Questo fornisce la previsione quantitativa per E-1; la sensibilità alla scelta di \Delta t \in [40, 300] ms è discussa nell’appendice E-1.

§6. Sintesi conclusiva

Risultati di T-1 — Stato rivisto

1. La quaterna è specificata in un contesto predittivo a orizzonte finito.
2. L’identità predittiva-KL è derivata correttamente.
3. Il teorema generico R(D)=C_\mu-D è sostituito dal corretto limite inferiore R_{T,h}(D)\ge E_{T,h}-D insieme a un criterio di uguaglianza esatto I(X;Z\mid Y)=0.
4. La codifica a distorsione zero è caratterizzata dalla statistica sufficiente minima S_h, e nel limite completo degli stati causali R(0)=C_{\mu,\nu}.
5. C_{\max} è trattato come empirico, non derivato internamente.
6. h^*=C_{\max}\Delta t è una parametrizzazione empirica, non un teorema del §2.

Questa appendice è mantenuta come parte del repository del progetto OPT insieme a theoretical_roadmap.pdf.