João Gabriel Camacho Presotto Métodos de Aprendizado de Máquina Fracamente Supervisionados Baseados em Ranqueamento Rio Claro - SP 2021 João Gabriel Camacho Presotto Métodos de Aprendizado de Máquina Fracamente Supervisionados Baseados em Ranqueamento Dissertação de Mestrado apresentada ao Ins- tituto de Geociências e Ciências Exatas do Câmpus de Rio Claro, da Universidade Es- tadual Paulista “Júlio de Mesquita Filho”, como parte dos requisitos para obtenção do título de Mestre em Ciência da Computação. Financiadora: FAPESP - Proc. 2019/04754-6 Orientador: Prof. Dr. Daniel Carlos Guima- rães Pedronette Rio Claro - SP 2021 P934m Presotto, João Gabriel Camacho Métodos de aprendizado de máquina fracamente supervisionados baseados em ranqueamento / João Gabriel Camacho Presotto. -- Rio Claro, 2021 85 p. : il., tabs. Dissertação (mestrado) - Universidade Estadual Paulista (Unesp), Instituto de Geociências e Ciências Exatas, Rio Claro Orientador: Daniel Carlos Guimarães Pedronette 1. Ciência da Computação. 2. Recuperação de Imagens por Conteúdo. 3. Aprendizado de Máquina. 4. Aprendizado Fracamente Supervisionado. 5. Modelo de Ranqueamento. I. Título. Sistema de geração automática de fichas catalográficas da Unesp. Biblioteca do Instituto de Geociências e Ciências Exatas, Rio Claro. Dados fornecidos pelo autor(a). Essa ficha não pode ser modificada. João Gabriel Camacho Presotto Métodos de Aprendizado de Máquina Fracamente Supervisionados Baseados em Ranqueamento Dissertação de Mestrado apresentada ao Ins- tituto de Geociências e Ciências Exatas do Câmpus de Rio Claro, da Universidade Es- tadual Paulista “Júlio de Mesquita Filho”, como parte dos requisitos para obtenção do título de Mestre em Ciência da Computação. Financiadora: FAPESP - Proc. 2019/04754-6 Comissão Examinadora • Prof. Dr. Daniel Carlos Guimarães Pedronette (Orientador) Departamento de Estatística, Matemática Aplicada e Computação Universidade Estadual Paulista - UNESP • Prof. Dr. Moacir Antonelli Ponti Instituto de Ciências Matemáticas e de Computação Universidade de São Paulo - USP • Prof. Dr. Fabricio Aparecido Breve Departamento de Estatística, Matemática Aplicada e Computação Universidade Estadual Paulista - UNESP Resultado: Aprovado Rio Claro - SP 27 de Agosto de 2021 Agradecimentos Aos meus pais e irmã pelo apoio e todo o suporte. Ao meu orientador pelos anos de parceria desde minha graduação. Agradeço à FAPESP pela concessão da bolsa de pesquisa, sob o processo nº 2019/04754-6, Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP). Resumo Apesar dos impressionantes avanços recentes nas técnicas de aprendizado de máquina, principalmente na compreensão de dados multimídia, desafios significativos ainda persistem. Um dos principais desafios em cenários reais apresenta-se na escassa disponibilidade de dados rotulados. Nesse contexto, desenvolver métodos capazes de explorar as informações presentes em dados não rotulados de modo a mitigar os problemas associados à insuficiência de dados rotulados é um desafio de suma importância. Métodos de aprendizado fracamente supervisionado conseguem lidar com tais restrições ao trabalhar com rótulos estimados ou aproximados como maneira de potencializar informações úteis de treinamento. Nessa linha de pesquisa, apresentaremos dois métodos de aprendizado fracamente supervisionado capazes de analisar as relações entre os dados rotulados e não rotulados, de modo a expandir pequenos conjuntos de treinamento rotulados. Ambos recorrem a um modelo de ranqueamento e utilizam diferentes estratégias para analisar as informações de similaridade codificadas nos dados não rotulados e identificar fortes relações de similaridade com os dados rotulados. Tais relações são consideradas durante a etapa de expansão do conjunto de treinamento. Os métodos foram avaliados em conjunto com diferentes classificadores supervisionados e semi-supervisionados, incluindo uma recente rede convolucional baseada em grafos. Foram considerados cinco diferentes coleções de imagens públicas e os vetores de características de cada imagem foram obtidos através de diferentes descritores visuais. Ganhos positivos de acurácia foram obtidos por ambos os métodos nos mais diferentes cenários quando comparados aos classificadores treinados sem o auxílio de nossos métodos e a técnicas de expansão similares, evidenciando a robustez das abordagens propostas. Palavras-chave: Aprendizado de Máquina, Aprendizado Fracamente Supervisionado, Aprendizado Semi-Supervisionado, Classificação, Hipergrafos, Modelo de Ranqueamento, Métricas de Correlação de Listas Ranqueadas, Recuperação de Imagens Baseada em Conteúdo Abstract Despite the impressive recent advances in machine learning techniques, especially in multimedia data understanding, significant challenges remain. One of the main challenges in real-world scenarios is the limited availability of labeled data. In this context, developing methods capable of exploiting the information encoded in the unlabeled data to mitigate the problems associated with insufficient labeled data, and to overcome this issue is something of paramount importance. Weakly supervised learning methods are capable to handle such restrictions by working with estimated or approximate labels as a way to maximize useful training information. In this line of research, we will present two weakly supervised methods that can analyze the relationships between labeled and unlabeled data to expand small labeled training sets. Both use a ranking model and different strategies to examine similarity information encoded in the unlabeled data to identify strong similarity relationships with the labeled data. Such relations will be considered during the training set expansion step. The methods were evaluated in conjunction with different supervised and semi-supervised classifiers, including a recent graph convolutional network. Five different public image datasets were considered with different visual descriptors. Positive accuracy gains were achieved by both methods in the different scenarios when compared to classifiers trained without the aid of our methods and compared to similar expansion techniques, evidencing the strength of both. Keywords: Classification, Content-based Image Retrieval, Hipergraphs Machine Learning, Rank Correlation Measures, Ranking, Semi-Supervised Learning, Weakly Supervised Learning Lista de ilustrações Figura 1 – Arquitetura típica de recuperação de imagens baseada em conteúdo. . . 19 Figura 2 – Ilustração do processo de construção das listas ranqueadas a partir do cálculo de similaridade entre as amostras. . . . . . . . . . . . . . . . . 20 Figura 3 – Exemplificação de como dados não rotulados podem ajudar no processo de classificação. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Figura 4 – Diferença entre a implementação dos pseudo-rótulos e dos “meta” pseudo-rótulos apresentada em [1]. . . . . . . . . . . . . . . . . . . . . 26 Figura 5 – Diagrama de funcionamento do método de aprendizado fracamente supervisionado baseado em correlações. . . . . . . . . . . . . . . . . . . 30 Figura 6 – Ilustração do método de expansão de conjuntos rotulados baseado em correlações de listas ranqueadas. . . . . . . . . . . . . . . . . . . . . . . 35 Figura 7 – Diferentes conjuntos gerados pela análise de uma métrica de correlação considerando diferentes limiares. . . . . . . . . . . . . . . . . . . . . . . 36 Figura 8 – Método proposto para definição automática do limiar de expansão. . . 36 Figura 9 – Valores de correlação segundo a posição na lista ranqueada τ0. . . . . . 37 Figura 10 – Interpolação por spline linear sL(a) feita sobre os valores de correlação do vetor ci. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Figura 11 – Derivadas da spline linear sL(a) e as médias móveis desses valores considerando um tamanho de janela m = 2. . . . . . . . . . . . . . . . 39 Figura 12 – Médias móveis mai dos valores de derivada da spline linear sL, as diferenças entre valores consecutivos e o valor mínimo dessas diferenças. 40 Figura 13 – Diagrama de funcionamento do método de aprendizado fracamente supervisionado baseado em hipergrafos. . . . . . . . . . . . . . . . . . . 42 Figura 14 – Criação das hiperarestas e atribuição dos pesos. . . . . . . . . . . . . . 44 Figura 15 – Hipergrafo construído pelo método LHRR com os vértices {v1, v2, v3, v4} e as hiperarestas {e1, e2, e3, e4} . . . . . . . . . . . . . . . . . . . . . . 45 Figura 16 – Ilustração do método de expansão de conjuntos rotulados baseado em hipergrafos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 Figura 17 – Exemplo do protocolo de validação cruzada considerado nos experimen- tos, com pequenos conjuntos de treinamento. . . . . . . . . . . . . . . . 53 Figura 18 – Exemplos de imagens do conjunto de dados MPEG-7. . . . . . . . . . . 53 Figura 19 – Exemplos de imagens do conjunto de dados Flowers. . . . . . . . . . . 54 Figura 20 – Exemplos de imagens do conjunto de dados Corel5k. . . . . . . . . . . 54 Figura 21 – Exemplos de imagens do conjunto de dados MNIST. . . . . . . . . . . 54 Figura 22 – Exemplos de imagens do conjunto de dados CUB-200-2011. . . . . . . . 54 Figura 23 – Avaliação do tamanho de vizinhança considerando o classificador OPF. 59 Figura 24 – Avaliação do tamanho de vizinhança considerando o classificador SVM. 59 Figura 25 – Avaliação do tamanho de vizinhança considerando o classificador kNN. 60 Figura 26 – Visualização em duas dimensões da coleção Flowers através do método UMAP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Figura 27 – Visualização em duas dimensões da expansão realizada pela métrica Jaccardk. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Figura 28 – Visualização em duas dimensões da expansão realizada pela métrica Jaccard com as listas re-ranqueadas pelo método LHRR. . . . . . . . . 73 Figura 29 – Visualização em duas dimensões da expansão realizada pela métrica Kendallτ com as listas re-ranqueadas pelo método BFS-Tree. . . . . . . 74 Figura 30 – Visualização em duas dimensões da expansão realizada pelo método baseado em hipergrafos se utilizando de ke = 18. . . . . . . . . . . . . . 75 Figura 31 – Visualização em duas dimensões da expansão realizada pelo método baseado em hipergrafos se utilizando de ke = 80. . . . . . . . . . . . . . 75 Lista de tabelas Tabela 1 – Melhores tamanhos de vizinhança k obtidos para cada combinação de coleção de imagens e descritor. . . . . . . . . . . . . . . . . . . . . . . 60 Tabela 2 – Acurácia (%) obtida pelo classificador OPF considerando o método de expansão baseado em correlações. . . . . . . . . . . . . . . . . . . . . . 62 Tabela 3 – Acurácia (%) obtida pelo classificador SVM considerando o método de expansão baseado em correlações. . . . . . . . . . . . . . . . . . . . . . 63 Tabela 4 – Acurácia (%) obtida pelo classificador kNN considerando o método de expansão baseado em correlações. . . . . . . . . . . . . . . . . . . . . . 64 Tabela 5 – Acurácia (%) obtida pelo classificador SGC considerando o método de expansão baseado em correlações. . . . . . . . . . . . . . . . . . . . . . 65 Tabela 6 – Acurácia (%) obtida pelos classificadores kNN, OPF, SVM e SGC considerando o método de expansão baseado em hipergrafos. . . . . . . 68 Tabela 7 – Acurácia (%) obtida com classificadores supervisionados, semi-super- visionados e os melhores resultados obtidos por ambos os métodos de expansão. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 Lista de símbolos α taxa de expansão de rótulos utilizada na expansão baseada em hiper- grafos. ci ranque de correlações. C matriz de produtos cartesianos dos elementos do hipergrafo. H matriz de incidências do hipergrafo. HT matriz de incidências transposta do hipergrafo. S matriz de similaridade do hipergrafo. W matriz de similaridade ou afinidade final do hipergrafo. Cp conjunto de pares de candidatos utilizados na expansão baseada em hipergrafos. D descritor visual. N (q, k) conjunto dos primeiros k vizinhos de um determinado item de dados xq. Nc(xl, ke) conjunto de candidatos não rotulados utilizado na expansão baseada em hipergrafos. Nh conjunto de vizinhança do hipergrafo. T conjunto de listas ranqueadas obtido a partir das listas de cada item de dados em X. T conjunto de listas ranqueadas. L conjunto de rótulos para cada item de dados. X coleção de dados. XE conjunto rotulado estimado. XL conjunto rotulado. XU conjunto não rotulado. XW conjunto rotulado expandido. ρ(vxi , vxj ) distância entre os vetores de características de dois itens de dados xi e xj. τC ranque de pares de candidatos utilizados na expansão baseada em hipergrafos. τq lista ranqueada do item de índice q. E(xe) função de estimativa de rótulos. G hipergrafo com V vértices e E hiperarestas. l comprimento da lista ranqueada. r(·, ·) métrica de correlação entre listas ranqueadas. sL(a) spline linear de interpolação. tp limiar de posição (ou posição limite) utilizado na expansão baseada em hipergrafos. th limiar de correlação. vxi vetor de características de um item de dados xi. w(ei) peso da hiperaresta ei. xq item de dados de índice q. Y (xi) função que associa o item de dados xi com seu rótulo correspondente. Sumário 1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2 ASPECTOS TEÓRICOS E TRABALHOS RELACIONADOS . . . . 18 2.1 Recuperação de Imagens Baseada em Conteúdo . . . . . . . . . . . 18 2.2 Modelo de Ranqueamento . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 Aprendizado de Máquina . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3.1 Aprendizado Supervisionado e Não Supervisionado . . . . . . . . . . . . . 21 2.3.2 Aprendizado Semi-Supervisionado . . . . . . . . . . . . . . . . . . . . . . 22 2.4 Aprendizado Fracamente Supervisionado . . . . . . . . . . . . . . . . 24 2.4.1 Definição Formal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.4.2 Abordagens Recentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3 APRENDIZADO FRACAMENTE SUPERVISIONADO BASEADO EM CORRELAÇÕES . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.1 Aprendizado de Variedades (Manifold Learning) . . . . . . . . . . . . 30 3.2 Métricas de Correlação de Listas Ranqueadas . . . . . . . . . . . . . 32 3.3 Expansão de Conjuntos Rotulados por Correlações . . . . . . . . . . 33 3.4 Definição do Limiar de Correlação . . . . . . . . . . . . . . . . . . . . 35 4 APRENDIZADO FRACAMENTE SUPERVISIONADO BASEADO EM HIPERGRAFOS . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.1 Construção do Hipergrafo . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.2 Expansão de Conjuntos Rotulados por Hipergrafos . . . . . . . . . . 47 4.3 Definição da Taxa de Expansão de Rótulos . . . . . . . . . . . . . . . 49 5 AVALIAÇÃO EXPERIMENTAL . . . . . . . . . . . . . . . . . . . . . 52 5.1 Protocolo Experimental . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.2 Coleções de Imagens e Descritores . . . . . . . . . . . . . . . . . . . 52 5.3 Classificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 5.3.1 Métodos Supervisionados . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 5.3.2 Métodos Semi-Supervisionados . . . . . . . . . . . . . . . . . . . . . . . . 56 5.4 Método de Expansão por Correlações . . . . . . . . . . . . . . . . . . 57 5.4.1 Definição do Tamanho de Vizinhança . . . . . . . . . . . . . . . . . . . . 57 5.4.2 Resultados de Classificação . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.5 Método de Expansão por Hipergrafos . . . . . . . . . . . . . . . . . . 66 5.5.1 Resultados de Classificação . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.6 Comparação entre os Métodos Propostos e Outras Abordagens . . 68 5.7 Análise Visual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 6 CONCLUSÕES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 14 1 Introdução Atualmente uma grande e crescente quantidade de conteúdo digital multimídia está disponível em diversas aplicações e domínios. Em um cenário em que usuários comuns evoluíram de meros consumidores para produtores ativos dessa categoria de conteúdo, um volume expressivo de imagens e vídeos tem sido gerados diariamente [2]. Por conta disso, tarefas para compreensão de imagens se tornaram um tópico de grande interesse, tanto no meio acadêmico quanto na indústria [3]. Diversos avanços tem sido realizados e técnicas de aprendizado de máquina modernas podem atualmente igualar o desempenho humano em tarefas como classificação de imagens [4]. Mesmo com o desenvolvimento substancial nesse domínio, que contribuiu em diversas aplicações como classificação e recuperação de imagens e vídeos, ainda existem desafios relevantes a serem explorados. De fato, grande parte dos resultados positivos tem sido obtidos a custo de grandes quantidades de dados de treinamento anotados ou rotulados [4]. Redes neurais convolucionais (Convolutional Neural Networks (CNNs)) são uma das principais técnicas que apresentam um expressivo sucesso, em especial em tarefas de aprendizado supervisionado aplicadas a visão computacional, mas que dependem de grandes quantidades de dados de treinamento [5]. Entretanto, obter grandes conjuntos de amostras de treinamento confiáveis é uma tarefa muito custosa. Considerando dados de vídeo, por exemplo, apesar da quantidade teoricamente ilimitada de vídeos disponíveis na rede, categorizar e processar esses vídeos de modo a criar um conjunto de dados útil é uma tarefa difícil e suscetível a erros, já que os rótulos associados a essa categoria de mídia retiradas de redes sociais são muitas vezes ruidosos [3]. Visto que rotular dados multimídia é normalmente custoso, demorado e suscetível a erros, muitos esforços têm sido feitos para contornar este problema [6]. O aprendizado fracamente supervisionado é uma área ativa de pesquisa [7, 8, 9, 10], que visa enfrentar desafios relacionados a disponibilidade de dados de treinamento. Seja trabalhar com rótulos não ideais, com rótulos que definem uma imagem na totalidade (image-level labels) ao invés de anotações de cada objeto pertencente a imagem (object- level labels) [7, 8, 9] ou com rótulos possivelmente ruidosos obtidos a partir de redes sociais [11], o aprendizado fracamente supervisionado representa uma série de métodos capazes de lidar com um nível de supervisão em que a informação de rótulos disponível é uma estimativa ou aproximação se comparado aos ideais, mas que ainda conseguem obter resultados expressivos. Essa categoria de métodos em diversas situações consideram tanto os dados rotulados quanto os dados não rotulados, podendo ser também caracterizados como métodos semi-supervisionados. Deste modo, este trabalho discute métodos capazes de estimar rótulos de elementos não rotulados a partir de suas relações com os elementos Capítulo 1. Introdução 15 rotulados em cenários onde o conjunto de dados possui escassez de amostras rotuladas e amostras não rotuladas em abundância. Em tarefas de classificação, obter resultados de acurácia positivos quando apenas pequenos conjuntos rotulados estão disponíveis é uma tarefa desafiadora que vem sendo investigada por décadas [12, 13, 14, 15]. Métodos de aprendizado semi-supervisionado, os quais tentam explorar de maneira efetiva os dados rotulados e não rotulados, são um tópico amplamente estudado [6, 13, 14, 15]. Muitos desses métodos semi-supervisionados exploram os dados não rotulados para aprimorar a acurácia do modelo, conseguindo produzir resultados relevantes em diversas tarefas, incluindo classificação de imagens [16, 17]. Nos últimos anos, essa área de pesquisa tem atraído bastante atenção [6, 16, 3, 2, 18], principalmente por conta do crescimento expressivo de coleções multimídia e a consequente dificuldade de rotular esses dados, grandes conjuntos de treinamento necessários às CNNs e aos recentes avanços em técnicas não supervisionadas [19, 20]. Dado o contexto, que destaca a relevância de abordagens capazes de trabalhar com escassez de dados rotulados, o objetivo do trabalho é investigar abordagens fracamente supervisionadas, em especial considerando os avanços em estratégias não supervisionadas baseadas em ranqueamento [19, 20, 4] e como tais abordagens poderiam ser exploradas em cenários próximos. Foi realizado um levantamento da literatura e feita uma investigação sobre novos métodos dessa categoria. Dessa forma, as principais contribuições desse trabalho consistem na proposta de dois métodos de aprendizado fracamente supervisionado aplicados a cenários em que apenas pequenos conjuntos rotulados estão disponíveis. Ambos recorrem a um modelo de ranqueamento e diferentes técnicas para expandir os conjuntos rotulados. Modelos de ranqueamento (ou de listas ranqueadas) permitem representar informações de similaridade entre elementos, as quais podem ser exploradas para atribuir rótulos estimados aos elementos não rotulados. Estes que têm sido explorados com sucesso por algoritmos de aprendizado de variedades (manifold learning) em cenários de recuperação não supervisionada [19, 20]. Estatísticas de ranques (rank statistics) [4] têm sido também utilizadas para descobrir novas classes em um conjunto de dados a partir de elementos rotulados de outras classes. O primeiro método, analisa informações de similaridade entre elementos rotulados e não rotulados através da análise de métricas de correlação de listas ranqueadas [21], capazes de atribuir um valor real a relação entre as listas ranqueadas de duas imagens. As informações de similaridade entre amostras são representadas através de um modelo de listas ranqueadas e estas são processadas por recentes métodos de aprendizado de variedades [19, 20] (métodos de re-ranqueamento). Tais algoritmos conseguem calcular medidas de similaridade globais considerando informações contextuais implícitas entre as amostras. Como resultado, é possível aprimorar a eficácia das listas ranqueadas (mais elementos da mesma classe a imagem de consulta nas primeiras posições), o que por Capítulo 1. Introdução 16 consequência resultará em cálculos de correlação mais eficazes. Com base nas listas ranqueadas mais eficazes, métricas de correlação de listas ranqueadas são exploradas com o intuito de identificar fortes relações de similaridade entre imagens. É possível atribuir classes aos dados não rotulados com base em tal informação, expandindo o conjunto de treinamento rotulado. Uma abordagem adaptativa capaz de definir automaticamente o limiar de correlação também é proposta. Limiar utilizado para selecionar quais amostras não rotuladas vão fazer parte do conjunto rotulado expandido. Este método é uma extensão do trabalho realizado em [22], inovando em diversos aspectos, incluindo o uso de métodos de re-ranqueamento e a seleção automática do limiar de correlação utilizado na etapa de expansão de rótulos. O segundo método de aprendizado fracamente supervisionado proposto e que é apre- sentado ao longo do trabalho explora informações codificadas no modelo de ranqueamento através de uma estrutura de hipergrafo construído por um algoritmo não supervisionado de aprendizado de variedades (manifold learning) baseado em ranqueamento [19]. Hipergrafos são uma poderosa generalização de grafos. Enquanto as arestas em grafos representam ligações entre pares de vértices, hiperarestas permitem representar relações entre conjuntos de elementos. As estruturas do hipergrafo construído a partir das informações dos ranques são então utilizadas para identificar e selecionar relações de similaridade sólidas entre amostras rotuladas e não rotuladas e tais relações são exploradas de modo a construir um conjunto rotulado expandido. O conjunto rotulado expandido gerado por ambos os métodos de aprendizado fracamente supervisionado pode ser utilizado tanto por classificadores supervisionados como para classificadores semi-supervisionados obtendo ganhos expressivos em termos da acurácia final, mesmo começando com poucas amostras rotuladas, se comparados com o treinamento sem utilizar dos métodos de expansão. Considerando métodos que tentam aprimorar tarefas de classificação [15, 23], ambos os métodos apresentados ao longo do texto não dependem de um único classificador, pois apresentam uma formulação flexível que pode ser utilizada em conjunto com diferentes classificadores. De forma análoga, outros métodos exploram pseudo-rótulos [24, 25, 1, 26, 27] como uma estratégia de aumentar a quantidade de dados rotulados através de redes neurais. Novamente, os métodos propostos são uma alternativa mais versátil, pois independem de um modelo como as redes neurais para gerar mais amostrar rotuladas. Uma ampla avaliação experimental foi conduzida com o intuito de avaliar ambos os métodos nos mais diferentes cenários. Foram consideradas cinco coleções de imagens públicas e diferentes descritores visuais, incluindo um descritor baseado em CNNs pré treinado em cenários de aprendizado de transferência (transfer learning). O método baseado em correlações entre listas ranqueadas foi avaliado considerando cinco métricas de correlação. A estratégia de expansão de conjuntos rotulados foi avaliada em conjunto com Capítulo 1. Introdução 17 diferentes classificadores supervisionados e semi-supervisionados, incluindo uma recente rede convolucional de grafos (Graph Convolutional Network (GCN)). Todos os experimentos foram conduzidos em um cenário de aprendizado fracamente supervisionado, considerando conjuntos de treinamento rotulados de tamanho limitado. Os resultados experimentais de ambos os métodos demonstram ganhos de acurácia significativos quando comparados ao treinamento dos classificadores sem os métodos de expansão e em comparação com métodos análogos da literatura. O restante do trabalho está dividido da seguinte maneira. O Capítulo 2 define os aspectos teóricos fundamentais e os trabalhos relacionados ao contexto do trabalho. O Capítulo 3 apresenta o método de aprendizado fracamente supervisionado baseado em correlações. O Capítulo 4 descreve o método de aprendizado fracamente supervisionado baseado em hipergrafos. O Capítulo 5 descreve a avaliação experimental realizada para avaliar ambos os métodos propostos. Por fim, o Capítulo 6 discute as conclusões obtidas ao longo do trabalho, as publicações que ambos os métodos originaram e possíveis trabalhos futuros. 18 2 Aspectos Teóricos e Trabalhos Relaciona- dos Este capítulo discute os principais aspectos teóricos e trabalhos relacionados aos métodos de aprendizado fracamente supervisionado baseados em ranqueamento que são apresentados ao longo do texto. Na Seção 2.1 são apresentados os principais conceitos da recuperação de imagens baseada em conteúdo, e quais aspectos desta categoria de métodos estão relacionados ao trabalho. Na Seção 2.2 é apresentada uma definição formal do modelo de ranqueamento que é utilizado como principal fonte de informações de ambos os métodos de aprendizado fracamente supervisionado propostos. A Seção 2.3 apresenta o conceito de aprendizado de máquina e suas categorias que se relacionam com o trabalho. Por fim, a Seção 2.4 discute a origem do termo aprendizado fracamente supervisionado e apresenta a uma definição formal do mesmo além de discutir algumas abordagens recentes que apresentam um funcionamento similar aos métodos apresentados nos próximos capítulos. 2.1 Recuperação de Imagens Baseada em Conteúdo Devido ao grande crescimento das coleções de imagens, é cada vez mais necessário encontrar maneiras eficazes e eficientes para realizar a busca e indexação dessa categoria de dados [28]. Os primeiros sistemas de recuperação de imagens realizavam buscas conside- rando palavras-chave e metadados [29], porém, essa metodologia é bastante limitada, pois ignora o conteúdo visual disponível e pode produzir resultados de buscas ambíguos. Como solução a essa situação surge a recuperação de imagens baseada em conteúdo (CBIR - Content-Based Image Retrieval) [28]. A recuperação de imagens baseada em conteúdo pode ser definida como qualquer tecnologia que ajude a organizar arquivos de imagens por seu conteúdo visual, e por essa definição, qualquer aplicação desde uma função de similaridade entre imagens até um robusto mecanismo de anotação se enquadram no âmbito de CBIR [28]. O principal objetivo da recuperação baseada em conteúdo é encontrar imagens similares, e com este objetivo são utilizados os descritores visuais, capazes de representar as imagens como vetores numéricos de características. Com os vetores de características gerados é possível então comparar as imagens através de uma função de distância, como a distância Euclidiana (a mais utilizada [30]), e dessas comparações uma lista ranqueada em ordem crescente de distâncias é gerada. Para extração de características das imagens, os descritores visuais podem utilizar de diferentes estratégias como analisar a cor, a forma, a textura das imagens [31, 32] ou até se utilizar de aprendizado profundo, principalmente as redes Capítulo 2. Aspectos Teóricos e Trabalhos Relacionados 19 neurais convolucionais. A Figura 1 apresenta a implementação clássica de recuperação de imagens baseada em conteúdo. Esta pode ser dividida em três partes: (i) a interface, (ii) o módulo de processamento da consulta e (iii) a base de dados. A interface é responsável pela interação com o usuário, com a inserção e saída dos dados. O módulo de processamento da consulta tem como tarefa extrair as características das imagens e fazer as operações necessárias de modo a compará-las. Por fim, a base de dados armazena as imagens e seus respectivos vetores de características, de modo a evitar a recalculá-los. Estão destacadas em vermelho as etapas relacionadas que são utilizadas durante a execução de nosso trabalho, onde o principal componente que dita o funcionamento dos métodos de aprendizado fracamente supervisionados propostos são as listas ranqueadas, geradas a partir do cálculo de distâncias entre os vetores de características das amostras. Figura 1 – Arquitetura típica de recuperação de imagens baseada em conteúdo. Coleção de Imagens (Database) Inserção de Dados Especificação da Consulta Visualização Interface Extração do Vetor de Características Cálculo das Similaridades Listas Ranqueadas Módulo de Processamento da Consulta Padrão de Consulta Imagens Similares Imagens Vetores de Características Extração do Vetor de Características Cálculo das Similaridades Fonte: Adaptado de [33]. 2.2 Modelo de Ranqueamento Os métodos apresentados ao longo desse trabalho se utilizam de um modelo de ranqueamento, definido a partir de uma coleção de dados X. Cada item de dados xi ∈ X Capítulo 2. Aspectos Teóricos e Trabalhos Relacionados 20 pode ser representado em um espaço de d dimensões por um vetor de características vxi , obtido a partir de um descritor D, que pode ser definido como uma tupla (ε, ρ) [34], onde ε: {xi} → Rd é uma função que extrai o vetor de características vxi e ρ: Rd × Rd → R+ é uma função que calcula a distância entre dois itens de dados a partir de seus vetores de características. Sendo assim, a distância entre dois itens de dados xi e xj pode ser obtida por ρ(vxi , vxj ). Para cada item de dados xq, uma lista ranqueada τq pode ser calculada a partir da função de distâncias ρ, que contêm os itens de dados da coleção X mais similares a xq. Formalmente, a lista ranqueada τq=(x1, x2, . . . , xl) pode ser definida como uma permutação da coleção Xl, onde l representa o comprimento das listas ranqueadas e Xl ⊂ X é um subconjunto que contêm os l itens de dados mais similares a xq. A posição de xi na lista ranqueada τq é indicada por τq(xi). Portanto, podemos dizer se xi está em uma posição anterior a xj na lista ranqueada de xq, então τq(i) < τq(j) e ρ(vq, vi) ≤ ρ(vq, vj). A Figura 2 ilustra o processo de construção de uma lista ranqueada τq a partir dos valores de distância ρ(·, ·) entre os vetores de características dos itens de dados. Figura 2 – Ilustração do processo de construção das listas ranqueadas a partir do cálculo de similaridade entre as amostras. Imagem de Consulta Distâncias entre os vetores de características Lista Ranqueada Fonte: Elaborado pelo autor. É possível calcular uma lista ranqueada τi para cada item de dados xi ∈ X de modo a obter um conjunto de listas ranqueadas T = {τ1, τ2, . . . , τN}. O conjunto T representa uma rica fonte de informações que é explorada ao longo desse trabalho. 2.3 Aprendizado de Máquina O aprendizado de máquina é uma área que envolve uma série de algoritmos capazes de realizar tarefas sem serem diretamente programados e de se adaptar a diferentes circunstâncias. Algoritmos de aprendizado de máquina funcionam de modo a analisar um determinado conjunto de dados e extrair padrões e informações, tomando decisões Capítulo 2. Aspectos Teóricos e Trabalhos Relacionados 21 baseadas nos dados, sem haver programação explícita para a resolução de uma determinada tarefa [35]. Esta categoria de algoritmo surge para contornar situações em que algoritmos convencionais não conseguem lidar [36], como reconhecer faces em uma fotografia, converter fala em texto escrito, dirigir um carro, tarefas que são naturais aos humanos, mas que não tem uma explicação concreta de como ser feitas. Com os avanços nas tecnologias, é cada vez mais fácil armazenar e processar grandes quantidades de dados, assim como acessá-los de locais distantes através da rede. Nesses cenários, métodos de aprendizado de máquina tem se mostrando bastante relevantes, capazes de detectar certos padrões e regularidades, facilitando o entendimento do contexto em que os dados estão inseridos ou permitindo fazer previsões [36]. Estes que também são capazes de se adaptar aos mais diferentes cenários, sem ser necessário programá-los para toda situação possível [36]. Atualmente, algoritmos de aprendizado de máquina tem sido bastante utilizados nos mais diferentes cenários, com destaque nas áreas de reconhecimento de padrões e visão computacional [37, 38, 39, 40]. Considerando os métodos de aprendizado de máquina relevantes ao nosso trabalho, é possível destacar três categorias: aprendizado supervisionado, aprendizado não supervisi- onado e aprendizado semi-supervisionado. Tais categorias são discutidas em mais detalhes a seguir. 2.3.1 Aprendizado Supervisionado e Não Supervisionado Métodos de aprendizado supervisionados são treinados a partir da utilização de dados rotulados e tomam decisões considerando dados não rotulados [35]. Amostras rotuladas possuem informação de classe ou categoria associada, enquanto os dados não rotulados não tem essa informação disponível. A partir de um conjunto de dados rotulados, o objetivo dessa categoria de método é construir um modelo capaz de estimar os rótulos para novas amostras desconhecidas. Um tipo comum de método de aprendizado supervisionado são os classificadores supervisionados, como redes neurais [41] e máquinas de vetores de suporte (SVM - Support Vector Machines) [42], ambos que tentam encontrar um hiperplano que melhor separa os dados considerados relevantes dos não relevantes. Podemos também destacar abordagens baseadas em programação genética [43, 44], grafos [45] e redes neurais profundas [46]. Apesar de populares, os métodos de aprendizado supervisionados não são adequados em todos os cenários. Situação que ocorre por conta da sensibilidade dessa categoria de método aos dados de treinamento, pois se a quantidade de dados rotulados disponível for muito pequena, o modelo pode não obter um nível de generalização adequado. Outro problema que pode ocorrer é o sobreajuste (overfitting), em que o modelo se especializa em somente uma tarefa, não conseguindo classificar adequadamente novos dados [35]. Capítulo 2. Aspectos Teóricos e Trabalhos Relacionados 22 Outra limitação apresentada por modelos supervisionados está relacionada ao tempo de treinamento, pois se a quantidade de dados de treinamento for muito elevada, esse tempo pode ser muito alto, tornando certas tarefas inviáveis. Os métodos de aprendizado não supervisionado não dependem de intervenção do usuário ou de informação de classe das amostras. Por conta disso, essa categoria de método tenta identificar estruturas relevantes a partir do conjunto de dados (normalmente representados como vetores de valores numéricos). Nesse contexto podemos destacar os métodos de agrupamento (clustering), em que as instâncias são separadas em grupos a partir da análise de similaridade entre as amostras [47]. No contexto de recuperação de imagens, algoritmos de aprendizado não supervisionado tem entre os principais objetivos substituir medidas de distâncias par a par por medidas globais e mais eficazes, realizando uma análise da informação do contexto em que as amostras estão inseridas [48]. Dentre as diversas abordagens de aprendizado não supervisionado podemos destacar: processos de difusão [49, 50], grafos [51, 48], agrupamento [52], frequência de padrões [53] e análises de listas ranqueadas [54]. Os métodos de aprendizado não supervisionado baseados em listas ranqueadas (ou modelo de ranqueamento) têm atraído interesse expressivo na literatura [55, 56, 19, 20]. Situação que pode ser justificada pelo baixo custo computacional requerido, pois estes métodos não necessitam das listas ranqueadas calculadas por completo (somente até um tamanho l� |X|), já que os resultados relevantes se concentram nas primeiras posições dos ranques. Dentre métodos baseados em ranqueamento que exploram diferentes estratégias, pode-se destacar: Correlation Graph [57], CPRR [58], Ranked List Graph Distance [59], ReckNNGraph [60], RL-Recom [61] e RL-Sim [54, 62]. 2.3.2 Aprendizado Semi-Supervisionado O aprendizado semi-supervisionado é uma vertente de aprendizado de máquina que tenta combinar as ideias utilizadas tanto no aprendizado supervisionado quanto no aprendizado não supervisionado [13, 63]. A título de exemplo, em um problema de classificação, pontos de dados não rotulados podem ser utilizados para auxiliar no processo de classificação. Tal exemplo é ilustrado na Figura 3, em que é possível prever o rótulo B da amostra com um certo grau de confiança ao observar as amostras não rotuladas em cinza, que formam dois conjuntos distintos. Os métodos de classificação semi- supervisionados se mostram bastante relevantes por conseguirem trabalhar em cenários em que a quantidade de dados rotulados é muito pequena. Em cenários análogos, a tarefa de construir um classificador supervisionado confiável baseado em um número reduzido de amostras rotuladas é uma tarefa muito difícil. Podemos dividir os métodos de aprendizado semi-supervisionados em duas cate- gorias principais: métodos indutivos e transdutivos. Métodos indutivos, assim como os Capítulo 2. Aspectos Teóricos e Trabalhos Relacionados 23 Figura 3 – Exemplificação de como dados não rotulados podem ajudar no processo de classificação. Dado de teste A ou B? Ao observarmos os dados não rotulados (em cinza) A B A B B Fonte: Adaptado de [10], FIG. 3. métodos de aprendizado supervisionados produzem um modelo de classificação capaz de prever rótulos de amostras previamente desconhecidas. Situação similar ao objetivo dos métodos supervisionados [64]: construir um modelo durante a etapa de treinamento e utilizá-lo para prever os rótulos de novas amostras. Os métodos transdutivos não produ- zem um modelo de classificação, mas conseguem fazer previsões dos rótulos diretamente, limitando-se às amostras que encontram durante a processo de treinamento [64]. Por conta disso, se novas amostras forem adicionadas a um conjunto de dados, um modelo transdutivo teria de ser novamente executado para considerar essas novas amostras. Nessa categoria, a informação é diretamente propagada via conexões diretas entre os pontos de dados. Situação que pode ser naturalmente representada por grafos, onde pontos similares são conectados e os rótulos podem ser propagados ao longo das arestas. Na prática, grande parte dos métodos transdutivos são diretamente modelados por grafos ou podem ser implicitamente entendidos como [64]. De maneira geral, métodos semi-supervisionados consideram uma série de hipóteses a respeito da distribuição dos dados em seu funcionamento [13]. Estas que podem são consideradas individualmente ou em conjunto, a depender do método [64]. A primeira das hipóteses, a hipótese da suavidade (smoothness assumption) considera que amostras próximas no espaço de características tem uma alta probabilidade de pertencerem a mesma classe. A hipótese da baixa densidade (low-density assumption) considera que a fronteira de decisão não deve ser colocada em regiões de alta densidade de amostras. Outra hipótese utilizada é de que amostras próximas entre si em uma representação de menor dimensiona- lidade devem possuir o mesmo rótulo (manifold assumption). Considerando o cenário de agrupamento (clustering), podemos também destacar a hipótese de agrupamentos (cluster assumption), em que pontos de dados pertencentes ao mesmo grupo pertencem a mesma classe. Capítulo 2. Aspectos Teóricos e Trabalhos Relacionados 24 2.4 Aprendizado Fracamente Supervisionado O termo aprendizado fracamente supervisionado (weakly supervised learning) é utilizado na literatura para representar diferentes situações. Em [7, 8, 9] o termo é utilizado para representar o uso de rótulos não ideais para suas aplicações, onde são utilizados rótulos que definem a imagem como um todo (image-level labels) ao invés de anotações de cada objeto que compõe as mesmas. O trabalho realizado em [11] apresenta uma diferente abordagem de aprendizado de transferência (transfer learning), em que os modelos são previamente treinados utilizando de bilhões de imagens “rotuladas” por etiquetas (hashtags) em redes sociais. Em termos práticos, essas etiquetas podem conter uma quantidade excessiva de ruído ou até gerar uma distribuição com um certo viés, o que pode prejudicar a tarefa de aprendizado de transferência [11]. Contudo, tal expectativa não se concretizou, e experimentos indicaram que o uso desses rótulos “fracos” se mostrou muito promissor. Além disso, em [10] o termo é definido como uma série de métodos de aprendizado de máquina capazes de trabalhar em cenários de supervisão fraca, em que rótulos completos e verdadeiros (fully ground-truth labels) não estão sempre disponíveis ou obtê-los manualmente tem um custo muito alto. Considerando as situações apresentadas, pode-se destacar como característica comum o desafio de lidar com um nível de supervisão em que os rótulos utilizados não são ideais ou são “fracos”. Cada uma das estratégias utilizam de rótulos que se comparado aos esperados são uma estimativa ou aproximação, mas que mesmo assim conseguem atingir resultados relevantes. No contexto deste trabalho, são apresentados métodos capazes de estimar rótulos de elementos não rotulados a partir das suas relações com os elementos rotulados, criando assim um conjunto rotulado expandido. O uso do termo aprendizado fracamente supervisionado advém do fato de que o conjunto rotulado expandido tem rótulos estimados, que podem ser considerados “fracos”. Sendo assim, o conjunto rotulado expandido ou fracamente rotulado, é composto da união dos rótulos reais, já disponíveis no conjunto de dados inicial, e dos rótulos “fracos”. Ao longo do texto são apresentados dois métodos de aprendizado fracamente supervisionado baseados em ranqueamento. Ambos funcionam a partir da análise da estrutura do conjunto de dados, explorando as informações de similaridade codificadas nas listas ranqueadas. Com diferentes estratégias, mas com a premissa de utilização do modelo de ranqueamento, os métodos tentam estabelecer relações entre os elementos rotulados e os não rotulados, de modo transmitir rótulos ao conjunto não rotulado quando uma forte relação de similaridade for identificada. Dessa forma, os métodos propostos também podem ser vistos como semi-supervisionados, visto que utilizam dados rotulados e não rotulados e são adequados para cenários em que há escassez de dados para treinamento. Capítulo 2. Aspectos Teóricos e Trabalhos Relacionados 25 Ao transmitir (ou expandir) os rótulos dos elementos rotulados aos não rotulados, um conjunto rotulado expandido é gerado. O conjunto expandido é utilizado para o treinamento de classificadores supervisionados ou semi-supervisionados, com o intuito de melhorar a acurácia obtida quando comparados com o treinamento sem a utilização do conjunto expandido. Os métodos apresentados analisam todo o conjunto de dados para criação das estruturas relacionadas e expansão de rótulos. Por conta disso, caso uma nova amostra seja adicionada, é necessário recalcular as listas ranqueadas e o restante das estruturas relacionadas a cada um dos métodos. Situação que representa um método semi-supervisionado transdutivo, em que se realizam previsões dos rótulos diretamente e limitando-se às amostras iniciais. Porém, caso os métodos de expansão sejam utilizados com seu objetivo principal, aprimorar o treinamento e resultados dos classificadores, esses classificadores podem ser utilizados em amostras desconhecidas, caracterizando um cenário indutivo. 2.4.1 Definição Formal Esta seção apresenta uma definição formal do problema considerado. Seja X = {x1, x2, . . . , xL, xL+1, . . . , xN} uma coleção de dados onde cada elemento xi representa um item de dados. A coleção X pode ser definida como uma coleção parcialmente rotulada, i.e., X = XL ∪ XU , onde XL = {xi}L i=1 representa um subconjunto de itens rotulados e XU = {xi}N i=L+1 o subconjunto não rotulado. Normalmente, a quantidade disponível de dados rotulados é muito menor do que a quantidade de dados não rotulados, ou seja, |XL| � |XU |. Podemos também definir formalmente os classificadores utilizados em conjunto com os métodos de expansão. Seja, L = {1, . . . , C} um conjunto que contêm os rótulos do conjunto de dados. Seja Y : X→ L uma função que associa cada item de dados xi ∈ X a seu rótulo correspondente Y (xi). Portanto, a tarefa de classificação realizada pode ser definida como a estimativa da função Y (xi) para cada item não rotulado xi ∈ XU a partir do modelo aprendido. O principal objetivo desse trabalho é aprender um subconjunto dos dados não rotulados que pode ser agregado a um conjunto rotulado expandido a partir de uma estimativa da função Y . Formalmente, seja XE ⊆ XU um conjunto rotulado estimado. O conjunto fracamente rotulado ou expandido XW é definido como XW = XL ∪ XE. Para cada xe ∈ XE, uma função de estimativa E(xe) é utilizada como estimativa da função Y (xe). Posteriormente, o conjunto rotulado expandido XW é utilizado para treinamento dos classificadores. Sendo assim, a questão central que irá ser discutida ao longo do trabalho é como definir o subconjunto XE e a função de estimativa de rótulos E(xe), de modo a permitir bons resultados ao combiná-los com os classificadores. Capítulo 2. Aspectos Teóricos e Trabalhos Relacionados 26 2.4.2 Abordagens Recentes A tentativa de atribuir rótulos aos dados não rotulados de modo a construir um conjunto rotulado expandido é algo amplamente estudado na literatura [65, 66, 1, 26, 27]. As técnicas de auto-rotulagem (self-labeled techniques) [65], uma categoria de classificadores semi-supervisionados, consideraram que suas previsões de rótulos são em maior parte verdadeiras e assim conseguem produzir um conjunto rotulado expandido. Mais recentemente, uma nova categoria de método de auto-rotulagem foi proposto, em [66] o conceito de pseudo-rótulos foi introduzido. O trabalho utiliza de uma rede neural profunda que é treinada utilizando de amostras rotuladas e de amostras pseudo-rotuladas, geradas em cada atualização de pesos da rede, ao analisar a classe que teve a maior probabilidade prevista pelo modelo. O conceito de pseudo-rótulos foi originalmente utilizado através do uso de redes neurais profundas, mas este pode ser utilizado com qualquer rede ou classificador que permita obter para cada amostra informações de probabilidade dessa pertencer a cada amostra. O conceito de pseudo-rótulos tem sido amplamente estudado [1, 26, 27], tentando minimizar cenários em que o método que gera os pseudo-rótulos está mal otimizado, o que pode gerar a treinamentos com amostras ruidosas, prejudicando os resultados. Em [1] o conceito de “meta” pseudo-rótulos é proposto, onde o modelo que gera os rótulos é adaptado conforme o desempenho obtido no conjunto rotulado ao se treinar com os “meta” pseudo-rótulos. A Figura 4 apresenta a diferença entre o conceito de pseudo-rótulos e os “meta” pseudo-rótulos. No primeiro um método previamente treinado gera os dados pseudo-rótulados utilizados para treinar o estudante (student). Já os “meta” pseudo-rótulos o professor (teacher) é treinado em conjunto do estudante, a partir da performance obtida por este no conjunto rotulado. Figura 4 – Diferença entre a implementação dos pseudo-rótulos e dos “meta” pseudo- rótulos apresentada em [1]. Fonte: Retirado de [1], Fig. 1 O trabalho realizado em [26] aprimora o aprendizado por pseudo-rótulos no contexto de segmentação de imagens ao trabalhar também com o grau de incerteza que o modelo tem a respeito das previsões que faz. O método gera esse grau de incerteza a partir da análise da variância da previsão. De maneira similar, em [27] se utiliza do grau de incerteza Capítulo 2. Aspectos Teóricos e Trabalhos Relacionados 27 das previsões para selecionar uma maior quantidade de amostras corretas ao conjunto expandido que é utilizado na etapa de treinamento. Considerando os métodos propostos ao longo do trabalho, esta é a primeira vez na literatura em que modelos de ranqueamento são explorados com o intuito de expandir conjuntos rotulados de treinamento e aprimorar tarefas de classificação. Além disso, ambos os métodos possuem uma formulação flexível, em que a etapa de expansão independe do classificador, permitindo sua combinação com diferentes classificadores nos mais diferentes cenários. 28 3 Aprendizado Fracamente Supervisionado Baseado em Correlações Explorar efetivamente as relações entre os dados rotulados e os dados não-rotulados é um desafio crucial presente nos métodos fracamente supervisionados. Em diversos métodos de aprendizado de máquina, visão computacional e tarefas de recuperação, as amostras de dados são comumente representadas como pontos em um espaço multidimensional. Em tal cenário, estimar a similaridade entre pontos de dados se mantêm como um ponto central de pesquisa, mesmo para representações obtidas por métodos recentes de aprendizado profundo. Métricas de distância tradicionais como a distância Euclidiana são frequentemente utilizadas, mas por considerar apenas a análise de pares acabam limitando avaliações de similaridade em dados mais complexos. Em contrapartida, listas ranqueadas fornecem uma representação contextual ine- rente, estabelecendo relações entre todos os elementos dos dados. Sendo assim, este capítulo apresentará um método capaz de tirar proveito dessa representação e aproveitar informa- ções de similaridade entre dados rotulados e não rotulados. Sendo assim, a ideia central que vai ser explorada pelo método proposto ao longo desse capítulo é: (i) A informação de contexto em que os dados estão inseridos presente nas listas ranqueadas pode ser analisada através de métricas de correlação de modo a identificar fortes relações de similaridade entre os dados; (ii) Identificadas as amostras com uma alta similaridade, estas relações podem ser utilizadas para expandir pequenos conjuntos rotulados de treinamento, permitindo um treinamento e classificação mais efetivos por classificadores supervisionados ou semi-supervisionados; (iii) Se tratando de listas ranqueadas, é considerada a utilização de métodos de re- ranqueamento, capazes de gerar listas mais efetivas (com mais amostras de mesma classe nas posições iniciais), permitindo gerar informações de similaridade com mais confiança a partir da análise das métricas de correlação. Como discutido ao longo das Seções 2.1 e 2.2, as listas ranqueadas são geradas a partir dos vetores de características extraídos por um descritor visual. Por conta disso, a qualidade das listas ranqueadas está fortemente associada a qualidade dos vetores de características. Considerando a qualidade das listas ranqueadas, o método de aprendizado fracamento supervisionado baseado em correlações também depende da qualidade dos Capítulo 3. Aprendizado Fracamente Supervisionado Baseado em Correlações 29 vetores de características. Assim, a análise entre amostras que será realizada a partir das métricas de correlação depende de um espaço de características capaz de representar as classes de maneira minimamente adequada. Além disso, a análise das listas ranqueadas tem de ser limitadas a uma constante l, de modo a manter o método escalável e adequado para conjuntos de dados com muitas amostras. Apesar das limitações, por conta da informação contextual que pode ser explorada por meio das listas ranqueadas, o método consegue rotular instâncias incertas, onde há uma alta sobreposição com outras classes, situação em que normalmente esse tipo de amostra é desconsiderado. A Figura 5 apresenta o método fracamente supervisionado baseado em correlações proposto, dividido em suas principais etapas desde a preparação dos dados até a classifi- cação. Primeiro são extraídas as características de cada imagem de modo a obter uma representação para cada imagem. Em seguida, o método proposto passa por cinco etapas principais: 1. Ranqueamento: listas ranqueadas são calculadas para cada uma das imagens com base nas distâncias entre os vetores de características extraídos 1; 2. Re-Ranqueamento: um algoritmo de re-ranqueamento explora informações de similaridade entre as imagens de modo a calcular distâncias mais globais e por consequência gerar listas ranqueadas mais efetivas. Essa etapa pode ser opcional, uma vez que as listas ranqueadas originais podem ser utilizadas na próxima etapa; 3. Similaridade entre Listas Ranqueadas: a similaridade entre as imagens é avali- ada por meio de métricas de correlação de ranqueamento; 4. Definição de Limiar: a variação das métricas de correlação nas primeiras posições das listas ranqueadas é explorada de modo a definir um limiar que é utilizado na etapa de expansão; 5. Expansão de Conjuntos Rotulados: relações de similaridade acima do limiar estimado na etapa anterior são selecionadas de modo a expandir os conjuntos rotulados de treinamento2. Por fim, o conjunto de treino ampliado é utilizado para treinamento de classificadores supervisionados ou semi-supervisionados. Cada etapa do método proposto é formalmente definida e discutida nas seções a seguir. O método proposto é flexível e independe tanto do extrator de características quanto do classificador. Os métodos selecionados para 1 É possível também obter as listas ranqueadas através da utilização de métodos de indexação como, por exemplo, os métodos BallTree [67] e K-DTree [68]. 2 O item 5 na Figura 5 ilustra a expansão de conjuntos rotulados em um cenário de classificação binária. Em verde as setas indicam uma alta relação de similaridade encontrada entre as imagens através da análise das correlações. Capítulo 3. Aprendizado Fracamente Supervisionado Baseado em Correlações 30 Figura 5 – Diagrama de funcionamento do método de aprendizado fracamente supervisi- onado baseado em correlações. Coleção de Imagens x1 x2 Re-ranqueamento2 Classificadores Supervisionados ou Semi-Supervisionados ... ... ... Conjunto Rotulado Expansão de Rótulos Expansão de Conjuntos Rotulados 5 ... ... Métrica de correlação: r(q1,q2) Similaridade entre Listas Ranqueadas 3Definição do Limiar4 Extração de Características ( 1, 2)>r q q th 1 Ranqueamento Fonte: Elaborado pelo autor. essas tarefas nesse trabalho são discutidos durante a avaliação experimental, onde são considerados métodos tradicionais e mais recentes. 3.1 Aprendizado de Variedades (Manifold Learning) Medir a similaridade entre objetos de forma precisa e eficaz é um ponto fundamental em muitas tarefas de ranqueamento e aprendizado de máquina. Entretanto, a mais comum comparação entre pares de vetores de características, muitas vezes baseada em funções de distância como a distância Euclidiana, ignora os complexos arranjos de similaridade e as informações estruturais do conjunto de dados. De modo a contornar tais limitações, métodos de aprendizado de variedades (manifold learning) tem sido propostos. Estes trabalham com medidas mais globais, capazes de considerar a estrutura dos conjuntos de dados e fornecer medidas de similaridade mais eficazes. Mais recentemente, métodos de aprendizado de variedades baseados em ranques tem apresentado avanços consideráveis [69, 19, 20]. Formalmente, o objetivo principal dos métodos de aprendizado de variedades baseados em ranques é explorar informações de similaridade codificadas no conjunto de listas ranqueadas T , capaz de capturar de uma melhor maneira a estrutura dos dados. Através de tal análise, um novo e mais eficaz conjunto de listas ranqueadas Tm é calculado de maneira não supervisionada de modo a melhorar a eficácia de métodos que trabalham com ranques. Portanto, podemos descrever os métodos de aprendizado de variedades como Capítulo 3. Aprendizado Fracamente Supervisionado Baseado em Correlações 31 uma função fm: Tm = fm(T ). (3.1) Por gerar um novo conjunto de listas ranqueadas, ao longo do texto, os referir aos métodos de aprendizado de variedades baseados em ranques são referidos como métodos de re-ranqueamento. A abordagem proposta é flexível e permite o uso de diversos métodos de re-ranqueamento que atendam à definição apresentada [19, 20, 57, 58, 59, 54, 61]. Esse trabalho considera dois métodos de aprendizado de variedades baseados em ranques para gerar a função fm: LHRR (Log-based Hypergraph of Ranking References) [19] e BFS-Tree Manifold Learning [20]. A escolha desses métodos deve-se ao fato de que ambos foram propostos recentemente e apresentam resultados de alta eficácia em diferentes conjuntos de dados. Tais métodos são discutidos brevemente a seguir. • LHRR (Log-based Hypergraph of Ranking References) [19]: explora a in- formação similaridade presente nas listas ranqueadas por meio de um hipergrafo. Hipergrafos são uma poderosa generalização dos grafos, a qual permite a criação de hiperarestas capazes de conectar um número qualquer de vértices e por consequência representar similaridades de ordem superiores entre conjuntos de objetos. O hipergrafo e suas hiperarestas são construídos com base nas referências entre os ranques, e os pesos das hiperarestas são atribuídos com base em uma função baseada em logaritmos. A abordagem usa das hiperarestas para construir uma representação dos dados que considera o contexto e explora das informações codificadas nesse contexto para gerar uma maneira mais eficaz de similaridade. A similaridade entre objetos é então calculada como um produto das similaridades entre suas respectivas hiperarestas. A função de similaridade é então utilizada para construir um novo e mais eficaz conjunto de listas ranqueadas. • BFS-Tree Manifold Learning [20]: usa das informações de similaridade codifi- cadas nas referências entre listas ranqueadas através de uma estrutura de árvore de busca em largura. A estrutura de árvore fornece uma representação hierárquica das primeiras k posições das listas ranqueadas, codificando relações de vizinhança de primeira e segunda ordem obtidas com as referências entre as listas ranqueadas. Os pesos das arestas são atribuídos aos elementos da árvore representam a similaridade sendo calculados com base em métricas de correlação entre listas ranqueadas. Assim que construída, a estrutura de árvore é explorada de modo a descobrir relações de similaridade ocultas entre os dados. Cada elemento é representado com base no caminho do mesmo até raiz da árvore junto dos pesos das arestas. Novas conexões são então estabelecidas entre os nós folha, estas que não são inicialmente feitas considerando somente as referências entre os ranques. Tais conexões permitem a descoberta de novas relações de similaridade. Capítulo 3. Aprendizado Fracamente Supervisionado Baseado em Correlações 32 Além dessas novas conexões de similaridade, a estrutura de árvore permite analisar a frequência com que cada elemento aparece. De maneira geral, um indicativo sólido de similaridade pode ser obtido através da coocorrência de elementos em diferentes níveis da estrutura de árvore, enquanto poucas aparições são indicativo de ruído. O algoritmo constrói uma árvore de busca em largura para cada item de dados do conjunto. Por fim, uma métrica de similaridade mais global e eficaz é calculada usando a informação de similaridade extraída de cada uma das árvores. 3.2 Métricas de Correlação de Listas Ranqueadas Com base em um conjunto de listas ranqueadas, uma similaridade contextual entre as amostras de dados pode ser calculada. Nesse cenário, uma questão fundamental consiste em como calcular as métricas de correlação entre listas ranqueadas. Métricas de correlação podem ser definidas como uma função r: T ×T → R+ que compara duas listas ranqueadas e atribui um valor real a essa comparação. Essa comparação é feita considerando as primeiras k posições das listas ranqueadas. A notação N (q, k) é utilizada ao longo da seção para se referir aos primeiros k vizinhos de um item de dados xq. O conjunto N (q, k) pode ser definido formalmente baseado na informação presente na lista ranqueada τq: N (q, k) = {Xk ⊂ X, | ∃xi ∈ Xk ∧ ∃xj ∈ X\Xk ∧ τq(i) < τq(j) ∧ |Xk| = k}. (3.2) São discutidas a seguir diferentes maneiras de se calcular uma métrica de correlação r(·, ·). Foram consideradas métricas de abordagens distintas como a interseção nas primeiras k posições (RBO [70] e Intersection [71]), a distância entre as posições (Kendallτ [71]) e operações entre conjuntos (Jaccard [72] e Jaccardk [73]). • Intersection [71]: calcula a quantidade de sobreposição entre duas listas ranqueadas τi e τj de tamanho k, considerando as sobreposições nas profundidades de 1 a k. Para cada profundidade d ∈ {1 . . . k}, a quantidade de sobreposição é calculada e a média de todas as sobreposições é computada, gerando uma métrica de similaridade. A métrica Intersection atribui um maior peso as primeiras posições das listas ranqueadas, já que estas são consideradas mais vezes durante o cálculo da métrica. A Equação 3.3 apresenta uma definição formal da métrica: r(τi, τj, k) = ∑k d=1 | N (i, d) ∩N (j, d) | k . (3.3) • Jaccard [72]: o coeficiente de Jaccard [72] é calculado através da análise de dois conjuntos não vazios de tamanho k. O coeficiente calcula a probabilidade de que um Capítulo 3. Aprendizado Fracamente Supervisionado Baseado em Correlações 33 elemento de pelo menos um dos dois conjuntos é elemento de ambos. Este é definido a seguir: r(τi, τj, k) = |N (i, k) ∩N (j, k)| |N (i, k) ∪N (j, k)| . (3.4) • Jaccardk [73]: o coeficiente de Jaccard [72] considera somente uma profundidade k de uma lista ranqueada, portanto ignora a informação fornecida pelas primeiras posições das listas ranqueadas com profundidade menor do que k. Surge então a métrica Jaccardk [73], sendo um índice de Jaccard [72] acumulado que considera profundidades de 1 a k, atribuindo pesos maiores às primeiras posições: r(τi, τj, k) = 1 k k∑ d=1 |N (i, d) ∩N (j, d)| |N (i, d) ∪N (j, d)| . (3.5) • Kendallτ [71]: tradicional métrica de distância entre permutações, é calculada com base no número de trocas necessárias em uma ordenação por flutuação (bubble sort) para converter uma permutação na outra [71]. A métrica é Kendallτ é definida a seguir: r(τi, τj, k) = (k · (k − 1)) 2 ·∑x,y∈N (i,k)∪N (j,k) K̄x,y(τi, τj) , (3.6) onde K̄x,y(τi, τj) é uma função que determina se duas imagens x e y estão na mesma ordem nas primeiras k posições das listas ranqueadas τi e τj, e pode ser definida como: K̄x,y(τi, τj) =  0 se (τi(x) 6 τi(y) ∧ τj(x) 6 τj(y)), 0 se (τi(x) > τi(y) ∧ τj(x) > τj(y)), 1 caso contrário. • RBO (Rank-Biased Overlap) [70]: assim como a métrica Intersection [71], também considera as sobreposições de duas listas ranqueadas em diferentes profun- didades. Entretanto, a métrica RBO [70] se utiliza de um parâmetro que determina a probabilidade de considerar a sobreposição na próxima profundidade, e é definida a seguir: r(τi, τj, k) = (1− pr) k∑ d=1 p(d−1) r |N (i, d) ∩N (j, d)| d , (3.7) onde pr ∈ [0, 1] é utilizada para calcular a probabilidade em uma profundidade d. 3.3 Expansão de Conjuntos Rotulados por Correlações Espera-se que valores altos de correlação sejam atribuídos a listas ranqueadas similares, valores superiores ao limiar definido para tarefa de expansão. A hipótese principal explorada pelo nosso trabalho é de que valores altos de métricas de correlação indicam fortes Capítulo 3. Aprendizado Fracamente Supervisionado Baseado em Correlações 34 relações de similaridade, informação que pode ser utilizada para expandir os conjuntos rotulados. Formalmente, seja xl ∈ XL um item rotulado e seja xu ∈ XU um item não rotulado. Portanto, se a métrica de correlação entre τl e τu ultrapassa um determinado limiar th apenas a elementos rotulados de mesma classe, o conjunto rotulado é expandido de modo a incorporar xu. Podemos definir o conjunto rotulado estimado XE como: XE = {xe : xe ∈ XU , xl ∈ XL ∧ r(τl, τe) ≥ th∧ @xz ∈ XL|r(τz, τe) ≥ th ∧ Y (xl) 6= Y (xz)}. (3.8) Sendo assim, classe estimada do elemento xe é a mesma que o item rotulado xl, logo: EC(xe) = Y (xl). (3.9) O conjunto rotulado expandido XW pode ser então definido através da união do conjunto rotulado original e do conjunto rotulado estimado: XW = XL ∪ XE. (3.10) A Figura 6 ilustra o processo de expansão de conjuntos rotulados. Começando com um pequeno conjunto rotulado, calculamos as métricas de correlação r(τl, τu) entre os itens rotulados e os não rotulados. Então, considerando o limiar th, para cada imagem rotulada, são selecionadas quais imagens não rotuladas obtêm uma correlação que seja maior ou igual ao limiar th, gerando uma série de conjuntos. Após isso, para remover inconsistências, no caso de um mesmo item ter um rótulo atribuído duas vezes ou mais, as interseções entre esses conjuntos são removidas. Por fim, o conjunto rotulado expandido é utilizado para treinamento de um classificador supervisionado ou semi-supervisionado. Considerando a complexidade computacional do método, a expansão de rótulos está intimamente associada a quantidade de amostras rotuladas. Seja L igual à quantidade de elementos do conjunto rotulado XL (L = |XL|) e l o comprimentos das listas ranqueadas considerado. Para cada item rotulado (L), uma métrica de correlação é calculada para cada item não rotulado (N − L). A complexidade das métricas de correlação varia, mas todas as métricas são limitadas a analisar somente as primeiras k posições das listas ranqueadas, e como k é uma constante, sua complexidade é portanto O(1). A complexidade total então é O(L(N − L)) se considerarmos as listas ranqueadas inteiras (de tamanho N), porém, as listas ranqueadas são normalmente definidas apenas até um tamanho constante l, de modo que k < l� N . Deste modo, as métricas de correlações são calculadas considerando somente as primeiras l posições das listas ranqueadas dos elementos rotulados, logo, a complexidade total pode ser reduzida para O(L). Capítulo 3. Aprendizado Fracamente Supervisionado Baseado em Correlações 35 Figura 6 – Ilustração do método de expansão de conjuntos rotulados baseado em corre- lações de listas ranqueadas. 0.75 0.750.8 0.7 0.75 Dados Rotulados 0.9 Conjunto de Treino Expandido Conjuntos gerados por cada item rotulado com o limiar 0.8 0.8 0.92 Dados Não Rotulados Fonte: Elaborado pelo autor. 3.4 Definição do Limiar de Correlação As métricas de correlação de listas ranqueadas fornecem uma maneira efetiva de analisar a informação de similaridade contextual codificada nos conjuntos de dados. Entretanto, de modo a executar uma expansão de conjuntos rotulados adequada, é essencial selecionar um limiar para os valores de correlação capaz de separar amostras relevantes das não relevantes. Caso esse limiar seja muito alto, expansões muito pequenas ou insignificantes podem ocorrer. Ao contrário, caso o valor de limiar seja muito baixo, amostras incorretas podem ser incorporadas ao conjunto de treinamento, o que pode diminuir os resultados de acurácia obtidos. A Figura 7 apresenta uma análise visual desse cenário. Considerando uma imagem de consulta (em azul), a partir de diferentes valores do limiar são selecionadas imagens em que a correlação entre estas e a imagem de consulta ultrapasse o limiar. Podemos observar que para valores de limiar muito altos, poucos elementos são selecionados, e conforme diminuímos esse valor mais imagens são selecionadas até que imagens incorretas começam a ser selecionadas (em vermelho). Com isso em mente, um método não supervisionado capaz de estimar um limiar adequado em cada cenário através da análise das correlações em diferentes posições nas listas ranqueadas. As primeiras posições das listas ranqueadas normalmente concentram amostras relevantes de mesma classe. A transição das amostras relevantes para não relevantes tende a causar mudanças bruscas nos valores de correlação, situação que pode ser identificada e explorada para definir um limiar adequado. Capítulo 3. Aprendizado Fracamente Supervisionado Baseado em Correlações 36 Figura 7 – Diferentes conjuntos gerados pela análise de uma métrica de correlação considerando diferentes limiares. Limiar = 0.75Limiar = 0.75 Limiar = 0.25Limiar = 0.25 Limiar = 1.00Limiar = 1.00 Limiar = 0.50Limiar = 0.50 Fonte: Elaborado pelo autor. A sequência de métricas de correlação é representada por splines lineares, derivadas e diferenças de médias móveis, cujos valores são utilizados para identificar tendências e estimar o limiar. A análise é conduzida para cada lista ranqueada e a média de cada limiar estimado é calculada para definir o parâmetro th utilizado na etapa de expansão do método de correlações. O método de obtenção do limiar pode ser dividido em quatro etapas principais, como está ilustrado na Figura 8. Cada uma das etapas é discutida com detalhes a seguir. Figura 8 – Método proposto para definição automática do limiar de expansão. Ranque de Correlações por Posição A Interpolação por Spline Média MóvelB Definição do Limiar pelo Valor MínimoC D Fonte: Elaborado pelo autor. A) Ranque de Correlações por Posição: O primeiro passo do método de definição do limar é criar um vetor de métricas de correlação calculadas a partir das posições das listas ranqueadas. Formalmente, Capítulo 3. Aprendizado Fracamente Supervisionado Baseado em Correlações 37 seja xi ∈ X um item de dados e τi a sua lista ranqueada de tamanho l. O vetor ci = [ci1, ci2, . . . , cil] denota um ranque de métricas de correlação definido a partir de τi. O valor de cada elemento cipo é definido como cipo = r(τi, τj), onde po é a posição de xj na lista ranqueada τi, de modo que po = τi(j) e r(·, ·) denota uma métrica de correlação entre listas ranqueadas, definida na seção anterior (Seção 3.2). A Figura 9 ilustra os valores de um vetor de métricas de correlação conforme as posições em uma lista ranqueada de uma imagem da coleção de imagens MPEG-7 [74]. Uma queda brusca nos valores de correlação pode ser observada perto do número de elementos por classe da coleção de imagens (perto da posição 20) pode ser observada. Figura 9 – Valores de correlação segundo a posição na lista ranqueada τ0. 0 5 10 15 20 25 30 35 40 Index in 0 0.0 0.2 0.4 0.6 0.8 1.0 Sp ea rm an M et ri c Spearman metric (r ( , )) over each element in 0 considering MPEG-7 dataset and ASC descriptor. r ( 0, x) Fonte: Elaborado pelo autor. B) Interpolação por Spline: Seja f uma função definida no intervalo [ci1, cil], a qual representa a relação entre as posições do ranque e os valores de correlação dados pelo vetor ci. Para estimar a função f , utilizamos de uma interpolação por spline linear sL(a). O intervalo [ci1, cil] pode ser dividido em [aj, aj+1] subintervalos com j = 1, . . . , l − 1, a1 = ci1 e al = cil. É possível definir um polinômio p(a) no intervalo [ci1, cil]: p(a) = pi(a), aj−1 < a < aj, (3.11) onde para j = 1, 2, . . . , l cada pj(a) é uma função polinomial definida no intervalo [aj−1, aj]. Capítulo 3. Aprendizado Fracamente Supervisionado Baseado em Correlações 38 Considerando os pontos a1, a2, . . . , al, a spline linear sL(a) que interpola a função f nesses pontos pode ser definida como: sL(a) = f(aj−1) a− aj aj−1 − aj + f(aj) a− aj−1 a− aj−1 , (3.12) onde a ∈ [aj−1, aj] e j = 2, . . . , l. Um exemplo de interpolação pode ser observado na Figura 10, que apresenta uma spline linear estimada com base nos valores de correlação obtidos no passo anterior. Figura 10 – Interpolação por spline linear sL(a) feita sobre os valores de correlação do vetor ci. 0 5 10 15 20 25 30 35 40 Index in 0 0.0 0.2 0.4 0.6 0.8 1.0 Sp ea rm an M et ri c Linear spline (sL) computed over Spearman metric (r ( , )) values in 0 considering MPEG-7 dataset and ASC descriptor. r ( 0, x) sL Fonte: Elaborado pelo autor. C) Média Móvel: Através da spline linear gerada no passo anterior, podemos calcular as derivadas para cada valor em ci. Para cada valor de correlação, a derivada correspondente é calculada: dij = df da (cij), (3.13) gerando um vetor de derivativas di = [di1, di2, . . . , dil]. Com base em cada valor do vetor de derivadas, as médias móveis são calculadas considerando um tamanho de janela m3. Seja mai = [mai1,mai2, . . . ,maiN ] o vetor de médias móveis, definido por: maij = 1 m m−1∑ l=0 dij+l. (3.14) 3 Em nossos experimentos, utilizamos m = 2. Capítulo 3. Aprendizado Fracamente Supervisionado Baseado em Correlações 39 A Figura 11 apresenta as derivadas calculadas a partir dos valores da spline linear e suas respectivas médias móveis. Figura 11 – Derivadas da spline linear sL(a) e as médias móveis desses valores considerando um tamanho de janela m = 2. 0 5 10 15 20 25 30 35 40 Index in 0 0.4 0.3 0.2 0.1 0.0 0.1 0.2 Sp ea rm an M et ri c D er iv at iv e Derivatives of the linear spline (sL) in each Spearman metric value (r ( , )) in 0 considering MPEG-7 dataset and ASC descriptor and the moving average (ma) of the derivatives with a window size of 2. df dx (r ( 0, x)) max Fonte: Elaborado pelo autor. D) Definição do Limiar pelo Valor Mínimo: Ao considerar as médias móveis das derivadas, avaliamos as tendências nos valores de derivadas das métricas de correlação. Nosso método tenta verificar onde os valores de derivadas começam a diminuir a uma taxa que indica baixos valores de confiança nas informações de similaridade. Para analisar essas tendências nos valores de médias móveis, são analisadas as diferenças entre valores consecutivos das médias. Ou seja, dado o vetor de médias móveis mai, a diferença entre valores consecutivos é definida por: difmaij = maij+1 −maij, (3.15) onde j = 1, 2, . . . , l − 1. Podemos definir um vetor de diferenças como: difmai = [difmai1 , difmai2 , . . . , difmail ] e com as diferenças calculadas, precisamos identificar a posição/índice que contém o menor valor. Essa posição é utilizada como o índice do vetor de correlações ci e define o limiar thi, e pode ser definida formalmente como: thi = ci[arg min difmai ]. (3.16) Capítulo 3. Aprendizado Fracamente Supervisionado Baseado em Correlações 40 A Figura 12 apresenta essa análise. Além das diferenças entre posições consecutivas das médias móveis, o menor valor dessas diferenças é destacado. O índice do menor valor na Figura 12 é igual a 16, logo, ao analisar os valores de correlação do ranque de correlações presente na Figura 9 podemos definir um limiar por volta de 0.8 nesse cenário. Figura 12 – Médias móveis mai dos valores de derivada da spline linear sL, as diferenças entre valores consecutivos e o valor mínimo dessas diferenças. 0 5 10 15 20 25 30 35 40 Index in 0 0.2 0.1 0.0 0.1 0.2 Sp ea rm an M et ri c D er iv at iv e Moving averages (ma) of the derivatives of the linear spline (sL) and the differences between each consecutive position. max max max 1 min value Fonte: Elaborado pelo autor. Por fim, de modo a estimar um limiar capaz de representar o conjunto de dados na totalidade, as etapas apresentadas anteriormente são repetidas para todos os itens de dados, gerando um limiar thi para cada xi ∈ X. O limiar global th que é considerado na tarefa de expansão é calculado a partir da média de todos os limiares thi estimados individualmente, sendo definido como: th = 1 N ∑ xi∈X thi. (3.17) 41 4 Aprendizado Fracamente Supervisionado Baseado em Hipergrafos A falta de dados de treinamento em cenário de supervisão fracamente supervisionada traz diversos desafios para aprimorar a acurácia em tarefas de classificação. Entre elas, a questão principal consiste em explorar ao máximo a informação presente nos dados não rotulados, os quais são abundantes, e como estabelecer relações confiáveis entre os escassos dados de treinamento disponíveis e as amostras não rotuladas. Uma solução para contornar esse problema é proposta ao longo desse capítulo, em que utilizaremos de um método de aprendizado de variedades baseado em ranqueamento e de uma estratégia de expansão de rótulos. A estratégia utilizada pelo método apresentado ao longo do capítulo se da através da análise de uma estrutura de hipergrafo construído a partir da análise do modelo de ranqueamento. Hipergrafos conseguem relacionar diversas amostras através de suas hiperarestas (diferente de pares em grafos convencionais), e essa representação pode ser explorada de modo a atribuir rótulos aos elementos não rotulados. De modo similar ao método de aprendizado fracamento supervisionado baseado em correlações (Capítulo 3), o desempenho do método está fortemente associada a qualidade das listas ranqueadas, e por consequência a qualidade dos vetores de características. Além disso, a análise das listas ranqueadas também deve ser limitada a uma constante l para tornar o método adequado a todos os cenários. Por trabalhar com um modelo de ranqueamento, o método é capaz de considerar instâncias com uma alta sobreposição com outras classes no espaço de características e ao utilizar uma estrutura de hipergrafo, o método apresenta um bom comportamento em conjuntos de dados grandes, por conseguir relacionar diversos conjuntos de elementos. A Figura 13 apresenta o método de aprendizado fracamente supervisionado baseado em hipergrafos proposto, dividido desde a preparação dos dados até a etapa final de classificação. A primeira etapa para funcionamento do método é extrair os vetores de características de cada imagem, após isso o método proposto passa por quatro etapas principais: 1. Ranqueamento: um conjunto de listas ranqueadas é criado para cada uma das imagens do conjunto de dados a partir das distâncias entre os vetores de características de cada uma das amostras; 2. Construção do Hipergrafo: é construído um hipergrafo e estruturas associadas a partir do método LHRR [19] de aprendizado de variedades. As informações fornecidas Capítulo 4. Aprendizado Fracamente Supervisionado Baseado em Hipergrafos 42 pelas estruturas do hipergrafos são utilizadas pelo método de expansão de rótulos; 3. Definição da Taxa de Expansão de Rótulos: o método de expansão proposto depende de um parâmetro que seleciona qual porcentagem das novas amostras rotuladas geradas é realmente incorporada ao conjunto expandido. Uma estratégia para definir essa taxa de expansão de rótulos é explorada; 4. Expansão de Conjuntos Rotulados: A informação fornecida pelo hipergrafo é explorada de modo a identificar hiperarestas e relações de similaridade de alta confiança entre os dados. Essas informações são utilizadas para construir um conjunto de pares (rotulados, não rotulados) de candidatos à expansão de rótulos. Os pares são ordenados de acordo com seu grau de confiança estimado e os melhores pares são selecionados para a expansão. Por fim, o conjunto rotulado de treino expandido é utilizado para treinamento de classificadores supervisionados ou semi-supervisionados. Figura 13 – Diagrama de funcionamento do método de aprendizado fracamente supervi- sionado baseado em hipergrafos. Coleção de Imagens Extração de Características Ranqueamento Construção do Hipergrafo Definição da Taxa de Expansão de RótulosExpansão de Conjuntos Rotulados Classificadores Supervisionados ou Semi-Supervisionados Fonte: Elaborado pelo autor. A Seção 4.1 discute o método de aprendizado de variedades que constrói o modelo de hipergrafo que é utilizado para realizar a tarefa de expansão. Na Seção 4.2 o método de expansão de conjuntos rotulados por hipergrafos é apresentado. Por fim, a Seção 4.3 apresenta uma estratégia para definir automaticamente um dos parâmetros do método de expansão. Capítulo 4. Aprendizado Fracamente Supervisionado Baseado em Hipergrafos 43 4.1 Construção do Hipergrafo Hipergrafos fornecem uma técnica robusta para representar relações de similari- dade entre os conjuntos de objetos. Além disso, listas ranqueadas concentram relevantes informações de similaridade nas primeiras posições. O algoritmo LHRR [19] se utiliza de um hipergrafo que é construído a partir das informações presentes nas listas ranqueadas para representar relações de similaridade codificadas na estrutura do conjunto de dados. Uma vez que as estruturas do hipergrafo define a base do método de expansão de rótulos, sua definição é discutida em detalhes a seguir. O algoritmo pode ser dividido em cinco etapas principais: 1. Normalização das Listas Ranqueadas: O primeiro passo para funcionamento do algoritmo é normalizar cada lista ranqueada considerando uma nova métrica de similaridade pn calculada sobre posições reciprocas dos ranques. Seja xi e xj dois itens de dados, a nova métrica de similaridade é: ρn(xi, xj) = 2l − (τi(xj) + τj(xi)), (4.1) onde l é o tamanho da lista ranqueada que considerada. Através dessa nova métrica, os itens de dados nas primeiras l posições das listas ranqueadas são ordenados se utilizando um algoritmo de ordenação estável. 2. Construção do Hipergrafo: Seja G = (V,E,w) um hipergrafo onde V é um conjunto finito de vértices e E o conjunto de hiperarestas. O conjunto de hiperarestas E é uma família de subconjuntos de V tal que ⋃ e∈E = V . Para cada vértice vi ∈ V um item xi ∈ X está associado. Cada hiperaresta tem um peso w(ei) atribuído, que representa o grau de confiança das relações estabelecidas pela hiperaresta ei. Dizemos que uma hiperaresta ei é incide no vértice vj quando vj ∈ ei. Com isso em mente, podemos representar o hipergrafo através de uma matriz de incidências Hb de tamanho |E| × |V |: hb(ei, vi) =  1 se vj ∈ ei, 0 caso contrário. Podemos também definir uma hiperaresta ei como um conjunto de vértices ei = {v1, v2, . . . , vm}. A matriz de incidências Hb permite apenas atribuições binárias de um vértice à hiperaresta, não considerando cenários onde é desejável considerar um certo grau de incerteza. Para contornar esse problema, podemos definir um hipergrafo probabilístico, onde a probabilidade de que um vértice pertence ao hipergrafo é considerada. Seja r : E × V → R+ uma função, podemos definir uma matriz de incidências contínua H onde: h(ei, vi) =  r(ei, vj) se vj ∈ ei, 0 caso contrário. Capítulo 4. Aprendizado Fracamente Supervisionado Baseado em Hipergrafos 44 Para cada item de dados xi ∈ X uma hiperaresta é definida com base no conjunto dos k vizinhos de xi. Seja xz ∈ N (xi, k) um vizinho de xi e seja xj ∈ N (xz, k) um vizinho de xz. Podemos definir uma medida de associação r(ei, vj), que indica o grau de que um vértice vj pertence a hiperaresta ei: r(ei, vj) = ∑ xz∈N (xi,k)∧xj∈N (xz ,k) wp(xi, xz) · wp(xz, xj), (4.2) onde wp(xi, xz) atribui um peso de relevância a xz com base em sua posição em τi. O peso wp(i, z) atribuído a xz com base em sua posição em τi pode ser definido como: wp(xi, xz) = 1− logk τi(xz). (4.3) A Figura 14 ilustra como as listas ranqueadas são exploradas para construção da hiperaresta e1 e como a relação entre a hiperaresta e os vértices é calculada. A hiperaresta e1 é criada a partir da lista ranqueada τ1 considerando as refêrencias aos ranques τ2 e τ3. Cada função wp atribui um peso a cada vértice de acordo com sua posição na lista ranqueada. Entre a hiperaresta e1 e o vértice v2 uma associação é definida por r(e1, v2), calculada usando dos pesos gerados por wp (Equação 4.3). A Figura 15 apresenta um exemplo de um hipergrafo construído pelo método LHRR [19] em sua totalidade com quatro vértices e quatro hiperarestas. Figura 14 – Definição da hiperaresta e1 através das referências entre os ranques considerando um tamanho de vizinhança igual 3. A Função wp atribui pesos de acordo com as posições das imagens nas hiperarestas e são utilizadas para definir uma relação entre a hiperaresta e seus vértices respectivos (r(e1, v2)). x1 x3 x3 τ1 x2 τ3 τ2 x2 x2 x1 x3 x1 e1wp(v1,v3) x4 x4 x4 Análise dos Ranques =3k v1 v3 v2wp(v1,v2) v1v2 v1v3 wp(v3,v2) wp(v2,v2) (r e 1 ,v 2 ) = wp(x1,x3) wp(x3,x2) + Hiperaresta vs Vértice wp(x1,x2) wp(x2,x2) (r e 1 ,v 2 ) = (1-log 3 2) (1-log 3 2) + (1-log 3 3) (1-log 3 1) (r e 1 ,v 2 ) = (0.63) (0.63) + (0) (1) (r e 1 ,v 2 ) = 0.40 Definição da Hiperaresta Fonte: Elaborado pelo autor. Capítulo 4. Aprendizado Fracamente Supervisionado Baseado em Hipergrafos 45 Figura 15 – Hipergrafo construído pelo método LHRR [19] com os vértices {v1, v2, v3, v4} e as hiperarestas {e1, e2, e3, e4}. v1 v2 v4 e1 e2 e3 e4v3 Fonte: Elaborado pelo autor. Cada hiperaresta possui um peso w(ei) respectivo, o qual representa o grau de confiança das relações estabelecidas entre os vértices. Antes de calcularmos os pesos w(ei) é preciso definir o conjunto de vizinhança do hipergrafo Nh. Dado uma hiperaresta ei, o conjunto Nh com os vértices com os valores mais altos de h(ei, ·) pode ser definido como: Nh(xq, k) = {S ⊆ eq, |S| = k ∧ ∀xi ∈ S, xj ∈ eq − S : h(eq, vi) > h(eq, vj)}. (4.4) É esperado que uma hiperaresta altamente efetiva contenha poucos vértices, que estão relacionados com altos valores de h(ei, ·) [19]. Com isso em mente, o peso w(ei) pode ser definido como: w(ei) = ∑ j∈Nh(xi,k) h(ei, vj). (4.5) Como cada hiperaresta é criada a partir da análise das listas ranqueadas τi, o peso w(ei) de cada hiperaresta pode ser considerado como uma medida de eficácia não supervisionada da lista ranqueada τi. Logo, altos valores de w(ei) podem ser interpretados como uma lista ranqueada de alta eficácia [19]. 3. Similaridade entre as Hiperarestas: O próximo passo do método LHRR é criar uma matriz de similaridade S. Sua construção se baseia em duas hipóteses [19]. A primeira é que itens de dados similares tem listas ranqueadas similares e, portanto, hiperarestas similares. Considerando que a matriz de incidências codifica todas as informações de similaridade, uma métrica de similaridade entre duas hiperarestas ei e ej pode ser calculada através da soma de todos os valores de h multiplicados pelos seus vértices correspondentes. Para considerar todos os elementos, essa operação pode ser realizada multiplicando a matriz de incidências pela sua transposta. Sh = HHT . (4.6) Capítulo 4. Aprendizado Fracamente Supervisionado Baseado em Hipergrafos 46 A segunda hipótese é a de que itens similares tem uma probabilidade alta de participarem da mesma hiperaresta. Portanto, para calcular a similaridade entre dois vértices vi e vj, os valores h da hiperaresta correspondente devem ser multiplicados. De modo similar a primeira hipótese, é possível realizar essa operação através da matriz de incidências, multiplicando a matriz transposta pela matriz não transposta: Sv = HT H. (4.7) Por fim, as duas similaridades são combinadas em uma matriz de similaridade S através do produto de Hadamard das matrizes Sh e Sv: S = Sh ◦ Sv. (4.8) 4. Produto Cartesiano dos Elementos das Hiperarestas: Construída a matriz de similaridade S, a próxima etapa é executar operações de produto cartesiano para extrair relações entre pares de elementos diretamente das hiperarestas. Operação feita com o objetivo de maximizar as informações de similaridade, e essa nova informação pode ser combinada com as similaridades das hiperarestas. O produto cartesiano entre duas hiperarestas eq ∈ E e ei ∈ E é: eq × ei = {(vy, vz) : vy ∈ eq ∧ vz ∈ ei} (4.9) O produto cartesiano entre os elementos da mesma hiperaresta eq pode ser descrito como e2 q. Cada par de vértices (vi, vj) ∈ eq 2 tem uma relação p : E × V × V → R+ estabelecida. Essa relação é calculada através do peso w(eq), o grau de confiança da hiperaresta. É possível também definir um grau de associação entre os vértices vi and vj: p(eq, vi, vj) = w(eq)× h(eq, vi)× h(eq, vj). (4.10) Com o grau de associação p calculado, a matriz C é construída considerando as relações entre todas as hiperarestas. Cada posição da matriz C é definida a seguir: Ci,j = ∑ eq∈E∧(vi,vj)∈eq 2 p(vi, vj). (4.11) 5. Similaridade Baseada em Hipergrafos: Calculadas as matrizes S e C nos passos 3 e 4, uma nova matriz de similaridade ou afinidade W é formada ao combiná-las: W = C ◦ S. (4.12) A matriz W concentra as informações de similaridade e é utilizada para calcular um novo conjunto de listas ranqueadas, o qual apresenta uma melhor eficácia em tarefas Capítulo 4. Aprendizado Fracamente Supervisionado Baseado em Hipergrafos 47 de ranqueamento. Deste modo, ambas a entrada e saída do modelo de hipergrafo são criadas com base na informação dos ranques, e os cálculos podem ser repetidos iterativamente para obter ranques e representações por hipergrafo cada vez mais eficazes. A notação (t) vai ser utilizada para representar a iteração atual do algoritmo. O conjunto de listas ranqueadas T (t+1) é calculado através da matriz de similaridade W(t) e o conjunto T (0) é construído a partir dos vetores de características iniciais. O processo é repetido ao longo de T iterações e o hipergrafo e estruturas relacionadas (a matriz W(T )) finais são utilizados no processo de expansão de rótulos, detalhado a seguir. 4.2 Expansão de Conjuntos Rotulados por Hipergrafos Como o método LHRR [19] cria um hipergrafo e estruturas capazes de fornecer informações mais eficazes com relação à similaridade entre itens de dados, o método de expansão de conjuntos rotulados que será discutido ao longo dessa seção explora das informações codificadas em tais estruturas. A informação presente nas hiperarestas vai ser explorada de modo a construir um conjunto de pares, que representa os candidatos a expansão de rótulos. Os pares de candidatos são ordenados com base no peso das hiperarestas e na similaridade entre os elementos. Os pares nas primeiras posições são então selecionados com base em um limiar de posição, de modo a compor o conjunto expandido. Cada passo do método de expansão será detalhado a seguir. A) Conjunto de Candidatos para a Expansão de Rótulos: Para cada item rotulado xl ∈ XL um conjunto de candidatos é definido pelos itens não rotulados com os maiores valores na hiperaresta de xl. Formalmente, seja Nh(xl, ke) um conjunto que contêm os ke maiores valores de h(·, ·) em sua respectiva hiperaresta exl (Equação 4.4). Portanto, podemos definir um conjunto de candidados não rotulados para cada item rotulado, dado por Nc(xl, ke), como: Nc(xq, ke) = {S ⊆ e(T ) q , |S| ≤ ke ∧ ∀xi ∈ S, xj ∈ e(T ) q − S : h(T )(xq, xi) > h(T )(xq, xj)}. (4.13) Um conjunto de pares de candidatos é então gerado considerando todo o conjunto de dados, a partir da união dos conjuntos de cada item rotulado. Sendo assim, o conjunto de pares de candidatos Cp pode ser definido como: Cp = ⋃ xl∈XL ⋃ xu∈Nc(xl,ke) {(xl, xu)}. (4.14) Capítulo 4. Aprendizado Fracamente Supervisionado Baseado em Hipergrafos 48 B) Ranque de Pares de Candidatos: Dado o conjunto de pares de candidatos Cp, queremos selecionar um subconjunto de pares que será utilizado nos procedimentos de expansão. Portanto, os pares são ordenados conforme o grau de confiança da hiperaresta que gerou o par (a hiperaresta do elemento rotulado) e com a similaridade entre os elementos (rotulado e não rotulado). O grau de confiança é obtido através do peso da hiperaresta do item rotulado w(T )(exl ), já a similaridade entre os itens rotulados e não rotulados é obtida pelo valor na matriz de similaridade W(T ) xl,xu . O ranque de pares de candidatos τC pode ser definido como uma permutação do con- junto Cp. A permutação τC é uma bijeção do conjunto Cp no conjunto {1, 2, . . . , |Cp|}. A posição do par (xl, xu) na lista ranqueada de pares de candidatos é indicada por τC((xl, xu)). O ranque τC é calculado de acordo com uma função sc(., .) a qual consi- dera informações de confiança e similaridade. Se no ranque de pares de candidatos (xl, xu) está em uma posição anterior a (xi, xj), isto é, τC((xl, xu)) < τC((xi, xj)), então sc(xi, xj) ≥ sc(xi, xj). Formalmente, podemos definir a função sc(., .) como: sc(xl, xu) = w(T )(exl )×W(T ) xl,xu (4.15) C) Seleção dos Pares de Candidatos: Assim que a lista ranqueada de pares de candidatos estiver construída, é necessário definir qual conjunto de pares participará do processo de expansão. Essa seleção será feita com base nas primeiras posições de τC até uma posição limite tp. O número de amostras selecionadas é proporcional ao tamanho do conjunto rotulado e ao tamanho de vizinhança ke: tp = |XL| × ke × α, (4.16) onde α é um parâmetro chamado taxa de expansão de rótulos, definido no intervalo [0, 1], que define a porcentagem de amostras selecionadas para a expansão. Uma estratégia para estimar o valor de α será discutida na Seção 4.3. D) Expansão de Conjuntos Rotulados: A partir do ranque τC e da posição limite tp, o conjunto rotulado estimado XE pode ser definido como: XE = {xe : xe ∈ XU |(xe, xl) ∈ Cp ∧ xl ∈ XL ∧ τC((xe, xl)) ≤ tp} (4.17) Assim que o conjunto rotulado estimado XE é gerado, a classe estimada do item xe será a mesma do item rotulado xl do seu par. Elementos do conjunto estimado que aparecem no conjunto de pares de candidatos em pares com imagens de diferentes classes são removidos, de modo a remover inconsistências (uma mesma imagem ter Capítulo 4. Aprendizado Fracamente Supervisionado Baseado em Hipergrafos 49 dois rótulos diferentes atribuídos). Sendo assim, podemos definir uma função de estimativa de rótulos baseada na informação de hipergrafos HE como: EH(xe) = Y (xl), (4.18) onde xe ∈ XE and (xe, xl) ∈ Cp. O conjunto rotulado expandido pode ser então definido pela união do conjunto rotulado original e do conjunto rotulado estimado: XW = XL ∪ XE. (4.19) Por fim, o conjunto XW será utilizado no treinamento de classificadores supervisio- nados ou semi-supervisionados. A Figura 16 ilustra como a expansão de conjuntos rotulados baseada em hipergrafos é feita. Começando com um pequeno conjunto rotulado são gerados conjuntos de candidatos não rotulados Nc(xq, ke) que contêm os maiores valores de h(·, ·) nas hiperarestas dos itens rotulados exl . No nosso exemplo, criamos conjuntos de candidatos a partir dos itens rotulados xl1 e xl2 com os ke = 3 maiores valores em suas respectivas hiperarestas. Isto irá criar um conjunto de pares de candidatos Cp que será utilizado para gerar um ranque τC considerando informações em ambas as hiperarestas e na matriz de similaridade W (Equação 4.15). A seguir, são selecionados os pares de candidatos do ranque τC na posição limite tp. Considerando os parâmetros especificados no exemplo: ke = 3, α = 0.5 e |XL| = 2, temos que tp = 3. A última etapa do método é estimar a classe de cada entrada selecionada em τC, a qual será a classe do item rotulado que gerou aquela entrada, por exemplo, o item não rotulado xu9 terá atribuída a classe do item rotulado xl1 . Além disso, caso alguma entrada apresente itens rotulados associados a diferentes classes, indicam cenários de baixa confiança e são removidos para que não sejam atribuídos rótulos diferentes a um mesmo item. Por fim, o conjunto de treino expandido XW é criado, o qual será utilizado para treinamento de classificadores supervisionados os semi-supervisionados. 4.3 Definição da Taxa de Expansão de Rótulos A fim de que o método de expansão baseado em hipergrafos opere de forma eficaz é necessário utilizar um valor adequado para a uma taxa de expansão de rótulo (α). Caso utilizemos de uma taxa de expansão de rótulos muito alta, uma quantidade alta de falsos positivos de τC podem ser selecionados para a expansão, o que diminuirá a acurácia obtida pelos classificadores. Por outro lado, caso o valor de α seja muito baixo, expansões com um número reduzido de amostras podem ocorrer, ocasionando impacto reduzido nos resultados de classificação se compararmos com o cenário sem expansão. Sendo assim, esta seção apresenta uma maneira de estimar o valor de α. Capítulo 4. Aprendizado Fracamente Supervisionado Baseado em Hipergrafos 50 Figura 16 – Ilustração do método de expansão de conjuntos rotulados baseado em hipergrafos. Primeiros k elemento da hiperaresta : peso da hiperaresta do item rotulado : valor na matriz de similaridade W Primeiros k elemento da hiperaresta União dos conjuntos gerados considerando a operação:Parâmetros Dados Não RotuladosDados Rotulados Conjunto de Treino Expandido Fonte: Elaborado pelo autor. A ideia central consiste em definir a magnitude de α de acordo com a eficácia das listas ranqueadas do conjunto de dados. Para os dados rotulados, o método irá analisar a eficácia a partir da quantidade de itens de dados da mesma classe nas primeiras posições das listas ranqueadas. O método também considera a análise dos dados não rotulados a partir das estruturas geradas durante a construção do hipergrafo para auxiliar na definição do parâmetro. A primeira etapa para estimar o parâmetro é analisar os dados rotulados, gerando um parâmetro αl intermediário. Para cada xl ∈ XL, será calculada a porcentagem de vizinhos da mesma classe de xl no conjunto de vizinhança correspondente. Formalmente, essa porcentagem é obtida pela função pc(xl): pc(xl) = |{xc : xc ∈ N (xl, ke) ∩ XL ∧ Y (xc) = Y (xl)}| |{xm : xm ∈ N (xl, ke) ∩ XL}| . (4.20) A taxa αl é definida pela porcentagem média ao analisar o conjunto rotulado XL: αl = 1 |XL| ∑ xl∈XL pc(xl). (4.21) A segunda parte do método irá estimar outro parâmetro αu intermediário, calculado com base no grau de confiança médio obtido por sc(., .) para os pares de candidatos Cp. Seja S um conjunto de valores de confiança definido por: S = {sc(xl, xu) ∈ R|(xl, xu) ∈ Cp}. Feito isso, será realizada uma normalização min-max sobre o conjunto S, gerando um Capítulo 4. Aprendizado Fracamente Supervisionado Baseado em Hipergrafos 51 conjunto S̄, que será utilizado para gerar o parâmetro αu, a média dos valores do novo conjunto: αu = 1 |S̄| ∑ s̄i∈S̄ s̄i. (4.22) Por fim, a taxa de expansão de rótulos α estimada é definida como a média entre os parâmetros intermediários αl e αu: α = 1 2(αl + αu). (4.23) 52 5 Avaliação Experimental Este capítulo apresenta a avaliação experimental realizada para aferir a eficácia de ambos os métodos