Naive Bayes

Um classificador na aprendizagem de máquina supervisionada tem como objetivo prever uma classe para uma entrada de acordo com dados de treinamento. O classificador Naive Bayes utiliza o teorema de Bayes para classificar um exemplo de teste, que é definido por um conjunto de características, com a classe mais provável para o exemplo.

Dado que um exemplo de entrada é definido por um vetor de características: [$x_1$, $x_2$, ..., $x_n$], e que um problema tem um conjunto $C$ de possíveis classes, o classificador precisa encontrar uma resposta $R$ definida por:

$$R = argmax_{(c \in C)} P(c | x_1, x_2, ..., x_n)$$

Ou seja, ele precisa encontrar a classe $c$ que tenha a maior probabilidade dadas as características do exemplo de teste.

Utilizando o teorema de Bayes podemos reescrever a expressão $P(c | x_1, x_2, ..., x_n)$ da seguinte forma:

$$P(c | x_1, x_2, ..., x_n) = \frac{ P(x_1, x_2, ..., x_n | c)P(c)}{ P(x_1, x_2, ..., x_n)}$$

Substituindo na fórmula para encontrar R, temos:

$$R = argmax_{(c \in C)} \frac{ P(x_1, x_2, ..., x_n | c)P(c)}{ P(x_1, x_2, ..., x_n)}$$

Como $ P(x_1, x_2, ..., x_n)$ é constante para um dado exemplo de teste, então, para maximizar $P(c | x_1, x_2, ..., x_n)$, basta maximizar o numerador $P(x_1, x_2, ..., x_n | c)P(c)$.

Classificando

A seguir aplicaremos o classificador Naive Bayes num problema de detecção de Spam. Um e-mail recebido pode ser Spam ou pode não ser Spam, assim os dados de treinamento para esse problema trazem mensagens que foram classificadas como Spam ou não Spam. O código abaixo define duas listas, uma com mensagens classificadas como Spam e outra com mensagens classificadas como não Spam. Para fins didáticos, as mensagens são curtas e simples, mas o classificador pode ser aplicado da mesma forma para mensagens maiores.

In [1]:
spam = ["offer is secret", "click secret link", "secret sport link"]
not_spam = ["play sport today", "went play sport", "secret sport event", "sport is today", "sport costs money"]

Usando o Naive Bayes, vamos classificar a mensagem "secret is secret" para saber se ela é Spam ou não. Primeiramente, precisamos definir quais são as características dos nossos exemplos. Num classificador de Spam, podemos usar as palavras como as características. Com isso, o vetor de características do exemplo "secret is secret" é: ["secret", "is", "secret"].

Dessa forma, temos que encontrar:

$$R = argmax_{(c \in C)} P(c | "secret", "is" , "secret")$$

Onde $C = \{spam, nãoSpam\}$.

Utilizando o Teorema de Bayes, escrevemos R como:

$$R = argmax_{(c \in C)} P("secret", "is", "secret" | c)P(c)$$

Para calcular P("secret", "is", "secret" | c), o Naive Bayes supõe que a ordem das palavras não importa e que as probabilidade das palavras são independentes. Essa suposição não é verdade para um texto, sabemos que as palavras não são escritas de forma independente e que a ordem importa, mas essa suposição simplifica e agiliza os cálculos. Mesmo com essa suposição, em diversos casos, o Naive Bayes tem desempenho similar a classificadores mais sofisticados.

Dessa forma, $P("secret", "is", "secret" | c)$ se resume a: $P("secret"|c)P("is"|c)P("secret"|c)$.

Substituindo na equação para encontrar $R$, temos:

$$R = argmax_{(c \in C)} P("secret"|c)P("is"|c)P("secret"|c)P(c)$$

Para estimar $P(c)$ basta contar quantas vezes a classe $c$ aparece nos dados de treinamento e dividir pelo total de dados de treinamento. Assim, temos:

In [2]:
total = len(spam) + len(not_spam)
p_spam = len(spam) / total
p_not_spam = len(not_spam) / total

print("P(spam) = {}".format(p_spam))
print("P(nãoSpam) = {}".format(p_not_spam))
P(spam) = 0.375
P(nãoSpam) = 0.625

Para calcular P("palavra"|c) precisamos contar quantas vezes "palavra" aparece na classe $c$ e dividir pelo total de palavras na classe $c$. A função implementada a seguir calcula a probabilidade de uma palavra dada uma classe. Ela recebe dois parâmetros, o primeiro é a palavra e o segundo é a lista com as mensagens de uma classe.

In [3]:
def p(word, messages):
    total = 0
    word_count = 0

    for m in messages:
        words = m.split()
        
        for w in words:
            total += 1
            if w == word:
                word_count += 1
                
    return word_count/total

print("P(\"secret\" | spam) = {}".format(p("secret", spam)))
print("P(\"secret\" | nãoSpam) = {}".format(p("secret", not_spam)))
P("secret" | spam) = 0.3333333333333333
P("secret" | nãoSpam) = 0.06666666666666667

Com a função para calcular probabilidades das palavras implementada, agora podemos verificar qual das duas classes tem a maior probabilidade para a mensagem "secret is secret".

Para a classe spam temos:

$$P("secret"|spam)P("is"|spam)P("secret"|spam)P(spam)$$

O código abaixo mostra o resultado desse cálculo:

In [4]:
p_test_spam = p("secret", spam)*p("is", spam)*p("secret", spam)*p_spam

print("O resultado da mensagem \"secret is secret\" para a classe spam é {}".format(p_test_spam))
O resultado da mensagem "secret is secret" para a classe spam é 0.004629629629629629

Para a classe nãoSpam temos:

$$P("secret"|nãoSpam)P("is"|nãoSpam)P("secret"|nãoSpam)P(nãoSpam)$$

O código abaixo mostra o resultado desse cálculo:

In [5]:
p_test_not_spam = p("secret", not_spam)*p("is", not_spam)*p("secret", not_spam)*p_not_spam

print("O resultado da mensagem \"secret is secret\" para a classe nãoSpam é {}".format(p_test_not_spam))
O resultado da mensagem "secret is secret" para a classe nãoSpam é 0.00018518518518518518

Com os dois resultados em mãos, temos que a mensagem "secret is secret" é classificada como Spam, pois essa classe obteve o maior valor. Intuitivamente podemos perceber que isso era esperado, já que a palavra "secret" aparece com bastante frequência nos dados de treinamento para classe spam e aparece apenas uma vez para classe nãoSpam.

O que calculamos anteriormente não são as probabilidades de ser ou não ser Spam, já que simplificamos o cálculo retirando o denominador na fórmula do teorema do Bayes. A probabilidade pode ser obtida normalizando os valores para que a soma deles seja 1. Assim, temos:

$$P("secret", "is", "secret" | spam) = \frac{0,004629629629629629}{0,004629629629629629+0,00018518518518518518} = 0,9615384615384616$$$$P("secret", "is", "secret" | nãoSpam) = \frac{0,00018518518518518518}{0,004629629629629629+0,00018518518518518518} = 0,038461538461538464$$

Suavização

Vamos agora classificar a mensagem "today is secret" da mesma forma realizada anteriormente.

Para a classe spam temos:

$$P("today"|spam)P("is"|spam)P("secret"|spam)P(spam)$$

O código abaixo mostra o resultado desse cálculo:

In [6]:
p_test_spam = p("today", spam)*p("is", spam)*p("secret", spam)*p_spam

print("O resultado da mensagem \"today is secret\" para a classe spam é {}".format(p_test_spam))
O resultado da mensagem "today is secret" para a classe spam é 0.0

Essa probabilidade não parece muito coerente, mudamos apenas uma palavra em relação mensagem anterior e diminuímos bruscamente o valor para classe spam.

Para a mensagem "today is secret" nós temos um problema. $P("today" | spam) = 0$, pois a palavra "today" não aparece nos dados de treinamento com a classificação Spam. Assim, uma única probabilidade igual a $0$ torna todas as outras probabilidades irrelevantes, pois 0 multiplicado por qualquer valor é igual a $0$.

Para resolver isso, utilizaremos uma técnica chamada Suavização de Laplace. A ideia dessa técnica é supor que cada palavra foi vista nos dados de treinamento uma vez a mais, ou seja, vamos adicionar 1 em todas as contagens.

Com isso, usando a suavização de Laplace, temos:

$$P_{Laplace}(palavra|c) = \frac{count(palavra, c) + 1}{N(c) + V(c) + 1}$$

Onde, $count(palavra, c)$ é a quantidade de vezes que a palavra aparece com a classe $c$, $N(c)$ é a quantidade de palavras nos exemplos da classe $c$ e $V(c)$ é o tamanho do vocabulário para a classe $c$.

Como estamos adicionando 1 para cada palavra existente nos dados de treinamento, então o total de palavras precisa ser acrescido num valor igual à quantidade de palavras únicas, ou seja, o tamanho do vocabulário. Além disso, somamos 1 ao total de palavras do vocabulário para representar a possibilidade de palavras desconhecidas.

O código a seguir implementa o cálculo da probabilidade de uma palavra numa determinada classe usando suavização de Laplace.

In [7]:
def p_laplace(word, messages):
    total = 1
    word_count = 1
    unique_words = set()

    for m in messages:
        words = m.split()
        
        for w in words:
            unique_words.add(w)
            total += 1
            if w == word:
                word_count += 1

    return word_count/(total+len(unique_words))

print("P_Laplace(\"today\" | spam) = {}".format(p_laplace("today", spam)))
P_Laplace("today" | spam) = 0.0625

Classificaremos novamente "today is secret", mas agora usando a suavização de Laplace. O código abaixo apresenta o resultado do cálculo:

In [8]:
p_test_spam = p_laplace("today", spam)*p_laplace("is", spam)*p_laplace("secret", spam)*p_spam

print("O resultado da mensagem \"today is secret\" para a classe spam é {}".format(p_test_spam))
O resultado da mensagem "today is secret" para a classe spam é 0.000732421875
In [9]:
p_test_not_spam = p_laplace("today", not_spam)*p_laplace("is", not_spam)*p_laplace("secret", not_spam)*p_not_spam

print("O resultado da mensagem \"today is secret\" para a classe nãoSpam é {}".format(p_test_not_spam))
O resultado da mensagem "today is secret" para a classe nãoSpam é 0.00047999999999999996

Com isso, a mensagem "today is secret" é classificada como Spam, pois essa classe obteve o maior valor.

Underflow

Usando o classificador Naive Bayes precisamos multiplicar as probabilidades de cada palavra numa mensagem. Como probabilidades são valores entre 0 e 1, multiplicar muitos valores dessa grandeza pode resultar em números extremamente pequenos. Por isso, é importante prestar atenção em casos que podem resultar em underflow.

Para evitar problemas de underflow, podemos calcular o logaritmo da multiplicação das probabilidades. Assim, temos:

$$\log( P(a_1|c)P(a_2|c)...P(a_n|c) ) = \log(P(a_1|c)) + \log(P(a_2|c)) + ... + \log(P(a_n|c))$$

Note que ao invés da multiplicação, usando o $\log$, nós somaremos os valores, evitando o underflow pela multiplicação de valores muito pequenos.