Избыточность (теория информации)
![]() | Эта статья включает список общих ссылок , но в ней отсутствуют достаточные соответствующие встроенные цитаты . ( июнь 2016 г. ) |
В теории информации избыточность измеряет дробную разницу между энтропией H(X) ансамбля X и ее максимально возможным значением. . [1] [2] Неофициально это количество потраченного впустую «пространства», используемого для передачи определенных данных. Сжатие данных — это способ уменьшить или устранить нежелательную избыточность, а прямое исправление ошибок — это способ добавления желаемой избыточности в целях обнаружения и исправления ошибок при передаче данных по зашумленному каналу ограниченной пропускной способности .
Количественное определение [ править ]
При описании избыточности необработанных данных скорость источника информации представляет собой среднюю энтропию на символ. Для источников без памяти это просто энтропия каждого символа, тогда как в наиболее общем случае случайного процесса она равна
в пределе, когда n стремится к бесконечности, совместной энтропии первых n символов, разделенной на n . В теории информации принято говорить о «скорости» или « энтропии » языка. Это уместно, например, когда источником информации является английская проза. Скорость источника без памяти просто , поскольку по определению нет взаимозависимости последовательных сообщений источника без памяти. [ нужна цитата ]
Абсолютная скорость языка или источника просто
логарифм мощности . пространства сообщений или алфавита (Эту формулу иногда называют функцией Хартли .) Это максимально возможная скорость передачи информации, которая может быть передана с помощью данного алфавита. (Логарифм следует привести к основанию, соответствующему используемой единице измерения.) Абсолютная скорость равна фактической скорости, если источник не имеет памяти и имеет равномерное распределение .
Тогда абсолютную избыточность можно определить как
разница между абсолютной ставкой и ставкой.
Количество называется относительной избыточностью и дает максимально возможный коэффициент сжатия данных , выражаемый в процентах, на который можно уменьшить размер файла. (Если выразить это как отношение исходного размера файла к размеру сжатого файла, то количество дает максимальную степень сжатия, которую можно достичь.) Дополнением к концепции относительной избыточности является эффективность , определяемая как так что . Источник без памяти с равномерным распределением имеет нулевую избыточность (и, следовательно, 100% эффективность) и не может быть сжат.
Другие понятия [ править ]
Мерой избыточности между двумя переменными является взаимная информация или нормализованный вариант. Мерой избыточности многих переменных является общая корреляция .
Избыточность сжатых данных означает разницу между ожидаемой длиной сжатых данных Сообщения (или ожидаемая скорость передачи данных ) и энтропия (или уровень энтропии ). (Здесь мы предполагаем, что данные эргодичны и стационарны , например, источник без памяти.) Хотя разница скоростей может быть сколь угодно малым, так как увеличилась, фактическая разница , не может, хотя теоретически может быть ограничено сверху единицей в случае источников без памяти с конечной энтропией.
Избыточность в контексте теории информации может также относиться к информации, которая является избыточной между двумя взаимными данными. Например, учитывая три переменные , , и , известно, что совместная взаимная информация может быть меньше суммы предельных взаимных сведений: . В этом случае хотя бы часть информации о раскрыто или та же. Эта формулировка избыточности дополняет понятие синергии, которая возникает, когда совместная взаимная информация превышает сумму маргинальных значений, что указывает на наличие информации, которая раскрывается только совместным государством, а не каким-либо более простым набором источников. [3] [4]
Групповое резервирование [ править ]
Приведенную выше меру попарной избыточности можно обобщить на набор из n переменных.
. [5] Как и в случае с парной мерой, приведенной выше, если это значение отрицательное, можно сказать, что набор переменных избыточен.
См. также [ править ]
- Минимальное избыточное кодирование
- Сжатие данных
- функция Хартли
- Негэнтропия
- Теорема исходного кодирования
- Переполненность
Ссылки [ править ]
- ^ Здесь предполагается — множества, на которых определены распределения вероятностей.
- ^ Маккей, Дэвид Дж. К. (2003). «2.4 Определение энтропии и связанных с ней функций». Теория информации, вывод и алгоритмы обучения . Издательство Кембриджского университета . п. 33. ISBN 0-521-64298-1 .
Избыточность и измеряет дробную разницу между H(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 .