Novo algoritmo reduz o tempo de computação em ordens de magnitude

• Um novo algoritmo acelera exponencialmente a computação, diminuindo drasticamente o número de iterações necessárias para resolver um problema.
• Ele tem um desempenho muito melhor do que algoritmos convencionais (sequenciais) em conjuntos de dados de grande escala, como análise de mídia social e agrupamento de dados genéticos. 

Milhares de problemas de otimização (problema de encontrar a melhor solução entre todas as soluções viáveis), como alocar fundos para ações para minimizar o risco nos retornos, ou atribuir funcionários a escritórios disponíveis para maximizar o fluxo de trabalho e a estatística dos funcionários, dependem fortemente de algoritmos sequenciais.

O padrão básico de funcionamento desses algoritmos não foi alterado (aprimorado) desde que foram estabelecidos no início da década de 1970. Eles resolvem qualquer problema específico sequencialmente em “n” etapas.

O número de etapas depende do tamanho do problema (que fornece certos valores ao algoritmo como entrada). Esse tipo de método geralmente resulta em um gargalo computacional. O ganho relativo de cada iteração torna-se cada vez menor à medida que o algoritmo avança.

E se um algoritmo pudesse dar alguns saltos, em vez de milhares de pequenos passos para resolver o problema? E se pudéssemos fazer com que um grande conjunto de algoritmos amplamente usados ​​hoje funcionasse exponencialmente mais rápido? Estamos falando dos algoritmos que nos ajudam a descobrir novas drogas e evitar o tráfico.

Para tornar isto possível, investigadores da Universidade de Harvard criaram um novo tipo de algoritmo, a que chamam “Breakthrough”, que acelera exponencialmente a computação ao diminuir drasticamente o número de iterações necessárias para resolver um problema.

Ele acelera a computação para uma ampla gama de problemas em diversas áreas, como extração de informações, design de leilões, visão artificial, biologia computacional, análise de redes e muito mais.

Segundo os desenvolvedores, ele é capaz de realizar grandes cálculos em vários segundos que antes levariam dias ou semanas. Isto poderia abrir as portas para novas abordagens de paralelização em larga escala, permitindo que processos práticos de resumo fossem construídos em escala excepcional.

Como funciona?

Os algoritmos sequenciais funcionam restringindo o número de soluções viáveis, uma etapa de cada vez. Já o novo algoritmo faz amostras paralelas de diferentes direções e, em seguida, elimina direções menos relevantes e seleciona as direções mais favoráveis ​​(de alto valor) para chegar à solução. Ele descarta seletivamente valores que serão ignorados em iterações futuras.

Algoritmo inovador usa amostragem adaptativa | Cortesia de pesquisadores

Mais especificamente, o algoritmo requer O (log n) passos sequenciais e atinge uma aproximação arbitrariamente próxima de 1/3. Ao permitir a paralelização, os algoritmos atingem uma aproximação de fator constante exponencialmente mais rápido do que qualquer método existente para maximização submodular.

Referência:Harvard SEAS | Publicações de Harvard

Por exemplo, se a tarefa é recomendar filmes semelhantes a Star Wars, um algoritmo convencional adicionaria um filme em cada etapa que tivesse atributos semelhantes (ação, aventura, fantasia) aos de Star Wars.

O algoritmo recém-desenvolvido, por outro lado, faz amostras aleatórias de um conjunto de filmes, eliminando aqueles que não correspondem de forma alguma a Star Wars. Isso fornece uma coleção diversificada de filmes (obviamente, você não quer 10 filmes do Superman em sua recomendação) semelhantes a Star Wars.

O algoritmo continuará adicionando variedade de filmes em cada etapa até ter itens suficientes para recomendar. A chave para tomar decisões valiosas em cada etapa está no processo de amostragem adaptativa.

Nº de etapas executadas por um algoritmo sequencial (preto) e inovador (vermelho) para resolver um problema

Testes e aplicações

Os pesquisadores testaram seu algoritmo de amostragem adaptativa em um grande conjunto de dados contendo 1 milhão de avaliações em 4.000 filmes de 6.000 usuários. Ele recomendou com sucesso filmes personalizados e variados para uma pessoa 20 vezes mais rápido do que os algoritmos convencionais.

Eles também aplicaram esse algoritmo em um problema de despacho de táxis – escolher os melhores locais para atender o número máximo de clientes com táxis limitados. Para 2 milhões de viagens de táxi, o algoritmo funcionou 6 vezes mais rápido que o estado da arte.

Pode produzir resultados muito melhores em conjuntos de dados em grande escala, como análises de redes sociais ou agrupamento de dados genéticos.  Fora isso, o algoritmo poderia ser aplicado no desenvolvimento de ensaios clínicos para múltiplas doenças, conjuntos de sensores para imagens médicas e detecção de interação entre medicamentos.

Leia:Pesquisar novo algoritmo de veículo autônomo pode mudar de faixa agressivamente

Hoje em dia, encontrar um subconjunto eficaz de dados de milhões de imagens/vídeos para treinar redes de aprendizagem profunda tornou-se uma tarefa desafiadora. Este estudo poderia ajudar a extrair subconjuntos valiosos rapidamente e ter um impacto significativo em problemas de sumarização de dados em grande escala.