Приближённый поиск ближайших соседей
Определение
Приближённый поиск ближайших соседей — поиск близких к запросу объектов по выбранной метрике, допускающий пропуск некоторых точных ближайших соседей. Такой пропуск отличается от другой проблемы: найденный текст может не отвечать на вопрос.
Также ищут: approximate nearest neighbor · ANN search · ANN-поиск · приближённый поиск векторов
Зачем это знать
Если ANN пропустил соседа из точной выдачи, это ошибка приближения. Если и точная выдача не содержит нужного фрагмента, проверьте коллекцию, представления и метрику. Эти причины нельзя различить по одному неверному ответу модели.
Карта понятия
Что подтверждено
В HNSW поиск проходит по многоуровневому графу от верхнего уровня к нижнему, используя найденный ближайший элемент как точку входа на следующий уровень.
Граница применимости: Malkov и Yashunin, arXiv:1603.09320v4, разделы 3–4 и алгоритм 5; описание HNSW без универсальных параметров и обещаний производительности.
В этом курсе recall@k — число общих соседей в точном и приближённом списках, делённое на k. Сравнивают по k различных идентификаторов.
Граница применимости: Учебное определение на основе точного и приближённого поиска: одинаковы запрос, набор векторов, метрика, k и правило выбора при равных оценках; 1 ≤ k ≤ число векторов. Это не универсальное соглашение библиотек.
Совпадение ANN с точным top-k считают по соседям. В DPR top-k accuracy считают по вопросам: для какой их доли среди первых k фрагментов есть ответ.
Граница применимости: Редакционное сопоставление определения recall@k этого курса с DPR, раздел 2; знаменатели — k соседей для одного запроса и число проверенных вопросов соответственно.
Что проверить
- Зафиксируйте запрос, набор векторов, метрику и число соседей k.
- Сравните точную и приближённую выдачи с одинаковым правилом разрешения равных оценок.
- Запишите формулу и знаменатель метрики совпадения.
- Отдельно проверьте наличие нужного факта в найденных текстах.
Первоисточники
- Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
Прочитан PDF arXiv:1603.09320v4, разделы 3–4 и алгоритм 5. Используется схема поиска по уровням графа без универсальных параметров и обещаний производительности.
- Getting started
Прочитаны IndexFlatL2 и Searching: brute-force L2, поиск k соседей и сортировка по возрастанию расстояния в этом примере.
- Dense Passage Retrieval for Open-Domain Question Answering
Разделы 2–3: отбор фрагментов и top-k retrieval accuracy. Знаменатель этой метрики — число проверенных вопросов.
Утверждения: 03