Aula_20_-_ML_-_Naive_Bayes

Prévia do material em texto

Inteligência Artificial
Aprendizado de Máquina: Naive Bayes
Professor: Felipe Alberto B. S. Ferreira (felipe.bsferreira@ufrpe.br)
mailto:felipe.bsferreira@ufrpe.br
Aprendizado de Máquina
§ Até agora: como usar um modelo para tomar decisões ótimas
§ Aprendizado de máquina: como obter um modelo através de dados 
/ experiência
§ Aprender parâmetros (ex.: probabilidades)
§ Aprender estruturas (ex.: redes bayesianas)
§ Aprender conceitos (ex.: segmentação, clusterização, redes neurais)
§ Hoje: classificação baseada em modelo com Naive Bayes
Classificação
Exemplo: Filtro de Spam
§ Entrada: um e-mail
§ Saída: sim / não
§ Configuração:
§ Obtenha uma grande quantidade de exemplos de e-
mails, cada um classificado corretamente (label)
§ Nota: alguém precisa fazer isso manualmente!
§ Deseja-se aprender a classificar (predizer a label) 
futuros novos e-mails
§ Características (features): atributos usados para 
decidir entre spam ou não
§ Palavras: FREE!
§ Padrões textuais: R$dd, CAPS
§ Não-textual: SenderInContacts, WidelyBroadcast
§ …
Caro Senhor.
Primeiro, eu gostaria de solicitar sua
discrição nesta transação, devido sua
natureza confidencial e secreta...
VOCÊ FOI SORTEADO PARA GANHAR 
UM PRÊMIO DE R$ 100,00 POR TER 
SIDO O 100º VISITANTE EM NOSSO 
WEBSITE HOJE! PARA OBTER SEU 
PRÊMIO RESPONDA ESTÁ MENSAGEM 
COM SEUS DADOS BANCÁRIOS!
Bom dia! Lembra daquela reunião de de 
amanhã? Ela foi adiada para a semana
seguinte, no mesmo horário. Você
estará disponível?
Exemplo: Reconhecimento de Dígitos
§ Entrada: imagem / matriz de pixels
§ Saída: um dígito de 0-9
§ Configuração:
§ Obtenha uma grande coleção de imagens, cada uma classificada
com um dígito de 0-9
§ Nota: alguém deve fazer esse processo manualmente!
§ Deseja-se aprender a classificar futuras novas imagens de dígitos
§ Características (features): atributos usados para decidir
entre os dígitos
§ Pixels: (6,8)=ON
§ Padrões de formato: NumComponentes, AspectRatio, NumLoops
§ …
0
1
2
1
??
Exemplo: Classificação de Flores de Íris
§ Entrada: dados tabulares
§ Saída: espécie (setosa, versicolor, virgínica)
§ Configuração:
§ Obtenha uma grande quantidade de linhas de dados, cada uma
classificada com uma espécie de íris
§ Nota: alguém deve fazer esse processo manualmente!
§ Deseja-se aprender a classificar futuras linhas de dados
§ Características (features): atributos usados para decidir a
espécie da flor
§ Comprimento e largura da sépala, comprimento e largura da pétala
Outros Problemas de Classificação
§ Classificação: dadas entradas x, predizer labels (classes) y
§ Exemplos:
§ Diagnóstico médico (entradas: sintomas,
classes: doenças)
§ Detecção de fraude (entrada: atividade bancária,
classes: fraude / não fraude)
§ Pontuação automática (entrada: prova,
classes: notas)
§ Identificação de emoções
§ Língua em um texto
§ … muitos outros
§ Classificação é uma tecnologia comercial importante!
Classificação Baseada em Modelo
Classificação Baseada em Modelo
§ Abordagem baseada em modelo
§ Construir um modelo (ex, rede Bayesiana) 
em que a saída (labels) e as entradas são
variáveis aleatórias
§ Instancie todas as variáveis observadas
(características)
§ Consulte pela distribuição da saída
condicionada às características
§ Desafios
§ Qual estrutura a rede deve ter?
§ Como devemos aprender os parâmetros?
Naïve Bayes para Dígitos
§ Naïve Bayes: Assume que todas as features são efeitos independentes da saída
§ Versão simples para reconhecimento de dígitos
§ Uma feature (variável) Fij para cada pixel <i,j>
§ Valores das features são on / off (1 / 0), baseada se a intensidade de cinza
é maior ou menor que 0.5
§ Cada entrada é mapeada para um vetor de características, ex.:
§ Muitos atributos, cada um valorado de forma binária
§ Naïve Bayes model:
§ O que precisamos aprender?
Y
F1 FnF2
Naïve Bayes Geral
§ Um modelo Naive Bayes geral:
§ Precisamos especificar como cada atributo depende da classe
§ Número total de parâmetros é linear em n
§ Modelo bastante simples, mas funciona em muitos cenários
Y
F1 FnF2
n x |F| x |Y| parâmetros|Y| x |F|n valores
Inferência em Modelos Naïve Bayes
§ Objetivo: calcular a distribuição posterior sobre a variável Y
§ Passo 1: obtenha a probabilidade conjunta da saída e das evidências
para cada classe (label)
§ Passo 2: Some para obter a probabilidade da evidência
§ Passo 3: Normalize para obter a probabilidade da saída dadas
dadas as evidências
+
Naïve Bayes Geral
§ O que precisamos para usar o modelo Naïve Bayes?
§ Método de inferência
§ Inicie com as tabelas de probabilidade: P(Y) e P(Fi|Y)
§ Use um algoritmo de inferência para obter P(Y|F1…Fn)
§ Nada de novo nesta etapa
§ Estimativa das tabelas de probabilidade condicional
§ P(Y), probabilidade a priori das classes
§ P(Fi|Y) para cada atributo (variáveis de evidência)
§ Essas probabilidades são chamadas de parâmetros do modelo e são
denotadas por q
§ Até agora, assumimos que essas tabelas eram dadas, mas…
§ …elas são tipicamente obtidas de um conjunto de dados de treino: iremos
ver isto em breve
Exemplo: Probabilidades Condicionais
1 0.1
2 0.1
3 0.1
4 0.1
5 0.1
6 0.1
7 0.1
8 0.1
9 0.1
0 0.1
1 0.01
2 0.05
3 0.05
4 0.30
5 0.80
6 0.90
7 0.05
8 0.60
9 0.50
0 0.80
1 0.05
2 0.01
3 0.90
4 0.80
5 0.90
6 0.90
7 0.25
8 0.85
9 0.60
0 0.80
Naïve Bayes para Texto
§ Naïve Bayes:
§ Atributos: Wi é a palavra na posição i
§ Predizer label (spam vs. não-spam) condicionada nas variáveis
§ Assumir que os atributos são condicionalmente independentes dada a classe
§ Novo: cada Wi é identicamente distribuída
§ Modelo:
§ Normalmente, cada variável tem sua própria distribuição P(F|Y)
§ Em um modelo chamado “bag-of-words”:
§ Cada posição é identicamente distribuída
§ Todas as posições compartilham as mesmas probabilidades P(W|Y)
§ Porque ter esta premissa?
§ O modelo insensível a ordem das palavras
Palavra na
posição i, não i-
ésima palavra do 
dicionário!
Exemplo: Filtro de Spam
§ Modelo:
§ Quais são os parâmetros?
§ De onde vem estas tabelas?
the : 0.0156
to : 0.0153
and : 0.0115
of : 0.0095
you : 0.0093
a : 0.0086
with: 0.0080
from: 0.0075
...
the : 0.0210
to : 0.0133
of : 0.0119
2002: 0.0110
with: 0.0108
from: 0.0107
and : 0.0105
a : 0.0100
...
no-spam : 0.66
spam: 0.33
Exemplo: Filtro de Spam
Word P(w|spam) P(w|not) Tot Spam Tot Not
(prior) 0.33333 0.66666 -1.1 -0.4
Gary 0.00002 0.00021 -11.8 -8.9
would 0.00069 0.00084 -19.1 -16.0
you 0.00881 0.00304 -23.8 -21.8
like 0.00086 0.00083 -30.9 -28.9
to 0.01517 0.01339 -35.1 -33.2
lose 0.00008 0.00002 -44.5 -44.0
weight 0.00016 0.00002 -53.3 -55.0
while 0.00027 0.00027 -61.5 -63.2
you 0.00881 0.00304 -66.2 -69.0
sleep 0.00006 0.00001 -76.0 -80.5
P(spam | w) = 98.9
Naïve Bayes para Dados Tabulares
§ Naïve Bayes:
§ Atributos (matriz): Cada coluna é um atributo diferente (variável aleatória)
§ Saída (vetor): Uma coluna específica define a saída (classe)
§ Iris Data Set:
§ Estimativa para dados contínuos (Gaussian Naive Bayes):
Y
F1 F4F2
Comprimento
da sépala (cm)
Largura da 
sépala (cm)
Comprimento 
da pétala (cm)
Largura da 
pétala (cm)
5.1 3.5 1.4 0.2
4.9 3 1.4 0.2
4.7 3.2 1.3 0.2
Classificação
Setosa (0)
Versicolor (1)
Virgínica (2)
F3
𝑃 𝑓!|𝑦 =
1
2𝜋𝜎"#
exp −
𝑓! − 𝜇"
#
2𝜎"#
Treinamento e Teste
Minimização Empírica de Riscos
§ Minimização empírica de riscos
§ Princípio básica de aprendizado de máquina
§ Queremos que o modelo (classificador, etc) que tenha melhor desempenho na
distribuição real de teste
§ Não conhecemos a distribuição real então selecionamos o melhor modelo com base 
no conjunto de treino
§ Encontrar o “melhor” modelo é por si só um problema de otimização
§ Preocupação: super-adaptação ao conjunto de treino (overfitting)
§ Melhor com mais dados (menor variância, mais próximo do conjunto de teste)
§ Melhor se limitarmos a complexidade da nossa hipótese (regularização e/ou espaço
reduzido de hipóteses)
Conceitos Importantes
§ Dados: instâncias classificadas (ex.: emailcomo spam ou não)
§ Conjunto de treinamento
§ Conjunto de validação
§ Conjunto de teste
§ Atributos: pares de atributos/classe que caracterizam cada
indivíduo no conjunto de dados
§ Ciclo de experimentação
§ Aprenda os parâmetros (ex.: probabilidades do modelo) no 
conjunto de treinamento
§ (Aprimore os hiperparâmetros no conjunto de validação)
§ Calcule o desempenho no conjunto de teste
§ Muito importante: nunca use os dados de teste na etapa de 
treinamento!
§ Avaliação (muitas métricas possíveis)
§ Acurácia: fração de instâncias classificadas corretamente
§ Overfitting e generalização
§ Queremos um classificador que se saia bem no conjunto de teste
§ Overfitting: modelo super-adaptado (decorado) ao conjunto de 
treino, mas pouca generalização
Dados de 
Treinamento
Dados de
Validação
Dados de
Teste
Generalização e Overfitting
0 2 4 6 8 10 12 14 16 18 20
-15
-10
-5
0
5
10
15
20
25
30
Polinômio de 15º grau
Overfitting
Exemplo: Overfitting
2 vence!!
Exemplo: Overfitting
§ Probabilidade relativas:
south-west : inf
nation : inf
morally : inf
nicely : inf
extent : inf
seriously : inf
...
O que houve de errado?
screens : inf
minute : inf
guaranteed : inf
$205.00 : inf
delivery : inf
signature : inf
...
Estimativa de Parâmetros
Estimativa de Parâmetros
§ Estimando a distribuição de uma variável aleatória
§ Elicitação: perguntar a um especialista (pouco prático?)
§ Empiricamente: use os dados de treino (aprendendo!)
§ Ex.: para cada resultado x, encontre sua taxa empírica:
§ Esta é a estimativa que maximiza a probabilidade dos dados
r r b
r b b
r bb
rb br bb
r
b
b
Máxima Probabilidade
§ Frequências relativas são estimativas de Máxima Probabilidade
Suavização
Eventos Não Observados
Suavização de Laplace
§ Estimativa de Laplace:
§ Imagine que você observou cada
resultado mais vezes do que você de 
fato viu
r r b
Suavização de Laplace
§ Estimativa de Laplace
§ Imagine que você viu cada resultado k vezes a 
mais
§ Laplace com k = 0?
§ k é a força da probabilidade a priori
r r b
Tuning (Refinamento)
Tuning nos Dados de Validação Held-Out Data
§ Agora temos dois tipos de valores
desconhecidos
§ Parâmetros: as probabilidades P(X|Y), P(Y)
§ Hiperparâmetros: ex.: quantidade de 
suavização, k
§ Como proceder?
§ Aprender os parâmetros dos dados de 
treino
§ Refinar os hiperparâmetros em um conjunto 
diferente. Porquê?
§ Para cada conjunto de hiperparâmetros, 
treine e teste nos dados de validação
§ Escolha o melhor conjunto de valores e 
teste no conjunto final de teste
Referência
§ Stuart RUSSEL e Peter NORVIG, Inteligência Artificial. 3ª ed.
§ Capítulo 20 (seções 20.1 a 20.2.2)