Tratando o intratável
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 verificou-se que há problemas sabidamente fáceis, outros sabidamente difíceis - os chamados "problemas intratáveis" - e um conjunto cuja real dificuldade é desconhecida.
O professor Marcelo Finger, professor do Instituto de Matemática e Estatística da Universidade de São Paulo (IME-USP), coordena desde 2009 um projeto 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 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.
Nesta entrevista, concedida à Agência FAPESP, o professor Marcelo conta detalhes sobre alguns dos resultados alcançados.
Em 2010, um programa de computador conseguiu decifrar uma língua extinta, chamada ugarítico. [Imagem: MIT]
De que forma o Projeto que o senhor coordena pode contribuir para tornar os programas mais inteligentes?
Prof. Marcelo - 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 se dedica a buscar meios para identificar quais desses problemas são passíveis de serem resolvidos e desenvolver metodologias para resolvê-los rapidamente.
De que forma isso vem sendo feito?
Prof. Marcelo - 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.
Algoritmos genéticos, programas de computador capazes de evoluir, estão sendo usados para desenvolver o comportamento de robôs e até para tentar descobrir novas leis da física. [Imagem: Lipson Lab]
Poderia dar algum exemplo de aplicação prática desse método?
Prof. Marcelo - 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?
Prof. Marcelo - 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.
Que tipo de aplicação poderemos ter em medicina?
Prof. Marcelo - 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.
Usando os sistemas probabilísticos, um cientista criou uma linguagem de computador que pode fazer renascer o campo da inteligência artificial. [Imagem: MIT]
E o que pretende a linha de pesquisa que trabalha com análise de imagens?
Prof. Marcelo - 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?
Prof. Marcelo - 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.
Com informações da Agência Fapesp - 13/06/2012
http://www.inovacaotecnologica.com.br
