Теорія впорядкованого патча

Початкове завдання T-1: Фільтр стабільності — повна специфікація теорії швидкості-спотворення Проблема: Теорія швидкості-спотворення Шеннона вимагає: джерела X, алфавіту відтворення та функції спотворення d(x, \hat{x}). У препринті використовується R_{pred}(D) без специфікації цих трьох елементів для субстрату OPT. Результат: Повна специфікація (\mathcal{X}, \hat{\mathcal{X}}, P_X, d) для задачі швидкості-спотворення в OPT.

У цій редакції надлишкова ентропія відрізняється від статистичної складності, доводиться predictive-KL-ідентичність на скінченному горизонті, доводиться загальна нижня межа R_{T,h}(D)\ge E_{T,h}-D, а також формулюється точний критерій рівності для випадку, коли ця нижня межа досягається. C_{\max} залишається емпіричним параметром, а не величиною, виведеною з формалізму швидкості-спотворення.
Статус закриття: ЧАСТКОВО РОЗВ’ЯЗАНО. Специфікацію чотирьох кортежів, predictive-KL-ідентичність і загальну нижню межу R_{T,h}(D) \geq E_{T,h}(\nu) - D встановлено разом із точним критерієм рівності. Попереднє загальне твердження про замкнену форму R(D) = C_\mu - D відкликано; коректним результатом є нижня межа. C_{\max} залишається емпіричним параметром, а не величиною, виведеною з формалізму швидкості-спотворення.

§0. Рівень формулювання

Робоче формулювання. Зафіксуймо T,h<\infty. Нехай X:=X_{1:T} позначає минулий блок, а Y:=X_{T+1:T+h} — блок випереджального погляду в майбутнє за фіксованої обчислюваної стаціонарної ергодичної міри \nu\in\mathcal M. Визначимо предиктивну інформацію на скінченному горизонті E_{T,h}(\nu):=I(X;Y). Коли існує границя на нескінченному горизонті, визначимо надлишкову ентропію E_\nu := I(\overleftarrow X;\overrightarrow X). Якщо S позначає повний каузальний стан \epsilon-машини, визначимо статистичну складність C_{\mu,\nu}:=H(S). Це різні величини. Задачу rate-distortion на скінченному горизонті в цьому додатку сформульовано в термінах E_{T,h}, а не C_{\mu,\nu}. Міра Соломонова \xi входить лише як мета-апріорне зважування (препринт, рівняння 1): окремі криві R(D) обчислюються для кожної міри \nu. Результати, що потребують повної суміші \xi, подано окремо.

§1. Повна специфікація чотирьох кортежів

1.1 Джерело X і розподіл P_X

Зафіксуймо обчислювану стаціонарну ергодичну міру \nu \in \mathcal{M} на \{0,1\}^\infty. Джерелом є процес (X_t)_{t \ge 1}, розподілений згідно з \nu. У ролі мета-апріорного розподілу \xi з рівняння (1) препринту зважує кожну таку \nu коефіцієнтом w_\nu \approx 2^{-K(\nu)}. Для фіксованого елемента \mathcal{M} пишемо P_X = \nu. Усі наведені нижче результати застосовуються помірно до кожної міри \nu; зв’язок із Соломоновим входить через межу домінування в §4.

1.2 Алфавіт відтворення \hat{X}

Для фіксованих T,h визначимо відношення предиктивної еквівалентності на блоках минулого зі скінченним горизонтом: x \sim_h x' \iff \nu(Y\in A\mid X=x)=\nu(Y\in A\mid X=x') \quad\text{для всіх вимірних }A\subseteq\{0,1\}^h. Нехай S_h — це клас еквівалентності X відносно \sim_h. Тоді S_h є мінімальною достатньою статистикою для передбачення Y за X на горизонті h.

Повний каузальний стан \epsilon-машини S — це об’єкт нескінченного горизонту, який отримують при переході до напівнескінченних минулих і повного майбутнього. У цьому додатку для виведень зі скінченним горизонтом використовується S_h, а S зарезервовано для повної границі каузального стану.

Статус обчислюваності. Для загальної обчислюваної \nu цей додаток не стверджує точної обчислюваності розбиття на предиктивні стани. Воно розглядається як ідеалізований вимірний об’єкт. Точна обчислюваність стверджується лише для явно визначених підкласів, таких як процеси зі скінченною пам’яттю.

1.3 Функція спотворення d_h(x, z)

Функція спотворення є KL-предиктивною дивергенцією: d_h(x,z):=D_{\mathrm{KL}}\!\big(P_\nu(Y\mid X=x)\,\|\,P_\nu(Y\mid Z=z)\big). Тут Z — це змінна репрезентації, породжена енкодером p(z\mid x). Коли Z=S_h, це точне спотворення предиктивного стану; коли Z є огрубленням або стохастичним кодом, P_\nu(Y\mid Z=z) є індукованим предиктивним законом.

Повний чотирикортеж

§2. Виведення R_{T,h}(D) для четвірки

Функція швидкість-спотворення для четвірки з §1 має вигляд:

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

2.1 Тотожність KL-спотворення

Нехай X:=X_{1:T}, Y:=X_{T+1:T+h}, а Z — будь-яке представлення, породжене енкодером p(z\mid x). Оскільки Z-X-Y є ланцюгом Маркова, \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). Еквівалентно, \mathbb E[d_h(X,Z)] = I(X;Y)-I(Z;Y)=E_{T,h}(\nu)-I(Z;Y). Отже, обмеження на спотворення \mathbb E[d_h(X,Z)]\le D еквівалентне I(Z;Y)\ge E_{T,h}(\nu)-D.

2.2 Переформулювання Information Bottleneck

Обмеження на спотворення звужує простір допустимих енкодерів до тих, що задовольняють \mathbb{E}[d_h(X,Z)] \le D. Це точно відповідає обмеженню I(Z;Y) знизу, задаючи задачу Information Bottleneck з обмеженнями. Оскільки досяжна область \{(I(Z;Y), I(X;Z))\} є опуклою за стандартних аргументів time-sharing, виконується сильна двоїстість. Це уможливлює точне переформулювання за допомогою лагранжіана Information Bottleneck (Tishby, Pereira & Bialek 1999 [28]): \mathcal{L}[p(z|x)] = I(X ; Z) - \beta \cdot I(Z ; Y) де множник Лагранжа \beta визначається через D. Лагранжіан IB простежує фронт Парето між швидкістю стиснення та предиктивною вірністю.

2.3 Головна теорема: загальна нижня межа та критерій рівності

Ми встановлюємо межу для функції швидкість-спотворення:

Твердження (загальна нижня межа та критерій рівності).
Для будь-якого кодувальника p(z\mid x) покладемо D:=\mathbb E[d_h(X,Z)]. Тоді I(X;Z)=E_{T,h}(\nu)-D+I(X;Z\mid Y). Отже, R_{T,h}(D)\ge E_{T,h}(\nu)-D. Для компактних скінченних алфавітів відтворення, де неперервність гарантує, що інфімум за кодувальниками досягається, рівність при заданому спотворенні D виконується тоді й лише тоді, коли існує кодувальник, що досягає цього спотворення і для якого I(X;Z\mid Y)=0. Для детермінованих кодувальників Z=g(X) це еквівалентно H(Z\mid Y)=0.

При нульовому спотворенні мінімальна достатня статистика S_h досягає R_{T,h}(0)=I(X;S_h)=H(S_h). Зауважимо, що ця швидкість при нульовому спотворенні H(S_h) у загальному випадку лежить строго вище за нижню межу E_{T,h}. Різниця є невід’ємним зазором H(S_h) - E_{T,h} = H(S_h|Y). Фізично цей зазор репрезентує структурну «збережену інформацію» в минулому, яку саме вікно майбутнього не здатне відновити. Виконання рівності при нульовому спотворенні (H(S_h|Y)=0) є сильно виродженим випадком, який для складних процесів, як правило, не має місця.

У повній границі причинних станів R(0)=C_{\mu,\nu}=H(S). Це дорівнює E_\nu лише в особливих випадках; загалом E_\nu < C_{\mu,\nu}.

2.4 Поведінка для грубіших алфавітів відтворення

Для будь-якого детермінованого огрублення 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. Невід’ємний додатковий член I(X;Z\mid Y) зникає лише тоді, коли огрублене представлення можна відновити з майбутнього вікна Y. Отже, грубіші алфавіти загалом породжують криві «швидкість–спотворення», що лежать строго вище за лінію E_{T,h}-D. Ця лінія є універсальною нижньою межею, а не типовою досяжною огинальною. Будь-який практично обчислюваний кодек використовує апроксимацію каузальних станів зі скінченною пам’яттю і тому має криву, розташовану вище за цю межу.

2.5 Граничні оцінки

(Примітка: у границі нескінченного горизонту точка нульової швидкості розташована при спотворенні E_\nu, а не при C_{\mu,\nu})

§3. C_{\max} — Характеризація та бар’єри

3.1 Лема збіжності на нескінченному горизонті

Основна теорема (§2.3) встановлює нижню межу R_{T,h}(D) \ge E_{T,h}(\nu) - D для скінченних (T, h). Тепер покажемо, що це поширюється на випадок нескінченного горизонту.

Лема (розширення на нескінченний горизонт). Нехай \nu — стаціонарна ергодична міра на \{0,1\}^\infty. Тоді:

1. E_{T,h}(\nu) = I(X_{1:T}\,;\,X_{T+1:T+h}) є неспадною за обома параметрами T і h (за нерівністю обробки даних: умовлення на довших блоках не може зменшити взаємну інформацію між минулим і майбутнім за стаціонарності).
2. Границя E_\nu := \lim_{T,h \to \infty} E_{T,h}(\nu) існує (можливо, дорівнює +\infty) за монотонною збіжністю.
3. Для кожного фіксованого D \ge 0 послідовність R_{T,h}(D) є неспадною за T (довші минулі відрізки не можуть зменшити оптимальну швидкість стиснення) і неспадною за h. Нарис доведення монотонності за h: Функція спотворення розкладається як d_{h+1}(x, z) = D_{\mathrm{KL}}\!\left(P_\nu(\cdot \mid x) \,\|\, P_z(\cdot \mid z)\right) на h+1 майбутніх кроках, що за правилом ланцюга можна записати як 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). Оскільки другий доданок є невід’ємним, маємо d_{h+1} \geq d_h поточково. Отже, множина обмежень \{P(z|x) : E[d_{h+1}] \leq D\} \subseteq \{P(z|x) : E[d_h] \leq D\}, а мінімізація на меншій множині допустимих значень не може зменшити швидкість: R_{T,h+1}(D) \geq R_{T,h}(D).
4. Отже, R_\nu(D) := \lim_{T,h \to \infty} R_{T,h}(D) існує.

Оскільки R_{T,h}(D) \ge E_{T,h}(\nu) - D виконується на кожному скінченному етапі, а обидві частини збігаються монотонно, ця межа переходить до границі:

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

Це і є нижня межа на нескінченному горизонті, на яку посилаються в Пропозиціях T-1a і T-1c нижче. Примітка: Для процесів, у яких E_\nu = +\infty (наприклад, для циклів де Брейна високого порядку за k \to \infty), межа виконується тривіально; такі процеси виключаються з множини, сумісної зі спостерігачем, O_{C_{\max},D_{\min}} для будь-якого скінченного C_{\max}.

3.2 Розбиття M Фільтром стабільності — Пропозиція T-1a

Пропозиція T-1a (нетривіальне розбиття).
Зафіксуймо емпіричні C_{\max}>0, \Delta t>0 та D_{\min}\ge0. Визначимо O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Тоді і O_{C_{\max},D_{\min}}, і його доповнення є непорожніми.

Доведення. Константний процес належить до O_{C_{\max},D_{\min}}, оскільки для нього E_\nu=0 і R_\nu(D)=0.
Для доповнення виберімо двійковий процес на циклі де Брейна порядку k: стаціонарний ергодичний двійковий процес періоду 2^k з рівномірною фазою, у якому кожне слово довжини k з’являється рівно один раз за цикл. Для цього процесу E_\nu=C_{\mu,\nu}=k. Отже, R_\nu(D_{\min})\ge k-D_{\min}. Вибір k>C_{\max}\Delta t + D_{\min} дає R_\nu(D_{\min})>C_{\max}\Delta t, тож \nu\notin O_{C_{\max},D_{\min}}. \square

3.3 Визначення/характеристика C_{\max} — T-1b

Визначення T-1b (емпіричний параметр пропускної здатності).
C_{\max} береться як емпіричний параметр пропускної здатності свідомого доступу, зовнішній щодо формалізму швидкість-спотворення. За заданого C_{\max} визначимо клас, сумісний зі спостерігачем: O_{C_{\max},D_{\min}} := \{\nu\in\mathcal M: R_\nu(D_{\min})\le C_{\max}\Delta t\}. Якщо потрібно підсумувати окремо заданий референтний клас \mathcal{O}_{ref}, визначимо C^{ref}_{max}:=\frac{1}{\Delta t}\sup_{\nu\in\mathcal{O}_{ref}}R_\nu(D_{\min}). Це підсумкова статистика вибраного класу, а не визначення самого класу.

3.4 Бар’єр не-емерджентності — ескіз доведення T-1c

Ескіз доведення T-1c (жодної скінченної універсальної межі лише з \xi).
Універсальна семиміра Соломонова \xi надає додатну апріорну вагу кожній обчислюваній мірі \nu\in\mathcal M. Клас \mathcal M містить стаціонарні ергодичні бінарні процеси з довільно великою надлишковою ентропією E_\nu (наприклад, наведене вище сімейство де Брейна). Оскільки R_\nu(D_{\min})\ge E_\nu-D_{\min}, не існує жодної скінченної загальної для всього носія верхньої межі на R_\nu(D_{\min}), яку можна було б вивести лише з \xi. Отже, будь-який скінченний C_{\max} потребує додаткового емпіричного внеску або обмеження класу понад голий соломоновський апріор. \square

§4. Зв’язок із соломоновським мета-апріорі

Чотирикортеж із §1 та виведення R(D) із §2 сформульовано для кожної міри \nu. Зв’язок із Соломоновим — тобто те, як мета-апріорі \xi зважує сумісні зі спостерігачем потоки, — є структурною відповідністю, а не виведенням.

Для будь-якої сумісної зі спостерігачем \nu \in O_{C_{\max},D_{\min}} рівновага швидкості-спотворення гарантує, що стиснений потік z_{0:T} є репрезентацією, відібраною Фільтром стабільності. Апріорі Соломонова \xi надає цій \nu вагу w_\nu \approx 2^{-K(\nu)}: простіші (з нижчим K) сумісні зі спостерігачем процеси є експоненційно ймовірнішими за \xi. Це є формальним вираженням аргументу парсимонії (Додаток T-4): Фільтр стабільності, діючи на \xi, відбирає найпростіший кодек, що вкладається в межі пропускної здатності.

Межа домінування з T-4b застосовується безпосередньо: для будь-якої обчислюваної фізичної міри \nu з K(\nu) < \infty:

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

Це гарантує, що мета-апріорі OPT \xi ніколи не надає сумісним зі спостерігачем потокам нижчої ймовірності, ніж будь-яка фіксована обчислювана фізична модель, з точністю до власної довжини опису моделі K(\nu).

§5. Квант досвідного біта h^\ast (попередній огляд E-1)

Задано емпіричний вибір C_{\max} та емпіричне вікно свідомого оновлення \Delta t, визначимо h^*:=C_{\max}\Delta t. Для C_{\max}\approx 10 біт/с і \Delta t\in[50,80] мс, h^*\approx 0.5\text{–}0.8 біта на один свідомий момент.

Будь-який стаціонарний ергодичний процес \nu \in \mathcal{M}, що задовольняє умову E_{T,h}(\nu) - D_{\min} > h^\ast, правомірно запускатиме Наративний розпад. Це тому, що R_{T,h}(D_{\min}) \ge E_{T,h} - D_{\min} > h^\ast = C_{\max} \Delta t, явно порушуючи критерій сумісності. Однак це достатня умова колапсу, а не строго необхідна: оскільки нижня межа рідко є точною (R_{T,h} > E_{T,h} - D_{\min} загалом, згідно з §2.4), процеси можуть зазнавати Наративного розпаду навіть тоді, коли E_{T,h} - D_{\min} \le h^\ast. Це дає кількісне передбачення для E-1; чутливість до вибору \Delta t \in [40, 300] мс обговорюється в додатку до E-1.

§6. Підсумок завершення

Результати T-1 — переглянутий статус

1. Чотирикортеж задано в умовах предиктивного налаштування зі скінченним горизонтом.
2. Тотожність predictive-KL виведено коректно.
3. Загальну теорему R(D)=C_\mu-D замінено правильньою нижньою межею R_{T,h}(D)\ge E_{T,h}-D разом із точним критерієм рівності I(X;Z\mid Y)=0.
4. Кодування з нульовим спотворенням охарактеризовано через мінімальну достатню статистику S_h, а в повній межі каузального стану R(0)=C_{\mu,\nu}.
5. C_{\max} розглядається як емпіричний, а не внутрішньо виведений.
6. h^*=C_{\max}\Delta t є емпіричною параметризацією, а не теоремою з §2.

Цей додаток підтримується як частина репозиторію проєкту OPT поряд із theoretical_roadmap.pdf.