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

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

История и применение

Для случая пропускной способности канала алгоритм был независимо изобретен Сугуру Аримото. и Ричард Блаут . Кроме того, трактовка Блахута дает алгоритмы для расчета искажения скорости и обобщенной мощности с ограничениями на входные данные (т.е. функцию стоимости мощности, аналогичную искажению скорости). Эти алгоритмы наиболее применимы к случаю произвольных конечных источников алфавита. Была проделана большая работа по распространению его на более общие случаи проблем. Недавно версия алгоритма, учитывающая непрерывные и многомерные выходные данные, была предложена для приложений в сотовой передаче сигналов. Существует также версия алгоритма Блахута–Аримото для направленной информации .

Алгоритм определения пропускной способности канала

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

$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)$

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

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

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

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

$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}}}}$

Для $t=0,1,2...$.

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

$\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$.

Итак, учитывая закон канала $p(y|x)$, емкость можно оценить численно с любой точностью.

Алгоритм искажения скорости

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

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

$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}}))}}$

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