Desempenho da pesquisa vetorial: A ascensão do recall

A introdução da pesquisa vetorial (KNN), com sua pontuação de similaridade baseada em distância, no paradigma de pesquisa existente exigiu uma mudança na forma como pensávamos sobre resultados "relevantes" e como medi-los. 

Os índices baseados em texto usam tf-idf como seu mecanismo de pontuação, com os resultados permanecendo os mesmos em todas as pesquisas, considerando um corpus fixo de palavras (aqui, os documentos em uma partição).

Em contrapartida, uma pesquisa KNN não garante o mesmo nível de idempotência. Os resultados são aproximado, muitas vezes diferentes entre as consultas. Este artigo é sobre a mudança da equipe de pesquisa de exata para aproximada. Ao longo do caminho, respondemos a perguntas sobre por que resultados aproximados podem se tornar o novo normal e o grau de aproximação aceitável.

Preparando o palco 

Cada partição de índice de pesquisa é um Bleve índice que compreende vários segmentos de zap (arquitetura segmentada), com cada segmento contendo um índice de vetor. Eles são compactados periodicamente por uma rotina de fusão para o índice Bleve.

Usos de pesquisa FAISS para a criação de índices vetoriais, treinamento, pesquisa e outras funcionalidades relacionadas. 

As duas grandes classes de índices usadas atualmente pelo Couchbase Search são:

1. 1. Índices planos - realizam uma pesquisa exaustiva, semelhante ao armazenamento dos vetores em uma matriz.
   2. Índices de FIV - índices baseados em centroides que envolvem o agrupamento (KMeans, neste caso) do conjunto de dados e, em seguida, o preenchimento desses agrupamentos.

Um resumo sobre o KNN 

Como mencionei anteriormente, o material de teste (e, igualmente importante, nosso pensamento!) estava predisposto à pontuação exata. A pesquisa baseada em texto é fundamentalmente exaustivo em que um índice invertido inclui todos os tokens nos documentos da partição. Todos os documentos em um índice invertido são elegíveis para a pesquisa e será pesquisado. 

Um índice vetorial baseado em centroide, em comparação, limita o conjunto de vetores elegíveis logo de cara, pesquisando apenas em clusters específicos, que podem ou não ser os mesmos para cada consulta. Isso significa que, para uma determinada consulta, a pesquisa exaustiva e potencialmente demorada é trocada pela aproximação.  

(Se a palavra "recall" o deixou um pouco desconcertado, aguarde - falaremos sobre isso daqui a pouco).

Considerando que limitamos nosso espaço de pesquisa logo no início, é importante fazer o "agrupamento correto". 

Uma das primeiras etapas de uma pesquisa envolve a escolha de quantos e quais clusters serão pesquisados. Se forem poucos, você acabará perdendo alguns vetores potencialmente semelhantes. Se forem muitos, a latência da pesquisa aumentará significativamente para um aumento relativamente pequeno na qualidade da pesquisa. 

A métrica usada para a qualidade da pesquisa é recall - qual porcentagem dos resultados retornados é objetivamente a mais próxima dos vetores de consulta. O conjunto dos vetores mais próximos do vetor de consulta é chamado de verdade básica e é usado como linha de base ao medir a recuperação. Como a pontuação KNN é a distância entre dois vetores, ela é independente dos outros documentos na partição (ao contrário do tf-idf) e, o que é mais importante, isso ajuda em uma comparação objetiva entre a verdade terrestre avaliada de forma independente e o resultado. 

Quanto (Aproximação) é demais (Aproximação): Recall de direção de 0,06 a 90+:

Munidos de todo esse conhecimento, decidimos começar a testar a recuperação. Nossos primeiros testes mostraram uma recuperação surpreendentemente baixa, próxima de 0 - 0,06 para ser mais preciso. 

Embora tivéssemos transferido a pesquisa do índice de vetores para o FAISS, havia alguns aspectos que precisávamos tratar do nosso lado. Um deles é o mapeamento dos IDs dos documentos para os vetores. A pesquisa mapeia cada número de documento para um hash de vetor exclusivo. Esses hashes são então passados como IDs personalizados para FAISS para aproveitar o suporte ao mapeamento de vetores para ID personalizada e as pesquisas retornam a ID personalizada. Considerando que os vetores (cada um com o mesmo tamanho) são concatenados em um grande vetor, assim como os IDs, a ordenação correta determina o mapeamento do vetor para o ID. Internamente, o FAISS usa um hashmap para armazenar vetores e seus IDs.

Uma análise mais detalhada mostrou que estávamos mapeando IDs ordenados aleatoriamente para vetores ao reconstruir índices durante uma mesclagem, o que fazia com que o conjunto de resultados fosse essencialmente aleatório. Isso estava afetando os índices flat e IVF, pois ambos dependiam do pedido das IDs ao recuperar os resultados. 

Depois que o problema de ordenação foi resolvido, juntamente com algumas outras correções de caminho de mesclagem, o recall saltou para cerca de 70. Agora estávamos no caminho certo - não tínhamos nenhum bug fundamental nos atormentando. Começamos a dar uma olhada nos botões que poderíamos ajustar. 

Botões giratórios - Centroides e Nprobe

A estratégia inicial usava um número fixo (100) de centroides para todos os índices de vetores com mais de 10 mil vetores. Em essência, isso era tratar 1 milhão de vetores da mesma forma que 20 mil vetores.

Os padrões de clustering do FAISS têm um número mínimo (39) e máximo (256) de pontos por cluster. Os pontos restantes são subamostrados. 100 centroides podem ter sido suficientes para 100 * 256 = 25600 vetores no máximo, mas para qualquer coisa acima disso, havia excessivo subamostragem ocorrendo, conforme refletido na recuperação. O que precisávamos era de uma fórmula para os centroides que se ajustasse ao conjunto de dados.

O que estamos buscando para otimizar: Recall@Ksem que a indexação e a latência da pesquisa sejam muito afetadas, se possível. 

Configuração

A configuração foi bastante simples - scripts criando um índice FAISS (treinando e adicionando IDs) e consultando-os, com os resultados da verdade básica conhecidos de antemão. Eu usei o SIFT10K e SIFT1M conjuntos de dados do documento original já que eles forneceram vetores de verdade usando a distância euclidiana. O recall@K foi o recall médio em 100/10k consultas, respectivamente.

Aumento dos centroides

A primeira fase envolveu o ajuste do número de clusters.

Resultados do Sift1M - 10.000 consultas

Resultados do Sift10k - 100 consultas

Insights

1. 1. A linha de base atual mostra um recall de 0,61, que pode ser definitivamente melhorado.
   2. O recall diminuições com um aumento no número de centroides. 
   3. O tempo de pesquisa diminui devido a aumento da localização mesmo com o aumento do tempo de treinamento.

O inverso é o aumento do tempo de busca, apesar do baixo tempo de treinamento, para um número menor de centroides, pois isso implica a busca em células maiores com um número maior de vetores.

Agora que foi estabelecido que o aumento dos centroides tem um impacto negativo na recuperação, vamos tentar entender intuitivamente por que isso acontece.

Com um conjunto de dados de tamanho fixo, aumentar o número de centroides pode diminuir o número de documentos em cada cluster. Com clusters menores, nós pesquisar menos vetores em geral e escolha os K vetores mais próximos.

Portanto, um aumento no número de clusters deve ser acompanhado por um aumento correspondente no número de clusters pesquisados.

Aumentando o nprobe

Sift1M - 10.000 consultas

Sift10k - 100 consultas

Insights

1. 1. Para o conjunto de dados 1M, a recuperação da linha de base é baixa devido a nprobe = 1.
      • Quando isso é corrigido, a recuperação aumenta rapidamente e não é mais uma preocupação, apesar da subamostragem.
      • No entanto, com uma grande capacidade de memorização vem uma maior latência de pesquisa. 
   2. Para o conjunto de dados de 10 mil, a recuperação da linha de base, embora não seja tão baixa quanto a do conjunto de dados de 1 milhão, ainda é motivo de preocupação.
      • Isso também é facilmente remediado com o aumento da nprobe. 

Os padrões para determinar nlist e nprobe foram então alterados para:

Basta dizer que foi assim que a equipe se sentiu quando conseguimos encontrar uma solução para o problema do recall:

Ajuste de um índice vetorial

O ajuste de um índice vetorial do Couchbase definitivamente não é algo para se preocupar.

Como a troca entre recuperação e latência é crucial na pesquisa vetorial, queríamos permitir ao usuário alguma flexibilidade quanto ao modo como desejava se apoiar. Juntamente com as considerações voltadas para o usuário, como facilidade de compreensão e intuitividade, a prova de futuro (compatibilidade futura) e a arquitetura segmentada implicaram algumas limitações na API.

Cada segmento é um índice vetorial com um número diferente de vetores. No momento da consulta, um o usuário não está ciente da distribuição de dados em nível de partição, muito menos em nível de segmento. Dependendo da natureza das mutações (grande número de exclusões, por exemplo), o o número de vetores pode variar bastante ao mesclar segmentos. Portanto, um não é possível aplicar uma abordagem única para todos os segmentos.  

Além disso, a compatibilidade futura exige que o os botões não são específicos para um tipo de índice FAISS já que essa é uma área que deve ser, em sua maior parte, abstraída do usuário, apesar de alterar os tipos de índice usados na implementação. Por exemplo, o usuário que especifica nprobe ou lista negra seria muito específico para o índice de FIV e seria uma mudança radical se os tipos de índice que alimentam a pesquisa de vetores fossem alterados. 

Permitir que o usuário alternar a métrica a ser otimizada (recall/latência) se encaixa no perfil. Embora o ajuste da recuperação seja feito de forma diferente para um índice IVF e, digamos, um índice HNSW, a recuperação é aplicável a ambos e pode ser ajustada no nível do segmento. Nos dados acima, a duplicação do nprobe leva a uma duplicação correspondente do tempo de pesquisa, mas com o aumento correspondente na recuperação sendo de poucos pontos. Portanto, ao otimizar a latência, reduzir pela metade o nprobe proporciona ganhos de latência sem afetar muito a recuperação. 

A configuração de definição de índice em que o usuário pode alternar entre recall e latência pode ser modificada é vector_index_optimized_for. Essa configuração foi documentada na documentação oficial. 

Para mais aprofundamentos e desenvolvimentos no espaço do Couchbase Vector Search, fique atento!