[pt] Métodos ensemble como random forest, boosting e bagging foram extensivamente
estudados e provaram ter uma acurácia melhor do que usar apenas
um preditor. Entretanto, a desvantagem é que os modelos obtidos utilizando
esses métodos podem ser muito mais difíceis de serem interpretados do que por
exemplo, uma árvore de decisão. Neste trabalho, nós abordamos o problema de
construir uma árvore de decisão que aproximadamente reproduza um conjunto
de árvores, explorando o tradeoff entre acurácia e interpretabilidade, que pode
ser alcançado quando a reprodução exata do conjunto de árvores é relaxada.
Primeiramente, nós formalizamos o problem de obter uma árvore de decisão
de uma determinada profundidade que seja a mais aderente ao conjunto
de árvores e propomos um algoritmo de programação dinâmica para resolver
esse problema. Nós também provamos que a árvore de decisão obtida por esse
procedimento satisfaz garantias de generalização relacionadas a generalização
do modelo original de conjuntos de árvores, um elemento crucial para a efetividade
dessa árvore de decisão em prática. Visto que a complexidade computacional
do algoritmo de programação dinâmica é exponencial no número
de features, nós propomos duas heurísticas para gerar árvores de uma determinada
profundidade com boa aderência em relação ao conjunto de árvores.
Por fim, nós conduzimos experimentos computacionais para avaliar os
algoritmos propostos. Quando utilizados classificadores mais interpretáveis, os
resultados indicam que em diversas situações a perda em acurácia é pequena
ou inexistente: restrigindo a árvores de decisão de profundidade 6, nossos
algoritmos produzem árvores que em média possuem acurácias que estão a
1 por cento (considerando o algoritmo de programção dinâmica) ou 2 por cento (considerando os algoritmos heurísticos) do conjunto original de árvores. / [en] Ensemble methods in machine learning such as random forest, boosting,
and bagging have been thoroughly studied and proven to have better accuracy
than using a single predictor. However, their drawback is that they give models
that can be much harder to interpret than those given by, for example, decision
trees. In this work, we approach in a principled way the problem of constructing
a decision tree that approximately reproduces a tree ensemble, exploring the
tradeoff between accuracy and interpretability that can be obtained once exact
reproduction is relaxed.
First, we formally define the problem of obtaining the decision tree of a
given depth that is most adherent to a tree ensemble and give a Dynamic
Programming algorithm for solving this problem. We also prove that the
decision trees obtained by this procedure satisfy generalization guarantees
related to the generalization of the original tree ensembles, a crucial element
for their effectiveness in practice. Since the computational complexity of the
Dynamic Programming algorithm is exponential in the number of features, we
also design heuristics to compute trees of a given depth with good adherence
to a tree ensemble.
Finally, we conduct a comprehensive computational evaluation of the
algorithms proposed. The results indicate that in many situations, there is little
or no loss in accuracy in working more interpretable classifiers: even restricting
to only depth-6 decision trees, our algorithms produce trees with average
accuracies that are within 1 percent (for the Dynamic Programming algorithm) or
2 percent (heuristics) of the original random forest.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:55539 |
| Date | 28 October 2021 |
| Contributors | MARCO SERPA MOLINARO, MARCO SERPA MOLINARO, MARCO SERPA MOLINARO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | English |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0022 seconds