Алгоритм Блахута–Аримото

Термин алгоритм Блахута–Аримото часто используется для обозначения класса алгоритмов для численного вычисления либо информационно-теоретической емкости канала, функции скорости-искажения источника или кодирования источника (т. е. сжатия для удаления избыточности). Это итеративные алгоритмы , которые в конечном итоге сходятся к одному из максимумов задачи оптимизации , которая связана с этими информационно-теоретическими концепциями.

Для случая пропускной способности канала алгоритм был независимо изобретен Сугуру Аримото ^[1] и Ричардом Блахутом . ^[2] Кроме того, обработка Блахута дает алгоритмы для вычисления искажения скорости и обобщенной пропускной способности с входными ограничениями (т. е. функция пропускной способности-стоимости, аналогичная функции пропускной способности-искажения). Эти алгоритмы наиболее применимы к случаю произвольных конечных источников алфавита. Большая работа была проделана для его распространения на более общие примеры проблем. ^{[3] [4]} Недавно была предложена версия алгоритма, которая учитывает непрерывные и многомерные выходные данные с приложениями в клеточной сигнализации. ^[5] Существует также версия алгоритма Блахута–Аримото для направленной информации . ^[6]

Дискретный канал без памяти (DMC) может быть определен с помощью двух случайных величин с алфавитом и закона канала как условного распределения вероятностей . Пропускная способность канала , определяемая как , указывает максимальную эффективность, которую канал может передавать, в единицах бит за использование. ^[7] Теперь, если мы обозначим мощность , то это матрица, в которой мы обозначим запись строки, столбца как . Для случая пропускной способности канала алгоритм был независимо изобретен Сугуру Аримото ^[8] и Ричардом Блахутом . ^[9] Они оба нашли следующее выражение для пропускной способности DMC с законом канала: ${\displaystyle X,Y}$${\displaystyle {\mathcal {X}},{\mathcal {Y}}}$ ${\displaystyle p(y|x)}$${\displaystyle C:=\sup _{p\sim X}I(X;Y)}$${\displaystyle |{\mathcal {X}}|=n,|{\mathcal {Y}}|=m}$${\displaystyle p_{Y|X}}$${\displaystyle n\times m}$${\displaystyle я^{й}}$${\displaystyle j^{th}}$${\displaystyle w_{ij}}$

${\displaystyle C=\max _{\mathbf {p} }\max _{Q}\sum _{i=1}^{n}\sum _{j=1}^{m}p_{i}w_{ij}\log \left({\dfrac {Q_{ji}}{p_{i}}}\right)}$

где и максимизируются при следующих требованиях: ${\displaystyle \mathbf {п} }$${\displaystyle Q}$

• ${\displaystyle \mathbf {п} }$— это распределение вероятностей на , то есть, если мы запишем как ${\displaystyle X}$${\displaystyle \mathbf {п} }$${\displaystyle (p_{1},p_{2}...,p_{n}),\sum _{i=1}^{n}p_{i}=1}$
• ${\displaystyle Q=(q_{ji})}$— это матрица, которая ведет себя как матрица перехода от к относительно закона канала. То есть, для всех :${\displaystyle m\times n}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle 1\leq i\leq n,1\leq j\leq m}$
  • ${\displaystyle q_{ji}\geq 0,q_{ji}=0\Leftrightarrow w_{ij}=0}$
  • Сумма всех строк равна 1, т.е. .${\displaystyle \sum _{i=1}^{n}q_{ji}=1}$

Затем, выбрав случайное распределение вероятностей , мы можем итеративно сгенерировать последовательность следующим образом:${\displaystyle \mathbf {p} ^{0}:=(p_{1}^{0},p_{2}^{0},...p_{n}^{0})}$${\displaystyle X}$${\displaystyle (\mathbf {p} ^{0},Q^{0},\mathbf {p} ^{1},Q^{1}...)}$

${\displaystyle (q_{ji}^{t}):={\dfrac {p_{i}^{t}w_{ij}}{\sum _{k=1}^{n}p_{k}^{t}w_{kj}}}}$

${\displaystyle p_{k}^{t+1}:={\dfrac {\prod _{j=1}^{m}(q_{jk}^{t})^{w_{kj}}}{\sum _{i=1}^{n}\prod _{j=1}^{m}(q_{ji}^{t})^{w_{ij}}}}}$

Для .${\displaystyle t=0,1,2...}$

Затем, используя теорию оптимизации, а именно метод спуска по координатам , Йенг ^[10] показал, что последовательность действительно сходится к требуемому максимуму. То есть,

${\displaystyle \lim _{t\to \infty }\sum _{i=1}^{n}\sum _{j=1}^{m}p_{i}^{t}w_{ij}\log \left({\dfrac {Q_{ji}^{t}}{p_{i}^{t}}}\right)=C}$.

Таким образом, учитывая закон канала , пропускную способность можно оценить численно с произвольной точностью.${\displaystyle p(y|x)}$

Предположим, у нас есть источник с вероятностью любого заданного символа. Мы хотим найти кодировку , которая генерирует сжатый сигнал из исходного сигнала, минимизируя ожидаемое искажение , где ожидание берется по совместной вероятности и . Мы можем найти кодировку, которая минимизирует функционал скорости-искажения локально, повторяя следующую итерацию до сходимости:${\displaystyle X}$${\displaystyle p(x)}$${\displaystyle p({\hat {x}}|x)}$${\displaystyle {\hat {X}}}$ ${\displaystyle \langle d(x,{\hat {x}})\rangle }$${\displaystyle X}$${\displaystyle {\hat {X}}}$

${\displaystyle p_{t+1}({\hat {x}}|x)={\frac {p_{t}({\hat {x}})\exp(-\beta d(x,{\hat {x}}))}{\sum _{\hat {x}}p_{t}({\hat {x}})\exp(-\beta d(x,{\hat {x}}))}}}$

${\displaystyle p_{t+1}({\hat {x}})=\sum _{x}p(x)p_{t+1}({\hat {x}}|x)}$

где — параметр, связанный с наклоном кривой «скорость-искажение», на который мы ориентируемся, и, таким образом, связанный с тем, насколько мы отдаем предпочтение сжатию по сравнению с искажением (чем выше, тем меньше сжатие).${\displaystyle \beta }$${\displaystyle \beta }$