Knowledge Accumulator

HNSW [2016] - один из столпов современных рекомендательных систем

В больших системах существуют миллионы вариантов того, что можно порекомендовать пользователю. Это слишком много, чтобы применять ML для оценки релевантности документа, и, чтобы сузить выбор, существует этап кандидатогенерации. Генераторы бывают тупыми - например, какие-нибудь фильтры по ключевым словам, но бывают и умные, основанные на эмбеддингах.

Идея следующая: у нас есть эмбеддинг пользователя u и N эмбеддингов документов d, и мы хотим взять k ближайших к пользователю документов. Проблема в том, для точного ответа на такой запрос нам придётся считать все N расстояний между u и d, но такие вычисления мы не можем себе позволить. Но нам и не нужен точный ответ, подойдут и просто k близких к u векторов. Такая постановка называется "approximate nearest neighbor search". HNSW - это на сегодня топовый способ решения такой задачи.

Navigable Small World (NSW) - одна из двух ключевых компонент, работает так: построим граф из всех документов, соединив рёбрами между собой ограниченное количество ближайших соседей к каждому документу. Когда нам поступает запрос на поиск соседей к какому-то вектору q, мы жадно ходим по графу и идём всегда в вершину, которая ближе всего к q. Когда мы попадаем в "локальный минимум", то считаем его ответом. Такая процедура позволяет не считать все расстояния для каждого q.

HNSW добавляет Hierarchical к выше описанной схеме - мы создаём несколько уровней графа для поиска в разных масштабах. На нижнем уровне находятся все вершины, но с каждым повышением уровня остаётся случайный поднабор вершин, таким образом, делая соседей дальше друг от друга и позволяя прыгать дальше на каждом шаге поиска. Поиск начинается с самого верхнего уровня, и, попадая в тупик, мы спускаемся ниже и продолжаем. Это позволяет сократить количество операций. На картинке иллюстрация работа поиска.

Строится граф чуть сложнее, и для интересующихся оставлю ссылки на материалы: статья с объяснением, видео.

@knowledge_accumulator

www.group-telegram.com/sg/knowledge_accumulator.com/117

4.2K viewsedited  Oct 16, 2023 at 07:38

HNSW [2016] - один из столпов современных рекомендательных систем

В больших системах существуют миллионы вариантов того, что можно порекомендовать пользователю. Это слишком много, чтобы применять ML для оценки релевантности документа, и, чтобы сузить выбор, существует этап кандидатогенерации. Генераторы бывают тупыми - например, какие-нибудь фильтры по ключевым словам, но бывают и умные, основанные на эмбеддингах.

Идея следующая: у нас есть эмбеддинг пользователя u и N эмбеддингов документов d, и мы хотим взять k ближайших к пользователю документов. Проблема в том, для точного ответа на такой запрос нам придётся считать все N расстояний между u и d, но такие вычисления мы не можем себе позволить. Но нам и не нужен точный ответ, подойдут и просто k близких к u векторов. Такая постановка называется "approximate nearest neighbor search". HNSW - это на сегодня топовый способ решения такой задачи.

Navigable Small World (NSW) - одна из двух ключевых компонент, работает так: построим граф из всех документов, соединив рёбрами между собой ограниченное количество ближайших соседей к каждому документу. Когда нам поступает запрос на поиск соседей к какому-то вектору q, мы жадно ходим по графу и идём всегда в вершину, которая ближе всего к q. Когда мы попадаем в "локальный минимум", то считаем его ответом. Такая процедура позволяет не считать все расстояния для каждого q.

HNSW добавляет Hierarchical к выше описанной схеме - мы создаём несколько уровней графа для поиска в разных масштабах. На нижнем уровне находятся все вершины, но с каждым повышением уровня остаётся случайный поднабор вершин, таким образом, делая соседей дальше друг от друга и позволяя прыгать дальше на каждом шаге поиска. Поиск начинается с самого верхнего уровня, и, попадая в тупик, мы спускаемся ниже и продолжаем. Это позволяет сократить количество операций. На картинке иллюстрация работа поиска.

Строится граф чуть сложнее, и для интересующихся оставлю ссылки на материалы: статья с объяснением, видео.

@knowledge_accumulator

BY Knowledge Accumulator