Português English
Contato

Defesa de Dissertação de Mestrado de Henrique Lemos dos Santos


Detalhes do Evento


Aluno: Henrique Lemos dos Santos
Orientador: Prof. Dr. Luis da Cunha Lamb

Título: Resolvendo a versão de decisão do problema de coloração de grafos: uma abordagem neuro-simbólica usando redes grafo-neurais.
Linha de Pesquisa: Aprendizado de Máquina, Representação de Conhecimento e Raciocínio

Data: 06/04/2020
Horário: 10h

Esta banca ocorrerá excepcionalmente de forma totalmente remota. Interessados em assistir a defesa poderão acessar a sala virtual através do link: https://mconf.ufrgs.br/webconf/00300205.

Banca Examinadora:
– Prof. Dr. Rodrigo Coelho Barros (PUCRS)
– Profa. Dra. Viviane Pereira Moreira (UFRGS)
– Prof. Dr. Leandro Krug Wives (UFRGS)

Presidente da Banca: Prof. Dr. Luis da Cunha Lamb (lamb@inf.ufrgs.br)

Resumo: Técnicas baseadas em aprendizado profundo têm recorrentemente atingido desempenho de estado-da-arte em diversas áreas ao longo dos últimos anos. Ainda há, no entanto, uma certa falta de compreensão em como problemas simbólicos e relacionais podem se beneficiar de modelos cuja arquitetura é baseada em aprendizado profundo. O caminho mais promissor para essa tão desejada integração consiste em arquiteturas neurais cuja propriedade de compartilhamento de parâmetros baseia-se em grafos e, dessa forma, podem ser treinadas para aprender características complexas de dados relacionais. Diversos problemas NP-Completos, tais como satisfatibilidade booleana e problema do caixeiro viajante, apresentam esse tipo de característica. Em ambos casos, um metamodelo chamado Graph Neural Network (GNN) pode trabalhar diretamente com entradas em formato de grafos, que representam uma instância do problema, e aprender a produzir uma resposta binária para o problema em questão. Nessa dissertação, estamos particularmente focados em aplicar um modelo de GNN ao problema da coloração de grafos: o modelo que propomos se aproveita de propriedades específicas desse problema ao contemplar tanto vértices quanto cores com representações internas na sua arquitetura e ao fazer com que tais representações passem por diversas etapas de troca de mensagens. Nesse sentido, a arquitetura que propomos é capaz de refletir a estrutura relacional do problema original, sem necessidade de uma redução em tempos polinomial para outro problema, enquanto ainda emprega uma estratégia de compartilhamento de parâmetros em função de vértices e cores. Nós também demonstramos como treinar tal modelo com instâncias muito difíceis, geradas de uma maneira adversarial: nós geramos pares de instâncias que são grafos no limite da satisfatibilidade — uma instância positiva e outra negativa que diferem apenas por uma única aresta, tal aresta faz com que a segunda instância não seja colorável por um dado número de cores C, enquanto a primeira permanece sendo minimamente colorável com C. Obtivemos uma acurácia de 83% durante treinamento e verificamos que nosso modelo é capaz de generalizar, até certo ponto, esse desempenho para instâncias de teste — não-vistas durante treinamento e que foram amostradas de diferentes distribuições. Nós mostramos que esse desempenho superou o desempenho de duas heurísticas e o desempenho de uma suposta abordagem neuro-simbólica generalista. Por fim, nós exploramos a memória interna do nosso modelos e encontramos evidências de como o seu raciocínio é construído em volta dos valores de representação de vértices e cores. Em suma, nossos resultados sugerem fortemente que GNNs são, de fato, ferramentas poderosas para resolver problemas combinatoriais mas que seu aprendizado pode ser amplamente melhorado quando as propriedades de um problema são totalmente agregadas à arquitetura neural e nenhuma conversão de problema é feita.
Palavras-chave: redes neurais profundas, redes neurais recorrentes, redes grafo-neurais, grafos, coloração de grafos, computação neuro-simbólica.