Curso de Ingeniería Neuronal Clase 2: Sistemas estáticos

Curso de Ingeniería NeuronalClase 2: Sistemas estáticos

Universidad de Santiago de ChilePrograma

Magíster en Ingeniería Informática

Septiembre 2014

Dr. Gonzalo Acuña L.

Universidad de Santiago de Chile Departamento de Ingeniería Informática

Ingeniería Neuronal Magíster en Ingeniería Informática

Temario• Introducción• Redes monocapa: Perceptron y Adaline

– El problema de la clasificación– Aprendizaje en redes monocapa

• Redes multicapa: Perceptron– El problema de la regresión– El método de retropropagación del error– Métodos de primer y segundo orden– El problema de la generalización

I . Introducción



• Sistema– Porción de la realidad que se desea aislar para

estudio.

– Combinación de elementos o componentes interrelacionados entre sí y con el todo, que actúan juntos para lograr una cierta meta.

– Variables entrada, salida, estado

Sistema estático: simultaneidad causa-efecto.



Denominación confusa:En el ámbito de los sistemas físicos,no implica

causas y efectos constantes en el tiempo.

Ejemplo: resistencia eléctrica y la Ley de Ohm:

R

i

+

-v



• Hay un problema transversal que es el de la “aproximación de funciones” que en el caso de sistemas estáticos puede diferenciarse en al menos otros dos subproblemas:

• Clasificación

• Regresión



• Clasificación:– Se trata de aproximar una función que

represente la probabilidad de pertenencia de un cierto objeto -caracterizado por un conjunto de variables de entrada, continuas o discretas- a una clase determinada (salida con valores discretos). Ejemplo: reconocimiento de caracteres.

y = f(x, w)



• Clasificación y funciones discriminantes• Cómo se puede realizar una clasificación?

• Mediante el uso de funciones discriminantes que están definidas en el espacio de vectores que se desea clasificar y producen un valor real que se puede comparar.



• Se tiene una función (gi) por clase (si)

• La regla de clasificación es:

u Є si si gi (u ) > gj ( u ); j ≠ i

• Para problemas de 2 clases se puede reducir a una función: g(u ) = g1(u ) – g2 (u), luego u Є s1 g( u ) > 0 y u Є s2 si no.



• Regresión:– Se trata de aproximar la función generadora

(desconocida) de un cierto proceso mediante otra que mapee elementos del conjunto de variables de entrada pertinentes en otros del conjunto de variables de salida. Usualmente aquí se trata con valores continuos.

y = f(x, w)

II. Redes Monocapa: Perceptron y Adaline



Perceptron Monocapa

• Historia: Frank Rossenblat, 1957

• Red de “3 capas” la última de ellas con función de transferencia de tipo umbral lógico diseñada para tarea de clasificación

• retina - células de asociación – unidad de decisión



• Clasificación lineal mediante Perceptron

• El Perceptron realiza una función discriminante lineal:g (u) = a1 u1 + a2 u2 + ...+ an un + a n+ 1 = a . u

El valor asociado a g( u ) = 0 corresponde a la frontera, un hiperplano, que separa las dos clases.

• Los perceptrones son adecuados sólo para clases linealmente separables.

• El problema de aprendizaje se reduce a encontrar un hiperplano que separa a las clases.



a y

X0

X1

w0

w1

0 0 1 1a X Xω ω θ= + = 01 0

1 1

X Xω θω ω

⇒ = − +

X0

X1

BB

BB

A

A

A

A

A

θ



REGLA DE APRENDIZAJE _

y ( x ) = Ø ( W • X) : Salida del perceptron ŷ ( x ) = Salida deseada Є 1, –1 ΔW k = η ( ŷ ( xk ) -y ( xk ) ) · xk

WK+1 = WK + ∆ WK

ó ∆WK = 0 si la salida es correcta + 2 η Xk Si ŷ ( xk ) = 1 , y ( Xk ) =-1

- 2η Xk Si ŷ ( xk ) = -1 ,y ( Xk ) =1

n > o; X1..... Xk : Secuencia de entrada



• Convergencia del algoritmo de aprendizaje del Perceptron:

Está demostrada para problemas linealmente separables la convergencia en un número finito de pasos.



• Espacio de salida para compuerta AND

(1,1)

(1,0)

(0,1)

(0,0)

1.5 = w1*I1 + w2*I2

Input 1

Input 2



• Espacio de salida para compuerta XOR • => necesidad de capa oculta

(1,1)

(1,0)

(0,1)

(0,0)

Input 1

Input 2



Redes Monocapa: Adaline

• Historia: Widrow - Hoff, 1960• Al igual que en el caso del Perceptron, se

desarrolló en forma independiente para resolver el problema de clasificación

• Adecuado cuando las clases son linealmente separables



• Entrenamiento:– Esta basado en el “Principio de Mínima

Alteración”

– Se basa en una regla de Mínimos Cuadrados considerando una función cuadrática del error de salida lo que finalmente da lugar a una regla, conocida como “Regla Delta” muy semejante a la del Perceptron.



Error cuadrático 2

ˆ2

1∑∑∈∈

−==Ss

ss

Ss

s yyEE

con s

ŷ : vectorde valores de salida deseados s

y : vector de salida de la red s s s 2

E : 2

1 I ŷ – y I medida del error cuadrático.

Para la muestra S : conjunto de muestras (entrenamiento)



2

1

( ) ( )

1( ( ) ( ))

2

( )

( 1) ( ) ( ( ) ( )) ( )

N

j j iji

y t W X t

J d t y t

Jd w X X

w

W t W t d t y t X tα=

= ⋅

= −

∂ = − −∂⇒ + = + −

∑

II. Redes Multicapa: Perceptron



Redes Multicapas Definición : Red en la que sus neuronas están

ordenadas en capas o estratos sucesivos. Cada capa recibe entradas desde la capa previa ( o entrada externa ) y envía sus salidas a la capa siguiente. No hay conexiones internas en cada capa.



V. RNA



Σ… fNL Σ……

x1(t)x2(t)

xn(t)

vi 1

bin1

Σ… fNL

vi 2

bin2

Σ… fNL

vi p

binp

Σ…

Σ…

wj 1

bout1wj 2

bout2

wj m

boutm

. .

. . .

.

y1(t)

y2(t)

ym(t)

Retropropagación



X1

X2

1

w11

w12

w21

w22

w31 w32

1

w’11

w’21

w’31

y

Backpropagation

X1

X2

1

w11

w12

w21

w22

w31 w32

1

w’11

w’21

w’31

Pesos Iniciales

Aleatorios

Salida de la Red

ˆerror y y= −

Calculo de la salida

Cálculo del

error

Retropropagación del error

Modificación de los pesos de la Red



RetropropagaciónX1

X2

1

w11

w12

w21

w22

w31 w32

1

w’11

w’21

w’31

y

1 ( )tt t t t

Jw w d w

wη η+

∂= + = + −∂



• Ejemplo:

• Capa Salida:

1

2 21 11 2 21 31

'

1 1( ) [ ( ' ' ' ) ]

2 2t t t

a

J y d f O w O w w d= − = + + −144424443

1 111 '

( ) ' ( ) (1 )'

t

t t t t t t

Jy d f O y d y y O

wδ

∂ = − ⋅ ⋅ = − −∂ 1442443

12

2 2

22

1( )

1

(1 )'( ) (1 ) ( )

1 1

(1 ) (1 )

1 1

1 (1 )

'( ) (1 )

x

xx x

x x

x x

x x

Sea f xe

ef x e e

x

e e

e e

y ye e

f x y y

−

− −− − −

− −

− −

− −

=+

∂ +⇒ = = − + ⋅ −

∂+ −= =

+ +

= − = −+ +

⇒ = −



• Capa Escondida:

• Si varias salidas:

1

11 1 11

'

11 1 1 1

'

'

( ) (1 ) ' (1 )11 1 1 1

' (1 )

t

t

t

OJ J a(Regla de la cadena)

w a O w

y d y y w O O Xt t t t

' w O O X

δ

δ

δ

∂∂ ∂ ∂= ⋅ ⋅∂ ∂ ∂ ∂

= − − ⋅ ⋅ −

= ⋅ ⋅ ⋅ −

144444424444443

144424443

1 1 1' ' (1 )

t

k jkk

w O O X

δ

δ= ⋅ − ⋅∑144424443



Salidas de la Red

Retropropagación

Error



X(t+1)

VZin (t)

)(1

1tNL e

f Zin−+=

Z(t)W

Y(t)X(t) E(t))1()( +−= ttfE XY

1=Ef&( )2)(

)(

1 t

t

NLe

ef

Zin

Zin

−

−

+=&

W j π E(t)

πZ(t)

-∆W

π

πX(t)

-∆V



Retropropagación usando gradiente descendente

• Ventajas:– Implementación simple

– Método estándar que generalmente funciona bien

• Desventajas:– Lento e ineficiente

– Puede quedar atrapado en mínimos locales entregando resultados sub-óptimos



• Métodos de Gradiente– En General:

Problema: Convergencia lenta. Tendencia a

quedar atrapada en mínimos locales

1

1: ( )

dirección

k kamplitud

pasobusqueda

k k

w w h d

Gradiente w w d w

+

+

= + ⋅

= + −∇



Mínimo local

Local Minimum

Global Minimum



• Ejemplo:2

1 1

2 1

( ) 1

: 1 1 1 ( 2 ) 1

1 1 ( 2 ) 1

.

k k

k

J x x y d

Si x x x

x x

cte

+

+ −

= == ⇒ = + ⋅ − = −

= − + ⋅ − =M

x

J(x)

-1 1



Mejoras a Gradiente Descendente

• Momentum– Añade porcentaje del último movimiento al

actual



La opción de calcular en forma elegante y eficiente el gradiente permite tratar el problema de optimización con toda la batería de métodos de optimización que proporciona la optimización en sistemas no-lineales.



Otros algoritmos para determinar valor de los pesos de

la red



Métodos de optimización

• Gradiente Conjugado

• Quasi-Newton

• Simulated Annealing

• Algoritmos genéticos

• …etc

[ ]2ˆ21∑

=−=

k

sh

t

ti

ii YYJMin

¿Deterministas o Estocásticos?



Fletcher y Reeves...

• Es una extensión del método de gradiente conjugado a funciones cualquiera (no necesariamente cuadráticas) y sin la utilización explícita del Hesiano.

• Etapa de inicialización:– Seleccionar un punto de partida

– Calcular

• Etapa iterativa– Determinar que minimiza

en la dirección

– Calcular donde

0x( )000 xfgd −∇=−=

kλ kkkk dxx ⋅+=+ λ1

kdkkkk dgd ⋅+−= ++ β11

kTk

kTk

kgggg⋅⋅= ++ 11β



Gradiente Conjugado

Dirección de gradienteX0

X1

X2

Gradienteconjugado

1k wk kd J dβ −= −∇ +



Métodos 2º orden tipo Newton

• Taylor de J(w):

0 0 0 0 0

2

0 0

0 0

10 0

1( ) ( ) ( ) ( ) ( ) (1)

2

(1) :

( ) ( ) ( ) (2)

( ) 0

0 ( ) ( )

( )

iji i j

J w J w w J w w w H w w

J JJ H

w w w

Derivando

J w J w H w w

mínimo J w

J w H w w

w w H J w−

= + − ∇ + − − +

∂ ∂∇ = =∂ ∂ ∂

∇ = ∇ + − +⇒ ⇒∇ =⇒ = ∇ + −

⇒ = − ∇

L

L



• Ejemplo:

• Quasi-Newton:– H-1 se aproxima en forma recursiva.

– BFGS Broyden, Fletcher, Goldfarb, Shanno

20

2

2

1 1

2 0

( ) ; 1

2 ; 2

11 ( 2 ) 0

21

0 ( 2 ) 02

J w w w

J Jw

w w

w w

w w

= =

∂ ∂= =∂ ∂

⇒ = + − =

= + − =



Métodos Quasi-Newton

( )[ ] kkkkk gxfxx ⋅∇⋅−= −+

12

1 α

( )kxf2∇

es una aproximación convenientemente elegida

de…

kG

kG

Simétrica

Definida positiva

• Hay muchas formas de actualizar la matriz G o su inversa S y que satisfacen los criterios para anteriores.

kkk qpG =⋅kkkkk dxxp ⋅=−= + α1

kkk ggq −= +1

)()()(

1kkk

Tk

Tkkkkkk

kk pGqppGqpGq

GG⋅−⋅

⋅−⋅⋅−+=+

)())(

1kkk

Tk

Tkkkkkk

kk qSpqqSpqSp

SS⋅−⋅

⋅−⋅⋅−+=+



Levenberg - Marquardt

• Modificación de Gauss-Newton

• Ventajas:– Bien definido aunque J no sea de rango pleno

– Globalmente convergente

1

1 [ ]T Tk k k k k k k

AproximaciónHessiano

w w J J I J rµ −+ = − +



• - convergencia lineal

• Convergencia cuadratica



Simulated Annealing• Energía mínima...

• ¿« f » diférenciable?

• ¿Óptimos locales?

• Parámetros?

• Enfriamiento?

• Calidad de la solución?

Ω

Estado inicial

Estado final



Algoritmos genéticos

• Rango= [-4 , 4]

• Bits=8

• Población=30

• Generaciones=50



• Los algoritmos genéticos son una clase de estrategias de búsqueda que presentan un compromiso equilibrado y razonable entre la exploración y la explotación; en efecto, analisis teóricos han mostrado que los algoritmos genéticos generan este compromiso de manera casi óptima.

a) Inicializar la Población : Creary evaluar la población inicial decromosomas.

b) Seleccionar y reproducir loscromosomas.

c) Evaluar los “fitness ” del

nuevo hijo.

d) Substituir los cromosomas de lapoblación por los hijos.

e) Volver a b)

• Evaluación.

• Selección.

• Reproducción con cruzamiento y mutación



Problemas en la práctica...

• ¿Qué algoritmo utilizar?

• ¿Qué fórmula Q-N utilizar?

• ¿Qué tipo de búsqueda lineal sedeberá implementar?

• ¿Cómo hacer la corrección de la

matriz cuando ?1+kS ISo=

Curso de Ingeniería Neuronal Clase 2: Sistemas estáticos

Documents

Transcript of Curso de Ingeniería Neuronal Clase 2: Sistemas estáticos