Меня зовут Иван Душенко и я ведущий системный аналитик в Лиге Цифровой Экономики. Последняя задача, над которой я работал — повышение точности семантического поиска изображений. В этой статье я расскажу про существующие меры расстояния и что это вообще такое. А ещё попробуем улучшить косинусное расстояние — самую популярную меру в мире машинного обучения.

Расстояние между объектами играет ключевую роль в анализе, классификации и кластеризации. Меры расстояния позволяют количественно оценивать схожесть и различия между векторами признаков, что является основой для многих алгоритмов, таких как k-ближайших соседей, методов кластеризации и векторного поиска.

Существует множество различных мер расстояния, каждая из которых имеет свои особенности и области применения. Среди наиболее распространенных — расстояния L1 (манхэттенское), L2 (евклидово), Lp (расстояние Минковского), L∞ (расстояние Чебышева), косинусное расстояние и расстояние Махаланобиса. Эти меры могут значительно различаться по своим математическим свойствам и интерпретации.

Например, расстояние L1 хорошо подходит для задач, где важна устойчивость к выбросам, тогда как L2 часто используется в контексте оптимизации и анализа данных с нормальным распределением. Косинусное расстояние, в свою очередь, позволяет оценивать угловое сходство между векторами, что особенно полезно в текстовой аналитике и обработке естественного языка. Правильный выбор меры расстояния может существенно повлиять на результаты анализа данных и эффективность алгоритмов.

Примеры

Для иллюстрации применения различных мер расстояния я буду использовать небольшой датафрейм (160 строк), который содержит ссылки на изображения, метки класса (13 классов) и векторы, рассчитанные квантованной мультимодальной моделью ruCLIP, предоставленной сообществу командой Сбера.

Расстояния L1 и L2

Расстояние L1 (Манхэттенское расстояние)

Расстояние L1, также известное как манхэттенское расстояние или расстояние городских кварталов, измеряет дистанцию между двумя точками в пространстве, учитывая только перемещение по осям координат. Эта метрика названа в честь уличной планировки Манхэттена, где движение происходит по прямым линиям вдоль улиц.

Формула

Для двух точек A(x1, y1) и B(x2, y2) в двумерном пространстве манхэттенское расстояние определяется так: 

Пример

Если у нас есть две точки A(2,3) и B(5,7), то манхэттенское расстояние между ними рассчитывается следующим образом: 

Свойства

Манхэттенское расстояние не зависит от вращения системы координат.

Оно менее чувствительно к выбросам по сравнению с евклидовой метрикой, так как не возводит разности в квадрат.

Применение

Манхэттенское расстояние часто используется в задачах, где важно учитывать перемещение по сетке, например, в робототехнике или при решении головоломок типа «Пятнашки», где оно служит эвристической функцией для поиска оптимального решения.

Проиллюстрируем применение:

import torch
import ruclip
device = torch.device('cuda' if torch.cuda.is_available() else 'cpu')
model, processor = ruclip.load("ruclip-vit-base-patch32-384", device=device)

predictor = ruclip.ONNXPredictor(
    clip_textual_model_path="models/clip_textual_test_infer.onnx",
    clip_image_model_path="models/clip_visual_test_infer_quant.onnx",
    clip_processor=processor,
    device=device,
    bs=512
)
from io import BytesIO
import requests
from PIL import Image
import pandas as pd

df = pd.read_csv('images.csv', delimiter=';')

def load_image(url):
    try:
        response = requests.get(url, timeout=15)
        response.raise_for_status()  # Проверка на ошибки HTTP
        return Image.open(BytesIO(response.content))
    except Exception as e:
        print(f"Error loading image from {url}: {e}")
        return None  # Возвращаем None в случае ошибки


df['embedding'] = df['url'].apply(load_image)
df.dropna(inplace=True)
df['embedding'] = df['embedding'].apply(lambda content: predictor.get_image_latents([content]))
import matplotlib.pyplot as plt
import requests
from PIL import Image
from io import BytesIO

# Функция для отображения изображений
def display_images(urls):
    plt.figure(figsize=(12, 6))

    for i, url in enumerate(urls):
        try:
            response = requests.get(url)
            img = Image.open(BytesIO(response.content))
            plt.subplot(2, 5, i + 1)  # 2 ряда и 5 столбцов
            plt.imshow(img)
            plt.axis('off')  # Отключаем оси для чистоты отображения
            plt.title(f'Image {i + 1}')
        except Exception as e:
            print(f"Error loading image from {url}: {e}")

    plt.tight_layout()
    plt.show()

search_query = 'лиса'
query_latents = predictor.get_text_latents([search_query])

# Функция для вычисления L1 дистанции
def l1_distance(vector):
    return torch.sum(torch.abs(vector - query_latents)).item()  # Вычисляем L1 дистанцию

# Применяем функцию к каждому вектору в столбце 'embedding'
df['l1_distance'] = df['embedding'].apply(l1_distance)

# Сортируем DataFrame по L1 дистанции
sorted_df = df.sort_values(by='l1_distance', ascending=True)

# Получаем лучшие совпадения
top_matches = sorted_df.head(10)

display_images(top_matches['url'].tolist())

Прекрасный результат!

Буханку ищет хуже.

Расстояние L2 (Евклидово расстояние)

Расстояние L2, известное как евклидово расстояние — наиболее распространенная мера расстояния в евклидовой геометрии. Оно измеряет кратчайшее расстояние между двумя точками в пространстве.

Формула

Для двух точек A(x1, y1) и B(x2, y2): 

Пример

Для тех же точек A(2, 3) и B(5, 7): 

Применение:

import numpy as np
def l2_distance(vector_a):
    # Вычисляем L2 дистанцию
    distance = np.sqrt(np.sum((vector_a.numpy() - query_latents.numpy()) ** 2))
    return distance

search_query = 'буханка'
query_latents = predictor.get_text_latents([search_query])
# Применяем функцию к каждому вектору в столбце 'embedding'
df['l2_distance'] = df['embedding'].apply(l2_distance)

# Сортируем DataFrame по L2 дистанции
sorted_df = df.sort_values(by='l2_distance', ascending=True)

# Получаем лучшие совпадения
top_matches = sorted_df.head(10)
display_images(top_matches['url'].tolist())

Гораздо лучше.

Сравнение L1 и L2 

Сложность вычислений: Расстояние L1 проще вычисляется, так как требует только суммирования абсолютных значений разностей координат. Евклидово расстояние требует вычисления квадратов разностей и извлечения квадратного корня.

Чувствительность к выбросам: L1 менее чувствительно к выбросам по сравнению с L2. Это делает его предпочтительным выбором в задачах с потенциальными выбросами.

Расстояние Lp (расстояние Минковского)

Расстояние Lp является обобщением расстояний L1 и L2, позволяя использовать различные значения параметра p для определения расстояния между двумя точками в пространстве. Эта мера расстояния часто используется в математике и машинном обучении для анализа данных, поскольку она предоставляет гибкость в выборе метрики в зависимости от конкретных требований задачи.

Общее определение

Расстояние Lp между двумя точками A и B в n-мерном пространстве определяется следующей формулой: 

где xi и yi — координаты точек A и B, соответственно, а p — параметр, который может принимать значения от 1 до бесконечности.

Примеры различных значений p

p=1: В этом случае расстояние L1 (манхэттенское расстояние) измеряет сумму абсолютных разностей координат. Это расстояние полезно в ситуациях, где необходимо учитывать перемещение по прямым линиям.

p=2: Это стандартное евклидово расстояние, которое измеряет кратчайшее расстояние между двумя точками в пространстве. Оно часто используется в задачах кластеризации и классификации.

p=∞: Расстояние L∞ (или максимальное расстояние) определяется как максимальная абсолютная разность между координатами двух точек: 

Чаще всего p устанавливают равным количеству измерений пространства.

Расстояние L∞ (расстояние Чебышева)

Расстояние L∞, также известное как максимальное расстояние или расстояние Чебышева, является одной из мер расстояния, которая измеряет максимальную абсолютную разницу между соответствующими координатами двух точек в пространстве. Эта метрика полезна в ситуациях, когда важно учитывать наибольшее отклонение по одной из координат.

Определение

Расстояние L∞ между двумя точками A(x1, y1, …, xn) и B(y1, y2, …, yn) в n-мерном пространстве определяется следующим образом: 

Это означает, что расстояние равно максимальному значению абсолютной разности между соответствующими координатами двух точек.

Пример

Рассмотрим две точки в двумерном пространстве: A(2, 3) и B(5, 7). Расстояние L∞ между этими точками рассчитывается следующим образом: 

В этом примере максимальная разность по координатам равна 4.

Применение:

def linf_distance(vector_a):
    # Вычисляем L∞ дистанцию
    distance = np.max(np.abs(vector_a.numpy() - query_latents.numpy()))
    return distance

search_query = 'лиса'
query_latents = predictor.get_text_latents([search_query])
# Применяем функцию к каждому вектору в столбце 'embedding'
df['linf_distance'] = df['embedding'].apply(linf_distance)

# Сортируем DataFrame по L1 дистанции
sorted_df = df.sort_values(by='linf_distance', ascending=True)

# Получаем лучшие совпадения
top_matches = sorted_df.head(10)
display_images(top_matches['url'].tolist())

Результат не впечатляет. Возможно, это связано с особенностями семантического пространства именно этой модели.

Проблема L-мер

К сожалению, все L-меры «ломаются» в искажённых пространствах, т. е. таких, в которых значения не нормированы. К примеру, если векторы имеют координаты по одной оси в пределах от 0 до 1, а по другой — от 0 до 10, то вклад координат по второй оси в L-расстояние в 10 раз больше. Одной из попыток исправить это стало расстояние Махаланобиса.

Расстояние Махаланобиса

Расстояние Махаланобиса — это мера, которая учитывает корреляцию между переменными и позволяет оценивать расстояние между многомерными векторами с учетом их распределения. 

Определение

Расстояние Махаланобиса определяется как расстояние от многомерного вектора до центра массы (среднего значения) в пространстве, учитывающем ковариацию между переменными. 

Вычисляется по следующей формуле: 

где: x — вектор характеристик, μ — вектор средних значений,

S−1 — обратная ковариационная матрица.

Если ковариационная матрица является единичной, то расстояние Махаланобиса становится равным евклидову расстоянию.

Проще говоря

Представим, что у нас есть множество точек, эллипсоидально расположенных в двумерном пространстве, и нам нужно посчитать дистанцию между двумя точками (красные на изображении).

Вся идея метода сводится к тому, что перед определением расстояния мы нормируем множество на его дисперсии и получаем вместо эллипса круг. После этого считаем расстояние. Для этого примера евклидово (поскольку пространство двумерно).

Преимущества и недостатки

Преимущества:

• Учитывает корреляции между переменными, что делает его более точным при анализе многомерных данных.

• Инвариантно к масштабу, что позволяет использовать его для данных с различными единицами измерения.

Недостатки:

• Требует вычисления ковариационной матрицы, что может быть проблематично при малом объеме данных или при наличии выбросов.

• Из-за того, что эта мера применима только если точки расположены эллипсоидально, и расположение точек должно быть плотным (а чаще всего это не так), адекватных результатов в векторном поиске у меня получить не удалось.

Какую L-меру выбрать

Обычно используют Lp меру, где p равно количеству измерений пространства. Т. е. для двумерного пространства это евклидово расстояние, для трёхмерного — L3 и т. д. И тут есть нюанс: в машинном обучении обычно мы используем значительное количество измерений. В моём случае их 512. Если вспомнить формулу, то нам придётся возводить числа в 512 степень, что кажется нерациональным. Предлагаю посмотреть на вопрос с другой стороны: что меняется при добавлении нового измерения?

В L1 учитывается только перемещение по осям координат. В L2 возводится в квадрат разность координат, что увеличивает вклад наибольшей разности в итоговый показатель. При Lp этот эффект становится всё более ярко выраженным, с увеличением значения p и в пределе (Linf) остаётся только максимальная абсолютная разница между соответствующими координатами. Таким образом, когда мы сталкиваемся с достаточно большим количеством измерений, можно пренебречь некоторой точностью в пользу вычислительной эффективности и использовать Linf. Но это нужно проверять эвристически: если какое-то из измерений не нормировано, ничего не получится, как в примере выше.

Расстояние Махаланобиса выбирают реже из-за сложности расчёта и требовательности к объёму данных. К тому же эта мера применима, только если точки расположены эллипсоидально.

Косинусное расстояние

Косинусное расстояние — это популярная мера, используемая для оценки схожести между двумя векторами в многомерном пространстве. Эта метрика основана на вычислении косинуса угла между двумя векторами, что позволяет оценить, насколько они направлены в одну сторону, независимо от их длины. Это делает косинусное расстояние особенно полезным в задачах, связанных с текстовой аналитикой и обработкой естественного языка.

Определение

Косинусное расстояние определяется как: 

где A⋅B — скалярное произведение векторов A и B, а ∣∣A∣∣ и ∣∣B∣∣ — нормы (длины) этих векторов. 

Преимущества и недостатки

Преимущества:

• Косинусное расстояние не так сильно зависит от длины векторов, что делает его полезным для работы с разреженными данными (например, текстами).

Недостатки:

• Косинусное расстояние не учитывает абсолютные значения векторов, а только их направление, что может быть недостатком в некоторых ситуациях.

• В случаях, когда важна информация о длине векторов (например, при анализе количественных данных), использование косинусного расстояния может привести к неверным выводам.

Пример расчета

Рассмотрим два вектора: A=[1, 2, 3] B=[4, 5, 6]

Сначала вычислим скалярное произведение: A*B=1*4+2*5+3*6=4+10+18=32

Теперь найдем нормы векторов:

Теперь можем подставить значения в формулу для косинусного расстояния: 

Расчет этого выражения даст нам значение косинусного расстояния между векторами 

A и B.

Применение:

from sklearn.metrics.pairwise import cosine_distances

def cos(vector):
    return cosine_distances(vector, query_latents)

# Пример использования
search_query = 'лиса'
query_latents = predictor.get_text_latents([search_query])  # Предполагаем, что predictor определен

# Применяем функцию к каждому вектору в столбце 'embedding'
df['cosine_distance'] = df['embedding'].apply(cos)

df['cosine_distance'] = df['cosine_distance'].astype(float)

# Сортируем DataFrame по косинусному расстоянию
sorted_df = df.sort_values(by='cosine_distance', ascending=True)

# Получаем лучшие совпадения
top_matches = sorted_df.head(10)

# Отображаем изображения из URL
display_images(top_matches['url'].tolist())

Выглядит идеально, но если у модели не хватает каких-то когнитивных способностей или знаний, не поможет ничего. Вот пример поиска героев сериала Arcane:

Модель явно не знает о таком сериале и правильно выдала только те изображения, на которых смогла прочитать название. Вот ещё один пример, запрос «вов»:

Модель явно понимает, что речь о компьютерной игре, но не знает подробностей, из-за чего в результаты попадает и Starcraft, и Warhammer, и даже сериал Arcane.

Проблемы косинусного расстояния

К сожалению, косинусное расстояние имеет несколько неприятных свойств.

1. Если оба вектора находятся на прямой, проходящей через начало координат, их косинусное расстояние будет равно нулю, даже если L-расстояние большое. Как можно увидеть на изображении ниже, все точки на полуокружности равноудалены (по евклидовому расстоянию) от центра вращения, но косинусное расстояние меняется.

2. При равном евклидовом расстоянии точек косинусное расстояние будет снижаться по мере удаления от начала координат. Об этом свидетельствует то, что на графике правая сторона косинусного расстояния более крутая.

Существует также миф о том, что косинусная дистанция устойчива к ненормированным пространствам. Представьте график, у которого ось X в миллиметрах, а ось Y — в километрах :) Не «устойчива», а «устойчивее, чем L-меры».

Сбалансированная мера расстояния

А теперь давайте поэкспериментируем и попробуем улучшить косинусное расстояние. Основное, от чего хотелось бы избавиться — это «слепота» косинусного расстояния к различиям точек, лежащих близко к прямой, проходящей через начало координат. А что, если «посмотреть» на векторы не из одной точки отсчёта, а из нескольких? Для этого построим второе косинусное расстояние для точек, повёрнутых на 90 градусов. Это равносильно тому, что мы взяли за точку отсчёта левый верхний угол.

Как можно увидеть на графике, функция расстояния стала менее изменчивой (именно к этому мы и стремились), хоть и не идеальной. Стоит оговориться, что в таком подходе отдельным вопросом становится точка вращения данных.

Выводы

В результате у нас получилось сбалансировать косинусное расстояние таким образом, что его поведение стало ближе к L-мерам и пропали основные недостатки. Однако полноценно от ненормированных данных не спасает ничего. 

Кроме того, в предложенном методе выбор центра вращения может быть нетривиальным вопросом. Можно также рассмотреть вариант линейного смещения вместо поворота (поворот в многомерном пространстве даже просто представить сложно). 

Использование нескольких точек отсчета может помочь лучше захватить структуру данных. Это может быть особенно полезно в многомерных пространствах. Но следует также заметить, что подобные трюки будут иметь эффект, только если семантическое пространство имеет высокую плотность. Из-за «проклятия размерности» такие пространства зачастую более разреженные, чем нам кажется.