View
216
Download
0
Category
Preview:
Citation preview
1
PTC-5001 Reconhecimento de Padrões (aula2)
1
TEORIA DA DECISÃO BAYESIANA
• A teoria da decisão Bayesiana é fundamental em reconhecimento de padrões
• Objetivo: separar classes, mas de forma probabilística
• A decisão é baseada em probabilidades e nos custos envolvidos na decisão
• Para isso, as probabilidades devem ser conhecidas (normalmente estimadas)
PTC-5001 Reconhecimento de Padrões (aula2)
2
• O exemplo dos peixes poderia ser considerado como probabilístico
PTC-5001 Reconhecimento de Padrões (aula2)
3
• Enfoque probabilístico
PTC-5001 Reconhecimento de Padrões (aula2)
4
Resumo
• Decisão Bayesiana por meio de exemplo
• Generalização da teoria Bayesiana
• Casos particulares
• Critérios para minimização do risco
• Funções discriminantes e superfícies de decisão
• Densidade normal e transformações lineares
• Funções discriminantes para densidade normal
• Erros e regiões de decisão
• Características discretasPTC-5001 Reconhecimento de Padrões
(aula2)5 PTC-5001 Reconhecimento de Padrões
(aula2)6
Uma primeira idéia: classificador utilizando apenas as probabilidades a priori
• Considerando o estado da natureza (classe) descrito pela variável aleatória Exemplo dos peixes: dois estados corvina = 1 e salmão = 2
• P(1) e P(2) probabilidades a priori (anteriores) (conhecimento anterior)
2
PTC-5001 Reconhecimento de Padrões (aula2)
7
Classificador utilizando apenas as probabilidades a priori
• Regra de Decisão:
Decida por 1 se P(1) > P(2),
senão decida por 2
• Qual é a utilidade?
PTC-5001 Reconhecimento de Padrões (aula2) 8
Melhoria: classificador utilizando uma característica (ou atributo) (feature)
Ex.: x=luminosidade do peixe (variável aleatória contínua)p(x|) função densidade de probabilidade
condicionada à classeé a função densidade de probabilidade de x dado
Exemplo dos peixes: a diferença entre p(x|1) e p(x|2) descreve a diferença de luminosidade entre as populações de corvina e salmão
PTC-5001 Reconhecimento de Padrões (aula2)
9
p(x|1) e p(x|2)
PTC-5001 Reconhecimento de Padrões (aula2)
10
Resulta o problema
• Considere que
se tem P(j) e p(x|j) para j = 1,2
e se mede x (luminosidade) de um peixe
Como esse conhecimento possibilita uma melhor classificação do peixe?
PTC-5001 Reconhecimento de Padrões (aula2)
11
• Na verdade, queremos
P(j|x)
isto é, a probabilidade da classe ser j,dada a luminosidade x do peixe
PTC-5001 Reconhecimento de Padrões (aula2)
12
Cálculo de P(j|x)
1 27 corvinas
2 18 salmões
x (discretizado)
P(j,x) = P(x|j)P(j) = P(j|x)P(x)
Resulta o ...
3
PTC-5001 Reconhecimento de Padrões (aula2)
13
Teorema de Bayes
Tem-se p(j,x) = P(j|x) p(x)
p(j,x) = p(x|j) P(j)
onde p(j,x) é a função densidade de probabilidade conjuntaResulta
xp
PxpxP jj
j
||
jj
j Pxpxpcom
2
1
|
PTC-5001 Reconhecimento de Padrões (aula2)
14
Nomenclatura
• Posterior
P(j|x) = probabilidade do estado da natureza (classe) ser j, dado x
• Verossimilhança
p(x|j) = verossimilhança de j em relação a x , isto é,
a classe j para a qual p(x|j) é maior, é a
mais verossímil (para iguais P(j))
• Evidência p(x) = apenas um fator de escala
posterior = verossimilhança anterior / evidência
PTC-5001 Reconhecimento de Padrões (aula2)
15
Considerando p(x|1) e p(x|2) ...
PTC-5001 Reconhecimento de Padrões (aula2)
16
Resulta P(j|x) para P(1)=2/3 e P(2)=1/3
PTC-5001 Reconhecimento de Padrões (aula2)
17
Como fazer a decisão por Bayes?Parece natural a regra
Se P(1|x) > P(2|x) escolha 1
Se P(2|x) > P(1|x) escolha 2
Senão 1 ou 2
PTC-5001 Reconhecimento de Padrões (aula2)
18
Para justificá-la, calcula-se a probabilidade de erro para um determinado x observado
P(erro|x) = P(1|x) se decidimos por 2
P(2|x) se decidimos por 1
• Considerando a regra de decisão:
Escolha a classe j com maior P(j|x)
P(erro|x) = min(P(1|x),P(2|x))
4
PTC-5001 Reconhecimento de Padrões (aula2)
19
Qual a probabilidade média de erro?
Quanto menor P(erro|x), menor P(erro)
Como P(erro|x) = min(P(1|x),P(2|x))
A decisão por Bayes minimiza a probabilidade de erro
dxxpxerroPdxxerroperroP
|,
PTC-5001 Reconhecimento de Padrões (aula2)
20
Outra forma da regra de decisão de Bayes
Tem-se
Note que p(x) é apenas um fator de escalaPortanto,
“ Decida por 1 se
Senão decida por 2”
2211 || PxpPxp
xp
PxpxP jj
j
||
PTC-5001 Reconhecimento de Padrões (aula2)
21
Teoria da decisão Bayesiana
Generalização
PTC-5001 Reconhecimento de Padrões (aula2)
22
Teoria da decisão Bayesiana(características contínuas)
Generalização
• Vetor de características x Rd
(espaço euclideano de características)• Várias classes {1, 2,..., c}• Várias ações {1, 2,..., a}• Função perda (i|j) descreve a perda (custo)
de tomar a ação i quando o estado da natureza é j
PTC-5001 Reconhecimento de Padrões (aula2)
23
Várias classes {1, 2,..., c} e vetor x
• Bayes
x
xx
p
PpP jj
j
||
jj
c
j
Pppcom |)(1
xx
PTC-5001 Reconhecimento de Padrões (aula2)
24
Risco
• Suponha que se observe x, que se tome a ação i, e o verdadeiro estado da natureza seja j
perda (i|j)
• Considerando todos os estados da natureza, a perda esperada (risco) em se tomar a ação i é
é o risco condicional
xx |||1
j
c
jjii PR
x|iR
5
PTC-5001 Reconhecimento de Padrões (aula2)
25
Risco total
• O risco total R é a perda esperada para uma determinada regra de decisão
onde (x) é a função de decisão que para cada x assume um valor 1.... a
Se para cada x, escolhermos (x)= i de modo que R((x)|x) seja mínimo
o risco total será minimizado
xxxx dpRR |
PTC-5001 Reconhecimento de Padrões (aula2)
26
Regra de decisão de Bayes (risco)
“Para minimizar o risco total, calcule R(i|x) para i=1,...,a, e então escolha a ação i para a
qual R(i|x) seja mínimo”
O risco total resultante é chamado
Risco de Bayes R*
xx |||1
j
c
jjii PR
PTC-5001 Reconhecimento de Padrões (aula2)
27
Teoria da decisão Bayesiana
Casos particulares
PTC-5001 Reconhecimento de Padrões (aula2)
28
Classificação em duas categorias
• Sejam as ações 1 corresponde a decidir por 1
2 corresponde a decidir por 2
• Considerando
e simplificando a notação: i,j = (i|j) , resulta
xx |||1
j
c
jjii PR
xxx ||| 22,111,11 PPR
xxx ||| 22,211,22 PPR
PTC-5001 Reconhecimento de Padrões (aula2)
29
Classificação em duas categorias
Regra de decisão:
Escolha 1 se R(1|x) < R(2|x)
Ou utilizando Bayes
com 2,1- 1,1 > 0 e 1,2- 2,2 > 0
xx || 22,22,111,11,2 PP
222,22,1111,11,2 || PpPp xx
PTC-5001 Reconhecimento de Padrões (aula2)
30
Classificação em duas categorias
• Outra forma: isolando a dependência de x em
Decida 1 se
onde
é a razão de verossimilhança
1
2
1,11,2
2,22,1
2
1
|
|
P
P
p
p
x
x
222,22,1111,11,2 || PpPp xx
2
1
|
|
x
x
p
p
6
PTC-5001 Reconhecimento de Padrões (aula2)
31
A região do espaço de x que se decide por i é Ri
PTC-5001 Reconhecimento de Padrões (aula2)
32
Classificação por taxa mínima de erro
• Se ação i corresponde a classificar em i
ação correta i=j
erro ij
• Vamos procurar a regra de decisão que minimiza a probabilidade de erro (taxa de erro)
• Para isso, deve-se calcular
xx |||1
j
c
jjii PR
PTC-5001 Reconhecimento de Padrões (aula2)
33
Classificação por taxa mínima de erro
• Nesse caso a função perda de interesse é chamada simétrica ou zero-um, ou seja
i,j = 0 se i = j i,j = 1....c
i,j = 1 se i j
todos os erros tem o mesmo custo
PTC-5001 Reconhecimento de Padrões (aula2)
34
Classificação por taxa mínima de erro
• Calculando o risco condicional
onde P(i|x) é a probabilidade condicional que a
ação i seja correta
xxxx |1||||1
iij
jj
c
jjii PPPR
xx |1| ii PR
PTC-5001 Reconhecimento de Padrões (aula2)
35
Classificação por taxa mínima de erro
• Resulta a regra de decisão (Bayes)
Decida por i se
P(i|x) > P(j|x) para todo j i
e a taxa de erro será mínima!
PTC-5001 Reconhecimento de Padrões (aula2)
36
Critérios para minimização do risco
7
PTC-5001 Reconhecimento de Padrões (aula2)
37
Critério Minimax
• Minimiza o máximo risco para uma faixa de probabilidades a priori
PTC-5001 Reconhecimento de Padrões (aula2)
38
Critério Neyman-Pearson
• Minimiza risco total sujeito a uma restrição.
• Isso pode ocorrer quando:a) há um recurso fixo para determinada ação i
b) não se pode classificar erroneamente um padrãode estado da natureza i mais que determinadafreqüênciaEx.: lei governamental pode-se errar no máximo
1% na classificação do salmão• Tem solução analítica para distribuição gaussiana e
algumas outras
PTC-5001 Reconhecimento de Padrões (aula2)
39
Classificadores, funções discriminantes e
superfícies de decisão
PTC-5001 Reconhecimento de Padrões (aula2)
40
Classificadores, funções discriminantes e
superfícies de decisão
• De um ponto de vista mais geral, pode-se considerar os classificadores de padrões representados por conjuntos de
funções discriminantes gi(x)
de forma a atribuir um vetor x a classe i
(região Ri do espaço de x) se
gi(x) > gj(x) para todo j i
PTC-5001 Reconhecimento de Padrões (aula2)
41
• Resulta o conceito: Classificador = máquina que calcula c funções discriminantes e escolhe a classe correspondente ao maior discriminante
PTC-5001 Reconhecimento de Padrões (aula2)
42
Classificador Bayesiano
gi(x) = - R(i|x)
onde a função discriminante máxima corresponde ao risco mínimo
• Caso da taxa mínima de erro
gi(x) = P(i|x)
8
PTC-5001 Reconhecimento de Padrões (aula2)
43
• A escolha da função discriminante não é única
• Pode-se aplicar em gi(x) uma função monotonicamente crescente f(gi(x))
c
jjj
iiii
Pp
PpPg
1
|
||
x
xxx
iii Ppg |xx
iii Ppg ln|ln xx
PTC-5001 Reconhecimento de Padrões (aula2)
44
Regiões e fronteiras de decisão
• Note que
Qualquer regra de decisão divide o espaço de características em c regiões de decisão R1...Rc
separadas por fronteiras de decisão
PTC-5001 Reconhecimento de Padrões (aula2)
45
Fronteiras de decisão separam as regiões de decisão
PTC-5001 Reconhecimento de Padrões (aula2)
46
Caso de duas classes
• É um classificador “dicotomizador”
• No lugar de utilizar duas funções discriminantes g1 e g2 e atribuir x a 1 se g1>g2, utiliza-se
g(x) = g1(x) - g2(x)
com a regra:
Decida por 1 se g(x) > 0
Senão decida por 2
O classificador calcula apenas uma função discriminante g(x) e classifica de acordo com o sinal da função
PTC-5001 Reconhecimento de Padrões (aula2)
47
Caso de duas classes
• Formas da função discriminante para taxa mínima de erro
xxx || 21 PPg
2
1
2
1 ln|
|ln
P
P
p
pg
x
xx
PTC-5001 Reconhecimento de Padrões (aula2)
48
Densidade normal
9
PTC-5001 Reconhecimento de Padrões (aula2)
49
Densidade normal
• Classificador de Bayes necessita de p(x|i) e P(i)
• Densidade normal (ou gaussiana) multivariável- Frequentemente um modelo adequado
(teorema do limite central)- Modela situações onde o vetor de características x
de uma classe i é contínuo e aleatoriamente corrompido a partir de um protótipo i
- Interesse analíticoPTC-5001 Reconhecimento de Padrões
(aula2)50
Densidade normal
Teorema do limite central
“O efeito resultante da soma de um grande número de perturbações aleatórias e independentes (com qq. distribuição) resulta numa distribuição gaussiana”
PTC-5001 Reconhecimento de Padrões (aula2)
51
Densidade normal
• Densidade de uma variável N(,2)
onde a média é
e a variância é
dxxxpx
dxxpxx
222
2
2
1exp
2
1
x
xp
PTC-5001 Reconhecimento de Padrões (aula2)
52
PTC-5001 Reconhecimento de Padrões (aula2)
53
Densidade normal multivariável
• Densidade normal para d dimensões p(x)~N(, )
onde x = vetor coluna de d componentes = vetor média = matriz de covariância (dxd)|| = determinante de e -1 = inversa de (x - )t = transposto de (x - )
é a distância de Mahalanobis (quadrática) μxΣμxx 12 td
μxΣμx
Σ
x 1
2
1
22
1exp
||2
1 t
dp
PTC-5001 Reconhecimento de Padrões (aula2)
54
Matriz de covariância
com
• é sempre simétrica e positiva semi-definida(y yT y 0)
• Vamos considerar sempre positiva definida• ii é a variância de xi
• ij é a covariância de xi e xj (mede a correlação)• Se xi e xj não são correlacionados então ij = 0• Se todos ij = 0 p(x)= p(x1) p(x2)... p(xd)
ii x
xxμxμxμxμxΣ dptt
jjiiji xx
10
PTC-5001 Reconhecimento de Padrões (aula2)
55
Alguns fatos sobre distribuição gaussiana
• É completamente caracterizada pelos seus dois primeiros momentos: média () e covariância ()
• As densidades marginais p(xi) , p(xi , xj) , etc.
são gaussianas
• Se as componentes de x não são correlacionadas, resulta
p(x)= p(x1) p(x2)... p(xd)
ou seja, “variáveis aleatórias gaussianas não-correlacionadas são também estatisticamente independentes”
• Funções lineares de variáveis aleatórias gaussianas são também gaussianas
PTC-5001 Reconhecimento de Padrões (aula2)
56
Transformações lineares
• Seja y = At x onde A é uma matriz d x kSe p(x) ~N(, ) então p(y) ~N(At, AtA)
• Particularmente, se k=1 (vetor) e fazendo A = a y=at x é um escalar que representa a projeção de x em aata representa a variância da projeção de x em a
PTC-5001 Reconhecimento de Padrões (aula2)
57 PTC-5001 Reconhecimento de Padrões (aula2)
58
Transformações lineares
Diagonalização
• Como é uma matriz real simétrica ela pode ser sempre diagonalizada por uma transformação ortonormal
y = t x onde é a matriz cujas colunas são autovetores ortonormais de (logo t = I)
• Assim, existem coordenadas nas quais as componentes de uma variável aleatória gaussiana são estatisticamente independentes
PTC-5001 Reconhecimento de Padrões (aula2)
59
Transformação Whitening
• É possível transformar uma distribuição gaussiana arbitrária numa esférica, isto é, que possui uma matriz de covariância proporcional à matriz identidade I
• Se é a matriz cujas colunas são autovetores ortonormais de , e a matriz diagonal dos autovalores correspondentes, então a transformação
resulta numa distribuição com matriz de covariância igual a matriz identidade
2
1
ΦΛAw
PTC-5001 Reconhecimento de Padrões (aula2)
60
Distância de Mahalanobis
• Amostras obtidas de uma população gaussiana tendem a se situar num aglomerado (cluster) cujo centro é determinado por e forma determinada por
• Os pontos de igual densidade de probabilidade possuem distância de Mahalanobis d(x) constante, onde
• Basta ver em
μxΣμxx 12 td
μxΣμx
Σ
x 1
2
1
22
1exp
||2
1 t
dp
11
PTC-5001 Reconhecimento de Padrões (aula2)
61 PTC-5001 Reconhecimento de Padrões (aula2)
62
• Os contornos de igual densidade de probabilidade são hiperelipsóides (de distância de Mahalanobis constante)
• O volume desses hiperelipsóides medem o espalhamento das amostras em relação a média
• Os eixos principais dos hiperelipsóides são determinados pelos autovetores de (descritos por )
• Os comprimentos desses eixos são determinados pelos autovalores (de )
PTC-5001 Reconhecimento de Padrões (aula2)
63
Eixos principais dos hiperelipsóides
PTC-5001 Reconhecimento de Padrões (aula2)
64
Funções discriminantes para densidade normal
PTC-5001 Reconhecimento de Padrões (aula2)
65
Funções discriminantes para densidade normal
• Lembre-se que a escolha da função discriminante não é única
c
jjj
iiii
Pp
PpPg
1
|
||
x
xxx
iii Ppg |xx
iii Ppg ln|ln xx
PTC-5001 Reconhecimento de Padrões (aula2)
66
Funções discriminantes para densidade normal
• Densidade normal p(x) ~N(, )
• Função discriminante mais adequada
• Resulta
iii Ppg ln|ln xx
iiiit
ii Pd
g ln||ln2
12ln
22
1 1 ΣμxΣμxx
μxΣμx
Σ
x 1
2
1
22
1exp
||2
1 t
dp
12
PTC-5001 Reconhecimento de Padrões (aula2)
67
Funções discriminantes para densidade normal
Caso 1: i= 2 I
• Características (não correlacionadas) estatisticamente independentes
Cada característica tem variância 2
matriz de covariância 2 I
• Os pontos de igual densidade de probabilidade pertencem a superfícies hiperesféricas
PTC-5001 Reconhecimento de Padrões (aula2)
68
• A função
simplifica
com
ii
i Pg
ln2
||||2
2
μx
x
it
ii μxμxμx 2||||
iiiit
ii Pd
g ln||ln2
12ln
22
1 1 ΣμxΣμxx
PTC-5001 Reconhecimento de Padrões (aula2)
69
Note que• Se x estiver eqüidistante de dois vetores média,
então a decisão ótima será a favor da classe que tiver maior probabilidade a priori
• Se as probabilidades a priori forem idênticas, então a decisão ótima será a favor da classe de média mais próxima
ii
i Pg
ln2
||||2
2
μx
x
PTC-5001 Reconhecimento de Padrões (aula2)
70
• Desenvolvendo a expressão
• Observe que o termo quadrático é independente de i
discriminante linear
iiti
tti Pg
i
ln2
2
12
μμxμxxx
ii
i Pg
ln2
||||2
2
μx
x
PTC-5001 Reconhecimento de Padrões (aula2)
71
Discriminante linear
ou
wi0 é o limiar (threshold, bias) da classe i
0itii wg xwx
ii μw2
1
ii
tii Pw
ln
2
120 μμ
iiti
tti Pg
i
ln2
2
12
μμxμxxx
PTC-5001 Reconhecimento de Padrões (aula2)
72
• Um classificador que utiliza uma função discriminante linear é chamado de
máquina linear
• As superfícies de decisão são
hiperplanos
resultantes de gi(x) = gj(x)
13
PTC-5001 Reconhecimento de Padrões (aula2)
73
• De gi(x)=gj(x) ou
Resulta
Com
00 jtjji
tii wgwg xwxxwx
00 xxw t
ji μμw
ji
j
i
jiji P
Pμμ
μμμμx
ln||||2
12
2
0
PTC-5001 Reconhecimento de Padrões (aula2)
74
• Considerando
• Estas eq. definem um hiperplano que passa por x0 e ortogonal ao vetor
• Logo o hiperplano separando Ri e Rj é ortogonal a linha que une as médias
• Note se P(i) = P(j) resulta
• Se P(i) P(j) o ponto x0 se afasta da média mais provável
ji μμw
ji μμx 2
10
00 xxw t
ji μμw ji
j
i
jiji P
Pμμ
μμμμx
ln||||2
12
2
0
PTC-5001 Reconhecimento de Padrões (aula2)
75 PTC-5001 Reconhecimento de Padrões (aula2)
76
PTC-5001 Reconhecimento de Padrões (aula2)
77
• Analisando por outro ângulo
Note que se P(i) é a mesma para todas as c classes, então de
resulta
ii
i Pg
ln2
||||2
2
μx
x
2
2
2
||||
i
igμx
x
PTC-5001 Reconhecimento de Padrões (aula2)
78
Classificador baseado na distância mínima
• Para classificar um vetor característica x, meça a distância euclideana de x a cada um dos c vetores média,
e atribua x à classe da média mais próxima
• Cada vetor média pode ser considerado um protótipo (template) de sua classe (template matching)
|||| iμx
14
PTC-5001 Reconhecimento de Padrões (aula2)
79
Caso 2: i=
• Matrizes de covariâncias idênticas, mas arbitrárias
• Amostras de mesma densidade de probabilidade pertencem a aglomerados hiperelipsóides de igual tamanho e forma, cada um deles centrado na sua média
• De
Resulta iit
ii Pg ln2
1 1 μxΣμxx
iiiit
ii Pd
g ln||ln2
12ln
22
1 1 ΣμxΣμxx
PTC-5001 Reconhecimento de Padrões (aula2)
80
• Expandindo
resulta
• Com
• Como esses discriminantes são lineares, as fronteiras de decisão são também hiperplanos
0itii wg xwx
ii μΣw 1
iitii Pw ln
2
1 10 μΣμ
it
i μxΣμx 1
PTC-5001 Reconhecimento de Padrões (aula2)
81
• Assim, se as regiões Ri e Rj são contíguas, a fronteira entre elas é
come
• Note que o hiperplano separando Ri e Rj não é em geral ortogonal a linha entre as médias.
• Probabilidades a priori iguais x0 no ponto médio entre as médias senão x0 se afasta da média mais provável
00 xxw t
ji μμΣw 1
ji
j
i
jit
ji
ji P
Pμμ
μμΣμμμμx
ln1
2
110
PTC-5001 Reconhecimento de Padrões (aula2)
82
PTC-5001 Reconhecimento de Padrões (aula2)
83
Classificador baseado na distância mínima
• Similarmente ao caso 1, se P(i) é a mesma para todas as c classes, então
“Para classificar um vetor característica x, meça a distância de Mahalanobis
de x a cada um dos c vetores média, e atribua x à classe da média mais próxima”
itiig μxΣμxx 1
2
1
it
i μxΣμx 1
PTC-5001 Reconhecimento de Padrões (aula2)
84
Caso 3: i arbitrário
• Tem-se
que pode ser escrita como (função quadrática)
onde
• Portanto, as superfícies de decisão são hiperquádricas: hiperplanos, hiperesferas, hiperelipsóides, hiperparabolóides, hiperhiperbolóides
0itii
ti wg xwxWxx
1
2
1 ii ΣW iii μΣw 1 iiiitii Pw ln||ln
2
1
2
1 10 ΣμΣμ
iiiit
ii Pd
g ln||ln2
12ln
22
1 1 ΣμxΣμxx
15
PTC-5001 Reconhecimento de Padrões (aula2)
85
• Essas superfícies não precisam ser simplesmente conectadas
PTC-5001 Reconhecimento de Padrões (aula2)
86
PTC-5001 Reconhecimento de Padrões (aula2)
87 PTC-5001 Reconhecimento de Padrões (aula2)
88
• As fronteiras de decisão podem ser complexas
PTC-5001 Reconhecimento de Padrões (aula2)
89
Exemplo: regiões de decisão para dados gaussianos de duas dimensões
PTC-5001 Reconhecimento de Padrões (aula2)
90
Note que
16
• O ponto médio entre a médias está em [3 2]t, mas o vértice da parábola está em [3 1,83]t !!!
PTC-5001 Reconhecimento de Padrões (aula2)
91 PTC-5001 Reconhecimento de Padrões (aula2)
92
Erros e regiões de decisão
Limites de erro
PTC-5001 Reconhecimento de Padrões (aula2)
93
Erros
• Considere um classificador Bayesiano ou outro
• Duas classes e duas regiões R1 e R2 não-ótimas
• Existem 2 modos que o erro de classificação pode ocorrer
a) x é atribuído a R2, mas a classe verdadeira é 1
b) x é atribuído a R1, mas a classe verdadeira é 2
2112 ,, RPRPerroP xx
PTC-5001 Reconhecimento de Padrões (aula2)
94
Erros
Desenvolvendo
2112 ,, RPRPerroP xx
221112 || PRPPRP xx
1
222
11 ||RR
dPpdPp xxxx
PTC-5001 Reconhecimento de Padrões (aula2)
95 PTC-5001 Reconhecimento de Padrões (aula2)
96
Erros (várias classes)
• Mais fácil calcular P(acerto)
• Bayes escolhe regiões de modo que o integrando seja máximo para todo x
xx
xx
dPp
PRPRPacertoP
i
c
i Rii
i
c
iii
c
iii
1
11
|
|,
17
PTC-5001 Reconhecimento de Padrões (aula2)
97
Limites de erro
• No caso gaussiano, os cálculos das probabilidades de erro podem ser muito complicados, especialmente para grandes dimensões, por causa da natureza descontínua das regiões de decisão
xx dPpacertoP i
c
i Ri
i
1
|
• Simplifica-se: não se utilizam os limites de integração dependendes das fronteiras de decisão
• Assim, no caso de duas classes a integral
pode ser aproximada de modo a fornecer o limite superior de erro
• Essas aproximações resultam noLimite de Chernoff
Limite de Bhattacharyya
PTC-5001 Reconhecimento de Padrões (aula2)
98
xxxxx dperroPderroperroP
|,
• A partir de
utilizando a desigualdade
min[a,b] <= a b1-
para a,b >= 0 e 0 <= <=1
chega-se a
PTC-5001 Reconhecimento de Padrões (aula2)
99
xxx dppPPerroP 21
121
1 ||
xxxxx dperroPderroperroP
|,
Para densidades normais
PTC-5001 Reconhecimento de Padrões (aula2)
100
onde
PTC-5001 Reconhecimento de Padrões (aula2)
101
)(2
11
kePP
PTC-5001 Reconhecimento de Padrões (aula2)
108
Teoria da decisão Bayesiana
características discretas
18
PTC-5001 Reconhecimento de Padrões (aula2)
103
Teoria da decisão de Bayes - características discretas
• Componentes discretas de x com m valores (v1...vm)• p(x|j) impulsiva
• onde
• Fórmula de Bayes
k
jkj PP || vxxx
x
xx
P
PPP jj
j
|| j
c
jj PPPcom
1
|xx
x
xxx jj Pdp ||
PTC-5001 Reconhecimento de Padrões (aula2)
104
• Risco condicional R(i|x)
Da mesma forma que para variáveis contínuas:
Para minimizar o risco total, escolha a ação i para o qual R(i|x) é mínimo, ou seja
* = arg i min[R(i|x)]
PTC-5001 Reconhecimento de Padrões (aula2)
105
Características binárias independentes• Duas classes e x = (x1,....,xd)t com xi = 0 ou 1
pi = Pr[xi = 1| 1] e qi = Pr[xi = 1| 2]
• Assumindo xi independentes, escreve-se P(x|j) como
• A razão de verossimilhança é
ii xi
d
i
xi ppP
1
11 1|x ii x
i
d
i
xi qqP
1
12 1|x
ii x
i
i
xd
i i
i
q
p
q
p
P
P
1
12
1
1
1
|
|
x
x
PTC-5001 Reconhecimento de Padrões (aula2)
106
• A partir de
função discriminante linear em xi
onde
i=1,...,d
2
1
1
ln1
1ln1ln
P
P
q
px
q
pxg
d
i i
ii
i
ii
x
d
iii wxwgou
10x
ii
iii pq
qpw
1
1ln
2
1
10 ln
1
1ln
P
P
q
pw
d
i i
i
2
1
2
1 ln|
|ln
P
P
p
pg
x
xx
0wg t xwx
PTC-5001 Reconhecimento de Padrões (aula2)
107
• Decide 1 se g(x)>0 e 2 se g(x)<=0
O valor de wi indica a importância de xi=1 (resposta “sim” para xi) na classificação
• Se pi > qi , então no caso de xi=1, há uma contribuição de wi votos para 1
• Se pi < qi há uma contribuição de |wi| votos para 2
d
iii wxwg
10x
ii
iii pq
qpw
1
1ln
PTC-5001 Reconhecimento de Padrões (aula2)
108
• Os valores de x aparecem nos vértices de um hipercubo de dimensão d
• A superfície de decisão é um hiperplano que separa os vértices de 1 dos vértices de 2
19
PTC-5001 Reconhecimento de Padrões (aula2)
109
Exemplo: Dados binários de 3 dimensões
• 2 classes
• 3 características binárias independentes
• probabilidades conhecidas P(1)= P(2)=0.5
pi=0.8 e qi=0.5 para i=1,2,3
Resulta
3863.1
8.015.0
5.018.0ln
1
1ln
ii
iii qq
ppw
75.2
5.0
5.0ln
5.01
8.01lnln
1
1ln
3
12
1
10
i
d
i i
i
P
P
q
pw
PTC-5001 Reconhecimento de Padrões (aula2)
110
A figura deve ser corrigida para w0 = -2.75
PTC-5001 Reconhecimento de Padrões (aula2)
111
• O plano g(x) = 0 é mostrado na figura
• Note que a fronteira coloca pontos com duas ou mais respostas “sim” (xi=1) na classe 1, porque essa classe tem maior probabilidade de ter qualquer característica com valor 1
• Suponha que p1= p2= 0.8 , p3= 0.5 e q1= q2= q3= 0.5
Resulta que x3 não fornece nenhuma informação sobre as classes (a fronteira de decisão é paralela a x3)
• Note que há uma faixa de posições da fronteira que deixa as classes imutáveis
Recommended