В первых двух частях этой серии мы обсудили два фундаментальных алгоритма поиска информации: индекс инвертированного файла и квантование произведения. Оба они оптимизируют производительность поиска, но фокусируются на разных аспектах: первый ускоряет скорость поиска, а второй сжимает векторы до меньшего представления с эффективным использованием памяти.
В этой статье мы объединим преимущества обоих подходов для создания быстрого алгоритма с эффективным использованием памяти. Для справки, большинство обсуждаемых идей будет основано на этой бумаге.
Остаточные векторы
Прежде чем углубиться в детали, я хотел бы объяснить, что такое остаточные векторы, и дать простую интуицию об их полезных свойствах. Мы будем использовать их позже при построении алгоритма.
Представьте, что мы построили кластер точек. Остаток – это смещение точки (вектора) от ее центра тяжести. По сути, чтобы найти невязку для определенного вектора, мы вычитаем из него вектор центроида. Если кластер был построен с помощью алгоритма k-средних, то центроид кластера является средним значением всех точек, принадлежащих этому кластеру. Таким образом, снятие остатков со всех точек будет эквивалентно вычитанию из них среднего значения. Вычитая среднее значение, точки будут центрироваться вокруг 0.
Мы можем наблюдать следующий факт:
Замена исходных векторов их остатками не меняет их относительного положения друг к другу.
То есть расстояние всегда остается одним и тем же. Давайте просто посмотрим на второе уравнение на рисунке ниже, где мы вычитаем среднее значение из вектора. Средний член просто сокращается — все выражение становится идентичным евклидову расстоянию.
Мы доказали этот факт, используя формулу для метрики L2 (евклидово расстояние). Важно помнить, что это правило может не работать для других метрик.
Итак, если для заданного запроса наша цель — найти ближайшего соседа, нам нужно вычесть среднее значение из запроса и перейти к обычной процедуре поиска среди остатков.
Прямо сейчас давайте рассмотрим другой пример с двумя кластерами, где мы вычисляем остатки для векторов каждого кластера отдельно. Вычитание среднего значения центроида из каждого вектора кластера приведет к центрированию всех векторов вокруг 0. Это полезное наблюдение, которое мы будем использовать в будущем. Кроме того, для данного запроса мы можем вычислить остатки запроса для всех кластеров. Остатки запроса позволяют вычислить расстояния до исходных остатков кластера.
Обучение
А теперь вернемся к самому интересному! Для векторной базы данных сначала мы строим инвертированный файловый индекс, который делит набор векторов на n разделов и, таким образом, уменьшает область поиска во время вывода.
Внутри каждого раздела мы вычисляем центроид и вычитаем его из каждого вектора. В результате векторы из всех разделов становятся ближе друг к другу и центрируются вокруг 0. Мы удаляем исходную базу данных векторов и вместо этого сохраняем остатки.
Теперь мы берем векторы из всех разделов и запускаем алгоритм квантования произведения. Важный аспект: мы не запускаем его для каждого раздела отдельно — это было бы неэффективно, поскольку количество разделов обычно велико, что приводит к необходимости большого объема памяти. для хранения всех кодовых книг. Вместо этого мы запускаем квантизацию произведения для всех остатков из всех разделов одновременно. По сути, теперь каждое подпространство содержит подвекторы из всех разделов. Затем для каждого подпространства выполняется алгоритм кластеризации и строятся k кластеров с их центроидами.
Какова была важность замены векторов их остатками? Если бы мы не заменяли векторы их остатками, то каждое подпространство содержало бы больше различных подвекторов (помните, что до того, как каждое подпространство содержало подвекторы из разных непересекающихся разбиений, эти разбиения могли быть очень далеко друг от друга в пространстве). Теперь векторы (остатки) из разных разделов перекрываются друг с другом. Поскольку теперь у нас меньше разнообразия в каждом подпространстве, для эффективного представления векторов требуется меньше значений воспроизведения. Другими словами:
При той же длине кодов PQ, что и раньше, мы можем более точно представлять векторы, потому что они имеют меньшую дисперсию.
Вывод
Для заданного запроса мы ищем k ближайших центроидов диаграммы Вороного. Все точки внутри этих областей будут нашими кандидатами. Поскольку наши исходные векторы были заменены их остатками, нам также нужно найти остаток вектора запроса. Однако нам нужно вычислить остаток запроса отдельно для каждого раздела Вороного (поскольку каждый регион имеет разные центроиды). Нашими кандидатами будут только остатки из выбранных областей Вороного, приблизительные расстояния до которых мы рассчитаем позже.
Остаток запроса затем разбивается на подвекторы. Как и в исходном алгоритме квантования произведения, для каждого подпространства мы вычисляем матрицу расстояний, содержащую расстояния от центроидов подпространства до подвектора запроса. Но имейте в виду, что остаток запроса различен для каждого раздела Вороного. По сути, это означает, что матрицу расстояний необходимо вычислять отдельно для каждого остатка запроса. Это цена вычислений, которую мы платим за оптимизацию.
Наконец, мы суммируем частичные расстояния, как мы делали ранее в алгоритме PQ.
Сортировка результатов
После того, как все расстояния рассчитаны, нам нужно выбрать k ближайших соседей. Чтобы сделать это эффективно, мы поддерживаем структуру данных MaxHeap. Его емкость ограничена k, и на каждом шаге он сохраняет k текущих наименьших расстояний. Всякий раз, когда рассчитывается новое расстояние, мы добавляем его в MaxHeap, только если значение расстояния меньше, чем наибольшее значение в MaxHeap. После расчета всех расстояний ответ на запрос уже хранится в MaxHeap. Преимуществом использования MaxHeap является быстрое время сборки, которое составляет O(n).
Производительность
Алгоритм использует преимущества как инвертированного файлового индекса, так и квантования продукта. В зависимости от количества разбиений Вороного, которые мы исследуем во время вывода, мы должны вычислить такое же количество матриц субвекторов и центроидов и сохранить их в памяти. Но по сравнению с общими преимуществами, которые мы получаем, это довольно хороший компромисс.
реализация FAISS
FAISS реализует описанный алгоритм в классе IndexIVFPQ.
Память, необходимая для хранения одного вектора, такая же, как и в исходном методе квантования произведения, за исключением того, что теперь мы добавляем еще 8 байтов для хранения информации о векторе в индексе инвертированного файла.
Ресурсы
Заключение
Используя знания из предыдущих частей статьи, мы рассмотрели реализацию современного алгоритма, обеспечивающего высокое сжатие памяти и ускоренную скорость поиска. Этот алгоритм широко используется в информационно-поисковых системах, когда мы имеем дело с миллиардами строк данных.
🚀 Спасибо, что читаете!
