A capacidade de processamento e a memória dos computadores cresceram exponencialmente nos últimos 50 anos, mas a lógica das máquinas pouco evoluiu. A classe de problemas possíveis de serem resolvidos foi determinada na década de 1930, quando o primeiro computador nem sequer havia sido construído. Depois foi descoberto que há problemas sabidamente fáceis, outros sabidamente difíceis – os chamados “problemas intratáveis” – e um conjunto cuja real dificuldade é desconhecida.
A avaliação foi feita por Marcelo Finger, professor do Instituto de Matemática e Estatística da Universidade de São Paulo (IME-USP), que desde 2009 coordena um Projeto Temático financiado pela Fapesp cuja meta é tornar os programas computacionais mais “inteligentes”. Para isso, a equipe pesquisa novas metodologias para resolver problemas que estão na intersecção de duas formas de raciocínio: o lógico e o probabilístico. As aplicações práticas são variadas e vão desde o desenvolvimento de sites de busca e tradutores automáticos mais eficientes até softwares capazes de analisar imagens gravadas em vídeo e detectar quando algo está fora do normal em um determinado local ou situação.
O Temático já resultou em 104 artigos publicados, três pós-doutorados, quatro doutorados, 15 mestrados e seis projetos de iniciação científica. Em entrevista à Agência Fapesp, Finger conta detalhes sobre alguns dos resultados alcançados.
“Solucionar problemas com 400 variáveis em menos de um segundo”
De que forma o Projeto Temático que o senhor coordena pode contribuir para tornar os programas mais inteligentes?
Marcelo Finger – Em computação existem problemas solúveis e problemas insolúveis. E dentro da categoria solúvel, grande parte é considerada intratável, ou seja, o tempo de resolução é tão grande que se torna inviável na prática. Os problemas na intersecção entre o raciocínio lógico e probabilístico geralmente estão na classe dos intratáveis ou em uma zona cinzenta, onde não sabemos se são passíveis de serem resolvidos rapidamente ou não. Uma das linhas de pesquisa do Temático se dedica a buscar meios para identificar quais desses problemas são possíveis de serem resolvidos e desenvolver metodologias para resolvê-los rapidamente.
De que forma isso vem sendo feito?
M.F. – Mostramos que para alguns dos problemas intratáveis há um fenômeno de transição de fase. De um lado, há uma grande classe de problemas fáceis, cuja resposta é sempre sim. Do outro lado, há uma classe de problemas um pouco mais difíceis, cuja resposta é sempre não. No meio estão os casos realmente complicados, para os quais não sabemos se há resposta rápida. Com base nesse conhecimento, criamos três algoritmos, um melhor do que o outro, para solucionar rapidamente os problemas que estão em um dos dois extremos. Antes, acreditava-se que era impossível resolver um problema com mais de seis variáveis. Mas, com esse método, conseguimos solucionar problemas com 400 variáveis em menos de um segundo.
“Estamos trabalhando com a web semântica na área médica”
Poderia dar algum exemplo de aplicação prática desse método?
M.F. – Queremos aplicá-lo em várias áreas, como a Linguística Computacional. Com o método que desenvolvemos será possível melhorar programas que fazem análise sintática. Isso pode ser usado em tradutores automáticos, por exemplo. Também estamos tentando melhorar os algoritmos de robôs, para que eles se tornem capazes de realizar tarefas mais complexas. Há ainda outras duas linhas, uma que trabalha com análise de imagens e outra com a web semântica.
O que é a web semântica?
M.F. – Significa relacionar domínios distintos e fazer com que eles se comuniquem. Hoje os sites de busca funcionam por associação de palavras. Com a web semântica é possível criar programas capazes de associar conceitos e fazer uma busca muito mais inteligente. Você procura por um termo e o programa responde com outra terminologia e de forma correta. No nosso projeto estamos trabalhando com a web semântica aplicada na área médica.
“Vamos tentar desenvolver algoritmos melhores”
Que tipo de aplicação poderemos ter em medicina?
M.F. – A ideia é criar uma ferramenta capaz de ajudar o médico no diagnóstico. O programa uniria as descrições de sintomas e outras informações lógicas sobre a doença com as observações médicas, que são de natureza probabilística. Por exemplo, febre pode ser sintoma de uma determinada doença, mas nem todos os portadores dessa doença vão ter febre. São dados probabilísticos. Isso tem uma aplicação prática mais imediata. Já temos um hospital interessado.
E o que pretende a linha de pesquisa do Temático que trabalha com análise de imagens?
M.F. – Criar um programa capaz de analisar as cenas gravadas por uma câmera e detectar quando ocorre algo fora do previsto. Isso poderia ser usado, por exemplo, por empresas aéreas para supervisionar procedimentos de abastecimento, carga e descarga de aviões. Ou então por empresas de segurança patrimonial. Estamos trabalhando com filmagens de voos, mas por enquanto conseguimos apenas casos em que não ocorreu nenhum imprevisto e, portanto, nossos dados não eram bons o suficiente para fazer um treinamento das probabilidades de erro.
Quais são os projetos futuros do Temático?
M.F. – Pretendemos estender o projeto por mais dois anos para dar continuidade aos trabalhos. Continuaremos com as mesmas linhas de pesquisa. Vamos tentar desenvolver algoritmos melhores, buscar soluções mais rápidas e expandir a metodologia para outros tipos de problema relacionados. Devo passar um ano na Universidade Cornell, nos Estados Unidos, para levar os nossos resultados e criar uma iteração com os pesquisadores de lá. Durante a minha ausência, o professor Fabio Gagliardi Cozman, da Escola Politécnica da USP, assumirá a coordenação.
***
[Karina Toledo, da Agência Fapesp]