Os algoritmos tradicionais alimentam ferramentas computacionais complicadas, como aprendizado de máquina. Uma nova abordagem, chamada de algoritmos com previsões, usa o poder do aprendizado de máquina para melhorar os algoritmos.
Algoritmos – os pedaços de código que permitem que os programas classifiquem, filtrem e combinem dados, entre outras coisas – são as ferramentas padrão da computação moderna. Como pequenas engrenagens dentro de um relógio, os algoritmos executam tarefas bem definidas em programas mais complicados.
Eles são onipresentes e, em parte por causa disso, foram meticulosamente otimizados ao longo do tempo. Quando um programador precisa classificar uma lista, por exemplo, ele busca um algoritmo padrão de “classificação” que é usado há décadas.
Agora, os pesquisadores estão dando uma nova olhada nos algoritmos tradicionais, usando o ramo da inteligência artificial conhecido como aprendizado de máquina. Sua abordagem, chamada de algoritmos com previsões, aproveita os insights que as ferramentas de aprendizado de máquina podem fornecer sobre os dados que os algoritmos tradicionais manipulam. Essas ferramentas têm, de forma real, rejuvenescido a pesquisa em algoritmos básicos.
O aprendizado de máquina e os algoritmos tradicionais são “duas maneiras substancialmente diferentes de computação, e os algoritmos com previsões são uma maneira de unir as duas”, disse Piotr Indyk, cientista da computação do Massachusetts Institute of Technology. “É uma maneira de combinar esses dois tópicos bastante diferentes.”
A recente explosão de interesse nessa abordagem começou em 2018 com um artigo de Tim Kraska, cientista da computação do MIT, e uma equipe de pesquisadores do Google. Nele, os autores sugeriram que o aprendizado de máquina poderia melhorar um algoritmo tradicional bem estudado chamado filtro Bloom, que resolve um problema simples, mas assustador.
Imagine que você administra o departamento de TI da sua empresa e precisa verificar se seus funcionários estão acessando sites que representam um risco de segurança. Ingenuamente, você pode pensar que precisará verificar todos os sites que eles visitam em uma lista negra de sites conhecidos. Se a lista for enorme (como é provavelmente o caso de sites indesejáveis na internet), o problema se torna complicado – você não pode verificar todos os sites em uma lista enorme no pequeno período de tempo antes de uma página da web ser carregada.
O filtro Bloom fornece uma solução, permitindo que você verifique com rapidez e precisão se o endereço ou URL de um determinado site está na lista negra. Ele faz isso essencialmente comprimindo a lista enorme em uma lista menor que oferece algumas garantias específicas.
Os filtros Bloom nunca produzem falsos negativos – se eles dizem que o site é ruim, é ruim. No entanto, eles podem produzir falsos positivos, então talvez seus funcionários não consigam visitar alguns sites aos quais deveriam ter acesso. Isso porque eles trocam alguma precisão por uma enorme quantidade de compactação de dados – um truque chamado “compactação com perdas”. Quanto mais os filtros Bloom compactam os dados originais, menos precisos eles são, mas mais espaço eles economizam.
Para um simples filtro Bloom, todo site é igualmente suspeito até que seja confirmado que não está na lista. Mas nem todos os sites são criados iguais: alguns são mais propensos do que outros a acabar em uma lista negra, simplesmente por causa de detalhes como seu domínio ou as palavras em seu URL. As pessoas entendem isso intuitivamente, e é por isso que você provavelmente lê os URLs para garantir que eles sejam seguros antes de clicar neles.
A equipe de Kraska desenvolveu um algoritmo que também pode aplicar esse tipo de lógica. Eles o chamaram de “filtro Bloom aprendido” e combina um pequeno filtro Bloom com uma rede neural recorrente (RNN) – um modelo de aprendizado de máquina que aprende como são os URLs maliciosos depois de serem expostos a centenas de milhares de sites seguros e inseguros.
Quando o filtro Bloom aprendido verifica um site, o RNN age primeiro e usa seu treinamento para determinar se o site está na lista negra. Se o RNN disser que está na lista, o filtro Bloom aprendido o rejeita. Mas se a RNN disser que o site não está na lista, então o pequeno filtro Bloom é acionado, pesquisando com precisão, mas sem pensar, seus sites compactados.
Ao colocar o filtro Bloom no final do processo e dar a palavra final, os pesquisadores garantiram que os filtros Bloom aprendidos ainda pudessem garantir que não houvesse falsos negativos. Mas como o RNN pré-filtra os verdadeiros positivos usando o que aprendeu, o pequeno filtro Bloom atua mais como um backup, mantendo seus falsos positivos no mínimo. Um site benigno que poderia ter sido bloqueado por um filtro Bloom maior agora pode passar pelo filtro Bloom aprendido mais preciso. Efetivamente, Kraska e sua equipe encontraram uma maneira de aproveitar duas maneiras comprovadas, mas tradicionalmente separadas, de abordar o mesmo problema para obter resultados mais rápidos e precisos.
“O aprendizado de máquina e os algoritmos tradicionais são duas formas substancialmente diferentes de computação, e os algoritmos com previsões são uma maneira de unir os dois.” – Piotr Indyk, Instituto de Tecnologia de Massachusetts
A equipe de Kraska mostrou que a nova abordagem funcionou, mas não formalizou o porquê. Essa tarefa coube a Michael Mitzenmacher, especialista em filtros Bloom da Universidade de Harvard, que considerou o artigo de Kraska “inovador e empolgante”, mas também fundamentalmente insatisfatório. “Eles fazem experimentos dizendo que seus algoritmos funcionam melhor. Mas o que exatamente aquilo significa?” ele perguntou. “Como nós sabemos?”
Em 2019, Mitzenmacher apresentou uma definição formal de um filtro de Bloom aprendido e analisou suas propriedades matemáticas, fornecendo uma teoria que explicava exatamente como funcionava. E enquanto Kraska e sua equipe mostraram que poderia funcionar em um caso, Mitzenmacher provou que sempre poderia funcionar.
Mitzenmacher também melhorou os filtros Bloom aprendidos. Ele mostrou que adicionar outro filtro Bloom padrão ao processo, desta vez antes do RNN, pode pré-filtrar os casos negativos e facilitar o trabalho do classificador. Ele então provou que era uma melhoria usando a teoria que ele desenvolveu.
Os primeiros dias de algoritmos com previsões seguiram essa trilha cíclica – ideias inovadoras, como os filtros Bloom aprendidos, inspiram resultados matemáticos rigorosos e compreensão, que por sua vez levam a mais ideias novas. Nos últimos anos, os pesquisadores mostraram como incorporar algoritmos com previsões em algoritmos de agendamento, design de chips e pesquisas de sequência de DNA.
Além dos ganhos de desempenho, o campo também avança em uma abordagem da ciência da computação que está crescendo em popularidade: tornar os algoritmos mais eficientes projetando-os para usos típicos.
Atualmente, os cientistas da computação geralmente projetam seus algoritmos para serem bem-sucedidos no cenário mais difícil – um projetado por um adversário tentando derrotá-los. Por exemplo, imagine tentar verificar a segurança de um site sobre vírus de computador. O site pode ser benigno, mas inclui “vírus de computador” na URL e no título da página. É confuso o suficiente para enganar até algoritmos sofisticados.
Indyk chama isso de abordagem paranóica. “Na vida real”, disse ele, “os inputs geralmente não são gerados por adversários”. A maioria dos sites que os funcionários visitam, por exemplo, não são tão complicados quanto nossa página de vírus hipotética, então será mais fácil para um algoritmo classificar. Ao ignorar os piores cenários, os pesquisadores podem projetar algoritmos adaptados às situações que provavelmente encontrarão. Por exemplo, enquanto os bancos de dados atualmente tratam todos os dados igualmente, algoritmos com previsões podem levar a bancos de dados que estruturam seu armazenamento de dados com base em seus conteúdos e usos.
E isso ainda é apenas o começo, pois os programas que usam aprendizado de máquina para aumentar seus algoritmos normalmente o fazem de maneira limitada. Assim como o filtro Bloom aprendido, a maioria dessas novas estruturas incorpora apenas um único elemento de aprendizado de máquina. Kraska imagina um sistema inteiro construído a partir de várias partes separadas, cada uma das quais se baseia em algoritmos com previsões e cujas interações são reguladas por componentes aprimorados de previsão.
“Aproveitar isso afetará muitas áreas diferentes”, disse Kraska.
Publicado em 17/03/2022 11h11
Artigo original: