[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. / [en] Decision diagrams are a generalization of decision trees. They have
been repeatedly proposed as a supervised classification model for machine
learning but have not been widely adopted. The reason appears to be the
difficulty of training the model, as the requirement of deciding splits and
merging nodes can lead to difficult combinatorial optimization problems.
A decision diagram has marked advantages over decision trees because it
better models disjoint binary concepts, avoiding the replication of subtrees
and thus has less sample fragmentation in internal nodes. Because of this,
devising an effective construction algorithm is important. In this context, the
Optimal Decision Diagram (ODD) algorithm was recently proposed, which
formulates the problem of building a diagram as a mixed-integer linear program
(MILP), with a warm start provided by a greedy constructive heuristic. Initial
experiments have shown that this heuristic can be improved upon, in order
to find close-to-optimal solutions more effectively and in turn provide the
MILP with a better warm start. In this study, we report improvements to this
constructive heuristic, by randomizing the split decisions, pruning pure flows
(i.e. flows with samples from a single class), and applying bottom-up pruning,
which considers the complexity of the model in addition to its accuracy. All
proposed improvements have positive effects on accuracy and generalization,
as well as the objective value of the ODD algorithm. The bottom-up pruning
strategy, in particular, has a substantial impact on the objective value, and
thus on the ability of the MILP solver to find optimal solutions. In addition, we
provide experiments on the expressiveness of decision diagrams when compared
to trees in the context of small boolean functions in Disjoint Normal Form
(DNF), as well as a web application for the visual exploration of the proposed
constructive approaches.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:64308 |
| Date | 16 October 2023 |
| Creators | PEDRO SARMENTO BARBOSA MARTINS |
| Contributors | THIBAUT VICTOR GASTON VIDAL |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | English |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0021 seconds