Elasticsearch: entenda a teoria por trás do mecanismo de busca textual

Alguns meses atrás comecei a fazer uma especialização sobre Mineração de Dados no Coursera e o segundo curso dessa especialização não me parecia muito atrativo no começo mas acabou se mostrando muito útil no entendimento de uma das ferramentas de trabalho que usamos na Extreme Digital Solutions: o elasticsearch.

Boa parte do conteúdo teórico que irei apresentar são anotações pessoais que fiz do curso Recuperação de Texto e Motores de Busca.

O propósito desse artigo é ser algo mais expositivo e não pretende explicar de forma exaustiva cada assunto mas mostrar os caminho “das pedras” e referências para o caso de você desejar ir mais a fundo.

Ao final espero que você aprenda sobre:

• Qual é o problema que um mecanismo de busca textual precisa resolver.
• Como o eslasticsearch consegue resolver esse problema de forma rápida.
• As possíveis formas de se medir a relevância de um documento e qual é a forma padrão usada pelo elasticsearch?
• Como interpretar e ajustar a função de transformação BM25 usada pelo elasticsearch?

Formulação Formal de um Mecanismo de Busca Textual

Vamos começar dando “nomes aos bois” usando notação matemática.

Suponha que você tenha um coleção de documentos textuais. Todas as palavras, ou termos, que existem dentro desses documentos formam um “vocabulário” que chamaremos de V e as palavras desse vocabulário iremos chamar de w (w de word).

As queries que um usuário digita chamaremos de q e que é formada pelas palavras “q1”, “q2”, etc. Palavras essas que pertencem ao vocabulário V:

Um documento textual “d” de índice i é formado por palavras “d_i_j” (palavra j do documento i) que pertencem ao vocabulário V.

Vamos chamar nossa coleção de M documentos de C, ou seja, se tivemos 100 documentos então M=100 e C é o conjunto de todos esses 100 documentos:

Um mecanismo de busca textual deve ser capaz de encontrar um subconjunto de documentos relevantes com base na query textual escrita pelo usuário, ou seja, em “matematiquês” ficaria 𝑅(𝑞) ⊆ 𝐶 . A query 𝑞 é uma “dica” de quais documentos irão ser ranqueados pela função 𝑅(𝑞).

A tarefa de um mecanismo de busca textual é computar 𝑅′(𝑞)≈𝑅(𝑞), ou seja, estimar os parâmetros da suposta função ideal 𝑅(𝑞).

Temos dois principais tipos de estratégias para estimar 𝑅(𝑞):

• Seleção de documentos: 𝑅′(𝑞)={𝑑 ∈ 𝐶 | 𝑓(𝑑,𝑞)=1}, onde 𝑓(𝑑,𝑞)∈{0,1} é uma função indicadora do tipo classificador binário. O sistema tem que decidir se o documento será listado ou não ao usuário.
• Ranqueamento de documentos: 𝑅′(𝑞)={𝑑∈𝐶 | 𝑓(𝑑,𝑞) ≥ 𝜃} , onde 𝑓(𝑑,𝑞)∈𝑅 é uma função que mede relevância e 𝜃 é um limiar pré-definido. O sistema terá que listar os documentos e indicar seus graus de relevância.

Iremos tratar do segundo caso por ser o caminho usado pelo elasticsearch.

Essa função 𝑅(𝑞) pode seguir modelos probabilísticos, inferenciais ou modelos baseados em similaridade.

O elasticsearch segue o modelo baseado em similaridade. Algumas possíveis funções de similaridade: distância euclidiana, produto interno e cosseno de similaridade.

Mas para calcular essa função de similaridade precisamos primeiro construir um espaço vetorial que tornará possível a obtenção desse resultado.

Documentos como Vetores de um Espaço

Cada documento pode ser representado como vetor num  espaço vetorial que tem uma dimensão (eixo) para cada palavra do vocabulário V. Assim, cada dimensão desse vetor representa a quantidade de vezes que a palavra associada aquela dimensão aparece no documento em questão. O mesmo se aplicada para a representação vetorial da query q digitada pelo usuário.

Essa ideia de contar quantas vezes uma palavra aparece num documento é chamado de Frequência do Termo (TF). Há diferentes formas de medir o TF de uma palavra (veja mais sobre isso aqui) mas a que usaremos aqui é a abordagem de simplesmente obter a quantidade de vezes que a palavra em questão aparece no documento.

Como exemplo, vamos supor que nosso vocabulário seja:

E nosso documento seja formado pelas palavras:

E a query digitada pelo usuário seja:

Então teríamos a seguinte representação de 𝑑1 e 𝑞 no espaço vetorial:

Produto Interno como Medida de Similaridade e função de Ranking

Da geometria analítica sabemos que o produto interno entre dois vetores relaciona seus módulos, ou seja, seus comprimentos, com o ângulo entre eles. Dado 𝑞=(𝑥1,𝑥2,…,𝑥𝑛) e 𝑑=(𝑦1,𝑦2,…,𝑦𝑛):

Bora brincar um pouco com essa ideia de calcular similaridade entre documentos usando o produto interno:

Note que o resultado para o segundo e terceiro documento, que falam de coisas diferentes, receberam o mesmo score pois a palavra “sobre” teve tanto peso quanto a palavra “presidencial”.

Seria mais inteligente não “dar muita bola” para palavras que se repetem muito em todos os documentos.

Para que isso não aconteça, podemos ponderar os vetores dos documentos pela IDF (por favor veja tf–idf), desse modo, um termo só terá peso maior se ele for um termo não tão comum nos outros documentos.

Isso irá resolver problema dos scores iguais para o segundo e terceiro documento.

Como você pode notar, o terceiro e quinto documento falam da mesma coisa mas como o termo “campanha” aparece muitas vezes no quinto documento ele ainda recebe um score maior.

Se uma palavra “campanha” aparece uma vez isso já me dá uma pista sobre o que o documento está falando, se aparecer uma segunda, terceira e quarta vez isso irá fortalecer ainda mais minha confiança de que o documento em questão realmente está falando de alguma campanha, mas chega um ponto que se eu ver mais vezes a palavra “campanha” (50 vezes por exemplo) isso já não irá me agregar muita informação ao ponto de eu soltar um: “tá bom, já entendi que você está falando de campanha. Não preciso de tanto!”. O nome disso é Saturação do Termo.

Para resolver esse problema de saturação do termo resultante da função 𝑇𝐹(𝑤,𝑑), podemos aplicar algumas transformações. A sessão seguinte trata de uma dessas transformações que funcionam muito bem, o BM25 e que é a transformação padrão usada pelo elasticsearch.

Transformação BM25: controlando a influência da saturação dos termos

Se fôssemos apenas levar 𝑐(𝑤,𝑑) ⟼ 𝑇𝐹(𝑤,𝑑) (neste caso TF(w, d) é a frequência relativa da palavra no documento enquanto c(w, f) a frequência absoluta) teríamos uma transformação linear, mas seria interessante termos uma transformação que tivesse um teto, um valor máximo, que pudesse ser ajustado.

Dentre as várias transformações que tentam minimizar o efeito de palavras que se repetem muitas vezes no mesmo documento, o Best-Match-25 (BM25) é o que trás os melhores resultados e o mesmo possui um teto que é ajustado usando o parâmetro 𝑘. Segue a tal transformação:

Caso 𝑘=0 o teto será 1, ou seja, estou dizendo que não estou interessado nas repetições de um termo, apenas ver uma vez basta. Quanto maior for o valor do parâmetro 𝑘, mais próximo a transformação ficará próximo da transformação linear 𝑐(𝑤,𝑑) ⟼ 𝑇𝐹(𝑤,𝑑).

Com algumas manipulações algébricas é fácil perceber o porquê o teto dessa transformação é (𝑘+1) pois:

Seguem algumas funções de ranqueamento que se valem do BM25:

• Okapi BM25
• BM25L
• BM25+
• BM25-Adpt
• BM25T

Todos essas variações podem ser vistas em detalhes no artigo Improvements to BM25 and Language Models Examined.

A função de ranqueamento que iremos tratar aqui é a Okapi BM25 pois é essa que é usada pelo elasticsearch atualmente por ser considerada hoje em dia como “estado da arte”. Mas antes precisamos entender sobre normalização do comprimento de documentos.

Normalização: controlando a influência do comprimento do documento

O comprimento de um documento é sua quantidade total de palavras.

Por que o comprimento do documento pode ser um problema? Documentos muito longos tem maiores chances de dar match com qualquer query, devido a grande quantidade de palavras. O documento pode ser longo por dois motivos:

• Ele é verborrágico, ou seja, usa de muitas palavras para descrever um mesmo assunto.
• Ele possui de fato mais conteúdo, ou seja, informações diversas.

Queremos penalizar mais o primeiro caso e nem tanto o segundo caso. Esse processo de penalizar documentos verborrágicos é chamado de Normalização do Comprimento do Documento.

Usa-se como ponto de referência (pivô) o comprimento médio dos documentos da coleção C, ou seja, um documento só será normalizado caso ele seja maior ou menor que a média.

Como podem notar, o parâmetro b assume valores entre 0 e 1 (incluso) e quanto maior for b maior será a penalização aplicada a um documento maior que média.

Okapi BM25: a fusão

Combinando a transformação BM25, mais a normalização de cumprimento apresentada acima e o TF-IDF teremos a seguinte função de ranking chamada BM25 Okapi:

De acordo como o artigo Practical BM25 - Part 1: How Shards Affect Relevance Scoring in Elasticsearch publicado no blog do elasticsearch:

No Elasticsearch 5.0, mudamos para o Okapi BM25 como nosso algoritmo de similaridade padrão, que é usado para ranquear os resultados relacionados a uma consulta.

Indexação Inversa dos Documentos

Para que o mecanismo de busca seja rápido em ranquear os documentos precisamos pré-calcular o máximo que pudermos os valores de TF, DF e IDF e armazena-los numa estrutura de dados que dê suporte aos algoritmos de busca textual como o BM25 Okapi.

Esse processo de criar essa estrutura de dados é chamado de Indexação Inversa dos Documentos.

A imagem acima mostra um pouco de como seria esse objeto de index inverso. Primeiro de cria um dicionário que representa o vocabulário V, que indica a quantidade de documentos possuem a palavra/termo em questão e sua frequência absoluta, que por sua vez está associado a um outro objeto chamado “Postagem” que indica a quantidade de vezes que essa palavra aparece nos documentos na qual ela está associada.

O elasticsearch usa uma biblioteca do Java chamada Apache Lucene para cuidar de todo o processo de indexação inversa e busca de documentos.

O Apache LuceneTM é uma biblioteca de mecanismo de busca de texto de alto desempenho e com recursos completos, totalmente escrita em Java. É uma tecnologia adequada para praticamente qualquer aplicativo que exija pesquisa full-text.”  - Apache Lucene Core

O elastic precisa criar o tal objeto de indexação inversa associada aos campos de texto para adiantar o máximo possível os cálculos dos scores de relevância.

O elasticsearch armazena diferentes tipos de dados em estruturas de dados mais apropriadas ao dado em questão, os dados textuais serão guardados em estruturas próprias para indexação inversa.

Antes de realizar a indexação inversa de um campo textual, podemos aplicar analyzer (veja Anatomy of an analyzer) que ajudam a tratar o dado de texto, removendo stopwords, aplicando stemming, removendo acentuação, deixar todas as palavras em minúsculo, limpar o texto de tags html, etc. Tais analyzers são configurados no mapping (veja Mapping).

Personalizando os Parâmetros do BM25

Vamos fazer alguns testes usando diferentes valores para os parâmetros do BM25 Okapi.

No mapping a seguir iremos definir k1=0, queremos dizer com isso que não iremos se importar com a saturação do termo na hora de calcular o score de relevância. Mas aplicaremos uma penalização média (b=05) para documentos compridos.

Já neste outro index, definiremos b=0, queremos dizer com isso que não iremos se importar com o comprimento do documento na hora de calcular o score de relevância de um documento. Mas consideraremos como teto de saturação de palavras como 3 (lembre que o teto é k+1).

Já o próximo index deixaremos penalizaremos ao máximo (b=1) documentos maiores que média e nosso teto de saturação de palavras é 3.

Vamos então criar nossos index:

Vamos indexar alguns documentos em cada um dos index para fins de comparação.

Agora iremos fazer a seguinte query para o index jornal1, passando o parâmetro explain como true, desse modo você poderá obter a explicação de cada passo do cálculo de score de relevância que o elastic realizou associado aos documentos listados como relevantes, basta printar o conteúdo que está em res1[“hits”][“hits”][0][“_explanation”].

Notem que todos os 3 primeiros docs contendo “notícias” e “campanhas” foram listados mesmo que o 3º não tenha nada a ver com o assunto da query. Os 2 primeiros ainda possuem uma palavra a mais que é relevante, a palavra “presidencial” mas o maior documento ficou em 2º lugar na ordem de relevância, ou seja, foi penalizado medianamente (b=0.5) por ser maior que a média.

Agora vejamos a mesma query aplicada no index jornal2:

Dessa vez, por não penalizamos o comprimento do (b=0), o maior documento ficou em primeiro lugar, mesmo com a saturação do termo “campanha” pois o teto é aproximadamente 3 palavras (k1=2, lembre que o teto é igual a k1+1), portanto as primeiras 3 palavras “campanha” foram consideradas no cálculo de relevância enquanto as 2 restantes foram ignoradas.

Note que até o 3º documento mais relevante dessa vez foi o que fala de comidas orgânicas mas que tem a palavra “campanha” repetida 4 vezes, como aproximadamente 3 delas foram usadas para o cálculo de relevância.

Agora vejamos o index jornal3:

Temos agora um cenário próximo do index jornal1 para os 3 primeiros, mas com a diferença de que o 3º documento mais relevante não é mais sobre comidas orgânicas pois tais documentos foram “bombardeados” de penalizações devido ao comprimento, saturação do termos e palavras não relevantes como “comidas” e “orgânicas”.

Deixo como dever de casa você conferir o passo a passo do cálculo de score de relevância que está contido nos res1, res2 e res3 ( res1[“hits”][“hits”][<indice do resultado aqui>][“_explanation”] ). Também indexar os mesmos documentos num index com as configurações padrões para o BM25 e executar a mesma query que fizemos aqui para fins de comparação.

É isso pessoal, qualquer vacilo que eu tenha cometido nas explicações por favor deixe nos comentários. Abraço a todos!