Redes neuronales artificiales para aprendizaje autom´atico y miner´ıa de datos Tratamiento Inteligente de la Informaci´ on y Aplicaciones

Juan A. Bot´ıa Departamento de Ingenier´ıa de la Informaci´ on y las Comunicaciones Universidad de Murcia

October 4, 2007

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de4,datos 2007

1 / 74

Gui´on de la clase 1

Introducci´on

2

Perceptr´on Algoritmos de ajuste de pesos

3

Redes Multi-capa Momentum RPROP Cascada-correlaci´on

4

Radial Basis Function Networks

5

Self Organizing Maps

6

Otras cuestiones concretas Datos discretos en redes neuronales Series temporales

7

Bibliograf´ıa

8

Ap´endice A

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de4,datos 2007

2 / 74

RNAs : Justificaci´on Modelo aproximador de funciones reales, discretas y vectoriales en la salida. Aplicaciones I I I

Reconocimiento de caracteres, de rostros, para pilotaje de veh´ıculos, etc.

Id´oneas cuando... I I

I I

I

Ejemplos del conjunto de aprendizaje formados por pares atributo-valor La salida de la funci´ on que define los datos de entrada tiene como salida un valor real, un valor discreto o un vector de valores reales y/o discretos Datos de entrenamiento contienen ruido (errores) No es necesario interpretar, para comprender, la funci´on objetivo aprendida por la RNA No es relevante el tiempo consumido en la fase de aprendizaje

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de4,datos 2007

3 / 74

Ideas iniciales La regla de decisi´on ´optima para minimizar la probabilidad de clasificar una nueva observaci´ on como ejemplar consiste en asignar a ese ejemplar nuevo la clase con mayor probabilidad a posteriori. El uso de redes neuronales para obtener clasificadores o modelos de regresi´ on implica emplear una estrategia diferente ⇒ usar la idea de funciones discriminantes una funci´on discriminante se especifica en una determinada forma param´etrica el valor de los par´ametros se determina (i.e. ajusta) mediante un algoritmo de aprendizaje sobre los datos de entrada. Representaci´on b´asica: combinaci´ on lineal de variables de entrada

October 2007 Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ ıa de4,datos

4 / 74

Discriminante m´as simple

Una funci´on discriminante, la denotaremos con y (x) es tal que el vector x se asigna a la clase C1 si y (x) > 0 y a la clase C2 si y (x) < 0. La m´as simple es lineal y (x) = w T x + ω0 , siendo w un vector d-dimensional y ω0 el bias

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de4,datos 2007

5 / 74

Interpretaci´on geom´etrica (ver [?])

Si consideramos y (x) = 0 como el l´ımite de decisi´ on entre las dos clases, corresponde a un hiperlano d − 1 dimensional, en un espacio x d-dimensional Con dos variables de entrada x1 y x2 , el l´ımite de decisi´ on es una l´ınea recta. Sean x A y x B del hiperplano citado, tenemos y (x A ) = y (x B ) = 0 y por la definici´ on de y (x) w T (x B − x A ) = 0, la orientaci´ on de w condiciona totalmente la orientaci´ on del discriminante.

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de4,datos 2007

6 / 74

Interpretaci´on geom´etrica (y II)

Sea x un punto cualquier del hiperplano la distancia normal del origen al T hiperplano viene dada por l = w||w ||x , como w T x = −ω0 , tenemos que ω0 l = − ||w || ω0 determina la posici´ on con respecto al eje del discriminante, en el espacio de las variables de entrada.

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de4,datos 2007

7 / 74

M´as de dos clases Si hay c clases, usamos un discriminante yk (x) para cada clase Ck de la forma T

yk (x) = wk + ωk k0, el punto x se asignar´ a a la clase Ck si se tiene que yk (x) > yj (x)∀j 6= k a La l´ınea de separaci´ on entre dos clases Ck y Cj vendr´ dada por el hiperplano yk (x) = yj (x) El hiperplano tendr´ a la forma T

(wk − wj ) x + (ωk0 − ωj0 ) = 0. La orientaci´ on del discriminante vendr´ a dada por (wk − wj ) La distancia al origen por el bias l =−

(ωk0 − ωj0 ) . ||wk − wj||

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de4,datos 2007

8 / 74

C´alculo de wi . Formulaci´ on del problema de los m´ınimos cuadrados

Se basa en la optimizaci´ on de una funci´ on de error de sumas cuadr´ aticas (adecuada para regresi´ on) transformamos el vector de entrada mediante M funciones φj (x), denominadas funciones base, y M P representamos la salida mediante una combinaci´ on lineal de esas funciones: yk (x) = wkj φj (x) + wk0 j=1

Podemos introducir una funci´ on φ0 = 1 adicional para que el discriminante quede: M P yk (x) = wkj φj (x) j=0

El error de sumas cuadr´ aticas se define mediante la funci´ on:

E (x) =

N c 1 XX n n 2 (yk (x ; w ) − tk ) , 2 n=1 k=1

yk (x n ; w ) la salida para el nodo k como funci´ on del vector de entrada y el vector de pesos w N es el n´ umero de patrones de entrenamiento c el n´ umero de nodos de salida tkn es el valor objetivo para el nodo k y el vector de entrada x n

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de4,datos 2007

9 / 74

Funci´on de error

Esta funci´on de error compone una superficie de variaciones suaves a la salida Es funci´on de wij y se puede minimizar con una gran cantidad de t´ecnicas, e.g. m´ınimos cuadrados y gradiente descendente E (w ) es una funci´on cuadr´atica con respecto w y por lo tanto las derivadas son funciones lineales en w As´ı, el valor de los pesos en el m´ınimo de la funci´on de error puede calcularse

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

10 / 74

Interpretaci´on geom´etrica Vamos a considerar una red de una u ´nica salida, i.e. c = 1 para una observaci´ on de entrada x n , la salida de la red ser´a de la forma M P yn = wj φj (x n ) j=0

Agrupamos todos los valores objetivo de los datos de entrada para formar un vector N dimensional, ~t Para cada una de las funciones base φj (x), agrupamos tambi´en sus ~ j tambi´en de dimensi´ correspondientes valores en φ on N Sea el n´ umero de funciones base, M tal que M + 1 < N. ~ j componen una base S, M + 1 dimensional que Los M + 1 vectores φ engendra un supespacio vectorial S. Si agrupamos las salidas de la red y n en un vector ~y , este vector estar´a M P ~j tambi´en en S ya que ~y = wj φ j=0

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

11 / 74

Interpretaci´on geom´etrica (II)

Cambiando los valores de wj cambiamos la direcci´ on de ~y

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

12 / 74

Interpretaci´on geom´etrica (III) Usando notaci´ on vectorial E (x) =

1 2

‚ ‚2 ‚P ‚ ‚M ~ j − ~t ‚ ‚ wi φ ‚ ‚ ‚j=1

Si minimizamos con respecto a los pesos

∂E ∂wj

~ T (~y − ~t) (ver Desarrollo A) =0=φ j

descompongamos ~t = ~t⊥ + ~tk , siendo ~tk proyeccion ortogonal de ~t en S ~t⊥ el resto ~ T ~t⊥ = 0 al ser perpendiculares, tenemos que Como φ j ∂E ~ T (~y − ~tk ) = 0, j = 1, . . . , M. =φ j ∂wj ~ i componen la base que egendra el subespacio S, el u y como φ ´nico producto vectorial con esa base que puede ser nulo es el del vector nulo, con lo que tenemos ~y = ~tk el proceso de aprendizaje trata de modificar el vector ~y de tal forma que se minimice la distancia a ~t

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

13 / 74

Soluci´on basada en la pseudoinversa Reescribimos la funci´ on de error E (w ) =

 c X M N X X 1 2

n=1 k=1



wkj φnj − tkn

j=0

2 

.



Al diferenciar con respecto a w e igualar las derivadas a cero   N X M  X wkj 0 φnj0 − tkn φnj = 0  0 n=1

j =0

En forma matricial (ΦT Φ)W T = ΦT T I I I

Φ una matriz N × M con los elementos φnj W una matriz c × M, con los elementos wkj T una matriz N × c con los elementos tkn

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

14 / 74

Soluci´on basada en la pseudoinversa (II)

La matriz ΦT Φ es cuadrada, de dimensiones M × M Si el determinante de ΦT Φ es distinto de cero (i.e. es no singular), podemos invertirla para obtener la soluci´ on W T = Φ† T

I I

Φ† es una matriz M × N denominada pseudo inversa de Φ Φ† = (ΦT Φ)−1 ΦT

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

15 / 74

Objeciones al m´etodo

Φ es, generalmente, una matriz no cuadrada y no tiene una inversa ΦT Φ suele tenerla I

la soluci´ on directa de las ecuaciones normales puede presentar dificultades F F F

F

la posibilidad de que ΦT Φ sea singular o casi singular ~ j son casi colineales si dos de los vectores φ los errores de redondeo t´ıpicos de una m´ aquina las van a hacer casi linealmente dependientes. Si esto ocurre, el procedimiento num´erico usado fallar´ a adecuado un m´etodo del tipo SVD (Singular Value Decomposition)

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

16 / 74

El perceptr´on (ver Minsky, 1969 [?]) Es la red m´ as sencilla Una u ´nica neurona, que puede tener varias entradas reales, y salida en {0,1}. Formalmente, dadas las entradas x1 , x2 , . . . , xn , la salida 0(x1 , x2 , . . . , xn ) se define mediante  o(x1 , x2 , . . . , xn ) =

1 −1

si w0 x0 + w1 x1 + . . . + wn xn > 0 sino

Los wi , i = 1, 2, . . . , n son los pesos asignados a cada entrada

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

17 / 74

El perceptr´ on. Capacidad de representaci´ on

Con un perceptr´ on podemos representar funciones l´ ogicas como AND y OR. Con un s´ olo nodo no podemos representar la funci´ on XOR.

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

18 / 74

Regla de entrenamiento del perceptr´on [?] Mecanismo de aprendizaje de respuestas ±1 adecuadas seg´ un el ejemplo de aprendizaje. Para cada ejemplo variar los wi seg´ un la expresi´ on wi ← wi + ∆wi en donde ∆wi = η(t − o)xi t es la salida esperada, o es la salida obtenida para el ejemplo η es el ratio de aprendizaje Problema: convergencia

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

19 / 74

Regla de entrenamiento delta

Soluciona el problema de la convergencia anterior Basada en gradiente descendente Se ajusta asint´oticamente a la representaci´ on deseada Medida de error E (~ w) =

1X (td − od )2 2 d∈D

D es el conjunto de ejemplos de entrenamiento, td es la salida de la funci´ on buscada, y od es la salida de la red.

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

20 / 74

Obtenci´on de la regla El vector de gradiente ser´ a ∆E (~ w) =

h

∂E ∂E , ∂E , . . . , ∂w ∂w0 ∂w1 n

i

y regla del gradiente ser´ a

~ ← +∆~ w w , ∆~ w = −η∆E (~ w) ∆E se obtiene seg´ un ∂E ∂wi

= = = = =

∂ 1 ∂wi 2

(td − od )2 d∈D P 1 ∂ (t − od )2 2 ∂wi d d∈D P 1 ∂ 2(td − od ) ∂w (td − od ) 2 i d∈D P ∂ ~ ~xd ) (td − od ) ∂w (td − w i d∈D P P

(td − od )(−xid )

d∈D

Finalmente ∆wi = η

X

(td − od )xid

d∈D

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

21 / 74

Gradiente descendente: algoritmo Paso 0: sea el conjunto de entrenamiento un conjunto de ejemplos en la forma < ~x , t > en donde ~x es el vector de valores de entrada, y t es el valor de salida. η es el ratio de aprendizaje. Paso 1: Inicializar cada wi a un valor aleatorio Paso 2: Hasta que se cumpla la condici´ on de terminaci´on I I

Inicializar los ∆wi ← 0 Para cada < ~x , t > hacer F F

Realizar una pasada con ~x y calcular o Para cada wi , hacer ∆wi ← ∆wi + η(t − o)xi

I

Para cada wi , hacer wi ← wi + ∆wi

El algoritmo anterior actualiza los pesos en cada pasada de todo el conjunto de entrenamiento

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

22 / 74

Versi´on estoc´astica

La versi´on estoc´astica lo hace para cada ejemplo: Paso 0: sea el conjunto de entrenamiento un conjunto de ejemplos en la forma < ~x , t > en donde ~x es el vector de valores de entrada, y t es el valor de salida. η es el ratio de aprendizaje. Paso 1: Inicializar cada wi a un valor aleatorio Paso 2: Hasta que se cumpla la condici´ on de terminaci´on I I

Inicializar los ∆wi ← 0 Para cada < ~x , t > hacer Realizar una pasada con ~x y calcular o Para cada wi , hacer wi ← wi + η(t − o)xi

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

23 / 74

Comentarios a las versiones

La versi´on est´andar es m´as costosa computacionalmente. La versi´on estoc´astica es m´as segura, un vector de error por cada ejemplo. La regla de entrenamiento se denomina regla delta, LMS (least-mean-square), regla ADALINE (ADAptative LINEar unit) y Widrow-Hoff.

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

24 / 74

Redes Multi-capa. Capacidad de representaci´ on

¿C´omo podemos aumentar la capacidad de representaci´on de un perceptr´on? Ejemplo I

Podr´ıamos intentar formar una red con varios perceptrones lineales como ...

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

25 / 74

Nodos

Su expresi´on ser´ıa

o(x1 , x2 ) = x3 w3,6 + x4 w4,6 + x5 w5,6 = (x1 w1,3 + x2 w2,3 )w3,6 + (x1 w1,4 + x2 w2,4 )w4,6 + (x1 w1,5 + x2 w2,5 )w5,6 = x1 (w1,3 w3,6 + w1,4 w4,6 + w1,5 w5,6 )+ x2 (w2,3 w3,6 + w2,4 w4,6 + w2,5 w5,6 ) Podr´ıamos usar perceptrones con umbral (i.e. salidas ±1) PROBLEMA −→ es necesario poder derivar las funciones de salida

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

26 / 74

Nodos (II) Soluci´on: sigmoide o = σ(~ w ~x ) = dσ(y ) dy

1 1+e −~w~x

con derivada

= σ(y )(1 − σ(y ))

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

27 / 74

Nodos (III)

Podr´ıamos obtener la expresi´ on resultande de aplicar la sigmoide a todos los nodos, para la red anterior Como puede verse, esta superficie ya es mucho m´as compleja que una superficie lineal.

o(x1 , x2 ) = σ(σ(x3 )w3,6 + σ(x4 )w4,6 + σ(x5 )w5,6 ) = σ(σ(x1 w1,3 + x2 w2,3 )w3,6 )+ σ(σ(x1 w1,4 + x2 w2,4 )w4,6 )+ σ(σ(x1 w1,5 + x2 w2,5 )w5,6 )

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

28 / 74

Capacidad de representaci´on

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

29 / 74

Algoritmo Backpropagation

Aprende los wi para una red neuronal multi-capa, con funciones de activaci´ on derivables Versi´ on fully-connected y conexi´ on estricta Funci´ on de error E (~ w) =

1 XX (tkd − okd )2 2 d∈D k∈O

en donde D es el conjunto de ejemplos y O el conjunto de nodos de salida. tkd ser´ a la salida esperada para el ejemplo d en el nodo k, okd la salida obtenida para el nodo k y el ejemplo d. Convergencia a m´ınimos locales

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

30 / 74

Algoritmo Backpropagation, versi´on estoc´astica Paso 1: Inicializar cada wij a un valor aleatorio Paso 2: Hasta que se cumpla la condici´ on de terminaci´ on Paso 3: Para cada < ~x , ~t > hacer Propagar la entrada por la red hacia adelante inicializando los nodos de entrada con ~x y calcular los o empezando por todos los nodos de la capa oculta, y a continuaci´ on los de la capa de salida. Propagar el error por la red, hacia atr´ as (1) Para cada nodo de salida k, calcular su error, δk seg´ un δk ← ok (1 − ok )(tk − ok ) (2) Para cada nodo oculto, h, calcular su error, δh seg´ un δh ← oh (1 − oh )

X

whk δk

k∈O

(3) Actualizar los wij seg´ un wij ← wij + ∆wij donde ∆wij = ηδi xij

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

31 / 74

Algoritmo Backpropagation

Similitud con regla delta En regla delta, wi se actualizan con ηxi (t − o). En backpropagation se suma a los wij el producto ηxij δi . En realidad δi es el producto de (t − o) por σ()0 en los nodos de salida P En los nodos de la capa oculta el producto es de σ()0 y whk δk k∈O

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

32 / 74

Algoritmo Backpropagation (y II)

Condiciones de parada En un problema “real” se realizan usualmente varios miles de pasadas (i.e. epochs) por todo el conjunto de entrenamiento. A veces la condici´on de parada del algoritmo es simplemente llegar a un n´ umero l´ımite de esas pasadas Otras es no alcanzar una cantidad m´ınima de error por pasada. Se ha de evitar el sobreaprendizaje u overfitting.

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

33 / 74

Momentum El algoritmo actualiza gradualmente los pesos de la red en la direcci´on de m´axima variaci´ on del error mediante la expresi´on wij (t + 1) = wij (t) − η

∂E (t) ∂wij

Si el valor de η es excesivamente grande, entonces la b´ usqueda hacia un error peque˜ no sufrir´a oscilaciones Si es muy peque˜ no, la convergencia al m´ınimo ser´a lenta y se necesitar´an muchas iteraciones para llegar a un error aceptable → momentum ∆wij (t) = −η

∂E (t) + µ∆wij (t − 1) ∂wij

Marca una inercia, en el avance hasta el punto ´ optimo, desde la u ´ltima actualizaci´on hasta la actual, lo cual evitaba las oscilaciones. Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

34 / 74

RPROP (ver [?])

Idea: variar el valor de η, conforme se avanzaba en el aprendizaje Ejemplos de algoritmos son Delta-Bar-Delta, SuperSAB y Quickprop. RPROP tiene en cuenta, en cada paso, la derivada parcial de cada peso, y su expresi´ on general para la cantidad con la que actualizar los pesos es

∆ij (t) =

∂E (t−1) ∂wij ∂E (t−1) ∂wij

η + × ∆ij (t − 1)

,

si

− > η × ∆ij (t − 1) > : ∆ij (t − 1)

,

si

,

si no

8 > >
0 ∂E (t)

× ∂wij < 0

Si de una iteraci´ on a otra, el valor de la derivada parcial del peso wij cambia su signo → la actualizaci´ on anterior fue demasiado elevada Si mantiene el signo lo que hacemos es aumentar el valor de actualizaci´ on para aumentar la velocidad de convergencia. La ecuaci´ on de actualizaci´ on queda

wij (t + 1) = wij (t) − ∆ij (t) ∗ sign

∂E (t)

!

∂wij

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

35 / 74

Algoritmo de cascada-correlaci´on (ver [?]) Responde al problema del objetivo m´ ovil del backpropagation Cada nodo en la red intenta jugar un rol determinado en el c´ alculo global El resto tambi´ en, y no se comunican entre s´ı Es dificil, en esas condiciones, que cada nodo encuentre su lugar Manifestaci´ on → el “efecto manada” Sup´ ongase dos tareas A y B a realizar por los nodos ocultos Cada nodo deber´ a decidir a cu´ al de las dos dedicarse Si A genera un error mayor que el de B entonces todos los nodos se concentrar´ an en resolver la tarea de A Una vez que A est´ a resuelta, se comenzar´ a a centrar la atenci´ on en B, y el problema en A reaparecer´ a Al final, la distribuci´ on de los nodos ser´ a correcta, pero existe un largo per´ıodo de indecisi´ on Soluci´ on → permitir que u ´nicamente un conjunto reducido de nodos cambie cada vez, manteniendo el resto constantes Dos ideas: arquitectura en cascada y algoritmo de aprendizaje

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

36 / 74

Correlaci´on en cascada - Arquitectura

Inicialmente se parte de una red sin nodos ocultos

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

37 / 74

Correlaci´on en cascada - Arquitectura (II) Cada nuevo nodo oculto recibe una conexi´ on de la entrada y se conecta a todas las salidas

October 4, datos 2007 Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ ıa de

38 / 74

Correlaci´on en cascada - Arquitectura (III) Un nuevo nodo oculto recibe conexiones de la entrada y todos los nodos ocultos preexistentes

October 4, datos 2007 Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ ıa de

39 / 74

Correlaci´on en cascada - Aprendizaje

Los pesos de los arcos que van desde la entrada a los nodos ocultos se congelan una vez se a˜ naden Los pesos de los arcos que van desde los nodos ocultos a los de salida se entrenan repetidamente Inicialmente (sin nodos ocultos) se entrenan los pesos de las entradas a las salidas (regla delta, regla de entrenamiento del perceptron, etc) Una vez no se tiene una reducci´ on significante del error, se evalua la red sobre D. I Si el error obtenido es aceptable, paramos I Si no, aun queda un resto de error que necesitamos reducir F Intentamos reducirlo a˜ nadiendo un nuevo nodo (usamos el algoritmo de creaci´ on de nodos) F Congelamos todos los pesos de entrada, incluido el del nuevo nodo F Entrenamos los pesos de salida de nuevo F Repetimos el ciclo hasta que el error es aceptable

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

40 / 74

Correlaci´on en cascada - Alg. Creaci´ on de nodos

Se comienza con un nodo candidato que recibe conexiones de 1 todo nodo de entrada 2 todo nodo oculto preexistente sin conectar su salida Se realizan varias pasadas de entrenamiento ajustando los pesos de entrada al nuevo nodo, intentando maximizar S → correlaci´ on entre V y el error residual Eo que se observa en la unidad de salida o

S =

˛ ˛ ˛ ˛ X ˛X ˛ ¯ ¯ ˛ ˛ (V − V )(E − E ) p p,o o ˛ ˛ ˛ o ˛ p

en donde I V es el valor de salida del nodo candidato I o es la salida de la red en la que medimos el error I p es la instancia de entrada I V ¯ la media de los valores de V sobre todas las entradas I E¯o la media de los valores de Eo sobre todas las entradas

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

41 / 74

Correlaci´on en cascada - Maximizando S

Para maximizar S necesitamos calcular ∂S/∂wi X ∂S/∂wi = σo (Ep,o − E¯o )fp0 Ii,p p,o

en donde σo es el signo de S fp0 es la derivada de la funci´ on de activaci´ on del nodo candidato, para la instancia p, con respecto a la suma de las entradas Ii,p es la entrada al nodo candidato desde el nodo de entrada i, con la instancia p Una vez calculada ∂S/∂wi para todo arco de entrada al nodo candidato realizamos gradiente ascendente para maximizar S

Juan A. Bot´ıa (Departamento de Ingenier´ıa de Redes la Informaci´ neuronales on yartificiales las Comunicaciones para aprendizaje Universidad autom´ de atico Murcia) y miner´ October ıa de 4, datos 2007

42 / 74

Redes RBF (ver [?])

Las redes RBF (Radial Basis Functions) Se trata de aproximar globalmente una funci´ on mediante el uso de varias RBF que realizan una aproximaci´ on local. La hip´ otesis inducida con este tipo de m´ etodos va a tener la forma fˆr (x) = w0 + w1 K1 (d(µ1 , x)) + w2 K2 (d(µ2 , x)) + · · · + wk Kk (d(µk , x))

(1)

en donde I cada µi es un punto del espacio