Избыточность (теория информации)

В теории информации избыточность измеряет дробную разницу между энтропией $H(X)$ ансамбля $X$ и ее максимально возможным значением. $\log(|{\mathcal {A}}_{X}|)$ . ^[1]^[2] Неофициально это количество потраченного впустую «пространства», используемого для передачи определенных данных. Сжатие данных — это способ уменьшить или устранить нежелательную избыточность, а прямое исправление ошибок — это способ добавления желаемой избыточности в целях обнаружения и исправления ошибок при передаче данных по зашумленному каналу ограниченной пропускной способности .

Количественное определение [ править ]

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

r=\lim _{n\to \infty }{\frac {1}{n}}H(M_{1},M_{2},\dots M_{n}),

в пределе, когда n стремится к бесконечности, совместной энтропии первых n символов, разделенной на n . В теории информации принято говорить о «скорости» или « энтропии » языка. Это уместно, например, когда источником информации является английская проза. Скорость источника без памяти просто $H(M)$ , поскольку по определению нет взаимозависимости последовательных сообщений источника без памяти. ^{[ нужна ссылка ]}

Абсолютная скорость языка или источника просто

R=\log |\mathbb {M} |,\,

логарифм мощности сообщений пространства или алфавита. (Эту формулу иногда называют функцией Хартли .) Это максимально возможная скорость передачи информации, которую можно передать с помощью данного алфавита. (Логарифм следует привести к основанию, соответствующему используемой единице измерения.) Абсолютная скорость равна фактической скорости, если источник не имеет памяти и имеет равномерное распределение .

Тогда абсолютную избыточность можно определить как

D=R-r,\,

разница между абсолютной ставкой и ставкой.

Количество ${\frac {D}{R}}$ называется относительной избыточностью и дает максимально возможный коэффициент сжатия данных , выражаемый в процентах, на который можно уменьшить размер файла. (Если выразить это как отношение исходного размера файла к размеру сжатого файла, то количество $R:r$ дает максимальную степень сжатия, которую можно достичь.) Дополнением к концепции относительной избыточности является эффективность , определяемая как ${\frac {r}{R}},$ так что ${\frac {r}{R}}+{\frac {D}{R}}=1$ . Источник без памяти с равномерным распределением имеет нулевую избыточность (и, следовательно, 100% эффективность) и не может быть сжат.

Другие понятия [ править ]

Мерой избыточности между двумя переменными является взаимная информация или нормализованный вариант. Мерой избыточности многих переменных является общая корреляция .

Избыточность сжатых данных означает разницу между ожидаемой длиной сжатых данных $n$ сообщения $L(M^{n})\,\!$ (или ожидаемая скорость передачи данных $L(M^{n})/n\,\!$ ) и энтропия $nr\,\!$ (или уровень энтропии $r\,\!$ ). (Здесь мы предполагаем, что данные эргодичны и стационарны , например, источник без памяти.) Хотя разница скоростей $L(M^{n})/n-r\,\!$ может быть сколь угодно малым, так как $n\,\!$ увеличилась, фактическая разница $L(M^{n})-nr\,\!$ , не может, хотя теоретически может быть ограничено сверху единицей в случае источников без памяти с конечной энтропией.

Избыточность в контексте теории информации может также относиться к информации, которая является избыточной между двумя взаимными данными. Например, учитывая три переменные $X_{1}$ , $X_{2}$ , и $Y$ , известно, что совместная взаимная информация может быть меньше суммы предельных взаимных сведений: $I(X_{1},X_{2};Y)<I(X_{1};Y)+I(X_{2};Y)$ . В этом случае хотя бы часть информации о $Y$ раскрыто $X_{1}$ или $X_{2}$ то же самое. Эта формулировка избыточности дополняет понятие синергии, которая возникает, когда совместная взаимная информация превышает сумму маргинальных значений, что указывает на наличие информации, которая раскрывается только совместным государством, а не каким-либо более простым набором источников. ^[3]^[4]

Групповое резервирование [ править ]

Приведенную выше меру попарной избыточности можно обобщить на набор из n переменных.

$Redundancy=I(X_{1},X_{2},...,X_{n};Y)-\left(I(X_{1};Y)+I(X_{2};Y)+...I(X_{n};Y)\right)$ . ^[5] Как и в случае с парной мерой, приведенной выше, если это значение отрицательное, можно сказать, что набор переменных избыточен.

См. также [ править ]

Ссылки [ править ]

^ Здесь предполагается ${\mathcal {A}}_{X}$ — множества, на которых определены распределения вероятностей.
^ Маккей, Дэвид Дж. К. (2003). «2.4 Определение энтропии и связанных с ней функций». Теория информации, вывод и алгоритмы обучения . Издательство Кембриджского университета . п. 33. ISBN 0-521-64298-1 . Избыточность и его измеряет дробную разницу между $H(X)$ максимально возможным значением, $|\log(|{\mathcal {A}}_{X}|)$
^ Уильямс, Пол Л.; Бир, Рэндалл Д. (2010). «Неотрицательное разложение многомерной информации». arXiv : 1004.2515 [ cs.IT ].
^ Гуткнехт, AJ; Вибрал, М.; Макке, А. (2021). «Кусочки и кусочки: понимание разложения информации на основе отношений часть-целое и формальной логики» . Труды Королевского общества A: Математические, физические и технические науки . 477 (2251). arXiv : 2008.09535 . Бибкод : 2021RSPSA.47710110G . дои : 10.1098/rspa.2021.0110 . ПМЦ 8261229 . ПМИД 35197799 . S2CID 221246282 .
^ Чечик, Гал; Глоберсон, Амир; Андерсон, М.; Янг, Э.; Нелькен, Израиль; Тишби, Нафтали (2001). «Меры групповой избыточности показывают снижение избыточности в слуховом пути» . Достижения в области нейронных систем обработки информации . 14 . МТИ Пресс.

Реза, Фазлолла М. (1994) [1961]. Введение в теорию информации . Нью-Йорк: Дувр [МакГроу-Хилл]. ISBN 0-486-68210-2 .
Шнайер, Брюс (1996). Прикладная криптография: протоколы, алгоритмы и исходный код на C. John Wiley & Sons, Inc. Нью-Йорк: ISBN 0-471-12845-7 .
Ауффарт, Б; Лопес-Санчес, М.; Серкидес, Дж. (2010). «Сравнение мер избыточности и релевантности для выбора признаков при классификации тканей на компьютерных изображениях». Достижения в области интеллектуального анализа данных. Приложения и теоретические аспекты . Спрингер. стр. 248–262. CiteSeerX 10.1.1.170.1528 .

[1] Здесь предполагается ${\mathcal {A}}_{X}$ — множества, на которых определены распределения вероятностей.

[2] Маккей, Дэвид Дж. К. (2003). «2.4 Определение энтропии и связанных с ней функций». Теория информации, вывод и алгоритмы обучения . Издательство Кембриджского университета . п. 33. ISBN 0-521-64298-1 . Избыточность и его измеряет дробную разницу между $H(X)$ максимально возможным значением, $|\log(|{\mathcal {A}}_{X}|)$

[3] Уильямс, Пол Л.; Бир, Рэндалл Д. (2010). «Неотрицательное разложение многомерной информации». arXiv : 1004.2515 [ cs.IT ].

[4] Гуткнехт, AJ; Вибрал, М.; Макке, А. (2021). «Кусочки и кусочки: понимание разложения информации на основе отношений часть-целое и формальной логики» . Труды Королевского общества A: Математические, физические и технические науки . 477 (2251). arXiv : 2008.09535 . Бибкод : 2021RSPSA.47710110G . дои : 10.1098/rspa.2021.0110 . ПМЦ 8261229 . ПМИД 35197799 . S2CID 221246282 .

[5] Чечик, Гал; Глоберсон, Амир; Андерсон, М.; Янг, Э.; Нелькен, Израиль; Тишби, Нафтали (2001). «Меры групповой избыточности показывают снижение избыточности в слуховом пути» . Достижения в области нейронных систем обработки информации . 14 . МТИ Пресс.

[1]

[2]

[3]

[4]

[5]