Редактирование: Поиск ближайших соседей с помощью иерархического маленького мира

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
'''Иерархический маленький мир''' (англ. ''Hierarchical Navigable Small World'') {{---}} структура данных, позволяющая эффективно искать <tex>k</tex> почти что ближайших соседей на больших множествах вершин.
+
'''Иерархический маленький мир''' (англ. ''Hierarchical Navigable Small World''<ref>[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]</ref>) {{---}} структура данных, позволяющая эффективно искать k почти что ближайших соседей. <br/>
Поиск ближайших соседей нужен в задачах [[Общие понятия|классификации]] и [[кластеризация|кластеризации]].
+
Ключевая идея {{---}} вероятностная эвристика для создания соединений на большие расстояния. <br/>
 
+
По своей концепции напоминает [[список с пропусками]]. <br/>
По своей концепции напоминает [[список с пропусками]].
 
  
 
== Применение ==
 
== Применение ==
Представим себе ситуацию:
+
Представим себе ситуацию: <br/>
* У социальной сети есть <tex>10^{11}</tex> пользовательских фотографий с отмеченными лицами на них.
+
* У социальной сети есть 10&sup1;&sup1; пользовательских фотографий с отмеченными лицами на них.
* По новой фотографии требуется быстро узнать кто на ней и предложить пользователю отметить этого человека.
+
* По новой фотографии требуется быстро узнать кто на ней и предложить пользователю отметить этого человека.<br/>
 
+
<br/>
 
Возможный процесс:
 
Возможный процесс:
# Обучаем [https://github.com/davidsandberg/facenet FaceNet] выдавать <tex>128</tex>-мерные вектора по изображению лица, такие, что у фотографий одного человека похожие значения векторов.
+
# Обучаем FaceNet<ref>[https://github.com/davidsandberg/facenet FaceNet]</ref> выдавать 128-мерные вектора по изображению лица, т.ч. у фотографий одного человека похожие значения векторов.
# Добавляем <tex>10^{11}</tex> векторов в иерархический маленький мир.
+
# Добавляем 10&sup1;&sup1; векторов в иерархический маленький мир.
 
# При добавлении новой фотографии, вычисляем соответствующий лицу вектор.
 
# При добавлении новой фотографии, вычисляем соответствующий лицу вектор.
# Ищем <tex>k</tex> его ближайших соседей.
+
# Ищем K его ближайших соседей.
 
# Классифицируем лицо с использованием [[Метрический классификатор и метод ближайших соседей#Использование ядер сглаживания|ядер сглаживания]].
 
# Классифицируем лицо с использованием [[Метрический классификатор и метод ближайших соседей#Использование ядер сглаживания|ядер сглаживания]].
 
# Если пользователь подтвердил нашу догадку, добавляем этот вектор в иерархический маленький мир.
 
# Если пользователь подтвердил нашу догадку, добавляем этот вектор в иерархический маленький мир.
Строка 19: Строка 18:
 
==Маленький мир==
 
==Маленький мир==
 
[[Файл: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>. Но при этом средняя степень вершины мала.
+
'''Маленький мир'''<ref>[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) Статья о маленьком мире на википедии]</ref> (англ. ''Small World''<ref>[https://en.wikipedia.org/wiki/Small-world_network Статья о маленьком мире на английской википедии]</ref>) {{---}} граф, в котором мат. ожидание кратчайшего пути между двумя случайно выбранными вершинами растёт пропорционально <tex>\log{N}</tex>. Но при этом средняя степень вершины мала.
  
Для маленького мира на точках в Евклидовом пространстве жадный поиск <tex>k</tex> ближайших соседей будет выглядеть так:
+
Для маленького мира на точках в Евклидовом пространстве жадный поиск k ближайших соседей будет выглядеть так:
 
  '''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>
Строка 45: Строка 44:
  
 
Расстояние между вершинами графа может измеряться [[Метрический классификатор и метод ближайших соседей#Использование различных метрик расстояния|различными метриками]]. <br/>
 
Расстояние между вершинами графа может измеряться [[Метрический классификатор и метод ближайших соседей#Использование различных метрик расстояния|различными метриками]]. <br/>
Очевидный недостаток этого алгоритма {{---}} опасность свалиться в локальный минимум, остановившись в каком-то кластере. С увеличением числа <tex>m</tex>, вероятность такого застревания экспоненциально падает.
+
Очевидный недостаток этого алгоритма {{---}} опасность свалиться в локальный минимум, остановившись в каком-то кластере. С увеличением числа m, вероятность такого застревания экспоненциально падает.
  
 
==Описание структуры==
 
==Описание структуры==
'''Иерархический Маленький мир''' {{---}} слоистая структура графов. На нулевом слое представлены все <tex>N</tex> вершин из исходной выборки. Вершина, присутствующая на уровне <tex>L</tex> так же присутствует на уровне <tex>L + 1</tex> с вероятностью <tex>P</tex>. Т.е. кол-во слоёв растет как <tex>O(\log N)</tex>. Количество соседей каждой вершины на каждом уровне ограниченно константой, что позволяет делать запросы на добавление и удаление вершины за <tex>O(\log N)</tex>.
+
'''Иерархический Маленький мир''' {{---}} слоистая структура графов. На нулевом слое представлены все '''N''' вершин из исходной выборки. Вершина, присутствующая на уровне '''L''' так же присутствует на уровне '''L + 1''' с вероятностью '''P'''. Т.е. кол-во слоёв растет как <tex>O(\log N)</tex>. Количество соседей каждой вершины на каждом уровне ограниченно константой, что позволяет делать запросы на добавление и удаление вершины за <tex>O(\log N)</tex>.
 
{|align="center"
 
{|align="center"
 
  |-valign="top"
 
  |-valign="top"
Строка 61: Строка 60:
 
     <font color="green">// Входные данные: иерархия графов hnsw, запрос 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>
     W = {ep} <font color="green">// Ближайшие к q вершины. </font>
+
     W = <tex>\emptyset</tex> <font color="green">// Ближайшие к q вершины. </font>
     C = {ep} <font color="green">// Вершины, которые предстоит посетить. </font>
+
     C = <tex>\emptyset</tex> <font color="green">// Вершины, которые предстоит посетить. </font>
     V = {ep} <font color="green">// Посещённые вершины. </font>
+
     V = <tex>\emptyset</tex> <font color="green">// Посещённые вершины. </font>
 
     '''while''' C != <tex>\emptyset</tex>
 
     '''while''' C != <tex>\emptyset</tex>
 
         u = {q1 | <tex>\forall</tex> q2 <tex>\in</tex> C, |q - q1| <= |q - q2|} <font color="green">// Ближайшая к q вершина из C. </font>
 
         u = {q1 | <tex>\forall</tex> q2 <tex>\in</tex> C, |q - q1| <= |q - q2|} <font color="green">// Ближайшая к q вершина из C. </font>
Строка 84: Строка 83:
 
[https://arxiv.org/abs/1603.09320 Оригинал]]]
 
[https://arxiv.org/abs/1603.09320 Оригинал]]]
 
# Идём с верхнего уровня до первого:
 
# Идём с верхнего уровня до первого:
## Жадно ищем ближайшую к <tex>q</tex> вершину на текущем уровне.
+
## Жадно ищем ближайшую к '''q''' вершину на текущем уровне.
 
## Спускаемся в соответствующую соседу вершине на уровень ниже.
 
## Спускаемся в соответствующую соседу вершине на уровень ниже.
# На нулевом уровне жадно ищем <tex>k</tex> ближайших соседей.
+
# На нулевом уровне жадно ищем '''k''' ближайших соседей.
 
  '''knn'''(hnsw, q, k, ef)''':'''
 
  '''knn'''(hnsw, q, k, ef)''':'''
     <font color="green">// Входные данные: иерархия графов hnsw, запрос q, искомое количество ближайших соседей  k, количество кандидатов при поиске ef. </font>
+
     <font color="green">// Входные данные: иерархия графов hnsw, запрос q, искомое количество ближайших соседей  K, количество кандидатов при поиске ef. </font>
 
     <font color="green">// Возвращает: k ближайших соседей q. </font>
 
     <font color="green">// Возвращает: k ближайших соседей q. </font>
 
     W = <tex>\emptyset</tex>  <font color="green">// Ближайшие к q вершины. </font>
 
     W = <tex>\emptyset</tex>  <font color="green">// Ближайшие к q вершины. </font>
Строка 100: Строка 99:
  
 
===Вставка элемента===
 
===Вставка элемента===
# Случайным образом выбираем максимальный слой, на котором будет представлена <tex>q</tex>.
+
# Случайным образом выбираем максимальный слой, на котором будет представлена '''q'''.
# На каждом уровне, где будет представлена <tex>q</tex>, сверху вниз:
+
# На каждом уровне, где будет представлена '''q''', сверху вниз:
## Жадно ищем <tex>m</tex> ближайших к <tex>q</tex> вершин.
+
## Жадно ищем '''M''' ближайших к '''q''' вершин.
## Добавляем связи <tex>q</tex> с ними.
+
## Добавляем связи '''q''' с ними.
 
## Удаляем лишние связи у новообразовавшихся соседей.
 
## Удаляем лишние связи у новообразовавшихся соседей.
 
  '''insert'''(hnsw, q, m, mMax, ef, mL)''':'''
 
  '''insert'''(hnsw, q, m, mMax, ef, mL)''':'''
Строка 137: Строка 136:
  
 
== Практическое использование ==
 
== Практическое использование ==
В библиотеке [https://github.com/nmslib/hnswlib Hnswlib] есть реализация иерархического маленького мира. Эта библиотека написана на C++, с биндингами на python.
+
В библиотеке Hnswlib<ref>[https://github.com/nmslib/hnswlib Hnswlib]</ref> есть реализация иерархического маленького мира. Эта библиотека написана на C++, с биндингами на python. <br/>
 
Пример использования:
 
Пример использования:
  '''import''' hnswlib
+
  import hnswlib
  '''import''' numpy '''as''' np
+
  import numpy as np
 
   
 
   
 
  dim = 128
 
  dim = 128
 
  num_elements = 10000
 
  num_elements = 10000
 
   
 
   
  <font color="green"># Создаём тестовые данные.</font>
+
  # Создаём тестовые данные.
 
  data = np.float32(np.random.random((num_elements, dim)))
 
  data = np.float32(np.random.random((num_elements, dim)))
 
  data_labels = np.arange(num_elements)
 
  data_labels = np.arange(num_elements)
 
   
 
   
  <font color="green"># Создаём иерархический маленький мир в L2.</font>
+
  # Создаём иерархический маленький мир в L2.
  <font color="green"># Возможные метрики {{---}} l2, cosine, ip (L2, косинус угла между векторами, скалярное произведение).</font>
+
  # Возможные метрики {{---}} l2, cosine, ip (L2, косинус угла между векторами, скалярное произведение).
 
  p = hnswlib.Index(space = 'l2', dim = dim)
 
  p = hnswlib.Index(space = 'l2', dim = dim)
 
   
 
   
  <font color="green"># Инициализируем структуру.</font>
+
  # Инициализируем структуру.
 
  p.init_index(max_elements = num_elements, ef_construction = 200, M = 16)
 
  p.init_index(max_elements = num_elements, ef_construction = 200, M = 16)
 
   
 
   
  <font color="green"># Добавляем данные (можно вызывать много раз).</font>
+
  # Добавляем данные (можно вызывать много раз).
 
  p.add_items(data, data_labels)
 
  p.add_items(data, data_labels)
 
   
 
   
  <font color="green"># Настраиваем качество, выставляя ef:</font>
+
  # Настраиваем качество, выставляя ef:
  p.set_ef(50) <font color="green"># ef должно быть > k</font>
+
  p.set_ef(50) # ef должно быть > k
 
   
 
   
  <font color="green"># Делаем запрос.</font>
+
  # Делаем запрос.
  <font color="green"># k - количество ближайших вершин</font>
+
  # k - количество ближайших вершин
 
  labels, distances = p.knn_query(data, k = 1)
 
  labels, distances = p.knn_query(data, k = 1)
  
 
== См. также ==
 
== См. также ==
* [[Общие понятия]]
+
[[Метрический классификатор и метод ближайших соседей]]<br />
* [[Метрический классификатор и метод ближайших соседей]]
+
[[Список с пропусками]]<br />
* [[Список с пропусками]]
+
 
 +
== Примечания ==
 +
[https://github.com/sgjurano/ysda-celebrity-faces Поиск знаменитостей на фотографии с помощью иерархического маленького мира]
  
 
== Источники информации ==
 
== Источники информации ==
* [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 об использовании иерархического маленького мира]
 
 
 
[[Категория: Машинное обучение]]
 
[[Категория: Машинное обучение]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: