Inovação em algoritmo acelera programas exponencialmente

Redação do Site Inovação Tecnológica -  03/07/2018

Os algoritmos nos ajudam a encontrar padrões nos dados. Por isso há grande interesse no desenvolvimento de algoritmos quânticos, para os computadores do futuro.[Imagem: CC0 Creative Commons]

Problemas de otimização

Você ouve falar muito sobre inovações em processadores, computadores e no hardware em geral - mas não é muito comum ouvir falar em inovação de software, certo?

Pois acaba de se tornar exponencialmente mais rápida uma grande classe de algoritmos usados hoje pelos mais variados tipos de programas, daqueles que orientam o tráfego e analisam imagens até o sofwares mais especializados, que identificam novas moléculas candidatas a fármacos, por exemplo.

Eric Balkanski e seus colegas da Universidade de Harvard, nos EUA, desenvolveram um tipo completamente novo de algoritmo que acelera exponencialmente a computação, reduzindo drasticamente o número de etapas paralelas necessárias para chegar a uma solução.

Grande parte dos chamados problemas de otimização - problemas que encontram a melhor de todas as possíveis soluções, como mapear a rota mais rápida do ponto A ao ponto B - dependem de algoritmos sequenciais que não mudaram desde que foram descritos pela primeira vez na década de 1970.

Esses algoritmos resolvem um problema seguindo um processo sequencial passo a passo. O número de passos é proporcional ao volume de dados. Mas isso levou a um gargalo computacional, resultando em linhas de questões e áreas de pesquisa que são computacionalmente caras demais para serem exploradas - a chamada propriedade de retornos decrescentes desses algoritmos resulta em que o ganho relativo de cada etapa se torna cada vez menor.

Saltos em lugar de passos

É aí que entra a inovação: Em vez de dar centenas ou milhares de pequenos passos para se aproximar da solução, o novo algoritmo pode dar apenas alguns saltos. Tradicionalmente, os algoritmos para problemas de otimização reduzem o espaço de pesquisa para a melhor solução, um passo de cada vez. Já esse novo algoritmo faz uma amostragem de várias direções em paralelo. Com base nessa amostra, o algoritmo descarta os rumos de baixo valor de seu espaço de pesquisa e escolhe os rumos mais valiosos para avançar em direção a uma solução.

É mais fácil entender com um exemplo.

Imagine que você está com vontade de assistir a um filme semelhante a Os Vingadores. Um algoritmo de recomendação tradicional adiciona sequencialmente, um de cada vez, filmes com atributos semelhantes aos de Os Vingadores. Já o novo algoritmo faz amostragens aleatórias de um grupo de filmes, descartando aqueles que são muito diferentes dos Vingadores, mas também aqueles que são muito parecidos entre si - afinal, você não quer dez filmes do Batman. O algoritmo continua adicionando lotes em cada etapa até que tenha filmes suficientes para recomendar.

Em um experimento de demonstração, o algoritmo filtrou um conjunto de dados com 1 milhão de avaliações de 6.000 usuários sobre 4.000 filmes e recomendou uma coleção personalizada e diversificada de filmes para um usuário individual 20 vezes mais rápido do que o programa estado-da-arte.

Múltiplas aplicações

"Esse algoritmo e essa abordagem em geral nos permite acelerar drasticamente a computação para uma classe gigantesca de problemas em muitas disciplinas diferentes, incluindo visão computacional, recuperação de informações, análise de redes, biologia computacional, design de leilões e muitas outras. Podemos agora executar em apenas alguns segundos cálculos que anteriormente levavam semanas ou meses," disse o professor Yaron Singer, orientador do grupo.

• Algoritmos fomentam desigualdade e discriminação, diz pesquisadora

Bibliografia:

An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
Eric Balkanski, Aviad Rubinstein, Yaron Singer
To be published
https://arxiv.org/abs/1804.06355