{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Naive Bayes\n",
    "\n",
    "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.\n",
    "\n",
    "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:\n",
    "\n",
    "$$R = argmax_{(c \\in C)} P(c | x_1, x_2, ..., x_n)$$\n",
    "\n",
    "Ou seja, ele precisa encontrar a classe $c$ que tenha a maior probabilidade dadas as características do exemplo de teste."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Utilizando o teorema de Bayes podemos reescrever a expressão $P(c | x_1, x_2, ..., x_n)$ da seguinte forma:\n",
    "\n",
    "$$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)}$$\n",
    "\n",
    "Substituindo na fórmula para encontrar R, temos:\n",
    "\n",
    "$$R = argmax_{(c \\in C)}  \\frac{ P(x_1, x_2, ..., x_n | c)P(c)}{ P(x_1, x_2, ..., x_n)}$$\n",
    "\n",
    "\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)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Classificando\n",
    "\n",
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "spam = [\"offer is secret\", \"click secret link\", \"secret sport link\"]\n",
    "not_spam = [\"play sport today\", \"went play sport\", \"secret sport event\", \"sport is today\", \"sport costs money\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Usando o Naive Bayes, vamos classificar a mensagem \"secret is secret\" para saber se ela é Spam ou não.\n",
    "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\"].\n",
    "\n",
    "Dessa forma, temos que encontrar: \n",
    "\n",
    "$$R = argmax_{(c \\in C)} P(c | \"secret\", \"is\" , \"secret\")$$\n",
    "\n",
    "Onde $C = \\{spam, nãoSpam\\}$.\n",
    "\n",
    "Utilizando o Teorema de Bayes, escrevemos R como:\n",
    "\n",
    "$$R = argmax_{(c \\in C)} P(\"secret\", \"is\", \"secret\" | c)P(c)$$\n",
    "\n",
    "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.\n",
    "\n",
    "Dessa forma, $P(\"secret\", \"is\", \"secret\" | c)$ se resume a: $P(\"secret\"|c)P(\"is\"|c)P(\"secret\"|c)$.\n",
    "\n",
    "Substituindo na equação para encontrar $R$, temos:\n",
    "\n",
    "$$R = argmax_{(c \\in C)} P(\"secret\"|c)P(\"is\"|c)P(\"secret\"|c)P(c)$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "P(spam) = 0.375\n",
      "P(nãoSpam) = 0.625\n"
     ]
    }
   ],
   "source": [
    "total = len(spam) + len(not_spam)\n",
    "p_spam = len(spam) / total\n",
    "p_not_spam = len(not_spam) / total\n",
    "\n",
    "print(\"P(spam) = {}\".format(p_spam))\n",
    "print(\"P(nãoSpam) = {}\".format(p_not_spam))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "P(\"secret\" | spam) = 0.3333333333333333\n",
      "P(\"secret\" | nãoSpam) = 0.06666666666666667\n"
     ]
    }
   ],
   "source": [
    "def p(word, messages):\n",
    "    total = 0\n",
    "    word_count = 0\n",
    "\n",
    "    for m in messages:\n",
    "        words = m.split()\n",
    "        \n",
    "        for w in words:\n",
    "            total += 1\n",
    "            if w == word:\n",
    "                word_count += 1\n",
    "                \n",
    "    return word_count/total\n",
    "\n",
    "print(\"P(\\\"secret\\\" | spam) = {}\".format(p(\"secret\", spam)))\n",
    "print(\"P(\\\"secret\\\" | nãoSpam) = {}\".format(p(\"secret\", not_spam)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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\".\n",
    "\n",
    "Para a classe spam temos:\n",
    "\n",
    "$$P(\"secret\"|spam)P(\"is\"|spam)P(\"secret\"|spam)P(spam)$$\n",
    "\n",
    "O código abaixo mostra o resultado desse cálculo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "O resultado da mensagem \"secret is secret\" para a classe spam é 0.004629629629629629\n"
     ]
    }
   ],
   "source": [
    "p_test_spam = p(\"secret\", spam)*p(\"is\", spam)*p(\"secret\", spam)*p_spam\n",
    "\n",
    "print(\"O resultado da mensagem \\\"secret is secret\\\" para a classe spam é {}\".format(p_test_spam))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Para a classe nãoSpam temos:\n",
    "\n",
    "$$P(\"secret\"|nãoSpam)P(\"is\"|nãoSpam)P(\"secret\"|nãoSpam)P(nãoSpam)$$\n",
    "\n",
    "O código abaixo mostra o resultado desse cálculo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "O resultado da mensagem \"secret is secret\" para a classe nãoSpam é 0.00018518518518518518\n"
     ]
    }
   ],
   "source": [
    "p_test_not_spam = p(\"secret\", not_spam)*p(\"is\", not_spam)*p(\"secret\", not_spam)*p_not_spam\n",
    "\n",
    "print(\"O resultado da mensagem \\\"secret is secret\\\" para a classe nãoSpam é {}\".format(p_test_not_spam))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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:\n",
    "\n",
    "$$P(\"secret\", \"is\", \"secret\" | spam) = \\frac{0,004629629629629629}{0,004629629629629629+0,00018518518518518518} = 0,9615384615384616$$\n",
    "\n",
    "\n",
    "$$P(\"secret\", \"is\", \"secret\" | nãoSpam) = \\frac{0,00018518518518518518}{0,004629629629629629+0,00018518518518518518} = 0,038461538461538464$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Suavização\n",
    "\n",
    "Vamos agora classificar a mensagem \"today is secret\" da mesma forma realizada anteriormente.\n",
    "\n",
    "Para a classe spam temos:\n",
    "\n",
    "$$P(\"today\"|spam)P(\"is\"|spam)P(\"secret\"|spam)P(spam)$$\n",
    "\n",
    "O código abaixo mostra o resultado desse cálculo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "O resultado da mensagem \"today is secret\" para a classe spam é 0.0\n"
     ]
    }
   ],
   "source": [
    "p_test_spam = p(\"today\", spam)*p(\"is\", spam)*p(\"secret\", spam)*p_spam\n",
    "\n",
    "print(\"O resultado da mensagem \\\"today is secret\\\" para a classe spam é {}\".format(p_test_spam))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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.\n",
    "\n",
    "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$.\n",
    "\n",
    "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. \n",
    "\n",
    "Com isso, usando a suavização de Laplace, temos:\n",
    "\n",
    "$$P_{Laplace}(palavra|c) = \\frac{count(palavra, c) + 1}{N(c) + V(c) + 1}$$\n",
    "\n",
    "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$.\n",
    "\n",
    "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.\n",
    "\n",
    "O código a seguir implementa o cálculo da probabilidade de uma palavra numa determinada classe usando suavização de Laplace."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "P_Laplace(\"today\" | spam) = 0.0625\n"
     ]
    }
   ],
   "source": [
    "def p_laplace(word, messages):\n",
    "    total = 1\n",
    "    word_count = 1\n",
    "    unique_words = set()\n",
    "\n",
    "    for m in messages:\n",
    "        words = m.split()\n",
    "        \n",
    "        for w in words:\n",
    "            unique_words.add(w)\n",
    "            total += 1\n",
    "            if w == word:\n",
    "                word_count += 1\n",
    "\n",
    "    return word_count/(total+len(unique_words))\n",
    "\n",
    "print(\"P_Laplace(\\\"today\\\" | spam) = {}\".format(p_laplace(\"today\", spam)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Classificaremos novamente \"today is secret\", mas agora usando a suavização de Laplace. O código abaixo apresenta o resultado do cálculo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "O resultado da mensagem \"today is secret\" para a classe spam é 0.000732421875\n"
     ]
    }
   ],
   "source": [
    "p_test_spam = p_laplace(\"today\", spam)*p_laplace(\"is\", spam)*p_laplace(\"secret\", spam)*p_spam\n",
    "\n",
    "print(\"O resultado da mensagem \\\"today is secret\\\" para a classe spam é {}\".format(p_test_spam))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "O resultado da mensagem \"today is secret\" para a classe nãoSpam é 0.00047999999999999996\n"
     ]
    }
   ],
   "source": [
    "p_test_not_spam = p_laplace(\"today\", not_spam)*p_laplace(\"is\", not_spam)*p_laplace(\"secret\", not_spam)*p_not_spam\n",
    "\n",
    "print(\"O resultado da mensagem \\\"today is secret\\\" para a classe nãoSpam é {}\".format(p_test_not_spam))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Com isso, a mensagem \"today is secret\" é classificada como Spam, pois essa classe obteve o maior valor."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Underflow\n",
    "\n",
    "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.\n",
    "\n",
    "Para evitar problemas de underflow, podemos calcular o logaritmo da multiplicação das probabilidades. Assim, temos:\n",
    "\n",
    "$$\\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))$$\n",
    "\n",
    "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."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}