[en] DECISION DIAGRAMS FOR CLASSIFICATION: NEW CONSTRUCTIVE APPROACHES

• Ano de defesa: 2023
• Autor(a) principal: PEDRO SARMENTO BARBOSA MARTINS
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] APRENDIZADO DE MAQUINA; [pt] CLASSIFICACAO; [pt] DIAGRAMA DE DECISAO; [pt] ARVORE DE DECISAO; [en] MACHINE LEARNING; [en] RECOGNITION; [en] DECISION DIAGRAM; [en] DECISION TREE
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=64308&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=64308&idi=2; http://doi.org/10.17771/PUCRio.acad.64308

[pt] Diagramas de decisão são uma generalização de árvores de decisão, já propostos como um modelo de aprendizado de máquina para classificação supervisionada mas não largamente adotados. A razão é a dificuldade em treinar o modelo, já que o requerimento de decidir splits (partições) e merges (uniões de nós) em conjunto pode levar a problemas difíceis de otimização combinatória. Um diagrama de decisão tem importantes vantagens sobre árvores de decisão, pois melhor expressa conceitos binários disjuntos, evitando o problema de duplicação de subárvores e, portanto, apresentando menos fragmentação em nós internos. Por esse motivo, desenvolver algoritmos efetivos de construção é um esforço importante. Nesse contexto, o algoritmo Optimal Decision Diagram (ODD) foi recentemente proposto, formulando a construção do diagrama com programação inteira mista (MILP na sigla em inglês), com um warm start proveniente de uma heurística construtiva gulosa. Experimentos mostraram que essa heurística poderia ser aperfeiçoada, a fim de encontrar soluções próximas do ótimo de maneira mais efetiva, e por sua vez prover um warm start melhor. Nesse estudo, reportamos aperfeiçoamentos para essa heurística construtiva, sendo eles a randomização das decisões de split, a poda de fluxos puros (ou seja, fluxos de exemplos pertencentes a uma única classe), e aplicando uma poda bottom-up (de baixo para cima), que considera a complexidade do modelo além da sua acurácia. Todos os aperfeiçoamentos propostos têm efeitos positivos na acurácia e generalização, assim como no valor objetivo do algoritmo ODD. A poda bottom-up, em especial, tem impacto significativo no valor objetivo, e portanto na capacidade da formulação MILP de encontrar soluções ótimas. Ademais, provemos experimentos sobre a expressividade de diagramas de decisão em comparação a árvores no contexto de pequenas funções booleanas em Forma Normal Disjuntiva (DNF na sigla em inglês), assim como uma aplicação web para a exploração visual dos métodos construtivos propostos.