Plano de Aula
• Introdução
Funções Lineares Discriminantes
•
Funções Discriminantes Lineares e Superfícies de Decisão
•
Funções Discriminantes Lineares Generalizadas
Alessandro L. Koerich
Reconhecimento de Padrões
Ciência da Computação
2008
Introdução
Introdução
• Assumimos agora que conhecemos as formas apropriadas das funções
discriminantes.
• São relativamente fáceis de calcular
• Usamos amostras para estimar os valores dos parâmetros do
classificador.
• Na ausência de informação sugerindo o contrário, classificadores
lineares são candidatos para tentativas iniciais de classificação.
• Problema: encontrar uma função discriminante linear
• Vamos examinar diversos procedimentos para determinar as funções
discriminantes.
• Elas podem não ser ótimas, mas são bastante simples de serem
utilizadas.
• Fornecem classificadores lineares.
• Solução: Minimizar uma função custo. Qual?
– Erro no treinamento: o erro médio (perda) incorrido na classificação do
conjunto de amostras de treinamento.
• Atenção! Lembre-se de que um baixo erro de treinamento não garante
um baixo erro de teste.
FDL e Superfícies de Decisão
FDL e Superfícies de Decisão
Duas Categorias
• Definição: É uma função que é uma combinação linear dos componentes de x
g(x) = w t x + w0
(1)
onde w é um vetor de pesos e w0 é o peso limiar (bias).
• Um classificador de duas classes com uma função discriminante da
forma (1) usa a seguinte regra:
– Decide
ω1 se g(x) > 0
e
ω2 se g(x) < 0
– Ou seja, decide ω1 se w t x > -w0 e ω2 caso contrário.
– Se g(x) = 0 x é atribuído a qualquer uma das classes.
FDL e Superfícies de Decisão
• A equação g(x) = 0 define a superfície de decisão que separa pontos
atribuídos a categoria ω1 de pontos atribuídos a categoria ω2
– Quando g(x) for linear, a superfície de decisão é um hiperplano
– Medida algébrica da distância de x ao hiperplano (resultado interessante!)
FDL e Superfícies de Decisão
FDL e Superfícies de Decisão
x = xp +
r.w
w
(pois w é colinear com x − x p e
visto que g(x) = 0 e wt .w = w
portanto r =
O Caso de Multi-Categorias
w
= 1)
w
2
• Definimos c funções discriminantes lineares
g i ( x) = wit x + wi 0
i = 1,..., c
e atribuímos x para ωi se gi(x) > gj(x) ∀ j ≠ i; no caso de empates,
a classificação é indefinida.
g(x)
w
em particular d( 0,H) =
w0
w
• Neste caso, o classificador é uma “máquina linear”
– Concluindo, um função discriminante linear divide o espaço de
características (feature space) por um superfície de decisão
hiperplano.
– A orientação da superfície é determinada pelo vetor normal w e a
localização da superfície é determinada pelo peso limiar (bias)
O Caso de Multi-Categorias
• Para duas regiões contiguas Ri e Rj; a fronteira que as separa é
uma porção do hiperplano Hij defina por:
gi(x) = gj(x)
⇔ (wi – wj)tx + (wi0 – wj0) = 0
• wi – wj é normal para Hij e
d ( x , H ij ) =
gi − g j
wi − w j
• Um máquina divide o espaço de características (feature space)
em c regiões de decisão, com gi(x) sendo a mais discriminante se
x estiver na região Ri
O Caso de Multi-Categorias
O Caso de Multi-Categorias
FDL Generalizadas
• É fácil mostrar que as regiões de decisão para uma máquina
linear são convexas, esta restrição limita a flexibilidade e precisão
do classificador.
• Fronteiras de decisão que separam classes podem nem sempre
ser lineares.
• A complexidade das fronteiras pode algumas vezes necessitar do
uso de superfícies altamente não lineares.
• Um método para generalizar o conceito de funções lineares de
decisão é considerar uma função de decisão generalizada como:
g(x) = w1f1(x) + w2f2(x) + … + wNfN(x) + wN+1
(1)
onde fi(x), 1 ≤ i ≤ N são funções escalares do padrão x, x ∈ Rn (Espaço
Euclideano)
FDL Generalizadas
FDL Generalizadas
• A função g(x) pode ser escrita como:
• Introduzindo fn+1(x) = 1 obtemos:
N +1
d
g ( x) = w0 +
∑
wi xi
i =1
Onde os coeficientes wi são os componentes do vetor de pesos w.
g ( x) =
∑ w f ( x) = w
i i
T
.x&
i =1
onde w = (w1,w2 ,...,wN ,wN +1 )T e x& = (f1(x),f 2(x),...,f N (x),f N +1(x))T
• Esta última representação de g(x) implica que qualquer função de
decisão definida pela equação (1) pode ser tratada como linear no
espaço N+1 dimensional (onde N+1>n).
• g(x) mantém suas características de não-linearidade em Rn
FDL Generalizadas
FDL Generalizadas
• A função de decisão generalizada utilizada com mais freqüência é g(x)
para qual fi(x) (1≤ i ≤ N) são polinomiais.
• Para padrões x ∈ Rn, a função de decisão quadrática mais geral é
dada por:
n −1
n
g ( x) = ( w& ) x
T
T: é o vetor transposto
g ( x) =
∑
i =1
& é um novo vetor de pesos que pode ser calculado a partir do
onde w
original w e da função linear original fi(x), 1 ≤ i ≤ N
• Funções de decisão quadráticas para um espaço de características 2dimensional.
g ( x) = w1 x12 + w2 x1 x2 + w3 x22 + w4 x1 + w5 x2 + w6
onde w = (w 1 , w2 ,..., w6 )T e x& = (x12 , x1 x2 , x22 , x1 , x2 ,1)T
wii xi2
+
n
n
∑ ∑ w x x + ∑w x + w
ij i
j
i =1 j =i +1
i i
n +1
(2)
i =1
• O número de termos no lado direito é:
l = N +1 = n +
n(n − 1)
(n + 1)(n + 2)
+ n +1 =
2
2
• Este é número total de pesos que são os parâmetros livres do
problema
– Se, por exemplo, n = 3, o vetor x& é 10-dimensional
– Se, por exemplo n = 10, o vetor x& é 65-dimensional
FDL Generalizadas
FDL Generalizadas
• No caso de funções de decisão polinomiais de ordem m, uma
típica fi(x) é dada por:
• A função de decisão quadrática comumente usada pode ser
representada como a superfície quadrática n- dimensional geral:
f i ( x) = xie1 xie2 ...xiem
1
2
m
onde 1 ≤ i1 , i2 ,..., im ≤ n e e i ,1 ≤ i ≤ m é 0 ou 1.
– É polinomial com grau entre 0 e m. Para evitar repetições, fazemos
i1 ≤ i2 ≤ …≤ im
n
g ( x) =
m
n
n
∑ ∑ ... ∑ w
i1 =1 i2 = i1
im =im−1
i1i2 ...im xi1 xi2 ...xim
+ g m −1 ( x)
(onde g0(x) = wn+1) é a função de decisão polinomial de ordem m
mais geral.
g(x) = xTAx + xTb +c
onde a matriz A = (aij), o vetor b = (b1, b2, …, bn)T e c, depende
dos pesos wii, wij, wi da equação (2)
• Se A é definida e positiva então a função de decisão é uma hiperelipsóide com eixos nas direções dos auto-vetores de A
– Em particular: se A = In (Identidade), a função de decisão é
simplesmente a hiper-esfera n-dimensional.
FDL Generalizadas
FDL Generalizadas
• Exemplo 1: Seja n = 3 e m = 2 então:
• Se A é definido e negativo, a função de decisão descreve uma
hiper-hiperbolóide
3
g 2 ( x) =
3
∑ ∑w
+ w1 x1 + w2 x2 + w3 x3 + w4
i1i2 xi1 xi2
i1 =1 i2 =i1
= w 11 x12 + w12 x1 x2 + w13 x1 x3 + w22 x22 + w23 x2 x3 + w33 x32 + w1 x1 + w2 x2 + w3 x3 + w4
• Exemplo 2: Seja n = 2 e m = 3 então:
2
g 3(x) =
2
2
∑ ∑ ∑w
i1 =1 i2 =i1 i3 =i2
i1i2i3 xi1 xi2 xi3
• Em resumo: é somente a matriz A que determina a forma e
características da função de decisão.
+ g 2(x) = w111 x13 + w112 x12 x2 + w122 x1 x22 +
+ w222 x23 + g 2(x)
2
onde g 2(x) =
2
∑ ∑w
i1 =1 i2 =i1
i1i2 xi1 xi2
+ g 1(x) = w11 x12 + w12 x1 x2 + w22 x22 + w1 x1 +
+ w2 x2 + w3
Problema
Considere um espaço 3-dimensional e funções de decisão polinomiais cúbicas
1.
Quantos termos são necessários para representar uma função de decisão se
somente forem assumidas funções cúbicas e lineares.
2.
Apresente a função de decisão geral polinomial de 4th ordem para um espaço de
características 2-dimensional
3.
• Matrizes positivas definidas
– Uma matriz quadrada A é positiva definida se xTAx>0 para todos
vetores coluna x não nulos.
– É negativa definida se xTAx < 0 para todos x não nulos.
R3
o espaço de características original e a função de decisão associada com
Seja
as classes ω1 e ω2 sendo:
g ( x) =
2 x12
+
x32
+ x2 x3 + 4 x1 − 2 x2 + 1
– É positivo semi-definido se xTAx ≥ 0.
para qual g(x) > 0 se x ∈ ω1 e g(x) < 0 se x ∈ ω2
– É negativa semi-definida se xTAx ≤ 0 para todo x.
a) Re-escreva g(x) como g(x) = xTAx + xTb + c
b) Determine a classe de cada um dos seguintes vetores:
(1,1,1), (1,10,0), (0,1/2,0)
– Estas definições são difíceis de serem verificadas diretamente e
podem ser esquecidas para todos os propósitos práticos.
• Mais útil na prática são as seguintes propriedades, que se
mantém quando a matriz A é simétrica e que são mais fáceis de
verificar.
• O i-ésimo menor principal de A é a matriz Ai formada pelas
primeiras i linhas e colunas de A. Então, o primeiro principal
menor de A é a matriz Ai = (a11), o segundo menor principal é a
matriz:
⎛ a11 a 12 ⎞
⎟⎟, e assim por diante.
A2 = ⎜⎜
⎝ a 21 a 22 ⎠
• Para fixas as idéias, considere uma matriz simétrica 2x2:
– É positivo definido se:
– det(A1) = a11 > 0
– det(A2) = a11a22 – a12a12 > 0
– É negativo definido se:
– det(A1) = a11 < 0
– det(A2) = a11a22 – a12a12 > 0
– É positivo semi-definido se:
– det(A1) = a11 ≥ 0
– det(A2) = a11a22 – a12a12 ≥ 0
– E é negativo semi-definido se:
– det(A1) = a11 ≤ 0
– det(A2) = a11a22 – a12a12 ≥ 0.
⎛a a ⎞
A = ⎜⎜ 11 12 ⎟⎟
⎝ a 21 a 22 ⎠
• A matriz A é positiva definida se dos seu menores principais A1,
A2, …, An tem determinantes estritamente positivos.
• Se estes determinantes são não-nulos e alternam sinais, iniciando
com det(A1) < 0, então a matriz A é negativa definida.
• Se os determinantes são todos não-negativos, então a matriz é
positiva semi-definida.
• Se o determinante alterna sinais, começando com det(A1) ≤ 0,
então a matriz é negativa semi-definida.
• Exercício 1: Verifique se as seguintes matrizes são positivas
definidas, negativas definidas, positiva semi-definida, negativa
semi-definida ou nenhuma delas.
⎛ 2 1⎞
(a ) A = ⎜⎜ ⎟⎟
⎝1 4 ⎠
⎛ − 2 4⎞
⎟⎟
(b) A = ⎜⎜
−
4
8
⎝
⎠
⎛ − 2 2⎞
⎟⎟
(c) A = ⎜⎜
⎝ 2 − 4⎠
⎛ 2 4⎞
⎟⎟
(d ) A = ⎜⎜
⎝4 3⎠
• Soluções do exercício 1:
• Exercício 2: Seja
• A1 = 2 >0
A2 = 8 – 1 = 7 >0
⇒ A é positivo definido
• A1 = -2
A2 = (-2 x –8) –16 = 0
⇒ A é negativo semi-positivo
• A1 = - 2
A2 = 8 – 4 = 4 >0
⇒ A é negativo definido
⎛ 2 1⎞
A = ⎜⎜ ⎟⎟
⎝1 4 ⎠
• Compute a fronteira de decisão atribuída a matriz A (g(x) = xTAx +
xTb + c) no caso onde bT = (1 , 2) e c = -3
• Resolva det(A-λI) = 0 e encontre a forma e as características da
fronteira de decisão separando duas classes ω1 e ω2
• Classifique os seguintes pontos:
• A1 = 2 >0
A2 = 6 – 16 = -10 <0
⇒ A não é nenhuma das acima
Solução do exercício 2:
1.
1⎞⎛ x1 ⎞
⎛1 ⎞
⎟⎟⎜⎜ ⎟⎟ + (x1,x2 )⎜⎜ ⎟⎟ − 3
4 ⎠⎝ x2 ⎠
⎝ 2⎠
⎛x ⎞
= ( 2 x1 + x2 ,x1 + 4 x2 )⎜⎜ 1 ⎟⎟ + x1 + 2 x2 − 3 = 2 x12 + x1 x2 + x1 x2 + 4 x22 + x1 + 2 x2 − 3
⎝ x2 ⎠
⎛2
g(x) = (x1,x2 )⎜⎜
⎝1
= 2 x12 + 4 x22 + 2 x1 x2 + x1 + 2 x2 − 3
⎛ 2 - λ 1 ⎞⎛ x1 ⎞
⎟⎟⎜⎜ ⎟⎟ = 0, obtemos :
Para λ2 = 3 + 2 usando ⎜⎜
⎝ 1 4 - λ ⎠⎝ x2 ⎠
⎧⎪( 2 − 1) x1 + x2 = 0
⇔ ( 2 − 1) x1 + x2 = 0
⎨
⎪⎩ x1 + (1 + 2 ) x2 = 0
Esta última equação é uma linha reta colinear ao vetor:
r
V2 = (1 ,1 − 2 )T
⎛ 2 - λ 1 ⎞⎛ x1 ⎞
⎟⎟⎜⎜ ⎟⎟ = 0, obtemos :
2. Para λ1 = 3 + 2 usando ⎜⎜
⎝ 1 4 - λ ⎠⎝ x2 ⎠
A fronteira de decisão elipse tem dois eixos, que são respectivamente
colineares aos vetores V1 e V2
⎧⎪(-1 - 2 ) x1 + x2 = 0
⇔ (−1 − 2 ) x1 + x2 = 0
⎨
⎪⎩ x1 + (1 − 2 ) x2 = 0
Esta última equação é uma linha reta colinear ao vetor:
• xT = (0, -1)
• xT = (1, 1)
3. X = (0, -1)T ⇒ g(0, -1) = -1 < 0 ⇒ x ∈ ω2
r
V1 = (1 ,1 + 2 )T
X = (1, 1)T ⇒ g(1, 1) = 8 > 0 ⇒ x ∈ ω1