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

Информационное расстояние — это расстояние между двумя конечными объектами (представленными в виде компьютерных файлов), выраженное как количество битов в кратчайшей программе, преобразующей один объект в другой или наоборот. универсальный компьютер . Это расширение колмогоровской сложности . ^[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] Перейти обратно: Перейти обратно: ^а ^б А. Н. Колмогоров, Три подхода к количественному определению информации, Проблемы информ. Передача, 1:1 (1965), 1–7

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

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

[BGLVZ98-4] Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и Ч. Беннетт, П. Гакс, М. Ли, П. М. Витаньи, В. Зурек, Информационная дистанция, Транзакции 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]