Как механизм отзыва векторов Файсса может быстро найти ближайшего соседа

Добро пожаловать вмоя маленькая станцияповернись~~

задний план

FaissЭто механизм поиска векторов Facebook с открытым исходным кодом, который используется для поиска N векторов, наиболее похожих на определенный вектор.

Первый выпуск Faiss был выпущен 23.02.2018, но его автор Matthijs уже опубликовал статью в 2011 году, прежде чем присоединиться к Facebook.статья о поиске ближайшего соседа, Faiss основан на идее этой статьи. После прочтения этой статьи метод индексации Файсса стал ясен.

описание проблемы

Учитывая D-мерный вектори коллекция $\Gamma = y_1,y_2 … y_N$ , необходимо найтиk ближайших соседей с кратчайшим расстоянием.

Взяв в качестве примера евклидово расстояние, его можно выразить как:

В нашем приложении $x \in \Gamma$

размер проблемы

Давайте попробуем провести исчерпывающий поиск самым грубым способом, чтобы увидеть, насколько сложно это решение.

Построить матрицу расстояний: каждые два вектораиФормула для расчета расстояния: $\sqrt{\Sigma{(x_i-y_i)^2}}, i\in [1,D]$ , потраченное время равно, матрица расстояний содержитэлементов, общее время равно
Найдите k ближайших соседей по матрице расстояний.Если используется алгоритм минимальной кучи, временная сложность равна

Выбирать N=2000W, k=1000,D=1000

получить

Матрица расстояний содержит 400T элементов, предполагая, что каждое расстояние представляет собой число с плавающей запятой, занимающее 32 бита и занимающее не менее 1600 ТБ пространства.
Временная сложность построения матрицы расстояний порядка величины $10^{17}$
Временная сложность нахождения k ближайших соседей по матрице расстояний порядка величины

Ближайшие соседи Офлайн

Вообще говоря, набор векторов обновляется каждый день, в это время вы можете попытаться сохранить k ближайших соседей, соответствующих каждому вектору напрямую.

Построение матрицы расстояний + время поиска N k ближайших соседей равно
Создание ближайшего соседа в автономном табличном пространстве

в нашем сценарии получить

Порядок времени, отнимающий много времени для поиска N k ближайших соседей, следующий: $10^{17}$
Место для хранения(удалить после построения) + 320G (при условии, что каждый индекс представлен целым числом, а дробь - числом с плавающей запятой)

Время на поиск k ближайших соседей: O(1)

Векторное квантование

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

Так называемое векторное квантование заключается в преобразовании исходного бесконечного пространства R^D отображать в конечный набор векторов $\mathcal{C} = \{c_i, i\in[1,l]\}$ в, из нихявляется натуральным числом. изменить это с R^D в коллекцию $\mathcal{C}$ Функция обозначается как,но $\forall q(y) \in \mathcal{C}$ , что в теории информации называется $\mathcal{C}$ для кодовой книги.

Конечно, функция отображения здесь не указана произвольно, и необходимо соблюдать принцип минимальной ошибки.Один из способов - установить функцию оптимизации на минимальную квадратичную ошибку $MSE(q)=\mathbb{E}_X[d(q(y),y)^2]$

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

Теперь давайте проанализируем пространственную и временную сложность векторного квантования.

Предположим, мы сопоставляем исходные векторы 2000 Вт с набором размером 20 Вт (в среднем каждая центральная точка представляет 100 векторов, что приводит к большой ошибке)

Матрица расстояний: нужно только хранить корреспонденцию $\mathcal{C}$ Расстояние между векторами, занимаемое пространство равно $|| \mathcal{C} ||^2$ , в этом случае $400G \times 4B=1.6T$
$y \to c \in \mathcal{C}$ Отношение отображения , если вектор идентифицируется как int, общее $N \times 4=80M$ ОЗУ
Временная сложность: временная сложность алгоритма k-средних составляет $O(m_{iter}NkD)$ ,в $m_{iter}$ — количество итераций, N — количество векторов исходного пространства, k — количество центральных точек, а D — размерность вектора. В этом примере временная сложность $4m*10^{15}$ , увеличение количества итераций до 25 уже достигло порядка перебора методом перебора.Пока количество итераций немного увеличивается, временная сложность будет выше.

Квантование продукта PQ (квантование продукта)

Часто распределение между разными частями нашего вектора различно.

Тогда вектор можно разделить наСуществуют разные части, и для каждой части выполняется векторное квантование.Предполагая среднее деление, размерность каждой части составляет D^*=D/m

вектор $[x_1,x_2,…,x_{D^*},…,x_{D-D^*+1},…,x_D]$ , который можно разбить на m групп векторов $[x_{i\_1},x_{i\_2},…,x_{i\_D^*}]$ , кодовая книга для каждой группы $\mathcal{C_i}$ , соответствующий квантователь обозначается как q_i , $\forall q_i(x_{i*}) \in \mathcal{C_i}$ . Тогда окончательная глобальная кодовая книга $\mathcal{C} = \mathcal{C_1} * \mathcal{C_2} ...* \mathcal{C_m}$ , от которого происходит название квантования произведения.

Взяв в качестве примера m=4, чтобы достичь уровня 20 Вт в предыдущем разделе, $|| \mathcal{C_i} ||$ Вам нужно всего лишь достичь 22, и вам нужно всего лишь достичь 67, чтобы восстановить уровень 2000 Вт.

к $\mathcal{C}$ В качестве примера возьмем случай достижения порядка 2000 Вт, количество центральных точек кодовой книги в каждой группе $k^{*}$ равно 67, теперь давайте проанализируем соответствующую пространственную и временную сложность

Матрица расстояний между центральными точками: примечание $|| \mathcal{C_i} ||$ за, размер матрицы расстояний. Если расстояние представлено числом с плавающей запятой, матрица расстояний в этом примере составляет около 70M.
$y \to c \in \mathcal{C_i}$ Отношение отображения , если вектор идентифицируется как int, общее $m \times N \times 4=320M$ ОЗУ
Временная сложность кластеризации: временная сложность алгоритма k-средних по-прежнему $O(m_{iter} NkD)$ , в этом примере необходимо выполнить k-средних для m групп соответственно, а общая временная сложность равна $O(mNk^*D*m_{iter})$ , в этом случае $5m*10^{12}$ , что на 3 порядка меньше, чем в предыдущем примере
Временная сложность матрицы расстояний: произведение размерности D на количество элементов матрицы расстояний, т.е.,о $7 \times 10^{10}$

Существенная причина, по которой квантование произведения значительно сокращает занимаемое пространство, заключается в том, что выраженное векторное пространство равно (k^*)^m , но занимает дисковое пространство mk^*

Эмпирическое значение, приведенное в статье, равно k^*=256 , m=8 , соответствующий размер векторного пространства равен $2^{64}$ записаться на прием $1.8\times 10^{19}$

Вычисление расстояния в сценарии квантования

В сценарии без квантизации расчет расстояния рассчитывается напрямую для двух точек. || x-y || _2

Но в случае квантования расстояние между x и y нужно вычислять не напрямую, а через центральную точку. Существует два варианта этого подхода:

SDC

SDC (вычисление симметричного расстояния): расстояние между двумя векторами измеряется расстоянием между центральными точками двух векторов. Ошибка меньше или равна расстоянию от x до центральной точки + расстоянию от y до центральной точки.

В сценарии PQ расстояние SDC выражается как: $SDC (x,y)= \hat{d}(x,y)=d(q(x),q(y))=\sqrt{\Sigma_j{d(q_j(x),q_j(y))^2}}$

Поскольку расстояние между центральными векторами было сохранено (см. предыдущий раздел), для расчета расстояния между x и y вам нужно только просмотреть таблицу Размер таблицы составляет около 70M, и она принимает порядки величин. вычислить матрицу расстояний. $10^{10}$

Если вы не хотите занимать пространство матрицы расстояний, временная сложность равна O(Dmk^*) , о 10^5

ADC

ADC (асимметричное вычисление расстояния): расстояние между x и y измеряется расстоянием между центральными точками, в которых расположены x и y. Используйте свойства треугольников: разница между двумя сторонами меньше, чем между третьей стороной, поэтому ошибка должна быть меньше или равна расстоянию между y и центральной точкой

)

В сценарии PQ расстояние АЦП выражается как: $\tilde{d}(x,y)=d(x,q(y))$

Пусть i-й элемент вектора x равен u_i(x) ,но $ADC(x,y)=\sqrt{\Sigma_j{d(u_j(x),q_j(y))^2}}$

В этом сценарии, если вы хотите получить расстояние, просматривая таблицу, размер матрицы расстояний в процессе подготовки данных составляет около O(mnk^* )*4=20G (каждый вектор должен вычислять расстояние от каждого вектора центра в m группах), трудоемкий порядок величины $10^{13}$

Если он рассчитывается напрямую, сложность такая же, как и у версии SDC без просмотра таблицы. O(Dmk^*) , о 10^5

Если используется стратегия поиска по таблице, АЦП платит больше памяти в случае более высокой точности.

IVFADC

В предыдущем разделе время прямого вычисления в основном тратилось на сравнение со всеми центральными векторами. Естественный подход состоит в том, чтобы сначала найти приблизительный узел-кандидат в центр и избежать вычислений с большим количеством точек, которые просто не могут быть их ближайшими соседями.

Грубое квантование + остаточное квантование

Поэтому Маттис предложил в статье процесс грубого квантования + остаточное квантование. В частности, сначала необходимо создать набор данных размером $kk^{'}$ (Предположим, что значение равно 1000) небольшая кодовая книга $\mathcal{C_c}$ , квантователь обозначается как q_c , поэтому каждый вектор будет иметь невязку r(y)=y-q_c(y) . Исходный вектор может иметь особенно большую разность/дисбаланс распределения, но эту проблему можно значительно облегчить, обработав результаты по остаточному принципу.

Правильно снова r(y) Используя шаг PQ, поскольку r(y) «Энергия» относительно исходного вектора ниже, поэтому моделирование можно выполнить более точно с помощью шага PQ. Обозначим квантователь шага PQ как q_p , то y проходит через q_c(y)+q_p(y-q_c(y)) Представлять. В этом случае расстояние между двумя векторами x, y d(x,y) можно аппроксимировать как

\ddot{d}(x,y) =d (x,q_c(y) + q_p(y-q_c(y))) = d(x - q_c(y) , q_p(y-q_c(y))) = \sqrt{\Sigma_jd({u_j(x-q_c(y)),q_{p_j}(u_j(y-q_c(y))))^2}}

Помните размер кодовой книги для остаточного квантования как k_p (Возьмите 64 в качестве примера), если вы хотите u_j(x-q_c(y)) Рассчитано заранее, то есть рассчитано заранее для каждого x и всех центральных векторов $c \in \mathcal{C_c}$ расстояние, а временная сложность $O(DNkk^{'} )$ , пример в этой статье $10^{13}$ , пространственная сложность $O(Nkk^{'})$ , пример в этой статье: 20G*4B=80GB.

структура индекса

С помощью инвертированного индекса можно значительно повысить эффективность поиска.

используется в диссертации $kk^{'}$ Перевернутый индекс для хранения приблизительной центральной точки c_i список соответствующих векторов $\mathcal{L}_i$ . Каждый вектор представлен в следующем формате, где id — это идентификатор индекса вектора, а code — это соответствующий список индексов центральной точки PQ. Количество центральных точек для каждой группы в PQ равно k^* , тебе нужно $\lceil log_2{k^*} \rceil$ бит, чтобы указать, какая центральная точка, в общей сложности $m*\lceil log_2{k^*} \rceil$ биты

При поиске вы можете q_c Функция получает все векторы из соответствующего кластера

процесс индексации

квантователемвекторсопоставить с
Рассчитать остатки
остатокколичественно, который содержит m групп
построитьзапись и добавить вСоответствующий инвертированный список $\mathcal{L}$

процесс поиска

Во многих случаях ближайший сосед не обязательно находится в текущем кластере, поэтому необходимо искать не только текущий кластер, но и соседние кластеры.

рассчитать $\mathcal{C_c}$ Ближайший к входному параметру xцентральная точка,
Если центральную точку все еще нужно обработать, удалите центральную точку., и вычислить соответствующий. В противном случае перейдите к шагу 6
рассчитатьРасстояние от центральной точки в каждой группе, $O(m*\frac{D}{m}*k^{*}) = O(Dk^*)$
Поскольку соответствующий индекс в том же инвертированном индексеиодинаковы, поэтому расстояние между x и y нужно смотреть только на остаточное расстояние. так какРасстояние до каждой центральной точки было рассчитано, поэтому для каждого вектора нужно просмотреть таблицу только m раз. О (м)
Вернуться к шагу 2
Используйте min-heap, чтобы получить K векторов с наименьшим расстоянием, поскольку ожидаемое количество элементов для каждого инвертированного индекса равно $\frac{N}{kk^{'}}$ , так долго $O((\frac{N}{kk^{'}}-K)*logK)$

Длительность всего процесса поиска составляет: $O((kk^{'}-w)*log{w}) + w*(O(Dk^*)+O(m))+O((\frac{N}{kk^{'}}-K)*logK)$

Экспериментальный эффект

оптимизация

При остаточном квантовании остатки от разных векторов к их соответствующим центрам объединяются для квантования, что фактически подразумевает предположение, что распределения в разных кластерах одинаковы. Это предположение вносит определенную ошибку, но в противном случае объем памяти будет увеличиваться. $kk^{'}$ раз
Различные группировки векторов могут привести к очень разным результатам. Эксперименты в статье показывают, что по сравнению со случайной группировкой связанные поля должны быть помещены в одну и ту же группу, что может повысить точность в 2-3 раза в некоторых сценариях. Перед индексированием векторы могут быть организованы в подходящем порядке с помощью некоторых методов анализа подобия.
Если для него выбрано значение 1, это приведет к поиску только вектора в текущем кластере, и результат может быть намного хуже, чем SDC. Рекомендация автора в статье – принять, но в разных сценариях сначала нужно выполнить тесты, чтобы достичь баланса между объемом памяти и потреблением времени.

Суммировать

По сути, Файсс кодирует вектор как комбинацию конечного числа векторов, преобразуя вычисление расстояния между векторами в расстояние между конечным числом векторов, которое можно вычислить заранее.

Ключ к упрощению расчета:

Вектор-кандидат сводится к вектору окрестности
Выразительная сила, вызванная квантованием продукта, подскочила: $ka \ll (a)^k$
Матрица расстояний результата квантования произведения предварительно вычисляется, так что вычисление расстояний становится операцией поиска в таблице. (квантование продукта поддерживает допустимые требования к пространству для матрицы расстояний)

Например: Следующие векторы 12, 13 ![пример_1]Боюсь 1-solve.byte IMG.com/to S-talent-i-he 2…)

Сначала выполните грубый расчет кластеризации на них

Обнаружено, что их идентификаторы кластеров равны 1

Затем разделите на три группы, чтобы вычислить остатки

Квантование продукта остатков

Тогда расстояния векторов 12 и 13 могут быть получены непосредственно путем накопления трех наборов произведений для количественной оценки векторных расстояний, в которых векторные расстояния рассчитываются заранее.

$d(12,13)=\sqrt{(a_{12})^2+(b_{23})^2+(c_{34})^2}$

использованная литература:«Квантование произведения для поиска ближайшего соседа»: Lear.in ria LP ES. положить в /pubs/2011/J…