Информационное расстояние - Information distance

Информационное расстояние расстояние между двумя конечными объектами (представленными как компьютер 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

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

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

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

[BGLVZ98-4] а ^б ^c ^d ^е C.H. Беннетт, П. Гакс, М. Ли, П.М.Б. Витани, В. Зурек, Информационное расстояние, IEEE Transactions on Information Theory, 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-я Ann. Конф. Вычислительная сложность, 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]