Поиск ближайших соседей с помощью иерархического маленького мира — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Операции над структурой)
Строка 1: Строка 1:
 +
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 +
|+
 +
|-align="center"
 +
|'''НЕТ ВОЙНЕ'''
 +
|-style="font-size: 16px;"
 +
|
 +
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 +
 +
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 +
 +
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 +
 +
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 +
 +
''Антивоенный комитет России''
 +
|-style="font-size: 16px;"
 +
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 +
|-style="font-size: 16px;"
 +
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 +
|}
 +
 
'''Иерархический маленький мир''' (англ. ''Hierarchical Navigable Small World'') {{---}} структура данных, позволяющая эффективно искать <tex>k</tex> почти что ближайших соседей на больших множествах вершин.
 
'''Иерархический маленький мир''' (англ. ''Hierarchical Navigable Small World'') {{---}} структура данных, позволяющая эффективно искать <tex>k</tex> почти что ближайших соседей на больших множествах вершин.
 
Поиск ближайших соседей нужен в задачах [[Общие понятия|классификации]] и [[кластеризация|кластеризации]].
 
Поиск ближайших соседей нужен в задачах [[Общие понятия|классификации]] и [[кластеризация|кластеризации]].

Версия 06:43, 1 сентября 2022

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

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

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

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Иерархический маленький мир (англ. Hierarchical Navigable Small World) — структура данных, позволяющая эффективно искать [math]k[/math] почти что ближайших соседей на больших множествах вершин. Поиск ближайших соседей нужен в задачах классификации и кластеризации.

По своей концепции напоминает список с пропусками.

Применение

Представим себе ситуацию:

  • У социальной сети есть [math]10^{11}[/math] пользовательских фотографий с отмеченными лицами на них.
  • По новой фотографии требуется быстро узнать кто на ней и предложить пользователю отметить этого человека.

Возможный процесс:

  1. Обучаем FaceNet выдавать [math]128[/math]-мерные вектора по изображению лица, такие, что у фотографий одного человека похожие значения векторов.
  2. Добавляем [math]10^{11}[/math] векторов в иерархический маленький мир.
  3. При добавлении новой фотографии, вычисляем соответствующий лицу вектор.
  4. Ищем [math]k[/math] его ближайших соседей.
  5. Классифицируем лицо с использованием ядер сглаживания.
  6. Если пользователь подтвердил нашу догадку, добавляем этот вектор в иерархический маленький мир.

Маленький мир

Жадный поиск ближайшего соседа. Чёрные ребра — короткие связи с соседями в небольшом радиусе [math]R[/math], красные рёбра — длинные связи, созданные по какой-то эвристике, обеспечивающие логарифмическое мат. ожидание длины пути. Оригинал

Маленький мир (англ. Small World) — граф, в котором мат. ожидание кратчайшего пути между двумя случайно выбранными вершинами растёт пропорционально [math]\log{N}[/math]. Но при этом средняя степень вершины мала.

Для маленького мира на точках в Евклидовом пространстве жадный поиск [math]k[/math] ближайших соседей будет выглядеть так:

knn(V, E, request, m, k):
    W = [math]\emptyset[/math]  // Ближайшие к q вершины. 
    C = [math]\emptyset[/math]  // Вершины, которые предстоит посетить. 
    V = [math]\emptyset[/math]  // Посещённые вершины. 
    for i = 1 to m
        C = С [math]\bigcup[/math] [math]random_v[/math] v [math]\in[/math] G
        TN = [math]\emptyset[/math]  // Ближайшие вершины в этом проходе.
        while true
            u = {q1 | [math]\forall[/math] q2 [math]\in[/math] C, |q - q1| <= |q - q2|} // Ближайшая к q вершина из C. 
            C = C [math]\setminus[/math] u
            if u дальше чем k-й элемент W
                break
            for e: (u, e) in G
                if e [math]{\notin}[/math] V
                    C = C [math]\bigcup[/math] e
                    V = V [math]\bigcup[/math] e
                    TN = TN [math]\bigcup[/math] e
        W = W [math]\bigcup[/math] TN
    return k ближайших к q вершин из W

Расстояние между вершинами графа может измеряться различными метриками.
Очевидный недостаток этого алгоритма — опасность свалиться в локальный минимум, остановившись в каком-то кластере. С увеличением числа [math]m[/math], вероятность такого застревания экспоненциально падает.

Описание структуры

Иерархический Маленький мир — слоистая структура графов. На нулевом слое представлены все [math]N[/math] вершин из исходной выборки. Вершина, присутствующая на уровне [math]L[/math] так же присутствует на уровне [math]L + 1[/math] с вероятностью [math]P[/math]. Т.е. кол-во слоёв растет как [math]O(\log N)[/math]. Количество соседей каждой вершины на каждом уровне ограниченно константой, что позволяет делать запросы на добавление и удаление вершины за [math]O(\log N)[/math].

Иерархический маленький мир. Источник

Операции над структурой

Поиск ближайших соседей в слое

Жадно идём по уровню в сторону запроса.

searchLayer(q, ep, ef, layer):
    // Входные данные: иерархия графов hnsw, запрос q, входные точки ep, искомое количество ближайших соседей ef, номер слоя layer.
    // Возвращает: ef ближайших соседей q в слое layer.
    W = {ep}  // Ближайшие к q вершины. 
    C = {ep}  // Вершины, которые предстоит посетить. 
    V = {ep}  // Посещённые вершины. 
    while C != [math]\emptyset[/math]
        u = {q1 | [math]\forall[/math] q2 [math]\in[/math] C, |q - q1| <= |q - q2|} // Ближайшая к q вершина из C. 
        f = {q1 | [math]\forall[/math] q2 [math]\in[/math] W, |q - q1| >= |q - q2|} // Самая дальняя от q вершина из W. 
        if |u - q| > |f - q|
            break // Мы в локальном минимуме. 
        for e : (u, e) in G
            if e [math]{\notin}[/math] V
                V = V [math]\bigcup[/math] e
                f = {q1 | [math]\forall[/math] q2 [math]\in[/math] W, |q - q1| >= |q - q2|} // Самая дальняя от q вершина из W. 
                if |e - q| < |f - q| or |W| < ef
                    C = C [math]\bigcup[/math] e
                    W = W [math]\bigcup[/math] e
                    if |W| > ef
                        W = W \ f
    return W

Поиск ближайших соседей во всей структуре

Жадный поиск вершины. Оригинал
  1. Идём с верхнего уровня до первого:
    1. Жадно ищем ближайшую к [math]q[/math] вершину на текущем уровне.
    2. Спускаемся в соответствующую соседу вершине на уровень ниже.
  2. На нулевом уровне жадно ищем [math]k[/math] ближайших соседей.
knn(hnsw, q, k, ef):
    // Входные данные: иерархия графов hnsw, запрос q, искомое количество ближайших соседей  k, количество кандидатов при поиске ef. 
    // Возвращает: k ближайших соседей q. 
    W = [math]\emptyset[/math]  // Ближайшие к q вершины. 
    mL = |hnsw| - 1
    ep = [math]random_v[/math] v [math]\in[/math] hnsw[mL]
    for level = mL to 1
        W = searchLayer(hnsw, q, ep, ef=1, level) // На каждом уровне, кроме нижнего мы ищем всего одну ближайшую вершину. 
        ep = W
    W = searchLayer(hnsw, q, ep, ef, lc=0)
    return k ближайших к q вершин из W

Вставка элемента

  1. Случайным образом выбираем максимальный слой, на котором будет представлена [math]q[/math].
  2. На каждом уровне, где будет представлена [math]q[/math], сверху вниз:
    1. Жадно ищем [math]m[/math] ближайших к [math]q[/math] вершин.
    2. Добавляем связи [math]q[/math] с ними.
    3. Удаляем лишние связи у новообразовавшихся соседей.
insert(hnsw, q, m, mMax, ef, mL):
    // Входные данные: иерархия графов hnsw, запрос на добавление q, желаемое количество связей m, максимальное количество связей вершины 
    //       на одном слое mMax, количество кандидатов при поиске ef, коэффициент выбора высоты mL. 
    // Возвращает: hnsw с вставленным элементом q. 
    W = [math]\emptyset[/math]  // Ближайшие к q вершины. 
    mL = |hnsw| - 1
    ep = [math]random_v[/math] v [math]\in[/math] hnsw[mL]
    qL = -ln(rand(eps, 1.0)) * mL // Верхний слой для вершины q. 
    for level = mL to qL + 1
        W = searchLayer(q, ep, ef=1, level)
        ep = W
    for level = min(mL, qL) to 0
        W = searchLayer(q, ep, ef, level)
        neighbours = M ближайших к q вершин из W
        for n [math]\in[/math] neighbours:
            // Добавляем двусторонние связи между n и q. 
            hnsw[level] = hnsw[level] [math]\bigcup[/math] (n, q)
            hnsw[level] = hnsw[level] [math]\bigcup[/math] (q, n)
            
            nNeighbours = {v| (v, n) in hnsw[level]} // Ищем всех соседей n на уровне level. 
            // Убираем лишние связи, если требуется. 
            if nNeighbours.Count() > mMax
                // Самая дальняя от n вершина, смежняя с ней. 
                v = {q1 | (q2, n) [math]\in[/math] nNeighbours & [math]\forall[/math]q2 [math]\in[/math] hnsw[level], |q - q1| >= |q - q2|}
                hnsw[level] = hnsw[level] [math]\setminus[/math] (n, v)
                hnsw[level] = hnsw[level] [math]\setminus[/math] (v, n)
        ep = W
    if qL > mL
        for level = mL to qL
            hnsw.append({q, {}})

Практическое использование

В библиотеке Hnswlib есть реализация иерархического маленького мира. Эта библиотека написана на C++, с биндингами на python. Пример использования:

import hnswlib
import numpy as np

dim = 128
num_elements = 10000

# Создаём тестовые данные.
data = np.float32(np.random.random((num_elements, dim)))
data_labels = np.arange(num_elements)

# Создаём иерархический маленький мир в L2.
# Возможные метрики — l2, cosine, ip (L2, косинус угла между векторами, скалярное произведение).
p = hnswlib.Index(space = 'l2', dim = dim)

# Инициализируем структуру.
p.init_index(max_elements = num_elements, ef_construction = 200, M = 16)

# Добавляем данные (можно вызывать много раз).
p.add_items(data, data_labels)

# Настраиваем качество, выставляя ef:
p.set_ef(50) # ef должно быть > k

# Делаем запрос.
# k - количество ближайших вершин
labels, distances = p.knn_query(data, k = 1)

См. также

Источники информации