Download Aux 7. Introducción a la Minería de Datos - U

Aux 7. Introducción a la Minerı́a de Datos
Gastón L’Huillier1,2 , Richard Weber2
glhuilli@dcc.uchile.cl
1 Departamento
de Ciencias de la Computación
Universidad de Chile
2 Departamento
de Ingenierı́a Industrial
Universidad de Chile
2010
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Auxiliar 7
Redes Neuronales (pt.2)
Back-propagation
Estimando los parámetros de la red
Uso en Rapidminer v5.0
Evaluación de Modelos
Holdout
Cross Validation
Evaluación de modelos de clasificación
Verificación de hipótesis
Use en Rapidminer v5.0
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Red Neuronal - Perceptrón Multicapa [1]
Artificial Neural Net MultiLayer Perceptron
La arquitectura de la red neuronal se caracteriza porque tiene sus
neuronas agrupadas en capas de diferentes niveles.
Cada una de las capas esta formada por un conjunto de neuronas y
se distinguen entre ellas en 3 niveles de capas distintas:
la capa de entrada: se encargan de recibir las señales o
patrones que proceden del exterior y propagar las señales a todas
las otras neuronas de la siguiente capa
las capas ocultas: son las que tienen la misión de realizar el
procesamiento no lineal de los patrones recibidos.
la capa de salida: actúa como salida de la red, proporcionando al
exterior la respuesta de la red, para cada uno de los patrones de
entrada.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Red Neuronal - Perceptrón Multicapa [2]
Figura: Ejemplo Red Neuronal.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Red Neuronal - Perceptrón Multicapa [2]
Figura: Diagrama Red Neuronal.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Red Neuronal - Perceptrón Multicapa [3]
mı́n
W1 ,W2
N
1 X
E=
N
i=1

y∗ (xi )k = f2 
M
X
j,k
w 2 · f1
j=1
K
2
1X
yi,k − y∗ (xi )k
2
!
k=1
A
X

!
a,j
w1 xi,a + wa,0
1

+ w0,k
2
a=1
j,k
a,j
A,M
Principal problema: Estimar W2 = {w2 }M,K
j=1,k=0 y W1 = {w1 }a=1,j=0
minimizando el error de aprendizaje.
Utilizando funciones de transferencia f2 : M → K y f1 : A → M, donde
N es la cantidad de objetos en la base de datos de
entrenamiento
M es la cantidad de neuronas en la capa escondida.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Red Neuronal - Perceptrón Multicapa [4]
mı́n
W1 ,W2
N
1 X
E=
N
i=1

y∗ (xi )k = f2 
M
X
j,k
w 2 · f1
j=1
K
2
1X
yi,k − y∗ (xi )k
2
!
k=1
A
X
!
a,j
w1 xi,a + wa,0
1


+ w0,k
2
a=1
K es la cantidad de clases en el problema de clasificación (en
regressión L = 1).
A es la cantidad de atributos para caracterizar a los objetos.
El método más conocido para estimar el óptimo de esta función
objetivo es el algoritmo Back-propagation. (La convergencia al mı́nimo
global no está asegurada)
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Red Neuronal - Perceptrón Multicapa [5]
Finalmente se puede ver que la red neuronal es una función
F : RA → RK continua no lineal. Es decir
Y = F(X, W)
Figura: Artificial Neural Network Multi-Layer Perceptron.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Algoritmo Back-propagation
Algoritmo que permite encontrar de manera heurı́stica la solución al
problema de minimización del error de la red neuronal.
Descrito originalmente el año 1974 [Werbos, 1994], pero no fue
reconocido hasta el año 1986 [PDP Research Group, 1986].
Compuesto de manera general por los siguientes pasos:
1
Se presentan las observaciones a la red y utilizando los pesos
actuales se calculan los valores de salida.
2
Se calculan los errores tomando las diferencias entre los resultados
obtenidos y los resultados esperados.
3
El error se retro-alimenta a través de la red y los pesos son ajustados
para minimizar el error.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Algoritmo Back-propagation
Una de las principales problemáticas del algoritmo backpropagation es
que se presenta la situación de encontrar como solución mı́nimos
locales.
Se puede evitar este problema modificando los valores de la tasa de
aprendizaje.
Figura: Problemas con los mı́nimos locales y la tasa de aprendizaje.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Algoritmo Back-propagation
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Algoritmo Back-propagation
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Algoritmo Back-propagation
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Algoritmo Back-propagation
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Algoritmo Back-propagation
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Algoritmo Back-propagation
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Algoritmo Back-propagation
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Algoritmo Back-propagation
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Algoritmo Back-propagation
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Ajuste de Parámetros [1]
Cantidad de Capas Ocultas
1
Cualquier función booleana puede ser representada por una red
neuronal con solo una capa intermedia. Lamentablemente puede
necesitar un numero exponencial (en numero de entradas) de nodos en
la capa media. [Fausett, 1994]
2
Cualquier función continua acotada puede ser aproximada con bajo
porcentaje de error, por una red neuronal con una sola capa
intermedia. [Cybenko, 1989, Hornik et al., 1990]
3
Cualquier función puede ser aproximada, con cierto nivel de
precisión, con una red neuronal con dos capas [Cybenko, 1989]
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Ajuste de Parámetros [2]
Cantidad de Neuronas [1]
1
La cantidad de neuronas de entrada y salida están definidas por el
problema.
2
La cantidad de neuronas en las capas ocultas determina los grados
de libertad del modelo:
Número muy pequeño de neuronas pueden que no sean
suficientes para problemas muy complejos.
Número muy grande de neuronas pueden sobre-entrenar el
modelo y tener una perdida de generalidad ante nuevas
observaciones.
3
Se suele usar (por defecto, y para comenzar el análisis de
(M cantidad de neuronas en la capa
sensibilidad) la regla M = (A+K)
2
media, A cantidad de neuronas en la capa de entrada, K cantidad de
neuronas en la capa de salida.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Ajuste de Parámetros [3]
Cantidad de Neuronas [2]
1
La cantidad de neuronas en las capas ocultas depende de una serie
de factores, entre ellos la cantidad de observaciones en el conjunto
de entrenamiento, la cantidad de “ruido”, complejidad del problema
de clasificación, cantidad de atributos (neuronas de entrada) y clases
(neuronas de salida), funciones de activación entre las capas,
algoritmo de entrenamiento.
2
Una opción es ir evaluando varias redes neuronales para ir
determinando el número apropiado de neuronas
3
Otra opción es comenzar con un número grande de neuronas y
conexiones, y a medida que se va construyendo la red neuronal, se van
podando aquellas conexiones que son innecesarias.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Ajuste de Parámetros [4]
Decaimiento de los pesos
1
Para prevenir que los pesos vayan creciendo sin control alguno a
valores muy grandes (señal de sobre entrenamiento), es conveniente
agregar un decaimiento a los pesos de la forma:
wt+1 = (1 − )wt
2
Pesos que no son necesarios y no se van actualizando en cada
iteración del algoritmo, van a decaer hasta anularse, mientras que
aquellos que si son necesarios y se van actualizando de manera
continua con backpropagation y ajustando con el decaimiento.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Ajuste de Parámetros [5]
Número de épocas
1
Para evitar el sobre entrenamiento y el tiempo computacional
necesario para entrenar la red, se puede fijar un cierto numero de
épocas de entrenamiento de acuerdo al comportamiento observado del
error de entrenamiento y de prueba.
Entrenamiento con ruido
1
Se puede dar el caso que sea necesario agregar ruido a las
observaciones de entrenamiento de manera de entregar una mayor
generalidad al modelo.
Función de activación
1
Una red neuronal MLP entrenada con el algoritmo backpropagation
entrena generalmente más rápido si se utiliza una función de
activación anti-simétrica ( f (−x) = −f (x) )
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Ajuste de Parámetros [6]
Sobre-entrenamiento en redes neuronales
Figura: [Mitchell, 1997] .
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Ajuste de Parámetros [6]
Sobre-entrenamiento en redes neuronales
Figura: [Mitchell, 1997] .
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Ajuste de Parámetros [7]
Preprocesamiento de datos de entrada
1
Los datos de entrada deben estar pre-procesados de manera que su
media sea cero, o un valor muy bajo con respecto a la varianza.
2
Los datos de entrada no deben estar correlacionados. Intentar de
utilizar variables que no expliquen las mismas caracterı́sticas de las
observaciones de una base de datos. Una alternativa es utilizar PCA u
otros métodos que aseguren variables independientes.
3
Las variables de entrada deben tener una varianza similar
Pesos iniciales
1
Pesos inı́ciales deben ser valores pequeños para evitar la
“saturación” de las neuronas: Valores de los pesos de
“entrada-capa-media” son mayores que aquellos pesos
“capa-media-salida” dado que actualizan sus valores con los errores de
back-propagation
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Ajuste de Parámetros [8]
Actualización de los pesos
1
Existen dos aproximaciones básicas para actualizar los pesos durante
el entrenamiento de la red:
Entrenamiento “On-line”: Pesos son actualizados con
backpropagation luego que cada observación es presentada a
la red neuronal.
Entrenamiento “Batch”: Pesos son actualizados una vez que
todas las observaciones son presentadas a la red neuronal.
2
Se recomienda el entrenamiento “Batch” dado que se utiliza la
dirección de máximo descenso, la más adecuada para el problema
de optimización no lineal que se desea resolver.
3
Entrenamiento “On-line” solo entrega una menor complejidad
computacional del entrenamiento en un orden.
4
Entrenamiento “On-line” es sensible al orden que se presentan las
observaciones a la red neuronal.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Ajuste de Parámetros [9]
Tasa de aprendizaje
1
Se recomienda utilizar una combinación de tasas de aprendizaje (η)
sobre distintas redes. Este parámetro, a grandes rasgos, permite
definir la velocidad por sobre la cual se va acercando al óptimo del
problema de optimización definido sobre una red neuronal artificial.
Momentum
1
Se puede incluir un parámetro llamado “momentum” (valor α) utilizado
para la actualización de los pesos en el algoritmo de backpropagation.
Permite considerar la “cantidad de movimiento” que cada peso
tiene al irse actualizando,
wt+1 = (1 − )wt + (1 − α)η
2
∂f (e)
x + α(wt − wt−1 )
∂e
No existe una regla general para los valores de ambos parámetros,
pero para el momentum se recomiendan valores cercanos a 0.2.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Auxiliar 7
Redes Neuronales (pt.2)
Back-propagation
Estimando los parámetros de la red
Uso en Rapidminer v5.0
Evaluación de Modelos
Holdout
Cross Validation
Evaluación de modelos de clasificación
Verificación de hipótesis
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Validación de Modelos
Conceptos básicos
Datos de Entrenamiento: Datos utilizados para entrenar el modelo
Datos de Prueba: Datos utilizados para probar el modelo
Datos Objetivo: Datos sobre los cuales se ejecuta posteriormente el
modelo
Error de predicción: Observaciones mal clasificadas sobre
observaciones totales.
Tasa de éxito = 1 – error de predicción
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Holdout [1]
1
Generalmente se tiene una base de datos, por lo que se debe dividir en
una base de datos de prueba y otra de entrenamiento. Ambos
conjuntos deben ser representativos con respecto a los datos objetivos.
Problemas:
1
Si una clase no está representada en los datos de entrenamiento, el
modelo no tendrá un buen desempeño para la clase y no se
medirá bien el error asociado.
2
Existe un trade-off entre la cantidad de datos considerados para el
conjunto de entrenamiento y de prueba.
1
2
Es necesario un conjunto de entrenamiento mayor para estimar
un buen modelo.
Es necesario un conjunto de prueba mayor para tener una buena
estimación del error.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Holdout [2]
1
Se puede considerar un “Holdout estratificado”, considerando la misma
frecuencia de clases en cada partición Entrenamiento / Prueba.
2
Se puede considerar una selección con reemplazo de la base de datos
original, probando una cierta cantidad de veces. El error estimado se
puede considerar como el promedio de errores para la iteración.
3
Se considera generalmente la regla 2/3 entrenamiento y 1/3 prueba
para la división de la base de datos.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Cross Validation [1]
Validación Cruzada de “n-folds”
1
Se subdividen los datos en n subconjuntos disjuntos.
2
Se considera la evaluación de n − 1 subconjuntos para el entrenamiento
del modelo y 1 subconjunto para la prueba. Este proceso se repite
hasta que los n subconjuntos fueron evaluados como prueba.
3
Una estimación del error, es el promedio de los errores considerados
para las n evaluaciones de la prueba.
4
El caso más usado es una validación cruzada de 10-fold
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Cross Validation [2]
Figura: Ejemplo Cross-Validation “10-folds”.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Cross Validation [3]
Validación Cruzada de “n-folds”
1
Caso usualmente recomendado: 10 veces validación cruzada con 10
folds.
2
La principal desventaja es el costo computacional de evaluar K veces n
modelos. Se tiene una complejidad de orden
O(K · n) ∗ O(modelo utilizado)
3
En el caso de tener pocos datos, es muy útil considerar “leave-one-out”
cross validation. Funciona igual a n-fold c.v., donde n es el numero de
observaciones presentes.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Evaluación Modelos de Clasificación [1]
Matriz de confusión
Clasificado y∗ = +1
Clasificado y∗ = −1
Real y = +1
TP
FN
Real y = −1
FP
TN
TP: Verdadero Positivo
TN: Verdadero Negativo
FP: Falso Positivo (error de tipo 1)
FN: Falso Negativo (error de tipo 2)
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Evaluación Modelos de Clasificación [2]
Matriz de confusión
Clasificado y∗ = +1
Clasificado y∗ = −1
Real y = +1
TP
FN
Real y = −1
FP
TN
N = TP + TN + FP + FN
TP + TN
Accuracy =
N
FP
FP-rate =
FP + TN
TP
TP-rate =
TP + FN
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Evaluación Modelos de Clasificación [2]
Matriz de confusión
Clasificado y∗ = +1
Clasificado y∗ = −1
Real y = +1
TP
FN
Real y = −1
FP
TN
Precision: Porcentaje de las observaciones correctamente clasificadas.
Precision =
TP
TP + FP
Recall: Porcentaje de todas las observaciones que deban ser clasificacdas,
sean clasificadas correctamente
Recall =
.
F-measure =
TP
TP + Fn
2 · Precision · Recall
Precision + Recall
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Verificación de hipótesis [1]
Supongamos que repetimos r veces la evaluación de K veces dos
modelos con los mismos conjuntos de entrenamiento y prueba. (i.e. r
veces K Holdouts con reemplazo, o r veces Cross-Validation de K-folds)
Figura: Se asume que a1 ∼ N(µ1 , σ1 ) y a2 ∼ N(µ2 , σ2 ).
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Verificación de hipótesis [2]
Sea xij = aij − bij , se considera el siguiente test de hipotesis
H0 : µD = donde µD = µ1 − µ2
Si se considera,
µ̂ =
r
K
1 XX
xij (media observada)
r·k
i=1 j=1
σ̂ =
r X
K
X
1
(xij − µ̂)2 (varianza observada)
r·K−1
i=1 j=1
µ̂
t= q
1
( r·K +
n2
)σ 2
n1
(Estadı́stico del test t-student)
n1 y n2 determinados por la cantidad de evaluaciones realizadas para modelo
1 y modelo 2 en el K-Cross Validation.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
Verificación de hipótesis [3]
Verificación de la hipotesis
H : µD 6= si |t| > tα,r·K−1
H : µD > si t > tα,r·K−1
H : µD < si t < tα,r·K−1
¿Cómo concluı́mos?
Por ejemplo si se tiene
H : µD > si tα,r·K−1
entonces tenemos que
µ1 > µ 2
Lo anterior indicarı́a que el modelo 1 puede ser considerado mejor que
el modelo 2, con cierto nivel de significancia.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
References I
Cybenko, G. (1989).
Approximation by superpositions of a sigmoidal function.
Mathematics of Control, Signals, and Systems, 2(4):303–314.
Fausett, L., editor (1994).
Fundamentals of neural networks: architectures, algorithms, and applications.
Prentice-Hall, Inc., Upper Saddle River, NJ, USA.
Hornik, K., Stinchcombe, M. B., and White, H. (1990).
Universal approximation of an unknown mapping and its derivatives using
multilayer feedforward networks.
Neural Networks, 3(5):551–560.
Mitchell, T. M. (1997).
Machine Learning.
McGraw-Hill, Inc., New York, NY, USA.
PDP Research Group, C. (1986).
Parallel distributed processing: explorations in the microstructure of cognition, vol.
1: foundations.
MIT Press, Cambridge, MA, USA.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos
References II
Werbos, P. J. (1994).
The roots of backpropagation: from ordered derivatives to neural networks and
political forecasting.
Wiley-Interscience, New York, NY, USA.
G. L’Huillier, R. Weber
IN643 - Redes Neuronales (pt2) y Evaluación de Modelos