276
правок
Изменения
м
== Источники информации ==
Нет описания правки
'''Иерархический маленький мир''' (англ. ''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>) {{---}} структура данных, позволяющая эффективно искать <tex>k </tex> почти что ближайших соседей на больших множествах вершин. <br/>Поиск ближайших соседей нужен в задачах [[Общие понятия|классификации]] и [[кластеризация|кластеризации]]. <br/> По своей концепции напоминает [[список с пропусками]]. <br/>
== Применение ==
Представим себе ситуацию: <br/>* У социальной сети есть <tex>10¹¹ ^{11}</tex> пользовательских фотографий с отмеченными лицами на них.* По новой фотографии требуется быстро узнать кто на ней и предложить пользователю отметить этого человека.<br/><br/>
Возможный процесс:
# Обучаем FaceNet<ref>[https://github.com/davidsandberg/facenet FaceNet]выдавать <tex>128</reftex> выдавать 128-мерные вектора по изображению лица, т.ч. такие, что у фотографий одного человека похожие значения векторов.# Добавляем <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 Оригинал]]]
'''Маленький мир'''<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> ближайших соседей будет выглядеть так:
'''knn'''(V, E, request, m, k)''':'''
W = <tex>\emptyset</tex> <font color="green">// Ближайшие к q вершины. </font>
Расстояние между вершинами графа может измеряться [[Метрический классификатор и метод ближайших соседей#Использование различных метрик расстояния|различными метриками]]. <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"
[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>
===Вставка элемента===
# Случайным образом выбираем максимальный слой, на котором будет представлена '''<tex>q'''</tex>.# На каждом уровне, где будет представлена '''<tex>q'''</tex>, сверху вниз:## Жадно ищем '''<tex>m''' </tex> ближайших к '''<tex>q''' </tex> вершин.## Добавляем связи '''<tex>q''' </tex> с ними.
## Удаляем лишние связи у новообразовавшихся соседей.
'''insert'''(hnsw, q, m, mMax, ef, mL)''':'''
== Практическое использование ==
В библиотеке Hnswlib<ref>[https://github.com/nmslib/hnswlib Hnswlib]</ref> есть реализация иерархического маленького мира. Эта библиотека написана на C++, с биндингами на python. <br/>
Пример использования:
'''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 />* [[Метрический классификатор и метод ближайших соседей]]<br />* [[Список с пропусками]]<br />
== Примечания Источники информации ==* [https://githubarxiv.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.comorg/sgjuranowiki/ysda%D0%9C%D0%B8%D1%80_%D1%82%D0%B5%D1%81%D0%B5%D0%BD_(%D0%B3%D1%80%D0%B0%D1%84) Википедия {{--celebrity-faces Поиск знаменитостей на фотографии с помощью иерархического маленького мира}} Мир тесен (граф)]<br* [https://en.wikipedia.org/wiki/>Small-world_network Wikipedia {{---}} Small-world network]* [https://github.com/nmslibsgjurano/hnswlib Реализация ysda-celebrity-faces Поиск знаменитостей на фотографии с помощью иерархического маленького мира на Python] <br/>* [https://m.habr.com/ru/company/mailru/blog/338360/ Статья от Mail.ru об использовании иерархического маленького мира]
[[Категория: Машинное обучение]]
