Introdução à busca por similaridade vetorial
Nos tutoriais anteriores, demos uma olhada em dados não estruturados, bancos de dados vetoriais e Milvus - o banco de dados vetorial de código aberto mais popular do mundo, usado para busca por similaridade. Também abordamos brevemente a ideia de embeddings, vetores de alta dimensão que servem como excelentes representações semânticas de dados não estruturados. Uma observação importante a lembrar - embeddings e representações vetoriais que estão "próximos" uns dos outros representam partes de dados semanticamente semelhantes.
Nesta introdução à busca vetorial (também conhecida como busca por similaridade), definiremos o que ela é e responderemos a algumas perguntas fundamentais sobre ela. Em seguida, desenvolveremos esse conhecimento examinando um exemplo de embedding de palavras e vendo como partes semanticamente semelhantes de dados não estruturados estão "perto" umas das outras, enquanto partes diferentes de dados não estruturados estão "longe" umas das outras. Isso levará a uma visão geral de alto nível da busca pelo vizinho mais próximo, um problema computacional que envolve encontrar o(s) vetor(es) mais próximo(s) de um vetor de consulta com base em uma métrica de distância unificada. Abordaremos alguns métodos bem conhecidos (algoritmos de busca por similaridade vetorial) para busca pelo vizinho mais próximo (incluindo meu favorito - ANNOY), além de métricas de distância comumente usadas.
Vamos mergulhar.
O que é Busca Vetorial ou Busca por Similaridade Vetorial?
Busca vetorial, também conhecida como busca por similaridade vetorial, busca pelo vizinho mais próximo ou busca semântica, é uma técnica usada em sistemas de recuperação de dados e recuperação de informações para encontrar itens ou pontos de dados que sejam semelhantes ou intimamente relacionados a um determinado vetor de consulta. Diferentemente da busca tradicional por palavras-chave, que corresponde a palavras ou frases exatas, a busca semântica entende a intenção e o significado contextual por trás de uma consulta, permitindo retornar resultados mais relevantes mesmo quando as palavras-chave exatas não estão presentes no conteúdo. Na busca vetorial, representamos pontos de dados, como imagens, textos e áudio, como vetores em um espaço de alta dimensão. O objetivo da busca vetorial é pesquisar e recuperar com eficiência os vetores mais relevantes que sejam semelhantes ou mais próximos de um vetor de consulta.
Normalmente, métricas de distância como a distância euclidiana ou a similaridade de cosseno medem a similaridade entre vetores. A proximidade do vetor no espaço vetorial determina quão semelhante ele é. Para organizar e exibir resultados de busca para vetores com eficiência, os algoritmos de busca vetorial usam estruturas de indexação, como estruturas baseadas em árvores ou técnicas de hashing.
A busca vetorial é central para bancos de dados vetoriais e tem várias aplicações, incluindo sistemas de recomendação, recuperação de imagens e vídeos, processamento de linguagem natural, detecção de anomalias e chatbots de perguntas e respostas. Usar busca semântica torna possível encontrar itens, padrões ou relacionamentos relevantes dentro de dados de alta dimensão, possibilitando uma recuperação de informações mais precisa e eficiente.
A busca vetorial é um método poderoso para analisar e recuperar informações de espaços de alta dimensão. Ela permite que os usuários encontrem itens semelhantes ou intimamente relacionados a uma determinada consulta, tornando-a crucial em vários domínios. Aqui estão os benefícios da busca vetorial:
Recuperação baseada em similaridade— A busca semântica permite a Recuperação baseada em similaridade, possibilitando que os usuários encontrem itens semelhantes ou intimamente relacionados a uma determinada consulta. A Recuperação baseada em similaridade é crucial em vários domínios, como sistemas de recomendação, onde os usuários esperam recomendações personalizadas com base em suas preferências ou semelhanças com outros usuários.
Análise de Dados de Alta Dimensionalidade — Com a crescente disponibilidade de dados de alta dimensionalidade, como imagens, áudio e dados textuais, os métodos de busca tradicionais tornam-se menos eficazes. A busca vetorial fornece uma maneira poderosa de analisar e recuperar informações de espaços de alta dimensionalidade, permitindo uma exploração de dados mais precisa e eficiente.
Busca pelo Vizinho Mais Próximo — Algoritmos eficientes de busca pelo vizinho mais próximo encontram os vizinhos mais próximos de um determinado vetor de consulta. A busca pelo vizinho mais próximo é útil para tarefas críticas, como busca por similaridade de imagens ou documentos, Retrieval baseado em conteúdo ou detecção de anomalias, que exigem encontrar as correspondências mais próximas ou itens semelhantes.
Experiência do Usuário Aprimorada— Ao aproveitar a busca semântica, as aplicações podem fornecer aos usuários resultados mais relevantes e personalizados. Seja entregando recomendações relevantes, recuperando imagens visualmente semelhantes ou encontrando documentos com conteúdo semelhante, a busca vetorial aprimora a experiência geral do usuário ao fornecer resultados mais direcionados e significativos.
Escalabilidade — Algoritmos de busca vetorial e estruturas de indexação lidam com conjuntos de dados em larga escala e espaços de alta dimensionalidade de forma eficiente. Eles permitem operações rápidas de busca e recuperação, tornando viável realizar consultas baseadas em similaridade em tempo real, mesmo em conjuntos de dados massivos.
Como Funciona um Mecanismo de Busca Vetorial?
Com a popularidade da IA e dos LLMs, todas as ferramentas de desenvolvedor, mecanismos de busca e bancos de dados estão adicionando recursos de busca vetorial ao seu conjunto de funcionalidades e, devido a isso, o termo mecanismo vetorial e Mecanismos de Busca Vetorial são frequentemente usados de forma intercambiável com Bancos de Dados Vetoriais. Mecanismos de Busca Vetorial conduzirão uma busca semântica vetorial (às vezes chamada de Busca Vetorial). A busca vetorial é uma técnica para encontrar itens ou pontos de dados semelhantes em um conjunto de dados com base em sua representação como vetores em um espaço de alta dimensionalidade. Cada item é mapeado para um ponto nesse espaço, com cada dimensão do vetor representando um recurso específico. O processo de busca vetorial envolve indexação, consulta, classificação e recuperação.
Para realizar a busca vetorial, primeiro você representa seus itens de dados como vetores, usando técnicas como Word2Vec ou para dados de texto. Uma estrutura de dados de índice armazena esses vetores de forma eficiente para recuperação rápida, usando métodos como KD-trees ou tabelas hash. Quando um usuário envia um item de consulta, ele é convertido em uma representação vetorial, comparado aos vetores indexados usando métricas de similaridade como similaridade de cosseno ou distância euclidiana, e os itens mais semelhantes são recuperados e classificados.
Casos de Uso da Busca Vetorial
- Busca por similaridade de imagem, vídeo e áudio
- Descoberta de medicamentos com IA
- Mecanismo de busca semântica
- Classificação de sequências de DNA
- Sistema de resposta a perguntas
- Sistema de recomendação
- Detecção de anomalias
- Retrieval Augmented Generation (RAG)
Agora que cobrimos os conceitos básicos da busca vetorial, vamos analisar os detalhes mais técnicos observando um exemplo de embedding de palavras e finalizar com uma visão geral de alto nível da busca pelo vizinho mais próximo.
Comparando embeddings
Assim que os usuários decidem que querem começar a criar busca vetorial em sua solução, a próxima pergunta que frequentemente fazem é “Qual Modelo de Machine Learning devo usar para criar Embeddings Vetoriais.” Antes de escolher um modelo, é importante entender embeddings vetoriais comparando alguns exemplos. Vamos passar por alguns exemplos de embeddings de palavras. Para simplificar, usaremos word2vec, um modelo antigo que usa uma metodologia de treinamento baseada em skipgrams. BERT e outros modelos modernos baseados em transformers poderão fornecer embeddings de palavras mais contextualizados, mas vamos nos ater ao word2vec por simplicidade. Jay Alammar fornece um ótimo tutorial sobre word2vec, se você estiver interessado em usar modelos de machine learning um pouco mais.
Algum trabalho preparatório
Antes de começar, precisaremos instalar a biblioteca gensim e carregar um modelo word2vec.
% pip install gensim --disable-pip-version-check
% wget https://s3.amazonaws.com/dl4j-distribution/GoogleNews-vectors-negative300.bin.gz
% gunzip GoogleNews-vectors-negative300.bin
Requirement already satisfied: gensim in /Users/fzliu/.pyenv/lib/python3.8/site-packages (4.1.2)
Requirement already satisfied: smart-open>=1.8.1 in /Users/fzliu/.pyenv/lib/python3.8/site-packages (from gensim) (5.2.1)
Requirement already satisfied: numpy>=1.17.0 in /Users/fzliu/.pyenv/lib/python3.8/site-packages (from gensim) (1.19.5)
Requirement already satisfied: scipy>=0.18.1 in /Users/fzliu/.pyenv/lib/python3.8/site-packages (from gensim) (1.7.3)
--2022-02-22 00:30:34-- https://s3.amazonaws.com/dl4j-distribution/GoogleNews-vectors-negative300.bin.gz
Resolving s3.amazonaws.com (s3.amazonaws.com)... 52.216.20.165
Connecting to s3.amazonaws.com (s3.amazonaws.com)|52.216.20.165|:443... connected.
HTTP request sent, awaiting response... 200 OK
Length: 1647046227 (1.5G) [application/x-gzip]
Saving to: GoogleNews-vectors-negative300.bin.gz
GoogleNews-vectors- 100%[===================>] 1.53G 2.66MB/s in 11m 23s
2022-02-22 00:41:57 (2.30 MB/s) - GoogleNews-vectors-negative300.bin.gz saved [1647046227/1647046227]
gunzip: GoogleNews-vectors-negative300.bin: unknown suffix -- ignored
Agora que fizemos todo o trabalho preparatório necessário para gerar embeddings de palavras em vetores, vamos carregar o modelo word2vec treinado.
>>> from gensim.models import KeyedVectors
>>> model = KeyedVectors.load_word2vec_format('GoogleNews-vectors-negative300.bin', binary=True)
Exemplo 0: Marlon Brando
Vamos dar uma olhada em como o word2vec interpreta o famoso ator Marlon Brando.
>>> print(model.most_similar(positive=['Marlon_Brando']))
[('Brando', 0.757453978061676), ('Humphrey_Bogart', 0.6143958568572998), ('actor_Marlon_Brando', 0.6016287207603455), ('Al_Pacino', 0.5675410032272339), ('Elia_Kazan', 0.5594002604484558), ('Steve_McQueen', 0.5539456605911255), ('Marilyn_Monroe', 0.5512186884880066), ('Jack_Nicholson', 0.5440199375152588), ('Shelley_Winters', 0.5432392954826355), ('Apocalypse_Now', 0.5306933522224426)]
Marlon Brando trabalhou com Al Pacino em The Godfather e com Elia Kazan em A Streetcar Named Desire. Ele também estrelou Apocalypse Now.
Exemplo 1: Se todos os reis tivessem suas rainhas no trono
Vetores podem ser somados e subtraídos uns dos outros para demonstrar mudanças semânticas subjacentes.
>>> print(model.most_similar(positive=['king', 'woman'], negative=['man'], topn=1))
[('queen', 0.7118193507194519)]
Quem disse que engenheiros não podem curtir um pouco de dance-pop de vez em quando?
Exemplo 2: Apple, a empresa, a fruta, ... ou ambas?
A palavra "apple" pode se referir tanto à empresa quanto à deliciosa fruta vermelha. Neste exemplo, podemos ver que Word2Vec retém ambos os significados.
>>> print(model.most_similar(positive=['samsung', 'iphone'], negative=['apple'], topn=1))
>>> print(model.most_similar(positive=['fruit'], topn=10)[9:])
[('droid_x', 0.6324754953384399)]
[('apple', 0.6410146951675415)]
"Droid" refere-se ao primeiro smartphone 4G LTE da Samsung ("Samsung" + "iPhone" - "Apple" = "Droid"), enquanto "apple" é a 10ª palavra mais próxima de "fruit".
Estratégias de busca vetorial
Agora que vimos o poder dos embeddings vetoriais, vamos dar uma breve olhada em algumas das formas pelas quais podemos conduzir uma busca de vizinhos mais próximos. Esta não é uma lista abrangente; vamos apenas passar brevemente por alguns métodos comuns para fornecer uma visão geral de alto nível de como a busca vetorial é conduzida em escala. Observe que alguns desses métodos não são exclusivos entre si — é possível, por exemplo, usar quantização em conjunto com particionamento de espaço.
(Também abordaremos cada um desses métodos em detalhe em tutoriais futuros, então fique atento para mais.)
Busca linear
O algoritmo de busca de vizinho mais próximo mais simples, porém mais ingênuo, é a boa e velha busca linear: calcular a distância de um vetor de consulta para todos os outros vetores no banco de dados vetorial.
Por razões óbvias, a busca ingênua não funciona ao tentar escalar nosso banco de dados vetorial para dezenas ou centenas de milhões de vetores. Mas quando o número total de elementos no banco de dados é pequeno, essa pode, na verdade, ser a maneira mais eficiente de realizar busca vetorial, já que uma estrutura de dados separada para o índice não é necessária, enquanto inserções e exclusões podem ser implementadas com bastante facilidade.
Devido à falta de complexidade espacial, bem como à sobrecarga constante de espaço associada à busca ingênua, esse método muitas vezes pode superar o particionamento espacial mesmo ao consultar um número moderado de vetores.
Particionamento espacial
O particionamento espacial não é um único algoritmo, mas sim uma família de algoritmos que usam todos o mesmo conceito.
Árvores K-dimensionais (kd-trees) talvez sejam as mais conhecidas dessa família e funcionam bissectando continuamente o espaço de busca (dividindo os vetores em buckets “esquerdo” e “direito”) de maneira semelhante às árvores de busca binária.
Índice de arquivo invertido (IVF) também é uma forma de particionamento espacial e funciona atribuindo cada vetor ao seu centróide mais próximo - as buscas são então conduzidas primeiro determinando o centróide mais próximo do vetor de consulta e realizando a busca ao redor dele, reduzindo significativamente o número total de vetores que precisam ser pesquisados. IVF é uma estratégia de indexação bastante popular e é comumente combinada com outros algoritmos de indexação para melhorar o desempenho.
Quantização
Quantização é uma técnica para reduzir o tamanho total do banco de dados reduzindo a precisão dos vetores.
Quantização escalar (SQ), por exemplo, funciona multiplicando vetores de ponto flutuante de alta precisão por um valor escalar e, em seguida, convertendo os elementos do vetor resultante para seus inteiros mais próximos. Isso não apenas reduz o tamanho efetivo de todo o banco de dados (por exemplo, por um fator de oito na conversão de float64_t para int8_t), mas também tem o efeito colateral positivo de acelerar os cálculos de distância vetorial entre vetores.
Quantização de produto (PQ) é outra técnica de quantização que funciona de forma semelhante à compressão por dicionário. Em PQ, todos os vetores são divididos em subvetores de tamanhos iguais, e cada subvetor é então substituído por um centróide.
Hierarchical Navigable Small Worlds (HNSW)
Hierarchical Navigable Small Worlds é um algoritmo de indexação e recuperação baseado em grafos.
Isso funciona de maneira diferente da quantização de produto: em vez de melhorar a pesquisabilidade do banco de dados reduzindo seu tamanho efetivo, HNSW cria um grafo multicamadas a partir dos dados originais. As camadas superiores contêm apenas "conexões longas", enquanto as camadas inferiores contêm apenas "conexões curtas" entre vetores no banco de dados (veja a próxima seção para uma visão geral das métricas de distância vetorial). Conexões individuais do grafo são criadas à la skip lists.
Com essa arquitetura em vigor, a busca se torna bastante direta – percorremos avidamente o grafo mais superior (aquele com as conexões entre vetores mais longas) em busca do vetor mais próximo do nosso vetor de consulta. Então fazemos o mesmo para a segunda camada, usando o resultado da busca da primeira camada como ponto de partida. Isso continua até concluirmos a busca na camada mais inferior, cujo resultado se torna o vizinho mais próximo do vetor de consulta.
HNSW, visualizado. Fonte da imagem: https://arxiv.org/abs/1603.09320
Vizinhos Mais Próximos Aproximados, Isso Aí
Este é provavelmente meu algoritmo ANN favorito, simplesmente por causa de seu nome brincalhão e pouco intuitivo. Approximate Nearest Neighbors Oh Yeah (ANNOY) é um algoritmo baseado em árvores popularizado pelo Spotify (ele é usado no sistema de recomendação de músicas deles). Apesar do nome estranho, o conceito subjacente por trás do ANNOY é, na verdade, bastante simples – árvores binárias.
O ANNOY funciona primeiro selecionando aleatoriamente dois vetores no banco de dados e bisseccionando o espaço de busca ao longo do hiperplano que separa esses dois vetores. Isso é feito iterativamente até que haja menos do que algum parâmetro predefinido NUM_MAX_ELEMS por nó. Como o índice resultante é essencialmente uma árvore binária, isso nos permite fazer nossa busca com complexidade O(log n).
ANNOY, visualizado. Fonte da imagem: https://github.com/spotify/annoy
Métricas de similaridade comumente usadas
Os melhores bancos de dados vetoriais são inúteis sem métricas de similaridade – métodos para calcular a distância entre dois vetores. Existem inúmeras métricas, então discutiremos aqui apenas o subconjunto mais comumente usado.
Métricas de similaridade de vetores de ponto flutuante
As métricas de similaridade de vetores de ponto flutuante mais comuns são, sem nenhuma ordem específica, distância L1, distância L2 e similaridade de cosseno. Os dois primeiros valores são métricas de distância (valores menores implicam maior similaridade, enquanto valores maiores implicam menor similaridade), enquanto a similaridade de cosseno é uma métrica de similaridade (valores maiores implicam maior similaridade).
A distância L1 também é comumente chamada de distância de Manhattan, nome apropriado devido ao fato de que ir do ponto A ao ponto B em Manhattan exige mover-se ao longo de uma de duas direções perpendiculares. A segunda equação, distância L2, é simplesmente a distância entre dois vetores no espaço euclidiano. A terceira e última equação é a distância de cosseno, equivalente ao cosseno do ângulo entre dois vetores. Observe que a equação para similaridade de cosseno acaba sendo o produto escalar entre versões normalizadas dos vetores de entrada a e b.
Com um pouco de matemática, também podemos mostrar que a distância L2 e a similaridade de cosseno são efetivamente equivalentes quando se trata de classificação por similaridade para vetores de norma unitária:
Lembre-se de que vetores de norma unitária têm magnitude 1:
Com isso, obtemos:
Como temos vetores de norma unitária, a distância de cosseno acaba sendo o produto escalar entre a e b (o denominador na equação 3 acima acaba sendo 1):
Essencialmente, para vetores de norma unitária, a distância L2 e a similaridade de cosseno são funcionalmente equivalentes! Lembre-se sempre de normalizar seus embeddings.
Métricas de similaridade de vetores binários
Vetores binários, como o nome sugere, não têm métricas baseadas em aritmética como os vetores de ponto flutuante. Em vez disso, métricas de similaridade para vetores binários dependem de matemática de conjuntos, manipulação de bits ou uma combinação de ambas (tudo bem, eu também odeio matemática discreta). Aqui estão as fórmulas para duas métricas de similaridade de vetores binários comumente usadas:
A primeira equação é chamada distância de Tanimoto/Jaccard, e é essencialmente uma medida da quantidade de sobreposição entre dois vetores binários. A segunda equação é a distância de Hamming, e é uma contagem do número de elementos vetoriais em a e b que diferem entre si.
Você muito provavelmente pode ignorar com segurança essas métricas de similaridade, já que a maioria das aplicações usa similaridade de cosseno sobre embeddings de ponto flutuante.
Concluindo
Neste tutorial, analisamos a busca vetorial, junto com alguns algoritmos comuns de busca vetorial e métricas de distância. Aqui estão alguns pontos principais:
Vetores de embedding são representações poderosas, tanto em termos de distância entre os vetores quanto em termos de aritmética vetorial. Ao aplicar uma quantidade generosa de álgebra vetorial aos embeddings, podemos realizar análise semântica escalável usando apenas operadores matemáticos básicos.
A busca vetorial semântica supera a limitação da busca por palavras-chave ao permitir que você pesquise com base no significado da sua consulta. Ela possibilita a recuperação rápida de respostas por meio da busca vetorial.
Há uma ampla variedade de algoritmos de busca aproximada de vizinhos mais próximos e/ou tipos de índice para escolher. O mais comumente usado hoje é o HNSW, mas um algoritmo de indexação diferente pode funcionar melhor para a sua aplicação específica, dependendo do número total de embeddings vetoriais que você tem, além do comprimento de cada vetor individual.
As duas principais métricas de distância usadas hoje são a distância L2/Euclidiana e a distância de cosseno. Essas duas métricas, quando usadas em embeddings normalizados, são funcionalmente equivalentes.
Obrigado por nos acompanhar neste tutorial! A busca vetorial é uma parte central do Milvus, e continuará sendo. Em tutoriais futuros, faremos alguns mergulhos mais profundos nos algoritmos ANNS mais comumente usados - HNSW e ScaNN.
Dê outra olhada nos cursos Vector Database 101
- Introdução a Dados Não Estruturados
- O que é um Banco de Dados Vetorial?
- Comparando Bancos de Dados Vetoriais, Bibliotecas de Busca Vetorial e Plugins de Busca Vetorial
- Introdução ao Milvus
- Início Rápido do Milvus
- Introdução à Busca por Similaridade Vetorial
- Noções Básicas de Índices Vetoriais e o Índice de Arquivo Invertido
- Quantização Escalar e Quantização de Produto
- Hierarchical Navigable Small Worlds (HNSW)
- Approximate Nearest Neighbors Oh Yeah (ANNOY)
- Escolhendo o Índice Vetorial Certo para o Seu Projeto
- DiskANN e o Algoritmo Vamana
Continue lendo
Notion's Vector Search Is Excellent. Their Next Problem Is Harder.
Notion solved vector search scaling in two years. The next bottleneck — offline context engineering, unified data, and the real-time/offline gap — is harder.
Announcing the General Availability of Single Sign-On (SSO) on Zilliz Cloud
SSO is GA on Zilliz Cloud, delivering the enterprise-grade identity management capabilities your teams need to deploy vectorDB with confidence.
Legal Document Analysis: Harnessing Zilliz Cloud's Semantic Search and RAG for Legal Insights
Enhance legal document analysis with Zilliz Cloud’s Semantic Search and RAG. Improve accuracy, efficiency, and scalability for contracts, case law, and compliance.