Evolução Gramatical Para Construção Automática De Funções De Similaridade No Contexto De Aprendizado Semissupervisionado
Data
2017-07-25
Autores
Miquilini, Patricia 
Orientadores
Basgalupp, Marcio Porto
Tipo
Dissertação de mestrado
Título da Revista
ISSN da Revista
Título de Volume
Resumo
In the context of machine learning, representing a dataset with graphs have been studied in the literature, especially in the field of semi-supervised learning. The principal feature of the techniques based on graphs (networks) is the way data is represented, in which network vertices represent the data and the edges represent the distances (relations) between the examples. In the context of building graphs for representing semi-supervised machine learning problems, different distance (or similarity) functions are used, such as Euclidean, Manhattan, among others. Distance functions can be considered as a metric when they meet the prop erties: non-negativity, coincidence, symmetry and subadditivity. Distance Metric Learning is an area that is designed to automatically build custom distance metrics for sp ecific problems. S tudies rep ort that satisfying metric properties is desirable, but it is not critical. One of the sub-areas of evolutionary algorithms, the Grammatical Evolution (GE) has emerged as a proper technique to develop mathematical functions. An automatically evolved function can not only produce the same solution developed by a human to solve a particular problem, but is also able to produce something entirely new and possibly better. In this context, this project proposes to use Grammatical Evolution to automatically evolve functions to be used in graph construction to represent datasets in the semi-supervised learning context. The algorithm develop ed is named GEAD (Grammatical Evolution for Automatically Design Dissimilarity functions for graph-based semi-supervised learning). Experiments were performed on 100 datasets and for performance analysis, the performance of the algorithm was compared with the performance of literature functions (Euclidiana, Manhattan and Chebyshev). The results shows that the algorithm developed can be an efficient alternative for the construction of distance functions, due to the excellent performance in relation to the functions of the literature.
No contexto de Aprendizado de Máquina, a representação de conjuntos de dados p or meio de grafos tem sido bastante estudada na literatura, em especial na área de aprendizado semissupervisionado. U ma das características principais das técnicas baseadas em grafos (redes) está na forma como os dados são representados, na qual os vértices da rede representam os dados e as arestas representam as similaridades/dissimilaridades (relações) entre os exemplos. No contexto d e construção de grafos para representação de problemas de aprendizado de máquina semissupervisionado, diversas funções de dissimilaridade são utilizadas, tais como distância Euclidiana, Manhattan, d entre outras. As funções de distância podem ser consideradas métricas quando atendem as propriedades de (i) não negatividade; (ii) coincidência; (iii) simetria; e (iv) desigualdade triangular. O aprendizado de métricas de distância (Metric Learning) é uma área que destina-se à construção automática de métricas de distância personalizadas para problemas específicos. Estudos relatam, no entanto, que satisfazer as propriedades de métrica é desejável porém não fundamental. Uma das subáreas de algoritmos evolutivos, a Evolução Gramatical (EG) tem se destacado como técnica adequada para evoluir funções matemáticas. Uma função evoluída automaticamente pode não apenas produzir a mesma solução desenvolvida “manualmente” por um humano para solucionar um determinado problema, mas também é capaz de produzir algo completamente novo e eficaz. Nesse contexto, a proposta deste projeto visa desenvolver um algoritmo para construção automática de medidas de dissimilaridade baseada em evolução gramatical para serem utilizadas na construção de grafos para representação de conjuntos de dados no contexto de aprendizado semissupervisionado. O algoritmo desenvolvido, foi nomeado por GEAD (Grammatical Evolution for Automatically design Dissimilarity functions for graph-based semi-supervised learning ). Foram realizados experimentos em 100 conjuntos de dados e para análise dos resultados, o desempenho do algoritmo foi comparado com funções da literatura (Euclidiana, Manhattan e Chebyshev). Os resultados indicam que o algoritmo desenvolvido pode ser uma alternativa eficiente para construção de funções de distância, diante do desempenho superior em relação às funções da literatura.
No contexto de Aprendizado de Máquina, a representação de conjuntos de dados p or meio de grafos tem sido bastante estudada na literatura, em especial na área de aprendizado semissupervisionado. U ma das características principais das técnicas baseadas em grafos (redes) está na forma como os dados são representados, na qual os vértices da rede representam os dados e as arestas representam as similaridades/dissimilaridades (relações) entre os exemplos. No contexto d e construção de grafos para representação de problemas de aprendizado de máquina semissupervisionado, diversas funções de dissimilaridade são utilizadas, tais como distância Euclidiana, Manhattan, d entre outras. As funções de distância podem ser consideradas métricas quando atendem as propriedades de (i) não negatividade; (ii) coincidência; (iii) simetria; e (iv) desigualdade triangular. O aprendizado de métricas de distância (Metric Learning) é uma área que destina-se à construção automática de métricas de distância personalizadas para problemas específicos. Estudos relatam, no entanto, que satisfazer as propriedades de métrica é desejável porém não fundamental. Uma das subáreas de algoritmos evolutivos, a Evolução Gramatical (EG) tem se destacado como técnica adequada para evoluir funções matemáticas. Uma função evoluída automaticamente pode não apenas produzir a mesma solução desenvolvida “manualmente” por um humano para solucionar um determinado problema, mas também é capaz de produzir algo completamente novo e eficaz. Nesse contexto, a proposta deste projeto visa desenvolver um algoritmo para construção automática de medidas de dissimilaridade baseada em evolução gramatical para serem utilizadas na construção de grafos para representação de conjuntos de dados no contexto de aprendizado semissupervisionado. O algoritmo desenvolvido, foi nomeado por GEAD (Grammatical Evolution for Automatically design Dissimilarity functions for graph-based semi-supervised learning ). Foram realizados experimentos em 100 conjuntos de dados e para análise dos resultados, o desempenho do algoritmo foi comparado com funções da literatura (Euclidiana, Manhattan e Chebyshev). Os resultados indicam que o algoritmo desenvolvido pode ser uma alternativa eficiente para construção de funções de distância, diante do desempenho superior em relação às funções da literatura.