Информационная дистанция

Информационное расстояние — это расстояние между двумя конечными объектами (представленными в виде компьютерных файлов), выраженное как количество битов в кратчайшей программе, преобразующей один объект в другой или наоборот. универсальный компьютер . Это расширение колмогоровской сложности . ^{[ 1 ]} Колмогоровская сложность одного конечного объекта — это информация в этом объекте; информационное расстояние между парой конечных объектов — это минимальная информация, необходимая для перехода от одного объекта к другому или наоборот. Информационная дистанция была впервые определена и исследована в ^{[ 2 ]} основанные на термодинамических принципах, см. также. ^{[ 3 ]} Впоследствии оно приобрело окончательный вид в. ^{[ 4 ]} Он применяется к нормализованному расстоянию сжатия и нормализованному расстоянию Google .

Характеристики

Формально информационная дистанция $ID(x,y)$ между $x$ и $y$ определяется

ID(x,y)=\min\{|p|:p(x)=y\;\&\;p(y)=x\},

с $p$ конечная двоичная программа для стационарного универсального компьютера с конечными двоичными строками на входе $x,y$ . В ^{[ 4 ]} доказано, что $ID(x,y)=E(x,y)+O(\log \cdot \max\{K(x\mid y),K(y\mid x)\})$ с

E(x,y)=\max\{K(x\mid y),K(y\mid x)\},

где $K(\cdot \mid \cdot )$ – колмогоровская сложность, определяемая формулой ^{[ 1 ]} типа префикса. ^{[ 5 ]} Этот $E(x,y)$ это важная величина.

Универсальность

Позволять $\Delta$ — класс верхних полувычислимых расстояний $D(x,y)$ удовлетворяющие плотности условию

\sum _{x:x\neq y}2^{-D(x,y)}\leq 1,\;\sum _{y:y\neq x}2^{-D(x,y)}\leq 1,

Это исключает нерелевантные расстояния, такие как $D(x,y)={\frac {1}{2}}$ для $x\neq y$ ; он заботится о том, чтобы с ростом расстояния увеличивалось и количество объектов на этом расстоянии от данного объекта. Если $D\in \Delta$ затем $E(x,y)\leq D(x,y)$ с точностью до постоянного аддитивного члена. ^{[ 4 ]} Вероятностные выражения расстояния - это первый когомологический класс информационных симметричных когомологий. ^{[ 6 ]} которое можно рассматривать как свойство универсальности.

Метричность

Расстояние $E(x,y)$ является метрикой с точностью до добавки $O(\log .\max\{K(x\mid y),K(y\mid x)\})$ член в метрических (в)равенствах. ^{[ 4 ]} Вероятностная версия метрики действительно уникальна, как показал Хан в 1981 году. ^{[ 7 ]}

Максимальное перекрытие

Если $E(x,y)=K(x\mid y)$ , тогда есть программа $p$ длины $K(x\mid y)$ который преобразует $y$ к $x$ и программа $q$ длины $K(y\mid x)-K(x\mid y)$ такое, что программа $qp$ преобразует $x$ к $y$ . (Программы имеют саморазграничивающийся формат, что означает, что можно решить, где заканчивается одна программа и начинается другая, путем объединения программ.) То есть кратчайшие программы для преобразования между двумя объектами можно сделать максимально перекрывающимися: $K(x\mid y)\leq K(y\mid x)$ его можно разделить на программу, преобразующую объект $x$ возражать $y$ и еще одна программа, которая объединилась с первыми конвертерами $y$ к $x$ в то время как объединение этих двух программ является самой короткой программой для преобразования между этими объектами. ^{[ 4 ]}

Минимальное перекрытие

Программы для преобразования между объектами $x$ и $y$ также можно сделать минимальное перекрытие. Существует программа $p$ длины $K(x\mid y)$ до аддитивного члена $O(\log(\max\{K(x\mid y),K(y\mid x)\}))$ это отображает $y$ к $x$ и имеет небольшую сложность, когда $x$ известно( $K(p\mid x)\approx 0$ ). Поменяв местами два объекта, мы получили другую программу. ^{[ 8 ]} Имея в виду параллелизм между теорией информации Шеннона и теорией сложности Колмогорова , можно сказать, что этот результат параллелен теоремам Слепиана-Вольфа и Кернера-Имре Чисара-Мартона .

Приложения

Теоретический

Результат Ан.А. Мучник о минимальном перекрытии выше является важным теоретическим приложением, показывающим что существуют определенные коды: для перехода к конечному целевому объекту из любого объекта существует программа, которая почти только зависит от целевого объекта! Этот результат достаточно точен, и член ошибки не может быть значительно улучшен. ^{[ 9 ]} Информационная дистанция была материальной в учебнике, ^{[ 10 ]} это встречается в Энциклопедии расстояний. ^{[ 11 ]}

Практичный

Чтобы определить сходство таких объектов, как геномы, языки, музыка, интернет-атаки и черви, программы и т. д., информационное расстояние нормализуется, а члены колмогоровской сложности аппроксимируются реальными компрессорами (колмогоровская сложность — это нижняя граница длина в битах сжатой версии объекта). Результатом является нормализованное расстояние сжатия (NCD) между объектами. Это относится к объектам, представленным в виде компьютерных файлов, например геному мыши или тексту книги. Если объектам просто даны имена, такие как «Эйнштейн» или «стол», название книги или имя «мышь», сжатие не имеет смысла. Нам нужна внешняя информация о том, что означает это имя. Эту информацию можно получить с помощью базы данных (например, Интернета) и средств поиска в базе данных (например, поисковой системы, такой как Google). Любая поисковая система в базе данных, предоставляющая совокупное количество страниц, может использоваться с нормализованным расстоянием Google (NGD). Доступен пакет Python для вычисления всех информационных расстояний и объемов, многомерной взаимной информации, условной взаимной информации, совместной энтропии, полных корреляций в наборе данных из n переменных. ^{[ 12 ]}

Ссылки

Сопутствующая литература

Архангельский А.В.; Понтрягин, Л.С. (1990), Общая топология I: основные понятия и конструкции Теория размерности , Энциклопедия математических наук, Springer , ISBN 3-540-18178-4

[Ko65-1] Jump up to: ^а ^б А. Н. Колмогоров, Три подхода к количественному определению информации, Проблемы информ. Передача, 1:1 (1965), 1–7

[LV92-2] М. Ли, ПМБ Витани, Теория термодинамики вычислений, Proc. Семинар IEEE по физике вычислений, Даллас, Техас, США, 1992, 42–46.

[3] М. Ли, ПМБ Витани, Обратимость и адиабатические вычисления: обмен времени и пространства на энергию, Proc. Р. Сок. Лонд. А от 9 апреля 1996 г., том. 452 нет. 1947 769–789

[BGLVZ98-4] Jump up to: ^а ^б ^с ^д ^и Ч. Беннетт, П. Гакс, М. Ли, П. М. Витаньи, В. Зурек, Информационная дистанция, Транзакции IEEE по теории информации, 44:4 (1998), 1407–1423.

[5] Л. А. Левин, Законы сохранения информации (нероста) и аспекты основания теории вероятностей, Проблемы информ. Трансмиссия, 10:3 (1974), 30–35.

[6] П. Бодо, Машина Пуанкаре-Шеннона: статистическая физика и аспекты машинного обучения информационных когомологий, Энтропия, 21:9 - 881 (2019)

[7] Те Сунь Хан, Уникальность информационной дистанции Шеннона и связанные с ней проблемы неотрицательности, Журнал комбинаторики. 6:4 с.320-331 (1981), 30–35

[8] Мучник, Андрей А. (2002). «Условная сложность и коды» . Теоретическая информатика . 271 (1–2): 97–109. дои : 10.1016/S0304-3975(01)00033-0 .

[9] Н. К. Верещагин, М. В. Вьюгин, Независимые программы минимальной длины для перевода между заданными строками, Учеб. 15-я Энн. Конф. Вычислительная сложность, 2000, 138–144.

[10] М.Хаттер, Универсальный искусственный интеллект: последовательные решения, основанные на алгоритмической вероятности, Springer, 1998.

[11] М. М. Деза, Э. Деза , Энциклопедия расстояний, Springer, 2009, дои : 10.1007/978-3-642-00234-2

[12] «InfoTopo: Анализ данных топологической информации. Глубокое статистическое обучение без и с учителем — Обмен файлами — Github» . github.com/pierrebaudot/infotopopy/ . Проверено 26 сентября 2020 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]