WikiDer > Информационное расстояние

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

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

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

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

с ${ displaystyle p}$ конечная двоичная программа для фиксированного универсальный компьютерс входами конечных двоичных строк ${ displaystyle x, y}$. В ^[4] доказано, что${ Displaystyle ID (х, y) знак равно Е (х, у) + О ( журнал CDOT макс {К (х середина у), К (у середина х) })}$ с

${ Displaystyle Е (х, у) = макс {К (х середина у), К (у середина х) },}$

куда ${ Displaystyle К ( cdot mid cdot)}$ это Колмогоровская сложность определяется ^[1] типа префикса.^[5] Этот ${ Displaystyle Е (х, у)}$ это важное количество.

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

Позволять ${ displaystyle Delta}$ быть классом верхний полувычислитель расстояния ${ Displaystyle D (х, у)}$ которые удовлетворяют плотность условие

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

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

Метричность

Расстояние ${ Displaystyle Е (х, у)}$ это метрика до добавки ${ Displaystyle О ( журнал. макс {К (х середина у), К (у середина х) })}$член в метрике (в) равенствах.^[4] Вероятностная версия метрики действительно уникальна, как показал Хан в 1981 году.^[7]

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

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

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

Программы для преобразования между объектами ${ displaystyle x}$ и ${ displaystyle y}$ также можно сделать минимальное перекрытие. Существует программа ${ displaystyle p}$ длины ${ Displaystyle К (х середина у)}$ до дополнительного срока ${ Displaystyle О ( журнал ( макс {К (х середина у), К (у середина х) }))}$ что отображает ${ displaystyle y}$ к ${ displaystyle x}$ и имеет небольшую сложность, когда ${ displaystyle x}$ известен (${ Displaystyle К (п середина х) приблизительно 0}$). Поменяв местами два объекта, у нас есть другая программа^[8] Имея в виду параллелизм между Теория информации Шеннона и Колмогоровская сложность теории, можно сказать, что этот результат параллелен Слепиан-Волк и Кёрнер – Имре Цисар – Мартон теоремы.

Приложения

Теоретическая

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

Практичный

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

Рекомендации

Связанная литература

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