Skriveforsking i Noreg og Skandinavia i dag

Neste capítulo, foram abordados os conceitos de Redes Neurais Artificiais, que são algorit- mos inspirados no funcionamento do cérebro humano. Foram apresentados alguns conceitos do sistema nervoso humano e também conceitos do neurônio artificial utilizado nas redes neurais artificiais. Também foram introduzidos os conceitos de Single e Multi-Layer Perceptrons e dois algoritmos utilizados no treinamento de redes neurais Multi-Layer Perceptrons.

Além das redes neurais, foram apresentados os conceitos de Algoritmos Genéticos, que têm como objetivo solucionar problemas utilizando como inspiração a teoria da evolução das espécies. Foi apresentado o Algoritmo Evolutivo tradicional, e também os principais operadores utilizados no processo evolutivo dos Algoritmos Genéticos. O próximo capítulo apresentará os conceitos fundamentais de classificação hierárquica multirrótulo, problema investigado nesta pesquisa de Doutorado.

3

Classificação Hierárquica e Multirrótulo

Este capítulo apresenta os conceitos de classificação hierárquica e classificação multirrótulo. Inicialmente, nas Seções3.1 e 3.2, são introduzidos os conceitos de classificação hierárquica simples-rótulo e classificação multirrótulo não hierárquica. Esses dois tipos de problemas po- dem ser combinados, dando origem a problemas de classificação mais complexos, chamados de problemas de classificação hierárquica multirrótulo. Esses problemas são formalmente defi- nidos na Seção3.3; os trabalhos mais recentes da literatura que tratam problemas hierárquicos multirrótulo são revisados na Seção3.4, separados em métodos que utilizam e que não utilizam abordagens bioinspiradas; na Seção3.5, é feita uma revisão das principais medidas de avalia- ção de classificadores hierárquicos multirrótulo encontradas na literatura; por fim, a Seção3.6

apresenta as considerações finais deste capítulo.

3.1 Classificação Hierárquica Simples-Rótulo

Em grande parte dos problemas de classificação descritos na literatura, um classificador atri- bui uma única classe a cada exemplo xi, e essas classes formam uma estrutura não hierárquica,

na qual não são considerados relacionamentos de superclasses e subclasses. Entretanto, em muitos problemas de classificação reais, uma ou mais classes podem ser divididas em subclas- ses ou agrupadas em superclasses. Nesses casos, as classes são estruturadas hierarquicamente, geralmente em uma estrutura do tipo árvore ou do tipo grafo acíclico direcionado (DAG). Es- ses tipos de problemas são conhecidos na literatura de AM como problemas de classificação hierárquica. Nesses problemas, novos exemplos são atribuídos a classes associadas a nós per- tencentes a uma estrutura hierárquica. Quando cada novo exemplo deve ser atribuído a um nó folha de uma hierarquia de classes, a tarefa de classificação hierárquica é denominada classifi- cação obrigatória em nós folhas. Quando a classe mais específica atribuída a um exemplo pode ser um nó interno (não folha) da hierarquia de classes, a tarefa de classificação é denominada

classificação não obrigatória em nós folhas (Freitas e Carvalho,2007). Nos trabalhos deSun e

Lim(2001) eSun et al.(2003), quando a tarefa de classificação em uma estrutura em árvore é

não obrigatória em nós folhas, a estrutura hierárquica é chamada de árvore virtual. Do mesmo modo, quando a mesma tarefa de classificação é executada em uma estrutura em DAG, essa estrutura é chamadaDAGvirtual.

Problemas hierárquicos podem ser tratados utilizando duas abordagens, chamadas local (ou top-down) e global (ou one-shot). A abordagem global também pode ser encontrada em alguns trabalhos com a denominação de big-bang. Na abordagem local, algoritmos de classificação convencionais são treinados para produzir uma hierarquia de classificadores, que são então apli- cados utilizando uma estratégia top-down para a classificação de novos exemplos. Inicialmente, a classe mais genérica de um novo exemplo é predita. Essa classe, localizada no primeiro ní- vel da hierarquia, é então utilizada para reduzir o conjunto de possíveis classes do próximo nível, que são suas subclasses. Dessa forma, durante a classificação de um exemplo, quando o mesmo é atribuído a uma classe que não é um nó folha, ele é posteriormente classificado em uma subclasse dessa classe. Uma desvantagem dessa abordagem é que, conforme a hierar- quia é percorrida em direção aos nós folhas, erros de classificação cometidos são propagados para os níveis mais profundos, a não ser que algum procedimento seja adotado para evitar esse problema. Por outro lado, a abordagem possui o aspecto positivo da utilização de qualquer algoritmo de classificação convencional nos nós da hierarquia de classes.

O trabalho deSun et al.(2004) apontou outro problema da abordagem local, chamado pro- blema do bloqueio (blocking problem). Esse problema acontece quando, em um determinado momento da classificação top-down, um exemplo não é classificado em nenhum nó interno da hierarquia, o que faz com que ele deixe de ser classificado em classes mais específicas. Esse é um dos motivos que podem fazer com que os classificadores baseados na abordagem local obtenham baixas taxas de acerto nas classes mais profundas da hierarquia.

De acordo comSilla e Freitas(2010), o aspecto mais importante da abordagem local é que a hierarquia de classes é levada em consideração por meio da utilização de informações locais, e que essas informações podem ser utilizadas de diferentes maneiras. Assim, parecem existir três principais diferentes grupos de classificadores baseados na abordagem local, caracterizados pela maneira como as informações locais são utilizadas e pela maneira como os classificadores são induzidos: um classificador local por nó, um classificador local por nó pai, e um classificador lo- cal por nível. No primeiro grupo, um classificador binário é treinado para cada nó da hierarquia de classes, exceto para o nó raiz. A abordagem que utiliza um classificador por nó pai treina um classificador multiclasse para cada nó interno da hierarquia, ou então utiliza algum método decomposicional com classificadores binários, como o Um-Contra-Todos ou Support Vector Machines(SVM) (Vapnik,1999) binários, com a finalidade de fazer a distinção entre suas sub- classes. Já o último grupo treina um classificador multiclasse para cada nível da hierarquia, sendo cada classificador responsável pelas predições das classes de seu nível correspondente.

Na abordagem global, ao contrário da abordagem local, um único classificador é induzido utilizando toda a hierarquia de classes de uma única vez. Após o treinamento do classificador,

a classificação de um novo exemplo ocorre em apenas um passo. Como métodos baseados na abordagem global precisam considerar as peculiaridades do problema de classificação, algorit- mos de classificação convencionais não podem ser utilizados, a não ser que sejam adaptados para considerar toda a hierarquia de classes. Como resultado, esses métodos geralmente pos- suem uma maior complexidade de implementação, mas evitam o problema de propagação de erros da abordagem local. Adicionalmente, se a abordagem global for utilizada para gerar regras de classificação, o conjunto de regras globais gerado tende a ser menos complexo (possuindo menos regras) do que a coleção de todos os conjuntos de regras locais gerados pelos classifica- dores utilizados na abordagem local (Vens et al.,2008;Alves et al.,2010;Otero et al.,2010).

Diferentemente da abordagem local, classificadores baseados na abordagem global não con- seguem utilizar informações locais durante a classificação de novos exemplos. Como as carac- terísticas utilizadas para classificar um exemplo em classes próximas à raiz são diferentes das características utilizadas para classificar o mesmo exemplo em classes mais profundas, geral- mente um classificador baseado na abordagem global tem dificuldades na exploração de dife- rentes conjuntos de características em diferentes níveis hierárquicos (Sun e Lim,2001).

A Figura 3.1 ilustra exemplos de dois problemas de classificação de artigos científicos, sendo um deles hierarquicamente estruturado como uma árvore e o outro hierarquicamente es- truturado como umDAG. A principal diferença entre o problema estruturado como uma árvore (Figura3.1(a)) e o problema estruturado como umDAG(Figura3.1(b)) é que, na estrutura em árvore, cada nó, exceto o nó raiz, possui exatamente um nó pai, enquanto que na estrutura em

DAG, cada nó pode possuir mais de um nó pai. Consequentemente, em problemas estrutura- dos como árvores, cada classe possui uma única profundidade, porque há apenas um possível caminho entre o nó raiz e qualquer outro nó da hierarquia. Diferentemente, em problemas es- truturados comoDAGs, a profundidade de uma classe não é mais única, pois pode haver mais de um caminho entre o nó raiz e qualquer nó da hierarquia. Essas características devem ser consideradas durante o desenvolvimento e avaliação de classificadores hierárquicos.

Todas as Classes (a) (b) Medicina Cardiologia Biomedicina Bioinformática

Biologia _ComputaçãoCiência da

Inteligência Artificial Redes de Computadores Matemática Microbiologia Biologia Molecular Todas as Classes Medicina Cardiologia Biomedicina Bioinformática

Biologia _ComputaçãoCiência da

Inteligência Artificial Redes de Computadores Matemática Microbiologia Biologia Molecular

Figura 3.1: Problemas de classificação de artigos científicos: (a) hierarquia estruturada como uma árvore; (b) hierarquia estruturada como umDAG.

De maneira geral, uma hierarquia estruturada como umDAGpode ser interpretada de duas maneiras. A primeira considera que se um exemplo é atribuído a uma classe cj, ele consequen-

um exemplo é atribuído a uma classe cj, ele deve ser atribuído a pelo menos uma subclasse da

classe cj. Intuitivamente, a primeira interpretação parece mais correta, já que respeita estrita-

mente a hierarquia de classes. Adicionalmente, essa é a interpretação correta para a hierarquia de classes da Gene Ontology (GO).

Em ambas as estruturas hierárquicas em árvore ou DAG, a tarefa de predição de classes associadas aos nós mais profundos da hierarquia geralmente apresenta baixas taxas de acerto. Isso ocorre porque essas classes geralmente possuem poucos exemplos positivos, o que dificulta a tarefa de aprendizado dos classificadores. Essas classes também trazem informações mais específicas sobre os exemplos atribuídos a elas.