Edit page

Bayesian Learning

Os bayesianos fazem da probabilidade a sua ferramenta principal, útil para quantificar a incerteza causada pelo ruído nos dados e pela reduzida dimensão dos dados.

Na abordagem de classificação, escolhe-se o classificador mais provável, dada a evidência conhecida, que neste caso se trata dos dados de treino. Assim, na presença de um objeto por classificar, procura-se a classe mais provável.

Teorema de Bayes

A peça central deste tipo de abordagem à classificação é o teorema de Bayes.

P(AB)=P(BA)×P(A)P(B)P(A \mid B) = \frac{P(B \mid A) \times P(A)}{P(B)}

Damos a AA o nome de crença e a BB o nome de evidência. A probabilidade de AA é denominada prior, pois se refere à probabilidade antes da evidência ser obtida, e a probabilidade condicionada P(AB)P(A \mid B) denomina-se posterior, pois é obtida depois da evidência se confirmar. À probabilidade P(BA)P(B \mid A) dá-se o nome de likelihood.

Lei da Probabilidade Total

A lei da probabilidade total indica que, para kk acontecimentos mutuamente exclusivos tal que

i=1kP(Bi)=1\sum_{i=1}^{k} P(B_i) = 1

podemos representar a probabilidade de qualquer outro acontecimento AA como

P(A)=i=1kP(A)P(Bi)=i=1kP(ABi)P(Bi)P(A) = \sum_{i=1}^{k} P(A) \cap P(B_i) = \sum_{i=1}^{k} P(A \mid B_i) \cdot P(B_i)

Classificador Maximum a Posteriori (MAP)

De modo a escolher a classe mais provável para um objeto não classificado, escolhemos a classe que tem maior probabilidade condicionada pela evidência.

y=arg maxci{P(cix)}=arg maxci{P(ci)×P(xci)P(x)}=arg maxci{P(ci)×P(xci)}\begin{aligned} y &= \underset{c_i}{\operatorname{arg\ max}}\{P(c_i \mid x)\} \\ &= \underset{c_i}{\operatorname{arg\ max}}\left\{\frac{P(c_i) \times P(x \mid c_i)}{P(x)}\right\} \\ &= \underset{c_i}{\operatorname{arg\ max}}\{P(c_i) \times P(x \mid c_i)\} \end{aligned}

Assim, a tarefa de treino limita-se ao cálculo das probabilidades a priori de cada classe. Na presença de um objeto ZZ a ser classificado, estima-se a likelihood ou máxima verosimilhança de ZZ para cada classe, ou seja, a probabilidade de observar ZZ supondo que pertence a cada uma das classes. Finalmente, escolhe-se a classe mais provável.

No caso de empate de duas classes, tendo estas a mesma likelihood, o classificador não é capaz de rotular o objeto, sendo contabilizado como um erro.

Estimação da Probabilidade a Priori

Considere-se um conjunto de treino de nn registos, em que nin_i registos pertencem à classe cic_i. A probabilidade a priori de cada classe pode ser estimada pelo quociente P(ci)=ninP(c_i) = \frac{n_i}{n}.

Estimação do Likelihood

Perante um conjunto de treino de nn registos, em que nin_i registos pertencem à classe cic_i, a likelihood de observar xx em cada umas das classes é estimada pelo quociente P(xci)=nxiniP(x | c_i) = \frac{n_{x \mid i}}{n_i}.

Contudo, nos dados de treino, a classe cic_i pode não conter nenhuma instância do objeto xx, fazendo com que a likelihood seja 0. Assim, a inexistência de uma dimensão de dados de treino significativamente robusta prejudica o cálculo destas probabilidades.

Variáveis Contínuas

Se num conjunto de treino definirmos as variáveis como valores contínuos, como por exemplo a altura de uma pessoa, deparamo-nos com um problema. A probabilidade de qualquer variável numérica contínua assumir qualquer valor é 0. Em contraste com o caso discreto, para variáveis contínuas faz-se uso de uma função de distribuição, de modo a calcular probabilidades.

P(xci)=fi(xμi,σi) onde XiN(μi,σi2)P(x \mid c_i) = f_i(x \mid \mu_i, \sigma_i) \text{ onde } X_i \sim N(\mu_i, \sigma_i^2)

Assume-se que cada classe segue uma distribuição normal, sendo apenas necessário calcular a média μ\mu e o desvio padrão σ\sigma através da amostra.

Múltiplas Variáveis

Na presença de múltiplas variáveis que descrevem os registos, generaliza-se a noção anterior para mais do que uma dimensão. As probabilidades condicionadas tornam-se agora probabilidades condicionadas conjuntas e, ao invés de calcular a média e desvio padrão, calculamos agora o vetor média e a matriz de covariância.

P(xci)=fi(xμi,Σi) onde XN(μ,Σ2)P(\vec{x} \mid c_i) = f_i(\vec{x} \mid \vec{\mu_i}, \vec{\Sigma_i}) \text{ onde } X \sim N(\vec{\mu}, \Sigma^2)

Complexidade do Modelo

Uma boa estimativa da complexidade de um modelo é dada pelo número de parâmetros que o modelo guarda internamente.

O classificador bayesiano precisa de saber cada um dos priors, ou seja, cada uma das P(ci)P(c_i). Contudo, apenas precisamos de guardar o valor de N1N-1 probabilidades pois conseguimos derivar a última destas através da relação i=1NP(ci)=1\sum\limits_{i=1}^{N} P(c_i) = 1

Para além destes valores, é necessário guardar o valor das likelihoods, P(xnci)P(x_n \mid c_i). Pela mesmo razão, podemos guardar todas as likelihoods expeto uma pois a soma destas é 1.

O modelo apresenta bons resultados quando a distribuição dos dados é bem aproximada. Contudo, requer um conjunto de dados bastante grande para estimar probabilidades conjuntas, o que torna o modelo impraticável para registos com muitas dimensões. Pode-se demonstrar que o número de observações necessárias cresce exponencialmente com o número de atributos. São também necessários várias cálculos de probabilidades, que podem ser computacionalmente exigentes.

Algoritmo/Suposição de Naive Bayes

O algoritmo de Naive Bayes aborda o problema da falta de dados suficientes para estimar a probabilidade conjunta de forma fiável. De forma a calcular estas probabilidades, o algoritmo assume uma simplificação do problema que, apesar de ingénua, fornece resultados bastante bons.

A suposição que o algoritmo realiza é a de assumir independência condicional, dada a classe, entre as variáveis que caracterizam os dados.

y^=arg maxci{P(cix)}=arg maxci{P(ci)×P(xci)P(x)}=arg maxci{P(ci)×P(xci)}=arg maxci{P(ci)×j=1dP(xjci)}\begin{aligned} \hat{y} &= \underset{c_i}{\operatorname{arg\ max}}\{P(c_i \mid x)\} \\ &= \underset{c_i}{\operatorname{arg\ max}}\left\{\frac{P(c_i) \times P(x \mid c_i)}{P(x)}\right\} \\ &= \underset{c_i}{\operatorname{arg\ max}}\{P(c_i) \times P(x \mid c_i)\} \\ &= \underset{c_i}{\operatorname{arg\ max}}\{P(c_i) \times \prod_{j=1}^{d} P(x_j \mid c_i)\} \end{aligned}

Assim, a tarefa de treino em tudo se assemelha ao do classificador MAP. A diferença reside no cálculo da likelihood, que é bastante simplificado, realizando-se através do produto as probabilidades condicionadas unidimensionais de observar ZZ, dada a classe.

Complexidade do Modelo

Apesar do pressuposta da independência condicional das variáveis ser, na maior parte dos casos, violada, este método apresenta resultados bastante bons. No caso em que a independência não é violada, trata-se do classificador ideal. Contudo, o pressuposto da independência condicional pode trazer uma pior exatidão quando existe dependência entre as variáveis.

Pode ser utilizada em conjuntos de dados com dimensões reduzidas pois o número de observações necessárias cresce, por causa do pressuposto da independência, linearmente com o número de atributos.

Overfitting

De modo a evitar o overfitting, pode ser aplicada a suposição de Naive-Bayes. A utilização de distribuições de probabilidade teóricas em vez de distribuições empíricas reduz o overfitting.