Introdução ao HNSWlib

A pesquisa semântica permite que as máquinas compreendam a linguagem e produzam melhores resultados de pesquisa, o que é essencial na IA e na análise de dados. Uma vez que a linguagem é representada como embeddings, a pesquisa pode ser efectuada utilizando métodos exactos ou aproximados. A pesquisa do vizinho mais próximo aproximado(ANN) é um método utilizado para encontrar rapidamente pontos num conjunto de dados que estão mais próximos de um determinado ponto de consulta, ao contrário da pesquisa exacta do vizinho mais próximo, que pode ser computacionalmente dispendiosa para dados de elevada dimensão. A ANN permite uma recuperação mais rápida, fornecendo resultados que são aproximadamente próximos dos vizinhos mais próximos.

Um dos algoritmos para a pesquisa ANN (Approximate Nearest Neighbor) é o HNSW (Hierarchical Navigable Small Worlds), implementado na HNSWlib, que será o foco da discussão de hoje. Neste blogue, iremos:

• Entender o algoritmo HNSW.

• Explorar o HNSWlib e seus principais recursos.

• Configurar o HNSWlib, abrangendo a construção do índice e a implementação da pesquisa.

• Compará-lo com o Milvus.

Entendendo o HNSW

Hierarchical Navigable Small Worlds (HNSW) é uma estrutura de dados baseada em gráficos que permite pesquisas de similaridade eficientes, particularmente em espaços de alta dimensão, construindo um gráfico de várias camadas de redes "small world". Introduzido em 2016, o HNSW aborda os problemas de escalabilidade associados aos métodos de pesquisa tradicionais, como as pesquisas de força bruta e baseadas em árvores. É ideal para aplicações que envolvem grandes conjuntos de dados, como sistemas de recomendação, reconhecimento de imagem e geração aumentada de recuperação (RAG).

Porque é que o HNSW é importante

O HNSW melhora significativamente o desempenho da pesquisa do vizinho mais próximo em espaços de alta dimensão. A combinação da estrutura hierárquica com a navegabilidade de mundo pequeno evita a ineficiência computacional dos métodos mais antigos, permitindo um bom desempenho mesmo com conjuntos de dados maciços e complexos. Para compreender melhor, vamos ver como funciona atualmente.

Como funciona o HNSW

1. Camadas hierárquicas: O HNSW organiza os dados numa hierarquia de camadas, em que cada camada contém nós ligados por arestas. As camadas superiores são mais esparsas, permitindo "saltos" amplos no gráfico, tal como fazer zoom num mapa para ver apenas as principais auto-estradas entre cidades. As camadas inferiores aumentam em densidade, fornecendo detalhes mais finos e mais ligações entre vizinhos mais próximos.

2. Conceito de pequenos mundos navegáveis: Cada camada no HNSW baseia-se no conceito de uma rede de "mundo pequeno", onde os nós (pontos de dados) estão apenas a alguns "saltos" de distância uns dos outros. O algoritmo de pesquisa começa na camada mais alta e mais esparsa e trabalha para baixo, movendo-se para camadas progressivamente mais densas para refinar a pesquisa. Esta abordagem é como passar de uma visão global para detalhes ao nível da vizinhança, estreitando gradualmente a área de pesquisa.

Fig 1: Um exemplo de um gráfico de mundo pequeno navegável

3. Estrutura do tipo Skip List: O aspeto hierárquico do HNSW assemelha-se a uma skip list, uma estrutura de dados probabilística em que as camadas superiores têm menos nós, permitindo pesquisas iniciais mais rápidas.

Fig 2: Um exemplo de estrutura de lista de saltos

Para procurar 96 na lista de saltos dada, começamos no nível superior, à esquerda, no nó de cabeçalho. Movendo-nos para a direita, encontramos 31, menos de 96, pelo que continuamos para o nó seguinte. Agora, precisamos de descer um nível, onde vemos novamente 31; como continua a ser inferior a 96, descemos mais um nível. Encontrando 31 mais uma vez, movemo-nos para a direita e chegamos a 96, o nosso valor alvo. Assim, localizamos 96 sem precisar de descer aos níveis mais baixos da lista de saltos.

4. Eficiência da Pesquisa: O algoritmo HNSW parte de um nó de entrada na camada mais alta, progredindo para vizinhos mais próximos a cada passo. Desce através das camadas, utilizando cada uma delas para uma exploração de grão grosso a fino, até atingir a camada mais baixa, onde provavelmente se encontram os nós mais semelhantes. Esta navegação em camadas reduz o número de nós e arestas que precisam de ser explorados, tornando a pesquisa rápida e precisa.

5. Inserção e manutenção: Ao adicionar um novo nó, o algoritmo determina a sua camada de entrada com base na probabilidade e liga-o a nós próximos utilizando uma heurística de seleção de vizinhos. A heurística tem como objetivo otimizar a conetividade, criando ligações que melhoram a navegabilidade, ao mesmo tempo que equilibram a densidade do grafo. Esta abordagem mantém a estrutura robusta e adaptável a novos pontos de dados.

Embora tenhamos uma compreensão básica do algoritmo HNSW, implementá-lo a partir do zero pode ser complicado. Felizmente, a comunidade desenvolveu bibliotecas como a HNSWlib para simplificar o uso, tornando-o acessível sem que seja necessário coçar a cabeça. Então, vamos dar uma olhada mais de perto no HNSWlib.

Visão geral do HNSWlib

HNSWlib, uma biblioteca popular que implementa HNSW, é altamente eficiente e escalável, com bom desempenho mesmo com milhões de pontos. Atinge uma complexidade de tempo sublinear, permitindo saltos rápidos entre camadas de gráficos e optimizando a pesquisa de dados densos e de elevada dimensão. Aqui estão as principais caraterísticas do HNSWlib:

• Estrutura baseada em gráficos: Um gráfico de várias camadas representa os pontos de dados, permitindo pesquisas rápidas e mais próximas.

• Eficiência em alta dimensão: Otimizado para dados de alta dimensão, fornecendo pesquisas aproximadas rápidas e precisas.

• Tempo de pesquisa sublinear: Alcança complexidade sublinear ao pular camadas, melhorando significativamente a velocidade.

• Atualizações dinâmicas: Suporta a inserção e exclusão de nós em tempo real sem exigir uma reconstrução completa do gráfico.

• Eficiência de memória: Uso eficiente da memória, adequado para grandes conjuntos de dados.

• Escalabilidade: Escala bem até milhões de pontos de dados, tornando-o ideal para aplicações de média escala, como sistemas de recomendação.

Nota: O HNSWlib é excelente para criar protótipos simples para aplicações de pesquisa vetorial. No entanto, devido a limitações de escalabilidade, pode haver melhores escolhas, como bases de dados vectoriais criadas especificamente para cenários mais complexos que envolvam centenas de milhões ou mesmo milhares de milhões de pontos de dados. Vamos ver isso em ação.

Primeiros passos com a HNSWlib: Um guia passo-a-passo

Esta seção demonstrará o uso da HNSWlib como uma biblioteca de pesquisa vetorial, criando um índice HNSW, inserindo dados e realizando pesquisas. Vamos começar com a instalação:

Configuração e importações

Para começar a usar a HNSWlib em Python, primeiro instale-a usando pip:

pip install hnswlib

Em seguida, importe as bibliotecas necessárias:

import hnswlib 
import numpy as np

Preparando os dados

Neste exemplo, usaremos NumPypara gerar um conjunto de dados aleatório com 10.000 elementos, cada um com uma dimensão de 256.

dim = 256  # Dimensionality of your vectors
num_elements = 10000  # Number of elements to insert

Vamos criar os dados:

data = np.random.rand(num_elements, dim).astype(np.float32)  # Example data

Agora que nossos dados estão prontos, vamos criar um índice.

Criar um índice

Ao construir um índice, precisamos de definir a dimensionalidade dos vectores e o tipo de espaço. Vamos criar um índice:

p = hnswlib.Index(space='l2', dim=dim)

• space='l2': Este parâmetro define a métrica de distância utilizada para a similaridade. Se o definir para 'l2' significa que utiliza a distância euclidiana (norma L2). Se, em vez disso, o definir para 'ip', utilizará o produto interno, o que é útil para tarefas como a semelhança de cosseno.

• dim=dim: Este parâmetro especifica a dimensionalidade dos pontos de dados com que vai trabalhar. Ele deve corresponder à dimensão dos dados que planeja adicionar ao índice.

Veja como inicializar um índice:

p.init_index(max_elements=num_elements, ef_construction=200, M=16)

• max_elements=num_elements: Isto define o número máximo de elementos que podem ser adicionados ao índice. Num_elements é a capacidade máxima, por isso definimos isto para 10.000, uma vez que estamos a trabalhar com 10.000 pontos de dados.

• ef_construction=200: Este parâmetro controla o compromisso precisão vs. velocidade de construção durante a criação do índice. Um valor mais elevado melhora a recuperação (precisão), mas aumenta a utilização da memória e o tempo de construção. Os valores comuns variam de 100 a 200.

• M=16: Este parâmetro determina o número de ligações bidireccionais criadas para cada ponto de dados, influenciando a precisão e a velocidade de pesquisa. Os valores típicos estão entre 12 e 48; 16 é frequentemente um bom equilíbrio para precisão e velocidade moderadas.

p.set_ef(50)  # This parameter controls the speed/accuracy trade-off

• ef: O parâmetro ef, abreviatura de "fator de exploração", determina quantos vizinhos são examinados durante uma pesquisa. Um valor ef mais elevado resulta em mais vizinhos a serem explorados, o que geralmente aumenta a exatidão (recuperação) da pesquisa, mas também a torna mais lenta. Por outro lado, um valor mais baixo de ef pode fazer uma pesquisa mais rápida, mas pode reduzir a precisão.

Nesse caso, definir ef como 50 significa que o algoritmo de pesquisa avaliará até 50 vizinhos ao encontrar os pontos de dados mais semelhantes.

Nota: ef_construction define o esforço de pesquisa de vizinhos durante a criação do índice, aumentando a precisão mas tornando a construção mais lenta. ef controla o esforço de pesquisa durante a consulta, equilibrando dinamicamente a velocidade e a recuperação para cada consulta.

Execução de pesquisas

Para executar uma pesquisa de vizinho mais próximo usando HNSWlib, primeiro criamos um vetor de consulta aleatório. Neste exemplo, a dimensionalidade do vetor corresponde aos dados indexados.

query_vector = np.random.rand(dim).astype(np.float32)  # Example query

labels, distances = p.knn_query(query_vector, k=5)  # k is the number of nearest neighbors

• query_vector: Esta linha gera um vetor aleatório com a mesma dimensionalidade que os dados indexados, assegurando a compatibilidade para a pesquisa do vizinho mais próximo.
• knn_query: O método procura os k vizinhos mais próximos do query_vector dentro do índice p. Devolve dois arrays: labels, que contém os índices dos vizinhos mais próximos, e distances, que indica as distâncias do vetor de consulta a cada um destes vizinhos. Aqui, k=5 especifica que queremos encontrar os cinco vizinhos mais próximos.

Aqui estão os resultados depois de imprimir as etiquetas e as distâncias:

print("Nearest neighbors' labels:", labels)
print("Distances:", distances)

> Nearest neighbors' labels: [[4498 1751 5647 4483 2471]]
> Distances: [[33.718    35.484592 35.627766 35.828312 35.91495 ]]

Aqui está, um guia simples para começar a usar a HNSWlib.

Como mencionado, o HNSWlib é um excelente motor de pesquisa vetorial para criar protótipos ou fazer experiências com conjuntos de dados de média dimensão. Se tiver requisitos de escalabilidade mais elevados ou necessitar de outras funcionalidades de nível empresarial, poderá ter de escolher uma base de dados vetorial criada para o efeito, como o Milvus de código aberto ou o seu serviço totalmente gerido no Zilliz Cloud. Assim, na secção seguinte, iremos comparar o HNSWlib com o Milvus.

HNSWlib vs. Bases de dados vectoriais criadas para fins específicos como o Milvus

Uma base de dados vetorial armazena dados como representações matemáticas, permitindo que os modelos de aprendizagem automática potenciem a pesquisa, as recomendações e a geração de texto, identificando dados através de métricas de semelhança para compreensão contextual.

As bibliotecas de índices vectoriais, como a HNSWlib, melhorama pesquisa e a recuperação de vectores, mas não possuem as funcionalidades de gestão de uma base de dados completa. Por outro lado, as bases de dados de vectores, como a Milvus, foram concebidas para lidar com incorporações de vectores em escala, proporcionando vantagens na gestão de dados, indexação e capacidades de consulta que as bibliotecas autónomas normalmente não possuem. Aqui estão alguns outros benefícios da utilização do Milvus:

• Pesquisa de similaridade vetorial de alta velocidade: O Milvus proporciona um desempenho de pesquisa ao nível dos milésimos de segundo em conjuntos de dados vectoriais à escala de mil milhões, ideal para aplicações como a recuperação de imagens, sistemas de recomendação, processamento de linguagem natural(PNL) e geração aumentada de recuperação(RAG).

• Escalabilidade e alta disponibilidade: Criado para lidar com grandes volumes de dados, o Milvus é escalonado horizontalmente e inclui mecanismos de replicação e failover para garantir a fiabilidade.

• Arquitetura distribuída: O Milvus utiliza uma arquitetura distribuída e escalável que separa o armazenamento e a computação em vários nós para maior flexibilidade e robustez.

• Pesquisa híbrida: Milvus suporta pesquisa multimodal, pesquisa híbrida esparsa e densa, e pesquisa híbrida densa e de texto completo, oferecendo uma funcionalidade de pesquisa versátil e flexível.

• Suporte flexível de dados: O Milvus suporta vários tipos de dados - vectores, escalares e dados estruturados - permitindo uma gestão e análise contínuas num único sistema.

• Comunidade e suporteactivos: Uma comunidade próspera fornece atualizações regulares, tutoriais e suporte, garantindo que o Milvus permaneça alinhado com as necessidades do usuário e os avanços no campo.

• Integração de IA: O Milvus foi integrado com várias estruturas e tecnologias populares de IA, facilitando aos programadores a criação de aplicações com as suas pilhas de tecnologia familiares.

Milvus também fornece um serviço totalmente gerenciado no Ziliz Cloud, que é descomplicado e 10x mais rápido do que Milvus.

Comparação: Milvus vs. HNSWlib

Caraterísticas	Milvus	HNSWlib
Escalabilidade	Lida com milhares de milhões de vectores com facilidade	Adequado para conjuntos de dados mais pequenos devido à utilização de RAM
Ideal para	Prototipagem, experimentação e aplicações de nível empresarial	Foca-se em protótipos e tarefas ANN leves
Indexação	Suporta mais de 10 algoritmos de indexação, incluindo HNSW, DiskANN, Quantização e Binário	Utiliza apenas um HNSW baseado em gráficos
Integração	Oferece APIs e serviços nativos da nuvem	Serve como uma biblioteca leve e autónoma
Desempenho	Optimiza para grandes dados, consultas distribuídas	Oferece alta velocidade, mas escalabilidade limitada

No geral, o Milvus é geralmente preferível para aplicações de grande escala e de nível de produção com necessidades de indexação complexas, enquanto o HNSWlib é ideal para prototipagem e casos de utilização mais simples.

Conclusão

A pesquisa semântica pode consumir muitos recursos, pelo que a estruturação interna de dados, como a efectuada pelo HNSW, é essencial para uma recuperação de dados mais rápida. Bibliotecas como a HNSWlib preocupam-se com a implementação, pelo que os programadores têm as receitas prontas para criar protótipos de capacidades vectoriais. Com apenas algumas linhas de código, podemos construir o nosso próprio índice e efetuar pesquisas.

A HNSWlib é uma óptima maneira de começar. No entanto, se quiser criar aplicações de IA complexas e prontas a produzir, as bases de dados vectoriais criadas para o efeito são a melhor opção. Por exemplo, a Milvus é uma base de dados vetorial de código aberto com muitas funcionalidades prontas para empresas, como pesquisa vetorial de alta velocidade, escalabilidade, disponibilidade e flexibilidade em termos de tipos de dados e linguagem de programação.

Ler mais

• O que é o Faiss (Facebook AI Similarity Search)?

• O que é HNSWlib? Uma biblioteca baseada em gráficos para pesquisa rápida de RNAs

• O que é ScaNN (Scalable Nearest Neighbors)?

• VectorDBBench: Uma ferramenta de benchmark VectorDB de código aberto

• Centro de recursos de IA generativa | Zilliz

• O que são bancos de dados vetoriais e como eles funcionam?

• O que é RAG?

• Modelos de IA de alto desempenho para seus aplicativos GenAI | Zilliz