Análisis de Datos - CINVESTAVwgomez/diapositi... · Regularización-5 -4 -3 -2 -1 0 1 2 3 4 5 0...

Análisis de Datos

Clasificadores linealesRegresión logística

Dr. Wilfrido Gómez Flores

Introducción

Clasificación Bayesiana – Máxima probabilidad posterior:p(ωi|x) > p(ωj |x), para i 6= j.

Enfoque paramétrico – Asume un tipo de distribución para es-timar la función de verosimilitud p(x|ωj).

Regresión logística – Enfoque no paramétrico que modela direc-tamente la probabilidad posterior p(ωi|x).

1/21 Regresión logística Marzo2019

Introducción

Dada una variable binaria de salida y ∈ {0, 1}, se desea modelarla probabilidad condicional p(y = 1|x) como una función de x.

Problema: la regresión lineal es incompatible para modelarp(y = 1|x):• Las funciones lineales se encuentran en el rango [−∞,∞].• La probabilidad p(y = 1|x) está en el rango [0, 1].

Solución: convertir las predicciones lineales en probabilidades me-diante la función logística.


Función logística

Proceso de conversión de predicciones lineales en probabilidades:

1. Mapear la probabilidad de [0, 1] a [−∞,∞] con la función logit:

lnp(y = 1|x)p(y = 0|x)

= lnp(y = 1|x)

1− p(y = 1|x)= wT x (1)

donde x y w son vectores aumentados.

2. Resolver (1) para p(y = 1|x) para obtener la función logística:

p(y = 1|x) = 1

1 + exp(−wT x)(2)

con yi ≡ p(y = 1|x) como la salida estimada.


Función logística

0 0.2 0.4 0.6 0.8 1

-4

-2

0

2

4

(a)

-5 -4 -3 -2 -1 0 1 2 3 4 5

0

0.2

0.4

0.6

0.8

1

(b)

(a) Función logit en el rango [−∞,∞]. (b) Función logística (o sigmoidal) esuna función ‘suave’ en el rango [0, 1].


Descenso de gradienteFunción de log-verosimilitud negativa de w:

L(w) = −n∑i=1

[yi ln yi + (1− yi) ln(1− yi)] (3)

El gradiente está dado por:

∇L(w) =

n∑i=1

(yi − yi)xi

= X(y − y) (4)

Minimizar L(w) mediante descenso de gradiente:

w(1) arbitrario

w(k + 1) = w(k)− ηX(y(k)− y) k ≥ 1(5)


Descenso de gradiente

Input: w← 0, umbral θ, η, kmax

Output: w

1 k ← 0

2 do3 k ← k + 1

4 y←[

11+exp(−wT X)

]T5 w← w − ηX(y − y)

6 until (‖w(k − 1)− w(k)‖ < θ) ∧ (k < kmax)


Descenso de gradiente

7

6

5

4

3

2

10 1 2 3

0

04

0.2

5 6

0.4

7

0.6

0.8

1

(a)

7

6

5

4

3

2

10 1 2 3

0

04

0.2

5 6

0.4

7

0.6

0.8

1

(b)

Regresión logística para dos clases (ω1 en rojo y ω2 en negro) entrenada condescenso de gradiente: (a) linealmente separables y (b) no linealmente separables.


Algoritmo de Newton

Algoritmo de Newton: enfoque alternativo para minimizar L(w)

sin seleccionar una tasa de aprendizaje η:

w(1) arbitrario

w(k + 1) = w(k)−H−1∇L(w(k)) k ≥ 1(6)

donde H es la matriz Hessiana de tamaño (d+ 1)× (d+ 1):

H =

∂2L(w)∂w2

0

∂2L(w)∂w0∂w1

· · · ∂2L(w)∂w0∂wd

∂2L(w)∂w1∂w0

∂2L(w)∂w2

1· · · ∂2L(w)

∂w1∂wd

......

. . ....

∂2L(w)∂wd∂w0

∂2L(w)∂wd∂w1

· · · ∂2L(w)∂w2

d

8/21 Regresión logística Marzo

2019

Algoritmo de Newton

Generalmente, el algoritmo de Newton tendrá un mejor desempeño por paso queel algoritmo de descenso de gradiente simple, aún teniendo el valor óptimo de η.


Algoritmo de Newton

A partir de L(w), la matriz Hessiana se define como:

∇2L(w) =

n∑i=1

yi(1− yi)xixTi

= XRXT (7)

donde

R =

y1(1− y1) 0 · · · 0

0 y2(1− y2) · · · 0...

.... . .

...0 0 · · · yn(1− yn)

donde yi es la probabilidad estimada del i-ésimo patrón.


Algoritmo de Newton

Input: w← 0, umbral θ, kmax

Output: w

1 k ← 0

2 do3 k ← k + 1

4 y←[

11+exp(−wT X)

]T5 R← diag (y(1− y))

6 w← w −(XRXT

)−1X(y − y)

7 until (‖w(k − 1)− w(k)‖ < θ) ∧ (k < kmax)


Regularización

-5 -4 -3 -2 -1 0 1 2 3 4 5

0

0.2

0.4

0.6

0.8

1

La regularización puede mejorar la generalización de la regresión logística, evi-tando el sobre-ajuste del modelo. Cuando ‖w‖ → ∞, la función logística tiendea una función escalón; se deben penalizar pesos con valores grandes.


RegularizaciónRegularización L2 de la función de log-verosimilitud en (3) :

L(w) = −n∑i=1

[yi ln yi + (1− yi) ln(1− yi)] +λ

2‖w‖2 (8)

donde λ es una constante que controla la fuerza de la regularización.

Minimizar la función de costoL(w) tal que se aproxime lo másposible al mínimo global dada larestricción λ

2 ‖w‖2.

-60 -40 -20 0 20 40-40

-20

0

20

40

60

Estimado no regularizado

(mínimo global)

Estimado regularizado

(aproximado al mínimo)


Regularización

Regla de actualización con descenso de gradiente:

w(1) arbitrario

w(k + 1) = w(k)− ηX(y(k)− y) + λw(k) k ≥ 1(9)

Regla de actualización con algoritmo de Newton:

w(1) arbitrario

w(k + 1) = w(k)−(XR(k)XT + λI

)−1X(y(k)− y) k ≥ 1

(10)donde I es una matriz identidad de tamaño (d+ 1)× (d+ 1).


Regularización

7

0

6

0.2

0.4

0.6

5

0.8

1

4

3

2 76

51 43

20 10

(a)

7

0

6

0.2

0.4

0.6

5

0.8

1

4

3

2 76

51 43

20 10

(b)

Regresión logística para dos clases (ω1 en rojo y ω2 en negro) entrenada conalgoritmo de Newton: (a) sin regularizar, w = [−361, 70, 38]T y (b) con regula-rización (λ = 1/2), w = [−28, 6, 3]T .


Caso multiclaseEn el caso multiclase se generan c funciones logísticas:

yij ≡ p(y = j|xi) =exp(wT

j xi)∑cl=1 exp(w

Tl xi)

,i = 1, . . . , n

j = 1, . . . , c(11)

Función de log-verosimilitud multiclase:

L(w1, . . . , wc) = −n∑i=1

c∑j=1

yij ln yij (12)

yij =

1 si xi ∈ ωj0 otro caso


Caso multiclaseGradiente de la función de verosimilitud multiclase:

∇L(w1, . . . , wc) =

n∑i=1

(yij − yij)xi

∇L(W ) = X(Y − Y ) (13)

Regla de actualización con descenso de gradiente:

W (1) arbitrario

W (k + 1) = W (k)− ηX(Y (k)− Y ) + λW (k) k ≥ 1

(14)

Un patrón de prueba xt se clasifica ωi si:

wTi xt > wT

j xt, ∀i 6= j (15)


Caso multiclase

Input: W ← [0T1 , . . . ,0Tc ], umbral θ, η, λ, kmax

Output: W

1 k ← 02 do3 k ← k + 1

4 Y ←[

exp(W T X)∑cj=1 exp(wT

j X)

]T5 W ← W − ηX(Y − Y ) + λW

6 until (‖wj(k − 1)− wj(k)‖ < θ, ∀j = 1, . . . , c)∧ (k < kmax)


Caso multiclase

0

0.2

0.4

0.6

0.8

1

Fronteras de decisión y las funciones de probabilidad generadas por regresiónlogística para patrones con cinco clases y dos características.


Entrenamiento y clasificación

En el caso de clasificación binaria, el entrenamiento de un discrimi-nante logístico consiste en calcular el vector de pesos w:

1. Aumentar cada patrón de entrenamiento xi, i = 1, . . . , n, pa-ra obtener el conjunto aumentado X ∈ R(d+1)×n. La salidadeseada del i-ésimo patrón es yi ∈ {0, 1}.

2. Obtener el vector de pesos aumentado w mediante descenso degradiente o algoritmo de Newton.


Entrenamiento y clasificación

En la etapa de clasificación, un patrón de prueba xt se aumentapara obtener xt ∈ Rd+1, se evalúa en la función lineal w, y seaplica la regla de decisión:

Decidir

ω1 si wT xt > 0

ω2 otro caso

Si el patrón de prueba se evalúa en la función logística en (2),entonces se obtiene la probabilidad de pertenecer a la clase conetiqueta 1.


Análisis de Datos - CINVESTAVwgomez/diapositi... · Regularización-5 -4 -3 -2 -1 0 1 2 3 4 5 0...

Documents

Transcript of Análisis de Datos - CINVESTAVwgomez/diapositi... · Regularización-5 -4 -3 -2 -1 0 1 2 3 4 5 0...