18 оттенков термина 'distance' (из теории информации)
Продираясь через смыслы книги по теории информации из моей прошлой заметки, я заметил, что в этой дисциплине много разных "дистанций" (distance). Я насчитал 18 штук, пришлось отложить перевод в сторону и разложить их по полочкам у себя в голове. Поехали.
1. Попарное расстояние / Pairwise Distance
Допустим, мы хотим организовать форум переводчиков и нужно узнать, насколько далеко участники живут друг от друга, чтобы выбрать оптимальное место проведения. Для этого мы не выводим какую-то общую цифру, а делаем таблицу-шахматку, где пересечении каждых двух участников указано расстояние между ними.
Это и есть попарное расстояние — не какой-то особый способ измерения, а сам принцип оценивания дистанции между каждой парой объектов в наборе данных.
В теории информации это один из базовых шагов: прежде чем анализировать систему или кодировать сообщения, ученые смотрят, как соотносятся друг с другом все элементы по отдельности.
2. Евклидово расстояние / Euclidean Distance
Окей. Как измерять это расстояние? Самое первое, что приходит в голову - померять расстояние линейкой по карте. То есть берем карту страны, проводим прямую линию от одного участника к другому. Ну или берем глобус - и тоже проводим мысленно линию. Вот эта дистанция по прямой в двухмерном или трехмерном пространстве - которую мы так часто считали в школе на уроках геометрии — и будет Евклидово расстояние.
В теории информации оно воспринимается чуток иначе — данные представляются в виде точек в пространстве (ну типа, по осям можно отложить рост, вес и возраст участника).
Евклидово расстояние тогда будет считаться между точками и в таком случае покажет, насколько участники антропометрически похожи друг на друга.
Тут правда есть большой минус — если один параметр сильно вырастет, он перетянет все внимание на себя.
3. Квадрат евклидова расстояния / Squared L2-Distance
Иногда в математике прямая линия — это неудобно из-за знака корня в формуле Пифагора. Так вот если мы просто не будем извлекать корень, мы получим квадрат евклидова расстояния (или squared L2). В чем плюс такого подхода?
Представьте, что вы бросаете дротики в мишень: вам важно не просто, насколько вы промахнулись, а насколько ваш промах штрафуется.
Вот в теории информации этот квадрат используется постоянно: он сильнее наказывает за большие ошибки, чем за маленькие. Если вы промахнулись на 2 см, штраф будет 4, а если на 5 см — штраф уж 25.
Такой подход помогает алгоритмам более агрессивно искать возможности, чтобы избежать огромных сбоев при передаче сигналов.
4. Манхэттенское расстояние (Расстояние L1) / L1-Distance
Но что делать, если «по прямой» ходить нельзя? Представьте, что вы бродите по улицам Нью-Йорка, которые образуют ровные кварталы.
Чтобы дойти до нужного дома, придется идти строго зигзагами: три квартала на север, два квартала на восток. Сумма этих шагов называется расстоянием L1 (или Манхэттенским расстоянием).
В теории информации эта концепция часто используется, когда параметры нельзя «смешивать» через квадратный корень: мы просто складываем абсолютные модули различий по каждому признаку по отдельности, как шаги по пиксельной сетке.
5. Геодезическое расстояние / “Geodesic” Distance
Усложним задачу: нам нужно долететь на самолете из Москвы во Владивосток. Если мы приложим линейку к плоской карте, мы явно ошибемся — ведь Земля — круглая. Кратчайший путь по искривленной поверхности сферы (дуга большого круга) — это и есть геодезическое расстояние.
В теории информации «геодезия» возникает, когда наши данные лежат не на плоском столе, а зажаты сложными правилами (например, законами физики). Если мы плавно меняем настройки нейросети, её состояния движутся по хитрой «кривой» поверхности, и «геодезическое расстояние» показывает истинную длину этого пути без срезания углов через пустоту.
6. Взвешенное «расстояние» / Weighted “Distance”
Вернемся на переводческую тусовку: мы выбираем, с кем договориться о встрече кулуарно, оценивая «дистанцию интересов» с тем или иным участником. Но для вас любовь участника к техническим дисциплинам имеет огромный вес, а то, какой рисунок кавычек предпочитает коллега — почти нулевой.
Вот вы и умножаете важные различия на большой коэффициент, а неважные — на крошечный. Это называется взвешенным расстоянием.
В теории кодирования и связи разным битам информации присваивают разные веса: ошибка в бите, отвечающем за знак числа (+ или -), гораздо критичнее, чем ошибка в последнем знаке после запятой. Взвешивание помогает алгоритмам защищать самые важные участки данных.
7. Расстояние Хэмминга / Hamming Distance
Перейдем от чисел к тексту. Вы переписываетесь в чате и делаете страшную опечатку: вместо слова «извИните» отправляете «извЕните». К счастью, ваш собеседник не граммар-наци и без проблем понимает вас. Почему?
Потому что между этими словами расстояние Хэмминга равно единице — ровно в одной позиции буквы различаются. Расстояние Хэмминга считает количество несовпадающих символов в двух строках одинаковой длины. Мы часто это видим в «кошках» типа Trados/Smartcat, когда вызываем функцию Concordance.
Это база в теории кодирования: когда файлы летят по интернету, из-за помех «10110» может превратиться в «10010». Посчитав расстояние Хэмминга между отправленным и полученным кодом, принимающий компьютер может рассчитать, сколько битов исказилось, и исправить ошибку.
8. Расстояние полной вариации / TV-Distance (Total Variation Distance)
Представьте, что вы с другом по дороге на форум решили зайти в клуб игровых автоматов. У вас шансы выиграть золото, серебро или бронзу составляют [60%, 30%, 10%], а у друга — [40%, 40%, 20%]. Насколько различаются ваши игровые условия в целом?
Расстояние полной вариации находит самое большое возможное различие в вероятностях для одного и того же события (в нашем случае — для золота: 60% - 40% = 20%). Это самый простой и строгий способ сказать: «Два этих случайных процесса отличаются максимум на столько-то процентов».
9. Расстояние Хеллингера / Hellinger Distance
Иногда нам нужно сравнить два вероятностных распределения, но так, чтобы редкие события не ломали математику, а само расстояние всегда красиво укладывалось в рамки от 0 до 1 (где 0 — близнецы, 1 — вообще не пересекаются). Для этого ученые берут квадратные корни из вероятностей и считают между ними аналог евклидова расстояния. Это и есть расстояние Хеллингера.
Если менее абстрактно, то представьте, что вы с другом сравниваете свои библиотеки по жанрам. Если вы читаете только иронические детективы, а он — только Стругацких и Лема, то расстояние Хеллингера будет равно 1.
В теории информации это расстояние используется в системах распознавания речи или текста, где нужно быстро понять, похожи ли два случайных подбора слов друг на друга.
10. Расстояние Бхаттачарьи / Bhattacharyya Distance
Это близкий родственник расстояния Хеллингера, но он скорее оценивает степень наложения (overlap).
Например, врач-диагност сравнивает графики распределения плотности тканей на снимках здорового органа и органа с патологией. Расстояние Бхаттачарьи покажет, насколько эти графики пересекаются.
Если графики распределения вероятностей вообще не пересекаются, это расстояние уходит в бесконечность.
В теории информации и компьютерном зрении его используют, чтобы оценить, насколько легко алгоритм может перепутать два класса объектов (например, кошку и собаку на размытом фото).
11. Дивергенция (Дистанция расхождения) / Divergence Distance
Отойдем немного в сторону непривычных вещей. Дело в том, что в теории информации часто нужны «расстояния», которые не работают как обычная линейка.
Мы привыкли, что от головы удава до хвоста удава расстояние будет тем же, что и от хвоста до головы — 38 попугаев.
В дивергенциях путь туда и путь обратно — это разные вещи (т. е. нарушается закон симметрии), поэтому слово «расстояние» тут частенько пишется в кавычках.
Возьмем, скажем, дистанцию между ошибками. Если вы переводите незнакомую тему, то ошибиться в термине, котором вы видите впервые — это нормально. Но ошибиться в термине из темы, с которой ты работаешь 30 лет — это катастрофа.
Другой пример, из медицины. Принять редкое заболевание за обычную простуду при анализе симптомов — это огромная статистическая ошибка. Принять простуду за редкое заболевание — ошибка другого масштаба и стоимости.
Дивергенции учитывают эту асимметрию направления и расстояние расхождения между реальностью и нашими представлениями.
12. Расстояние Кульбака — Лейблера / KL Distance (Kullback–Leibler Divergence
Самый знаменитый пример дивергенции и самый частый гость в ИТ-текстах про нейросети и LLM (включая ChatGPT). Представьте, что вы решили закодировать все свои сообщения другу, используя короткие символы для частых слов (типа «привет», «как») и длинные для редких. Но вы взяли статистику частоты слов из словаря Даля, а не из Тик-тока.
Расстояние Кульбака-Лейблера (KL-дивергенция) измерит, сколько лишних битов вы потратите на передачу сообщений из-за того, что ваша модель представлений о языке не совпадает с истинным распределением слов у молодежи (Тик-ток).
Она показывает плату за наше незнание или неточную оценку вероятностей.
13. Минимальное расстояние Ятракоса . Yatracos’ Minimum-Distance
Представьте, что перед вами кусок текста со случайными словами, и вы пытаетесь угадать, по какому закону они там перемешиваются/складываются. У вас есть несколько математических моделей-кандидатов. Как выбрать лучшую, если слов слишком много и они слишком запутанные?
Или же у вас есть огромный массив хаотичных медицинских данных (например, показатели тысяч датчиков реанимации) и вам нужно подобрать для них идеальную математическую модель, стандартные методы могут давать сбой из-за тяжелых хвостов распределений.
Минимальное расстояние Ятракоса — это специальный инструмент для подбора идеальной модели. Оно строит особую коллекцию «тестовых вопросов» (кубиков данных) и смотрит, какая из ваших моделей дает наименьшее отклонение от реальности (эмпирических данных) по всем тестам одновременно.
14. Минимальное расстояние Фитингофа / Fitingof Minimal Distance
Этот термин из мира сжатия данных и архиваторов (вроде ZIP, RAR и т. п.). Представьте, что вы набрали на клавиатуре случайный набор букв «АААБББААА». Насколько этот текст далек от абсолютно хаотичного, несжимаемого шума?
Расстояние Фитингофа измеряет, насколько структура вашего сообщения отличается от идеального «хаоса» (энтропии). По сути, оно показывает, можно ли сжать этот текст сильнее, найдя в нем скрытые закономерности и повторяющиеся паттерны, о которых вы —создатель текста — даже не задумывались.
15. Расстояние Вассерштейна (Метрика «землекопа») / Wasserstein Distance (Earth Mover's Distance)
Представьте, что во дворе насыпаны кучи песка, а вам нужно пересыпать их так, чтобы получился песчаный замок определенной формы. Каждую песчинку нужно перенести на какое-то расстояние. Вы по природе ленивы и не хотите делать эту работу или сделать с минимальными усилиями. Варианта не делать у вас нет, а чтобы сделать с минимальными усилиями, надо умножить массу песка на дистанцию переноса.
Это и есть расстояние Вассерштейна (в английском языке у этого термина более народный синоним — Earth Mover's Distance — дистанция землекопа).
В более научном применении, можно представить, что у вас есть одно распределение пикселей (скан МРТ пациента год назад) и второе распределение (скан сегодня). За год ткани немного сместились, опухоль уменьшилась. Обычные метрики скажут, что картинки «абсолютно разные», потому что пиксели не совпадают один в один.
Поэтому в ИТ-медицине это это расстояние используется, чтобы проанализировать старый снимок органа с новым, учитывая деформацию.
16. Расстояние Синкхорна / Sinkhorn Distance
Посчитать классическое расстояние Вассерштейна для миллионов пикселей в современных нейросетях — это адски долгая и дорогая по ресурсам задача, компьютер просто «задымится» и «прожжет» дыру в вашем бюджете.
Чтобы решить эту проблему, ученые добавили в алгоритм Вассерштейна капельку случайного хаоса (энтропии), которая разрешает песчинкам лететь чуть-чуть неидеально, зато супербыстро.
Это сглаженное и гораздо более быстро вычисляемое расстояние называется расстоянием Синкхорна.
Именно благодаря ему алгоритмы в машинном обучении могут довольно быстро, нередко в реальном времени, сопоставлять огромные массивы информации, переводить тексты и обрабатывать графику. Например, с его помощью сопоставляются белки, ищутся молекулы-кандидаты для лекарств и алайнятся многоязычные параллельные тексты.
17. Расстояние Орнштейна / Ornstein’s Distance (d-bar distance)
Теперь усложним задачу для алгоритма Вассерштейна. Представьте, что вы сравниваете не просто статичные кучи песка, а целые кинофильмы или непрерывные кардиограммы, где буквы/символы/данные зависят друг от друга (например, в английском после Q часто идет U). Как измерить разницу между двумя такими процессами во времени?
Расстояние Орнштейна (или d-метрика) — это способ применить идею «минимальной переделки» к случайным последовательностям. Оно определяет, какой минимальный процент букв в длинном изменяющемся потоке данных нужно перезаписать, чтобы один случайный процесс стал неотличим от другого с сохранением всей его внутренней структуры и зависимостей.
18. Расстояние Ле Кама / Le Cam Distance
Представьте, что у вас есть два разных дизайна клинических исследований лекарства, которые работают со случайными выборками пациентов. Расстояние Ле Кама измеряет дистанцию между самими этими экспериментами.
Если расстояние Ле Кама между двумя моделями экспериментов близко к нулю, это значит, что они содержат одинаковое количество полезной информации и следовательно — асимптотически эквивалентны.
На практике это означает математический потолок: какой бы крутой алгоритм вы ни создали, вы не сможете выжать из данных второго эксперимента больше информации, чем из первого.
Иными словами, это расстояние показывает границы нашей способности познавать мир по неполным данным.
Можно сделать вывод, что термин «distance» в ИТ и теории информации — это не физическое «расстояние», а мера различия, ошибки или информационного расхождения.