Викиконспекты - Вклад участника [ru]

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

2020-03-24T14:45:30Z

31.173.28.101: /* Операции над структурой */

'''Иерархический маленький мир''' (англ. ''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|Жадный поиск ближайшего соседа.
Чёрные ребра {{---}} короткие связи с соседями в небольшом радиусе <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 Оригинал]]]
'''Маленький мир''' (англ. ''Small World'') {{---}} граф, в котором мат. ожидание кратчайшего пути между двумя случайно выбранными вершинами растёт пропорционально <tex>\log{N}</tex>. Но при этом средняя степень вершины мала.

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

Расстояние между вершинами графа может измеряться [[Метрический классификатор и метод ближайших соседей#Использование различных метрик расстояния|различными метриками]]. 
Очевидный недостаток этого алгоритма {{---}} опасность свалиться в локальный минимум, остановившись в каком-то кластере. С увеличением числа <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)''':'''
// Входные данные: иерархия графов hnsw, запрос q, входные точки ep, искомое количество ближайших соседей ef, номер слоя layer.
// Возвращает: ef ближайших соседей q в слое layer.
W = {ep} // Ближайшие к q вершины. 
C = {ep} // Вершины, которые предстоит посетить. 
V = {ep} // Посещённые вершины. 
'''while''' C != <tex>\emptyset</tex>
u = {q1 | <tex>\forall</tex> q2 <tex>\in</tex> C, |q - q1| <= |q - q2|} // Ближайшая к q вершина из C. 
f = {q1 | <tex>\forall</tex> q2 <tex>\in</tex> W, |q - q1| >= |q - q2|} // Самая дальняя от q вершина из W. 
'''if''' |u - q| > |f - q|
'''break''' // Мы в локальном минимуме. 
'''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|} // Самая дальняя от q вершина из W. 
'''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)''':'''
// Входные данные: иерархия графов hnsw, запрос q, искомое количество ближайших соседей k, количество кандидатов при поиске ef. 
// Возвращает: k ближайших соседей q. 
W = <tex>\emptyset</tex> // Ближайшие к q вершины. 
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) // На каждом уровне, кроме нижнего мы ищем всего одну ближайшую вершину. 
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)''':'''
// Входные данные: иерархия графов hnsw, запрос на добавление q, желаемое количество связей m, максимальное количество связей вершины 
// на одном слое mMax, количество кандидатов при поиске ef, коэффициент выбора высоты mL. 
// Возвращает: hnsw с вставленным элементом q. 
W = <tex>\emptyset</tex> // Ближайшие к q вершины. 
mL = |hnsw| - 1
ep = <tex>random_v</tex> v <tex>\in</tex> 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 <tex>\in</tex> neighbours:
// Добавляем двусторонние связи между n и q. 
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]} // Ищем всех соседей n на уровне level. 
// Убираем лишние связи, если требуется. 
'''if''' nNeighbours.Count() > mMax
// Самая дальняя от n вершина, смежняя с ней. 
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

# Создаём тестовые данные.
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)

== См. также ==
* [[Общие понятия]]
* [[Метрический классификатор и метод ближайших соседей]]
* [[Список с пропусками]]

== Источники информации ==
* [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 об использовании иерархического маленького мира]

[[Категория: Машинное обучение]]

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

2020-03-24T14:44:02Z

31.173.28.101: /* Поиск ближайших соседей в слое */

'''Иерархический маленький мир''' (англ. ''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|Жадный поиск ближайшего соседа.
Чёрные ребра {{---}} короткие связи с соседями в небольшом радиусе <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 Оригинал]]]
'''Маленький мир''' (англ. ''Small World'') {{---}} граф, в котором мат. ожидание кратчайшего пути между двумя случайно выбранными вершинами растёт пропорционально <tex>\log{N}</tex>. Но при этом средняя степень вершины мала.

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

Расстояние между вершинами графа может измеряться [[Метрический классификатор и метод ближайших соседей#Использование различных метрик расстояния|различными метриками]]. 
Очевидный недостаток этого алгоритма {{---}} опасность свалиться в локальный минимум, остановившись в каком-то кластере. С увеличением числа <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)''':'''
// Входные данные: иерархия графов hnsw, запрос q, входные точки ep, искомое количество ближайших соседей ef, номер слоя layer.
// Возвращает: ef ближайших соседей q в слое layer.
W = <tex>\{ep\}</tex> // Ближайшие к q вершины. 
C = <tex>\{ep\}</tex> // Вершины, которые предстоит посетить. 
V = <tex>\{ep\}</tex> // Посещённые вершины. 
'''while''' C != <tex>\emptyset</tex>
u = {q1 | <tex>\forall</tex> q2 <tex>\in</tex> C, |q - q1| <= |q - q2|} // Ближайшая к q вершина из C. 
f = {q1 | <tex>\forall</tex> q2 <tex>\in</tex> W, |q - q1| >= |q - q2|} // Самая дальняя от q вершина из W. 
'''if''' |u - q| > |f - q|
'''break''' // Мы в локальном минимуме. 
'''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|} // Самая дальняя от q вершина из W. 
'''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)''':'''
// Входные данные: иерархия графов hnsw, запрос q, искомое количество ближайших соседей k, количество кандидатов при поиске ef. 
// Возвращает: k ближайших соседей q. 
W = <tex>\emptyset</tex> // Ближайшие к q вершины. 
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) // На каждом уровне, кроме нижнего мы ищем всего одну ближайшую вершину. 
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)''':'''
// Входные данные: иерархия графов hnsw, запрос на добавление q, желаемое количество связей m, максимальное количество связей вершины 
// на одном слое mMax, количество кандидатов при поиске ef, коэффициент выбора высоты mL. 
// Возвращает: hnsw с вставленным элементом q. 
W = <tex>\emptyset</tex> // Ближайшие к q вершины. 
mL = |hnsw| - 1
ep = <tex>random_v</tex> v <tex>\in</tex> 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 <tex>\in</tex> neighbours:
// Добавляем двусторонние связи между n и q. 
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]} // Ищем всех соседей n на уровне level. 
// Убираем лишние связи, если требуется. 
'''if''' nNeighbours.Count() > mMax
// Самая дальняя от n вершина, смежняя с ней. 
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

# Создаём тестовые данные.
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)

== См. также ==
* [[Общие понятия]]
* [[Метрический классификатор и метод ближайших соседей]]
* [[Список с пропусками]]

== Источники информации ==
* [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 об использовании иерархического маленького мира]

[[Категория: Машинное обучение]]