Detalhes bibliográficos
Ano de defesa: |
2020 |
Autor(a) principal: |
Santos, Henrique Lemos dos |
Orientador(a): |
Lamb, Luis da Cunha |
Banca de defesa: |
Não Informado pela instituição |
Tipo de documento: |
Dissertação
|
Tipo de acesso: |
Acesso aberto |
Idioma: |
eng |
Instituição de defesa: |
Não Informado pela instituição
|
Programa de Pós-Graduação: |
Não Informado pela instituição
|
Departamento: |
Não Informado pela instituição
|
País: |
Não Informado pela instituição
|
Palavras-chave em Português: |
|
Palavras-chave em Inglês: |
|
Link de acesso: |
http://hdl.handle.net/10183/211255
|
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. |