Busca Aproximada de Vizinhos Mais Próximos em Sistemas de Recomendação
Introdução
Em fevereiro de 2024, ouvimos Yury Malkov no SF Unstructured Data Meetup falar sobre Approximate Nearest Neighbor (ANN) e seu papel fundamental em sistemas de recomendação. A busca ANN já está integrada às stacks de produção das ferramentas mais populares do mundo. Yury nos ajuda a entender os principais conceitos e o contexto que impulsionaram a adoção de ANN em sistemas de recomendação em larga escala.
Link para o replay no YouTube da palestra de Yury Malkov: Assista à palestra no YouTube
Por que você deveria se importar com ANN?
Yuri Malkov é literalmente um gênio. Se você não acredita em mim, confira a listagem dele no Google Scholar https://scholar.google.com/citations?user=KvAyakQAAAAJ&hl=en. Físico, pesquisador de lasers e inventor do HNSW - um algoritmo de indexação baseado em grafos agora integrado de fábrica a todos os principais bancos de dados vetoriais. Ele agora trabalha para a OpenAI como Research Scientist. Diga-me se isso não parece uma biografia plausível do Tony Stark em 2024.
Com isso, vamos nos aprofundar na palestra de Yuri sobre “Approximate Nearest Neighbor Search in Recommender Systems.”
O que é busca ANN?
Vamos ser breves, pois já cobrimos os fundamentos da busca ANN resumidamente e em detalhes.
Buscas por vizinhos mais próximos são um conjunto de técnicas estatísticas que podemos usar para fazer buscas por similaridade em aplicações de machine learning ou ciência de dados. Diferentemente de seu primo especial com sabor K, o KNN, que compara cada ponto de dados em um sistema com todos os outros ao concluir sua busca, os algoritmos de busca ANN usam várias técnicas de indexação para retornar vizinhos mais próximos aproximados. As buscas ANN se tornaram centrais para muitas aplicações e tecnologias voltadas para clientes hoje. De mecanismos de busca (como o Google, não busca vetorial) a sites de mídia social, ANN e sistemas de recomendação já estão integrados em toda a stack, em produção.
ANN não era a única solução para sistemas de recomendação. Então, como chegamos aqui? Vamos passar por soluções ANN maduras no mercado hoje, o que torna os sistemas de recomendação um problema difícil para algoritmos de vizinhos mais próximos, como os desenvolvedores estruturaram sistemas de recomendação e como os pesquisadores estão usando ANN para reescrever a stack de sistemas de recomendação. Yuri observa em sua palestra que existem muitas soluções ANN maduras. Muitos desses tópicos são abordados em profundidade em nosso Guia Visual para Escolher um Índice Vetorial, mas eu montei uma tabela das ferramentas listadas na apresentação de Yuri.
Tabela de índices ANN mencionados
| Índice ANN | Classificação | Cenário |
|---|---|---|
| LSH | Índice baseado em grafo | - Grandes conjuntos de dados multidimensionais altamente complexos - Usa distância euclidiana para agrupar pontos de dados em buckets - Retorna apenas os resultados mais próximos |
| HNSW | Índice baseado em grafo | - Consulta de altíssima velocidade - Requer uma taxa de recall tão alta quanto possível - Grandes recursos de memória |
| SCANN | Índice baseado em quantização | - Consulta de altíssima velocidade - Requer uma taxa de recall tão alta quanto possível - Grandes recursos de memória |
| IVF_PQ | Índice baseado em quantização (invertido) | - Índice invertido - Consulta de altíssima velocidade - Recursos de memória limitados - Aceita comprometimento substancial na taxa de recall |
| IVF_HSNW | Índice baseado em grafo (invertido) | - Índice invertido - Baseado em HSNW - Requer uma taxa de recall tão alta quanto possível - Grandes recursos de memória |
| DiskANN | Múltiplos índices de vizinho mais próximo | - Modificações de ANN e toolkit para buscas ANN |
| ANNOY | Múltiplos índices de vizinho mais próximo | - Implementações de LSH ou KDtrees - Busca eficiente em memória e rápida em espaços de alta dimensionalidade |
| Muitos outros | - | - FAISS, cuHNSW, ngt, song |
Sobre benchmarks ANN
Yuri passa pelos benchmarks ANN na velocidade da luz - apontando para ANNBenchmarks com a ressalva de que fazer benchmarking de algoritmos ANN inversos pode ficar complicado. Vamos desacelerar isso:
O que é ANN-Benchmarks?
ANN-Benchmarks é um ambiente de benchmarking que avalia vários algoritmos de busca aproximada de vizinho mais próximo, fornecendo resultados divididos por medida de distância e conjunto de dados em seu site. Os benchmarks exibem métricas de desempenho como taxa de recall e consultas por segundo, e os usuários podem contribuir enviando seu código via pull requests no GitHub .
Embora você possa encontrar dados de benchmarking de algoritmos ANN em muitos lugares (github, ANN-Benchmarks, até mesmo documentação de produto), você sempre verá gráficos plotando QPS - consultas por segundo. Mais QPS, melhor! Vrum vrum!
Uma observação sobre a escolha de algoritmos ANN (e outros algoritmos de busca vetorial)
Se olhar para benchmarks de algoritmos te dá sangramento nasal, você não está sozinho. É por isso que a equipe do Milvus criou o Knowhere. Knowhere é o mecanismo principal open-source de execução vetorial do Milvus, que incorpora várias bibliotecas de busca por similaridade vetorial, incluindo Faiss, Hnswlib e Annoy. O Knowhere controla em qual hardware (CPU ou GPU) executar a construção de índices e as solicitações de busca. É assim que o Knowhere recebe seu nome - sabendo onde executar as operações. Mais tipos de hardware, incluindo DPU e TPU, serão suportados em versões futuras.
Com base no Knowhere - a equipe do Zilliz Cloud lançou o Cardinal, que é o mecanismo principal de busca vetorial da Zilliz. Esse mecanismo de busca já demonstrou um aumento de desempenho de três vezes em comparação com a versão anterior, oferecendo uma performance de busca (QPS) que chega a dez vezes a do Milvus. A busca ANN há muito tempo está integrada a sistemas de recomendação. Para descobrir por que os algoritmos de busca ANN se tornaram tão populares em sistemas de recomendação em produção, precisamos dar um passo atrás e observar as motivações, a arquitetura e as soluções inovadoras que a ANN superou.
Aplicações de sistemas de recomendação em escala: motivações e desafios
Objetivo: O objetivo básico de todos os sistemas de recomendação é retornar um item (vídeo, produto, documento, mensagem) para uma consulta (usuário, aplicação, contexto). Lembre-se dessa relação item-consulta - ela é importante para entender os algoritmos de busca (recomendação).
Mercado: As tecnologias de recomendação apresentaram e representam um grande mercado, dada sua capacidade de gerar comportamento do consumidor.
Desafios típicos em escala:
Generabilidade:
- Tradicionalmente, os sistemas de recomendação tiveram baixa generabilidade - em grande parte devido à dependência de dados, modelos e infraestrutura internos.
Corpus enormes:
Grandes conjuntos de dados (milhões a trilhões de itens, consultas) geram grandes custos de inferência.
Eficiência e contenção dos custos de inferência são muito importantes.
O processamento pesado de vídeos e imagens exigiu engenheiros dedicados para manter a infraestrutura.
Soluções, maturidade:
Soluções/infraestrutura internas geralmente desenvolvidas internamente (ex.: Google, Meta, X,)
Normalmente, um funil de recomendação em múltiplas etapas (veja abaixo) para economizar custos de inferência
Ferramentas prontas para uso vêm ganhando popularidade e tração com o surgimento de bancos de dados vetoriais e LLMs.
Funil típico em múltiplas etapas
Yuri explora um diagrama de um sistema de recomendação típico em produção. No exemplo abaixo para recomendação de vídeos, uma aplicação recebe itens e uma consulta e deve retornar um pin de recomendação de vídeo. Essas aplicações são funis em múltiplas etapas, nos quais candidatos a itens são gerados e passam por modelos de ranqueamento sucessivos para refinar os resultados da busca.
Etapa 1: Geração de candidatos - ANN + Modelo leve
Nesta etapa inicial, o sistema usa vizinhos mais próximos aproximados para vasculhar rapidamente a vasta base de dados de vídeos e identificar uma lista preliminar de vídeos candidatos que sejam relevantes para a consulta do usuário. Esse processo foi projetado para ser rápido e eficiente, lidando com potencialmente milhões de itens ao focar naqueles com maior probabilidade de corresponder às características da consulta. O 'Modelo leve' usado nesta etapa é normalmente um modelo mais simples, menos intensivo computacionalmente, que ajuda a reduzir o conjunto de candidatos àqueles que melhor se alinham aos interesses ou termos de busca do usuário.
Etapa 2: Ranqueamento leve - Força bruta + Modelo intermediário
Depois que um conjunto de candidatos é gerado, a próxima etapa envolve uma análise mais detalhada desses candidatos. Isso é feito usando uma abordagem de 'Força bruta', na qual cada candidato é avaliado de forma mais aprofundada usando um 'Modelo intermediário', que é mais complexo do que o Modelo leve usado na primeira etapa. Esse modelo leva em conta recursos adicionais, como métricas de engajamento do usuário, relevância contextual e qualidade do conteúdo, para ranquear os candidatos de modo que os vídeos mais relevantes sejam empurrados para o topo da lista de recomendações. Esta etapa atinge um equilíbrio entre desempenho e precisão, refinando a seleção ao focar mais em qualidade e relevância.
Etapa 3: Ranqueamento completo - Força bruta + Modelo pesado
A etapa final no processo de recomendação é a fase de Ranking Completo, que emprega um 'Modelo Pesado'—o mais sofisticado e intensivo em recursos dos modelos usados. Este modelo incorpora uma ampla variedade de sinais e pontos de dados, incluindo análise mais profunda do perfil do usuário, preferências de longo prazo, análise detalhada de conteúdo e, possivelmente, dados em tempo real, como tendências atuais de visualização. O método de Força Bruta aplicado aqui garante que cada vídeo seja pontuado e classificado de forma abrangente, assegurando que as recomendações finais sejam altamente personalizadas e relevantes. Esta etapa garante recomendações da mais alta qualidade, mas requer mais poder de processamento e tempo, tornando-a adequada para o refinamento final da lista de recomendações.
Por que o HSNW vacila em sistemas de recomendação tradicionais e soluções (imperfeitas) Sabendo que sistemas de recomendação de produção em larga escala são limitados por grandes conjuntos de dados e pelos custos associados, Yuri afirma que itens e consultas se situam em dois - planos incompatíveis. Quando consultas e itens residem em espaços diferentes e incompatíveis, algoritmos tradicionais de busca por similaridade como Hierarchical Navigable Small World (HNSW) enfrentam desafios porque esses algoritmos dependem de uma relação mensurável ou função de distância diretamente entre a consulta e os itens. Sem uma métrica clara para avaliar a proximidade, o HNSW não consegue desempenhar efetivamente sua função, que é navegar por um grafo de itens para encontrar as correspondências mais próximas de uma consulta.****
Uma revisão de soluções inovadoras para a incompatibilidade item-consulta
Distância L2 em vetores de dados
Como funciona: Usa a distância L2 entre entradas de dados vetorizadas para criar uma estrutura de grafo substituta para sistemas de recomendação.
Prós: Simplifica o processo usando um cálculo de distância direto, oferecendo uma vantagem de velocidade durante as fases de geração de candidatos e reclassificação.
Contras: Pode não capturar relações complexas ou nuances entre itens e consultas de forma tão eficaz quanto modelos mais sofisticados, potencialmente levando a recomendações menos personalizadas.
Ranking em grafo bipartido
Como funciona: Projeta itens e consultas em um grafo bipartido onde os itens são vinculados aos seus usuários ou consultas mais próximos, permitindo que arestas sejam geradas com base nessas relações.
Prós: Eficaz na estruturação de dados relacionais entre usuários e itens, embora comparações diretas com outros métodos sejam limitadas.
Contras: A construção e manutenção do grafo bipartido podem ser intensivas em recursos, e a eficácia pode variar muito dependendo da densidade e qualidade das conexões do grafo.
Fonte da imagem: https://www.vldb.org/pvldb/vol15/p794-tan.pdf
Reclassificação por grafo (focada em texto)
Como funciona: Utiliza um grafo criado a partir de vetores para geração de candidatos, aplicando diretamente um ranqueador pesado ao grafo para recuperação de texto, o que melhora a qualidade dos resultados.
Prós: Elimina o funil tradicional de múltiplas etapas, permitindo a correção de erros cometidos em etapas anteriores de filtragem de candidatos.
Contras: Principalmente eficaz para recuperação baseada em texto; pode não ser tão eficaz em outros contextos em que características não textuais predominam, limitando sua aplicabilidade.
Fonte da imagem: https://arxiv.org/pdf/2208.08942
Busca em grafo em cascata
Como funciona: Começa com uma função de distância leve para a busca inicial e faz uma transição perfeita para uma função de distância mais pesada durante o processo de busca.
Prós: Oferece flexibilidade ao adaptar a função de distância em tempo real, otimizando tanto a velocidade quanto a precisão ao longo do processo de busca.
Contras: A complexidade de gerenciar e otimizar funções de distância duplas pode aumentar a sobrecarga computacional e a complexidade do sistema, potencialmente impactando a escalabilidade.
Fonte da imagem: https://arxiv.org/pdf/2202.10226
Por que a busca ANN é tão popular?
Juntando tudo isso – Yuri traçou um bom panorama de por que os algoritmos ANN tiveram uma implementação tão ampla, especialmente em aplicações (como sistemas de recomendação em larga escala) que trabalham com conjuntos de dados de alta dimensionalidade.
Correspondência boa o suficiente (ou melhor) - Se você não precisa de uma correspondência perfeita, uma variante de ANN quase sempre é uma solução melhor do que outros algoritmos NN.
Flexibilidade - com uma ampla variedade de implementações, um desenvolvedor pode escolher o custo
Maturidade - ANN foram implementados em todas as principais linguagens de programação, e existem vários frameworks populares para selecionar e executar buscas ANN.
Recursos adicionais
https://zilliz.com/learn/Local-Sensitivity-Hashing-A-Comprehensive-Guide
https://zilliz.com/learn/how-to-pick-a-vector-index-in-milvus-visual-guide
Link para a reprise no YouTube da palestra de Yury Malkov: Assista à palestra no YouTube
Continue lendo
Milvus 2.6.x Now Generally Available on Zilliz Cloud, Making Vector Search Faster, Smarter, and More Cost-Efficient for Production AI
Milvus 2.6.x is now GA on Zilliz Cloud, delivering faster vector search, smarter hybrid queries, and lower costs for production RAG and AI applications.
Expanding Our Global Reach: Zilliz Cloud Launches in Azure Central India
Zilliz Cloud expands to Azure Central India. This new region helps customers meet compliance, reduce latency, and optimize cloud costs when building AI applications.
Similarity Metrics for Vector Search
Exploring five similarity metrics for vector search: L2 or Euclidean distance, cosine distance, inner product, and hamming distance.