Поиск ближайших соседей с помощью иерархического маленького мира — различия между версиями
Marsermd (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показано 36 промежуточных версий 4 участников) | |||
Строка 1: | Строка 1: | ||
− | '''Иерархический маленький мир''' (англ. ''Hierarchical Navigable Small World'' | + | '''Иерархический маленький мир''' (англ. ''Hierarchical Navigable Small World'') {{---}} структура данных, позволяющая эффективно искать <tex>k</tex> почти что ближайших соседей на больших множествах вершин. |
− | По своей концепции напоминает [[список с пропусками]] | + | Поиск ближайших соседей нужен в задачах [[Общие понятия|классификации]] и [[кластеризация|кластеризации]]. |
− | + | ||
+ | По своей концепции напоминает [[список с пропусками]]. | ||
== Применение == | == Применение == | ||
− | Представим себе ситуацию: | + | Представим себе ситуацию: |
− | * У социальной сети есть 10 | + | * У социальной сети есть <tex>10^{11}</tex> пользовательских фотографий с отмеченными лицами на них. |
− | * По новой фотографии требуется быстро узнать кто на ней и предложить пользователю отметить этого человека. | + | * По новой фотографии требуется быстро узнать кто на ней и предложить пользователю отметить этого человека. |
− | + | ||
Возможный процесс: | Возможный процесс: | ||
− | # Обучаем | + | # Обучаем [https://github.com/davidsandberg/facenet FaceNet] выдавать <tex>128</tex>-мерные вектора по изображению лица, такие, что у фотографий одного человека похожие значения векторов. |
− | # Добавляем 10 | + | # Добавляем <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>. Но при этом средняя степень вершины мала. |
− | Для маленького мира на точках в Евклидовом пространстве жадный поиск | + | Для маленького мира на точках в Евклидовом пространстве жадный поиск <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> | ||
Строка 31: | Строка 32: | ||
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|} <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> |
C = C <tex>\setminus</tex> u | C = C <tex>\setminus</tex> u | ||
'''if''' u дальше чем k-й элемент W | '''if''' u дальше чем k-й элемент W | ||
Строка 43: | Строка 44: | ||
'''return''' k ближайших к q вершин из W | '''return''' k ближайших к q вершин из W | ||
− | Очевидный недостаток этого алгоритма {{---}} опасность свалиться в локальный минимум, остановившись в каком-то кластере. С увеличением числа m, вероятность такого застревания экспоненциально падает. | + | Расстояние между вершинами графа может измеряться [[Метрический классификатор и метод ближайших соседей#Использование различных метрик расстояния|различными метриками]]. <br/> |
+ | Очевидный недостаток этого алгоритма {{---}} опасность свалиться в локальный минимум, остановившись в каком-то кластере. С увеличением числа <tex>m</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" | ||
Строка 59: | Строка 61: | ||
<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 = | + | W = {ep} <font color="green">// Ближайшие к q вершины. </font> |
− | C = | + | C = {ep} <font color="green">// Вершины, которые предстоит посетить. </font> |
− | V = | + | V = {ep} <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> | ||
Строка 82: | Строка 84: | ||
[https://arxiv.org/abs/1603.09320 Оригинал]]] | [https://arxiv.org/abs/1603.09320 Оригинал]]] | ||
# Идём с верхнего уровня до первого: | # Идём с верхнего уровня до первого: | ||
− | ## Жадно ищем ближайшую к | + | ## Жадно ищем ближайшую к <tex>q</tex> вершину на текущем уровне. |
## Спускаемся в соответствующую соседу вершине на уровень ниже. | ## Спускаемся в соответствующую соседу вершине на уровень ниже. | ||
− | # На нулевом уровне жадно ищем | + | # На нулевом уровне жадно ищем <tex>k</tex> ближайших соседей. |
'''knn'''(hnsw, q, k, ef)''':''' | '''knn'''(hnsw, q, k, ef)''':''' | ||
− | <font color="green">// Входные данные: иерархия графов hnsw, запрос q, искомое количество ближайших соседей | + | <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">// | + | W = <tex>\emptyset</tex> <font color="green">// Ближайшие к q вершины. </font> |
mL = |hnsw| - 1 | mL = |hnsw| - 1 | ||
ep = <tex>random_v</tex> v <tex>\in</tex> hnsw[mL] | ep = <tex>random_v</tex> v <tex>\in</tex> hnsw[mL] | ||
Строка 98: | Строка 100: | ||
===Вставка элемента=== | ===Вставка элемента=== | ||
− | # Случайным образом выбираем максимальный слой, на котором будет представлена | + | # Случайным образом выбираем максимальный слой, на котором будет представлена <tex>q</tex>. |
− | # На каждом уровне, где будет представлена | + | # На каждом уровне, где будет представлена <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)''':''' | ||
Строка 107: | Строка 109: | ||
<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> | ||
− | W = <tex>\emptyset</tex> <font color="green">// | + | W = <tex>\emptyset</tex> <font color="green">// Ближайшие к q вершины. </font> |
mL = |hnsw| - 1 | mL = |hnsw| - 1 | ||
ep = <tex>random_v</tex> v <tex>\in</tex> hnsw[mL] | ep = <tex>random_v</tex> v <tex>\in</tex> hnsw[mL] | ||
Строка 118: | Строка 120: | ||
neighbours = M ближайших к q вершин из W | neighbours = M ближайших к q вершин из W | ||
'''for''' n <tex>\in</tex> neighbours: | '''for''' n <tex>\in</tex> neighbours: | ||
+ | <font color="green">// Добавляем двусторонние связи между n и q. </font> | ||
hnsw[level] = hnsw[level] <tex>\bigcup</tex> (n, q) | hnsw[level] = hnsw[level] <tex>\bigcup</tex> (n, q) | ||
hnsw[level] = hnsw[level] <tex>\bigcup</tex> (q, n) | hnsw[level] = hnsw[level] <tex>\bigcup</tex> (q, n) | ||
− | nNeighbours = {v| (v, n) '''in''' hnsw[level]} | + | |
+ | nNeighbours = {v| (v, n) '''in''' hnsw[level]} <font color="green">// Ищем всех соседей n на уровне level. </font> | ||
<font color="green">// Убираем лишние связи, если требуется. </font> | <font color="green">// Убираем лишние связи, если требуется. </font> | ||
'''if''' nNeighbours.Count() > mMax | '''if''' nNeighbours.Count() > mMax | ||
Строка 133: | Строка 137: | ||
== Практическое использование == | == Практическое использование == | ||
− | В библиотеке | + | В библиотеке [https://github.com/nmslib/hnswlib Hnswlib] есть реализация иерархического маленького мира. Эта библиотека написана на C++, с биндингами на python. |
Пример использования: | Пример использования: | ||
− | 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) | ||
− | # Создаём иерархический маленький мир в L2. | + | <font color="green"># Создаём иерархический маленький мир в L2.</font> |
− | # Возможные метрики {{---}} l2, cosine, ip (L2, косинус угла между векторами, скалярное произведение). | + | <font color="green"># Возможные метрики {{---}} l2, cosine, ip (L2, косинус угла между векторами, скалярное произведение).</font> |
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) | ||
− | # Настраиваем качество, выставляя ef: | + | <font color="green"># Настраиваем качество, выставляя ef:</font> |
− | p.set_ef(50) # ef должно быть > k | + | p.set_ef(50) <font color="green"># ef должно быть > k</font> |
− | # Делаем запрос. | + | <font color="green"># Делаем запрос.</font> |
− | # k - количество | + | <font color="green"># k - количество ближайших вершин</font> |
labels, distances = p.knn_query(data, k = 1) | labels, distances = p.knn_query(data, k = 1) | ||
== См. также == | == См. также == | ||
− | [[Метрический классификатор и метод ближайших соседей]] | + | * [[Общие понятия]] |
− | [[Список с пропусками]] | + | * [[Метрический классификатор и метод ближайших соседей]] |
+ | * [[Список с пропусками]] | ||
− | == | + | == Источники информации == |
− | [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 об использовании иерархического маленького мира] | ||
− | + | [[Категория: Машинное обучение]] |
Текущая версия на 19:40, 4 сентября 2022
Иерархический маленький мир (англ. Hierarchical Navigable Small World) — структура данных, позволяющая эффективно искать классификации и кластеризации.
почти что ближайших соседей на больших множествах вершин. Поиск ближайших соседей нужен в задачахПо своей концепции напоминает список с пропусками.
Содержание
Применение
Представим себе ситуацию:
- У социальной сети есть пользовательских фотографий с отмеченными лицами на них.
- По новой фотографии требуется быстро узнать кто на ней и предложить пользователю отметить этого человека.
Возможный процесс:
- Обучаем FaceNet выдавать -мерные вектора по изображению лица, такие, что у фотографий одного человека похожие значения векторов.
- Добавляем векторов в иерархический маленький мир.
- При добавлении новой фотографии, вычисляем соответствующий лицу вектор.
- Ищем его ближайших соседей.
- Классифицируем лицо с использованием ядер сглаживания.
- Если пользователь подтвердил нашу догадку, добавляем этот вектор в иерархический маленький мир.
Маленький мир
![](/wiki/images/thumb/2/27/SmallWorld_Greedy.png/500px-SmallWorld_Greedy.png)
Маленький мир (англ. Small World) — граф, в котором мат. ожидание кратчайшего пути между двумя случайно выбранными вершинами растёт пропорционально
. Но при этом средняя степень вершины мала.Для маленького мира на точках в Евклидовом пространстве жадный поиск
ближайших соседей будет выглядеть так:knn(V, E, request, m, k): W =// Ближайшие к q вершины. C = // Вершины, которые предстоит посетить. V = // Посещённые вершины. for i = 1 to m C = С v G TN = // Ближайшие вершины в этом проходе. while true u = {q1 | q2 C, |q - q1| <= |q - q2|} // Ближайшая к q вершина из C. C = C u if u дальше чем k-й элемент W break for e: (u, e) in G if e V C = C e V = V e TN = TN e W = W TN return k ближайших к q вершин из W
Расстояние между вершинами графа может измеряться различными метриками.
Очевидный недостаток этого алгоритма — опасность свалиться в локальный минимум, остановившись в каком-то кластере. С увеличением числа , вероятность такого застревания экспоненциально падает.
Описание структуры
Иерархический Маленький мир — слоистая структура графов. На нулевом слое представлены все
вершин из исходной выборки. Вершина, присутствующая на уровне так же присутствует на уровне с вероятностью . Т.е. кол-во слоёв растет как . Количество соседей каждой вершины на каждом уровне ограниченно константой, что позволяет делать запросы на добавление и удаление вершины за .![]() Иерархический маленький мир. Источник |
Операции над структурой
Поиск ближайших соседей в слое
Жадно идём по уровню в сторону запроса.
searchLayer(q, ep, ef, layer): // Входные данные: иерархия графов hnsw, запрос q, входные точки ep, искомое количество ближайших соседей ef, номер слоя layer. // Возвращает: ef ближайших соседей q в слое layer. W = {ep} // Ближайшие к q вершины. C = {ep} // Вершины, которые предстоит посетить. V = {ep} // Посещённые вершины. while C !=u = {q1 | q2 C, |q - q1| <= |q - q2|} // Ближайшая к q вершина из C. f = {q1 | q2 W, |q - q1| >= |q - q2|} // Самая дальняя от q вершина из W. if |u - q| > |f - q| break // Мы в локальном минимуме. for e : (u, e) in G if e V V = V e f = {q1 | q2 W, |q - q1| >= |q - q2|} // Самая дальняя от q вершина из W. if |e - q| < |f - q| or |W| < ef C = C e W = W e if |W| > ef W = W \ f return W
Поиск ближайших соседей во всей структуре
![](/wiki/images/b/be/HnswSearch.png)
- Идём с верхнего уровня до первого:
- Жадно ищем ближайшую к вершину на текущем уровне.
- Спускаемся в соответствующую соседу вершине на уровень ниже.
- На нулевом уровне жадно ищем ближайших соседей.
knn(hnsw, q, k, ef): // Входные данные: иерархия графов hnsw, запрос q, искомое количество ближайших соседей k, количество кандидатов при поиске ef. // Возвращает: k ближайших соседей q. W =// Ближайшие к q вершины. mL = |hnsw| - 1 ep = v 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
Вставка элемента
- Случайным образом выбираем максимальный слой, на котором будет представлена .
- На каждом уровне, где будет представлена
- Жадно ищем ближайших к вершин.
- Добавляем связи с ними.
- Удаляем лишние связи у новообразовавшихся соседей.
, сверху вниз:
insert(hnsw, q, m, mMax, ef, mL): // Входные данные: иерархия графов hnsw, запрос на добавление q, желаемое количество связей m, максимальное количество связей вершины // на одном слое mMax, количество кандидатов при поиске ef, коэффициент выбора высоты mL. // Возвращает: hnsw с вставленным элементом q. W =// Ближайшие к q вершины. mL = |hnsw| - 1 ep = v 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 neighbours: // Добавляем двусторонние связи между n и q. hnsw[level] = hnsw[level] (n, q) hnsw[level] = hnsw[level] (q, n) nNeighbours = {v| (v, n) in hnsw[level]} // Ищем всех соседей n на уровне level. // Убираем лишние связи, если требуется. if nNeighbours.Count() > mMax // Самая дальняя от n вершина, смежняя с ней. v = {q1 | (q2, n) nNeighbours & q2 hnsw[level], |q - q1| >= |q - q2|} hnsw[level] = hnsw[level] (n, v) hnsw[level] = hnsw[level] (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)
См. также
Источники информации
- Yu. A. Malkov, D. A. Yashunin — Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
- Википедия — Мир тесен (граф)
- Wikipedia — Small-world network
- Поиск знаменитостей на фотографии с помощью иерархического маленького мира
- Статья от Mail.ru об использовании иерархического маленького мира