Mt803 Aula13 Bayes Rna Svm

Introdução à Aprendizagem de Máquina (Parte II)

Stanley R. M. Oliveira

Class

X1 X2 Xk...

A1

A2

Naïve Bayes Redes Neurais SVM

2MT-803: Introdução à Aprendizagem de Máquina – Aula 13.

Resumo da Aula

� Classificação Bayesiana:� Arcabouço probabilístico;� Classificador Naïve Bayes.

� Redes Neurais Artificiais (RNA):� Motivação, definições, aplicações.

� O modelo Perceptron.

� O Classificador MultiLayer Perceptron.

� Support Vector Machines (SVM):� Conceitos gerais.

� Abordagem para dados linearmente separáveis.

� Abordagem para dados não-linearmente separáveis.

Classificação Bayesiana

Class

X1 X2 Xk...

P(x1,…,xk|C) = P(x1|C) × P(x2|C) × … × P(xk|C)


Classificação Bayesiana ...

� Um arcabouço probabilístico para solucionar problemas de classificação.

� Predição probabilística: Prediz hipóteses múltiplas que são ponderadas por suas probabilidades.

� Classificador Bayesiano: prediz a probabilidade que uma dada amostra pertence a uma determinada classe.

� Incremental: Cada amostra no conjunto de treinamento pode aumentar/diminuir a probabilidade de que uma hipótese é correta.


Classificador “Naïve Bayes”

� Suposição: independência de atributos

P(x1,…,xk|C) = P(x1|C)× P(x2|C) × … × P(xk|C)

� Se o i-ésimo atributo for nominal:P(xi|C) é estimado como a frequência relativa das amostras no i-ésimo atributo (xi) que pertencem à classe C.

� Se o i-ésimo atributo for numérico:P(xi|C) é estimado através de uma função de densidadeGaussiana (Normal).

� Computacionalmente fácil em ambos os casos.


Classificação Bayesiana

� Na Prática: requer conhecimento inicial de muitas probabilidades ⇒ significativo custo computacional.

� Probabilidade Condicional :

� Teorema de Bayes :

)(

)()|()|(

AP

CPCAPACP =

)(

),()|(

)(

),()|(

CP

CAPCAP

AP

CAPACP

=

=


Classes:

compra_computador = ‘sim’

compra_computador = ‘nao’

Amostra:

X = (Idade <= 30,

Renda = media,

Aluno = ‘sim’

Credito = ‘normal’) ?

Idade Renda Aluno Credito Classe

<=30 alta nao normal nao

<=30 alta nao excelente nao

31…40 alta nao normal sim

>40 media nao normal sim

>40 baixa sim normal sim

>40 baixa sim excelente nao

31…40 baixa sim excelente sim

<=30 media nao normal nao

<=30 baixa sim normal sim

>40 media sim normal sim

<=30 media sim excelente sim

31…40 media nao excelente sim

31…40 alta sim normal sim

>40 media nao excelente nao

Classificador “Naïve Bayes”: Exemplo


� P(Ci): P(compra_computador = “sim”) = 9/14 = 0.643P(compra_computador = “nao”) = 5/14 = 0.357

� Cálculo de P(X|Ci) para cada classe:P(Idade = “<=30” | compra_computador = “sim”) = 2/9 = 0.222

P(Idade = “<= 30” | compra_computador = “nao”) = 3/5 = 0.6

P(Renda = “media” | compra_computador = “sim”) = 4/9 = 0.444

P(Renda = “media” | compra_computador = “nao”) = 2/5 = 0.4

P(Aluno = “sim” | compra_computador = “sim”) = 6/9 = 0.667

P(Aluno = “sim” | compra_computer = “nao”) = 1/5 = 0.2

P(Credito = “normal” | compra_computador = “sim”) = 6/9 = 0.667

P(Credito = “normal” | compra_computador = “nao”) = 2/5 = 0.4

� X = (Idade <= 30, Renda = media, Aluno = ‘yes’, Credito = ‘normal’) ??

P(X|Ci) : P(X|compra_computador = “sim”) = 0.222 x 0.444 x 0.667 x 0.667 = 0.044P(X|compra_computador = “nao”) = 0.6 x 0.4 x 0.2 x 0.4 = 0.019

P(X|Ci)*P(Ci) : P(X|compra_computador = “sim”) * P(compra_computador = “sim”) = 0.028P(X|compra_computador = “nao”) * P(compra_computador = “nao”) = 0.007

Portanto, X pertence a classe (“compra_computador = sim”).



Name Give Birth Can Fly Live in Water Have Legs Class

human yes no no yes mammalspython no no no no non-mammalssalmon no no yes no non-mammalswhale yes no yes no mammalsfrog no no sometimes yes non-mammalskomodo no no no yes non-mammalsbat yes yes no yes mammalspigeon no yes no yes non-mammalscat yes no no yes mammalsleopard shark yes no yes no non-mammalsturtle no no sometimes yes non-mammalspenguin no no sometimes yes non-mammalsporcupine yes no no yes mammalseel no no yes no non-mammalssalamander no no sometimes yes non-mammalsgila monster no no no yes non-mammalsplatypus no no no yes mammalsowl no yes no yes non-mammalsdolphin yes no yes no mammalseagle no yes no yes non-mammals

0027.020

13004.0)()|(

021.020

706.0)()|(

0042.013

4

13

3

13

10

13

1)|(

06.07

2

7

2

7

6

7

6)|(

=×=

=×=

=×××=

=×××=

NPNAP

MPMAP

NAP

MAP

A: attributes

M: mammals

N: non-mammals

P(A|M)P(M) > P(A|N)P(N)

=> Mammals

Give Birth Can Fly Live in Water Have Legs Class

yes no yes no ?


O valor do atributo “Class” é mammals ounon-mammals ?


Como estimar Probabilidades ?

� Distribuição Normal :

� Para cada par (Ai,ci).

� X(Renda=120; Classe=Nao)?� Se Classe = Nao

� Média da amostra = 110

� Variância da amostra = 2975

2

2

2

)(

22

1)|( ij

ijiA

ij

jiecAP

σ

µ

πσ

−−

=

0072.0)54.54(2

1)|120(Re )2975(2

)110120( 2

===−

−

eNaondaPπ

Tid Retorno EstadoCivil

RendaAnual Mentiu

1 Sim Solteiro 125K Nao

2 Nao Casado 100K Nao

3 Nao Solteiro 70K Nao

4 Sim Casado 120K Nao

5 Nao Divorciado 95K Sim


7 Sim Divorciado 220K Nao

8 Nao Solteiro 85K Sim


10 Nao Solteiro 90K Sim


Example of Naïve Bayes Classifier

? 120K)RendaCasado,ilEstado_Civ Nao,Retorno( ====Classe

� P(X|Classe=Nao) = P(Retorno=Nao|Classe=Nao)× P(Casado| Classe=Nao)× P(Renda=120K| Class=Nao)

= 4/7 × 4/7 × 0.0072 = 0.0024

� P(X|Class=Yes) = P(Retorno=Nao| Classe=Sim)× P(Casado| Classe=Sim)× P(Renda=120K| Classe=Sim)

= 1 × 0 × 1.2 × 10-9 = 0

Como P(X|Nao)P(Nao) > P(X|Sim)P(Sim)

Portanto P(Nao|X) > P(Sim|X)=> Classe = Nao.

P(Refund=Yes|No) = 3/7P(Refund=No|No) = 4/7P(Refund=Yes|Yes) = 0P(Refund=No|Yes) = 1P(Marital Status=Single|No) = 2/7P(Marital Status=Divorced|No)=1/7P(Marital Status=Married|No) = 4/7P(Marital Status=Single|Yes) = 2/7P(Marital Status=Divorced|Yes)=1/7P(Marital Status=Married|Yes) = 0

For taxable income:If class=No: sample mean=110

sample variance=2975If class=Yes: sample mean=90

sample variance=25

naive Bayes Classifier:Classificador Naïve Bayes


Exercício – Naïve Bayes� Calcular a probabilidade, utilizando o teorema de Bayes,

para o problema de previsão de tempo para jogar tênis.

� Amostra (aspecto = sol, temp = fresco, umidade = elevada,

vento = forte) = ?


O problema da Probabilidade Nula

� O Classificador Naïve Bayes requer que cada probabilidade condicional seja não nula.

� Caso uma das probabilidades seja nula, usa-se a correção de Laplace:

∏=

=n

kCixkPCiXP

1

)|()|(

c: número de classes

p: probabilidade a priori

m: parâmetro

mN

mpNCAP

cN

NCAP

N

NCAP

c

ici

c

ici

c

ici

++

=

++

=

=

)|(:estimate-m

1)|(:Laplace

)|( :Original


Classificador “Naïve Bayes” ...

� Robusto com relação a ruídos (pontos isolados).

� Capacidade de lidar com valores “missing” ignorando a observação durante o cálculo de estimativa de probabilidade.

� Robusto com relação aos atributos irrelevantes.

� Na prática, se um modelo possui atributos independentes, o classificador bayesiano pode superar as árvores de decisão.

� Por outro lado, a suposição de independência pode não funcionar bem para alguns domínios.

� Solução: uso de outras técnicas, tais como redes de crença Bayesiana (BBN).

Redes Neurais


Redes Neurais

Motivação

� Cérebro

� Organiza os neurônios para executar tarefas muito mais rapidamente que os computadores digitais.

� Constrói as próprias regras através de experiência (conhecimento).


Processo de InferênciaSistemas Especialistas

Processamento linguísticoLógica Fuzzy

Evolução biológicaComputação Evolucionária

Neurônios biológicosRedes Neurais Artificiais

Inspiração na NaturezaTécnica Computacional

Técnica x Natureza


Definições:

� Técnica inspirada no funcionamento do cérebro, onde neurônios artificiais, conectados em rede, são capazes de aprender e de generalizar.

� Técnica de aproximação de funções por regressão não linear.

Redes Neurais Artificiais (RNA)


Redes Neurais Artificiais (RNA) ...

� A característica mais significante de redes neurais está em sua habilidade de aproximarqualquer função contínua ou não contínua com um grau de correção desejado.

� Esta habilidade das redes neurais as tem tornado útil para modelar sistemas não lineares.



� Devido à sua estrutura, as Redes Neurais Artificiais são bastante efetivas no aprendizado de padrões a partir de dados:

� não-lineares,

� incompletos,

� com ruído e até

� compostos de exemplos contraditórios.


� Definição:� Processador paralelo distribuído com capacidade

natural para armazenar conhecimento experimental e disponibilizá-lo para uso.

� Imita o cérebro de duas formas:

� aquisição de conhecimento através de aprendizagem;

� armazenamento do conhecimento nas conexões inter-neurônios (pesos)

� A aprendizagem é feita por um algoritmo que modificaos pesos da rede de uma forma ordenada para adquirir uma arquitetura previamente desejada.

� Além da modificação dos pesos uma rede pode modificar sua própria topologia.



� Modelam a forma do cérebro desempenhar funções ou tarefas.

� Implementação em hardware ou simuladas em software.

� Possuem interconexão maciça das células computacionais para adquirir um bom desempenho.

� Desempenham as computações através da aprendizagem.

Redes Neurais Artificiais (RNA)...


� As sinapses (entradas), com seus pesosassociados.

� A junção somadora; e

� A função de ativação → permitem que os nodos ocultos ou de saída produzam valores não lineares.

Componentes de um neurônio artificial


Componentes de um neurônio artificial

pesos sinápticos


Princípio de funcionamentoA operação de um neurônio artificial se resume em:

� Sinais são apresentados à entrada (x1 a xm);

� Cada sinal é multiplicado por um peso que indica sua influência na saída da unidade (wk);

� É feita a soma ponderada dos sinais que produz um nível de atividade (uk);

� A função de ativação f(uk) tem a função de limitar a saída e introduzir não-linearidade ao modelo.

� O bias bk tem o papel de aumentar ou diminuir a influência do valor das entradas.

� É possível considerar o bias como uma entrada de valor constante 1, multiplicado por um peso igual a bk.


� Matematicamente a saída pode ser expressa por:

ou considerando o bias como entrada de valor x0=1 e peso wk0=bk,

Expressão matemática do neurônio


Funções de ativação


Exemplo de uma RNA

Output Y é 1 se pelo menos 2 dos 3 argumentos do vetor X são iguais a 1.

X1 X2 X3 Y1 0 0 01 0 1 11 1 0 11 1 1 10 0 1 00 1 0 00 1 1 10 0 0 0

X1

X2

X3

Y

Caixa preta

Output

Input


Exemplo de uma RNA ...

X1 X2 X3 Y1 0 0 -11 0 1 11 1 0 11 1 1 10 0 1 -10 1 0 -10 1 1 10 0 0 -1

ΣΣΣΣ

X1

X2

X3

Y

Caixa preta

0.3

0.3

0.3 t=0.4

Outputnó

Inputnós

=-1,

seonde Y

>−++ 0;0.40.30.30.31, 321 XXX

se <−++ 0.0.40.30.30.3321

XXX


� O modelo é um conjunto de nós interconectados e links com pesos.

� O nó output soma cada um de seus valores de input de acordo com os pesos de seus links.

� O nó output é então comparado com algum threshold t.

)( tXwIYi

ii −= ∑

Modelo Perceptron:

)( tXwsignYi

ii −= ∑

ou

O Modelo Perceptron


Um neurônio

� O vetor x (n-dimensional) é mapeado em uma variável ypor meio do produto escalar e de um mapeamento de uma função não-linear.

µk-

f

Soma Ponderada

Inputvetor x

Output y

Função de Ativação

Pesosvetor w

∑

w0

w1

wn

x0

x1

xn

)sign(y

:ExemploPor

n

0i

kiixw µ+= ∑=


Estrutura geral de uma rede neural

O treinamento da rede significa –encontrar (aprender) os pesos dos neurônios.


Redes Neurais Artificiais

� Vantagens:� A precisão da classificação é geralmente alta.

� Robusta – tolerância a ruídos em amostras.

� Output pode assumir valores discretos, reais, ou um vetor de valores discretos ou reais.

� Rápida avaliação da função de aprendizado.

� Desvantagens:� O tempo do treinamento é longo.

� Requer um número de parâmetros que é melhor determinado empiricamente.

� Dificuldade de interpretação dos pesos.

� Não é fácil de incorporar conhecimento do domínio.


Redes Neurais Artificiais: Aplicações� Engenharia (civil, mecânica, elétrica etc).

� Finanças.

� Controle e automação.

� Reconhecimento de padrões.

� Aproximação de funções.

� Processamento de imagens.

� Visão computacional.

� Robótica.

� Linguagem natural.

� Bioinformática, etc ...


Treinamento da rede

� Objetivo final do treinamento

� Obter um conjunto de pesos que permite que quase todas as tuplas

no conjunto de treinamento sejam classificadas corretamente.

� Passos

� Os pesos são inicializados com valores aleatórios.

� As tuplas (vetor de input) são alimentadas na rede uma por uma.

� Para cada unidade (neurônio):

� Computar a entrada da rede para a unidade como uma combinação linear de todas as entradas para a unidade;

� Computar o valor de saída (output) – usa a função de ativação;

� Computar o erro;

� Atualizar os pesos.


Principais modelos de Redes Neurais

� Perceptrons de múltiplas camadas (algoritmo de retropropagação - Backpropagation).

� Redes de Função de Base Radial (RBF).

� Mapas auto-organizáveis (SOM).

� Máquinas de Vetor de Suporte (SVM), etc ...


Classificador Multi-Layer Perceptron

Output nodes

Input nodes

Hidden nodes

Output vector

Input vector: xi

wij

∑ +=i

jiijj OwI θ

jIje

O −+=1

1

))(1( jjjjj OTOOErr −−=

jkk

kjjj wErrOOErr ∑−= )1(

ijijij OErrlww )(+=

jjj Errl)(+=θθ


Algoritmo do MultiLayer Perceptron

� Iniciar os pesos (w0, w1, …, wk)

�Ajustar os pesos de tal maneira que o outputda rede seja consistente com as classes do conjunto de treinamento.

� Função Objetivo:

� Encontrar os pesos wi’s que minimizam a função objetivo acima.

� Exemplo: algoritmo backpropagation.

[ ]2),(∑ −=i

iii XwfYE


Backpropagation - Problema XOR

OU exclusivo:

Entrada Saída0 1 10 0 01 1 01 0 1

Support Vector Machines

A1

A2


SVM — Idéia Geral

Vetores Suporte

Menor Margem Maior Margem


m

Seja D (X1, y1), …, (X|D|, y|D|), onde Xi é o conjunto de tuplas de treinamento associadas à classe yi.

Existem infinitas linhas (hiperplanos) separando duas classes. O alvo éachar o melhor hiperplano que minimize o erro da classificação.

SVM busca o hiperplano com a maior margem (maximum marginal hyperplane - MMH).

SVM— Dados separados linearmente


SVM—Support Vector Machines� Um novo método de classificação para dados linear e não-linear.

� SVM usa um mapeamento não-linear para transformar os dados originais (treinamento) em uma dimensão maior.

� Na nova dimensão, SVM busca um hiperplano que gere uma separação linear ótima.

� SVM sempre separa duas classes por meio de um hiperplano com a maior distância entre as classes.

� SVM encontra o hiperplano usando vetores suportes(tuplas especiais no treinamento) e margens definidas pelos vetores suportes.



Encontrar um hiperplano linear (limite de decisão) capaz de separar os dados.



� Uma possível solução.



� Outra possível solução.



� Outras possíveis soluções.



� Qual é o melhor hiperplano? B1 ou B2?

� Como podemos definir o melhor?



� Encontrar um hiperplano que maximize a margem => B1 é melhor do que B2.



0=+• bxwrr

1−=+• bxwrr

1+=+• bxwrr

−≤+•−

≥+•=

1bxw if1

1bxw if1)( rr

rrrxf

2||||

2 Margin

wr=



� Nós queremos maximizar:

� Que é equivalente a minimizar:

� mas sujeito às seguintes restrições:

� Como a função objetivo é quadrática e as restrições são lineares nos parâmetros w e b→ otimização convexa.� Abordagem numérica p/ solucionar → programação quadrática.

2||||

2 Margin

wr=

−≤+•−

≥+•=

1bxw if1

1bxw if1)(

i

irr

rrrixf

2

||||)(

2wwL

r

=



� E se o problema não for linearmente separável?



� E se o problema não for linearmente separável?� Introduzir variáveis slack (folga) nas restrições:

� Minimizar a função objetivo:

� sujeita a:

+−≤+•−

≥+•=

ii

ii

1bxw if1

-1bxw if1)(

ξξ

rr

rrrixf

+= ∑

=

N

i

k

iCw

wL1

2

2

||||)( ξ

r


Nonlinear Support Vector Machines

� E se o limite de decisão não for linear?


Nonlinear Support Vector Machines� Transformar os dados originais (treinamento) para uma

dimensão maior.


SVM é eficaz para alta dimensionalidade?

� A complexidade do classificador treinado é caracterizada pelo

número de vetores suporte e não pela dimensionalidade dos dados.

� Os vetores suporte são exemplos de treinamentos essenciais ou

críticos.

� Se um treinamento for repetido, os mesmos hiperplanos de separação

devem ser encontrados (determinístico).

� O número de vetores suporte encontrado pode ser usado para

computar (upper) bound na taxa de erro esperado do classificador

SVM, que é independente da dimensionalidade dos dados.

� Assim, SVM com um pequeno número de vetores suporte pode ter

boa generalização, mesmo com a dimensionalidade dos dados alta.


SVM versus Redes Neurais

� SVM

� Novo conceito

� Algoritmo determinístico

� Ótimas propriedades para generalização

� Aprendizado difícil – usa técnicas de programação quadrática.

� Usando kernels (núcleos) écapaz de aprender funções complexas.

� Redes Neurais

� Relativamente velho

� Algoritmo não-determinístico

� Generaliza bem, mas não tem forte fundamento matemático

� Pode aprender facilmente em um modo incremental.

� Para aprender funções complexas pode-se usar omultilayer perceptron (que não é trivial).


SVM – Links Relacionados

� SVM Website:

� http://www.kernel-machines.org/

� Exemplos de Implementações:

� LIBSVM: Uma implementação eficiente do SVM, Classificação

multi-classes, incluindo várias interfaces com java, python, etc.

� SVM-light: Implementação mais simples, com performance

inferior ao LIBSVM. Suporta somente classificação binária.

Implementada em linguagem C.

� SVM-torch: Recente implementação também em Linguagem C.

Documents

Mt803 Aula13 Bayes Rna Svm