Redes Bayesianas e Aplicações

Classificadores Bayesianos

3.1 Classificação Bayesiana

Seja \(\mathbf{X}\) um vetor aleatório de entrada de ordem \(p\), sendo suas componentes expressas por \(X_i\), \(i\)-ésima variável explicativa assumindo o valor \(x_i\), \(\mathbf{x}=\{x_1,\ldots,x_p\}\), bem como \(Y\) sendo uma variável aleatória categórica de saída, assumindo o valor \(y \in \{ 1,\ldots, c\}\).

Desta forma, a tarefa de classificação pode ser definida como

\[\underset y {\arg\max} \text{ } \left\{ P(Y=y|\mathbf{X}=\mathbf{x})=P(Y=y)\frac{P(\mathbf{X=\mathbf{x}}|Y=y)}{P(\mathbf{X=\mathbf{x}})} \right\}.\]

Uma vez que \(P(\mathbf{X=\mathbf{x}})\) é independente de \(Y\), particularmente temos \(\underset y {\arg\max} \text{ } P(\mathbf{X}=\mathbf{x},Y=y)\). Isto é, desejamos verificar para qual valor \(y\), dado \(\mathbf{x}\) conhecido, a conjunta assume valor máximo.

Dado um conjunto de dados com \(n\) observações independentes de \(P(\mathbf{X},Y)\), expresso por \(\{ (\mathbf{x}_i,y_i) \}^{n}_{i=1}\), desejamos encontrar um modelo capaz de estimar \(P(\mathbf{X},Y)\) de forma conveniente. Ou seja, classificar com acertividade uma nova observação de \(\mathbf{X}\) para a categoria mais plausível em \(Y\). Modelos capazes de realizar essa tarefa são chamados de classificadores e são métodos baseados em propor

\[\underset y {\arg\max} \text{ } \hat{P}(Y=y|\mathbf{X}=\mathbf{x}),\]

sendo \(\hat{P}\) a distribuição estimada via o conjunto \(\{ (\mathbf{x}_i,y_i) \}^{n}_{i=1}\).

Em suma, o método se baseia em calcular a probabilidade de uma nova observação \(x\) e predize-la, isto é, classificá-la, para uma das categorias \(\{ 1,\ldots, c\}\).

A decomposição direta de \(P(\mathbf{X},Y)\), ou \(\hat{P}(\mathbf{X},Y)\), via o teorema de Bayes resulta em um problema computacionalmente exaustivo. Isso ocorre pois o número de parâmetros na verossimilhança, \(P(\mathbf{X}| Y)\), aumenta de forma exponencial com o aumento do número de variáveis de entrada.

Desta forma, a fatoração da distribuição conjunta, como vista anteriormente, pode auxiliar na proposta de bons classificadores. Para um contexto específico de tarefas de classificação, as redes bayesianas podem ser vistas como estruturas particulares e conhecidas como classificadores bayesianos (Friedman, Geiger, e Goldszmidt 1997).

Por definição, os classificadores bayesianos também são grafos acíclicos direcionados e seus parâmetros são estimados como visto anteriormente. No entanto, devido a forma de fatoração realizada da distribuição conjunta, não possuem interpretação direta sobre a influência das variáveis. Neste texto, consideramos quatro classificadores bayesianos popularmente conhecidos: Naïve Bayes, TAN, KDB e AODE.

Alguns procedimentos de estimação destes classificadores utilizam alguns conceitos, expostos na seção seguinte.

3.1.1. Medidas de informação

Desenvolvidas em um ramo da teoria da probabilidade e matemática estatística que trata de problemas relacionados à comunicação denominada Teoria da Informação (Shannon (1948)). Por conveniência essas medidas são apresentadas para o caso discreto, sendo análogas para o caso contínuo.

Informação Mútua: Medida da dependência entre as duas variáveis, mensura a quantidade de informação que uma variável aleatória possui em comum outra. Definida por:

\[I(X_i,X_j)=\sum_{i}\sum_{j}p(x_i,x_j)\log\frac{p\left(x_i,x_j\right)}{p\left(x_i\right)p\left(x_j\right)}.\]

Informação Mútua Condicional: Expressa a informação mútua de duas variáveis aleatórias condicionadas a um terceiro vetor aleatório. Seja \(Z\) um vetor aleatório, esta medida é definida por

\[ \begin{aligned} I(X_i,X_j|Z)&=E_z\left(I(X_i,X_j|Z=z)\right)\\ &=\sum_{z}\sum_{x}\sum_{y}p(z)p(x_i,x_j|z)\log\frac{p\left(x_i,x_j|z\right)}{p\left(x_i|z\right)p\left(x_j|z\right)}.\\ \end{aligned} \]

Ambas as medidas acima citadas são não negativas e simétricas, bem como estão intrinsicamente vinculadas ao conceito de Entropia de uma variável aleatória.

3.2 Naïve Bayes (NB)

O Naïve Bayes (Maron e Kuhns 1960)(Minsky 1961)(Duda, Hart, e Stork 1973), é o classificador mais simples e o mais difundido entre os classificadores bayesianos. Sua arquitetura é fixa, portanto, não necessita de nenhum método de estimação de estrutura para modelagem, apenas os parâmetros são desconhecidos e devem ser estimados.

Seu pressuposto é de independência condicional entre as variáveis de entrada \((X_1,\ldots,X_p)\) e de saída \(\{Y\}\). Tal suposição potencializa a eficiência computacional, pois o número de parâmetros a serem estimados é reduzido em comparação com diversos outros métodos (Cheng e Greiner 1999). Além disso, a variável de saída não deve possuir nenhum pai. Ou seja, apenas a variável a ser predita é considerada como pai de todas as demais variáveis, as quais não possuem filhos ou outros pais.

Essa suposição, ingênua, de independência condicional é representada pela seguinte fatoração:

\[P(\mathbf{X},Y)=P(Y)\prod_{i=1}^{p}P(X_i|Y).\]

A estrutura probabilística do classificador bayesiano é representada pelo grafo da Figura 3.1:

Figura 3.1. Representção do classificador Naïve Bayes.

A suposição de independência condicional é, de fato, bastante ingênua, porém reduz de exponencial para linear o número de parâmetros. Além disso, esse classificador pode produzir resultados preditivos satisfatórios para alguns conjuntos de dados reais, até mesmo comparado a métodos mais complexos e com elevado custo computacional. Quando a suposição de independência condicional de todos os atributos dada a classe é satisfeita, o classificador Bayes ingênuo possui capacidade preditiva satisfatória. Tais fatos tornam o Naïve Bayes um método importante para tarefas de classificação (Cheng e Greiner 1999).

Na estimação dos parâmetros para dados discretos, o caso conjugado Multinomial-Dirichlet, via estimação bayesiana pela média a posteriori e priori uniforme, é conhecido como m-estimador, sendo m o tamanho amostral imaginário. (Cestnik e others 1990).

Para o caso contínuo, comumente \(X_{i}|y \sim N \left(\mu_{i|y},\sigma_{i|y}^{2}\right)\), sendo \(\mu_{i|y}\) e \(\sigma_{i|y}^{2}\) a média e a variância da variável \(X_{i}\) condicionada a \(Y=y\). Caso conhecido como naive bayes gaussiano (Perez, Larranaga, e Inza 2006).

Os próximos classificadores apresentados são formas de generalização do classificador Naïve Bayes.

3.3 Tree-Augmented Naïve Bayes (TAN)

O classificador Naïve Bayes de árvore aumentada (TAN - Tree-Augmented Naïve Bayes) foi proposto em Friedman e Goldszmidt (1996) e incorpora algumas dependências entre as variáveis de entrada ao construir uma árvore direcionada.

A estrutura do TAN é semiflexível, uma vez que relaxa a suposição de independência condicional entre as variáveis explicativas. Da mesma forma que no classificador naive bayes, a variável de interesse é variável pai de todas as variáveis preditoras, porém é permitido que cada variável preditora dependa de, no máximo, uma variável além da variável a ser classificada (Bielza e Larranaga 2014).

A inserção de até uma dependência adicional por variável de entrada, é representada pela seguinte fatoração:

\[P(\mathbf{X},Y) = P(Y) \prod_{i=1}^{p}P(X_i|Y,X_j),\]

que é um caso especial da fatoração de uma rede bayesiana, sendo \(\Pi_{X_i}=\{Y,X_j\}\), sendo \(X_j\) uma única outra covariável do conjunto \(\mathbf{X}\) e \(\Pi_{Y}= \emptyset\), pois \(Y\) é a variável raiz.

Figura 3.2. Representação do classificador TAN.

Esse classificador é inspirado no modelo de árvores bayesianas condicionais apresentado por Geiger (1992) e utiliza do Algoritmo de Chow-Liu (Chow e Liu 1968) para aprendizado de árvores. Do ponto de vista da teoria dos grafos, uma árvore é um grafo acíclico, conectado e não direcionado. Ou seja, uma árvore com \(p\) nós é representa por um grafo com \(p-1\) arestas (Chen 2012).

Algoritmo de Chow-Liu é apresentado pelos seguintes passos (Friedman e Goldszmidt 1996).

1. Calcule a informação mútua \(I(X_i;X_j|Y)\), sendo \(i ̸= j\);

2. Construa um grafo completo e, para cada aresta, atribua o peso da informação mútua calculada em 1;

3. A partir disso, construa uma árvore geradora de peso máximo (maximum weighted spanning tree);

4. Transforme o resultado da árvore não direcionada em uma árvore direcionada. Para isso escolha a variável de classificação como raiz (\(\Pi_Y = \emptyset\)) e direcione seus arcos opostamente a ela.

A Figura 3.3 exibe uma analogia ao processo de criação de uma árvore geradora de peso máximo, através das da criação de uma árvore geradora de peso mínimo. O algoritmo busca, a cada passo, arestas com o menor peso e só termina um passo antes da criação um ciclo (Cormen et al. 2009).

Chow e Liu (1968) provam que este procedimento encontra a árvore que maximiza a função de verossimilhança (Friedman, Geiger, e Goldszmidt 1997).

Figura 3.3. Método para obtenção de uma árvore geradora de peso minímo (Algoritmo de Kruskal) (Cormen et al. 2009).

Ou seja, as \(p\) variáveis de entrada formam um grafo que se restringe a uma árvore direcionada que representa as relações de dependência entre as variáveis de entrada. Além disso, há um arco partindo da variável categórica de saída e para cada variável de entrada.

3.4 KDB

Introduzido por Sahami (1996), a rede bayesiana de k dependência (KDB - K-Dependence Bayesian Network) é flexível ao ponto de permitir um limite de K pais para cada variável de entrada, além da variável de classificação, desta forma \(K \in \{0,\ldots,p-1\}\).

A flexibilização da restrição do TAN de possuir até um pai além da variável de classificação, faz com que esse parâmetro K varie permitindo maior adaptação das dependência entre as variáveis de entrada. Se o valor de K for grande o suficiente, espera-se que o modelo explore e capture todas as dependências que existem na base de dados \cite(Sahami 1996).

A decomposição da distribuição conjunta é dada por

\[ P(\mathbf{X},Y)= P(Y)\prod_{i=1}^p P(X_i|\Pi_{X_i}), \]

sendo que \(1 \leq |\Pi_{X_1}| \leq K\).

O Algoritmo abaixo, proposto por (Sahami 1996), descreve as etapas de aprendizado do classificador bayesiano K-DB.

1. Para cada variável \(X_{i},\) calcule a medida de informação mútua \(I(X_{i},Y)\);

2. Para cada par de variáveis explicativas, calcule a medida de informação mútua condicional \(I(X_{i},X_{j}|Y);\);

3. Defina \(S\) como a lista de variáveis explicativas utilizadas, inicialmente considere \(S\) como vazio;

4. Inicie a rede com a variável de classificação \(Y\);

5. Repita até a lista \(S\) conter todas as variáveis explicativas:

   1. Selecione a variável explicativa \(X_{max}\)que ainda não está contida em \(S\) e que possua a maior medida \(I(X_{max},Y)\);

   2. Adicione à rede a variável \(X_{max}\);

   3. Adicione um arco de \(Y\) para \(X_{max};\)

   4. Adicione \(m=min(|S|,K)\) arcos partindo das \(m\) \(X_{j}\) variáveis explicativas com o maior valor \(I(X_{max},X_{j}|Y)\);

   5. Adicione \(X_{max}\) à lista \(S\);

A Figura 3.3 apresenta um exemplo de estrutura do K-DB para qual o máximo de pais é \(K=2\).

Figura 3.3. KDB.

Nesse caso, o conjunto de pais de cada uma das variáveis \(X_i\) é \(\Pi_{X_1}=\{Y\}\), \(\Pi_{X_2}=\{Y,X_1\}\), \(\Pi_{X_3}=\{Y,X_1,X_2\}\), e assim por diante.

Esse classificador é uma generalização de ambos os classificadores anteriores, quando define-se \(K=0\) o Naïve Bayes é obtido, ou seja, \(0\) dependências entre os atributos dada a classe, quando \(K=1\) retorna-se ao TAN, permissão de até uma dependência para cada variável de entrada (Bielza e Larranaga 2014).

3.5 Avereged One-Dependence Estimator

o estimador médio de uma dependência (AODE - Averaged One-Dependence Estimator), proposto em Webb, Boughton, e Wang (2005), baseia-se em classificadores de única dependência, como o TAN ou 1DB, também denominados one dependence estimators (ODE).

Geralmente, os classificadores que permitem apenas uma dependência entre as covariáveis realizam uma seleção de modelo, que se torna um processo custoso computacionalmente Zheng e Webb (2017). O AODE tenta evitar esse problema, utilizando a média de todos os SPODE (SuperParent one-dependence estimator), isto é, um classificador de uma dependência superpai.

A Figura 3.4 apresenta um exemplo de estrutura do classificador SPODE. As variáveis que estão nas posições centrais dos grafos são as únicas que influenciam todas demais e a variável de classificação é a única dependência da superpai.

Figura 3.4. Representação dos superpais do AODE. Adaptado de Yu et al. (2017).

De maneira geral, o AODE seleciona uma classe limitada de classificadores que podem ter somente uma variável como pai e, agrega as predições de todos os classificadores qualificados dentro dessa classe (Webb, Boughton, e Wang 2005). Para ser qualificado, o modelo deve possuir uma acurada probabilidade estimada fazendo com que diminua a variância do classificador e o custo computacional (Bielza e Larranaga 2014).

A sua forma probabilística, para cada um dos superpais, pode ser representada por:

\[P(\mathbf{X},Y)= P(Y)P(X_j|Y)\prod_{i=1}^{p-1} P(X_i|X_j,Y),\] sendo que \(X_j\) é a variável superpai.

Desta forma, a estimação via o AODE é realizada como

\[ \begin{aligned} \hat{P}(Y=y|X=x) & = \frac{\sum_{i=1}^{p}\frac{\hat{P}\left(y,x_{i}\right)\hat{P}\left(x|y,x_{i}\right)}{\hat{P}(x)}}{p} \\ \end{aligned} \]

\[ \approx\frac{\sum_{i:C\left(x_{i}\right)\geq m}\hat{P}\left(x_{i},y\right)\prod_{j=1}^{p}\hat{P}\left(x_{j}\left|x_{i},y\right.\right)/\hat{P}(x)}{\left|\left\{ i:C\left(x_{i}\right)\geq m\right\} \right|} . \]

onde \(C(x_i)\) é o número de observações utilizadas para estimar o modelo na variável de entrada \(x_i\) e \(m = 30\) ou \(m = 100\), normalmente.

Este método reduz o problema de seleção de modelo para selecionar entre até \(p\) modelos, os modelos em que cada variável de entrada depende da variável de saída e o mesmo atributo único de tal forma que o valor dessa variável de entrada \(x_i\) ocorra com frequência suficiente para que possamos ter confiança na precisão de sua estimativa.

Em outras palavras, o classificador AODE realiza uma média bayesiana com prioris uniformes sobre todos os modelos plausíveis que têm todos os atributos que dependem de uma única variável de entrada e da variável de saída.

Esse classificador é chamado de ensemble, ou seja, uma combinação, já que agrega vários estimadores para gerar uma estrutura para o modelo final.

A Tabela abaixo exibe a complexidade computacional de cada um dos classificadores aqui discutidos (Sahami 1996)(Webb, Boughton, e Wang 2005).

Algoritmo	Estrutura	Parâmetros	Classificação
NB	\(\mathcal{O}(np)\)	\(\mathcal{O}(cpv)\)	\(\mathcal{O}(cp)\)
TAN	\(\mathcal{O}(np^2 + kp^2v^2 + p^2 \log p)\)	\(\mathcal{O}(c(pv)^2)\)	\(\mathcal{O}(cp)\)
KDB	\(\mathcal{O}(np^2kv^2)\)	\(\mathcal{O}(p(c + v^K))\)	\(\mathcal{O}(cpK)\)
AODE	\(\mathcal{O}(np^2)\)	\(\mathcal{O}(c(pv)2)\)	\(\mathcal{O}(cp^2)\)

sendo \(n\) o número de observações, \(c\) o número de categorias da variável de saída, \(p\) o número de variáveis de entrada, e \(v\) é o número médio de valores para um atributo.

3.5 Medidas de capacidade preditiva

Para classificação binária as métricas são provenientes da matriz de confusão, apresentada na tabela abaixo.

Modelo\Real	\(Y=0\)	\(Y=1\)
\(Y=0\)	\(VN\)	\(FN\)
\(Y=1\)	\(FP\)	\(VP\)

Em que \(VP\) representa os valores verdadeiros positivos, \(VN\) os valores verdadeiros negativos, \(FP\) os valores falsos positivos e \(FN\) os valores falsos negativos.

Nesse texto serão consideradas as métricas abaixo para quantificar a capacidade preditiva dos classificadores (Baldi et al. 2000).

Acurácia: métrica que considera o número total de acertos do modelo sobre o número total de observações disponíveis. O melhor modelo é o que apresentar a maior acurácia. É definida como:

\[ACC=\frac{VP+VN}{VP+VN+FP+FN}.\]

F1 score (F1): métrica que representa uma combinação de outras duas métricas, o Recall (R), também chamada sensibilidade, e a Precisão (P), também conhecida como valor preditivo positivo. O melhor modelo é o que apresentar o maior valor F1. É definido como:

\[F1=\frac{2*P*R}{P+R},\]

em que \(R=\frac{VP}{VP+FN}\) e \(P =\frac{VP}{VP+FP}.\)

Correlação de Matthew (MCC): métrica que representa uma correlação. O melhor modelo é o que apresentar a maior MCC. É definida por:

\[MCC = \dfrac{VP \times VN - FP \times FN}{\sqrt{(VP + FP)(VP + FN)(VN + FP)(VN + FN)}}.\]

É interpretada de maneira similar ao coeficiente de correlação de Pearson: quando igual 1, a classificação é perfeita; quando igual a 0, classificação é nula; quando igual a -1, a classificação é totalmente inversa.

Uma abordagem comum para tarefas de classificação quando \(c>2\), quando a variável de saída possui mais de duas classes, é utilizar medidas micro e médias macro, as quais representam duas abordagens diferentes para interpretar a matriz de confusão (Yao e Zhou 2008).

3.6 Classificadores bayesianos em linguagem R

O pacote bnclassify (Mihaljević, Bielza, e Larrañaga 2020) implementa algoritmos para aprendizagem de estrutura e dos parâmetros de diversos classificadores bayesianos.

require(bnclassify)

lizards <- bnlearn::lizards

nb <- nb('Species', lizards)
nb <- lp(nb, lizards, smooth = 1)
plot(nb)

Y.ch <- predict(nb, lizards)

table(Y.ch,lizards$Species)

##            
## Y.ch        Sagrei Distichus
##   Sagrei        86        73
##   Distichus     78       172

cv(nb, lizards, k = 10)

## [1] 0.631115

tan_mod <- bnc('tan_cl','Species', lizards,smooth = 1)
plot(tan_mod)

Y.ch <- predict(tan_mod, lizards)

table(Y.ch,lizards$Species)

##            
## Y.ch        Sagrei Distichus
##   Sagrei        86        73
##   Distichus     78       172

cv(tan_mod, lizards, k = 10)

## [1] 0.6308391

plot(tan_mod)

Y.ch <- predict(tan_mod, lizards)

table(Y.ch,lizards$Species)

##            
## Y.ch        Sagrei Distichus
##   Sagrei        86        73
##   Distichus     78       172

cv(tan_mod, lizards, k = 10)

## [1] 0.6308914

aode_mod <- aode('Species', lizards)
aode_mod <- lp(aode_mod, lizards, smooth = 1)


Y.ch <- predict(aode_mod, lizards)

table(Y.ch,lizards$Species)

##            
## Y.ch        Sagrei Distichus
##   Sagrei        86        73
##   Distichus     78       172

cv(aode_mod, lizards, k = 10)

## [1] 0.630694

Referências

Baldi, Pierre, Søren Brunak, Yves Chauvin, Claus AF Andersen, e Henrik Nielsen. 2000. «Assessing the accuracy of prediction algorithms for classification: an overview». Bioinformatics 16 (5): 412–24.

Bielza, Concha, e Pedro Larranaga. 2014. «Discrete Bayesian network classifiers: A survey». ACM Computing Surveys (CSUR) 47 (1): 1–43.

Cestnik, Bojan, e others. 1990. «Estimating probabilities: a crucial task in machine learning.» Em ECAI, 90:147–49.

Chen, Wai-Kai. 2012. Applied graph theory. Vol. 13. Elsevier.

Cheng, Jie, e Russell Greiner. 1999. «Comparing Bayesian network classifiers». Em Proceedings of the Fifteenth conference on Uncertainty in artificial intelligence, 101–8. Morgan Kaufmann Publishers Inc.

Chow, CKCN, e Cong Liu. 1968. «Approximating discrete probability distributions with dependence trees». IEEE transactions on Information Theory 14 (3): 462–67.

Cormen, Thomas H, Charles E Leiserson, Ronald L Rivest, e Clifford Stein. 2009. Introduction to algorithms. MIT press.

Duda, Richard O, Peter E Hart, e David G Stork. 1973. Pattern classification and scene analysis. Vol. 3. Wiley New York.

Friedman, Nir, Dan Geiger, e Moises Goldszmidt. 1997. «Bayesian network classifiers». Machine learning 29 (2): 131–63.

Friedman, Nir, e Moises Goldszmidt. 1996. «Building classifiers using Bayesian networks». Em Proceedings of the national conference on artificial intelligence, 1277–84.

Geiger, Dan. 1992. «An entropy-based learning algorithm of Bayesian conditional trees». Em Uncertainty in Artificial Intelligence, 92–97. Elsevier.

Maron, Melvin Earl, e John Larry Kuhns. 1960. «On relevance, probabilistic indexing and information retrieval». Journal of the ACM 7 (3): 216–44.

Mihaljević, Bojan, Concha Bielza, e Pedro Larrañaga. 2020. «bnclassify: Learning Bayesian Network Classifiers».

Minsky, Marvin. 1961. «Steps toward artificial intelligence». Proceedings of the IRE 49 (1): 8–30.

Perez, Aritz, Pedro Larranaga, e Inaki Inza. 2006. «Supervised classification with conditional Gaussian networks: Increasing the structure complexity from naive Bayes». International Journal of Approximate Reasoning 43 (1): 1–25.

Sahami, M. 1996. «Learning Limited Dependence Bayesian Classifiers». Em In KDD-96: Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, 335–38. Menlo Park, CA: AAAI Press.

Shannon, Claude E. 1948. «A mathematical theory of communication». The Bell system technical journal 27 (3): 379–423.

Webb, Geoffrey I, Janice R Boughton, e Zhihai Wang. 2005. «Not so naive Bayes: aggregating one-dependence estimators». Machine learning 58 (1): 5–24.

Yao, Yiyu, e Bing Zhou. 2008. «Micro and macro evaluation of classification rules». Em 2008 7th IEEE International Conference on Cognitive Informatics, 441–48. IEEE.

Yu, Liangjun, Liangxiao Jiang, Dianhong Wang, e Lungan Zhang. 2017. «Attribute value weighted average of one-dependence estimators». Entropy 19 (9): 501.

Zheng, Fei, e Geoffrey I. Webb. 2017. «Averaged One-Dependence Estimators». Em Encyclopedia of Machine Learning and Data Mining, editado por Claude Sammut e Geoffrey I. Webb, 85–87. Boston, MA: Springer US.