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)$.
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.
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:
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.
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:
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:
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$$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:
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.
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:
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
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.
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.