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

Класс алгоритмов в теории информации

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

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

Для случая пропускной способности канала алгоритм был независимо изобретен Сугуру Аримото ^[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 i^{th}}$ ${\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 {p} }$ ${\displaystyle Q}$

• ${\displaystyle \mathbf {p} }$— это распределение вероятностей на , то есть, если мы запишем как ${\displaystyle X}$ ${\displaystyle \mathbf {p} }$ ${\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 }$

Ссылки

1. Аримото, Сугуру (1972), «Алгоритм вычисления пропускной способности произвольных дискретных каналов без памяти», IEEE Transactions on Information Theory , 18 (1): 14–20, doi :10.1109/TIT.1972.1054753, S2CID  8408706.
2. Блахут, Ричард (1972), «Вычисление пропускной способности канала и функций скорости-искажения», IEEE Transactions on Information Theory , 18 (4): 460–473, CiteSeerX 10.1.1.133.7174 , doi :10.1109/TIT.1972.1054855 .
3. Vontobel, Pascal O. (2003). "Обобщенный алгоритм Блахута–Аримото". Труды Международного симпозиума IEEE по теории информации, 2003. стр. 53. doi :10.1109/ISIT.2003.1228067. ISBN 0-7803-7728-1.
4. Иддо Найсс; Хаим Пермутер (2010). «Расширение алгоритма Блахута-Аримото для максимизации направленной информации». arXiv : 1012.5071v2 [cs.IT].
5. Томаш Йетка; Кароль Ниенальтовски; Томаш Винарски; Славомир Блонски; Михал Коморовски (2019), "Информационно-теоретический анализ многомерных одноклеточных сигнальных реакций", PLOS Computational Biology , 15 (7): e1007132, arXiv : 1808.05581 , Bibcode : 2019PLSCB..15E7132J, doi : 10.1371/journal.pcbi.1007132 , PMC 6655862 , PMID  31299056 
6. Naiss, Iddo; Permuter, Haim H. (январь 2013 г.). «Расширение алгоритма Блахута–Аримото для максимизации направленной информации». Труды IEEE по теории информации . 59 (1): 204–222. arXiv : 1012.5071 . doi : 10.1109/TIT.2012.2214202. S2CID  3115749.
7. Cover, TM (2006). Элементы теории информации. Джой А. Томас (2-е изд.). Хобокен, Нью-Джерси: Wiley-Interscience. ISBN 0-471-24195-4. OCLC  59879802.
8. Аримото, Сугуру (1972), «Алгоритм вычисления пропускной способности произвольных дискретных каналов без памяти», IEEE Transactions on Information Theory , 18 (1): 14–20, doi :10.1109/TIT.1972.1054753, S2CID  8408706.
9. Блахут, Ричард (1972), «Вычисление пропускной способности канала и функций скорости-искажения», IEEE Transactions on Information Theory , 18 (4): 460–473, CiteSeerX 10.1.1.133.7174 , doi :10.1109/TIT.1972.1054855 .
10. Yeung, Raymond W. (2008). Теория информации и сетевое кодирование. Нью-Йорк: Springer. ISBN 978-0-387-79234-7. OCLC  288469056.