Теория упорядоченного патча

Исходная задача T-1: Фильтр стабильности — полная спецификация rate-distortion Проблема: Теория rate-distortion Шеннона требует: источник X, алфавит воспроизведения и функцию искажения d(x, \hat{x}). В препринте используется R_{pred}(D) без спецификации этих трёх элементов для субстрата OPT. Результат: Полная спецификация (\mathcal{X}, \hat{\mathcal{X}}, P_X, d) для задачи rate-distortion в OPT.

В этой редакции избыточная энтропия отделяется от статистической сложности, доказывается тождество predictive-KL при конечном горизонте, доказывается общая нижняя граница R_{T,h}(D)\ge E_{T,h}-D, и формулируется точный критерий равенства для случая, когда эта нижняя граница достигается. C_{\max} остаётся эмпирическим параметром, а не величиной, выводимой из формализма rate-distortion.
Статус закрытия: ЧАСТИЧНО РЕШЕНО. Спецификация четвёрки, тождество predictive-KL и общая нижняя граница R_{T,h}(D) \geq E_{T,h}(\nu) - D установлены вместе с точным критерием равенства. Более раннее общее утверждение о замкнутой форме R(D) = C_\mu - D отозвано; корректным результатом является нижняя граница. C_{\max} остаётся эмпирическим параметром, а не величиной, выводимой из формализма rate-distortion.

§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 Переформулировка через информационное бутылочное горлышко

Ограничение на искажение сужает пространство допустимых кодеров до тех, которые удовлетворяют условию \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 (например, для de Bruijn-циклов высокого порядка при k \to \infty) граница выполняется тривиально; такие процессы исключаются из observer-compatible множества 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.