Энтропийная скорость

Теория информации
Собственная информация Информационная энтропия Дифференциальная энтропия Условная энтропия Энтропия объединения Взаимная информация Условная взаимная информация Относительная энтропия Энтропийная скорость
Избыточность информации Скорость передачи информации Пропускная способность канала
Теорема Шеннона для канала без шума Теоремы Шеннона для канала с шумом Теорема Шеннона — Хартли

Энтропийная скорость случайного процесса — в теории информации — величина, показывающая скорость возрастания энтропии при увеличении длины последовательности случайных величин, для которых она рассчитывается^[1].

Энтропийная скорость является пределом совместной энтропии ${\displaystyle N}$ случайных величин ${\displaystyle X_{k}}$, поделённым на ${\displaystyle N}$, при стремлении ${\displaystyle N}$ к бесконечности^[1]:

${\displaystyle H(X)=\lim _{N\to \infty }{\frac {1}{N}}H(X_{1},X_{2},\dots X_{N})}$,

если предел существует. Альтернативно связанной величиной является^[2]:

${\displaystyle H'(X)=\lim _{N\to \infty }H(X_{N}|X_{N-1},X_{N-2},\dots X_{1})}$.

Величины ${\displaystyle H(X)}$ и ${\displaystyle H'(X)}$ соответствуют двум различным понятиям скорости энтропии. Первая — это энтропия на символ ${\displaystyle N}$ случайных величин, а вторая — условная энтропия последней случайной величины, учитывая прошлые. Для стационарных случайных процессов выполняется равенство ${\displaystyle H(X)=H'(X)}$^[2]. Энтропийную скорость можно рассматривать как общее свойство случайных эргодических источников, то есть свойство асимптотической равнораспределенности^[3].

Энтропийную скорость можно использовать для оценки сложности случайных процессов. Она используется в различных приложениях от описания сложности языков, слепого разделения сигналов до оптимизации преобразователей и алгоритмов сжатия данных. Например, критерий максимальной энтропийной скорость может быть использован для отбора признаков в машинном обучении^[4].

Рассмотрим последовательности из ${\displaystyle N}$ случайных величин, принимающих ${\displaystyle M}$ значений^[1].

• Если значения случайных величин равновероятны, то, так как количество различных последовательностей равно ${\displaystyle M^{N}}$, получаем ${\displaystyle H(X_{1},X_{2},\dots X_{N})=\log _{2}M^{N}}$, и энтропийная скорость равна ${\displaystyle H(X)=\log _{2}M}$ бит на символ.

• Если ${\displaystyle X_{1},X_{2},\dots X_{N}}$ независимые одинаково распределённые случайные величины, то

${\displaystyle H(X)=\lim _{N\to \infty }{\frac {1}{N}}H(X_{1},X_{2},\dots X_{N})=\lim _{N\to \infty }{\frac {1}{N}}NH(X_{1})=H(X_{1})}$.

• Если ${\displaystyle X_{1},X_{2},\dots X_{N}}$ независимые, но не одинаково распределённые случайные величины, то

${\displaystyle H(X_{1},X_{2},\dots X_{N})=\sum _{i=1}^{N}H(X_{i})}$.

Тогда

${\displaystyle H(X)=\lim _{N\to \infty }{\frac {1}{N}}\sum _{i=1}^{N}H(X_{i})}$,

однако этот предел может не существовать.

Для стационарной цепи Маркова, определённой на счётном числе состояний, заданных матрицей переходов ${\displaystyle p_{ij}}$, энтропийная скорость задаётся выражением^[3]:

${\displaystyle \displaystyle H(X)=-\sum _{ij}\mu _{i}p_{ij}\log _{2}p_{ij}}$,

где ${\displaystyle \mu _{i}}$ является решением системы уравнений:

${\displaystyle \mu _{j}=-\sum _{i}\mu _{i}p_{ij}}$

для всех ${\displaystyle j}$.

Если цепь Маркова неприводима и непериодична, то она имеет единственное стационарное распределение на состояниях, и любое начальное распределение стремится к стационарному распределению при ${\displaystyle N\rightarrow \infty }$. В этом случае, даже если начальное распределение не является стационарным распределением, скорость энтропии, которая определяется в терминах долгосрочного поведения, равна ${\displaystyle H(X)}$^[5].

• Марковский источник информации

• Einicke G. A. Maximum-Entropy Rate Selection of Features for Classifying Changes in Knee and Ankle Dynamics During Running // IEEE Journal of Biomedical and Health Informatics. — 2018. — Т. 28, вып. 4. — doi:10.1109/JBHI.2017.2711487.
• Cover T., Thomas J. Elements of Information Theory. — John Wiley and Sons, Inc., 2006. — ISBN 0-471-24195-4.