Funciones Discriminantes
Lineales
Enrique Ferreira
Reconocimiento de Patrones
03 de octubre de 2015
Objetivos
 Introducir el concepto de funciones discriminantes
 caso lineal
 superficies discriminantes
 clasificacion
 Concepto de Separabilidad lineal
 Algoritmos de clasificacion
 Gradiente
 Perceptron y variantes
 Relajacion
 Casos no separables
 Minimos cuadrados
 Widrow-Hoff, LMS
03/10/2015
Reconocimiento de Patrones
2
Funciones Discriminantes
 Usar funciones lineales:
 g(x) = w.x + wo
 para clasificar conjunto de patrones
 g(x)=0 es un hiperplano en Rn
 w es vector normal (pesos) a hiperplano
 g(x) es proporcional a distancia (con signo) de x a
hiperplano
 caso 2 clases:
 Clase 1: g(x) > 0
 Clase 2: g(x) < 0
03/10/2015
Reconocimiento de Patrones
3
Funciones Discriminantes
 Caso C clases:
 Mas de una forma de hacerlo con funciones
discriminantes
 uso C funciones discriminantes
 gi(x) para ver si pertenece o no a clase i, i=1..C
 usar C(C-1)/2
 una funcion por par de clases
 usar C funciones de nuevo
 tomar clase j=arg max gi(x)
 bordes gi=gj son hiperplanos
 bordes de clases son convexos (limitante)
03/10/2015
Reconocimiento de Patrones
4
Funciones Discriminantes
 Generalizaciones
 usar funciones cuadraticas
 polinomiales
 expansion en series
 sigmoidales
 redes neuronales artificiales
 funciones bases
 radial basis functions
 Permiten generar regiones de decision mas
complejas
 Calculo de pesos mas complicado
03/10/2015
Reconocimiento de Patrones
5
Separabilidad Lineal
 Problema:
 dado conjunto de entrenamiento (patrones) {xi,ci}, calcular
pesos de funcion discriminante para C=2
 Decimos que dicho conjunto es linealmente
separable si existe w tal que separa todos los
patrones correctamente
 Separabilidad Lineal:
 patrones (xk,ck)
 condición (caso wo=0):
 wt.xk > 0, ck=0
 wt.xk < 0, ck=1
 wt.zk > 0, con zk = (1-2ck).xk
03/10/2015
Reconocimiento de Patrones
6
Encontrar Solucion a vector de pesos
 Encontrar w solucion a Problema
 si es linealmente separable
 puede haber varias soluciones posibles
 se ve geometricamente
 Gradiente descendente
 definiendo funcion J a minimizar en solucion
 Funcion posible (Perceptron)
 J = -Sum(wt.xk) para todos los patrones mal clasificados
 Newton
 Aproximando a error cuadratico
03/10/2015
Reconocimiento de Patrones
7
Variantes
 Gradiente descendente
 incremento fijo, de a un patron
 w’ = w + z
 incremento variable n(k)
 margen de correccion
 Teoremas
 Se puede probar que algoritmos convergen
 para el caso de incremento variable se debe verificar que
 sum n(k)  inf
 sum n2(k)/(sum n(k))^2 0
03/10/2015
Reconocimiento de Patrones
8
Perceptron
 Perceptron
 Separa espacio con hiperplano
 y = f ( w1 u1 + w2 u2 + ... + wn un ),
 f(s) = { 1 si s0, 0 si s<0 }
 Puede incluir offset w0.
u2
u1
wt.u=0
 Importante históricamente
 estudiado muy detalladamente (Minsky y Papert ‘69)
 Es un clasificador lineal en 2 clases.
 bueno si patrones linealmente separables
 XOR problem
 Análogo a clasificador de Bayes gaussiano.
 minimiza probabilidad de error
 clasificador denominado paramétrico
03/10/2015
Reconocimiento de Patrones
9
Aprendizaje: Perceptron
 Separabilidad Lineal:
 n

y ( x )  sgn   w i x i  w 0 
 i 1

 patrones (uk,vk)
 condición:
 sgn(wt.uk)=vk
 wt.zk > 0, con zk = vkuk
 Algoritmos:
new
 w i   1  v y ( u ) v u i
p
p
old
  wi
 w i   v  y ( u ) u i
p
p
p
 w     N   w z z
t
D (w ) 
1
t
min w z
w
p
p
p
M  M
p
w
t
1
t
2
2
2
w w*
 Convergencia
 Cota para M, número total de
pasos para llegar a solución w*.
Reconocimiento de Patrones
p
p
w w *   MD ( w *) w *
( w w *)
p
D max  max D ( w )
p
 distancia de solución a patrones
 medida de separabilidad
p
w
w  M z
 separarme de zona de transición
 D: medida de performance
 wi
 2 v p u p , si v p  y ( u p )
 wi  
0 , de otra forma

 muchas opciones basadas en error
en la salida
 : umbral de corrección
03/10/2015
wi
2
 N  (  2  )
 D ( w *)
2
 M
N (  2  )
1  2
M  N
D

2
max
10
p
Criterios de relajacion
 Se pueden usar otras funciones a optimizar
 funcion cuadratica
 J=sum(wt.xk)^2, para xk mal clasificados
 gradiente continuo
 se usa: (Batch relaxation with margin)
 normalizacion para evitar problemas de escala
 margen de clasificacion para no quedarme en mala solucion
 Se puede probar convergencia para el caso de update por
patron y con margen (single sample relaxation rule with
margin) mas facil, con 0 < n < 2
 explicacion geometrica de regla
 wk+1.x-b=(1-n)(wk.x-b)
03/10/2015
Reconocimiento de Patrones
11
Optimización Lineal: Least-Squares (LSE)
 Dado conjunto de pares entradasalida deseados y modelo lineal
paramétrico
 podemos asumir yi  R sin perder
generalidad
 obtenemos sistema lineal
 con mayor número de ecuaciones
que incógnitas
 minimizando el error cuadrático E
 Off-line: Pseudoinverse
 si podemos armar el sistema
lineal de antemano
 On-line: Obtención recursiva de la
pseudoinverse
 datos obtenidos en forma
secuencial durante cálculo
 Variantes:
 forgetting factor
 LSE vs Kalman Filter
 LSE vs MLE, unbiased,
consistent
03/10/2015
( u i , y i ),
i  1,..., m
y   1 f 1 ( u )   2 f 2 ( u )  ...   n f n ( u )
a i  [ f 1 ( u i ), f 2 ( u i ),..., f n ( u i )]
t
  [ 1 ,  2 ,...,  n ], y  [ y 1 ,..., y m ]
t
t
y  A
E
(y
 ai )  ( y  A  ) ( y  A  )
t
i
2
t
i
1
  (A A ) A y
t
t
 k  Pk A tk y k Pk  ( A tk A k )  1

t

Pk a k  1 a k  1 Pk
Pk  1  Pk 
,

t
1

a
P
a

k 1 k k 1
 k  1   k  Pk  1 a k  1 ( y k  1  a kt  1 k ),
Reconocimiento de Patrones
12
P0   I
0  0
Widrow-Hoff: Adaline
 Adaptive Linear Element
 Estructura:
y=0
 Como un Perceptron pero con
función lineal a la salida.
 Permite trabajar con problemas
más generales
 Widrow y Hoff propusieron un
método computacionalmente más
eficiente denominado LMS para
determinar parámetros del Adaline
(1962).
 similar a aplicar gradiente
descendente
 muy intuitivo
03/10/2015
Reconocimiento de Patrones
n
y 
wx
 w0
i
i
p
 yp
i 1
Ep 
1
2
t
2
 p w i   t p  y p  x i
13
Aprendizaje: Adaline
 Adaptive Linear Element”
 Aprendizaje
 La salida lineal permite aplicar método de
gradiente en aprendizaje
 Widrow y Hoff propusieron un método
computacionalmente más eficiente
denominado LMS (1962)
n
o
 error instantáneo
 aplica gradiente descendente a estimación
actual de gradiente
E p (w) 
 muy intuitivo
1
2
 p w i  
 Convergencia
 Depende de  y valores propios de
función E
 matrix de correlación de entradas
 malos valores de  pueden causar
lentitud u oscilación
 : medida de memoria de algoritmo
 variar  durante aprendizaje
03/10/2015
i
i
 w0
i 1
 aproximación estocástica
 disparidad de valores i.
wx
e (w) 
2
E p
w
1
2
t
 op 
2
p
  t p  o p  x i
n
E  E0 

i
( wi  wi 0 )
2
i 1
 w i  
 wi
Reconocimiento de Patrones
new
E
wi
  wi
old
  2 i  w i  w i 0 
  w i  (1  2 i ) w i
14
old
Referencias
 Duda and Hart. Capitulo 5.
 Simon Haykin, “Neural Networks”, Prentice Hall,
1999.
 Hertz, Krogh and Palmer, “Introduction to the theory
of Neural Computation”, Addison-Wesley, 1991.
03/10/2015
Reconocimiento de Patrones
15
Descargar

Discriminantes Lineales