Clasificadores lineales

Clasificadores lineales y no lineales Introducción a Redes Neuronales

1

Clasificadores Lineales
• Suponga que la función discriminante es de la siguiente forma:

g i  x   w x  i 0
• Un clasificador que usa funciones discriminantes lineales se conoce como linear machine
2

t i

Clasificadores Lineales
• En el caso de dos clases se tiene que:

g1  x   w x  10 g 2  x  w x  20
• El criterio de decisión es:
si g1 (x)  g 2 (x)  Decision es C1 si g1 (x)  g 2 (x)  Decision es C 2
3

t 1

t 2

Clasificadores Lineales
• la superficie de decisión de una linear machine son conjuntos de hiperplano definido por la ecuación lineal g1(x)=g2(x) • Para dos clases, el criterio de decision se puede representar como:

g  x   g1  x   g 2  x 

4Clasificadores Lineales
• la superficie de decisión de una linear machine son conjuntos de hiperplano definido por la ecuación lineal g1(x)=g2(x) • Para dos clases, el criterio de decision se puede representar como:

g  x   g1  x   g 2  x 

si g (x)  0  Decision es C1 si g (x)  0  Decision es C2
5

Clasificadores Lineales
• Considerando el caso de 2 clases y una funcióndiscriminante lineal

Donde:

l = dimensión del vector de características
6

Clasificadores Lineales
20 Clase 1 Clase 2 W*X+w0 15

10

X2

5

0

-5

-10 -5

0

5

10 X1

15

20

25

7

Clasificadores Lineales
• W se conoce como vector de pesos (weight vector) y w0 como threshold o bias. • Si x1 y x2 son dos puntos del hiperplano, entonces:

8

ClasificadoresLineales

9

Clasificadores Lineales
• Algoritmo Perceptron
•Estimación de •Se asume que w1 y w2 son linealmente separables •Existe un hiperplano defino por de modo que se cumpla que

10

Clasificadores Lineales
• Algoritmo Perceptron
Si se tiene un hiperplano que no cruza por el origen: Se agrega una dimensión adicional para el bias

11

Clasificadores Lineales
• AlgoritmoPerceptron

12

Clasificadores Lineales
• Algoritmo Perceptron
Estimación de w
Se define una función de costo:

Y : vectores de entrenamiento mal clasificados x: vale -1 si x  w1 vale 1 si x  w2 Si x es mal clasificado, por ejemplo: xw1 pero wTx < 0 x=-1 positivo

 J(w) es siempre positiva
13

Clasificadores Lineales
• Algoritmo Perceptron
Estimación de W
Solución  J(w)=0Para estimar w se utiliza el método del gradiente:

Donde w(t) es el vector de peso estimado en la iteración i t: : es un real positivo

14

Clasificadores Lineales
• Algoritmo Perceptron
Estimación de W

donde finalmente se tiene

15

Clasificadores Lineales
• Algoritmo Perceptron
Estimación de w •Para que la solución converja en un N° finito de iteraciones se debe cumplir (ointentar) que:

Por ejemplo se puede escoger
16

Clasificadores Lineales
• Algoritmo Perceptron
•La solución no es única, existe mas de un hiperplano que separa las clases •La convergencia depende de t •Las clases deben ser linealmente separables

17

Clasificadores Lineales
• Variantes del Algoritmo Perceptron
reward and punishment
Para w(t) estimado en la iteración i y x(t) elvector de características en la iteración i, se tiene que:

18

Clasificadores Lineales
• Variantes del Algoritmo Perceptron
Pocket Algorithm
Converge a una solución inclusive si las clases no son separables linealmente •Inicializar el vector w(0) aleatoriamente. Definir un vector ws y un contador hs •En la iteración i estima w(t+1) según el algoritmo perceptron. •Estimar el numero de hvectores de entrenamiento correctamente clasificados •Si h>hs, reemplazar ws s con w(t+1) y hs con h Continuar la iteración •En caso contrario cambiar el peso

19

Clasificadores Lineales
• Ejemplo Algoritmo Perceptron
Para una iteración i se tiene que el vector w es:

El limite de decisión es: Los vectores de entrenamiento mal clasificados son:

Estimar w(t+1)
20

Clasificadores...