Post on 13-Aug-2020
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.
2/21 Regresión logística Marzo2019
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.
3/21 Regresión logística Marzo2019
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].
4/21 Regresión logística Marzo2019
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)
5/21 Regresión logística Marzo2019
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)
6/21 Regresión logística Marzo2019
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.
7/21 Regresión logística Marzo2019
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 η.
9/21 Regresión logística Marzo2019
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.
10/21 Regresión logística Marzo2019
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)
11/21 Regresión logística Marzo2019
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.
12/21 Regresión logística Marzo2019
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)
13/21 Regresión logística Marzo2019
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).
14/21 Regresión logística Marzo2019
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 .
15/21 Regresión logística Marzo2019
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
16/21 Regresión logística Marzo2019
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)
17/21 Regresión logística Marzo2019
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)
18/21 Regresión logística Marzo2019
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.
19/21 Regresión logística Marzo2019
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.
20/21 Regresión logística Marzo2019
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.
21/21 Regresión logística Marzo2019