Genética digital

Pesquisa pioneira aposta na capacidade evolutiva de algoritmos para criar uma solução inédita em classificação de dados: o algoritmo evolucionário hiper-heurístico HEAD-DT

Entreteses11 p099 geneticaDigital

 

Texto: Valquíria Carnaúba

Qual seria a melhor e mais simples forma de resolver problemas de classificação de dados, como no caso de serviços bancários, controle de entrada e saída de pessoas e diagnósticos médicos? Existem diversos métodos, como as funções matemáticas e as redes neurais (sistemas computacionais inspirados no sistema nervoso central). E existem as árvores de decisão, aplicações baseadas no fornecimento de dados a computadores específicos, de modo a permitir que aprendam por si mesmos. Seu pleno funcionamento apoia-se nos algoritmos, sequências de instruções executáveis que oferecem soluções a determinados problemas. Cada árvore de decisão, por sua vez, opera a partir de um nó interno com perguntas-chave, cujas respostas levam a outras perguntas mais específicas, gerando por fim nós terminais – conjuntos de dados convertidos em informações. A sequência completa de comandos é, então, incluída em um nó folha (rótulo), como é chamado o resultado de cada operação (vide infográfico).

As árvores de decisão são amplamente utilizadas no aprendizado de máquina (machine learning), método de análise de dados que automatiza a construção de modelos analíticos. Sua vantagem em relação a outras ferramentas está na facilidade de interpretação dos dados, conforme observa Márcio Porto Basgalupp, docente da disciplina de Ciência da Computação do Instituto de Ciência e Tecnologia (ICT/Unifesp) - Campus São José dos Campos. Ele coordena o projeto Programação Genética para Evolução de Algoritmos de Indução de Árvores de Decisão, que faz parte do Programa de Apoio a Jovens Pesquisadores da Fundação de Amparo à Pesquisa do Estado de São Paulo (Fapesp). Baseado nas recentes descobertas da área, o pesquisador propôs o HEAD-DT, algoritmo evolucionário (que se aperfeiçoa sem a intervenção humana), hiper-heurístico, que gera automaticamente outros comandos, capazes de formar novas árvores de decisão. 

Heurística parece uma palavra estranha, mas o termo se aplica a diversos campos do conhecimento. O dicionário Michaelis, por exemplo, contém uma definição, relativa à Pedagogia, que dá pistas interessantes para entender seu conceito na Ciência da Computação: significa o método educacional que incentiva o estudante a buscar soluções diante de uma situação-problema, promovendo o aprendizado baseado na experiência pessoal. Quando falamos de máquinas, a heurística consistiria na aplicação de métodos de aprendizado automatizado. Logo, uma hiper-heurística reuniria, em um só sistema, várias heurísticas mais simples (diversas formas de solução para um mesmo problema), de modo a resolver os impasses da pesquisa computacional de forma eficiente.

O projeto de programação genética para evolução de algoritmos resultou do doutorado-sanduíche de Basgalupp na Universidade de Kent (Inglaterra), orientado por Alex Freitas, docente da referida instituição. A tese de doutorado, propriamente dita, foi inspirada em Charles Darwin, tendo sido orientada no Brasil por André Carlos Ponce de Leon Ferreira de Carvalho, docente da Universidade de São Paulo (USP). Basgalupp, na época, decidiu explorar a hiper-heurística evolutiva, uma etapa mais avançada que a heurística computacional. “O algoritmo HEAD-DT parte de operações tradicionais de indução de árvores de decisão – desenvolvidas manualmente por programadores. Conduzido por um algoritmo típico de busca evolutiva, combina os componentes mais adequados para o problema em questão. No final, espera-se que o algoritmo genérico fabrique, automaticamente, um novo comando para, então, obter uma nova árvore de decisão. Cada solução é uma gênese, e o conjunto de soluções passa a ser combinada para que outras melhores apareçam”, explica o docente. 

Aprendizado de máquina x inteligência artificial

Embora o machine learning e a forma como opera nos remetam facilmente à inteligência artificial (AI), ambas tratam de tecnologias distintas. Enquanto a AI envolve máquinas que podem realizar tarefas que são características da inteligência humana, o aprendizado de máquina seria uma ferramenta para alcançar a AI. Associar os dois termos é natural: afinal o desenvolvimento desses dois campos está diretamente ligado à revolução digital, que modifica – dia após dia – o modo como produzimos e lidamos com um volume crescente de dados (no formato de vídeos, fotos, posts em redes sociais e blogs, entre outros de uma extensa lista). 

As árvores de decisão tornaram-se cruciais para aperfeiçoar negócios em plataformas de e-commerce, por exemplo, facilitando transações, antecipando as necessidades de clientes e otimizando preços. Mas o que indica se um algoritmo é bom ou não? A resposta depende do refinamento dos atributos que compõem o algoritmo. Quanto maior a taxa de acerto, melhor o algoritmo. Os pesquisadores trabalham com comandos personalizados, criando diferentes softwares para determinados domínios de aplicação. “Tentamos encontrar qual o algoritmo mais específico para um dado problema. É mais simples encontrar uma solução específica do que uma geral”, complementa o autor.

O maior desafio encontrado durante o desenvolvimento do projeto – segundo Basgalupp – foi justamente seu caráter pioneiro. Houve vantagens óbvias no fato de ser novidade, mas os pesquisadores foram obrigados a enfrentar a ausência de trabalhos relacionados para serem usados como base. Verificou-se, inclusive, a dificuldade de entendimento por parte de pessoas que eram da mesma área. Para além do ônus, entretanto, o ineditismo trouxe o bônus: a pesquisa originou o artigo A Hyper-Heuristic Evolutionary Algorithm for Automatically Designing Decision-Tree Algorithms, premiado na conferência Genetic and Evolutionary Computation Conference (Gecco), sobre computação evolutiva, que se realizou na Filadélfia (EUA). O prêmio resultou em um convite para os pesquisadores submeterem uma versão ampliada do trabalho ao periódico Evolutionary Computation Journal.

Entreteses11 p100 Basgalupp

Dedicado à computação evolutiva, Márcio Basgalupp explica como o algoritmo HEAD-DT, proposto em seu estudo, pode facilitar tomadas de decisão para a geração automática de árvores de decisão

Entreteses11 p100 arvore decisao

Artigos relacionados:

BASGALUPP, Márcio P.; CARVALHO, André C. P. L. F. de; BARROS, Rodrigo C.; RUIZ, Duncan D.; FREITAS, A. A. Lexicographic multi-objective evolutionary induction of decision trees. International Journal of Bio-Inspired Computation, [s.l.], v. 1, n. 1/2, p. 105–117, 2009. Disponível em: <https://www.inderscience.com/info/inarticle.php?artid=22779 >. Acesso em: 12 abr. 2019.

BARROS, Rodrigo Coelho; BASGALUPP, Márcio Porto; CARVALHO, André C. P. L. F. de; FREITAS, Alex A. A survey of evolutionary algorithms for decision-tree induction. IEEE Transactions on Systems, Man, and Cybernetics - Part C: Applications and Reviews, [s.l.], v.42, n.3, p. 291-312, maio 2012. Disponível em: <https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5928432 >. Acesso em: 12 abr. 2019.

BARROS, Rodrigo Coelho; RUIZ, Duncan D.; BASGALUPP, Márcio Porto. Evolutionary model trees for handling continuous classes in machine learning. Information Sciences, [s.l.], v. 181, n. 5, p. 954–971, mar. 2011. Disponível em: <https://doi.org/10.1016/j.ins.2010.11.010 >. Acesso em: 12 abr. 2019.

BARROS, Rodrigo C.; BASGALUPP, Márcio P.; CARVALHO, André C. P. L. F. de. Investigating fitness functions for a hyper-heuristic evolutionary algorithm in the context of balanced and imbalanced data classification. Genetic Programming and Evolvable Machines, [s.l.], v. 16, n. 3, p. 241-281, set. 2015. Disponível em: <https://link.springer.com/article/10.1007/s10710-014-9235-z >. Acesso em: 16 abr. 2019.