Поиск ближайших соседей с помощью иерархического маленького мира — различия между версиями
Marsermd (обсуждение | вклад) (→Маленький мир) |
м (rollbackEdits.php mass rollback) |
||
(не показано 109 промежуточных версий 4 участников) | |||
Строка 1: | Строка 1: | ||
− | ''' | + | '''Иерархический маленький мир''' (англ. ''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>. Но при этом средняя степень вершины мала. | ||
− | Для маленького мира на точках в Евклидовом пространстве | + | Для маленького мира на точках в Евклидовом пространстве жадный поиск <tex>k</tex> ближайших соседей будет выглядеть так: |
− | + | '''knn'''(V, E, request, m, k)''':''' | |
− | + | W = <tex>\emptyset</tex> <font color="green">// Ближайшие к q вершины. </font> | |
− | + | C = <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> <tex>random_v</tex> v <tex>\in</tex> G | |
− | + | 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> | |
− | '''if''' | + | C = C <tex>\setminus</tex> u |
+ | '''if''' u дальше чем k-й элемент W | ||
'''break''' | '''break''' | ||
− | '''for''' | + | '''for''' e: (u, e) '''in''' G |
− | '''if''' | + | '''if''' e <tex>{\notin}</tex> V |
− | + | C = C <tex>\bigcup</tex> e | |
− | + | V = V <tex>\bigcup</tex> e | |
− | + | TN = TN <tex>\bigcup</tex> e | |
− | + | W = W <tex>\bigcup</tex> TN | |
− | '''return''' k | + | '''return''' k ближайших к q вершин из W |
− | Очевидный недостаток этого алгоритма {{---}} опасность свалиться в локальный минимум. | + | Расстояние между вершинами графа может измеряться [[Метрический классификатор и метод ближайших соседей#Использование различных метрик расстояния|различными метриками]]. <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" | ||
+ | |-valign="top" | ||
+ | |[[Файл:HNSW.png|мини|500px|Иерархический маленький мир. [https://arxiv.org/abs/1603.09320 Источник]]] | ||
+ | |} | ||
+ | |||
+ | ==Операции над структурой== | ||
+ | ===Поиск ближайших соседей в слое=== | ||
+ | Жадно идём по уровню в сторону запроса. | ||
+ | '''searchLayer'''(q, ep, ef, layer)''':''' | ||
+ | <font color="green">// Входные данные: иерархия графов hnsw, запрос q, входные точки ep, искомое количество ближайших соседей ef, номер слоя layer.</font> | ||
+ | <font color="green">// Возвращает: ef ближайших соседей q в слое layer.</font> | ||
+ | W = {ep} <font color="green">// Ближайшие к q вершины. </font> | ||
+ | C = {ep} <font color="green">// Вершины, которые предстоит посетить. </font> | ||
+ | V = {ep} <font color="green">// Посещённые вершины. </font> | ||
+ | '''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> | ||
+ | f = {q1 | <tex>\forall</tex> q2 <tex>\in</tex> W, |q - q1| >= |q - q2|} <font color="green">// Самая дальняя от q вершина из W. </font> | ||
+ | '''if''' |u - q| > |f - q| | ||
+ | '''break''' <font color="green">// Мы в локальном минимуме. </font> | ||
+ | '''for''' e : (u, e) '''in''' G | ||
+ | '''if''' e <tex>{\notin}</tex> V | ||
+ | V = V <tex>\bigcup</tex> e | ||
+ | f = {q1 | <tex>\forall</tex> q2 <tex>\in</tex> W, |q - q1| >= |q - q2|} <font color="green">// Самая дальняя от q вершина из W. </font> | ||
+ | '''if''' |e - q| < |f - q| or |W| < ef | ||
+ | C = C <tex>\bigcup</tex> e | ||
+ | W = W <tex>\bigcup</tex> e | ||
+ | if |W| > ef | ||
+ | W = W \ f | ||
+ | '''return''' W | ||
+ | ===Поиск ближайших соседей во всей структуре=== | ||
+ | [[Файл:HnswSearch.png|мини|500px|Жадный поиск вершины. | ||
+ | [https://arxiv.org/abs/1603.09320 Оригинал]]] | ||
+ | # Идём с верхнего уровня до первого: | ||
+ | ## Жадно ищем ближайшую к <tex>q</tex> вершину на текущем уровне. | ||
+ | ## Спускаемся в соответствующую соседу вершине на уровень ниже. | ||
+ | # На нулевом уровне жадно ищем <tex>k</tex> ближайших соседей. | ||
+ | '''knn'''(hnsw, q, k, ef)''':''' | ||
+ | <font color="green">// Входные данные: иерархия графов hnsw, запрос q, искомое количество ближайших соседей k, количество кандидатов при поиске ef. </font> | ||
+ | <font color="green">// Возвращает: k ближайших соседей q. </font> | ||
+ | W = <tex>\emptyset</tex> <font color="green">// Ближайшие к q вершины. </font> | ||
+ | mL = |hnsw| - 1 | ||
+ | ep = <tex>random_v</tex> v <tex>\in</tex> hnsw[mL] | ||
+ | '''for''' level = mL to 1 | ||
+ | W = searchLayer(hnsw, q, ep, ef=1, level) <font color="green">// На каждом уровне, кроме нижнего мы ищем всего одну ближайшую вершину. </font> | ||
+ | ep = W | ||
+ | W = searchLayer(hnsw, q, ep, ef, lc=0) | ||
+ | '''return''' k ближайших к q вершин из W | ||
− | |||
− | |||
===Вставка элемента=== | ===Вставка элемента=== | ||
+ | # Случайным образом выбираем максимальный слой, на котором будет представлена <tex>q</tex>. | ||
+ | # На каждом уровне, где будет представлена <tex>q</tex>, сверху вниз: | ||
+ | ## Жадно ищем <tex>m</tex> ближайших к <tex>q</tex> вершин. | ||
+ | ## Добавляем связи <tex>q</tex> с ними. | ||
+ | ## Удаляем лишние связи у новообразовавшихся соседей. | ||
+ | '''insert'''(hnsw, q, m, mMax, ef, mL)''':''' | ||
+ | <font color="green">// Входные данные: иерархия графов hnsw, запрос на добавление q, желаемое количество связей m, максимальное количество связей вершины </font> | ||
+ | <font color="green">// на одном слое mMax, количество кандидатов при поиске ef, коэффициент выбора высоты mL. </font> | ||
+ | <font color="green">// Возвращает: hnsw с вставленным элементом q. </font> | ||
+ | W = <tex>\emptyset</tex> <font color="green">// Ближайшие к q вершины. </font> | ||
+ | mL = |hnsw| - 1 | ||
+ | ep = <tex>random_v</tex> v <tex>\in</tex> hnsw[mL] | ||
+ | qL = -ln(rand(eps, 1.0)) * mL <font color="green">// Верхний слой для вершины q. </font> | ||
+ | '''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 <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> (q, n) | ||
+ | |||
+ | nNeighbours = {v| (v, n) '''in''' hnsw[level]} <font color="green">// Ищем всех соседей n на уровне level. </font> | ||
+ | <font color="green">// Убираем лишние связи, если требуется. </font> | ||
+ | '''if''' nNeighbours.Count() > mMax | ||
+ | <font color="green">// Самая дальняя от n вершина, смежняя с ней. </font> | ||
+ | v = {q1 | (q2, n) <tex>\in</tex> nNeighbours & <tex>\forall</tex>q2 <tex>\in</tex> hnsw[level], |q - q1| >= |q - q2|} | ||
+ | hnsw[level] = hnsw[level] <tex>\setminus</tex> (n, v) | ||
+ | hnsw[level] = hnsw[level] <tex>\setminus</tex> (v, n) | ||
+ | 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) | ||
+ | |||
+ | == См. также == | ||
+ | * [[Общие понятия]] | ||
+ | * [[Метрический классификатор и метод ближайших соседей]] | ||
+ | * [[Список с пропусками]] | ||
+ | |||
+ | == Источники информации == | ||
+ | * [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 об использовании иерархического маленького мира