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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Маленький мир)
(Операции над структурой)
(не показаны 73 промежуточные версии 3 участников)
Строка 1: Строка 1:
'''Иерархический маленький мир''' (англ. ''Hierarchical Navigable Small World'') {{---}} структура данных, позволяющая эффективно находить K почти что ближайших соседей. По своей концепции напоминает [[список с пропусками]].
+
'''Иерархический маленький мир''' (англ. ''Hierarchical Navigable Small World'') {{---}} структура данных, позволяющая эффективно искать <tex>k</tex> почти что ближайших соседей на больших множествах вершин.
 +
Поиск ближайших соседей нужен в задачах [[Общие понятия|классификации]] и [[кластеризация|кластеризации]].
 +
 
 +
По своей концепции напоминает [[список с пропусками]].
 +
 
 +
== Применение ==
 +
Представим себе ситуацию:
 +
* У социальной сети есть <tex>10^{11}</tex> пользовательских фотографий с отмеченными лицами на них.
 +
* По новой фотографии требуется быстро узнать кто на ней и предложить пользователю отметить этого человека.
 +
 
 +
Возможный процесс:
 +
# Обучаем [https://github.com/davidsandberg/facenet FaceNet] выдавать <tex>128</tex>-мерные вектора по изображению лица, такие, что у фотографий одного человека похожие значения векторов.
 +
# Добавляем <tex>10^{11}</tex> векторов в иерархический маленький мир.
 +
# При добавлении новой фотографии, вычисляем соответствующий лицу вектор.
 +
# Ищем <tex>k</tex> его ближайших соседей.
 +
# Классифицируем лицо с использованием [[Метрический классификатор и метод ближайших соседей#Использование ядер сглаживания|ядер сглаживания]].
 +
# Если пользователь подтвердил нашу догадку, добавляем этот вектор в иерархический маленький мир.
  
 
==Маленький мир==
 
==Маленький мир==
 
[[Файл:SmallWorld_Greedy.png|мини|500px|Жадный поиск ближайшего соседа.  
 
[[Файл:SmallWorld_Greedy.png|мини|500px|Жадный поиск ближайшего соседа.  
Чёрные ребра {{---}} короткие связи с ближайшими соседями, красные рёбра {{---}} длинные связи, обеспечивающие малое мат. ожидание длины пути.
+
Чёрные ребра {{---}} короткие связи с соседями в небольшом радиусе <tex>R</tex>, красные рёбра {{---}} длинные связи, созданные по какой-то эвристике, обеспечивающие логарифмическое мат. ожидание длины пути.
 
[https://www.hse.ru/mirror/pubs/lib/data/access/ram/ticket/30/1551306415713d428dca7fd05f3d108fe8e66042c4/Approximate%20nearest%20neighbor%20algorithm%20based%20on%20navigable%20(Information%20Systems).pdf Оригинал]]]
 
[https://www.hse.ru/mirror/pubs/lib/data/access/ram/ticket/30/1551306415713d428dca7fd05f3d108fe8e66042c4/Approximate%20nearest%20neighbor%20algorithm%20based%20on%20navigable%20(Information%20Systems).pdf Оригинал]]]
 
'''Маленький мир''' (англ. ''Small World'') {{---}} граф, в котором мат. ожидание кратчайшего пути между двумя случайно выбранными вершинами растёт пропорционально <tex>\log{N}</tex>. Но при этом средняя степень вершины мала.
 
'''Маленький мир''' (англ. ''Small World'') {{---}} граф, в котором мат. ожидание кратчайшего пути между двумя случайно выбранными вершинами растёт пропорционально <tex>\log{N}</tex>. Но при этом средняя степень вершины мала.
  
Для маленького мира на точках в Евклидовом пространстве, жадный поиск K ближайших соседей будет выглядеть так:
+
Для маленького мира на точках в Евклидовом пространстве жадный поиск <tex>k</tex> ближайших соседей будет выглядеть так:
 
  '''knn'''(V, E, request, m, k)''':'''
 
  '''knn'''(V, E, request, m, k)''':'''
     W = <tex>\emptyset</tex>  <font color="green">// ближайшие к q вершины </font>
+
     W = <tex>\emptyset</tex>  <font color="green">// Ближайшие к q вершины. </font>
     C = <tex>\emptyset</tex>  <font color="green">// вершины, которые предстоит посетить </font>
+
     C = <tex>\emptyset</tex>  <font color="green">// Вершины, которые предстоит посетить. </font>
     V = <tex>\emptyset</tex>  <font color="green">// посещённые вершины </font>
+
     V = <tex>\emptyset</tex>  <font color="green">// Посещённые вершины. </font>
 
     '''for''' i = 1 '''to''' m
 
     '''for''' i = 1 '''to''' m
         C = С <tex>\bigcup</tex> random_v v <tex>\in</tex> G
+
         C = С <tex>\bigcup</tex> <tex>random_v</tex> v <tex>\in</tex> G
         TN = <tex>\emptyset</tex>  <font color="green">// ближайшие вершины в этом проходе</font>
+
         TN = <tex>\emptyset</tex>  <font color="green">// Ближайшие вершины в этом проходе.</font>
 
         '''while''' ''true''
 
         '''while''' ''true''
             u = {q1 | <tex>\forall</tex> q2 <tex>\in</tex> C, |q - q1| < |q - q2|}
+
             u = {q1 | <tex>\forall</tex> q2 <tex>\in</tex> C, |q - q1| <= |q - q2|} <font color="green">// Ближайшая к q вершина из C. </font>
 
             C = C <tex>\setminus</tex> u
 
             C = C <tex>\setminus</tex> u
 
             '''if''' u дальше чем k-й элемент W
 
             '''if''' u дальше чем k-й элемент W
 
                 '''break'''
 
                 '''break'''
             '''for''' e : смежные с u вершины
+
             '''for''' e: (u, e) '''in''' G
 
                 '''if''' e <tex>{\notin}</tex> V
 
                 '''if''' e <tex>{\notin}</tex> V
 
                     C = C <tex>\bigcup</tex> e
 
                     C = C <tex>\bigcup</tex> e
Строка 26: Строка 42:
 
                     TN = TN <tex>\bigcup</tex> e
 
                     TN = TN <tex>\bigcup</tex> e
 
         W = W <tex>\bigcup</tex> TN
 
         W = W <tex>\bigcup</tex> TN
     '''return''' k первых вершин из W
+
     '''return''' k ближайших к q вершин из W
  
Очевидный недостаток этого алгоритма {{---}} опасность свалиться в локальный минимум, остановившись в каком-то кластере. С увеличением числа m, вероятность такого застревания экспоненциально падает.
+
Расстояние между вершинами графа может измеряться [[Метрический классификатор и метод ближайших соседей#Использование различных метрик расстояния|различными метриками]]. <br/>
 +
Очевидный недостаток этого алгоритма {{---}} опасность свалиться в локальный минимум, остановившись в каком-то кластере. С увеличением числа <tex>m</tex>, вероятность такого застревания экспоненциально падает.
  
 
==Описание структуры==
 
==Описание структуры==
'''Иерархический Маленький мир''' (англ. ''Hierarchical Navigable Small World'') {{---}} слоистая структура графов. На нулевом слое представлены все '''N''' вершин из исходной выборки. Вершина, присутствующая на уровне '''L''' так же присутствует на уровне '''L + 1''' с вероятностью '''P'''. Т.е. кол-во слоёв растет как <tex>O(\log N)</tex>. Количество соседей каждой вершины на каждом уровне ограниченно константой, что позволяет делать запросы на добавление и удаление вершины за <tex>O(\log N)</tex>.
+
'''Иерархический Маленький мир''' {{---}} слоистая структура графов. На нулевом слое представлены все <tex>N</tex> вершин из исходной выборки. Вершина, присутствующая на уровне <tex>L</tex> так же присутствует на уровне <tex>L + 1</tex> с вероятностью <tex>P</tex>. Т.е. кол-во слоёв растет как <tex>O(\log N)</tex>. Количество соседей каждой вершины на каждом уровне ограниченно константой, что позволяет делать запросы на добавление и удаление вершины за <tex>O(\log N)</tex>.
 
{|align="center"
 
{|align="center"
 
  |-valign="top"
 
  |-valign="top"
Строка 42: Строка 59:
 
Жадно идём по уровню в сторону запроса.   
 
Жадно идём по уровню в сторону запроса.   
 
  '''searchLayer'''(q, ep, ef, layer)''':'''
 
  '''searchLayer'''(q, ep, ef, layer)''':'''
     <font color="green">// Входные данные: запрос q, входные точки ep, искомое количество ближайших соседей ef, номер слоя layer</font>
+
     <font color="green">// Входные данные: иерархия графов hnsw, запрос q, входные точки ep, искомое количество ближайших соседей ef, номер слоя layer.</font>
     <font color="green">// Возвращает: ef ближайших соседей q в слое layer</font>
+
     <font color="green">// Возвращает: ef ближайших соседей q в слое layer.</font>
     candidates = new TreeSet(ep) <font color="green">// Вершины упорядочены по возрастанию расстояния до q. </font>
+
     W = {ep<font color="green">// Ближайшие к q вершины. </font>
     result = new TreeSet(ep)
+
     C = {ep}  <font color="green">// Вершины, которые предстоит посетить. </font>
     visited = new HashSet(ep)
+
     V = {ep}  <font color="green">// Посещённые вершины. </font>
     '''while''' candidates.isNotEmpty()
+
     '''while''' C != <tex>\emptyset</tex>
         current = candidates.getMin()
+
         u = {q1 | <tex>\forall</tex> q2 <tex>\in</tex> C, |q - q1| <= |q - q2|} <font color="green">// Ближайшая к q вершина из C. </font>
         furthest = result.getMax()
+
         f = {q1 | <tex>\forall</tex> q2 <tex>\in</tex> W, |q - q1| >= |q - q2|} <font color="green">// Самая дальняя от q вершина из W. </font>
         '''if''' distance(current, q) > distance(furthest, q)
+
         '''if''' |u - q| > |f - q|
 
             '''break''' <font color="green">// Мы в локальном минимуме. </font>
 
             '''break''' <font color="green">// Мы в локальном минимуме. </font>
         '''for''' v : смежные с current вершины в слое layer
+
         '''for''' e : (u, e) '''in''' G
             '''if''' !visited.contains(r)
+
             '''if''' e <tex>{\notin}</tex> V
                 visited.add(v)
+
                 V = V <tex>\bigcup</tex> e
                 furthest = result.getMax()
+
                 f = {q1 | <tex>\forall</tex> q2 <tex>\in</tex> W, |q - q1| >= |q - q2|} <font color="green">// Самая дальняя от q вершина из W. </font>
                 '''if''' distance(v, q) < distance(furthest, q) or result.count() < ef
+
                 '''if''' |e - q| < |f - q| or |W| < ef
                     candidates.add(v)
+
                     C = C <tex>\bigcup</tex> e
                     result.add(v)
+
                     W = W <tex>\bigcup</tex> e
                     if result.count() > ef
+
                     if |W| > ef
                         result.removeLast()
+
                         W = W \ f
     '''return''' result
+
     '''return''' W
  
 
===Поиск ближайших соседей во всей структуре===
 
===Поиск ближайших соседей во всей структуре===
 
[[Файл:HnswSearch.png|мини|500px|Жадный поиск вершины.
 
[[Файл:HnswSearch.png|мини|500px|Жадный поиск вершины.
 
[https://arxiv.org/abs/1603.09320 Оригинал]]]
 
[https://arxiv.org/abs/1603.09320 Оригинал]]]
Жадно ищем ближайшего соседа на каждом уровне, кроме 0. Когда находим, спускаемся через него на уровень ниже.
+
# Идём с верхнего уровня до первого:
На нулевом уровне жадно ищем '''K''' ближайших соседей.
+
## Жадно ищем ближайшую к <tex>q</tex> вершину на текущем уровне.
  '''knn'''(hnsw, q, K, ef)''':'''
+
## Спускаемся в соответствующую соседу вершине на уровень ниже.
     <font color="green">// Входные данные: граф hnsw, запрос q, искомое количество ближайших соседей  K, количество кандидатов при поиске ef</font>
+
# На нулевом уровне жадно ищем <tex>k</tex> ближайших соседей.
     <font color="green">// Возвращает: K ближайших соседей q</font>
+
  '''knn'''(hnsw, q, k, ef)''':'''
     result = new TreeSet() <font color="green">// Вершины упорядочены по возрастанию расстояния до request. </font>
+
     <font color="green">// Входные данные: иерархия графов hnsw, запрос q, искомое количество ближайших соседей  k, количество кандидатов при поиске ef. </font>
     ep = случайная вершина из верхнего слоя hnsw
+
     <font color="green">// Возвращает: k ближайших соседей q. </font>
     maxLevel = индекс самого высокого слоя в hnsw
+
     W = <tex>\emptyset</tex>  <font color="green">// Ближайшие к q вершины. </font>
     '''for''' level = maxLevel to 1
+
     mL = |hnsw| - 1
         result = searchLayer(q, ep, ef=1, level) <font color="green">// На каждом уровне, кроме нижнего мы ищем всего одну ближайшую вершину. </font>
+
     ep = <tex>random_v</tex> v <tex>\in</tex> hnsw[mL]
         ep = result.getMin()
+
     '''for''' level = mL to 1
     result = searchLayer(q, ep, ef, lc=0)
+
         W = searchLayer(hnsw, q, ep, ef=1, level) <font color="green">// На каждом уровне, кроме нижнего мы ищем всего одну ближайшую вершину. </font>
     '''return''' первые K элементов из result
+
         ep = W
 +
     W = searchLayer(hnsw, q, ep, ef, lc=0)
 +
     '''return''' k ближайших к q вершин из W
  
 
===Вставка элемента===
 
===Вставка элемента===
Случайным образом выбираем максимальный слой, на котором представлена '''q'''.
+
# Случайным образом выбираем максимальный слой, на котором будет представлена <tex>q</tex>.
Жадно ищем '''M''' ближайших вершин к '''q''' на каждом уровне, на котором она представлена; добавляем связи '''q''' с ними; удаляем лишние связи у новообразовавшихся соседей.
+
# На каждом уровне, где будет представлена <tex>q</tex>, сверху вниз:
 +
## Жадно ищем <tex>m</tex> ближайших к <tex>q</tex> вершин.
 +
## Добавляем связи <tex>q</tex> с ними.
 +
## Удаляем лишние связи у новообразовавшихся соседей.
 
  '''insert'''(hnsw, q, m, mMax, ef, mL)''':'''
 
  '''insert'''(hnsw, q, m, mMax, ef, mL)''':'''
     <font color="green">// Входные данные: граф hnsw, запрос на добавление q, желаемое количество связей m, максимальное количество связей вершины </font>
+
     <font color="green">// Входные данные: иерархия графов hnsw, запрос на добавление q, желаемое количество связей m, максимальное количество связей вершины </font>
 
     <font color="green">//      на одном слое mMax, количество кандидатов при поиске ef, коэффициент выбора высоты mL. </font>
 
     <font color="green">//      на одном слое mMax, количество кандидатов при поиске ef, коэффициент выбора высоты mL. </font>
 
     <font color="green">// Возвращает: hnsw с вставленным элементом q. </font>
 
     <font color="green">// Возвращает: hnsw с вставленным элементом q. </font>
     result = new TreeSet() <font color="green">// Вершины упорядочены по возрастанию расстояния до q. </font>
+
     W = <tex>\emptyset</tex>  <font color="green">// Ближайшие к q вершины. </font>
     ep = случайная вершина из верхнего слоя hnsw
+
     mL = |hnsw| - 1
     maxLevel = индекс самого высокого слоя в hnsw
+
     ep = <tex>random_v</tex> v <tex>\in</tex> hnsw[mL]
     qLevel = -ln(rand(eps, 1.0)) * mL <font color="green">// Верхний слой для вершины q. </font>
+
     qL = -ln(rand(eps, 1.0)) * mL <font color="green">// Верхний слой для вершины q. </font>
     '''for''' level = maxLevel to qLevel + 1
+
     '''for''' level = mL to qL + 1
         result = searchLayer(q, ep, ef=1, level)
+
         W = searchLayer(q, ep, ef=1, level)
         ep = result
+
         ep = W
     '''for''' level = min(maxLevel, qLevel) to 0
+
     '''for''' level = min(mL, qL) to 0
         result = searchLayer(q, ep, ef, level)
+
         W = searchLayer(q, ep, ef, level)
         neighbors = searchLayer.getFirst(M)
+
         neighbours = M ближайших к q вершин из W
         Добавить связи между neighbours и q на уровне level
+
         '''for''' n <tex>\in</tex> neighbours:
        '''for''' v : neighbors
+
            <font color="green">// Добавляем двусторонние связи между n и q. </font>
 +
            hnsw[level] = hnsw[level] <tex>\bigcup</tex> (n, q)
 +
            hnsw[level] = hnsw[level] <tex>\bigcup</tex> (q, n)
 +
           
 +
            nNeighbours = {v| (v, n) '''in''' hnsw[level]} <font color="green">// Ищем всех соседей n на уровне level. </font>
 
             <font color="green">// Убираем лишние связи, если требуется. </font>
 
             <font color="green">// Убираем лишние связи, если требуется. </font>
            vNeighbours = смежные с v на уровне level
+
             '''if''' nNeighbours.Count() > mMax
             '''if''' vNeighbours.Count() > mMax
+
                 <font color="green">// Самая дальняя от n вершина, смежняя с ней. </font>
                 оставить у v только связи с ближайшими mMax смежными вершинами на уровне level
+
                v = {q1 | (q2, n) <tex>\in</tex> nNeighbours & <tex>\forall</tex>q2 <tex>\in</tex> hnsw[level], |q - q1| >= |q - q2|}
         ep = result
+
                hnsw[level] = hnsw[level] <tex>\setminus</tex> (n, v)
     '''if''' qLevel > maxLevel
+
                hnsw[level] = hnsw[level] <tex>\setminus</tex> (v, n)
         Добавить недостающие слои в hnsw, в каждый из них положить q
+
         ep = W
 +
     '''if''' qL > mL
 +
         '''for''' level = mL to qL
 +
            hnsw.append({q, {}})
 +
 
 +
== Практическое использование ==
 +
В библиотеке [https://github.com/nmslib/hnswlib Hnswlib] есть реализация иерархического маленького мира. Эта библиотека написана на C++, с биндингами на python.
 +
Пример использования:
 +
'''import''' hnswlib
 +
'''import''' numpy '''as''' np
 +
 +
dim = 128
 +
num_elements = 10000
 +
 +
<font color="green"># Создаём тестовые данные.</font>
 +
data = np.float32(np.random.random((num_elements, dim)))
 +
data_labels = np.arange(num_elements)
 +
 +
<font color="green"># Создаём иерархический маленький мир в L2.</font>
 +
<font color="green"># Возможные метрики {{---}} l2, cosine, ip (L2, косинус угла между векторами, скалярное произведение).</font>
 +
p = hnswlib.Index(space = 'l2', dim = dim)
 +
 +
<font color="green"># Инициализируем структуру.</font>
 +
p.init_index(max_elements = num_elements, ef_construction = 200, M = 16)
 +
 +
<font color="green"># Добавляем данные (можно вызывать много раз).</font>
 +
p.add_items(data, data_labels)
 +
 +
<font color="green"># Настраиваем качество, выставляя ef:</font>
 +
p.set_ef(50) <font color="green"># ef должно быть > k</font>
 +
 +
<font color="green"># Делаем запрос.</font>
 +
<font color="green"># k - количество ближайших вершин</font>
 +
labels, distances = p.knn_query(data, k = 1)
  
 
== См. также ==
 
== См. также ==
[[Метрический классификатор и метод ближайших соседей]]<br />
+
* [[Общие понятия]]
[[Иерархическая кластеризация]]
+
* [[Метрический классификатор и метод ближайших соседей]]
 +
* [[Список с пропусками]]
  
== Примечания ==
 
 
== Источники информации ==
 
== Источники информации ==
[https://en.wikipedia.org/wiki/Small-world_network Статья на википедии о маленьких мирах]
+
* [https://arxiv.org/abs/1603.09320 Yu. A. Malkov, D. A. Yashunin {{---}} Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs]
 +
* [https://ru.wikipedia.org/wiki/%D0%9C%D0%B8%D1%80_%D1%82%D0%B5%D1%81%D0%B5%D0%BD_(%D0%B3%D1%80%D0%B0%D1%84) Википедия {{---}} Мир тесен (граф)]
 +
* [https://en.wikipedia.org/wiki/Small-world_network Wikipedia {{---}} Small-world network]
 +
* [https://github.com/sgjurano/ysda-celebrity-faces Поиск знаменитостей на фотографии с помощью иерархического маленького мира]
 +
* [https://m.habr.com/ru/company/mailru/blog/338360/ Статья от Mail.ru об использовании иерархического маленького мира]
 +
 
 +
[[Категория: Машинное обучение]]

Версия 17:45, 24 марта 2020

Иерархический маленький мир (англ. 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)

См. также

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