Направленная информация

Направленная информация - это мера теории информации , которая количественно определяет поток информации из случайной строки. $X^{n}=(X_{1},X_{2},\dots ,X_{n})$ к случайной строке $Y^{n}=(Y_{1},Y_{2},\dots ,Y_{n})$. Термин «направленная информация» был придуман Джеймсом Мэсси и определяется как

$I(X^{n}\to Y^{n})\triangleq \sum _{i=1}^{n}I(X^{i};Y_{i}|Y^{i-1})$

где $I(X^{i};Y_{i}|Y^{i-1})$ это условная взаимная информация $I(X_{1},X_{2},...,X_{i};Y_{i}|Y_{1},Y_{2},...,Y_{i-1})$.

Направленная информация применима к проблемам, где причинно-следственная связь играет важную роль, например, пропускная способность каналов с обратной связью , пропускная способность дискретных сетей без памяти , пропускная способность сетей с блочной памятью, азартные игры с причинно-следственной информацией, сжатие причинно-следственной информации, настройки связи в режиме реального времени , и статистическая физика.

Причинная обусловленность

Сутью направленной информации является причинная обусловленность . Вероятность $y^{n}$ причинно обусловлено $x^{n}$ определяется как

$P(x^{n}||y^{n})\triangleq \prod _{i=1}^{n}P(x_{i}|x^{i-1},y^{i})$.

Это похоже на цепное правило для обычного кондиционирования. $P(x^{n}|y^{n})=\prod _{i=1}^{n}P(x_{i}|x^{i-1},y^{n})$ кроме одного условия на «прошлые» и «настоящие» символы $y^{i}$ а не все символы $y^{n}$. Чтобы включить только «прошлые» символы, можно ввести задержку, добавив постоянный символ:

$P(x^{n}||(0,y^{n-1}))\triangleq \prod _{i=1}^{n}P(x_{i}|x^{i-1},y^{i-1})$.

Часто злоупотребляют обозначениями, записывая $P(x^{n}||y^{n-1})$ для этого выражения, хотя формально все строки должны иметь одинаковое количество символов.

Можно также указать несколько строк: $P(x^{n}||y^{n},z^{n})\triangleq \prod _{i=1}^{n}P(x_{i}|x^{i-1},y^{i},z^{i})$.

Причинно обусловленная энтропия

определяется Причинно обусловленная энтропия как:

$H(X^{n}||Y^{n})=\mathbf {E} \left[-\log {P(X^{n}||Y^{n})}\right]=\sum _{i=1}^{n}H(X_{i}|X^{i-1},Y^{i})$

Аналогично, можно причинно обусловить несколько строк и написать $H(X^{n}||Y^{n},Z^{n})=\mathbf {E} \left[-\log {P(X^{n}||Y^{n},Z^{n})}\right]$.

Свойства

Правило декомпозиции причинной обусловленности является

$P(x^{n},y^{n})=P(x^{n}||y^{n-1})P(y^{n}||x^{n})$.

Это правило показывает, что любой продукт $P(x^{n}||y^{n-1}),P(y^{n}||x^{n})$ дает совместное распределение $P(x^{n},y^{n})$.

Вероятность причинной обусловленности $P(y^{n}||x^{n})=\prod _{i=1}^{n}P(y_{i}|y^{i-1},x^{i})$ – вектор вероятности, т. е.

$P(y^{n}||x^{n})\geq 0\quad {\text{and}}\quad \sum _{y^{n}}P(y^{n}||x^{n})=1\quad {\text{for all }}(x^{n},y^{n})$.

Направленная информация может быть записана в терминах причинной обусловленности:

$I(X^{N}\rightarrow Y^{N})=\mathbf {E} \left[\log {\frac {P(Y^{N}||X^{N})}{P(Y^{N})}}\right]=H(Y^{n})-H(Y^{n}||X^{n})$.

Отношение обобщается до трех строк: направленная информация, вытекающая из $X^{n}$ к $Y^{n}$ причинно обусловлено $Z^{n}$ является

$I(X^{n}\to Y^{n}||Z^{n})=H(Y^{n}||Z^{n})-H(Y^{n}||X^{n},Z^{n})$.

Закон сохранения информации

Этот закон, установленный Джеймсом Мэсси и его сыном Питером Мэсси, дает интуицию, связывая направленную информацию и взаимную информацию. Закон гласит, что для любого $X^{n},Y^{n}$, имеет место следующее равенство:

$I(X^{n};Y^{n})=I(X^{n}\to Y^{n})+I(Y^{n-1}\to X^{n}).$

Две альтернативные формы этого закона:

$I(X^{n};Y^{n})=I(X^{n}\to Y^{n})+I(Y^{n}\to X^{n})-I(X^{n}\leftrightarrow Y^{n})$

$I(X^{n};Y^{n})=I(X^{n-1}\to Y^{n})+I(Y^{n-1}\to X^{n})+I(X^{n}\leftrightarrow Y^{n})$

где $I(X^{n}\leftrightarrow Y^{n})=\sum _{i=1}^{n}I(X_{i};Y_{i}|X^{i-1},Y^{i-1})$.

Оценка и оптимизация

Оценка и оптимизация направляемой информации является сложной задачей, поскольку она $n$ условия, где $n$ может быть большим. Во многих случаях интерес представляет оптимизация предельного среднего, т. е. когда $n$ растет до бесконечности, что называется многобуквенным выражением.

Оценка

Оценка направленной информации по выборкам представляет собой трудную задачу, поскольку выражение направленной информации зависит не от выборок, а от совместного распределения. $\{P(x_{i},y_{i}|x^{i-1},y^{i-1})_{i=1}^{n}\}$ что может быть неизвестно. Существует несколько алгоритмов, основанных на взвешивании контекстного дерева. и эмпирические параметрические распределения и использование долговременной кратковременной памяти .

Оптимизация

Максимизация направленной информации является фундаментальной проблемой теории информации. Например, учитывая распределение каналов $\{P(y_{i}|x^{i},y^{i-1}\}_{i=1}^{n})$, цель может заключаться в оптимизации $I(X^{n}\to Y^{n})$ по входным распределениям каналов $\{P(x_{i}|x^{i-1},y^{i-1}\}_{i=1}^{n})$.

Существуют алгоритмы оптимизации направленной информации на основе алгоритма Блахута-Аримото , Марковский процесс принятия решения , Рекуррентная нейронная сеть , Обучение с подкреплением . и графические методы (Q-графики) . Для алгоритма Блахута- Аримото Основная идея состоит в том, чтобы начать с последней взаимной информации направленного информационного выражения и идти назад. Для процесса принятия решений марковского Основная идея заключается в том, чтобы превратить оптимизацию в процесс принятия решений Маркова с бесконечным горизонтом среднего вознаграждения . Для рекуррентной нейронной сети Основная идея — смоделировать входное распределение с помощью Рекуррентной нейронной сети и оптимизировать параметры с помощью Градиентного спуска . Для обучения с подкреплением Основная идея состоит в том, чтобы решить Марковского процесса принятия решений формулировку емкости с использованием инструментов обучения с подкреплением , которые позволяют работать с большими или даже непрерывными алфавитами.

Теория двунаправленной коммуникации Марко

Направленная информация Мэсси была мотивирована ранней работой Марко (1966) по разработке теории двунаправленной коммуникации. Марко Определение направленной трансформации несколько отличается от определения Мэсси тем, что в какой-то момент $n$, одно условие на прошлые символы $X^{n-1},Y^{n-1}$ только и каждый принимает пределы:

$T_{12}=\lim _{n\to \infty }\mathbf {E} \left[-\log {\frac {P(X_{n}|X^{n-1})}{P(X_{n}|X^{n-1},Y^{n-1})}}\right]\quad {\text{and}}\quad T_{21}=\lim _{n\to \infty }\mathbf {E} \left[-\log {\frac {P(Y_{n}|Y^{n-1})}{P(Y_{n}|Y^{n-1},X^{n-1})}}\right].$

Марко определил несколько других величин, в том числе:

• Общая информация: $H_{1}=\lim _{n\to \infty }\mathbf {E} \left[-\log P(X_{n}|X^{n-1})\right]$ и $H_{2}=\lim _{n\to \infty }\mathbf {E} \left[-\log P(Y_{n}|Y^{n-1})\right]$
• Бесплатная информация: $F_{1}=\lim _{n\to \infty }\mathbf {E} \left[-\log P(X_{n}|X^{n-1},Y^{n-1})\right]$ и $F_{2}=\lim _{n\to \infty }\mathbf {E} \left[-\log P(Y_{n}|Y^{n-1},X^{n-1})\right]$
• Совпадение: $K=\lim _{n\to \infty }\mathbf {E} \left[-\log {\frac {P(X_{n}|X^{n-1})P(Y_{n}|Y^{n-1})}{P(X_{n},Y_{n}|X^{n-1},Y^{n-1})}}\right].$

Общую информацию обычно называют уровнем энтропии. Марко показал следующие соотношения для интересующих его задач:

• $K=T_{12}+T_{21}$
• $H_{1}=T_{12}+F_{1}$ и $H_{2}=T_{21}+F_{2}$

Он также определил величины, которые назвал остаточной энтропией :

• $R_{1}=H_{1}-K=F_{1}-T_{21}$
• $R_{2}=H_{2}-K=F_{2}-T_{12}$

и разработал закон сохранения $F_{1}+F_{2}=R_{1}+R_{2}+K=H_{1}+H_{2}-K$ и несколько границ.

Связь с передачей энтропии

Направленная информация связана с энтропией переноса , которая представляет собой усеченную версию направленной трансформации Марко. $T_{21}$.

Энтропия переноса во времени $i$ и с памятью $d$ является

$T_{X\to Y}=I(X_{i-1},\dots ,X_{i-d};Y_{i}|Y_{i-1},\dots ,Y_{i-d}).$

где не указан настоящий символ $X_{i}$ или прошлые символы $X^{i-d-1},Y^{i-d-1}$ раньше времени $i-d$.

Энтропия переноса обычно предполагает стационарность, т. е. $T_{X\to Y}$ не зависит от времени $i$.