[en] DECISION TREES WITH EXPLAINABLE RULES

[pt] ÁRVORES DE DECISÃO COM REGRAS EXPLICÁVEIS

[pt] VICTOR FEITOSA DE CARVALHO SOUZA

[pt] APRENDIZADO DE MAQUINA

[pt] MODELO EXPLICAVEL

[pt] ALGORITMOS DE APROXIMACAO

[pt] ARVORE DE DECISAO

[pt] CLASSIFICACAO

[en] MACHINE LEARNING

[en] EXPLAINABLE MODEL

[en] APPROXIMATION ALGORITHMS

[en] DECISION TREE

[en] CLASSIFICATION

[pt] As árvores de decisão são estruturas comumente utilizadas em cenários nos quais modelos explicáveis de Aprendizado de Máquina são desejados, por serem visualmente intuitivas. Na literatura existente, a busca por explicabilidade em árvores envolve a minimização de métricas como altura e número de nós. Nesse contexto, definimos uma métrica de explicabilidade, chamada de explanation size, que reflete o número de atributos necessários para explicar a classificação dos exemplos. Apresentamos também um algoritmo, intitulado SER-DT, que obtém uma aproximação O(log n) (ótima se P diferente NP) para a minimização da altura no pior caso ou caso médio, assim como do explanation size no pior caso ou caso médio. Em uma série de experimentos, comparamos a implementação de SER-DT com algoritmos conhecidos da área, como CART e EC2, além de testarmos o impacto de parâmetros e estratégias de poda nesses algoritmos. SER-DT mostrou-se competitivo em acurácia com os algoritmos citados, mas gerou árvores muito mais explicáveis.

[en] Decision trees are commonly used structures in scenarios where explainable Machine Learning models are desired, as they are visually intuitive. In the existing literature, the search for explainability in trees involves minimizing metrics such as depth and number of nodes. In this context, we define an explainability metric, called explanation size, which reflects the number of attributes needed to explain the classification of examples. We also present an algorithm, called SER-DT, which obtains an O(log n) approximation (optimal if P different NP) for the minimization of depth in the worst/average case, as well as of explanation size in the worst/average case. In a series of experiments, we compared the SER-DT implementation with well-known algorithms in the field, such as CART and EC2 in addition to testing the impact of parameters and pruning strategies on these algorithms. SER-DT proved to be competitive in terms of accuracy with the aforementioned algorithms, but generated much more explainable trees.

EDUARDO SANY LABER

MARCO SERPA MOLINARO

EDUARDO SANY LABER

CLAUDSON FERREIRA BORNSTEIN

2023-08-04

2023-03-15

[pt] TEXTO

application/pdf

PORTUGUÊS

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=63537@1

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=63537@2

https://doi.org/10.17771/PUCRio.acad.63537