Tratamento bayesiano de interações entre atributos de alta cardinalidade

Orientador: Jacques Wainer Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Analisamos o uso de métodos Bayesianos em um problema de classificação de padrões de interesse prático para a Receita Federal do Brasil que é caracterizado pela presença de atributos de alta cardinalidade e pela existência de interações relevantes entre eles. Mostramos que a presença de atributos de alta cardinalidade pode facilmente gerar tantas subdivisões no conjunto de treinamento que, mesmo tendo originalmente uma grande quantidade de dados, acabemos obtendo probabilidades pouco confiáveis, inferidas a partir de poucos exemplos. Revisamos as estratégias usualmente adotadas para lidar com esse problema dentro do universo Bayesiano, exibindo sua dependência em suposições de não interação inaceitáveis em nosso domínio alvo. Mostramos empiricamente que estratégias Bayesianas mais avançadas para tratamento de atributos de alta cardinalidade, como pré-processamento para redução de cardinalidade e substituição de tabelas de probabilidades condicionais (CPTs) de redes Bayesianas (BNs) por tabelas default (DFs), árvores de decisão (DTs) e grafos de decisão (DGs) embora tragam benefícios pontuais não resultam em ganho de desempenho geral em nosso domínio alvo. Propomos um novo método Bayesiano de classificação, chamado de hierarchical pattern Bayes (HPB), que calcula probabilidades posteriores para as classes dado um padrão W combinando as observações de W no conjunto de treinamento com probabilidades prévias que são obtidas recursivamente a partir das observações de padrões estritamente mais genéricos que W. Com esta estratégia, ele consegue capturar interações entre atributos de alta cardinalidade quando há dados suficientes para tal, sem gerar probabilidades pouco confiáveis quando isso não ocorre. Mostramos empiricamente que, em nosso domínio alvo, o HPB traz benefícios significativos com relação a redes Bayesianas com estruturas populares como o naïve Bayes e o tree augmented naïve Bayes, com relação a redes Bayesianas (BNs) onde as tabelas de probabilidades condicionais foram substituídas pelo noisy-OR, por DFs, por DTs e por DGs, e com relação a BNs construídas, após uma fase de redução de cardinalidade usando o agglomerative information bottleneck. Além disso, explicamos como o HPB, pode substituir CPTs e mostramos com testes em outro problema de interesse prático que esta substituição pode trazer ganhos significativos. Por fim, com testes em vários conjuntos de dados públicos da UCI, mostramos que a utilidade do HPB ser bastante ampla Abstract: In this work, we analyze the use of Bayesian methods in a pattern classification problem of practical interest for Brazil¿s Federal Revenue which is characterized by the presence of high cardinality attributes and by the existence of relevant interactions among them.We show that the presence of high cardinality attributes can easily produce so many subdivisions in the training set that, even having originally a great amount of data, we end up with unreliable probability estimates, inferred from small samples. We cover the most common strategies to deal with this problem within the Bayesian universe and show that they rely strongly on non interaction assumptions that are unacceptable in our target domain. We show empirically that more advanced strategies to handle high cardinality attributes like cardinality reduction by preprocessing and conditional probability tables replacement with default tables, decision trees and decision graphs, in spite of some restricted benefits, do not improve overall performance in our target domain. We propose a new Bayesian classification method, named hierarchical pattern Bayes (HPB), which calculates posterior class probabilities given a pattern W combining the observations of W in the training set with prior class probabilities that are obtained recursively from the observations of patterns that are strictly more generic than W. This way, it can capture interactions among high cardinality attributes when there is enough data, without producing unreliable probabilities when there is not. We show empirically that, in our target domain, HPB achieves significant performance improvements over Bayesian networks with popular structures like naïve Bayes and tree augmented naïve Bayes, over Bayesian networks where traditional conditional probability tables were substituted by noisy-OR gates, default tables, decision trees and decision graphs, and over Bayesian networks constructed after a cardinality reduction preprocessing phase using the agglomerative information bottleneck method. Moreover, we explain how HPB can replace conditional probability tables of Bayesian Networks and show, with tests in another practical problem, that such replacement can result in significant benefits. At last, with tests over several UCI datasets we show that HPB may have a quite wide applicability Doutorado Sistemas de Informação Doutor em Ciência da Computação