Entreteses

Qual seria a melhor e mais simples forma de resolver problemas de classificação, como análise de créditos em bancos, controles de entrada e saída de pessoas, diagnóstico médico, etc?

Existem diversas maneiras de resolver esse tipo de problema, como funções matemáticas, redes neurais artificiais, máquinas de vetores de suporte, e árvores de decisão. Dado um problema de classificação, as árvores de decisão podem ser construídas por diversos algoritmos, cada qual com suas particularidades mas com algo em comum: todos desenvolvidos por seres humanos. A estrutura de uma árvore de decisão consiste em nós internos, que representam perguntas sobre determinadas características (por exemplo, sexo de uma pessoa), seguidos de arestas, que representam respostas para as perguntas (masculino ou feminino), e por fim os nós folha, que representam o rótulo, ou seja, a classe (categoria) à qual pertence essa pessoa.

A vantagem de se utilizar esse método de representação do conhecimento em relação a outros está na facilidade de interpretação: qualquer pessoa consegue entender e interpretar os dados contidos nas árvores de decisão, conforme observa Márcio Porto Basgalupp, do Departamento de Ciência da Computação do Instituto de Ciência e Tecnologia (ICT-Unifesp) e coordenador do projeto “Programação Genética para Evolução de Algoritmos de Indução de Árvores de Decisão”, parte do programa Jovem Pesquisador da Fundação de Amparo à Pesquisa do Estado de São Paulo (Fapesp).

Segundo Basgalupp, as árvores de decisão podem ser construídas com diversos algoritmos, até agora desenvolvidos por seres humanos. O objetivo principal da pesquisa é fazer com que o algoritmo genético fabrique sozinho, automaticamente, um novo algoritmo para, no fim, obter uma nova árvore de decisão. “É um trabalho pioneiro nessa área: realizar a construção automática de algoritmos, softwares ou programas, que gerarão outros”.

O projeto surgiu como resultado do pós-doutorado de Basgalupp. “Passei no concurso e transformei o meu projeto em proposta de Jovem Pesquisador, submetida à Fapesp em 2011”, afirma. “Requisitei três anos para o seu pleno desenvolvimento, que está previsto para acontecer até agosto de 2014.” A pesquisa está sendo feita em parceria com a Universidade de São Paulo (Campus São Carlos), por André Carlos Ponce de Leon Ferreira de Carvalho, e com a University of Kent (Inglaterra) por Alex Freitas. Também participa deste trabalho Rodrigo Coelho Barros, doutorando do Laboratório de Computação Bioinspirada (BioCom) da USP e bolsista da Fapesp.

O projeto tem como inspiração o evolucionismo de Charles Darwin, explica Basgalupp. “De alguma forma, nós representamos o problema computacionalmente, geralmente no formato de gênese. Cada solução é uma gênese que vamos combinando-as para que as melhores apareçam”, diz. “Desse modo, aquelas que se mostrarem mais aptas terão chance de trocar de gênese, de sobreviver, de cruzar com outras e gerar filhas descendentes”.

Selecionando os melhores

Mas, o que diz se um algoritmo é bom ou não? A resposta depende da taxa de acerto da árvore de indução por ele construída. Quanto maior a taxa, melhor o algoritmo.

Os pesquisadores trabalham com o algoritmo customizado, criam diferentes softwares para determinados domínios de aplicação. “Tentamos encontrar qual é o algoritmo superior para aquele determinado problema. É mais simples conseguir achar uma solução específica do que uma geral”, explica Basgalupp.

Restando apenas um ano para o seu término, a pesquisa já obteve bons resultados, inclusive originou o artigo A Hyper-Heuristic Evolutionary Algorithm for Automatically Designing Decision-Tree Algorithms, premiado em uma conferência de computação evolutiva, realizada na Filadélfia (Estados Unidos), a Genetic and Evolutionary Computacion Conference (Gecco). O prêmio resultou em convite para os pesquisadores submeterem uma versão estendida do trabalho no periódico Evolutionary Computacion Journal.

Basgalupp afirma que o maior desafio encontrado foi justamente o caráter pioneiro do projeto. Se há vantagens óbvias no fato de ser novidade, por outro lado, os pesquisadores são obrigados a enfrentar a ausência de trabalhos relacionados para usar como base. “Há a dificuldade de entendimento, mesmo com pessoas que são da área. A tarefa de explicar, convencê-los da novidade do projeto foi a grande dificuldade durante todo o processo”, explica.

O programa deverá produzir um impacto significativo na área de tecnologia por permitir o desenvolvimento automático de algoritmos melhores, produzidos e testados por máquinas, antes de serem submetidos ao uso humano.