Implementando artigos acadêmicos: Lições aprendidas com Elasticsearch e Lucene

Conecte-se perfeitamente com as principais plataformas de IA e machine learning. Inicie um teste gratuito na nuvem para explorar os recursos de IA generativa da Elastic ou experimente agora mesmo em sua máquina.

Este artigo compartilha estratégias para implementar artigos acadêmicos em um aplicativo de software. Este artigo utiliza exemplos do Elasticsearch e do Lucene com o objetivo de ajudar outros engenheiros a aprender com nossas experiências. Você pode ler essas estratégias e pensar: "Mas isso é só desenvolvimento de software!" E isso seria de fato verdade: como engenheiros, já possuímos as práticas e ferramentas adequadas, elas só precisam ser adaptadas a um novo desafio.

Histórico

Ao desenvolver o Elasticsearch, ocasionalmente nos deparamos com um problema importante para o qual não existe uma abordagem simples ou estabelecida para resolvê-lo. É natural perguntar: "Hum, existe algum artigo acadêmico que aborde esse assunto?" Outras vezes, o trabalho acadêmico é uma fonte de inspiração. Nos deparamos com um artigo que propõe um novo algoritmo ou estrutura de dados e pensamos: "Isso seria muito útil!" Aqui estão alguns exemplos de como o Elasticsearch e o Apache Lucene incorporam o trabalho acadêmico:

• HyperLogLog++ para agregações de cardinalidade
• Algoritmo C3 para seleção adaptativa de réplicas
• Grafos Hierárquicos Navegáveis de Pequeno Mundo (HNSW) para busca de vetor mais próximo no Lucene.
• Estatística MIC para aprimorar a classificação em aprendizado de máquina.
• Block-max WAND para recuperação mais rápida dos melhores resultados no Lucene
• ... e muito mais

Artigos acadêmicos são um recurso inestimável para engenheiros que desenvolvem sistemas com uso intensivo de dados. Mas implementá-los pode ser intimidante e propenso a erros — as descrições dos algoritmos costumam ser complexas, com detalhes práticos importantes omitidos. E os testes representam um verdadeiro desafio: por exemplo, como podemos testar minuciosamente um algoritmo de aprendizado de máquina cujo resultado depende fortemente do conjunto de dados?

Avalie o artigo como se fosse uma dependência de software.

Adicionar uma nova dependência de software exige uma avaliação cuidadosa: se o outro pacote estiver incorreto, lento ou inseguro, nosso projeto também poderá estar. Antes de incluir uma dependência, os desenvolvedores certificam-se de avaliar sua qualidade.

O mesmo se aplica aos artigos acadêmicos que você está considerando publicar. Pode parecer que, pelo simples fato de um algoritmo ter sido publicado em um artigo, ele deve estar correto e ter um bom desempenho. Mas, mesmo tendo passado por um processo de revisão, um artigo acadêmico pode apresentar problemas. Talvez a prova de correção dependa de pressupostos que não são realistas. Ou talvez a seção de "experimentos" mostre um desempenho muito melhor do que a linha de base, mas isso só se aplica a um conjunto de dados específico. Mesmo que o artigo seja de ótima qualidade, sua abordagem pode não ser adequada para o seu projeto.

Ao considerar se devemos ou não nos “depender” de um artigo acadêmico, é útil fazer as mesmas perguntas que faríamos sobre um pacote de software:

• A biblioteca é amplamente utilizada e "testada em situações reais"? → Outros pacotes implementaram este artigo e funcionou bem para eles?
• Existem parâmetros de comparação de desempenho disponíveis? Essas medidas parecem precisas e justas? → O artigo inclui experimentos realistas? Eles são bem projetados?
• A melhoria de desempenho é suficientemente significativa para justificar a complexidade? → O artigo se compara a uma abordagem de referência robusta? Em quanto ele supera essa linha de base?
• Essa abordagem se integrará bem ao nosso sistema? → As premissas e as compensações do algoritmo são adequadas ao nosso caso de uso?

Por algum motivo, quando um pacote de software publica uma comparação de desempenho com seus concorrentes, ele sempre acaba sendo o mais rápido! Se os parâmetros de referência fossem elaborados por terceiros, eles poderiam ser mais equilibrados. O mesmo fenômeno se aplica a artigos acadêmicos. Se um algoritmo apresenta bom desempenho não apenas no artigo original, mas também aparece em outros artigos como uma base de referência sólida, então é muito provável que seja confiável.

Seja criativo nos testes.

Os algoritmos descritos em artigos acadêmicos geralmente apresentam um comportamento mais sofisticado do que os tipos de algoritmos que encontramos rotineiramente. Talvez seja um algoritmo de aproximação que prioriza a velocidade em detrimento da precisão. Ou talvez seja um método de aprendizado de máquina que recebe um grande conjunto de dados e produz resultados (às vezes inesperados). Como podemos escrever testes para esses algoritmos se não conseguimos caracterizar seu comportamento de forma simples?

Foco nos invariantes

Ao projetar testes unitários, é comum pensar em termos de exemplos: se fornecermos ao algoritmo esta entrada de exemplo, ele deverá produzir aquela saída. Infelizmente, para a maioria dos algoritmos matemáticos, os testes baseados em exemplos não abrangem suficientemente seu comportamento.

Vamos considerar o algoritmo C3, que o Elasticsearch usa para determinar qual nó deve processar uma solicitação de pesquisa. O sistema classifica cada nó usando uma fórmula complexa que incorpora o serviço anterior do nó, os tempos de resposta e o tamanho da sua fila. Testar alguns exemplos não garante que entendemos a fórmula corretamente. É útil dar um passo atrás e pensar em testar invariantes: se o tempo de serviço aumentar, a classificação do nó diminui? Se o tamanho da fila for 0, a classificação é determinada pelo tempo de resposta, como afirma o artigo?

Focar nos invariantes pode ajudar em diversos casos comuns:

• O método deve ser independente da ordem? Nesse caso, passar os dados de entrada em uma ordem diferente deve resultar na mesma saída.
• Alguma etapa do algoritmo produz probabilidades de classe? Nesse caso, a soma dessas probabilidades deve ser igual a 1.
• A função é simétrica em relação à origem? Nesse caso, inverter o sinal da entrada deve simplesmente inverter o sinal da saída.

Quando implementamos o C3 pela primeira vez, encontramos um erro na fórmula em que, acidentalmente, usamos o inverso do tempo de resposta em vez do próprio tempo de resposta. Isso significava que os nós mais lentos podiam ser classificados em posições mais altas! Ao corrigir o problema, garantimos a adição de verificações de invariância para evitar erros futuros.

Compare com uma implementação de referência.

Juntamente com o artigo, espera-se que os autores tenham publicado uma implementação do algoritmo. (Isso é especialmente provável se o artigo contiver experimentos, já que muitas revistas exigem que os autores publiquem o código para reproduzir os resultados.) Você pode testar sua abordagem em relação a esta implementação de referência para garantir que não tenha deixado passar detalhes importantes do algoritmo.

Ao desenvolver a implementação HNSW do Lucene para busca de vizinhos mais próximos, realizamos testes em relação a uma biblioteca de referência dos autores do artigo. Executamos o Lucene e a biblioteca no mesmo conjunto de dados, comparando a precisão dos resultados e o número de cálculos realizados. Quando esses números coincidem de perto, sabemos que o Lucene implementa o algoritmo fielmente.

Ao incorporar um algoritmo em um sistema, muitas vezes é necessário fazer modificações ou extensões, como escalá-lo para vários núcleos ou adicionar heurísticas para melhorar o desempenho. O ideal é primeiro implementar uma versão "vanilla", testá-la em comparação com a versão de referência e, em seguida, fazer alterações incrementais. Dessa forma, você pode ter certeza de que capturou todas as partes principais antes de fazer personalizações.

Duelo contra um algoritmo existente

A última seção levanta outra ideia para um invariante de teste: comparar a saída do algoritmo com a saída de um algoritmo mais simples e melhor compreendido. Como exemplo, considere o algoritmo block-max WAND do Lucene, que acelera a recuperação de documentos ignorando aqueles que não podem aparecer nos primeiros resultados. É difícil descrever exatamente como o WAND com block-max deve se comportar em todos os casos, mas sabemos que aplicá-lo não deve alterar os melhores resultados! Assim, nossos testes podem gerar diversas consultas de pesquisa aleatórias e, em seguida, executá-las com e sem a otimização WAND , verificando se os resultados sempre coincidem.

Um aspecto importante desses testes é que eles geram entradas aleatórias para realizar a comparação. Isso pode ajudar a analisar casos que você não teria imaginado e revelar problemas inesperados. Como exemplo, o teste de comparação aleatória do Lucene para pontuação BM25F ajudou a detectar erros em casos extremos sutis. A ideia de alimentar um algoritmo com entradas aleatórias está intimamente relacionada ao conceito de fuzzing, uma técnica de teste comum em segurança da computação.

Elasticsearch e Lucene frequentemente utilizam essa abordagem de teste. Se você vir um teste que menciona um "duelo" entre dois algoritmos (TestDuelingAnalyzers, testDuelTermsQuery...), então você sabe que essa estratégia está em ação.

Utilize a terminologia do artigo.

Quando outro desenvolvedor trabalhar com seu código, ele precisará consultar o documento para seguir os detalhes. O comentário sobre a implementação do HyperLogLog++ do Elasticsearch resume bem a situação: "Tentar entender o que essa classe faz sem ter lido o artigo é considerado uma aventura." Este comentário sobre o método também serve de bom exemplo. Inclui um link para o artigo acadêmico e destaca as modificações feitas no algoritmo em relação à sua descrição original.

Como os desenvolvedores irão basear sua compreensão do código no documento, é útil usar exatamente a mesma terminologia. Como a notação matemática é concisa, isso pode resultar em nomes que normalmente não seriam considerados de "bom estilo", mas que são muito claros no contexto do artigo. As fórmulas de artigos acadêmicos são uma das poucas ocasiões em que você encontrará nomes de variáveis enigmáticos no Elasticsearch, como rS e muBarSInverse.

A maneira recomendada pelo autor para ler um artigo: com um café bem forte.

Você pode enviar um e-mail ao autor.

Ao analisar uma prova difícil, você pode passar horas tentando decifrar uma fórmula, sem saber se está entendendo errado ou se há apenas um erro de digitação. Se fosse um projeto de código aberto, você poderia fazer a pergunta no GitHub ou no StackOverflow. Mas onde você pode encontrar um artigo acadêmico? Os autores parecem estar ocupados e podem se incomodar com seus e-mails.

Pelo contrário, muitos acadêmicos adoram saber que suas ideias estão sendo colocadas em prática e ficam felizes em responder a perguntas por e-mail. Se você trabalhar em um produto com o qual eles estejam familiarizados, eles podem até listar o aplicativo em seu site!

Há também uma tendência crescente entre os acadêmicos de discutir artigos publicamente, utilizando muitas das mesmas ferramentas do desenvolvimento de software. Se um artigo for acompanhado de um pacote de software, você poderá encontrar respostas para perguntas frequentes no Github. Comunidades do Stack Exchange como "Theoretical Computer Science" e "Cross Validated" também contêm discussões detalhadas sobre artigos populares. Algumas conferências começaram a publicar todas as resenhas de artigos online. Essas resenhas contêm discussões com os autores que podem revelar informações úteis sobre a abordagem.

Continua

Este post aborda os princípios básicos da escolha de um artigo acadêmico e

implementá-lo corretamente é suficiente, mas não abrange todos os aspectos da implantação do algoritmo. Por exemplo, se o algoritmo for apenas um componente em um sistema complexo, como podemos garantir que as alterações nesse componente levem a melhorias de ponta a ponta? E se a integração do algoritmo exigir modificações ou extensões substanciais que o artigo original não aborda? Esses são tópicos importantes sobre os quais esperamos compartilhar mais em publicações futuras.