p E se uma grande classe de algoritmos usados ​​hoje - desde os algoritmos que nos ajudam a evitar o tráfego até os algoritmos que identificam novas moléculas de drogas - funcionasse exponencialmente mais rápido? p Os cientistas da computação da Escola de Engenharia e Ciências Aplicadas (SEAS) de Harvard John A. Paulson desenvolveram um tipo completamente novo de algoritmo, um que acelera exponencialmente a computação, reduzindo drasticamente o número de etapas paralelas necessárias para chegar a uma solução.

p Os pesquisadores apresentarão sua nova abordagem em duas conferências futuras:o ACM Symposium on Theory of Computing (STOC), 25 a 29 de junho e Conferência Internacional sobre Aprendizado de Máquina (ICML), 10 a 15 de julho.

p Muitos dos chamados problemas de otimização, problemas que encontram a melhor solução de todas as soluções possíveis, 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 passo a passo sequencial. O número de etapas é proporcional ao tamanho dos dados. Mas isso levou a um gargalo computacional, resultando em linhas de questões e áreas de pesquisa que são muito caras para explorar.

p "Esses problemas de otimização têm uma propriedade de retornos decrescentes, "disse Yaron Singer, Professor assistente de Ciência da Computação no SEAS e autor sênior da pesquisa. "À medida que um algoritmo avança, o ganho relativo de cada etapa torna-se cada vez menor. "

p Singer e seu colega perguntaram:e se, em vez de tomar centenas ou milhares de pequenos passos para chegar a uma solução, um algoritmo poderia dar apenas alguns saltos?

p "Este algoritmo e abordagem geral nos permitem acelerar drasticamente a computação para uma classe extremamente grande de problemas em muitos campos diferentes, incluindo visão computacional, recuperação de informação, análise de rede, biologia Computacional, projeto de leilão, e muitos outros, ", disse Singer." Agora podemos realizar cálculos em apenas alguns segundos que antes levariam semanas ou meses. "

p "Este novo trabalho algorítmico, e a análise correspondente, abre as portas para novas estratégias de paralelização em grande escala que têm acelerações muito maiores do que o que já foi possível antes, "disse Jeff Bilmes, Professor do Departamento de Engenharia Elétrica da Universidade de Washington, que não participou da pesquisa. "Essas habilidades vão, por exemplo, permitem que processos de sumarização do mundo real sejam desenvolvidos em escala sem precedentes. "

p Tradicionalmente, algoritmos para problemas de otimização restringem o espaço de busca para a melhor solução uma etapa de cada vez. Em contraste, este novo algoritmo mostra uma variedade de direções em paralelo. Com base nessa amostra, o algoritmo descarta as direções de baixo valor de seu espaço de busca e escolhe as direções mais valiosas para progredir em direção a uma solução.

p Veja este exemplo de brinquedo:

p Você está com vontade de assistir a um filme semelhante a Os Vingadores. Um algoritmo de recomendação tradicional adicionaria sequencialmente um único filme em cada etapa, com atributos semelhantes aos de Os Vingadores. Em contraste, o novo algoritmo mostra um grupo de filmes aleatoriamente, descartando aqueles que são muito diferentes dos Vingadores. O que resta é um lote de filmes que são diversos (afinal, você não quer dez filmes do Batman), mas semelhante a Os Vingadores. O algoritmo continua a adicionar lotes em cada etapa até que tenha filmes suficientes para recomendar.

p Este processo de amostragem adaptativa é a chave para a capacidade do algoritmo de tomar a decisão certa em cada etapa.

p "Algoritmos tradicionais para esta classe de problema adicionam avidamente dados à solução enquanto consideram todo o conjunto de dados em cada etapa, "disse Eric Balkanski, aluno de pós-graduação da SEAS e coautor da pesquisa. "A força do nosso algoritmo é que, além de adicionar dados, ele também remove seletivamente os dados que serão ignorados em etapas futuras. "

p Em experimentos, Singer e Balkanski demonstraram que seu algoritmo pode filtrar um conjunto de dados que continha 1 milhão de classificações de 6, 000 usuários em 4, 000 filmes e recomendar uma coleção personalizada e diversificada de filmes para um usuário individual 20 vezes mais rápido do que o estado da arte.

p Os pesquisadores também testaram o algoritmo em um problema de despacho de táxi, onde há um certo número de táxis e o objetivo é escolher os melhores locais para atender ao máximo de clientes em potencial. Usando um conjunto de dados de dois milhões de viagens de táxi da comissão de táxi e limusine da cidade de Nova York, o algoritmo de amostragem adaptativa encontrou soluções 6 vezes mais rápidas.

p "Essa lacuna aumentaria ainda mais significativamente em aplicativos de maior escala, como agrupamento de dados biológicos, leilões de pesquisa patrocinados, ou análises de mídia social, "disse Balkanski.

p Claro, o potencial do algoritmo vai muito além das recomendações de filmes e otimizações de despacho de táxi. Pode ser aplicado a:

• projetar ensaios clínicos para medicamentos para tratar a doença de Alzheimer, esclerose múltipla, obesidade, diabetes, Hepatite C, HIV e mais
• biologia evolutiva para encontrar bons subconjuntos representativos de diferentes coleções de genes a partir de grandes conjuntos de dados de genes de diferentes espécies
• projetar matrizes de sensores para imagens médicas
• identificando a detecção de interação droga-droga em fóruns de saúde on-line

p Esse processo de aprendizagem ativa é a chave para a capacidade do algoritmo de tomar a decisão certa em cada etapa e resolve o problema dos retornos decrescentes.

p "Esta pesquisa é um verdadeiro avanço para otimização discreta em grande escala, "disse Andreas Krause, professor de Ciência da Computação na ETH Zurique, que não participou da pesquisa. "Um dos maiores desafios do aprendizado de máquina é encontrar o que é bom, subconjuntos representativos de dados de grandes coleções de imagens ou vídeos para treinar modelos de aprendizado de máquina. Esta pesquisa pode identificar esses subconjuntos rapidamente e ter um impacto prático substancial sobre esses problemas de sumarização de dados em grande escala. "

p O modelo Singer-Balkanski e as variantes do algoritmo desenvolvido no artigo também podem ser usados ​​para avaliar mais rapidamente a precisão de um modelo de aprendizado de máquina, disse Vahab Mirrokni, um dos principais cientistas do Google Research, que não participou da pesquisa.

p "Em alguns casos, temos um acesso de caixa preta à função de precisão do modelo, que consome muito tempo para calcular, "disse Mirrokni." Ao mesmo tempo, A precisão do modelo de computação para muitas configurações de recursos pode ser feita em paralelo. Esta estrutura de otimização adaptativa é um ótimo modelo para essas configurações importantes e os insights das técnicas algorítmicas desenvolvidas nesta estrutura podem ter um impacto profundo nesta importante área de pesquisa de aprendizado de máquina. "

p Singer e Balkanski continuam a trabalhar com os profissionais na implementação do algoritmo.