Entrenamiento de redes neuronales basado en algoritmos evolutivos (página 2)

1.2. Organización de esta tesis

El resto de este trabajo se encuentra organizado de la siguiente manera: •

•

•

•

•

• Los capítulos 2 a 4 son capítulos introductorios, y se presentan las tecnologías utilizadas a lo largo de esta tesis. Luego, en los capítulos restantes, se realiza una presentación del problema, la solución propuesta y los resultados y conclusiones obtenidas a lo largo de los experimentos. En el Capítulo 2 se presentan las redes neuronales. Se introducen los conceptos básicos de ésta técnica y se realiza una descripción detallada del modo de funcionamiento de las mismas. El Capítulo 3 está dedicado al estudio de los métodos de aprendizaje de las redes neuronales. Se realiza una introducción a los métodos de entrenamiento y se desarrolla en detalle el algoritmo Backpropagation. Se exponen los distintos modos de entrenamiento y se enumeran las distintas técnicas para acelerar el entrenamiento de una red neuronal. Se introduce el concepto de generalización. En el Capítulo 4 se introducen los conceptos generales de los algoritmos genéticos. Se describe en detalle las características de esta técnica y se realiza una descripción pormenorizada de los operadores genéticos. Esta descripción sirve como base para entender las características de la solución propuesta. En el Capítulo 5 se enumerar las deficiencias que tiene el algoritmo de entrenamiento backpropagation y que llevan a la necesidad de buscar una forma alternativa y complementaria de entrenar redes neuronales. Se plantean los objetivos de diseño del método alternativo. En el Capítulo 6 se describen las características principales que convierten a los algoritmos genéticos como una alternativa interesante para entrenar redes neuronales. Se presentan las características de diseño del método alternativo y se proponen algunas variantes de los operadores genéticos para entrenar redes neuronales.

L. Federico Bertona Introducción 3 •

•

•

• Entrenamiento de redes neuronales basado en algoritmos evolutivos

El Capítulo 7 está dividido en dos partes. En la primera de ellas se realiza una presentación del diseño experimental. Se describen las características de los experimentos y la manera en que se analizarán los resultados. La segunda parte de dicho capítulo esta dedicada a la presentación de los resultados y al análisis de los mismos. Se muestran los principales resultados obtenidos a lo largo de cada experimento de manera gráfica y se realiza una descripción detallada de los mismos. En el Capítulo 8 se retoman todas las cuestiones surgidas a lo largo de este trabajo y se responden a las mismas en base a los resultados experimentales y/o los fundamentos teóricos introducidos. Contiene las conclusiones finales de este trabajo. También en este capítulo se identifican las limitaciones del trabajo y se plantean futuras líneas de investigación. En el Apéndice A se despliegan los datos numéricos obtenidos a lo largo de la etapa de experimentación. En el Apéndice B se introduce la metodología de software aplicada al desarrollo realizado en esta tesis. En el se presentan los conceptos fundamentales que se utilizaron para diseñar y desarrollar el sistema utilizado en esta tesis.

L. Federico Bertona Redes neuronales 5 Entrenamiento de redes neuronales basado en algoritmos evolutivos

Capítulo 2: Redes neuronales

Las redes neuronales artificiales (RNA) son modelos matemáticos que intentan reproducir el funcionamiento del sistema nervioso. Como todo modelo, realizan una simplificación del sistema real que simulan y toman las características principales del mismo para la resolución de una tarea determinada.

2.1. El modelo biológico

El cerebro es el elemento principal del sistema nervioso humano y está compuesto por un tipo especial de célula llamada neurona. Una neurona es una célula viva y como tal posee todos los elementos comunes de las células biológicas. A su vez, las neuronas tienen características propias que le permiten comunicarse entre ellas, lo que las diferencia del resto de las células biológicas. La figura 2.1 muestra la estructura típica de una neurona biológica. Figura 2.1. Neurona biológica

De la figura se observa que la neurona biológica esta compuesta por un cuerpo celular o soma, del cual se desprende árbol de ramificaciones llamado árbol dendrítico, compuesto por las dendritas. Del soma también parte una fibra tubular, llamada axón, el cual suele ramificarse cerca de su extremo. Las dendritas actúan como un canal de entrada de señales provenientes desde el exterior hacia la neurona, mientras que el axón actúa como un canal de salida. El espacio entre dos neuronas vecinas se denomina sinapsis. En el córtex cerebral se observa una organización horizontal en capas, así como también una organización vertical en columnas de neuronas. La intensidad de una sinapsis no es fija, sino que puede ser modificada en base a la información proveniente del medio. De esta manera la estructura del cerebro no permanece fija sino que se va modificando por la formación de nuevas conexiones, ya sean excitadoras o inhibidoras, la destrucción de conexiones, la modificación de la intensidad de la sinapsis, o incluso por muerte neuronal.

6 Redes neuronales L. Federico Bertona Entrenamiento de redes neuronales basado en algoritmos evolutivos

Desde un punto de vista funcional, las neuronas conforman un procesador de información sencillo. Constan de un subsistema de entrada (dendritas), un subsistema de procesamiento (el soma) y un subsistema de salida (axón) Como se menciono antes, una de las características principales de las neuronas, y que la distinguen del resto de las células, es su capacidad de comunicarse. Las señales nerviosas pueden ser eléctricas o químicas. La transmisión química se da principalmente en la comunicación entre neuronas, mientras que la eléctrica se produce dentro de una neurona [García Martínez, et alt, 2003]. En general, una neurona recibe información de cientos de neuronas vecinas y la transmite a otras tantas neuronas. La comunicación entre neuronas se lleva a cabo de la siguiente manera: en el soma de las neuronas transmisoras o presinápticas se genera un pulso eléctrico llamado potencial de acción. El pulso eléctrico se propaga a través del axón en dirección a las sinapsis. La información se transmite a las neuronas vecinas utilizando un proceso químico, mediante la liberación de neurotransmisores. Estos neurotransmisores se transmiten a través de la sinapsis hacia la neurona receptora. La neurona receptora o postsináptica toma la señal enviada por cientos de neuronas a través de las dendritas y la transmite al cuerpo celular. Estas señales pueden ser excitadoras (positivas) o inhibidoras (negativas) [Gurney, 1997]. El soma es el encargado de integrar la información proveniente de las distintas neuronas. Si la señal resultante supera un determinado umbral (umbral de disparo) el soma emite un pulso que se transmite al lo largo del axón dando lugar a la transmisión eléctrica a lo largo de la neurona. Al llegar la señal al extremo del axón se liberan neurotransmisores que permiten transmitir la señal a las neuronas vecinas. [Nascimiento, 1994].

2.2. Estructura de un sistema neuronal artificial

Como se dijo anteriormente, las redes neuronales son modelos matemáticos que intentan reproducir el comportamiento del cerebro humano. El principal objetivo de este modelo es la construcción de sistemas capaces de presentar un cierto comportamiento inteligente. Esto implica la capacidad de aprender a realizar una determinada tarea. Las características principales que reproducen las redes neuronales artificiales se pueden reducir a los siguientes tres conceptos: procesamiento paralelo, distribuido y adaptativo. [Del Brio y Sanz Molina, 2002] El verdadero poder de este modelo radica en el procesamiento paralelo realizado por las neuronas artificiales. La neurona artificial es un elemento de procesamiento simple y constituye el elemento principal de un sistema neuronal artificial. Estas neuronas artificiales se combinan en estructuras denominadas capas. Una red neuronal artificial esta un compuesta por un conjunto de capas. De esta manera, la información se encuentre distribuida a lo largo de las sinapsis de la red, dándole a este sistema cierta tolerancia a fallos. A su vez, las redes neuronales artificiales son capaces de adaptar su funcionamiento a distintos entornos modificando sus conexiones entre neuronas. De esta manera pueden aprender de la experiencia y generalizar conceptos.

L. Federico Bertona Redes neuronales 7 Entrenamiento de redes neuronales basado en algoritmos evolutivos

Por último, un conjunto de redes neuronales, junto con las interfases de entrada y salida, y los módulos lógicos adicionales conforman un sistema neuronal artificial.

2.3. Modelo de neurona artificial

La neurona artificial es un elemento de procesamiento simple que a partir de un vector de entradas produce una única salida. En general podemos encontrar tres tipos de neuronas artificiales, donde cada una de las cuales tiene su contraparte en el sistema nervioso:

1. Las que reciben información directamente desde el exterior, a las cuales se las denomina neuronas de entrada. 2. Las que reciben información desde otras neuronas artificiales, a las cuales se las denomina neuronas ocultas. Es en estas neuronas, en particular en sus sinapsis, donde se realiza la representación de la información almacenada. 3. Las que reciben la información procesada y las devuelven al exterior. A estas neuronas se las denomina neuronas de salida.

La figura 2.2 muestra los elementos que componen una neurona artificial: •

•

•

• Figura 2.2. Neurona artificial

Conjunto de entradas, xj(t). Estas pueden ser provenientes del exterior o de otras neuronas artificiales.

Peso sinápticos, wij. Representan el grado de comunicación entre la neurona artificial j y la neurona artificial i. Pueden ser excitadores o inhibidores

Regla de propagación, si(wij, xj(t)). Integra la información proveniente de las distintas neuronas artificiales y proporciona el valor del potencial postsináptico de la neurona i.

Función de activación, fi(ai(t-1), hi(t)). Provee el estado de activación actual de la neurona i.

Entrenamiento de redes neuronales basado en algoritmos evolutivos 8 Redes neuronales L. Federico Bertona • Función de salida, Fi(ai(t)). Representa la salida actual de la neurona i. De esta forma, la salida producida por una neurona i, para un determinado instante de tiempo t puede ser escrita en forma general de la siguiente manera yi(t) = Fi( fi[ai(t -1),s i(wij,x j(t))]) (2.1) A continuación se estudian cada uno de los puntos introducidos anteriormente.

2.3.1. Entradas y salidas

Las entradas y salidas de una neurona pueden ser clasificadas en dos grandes grupos, binarias o continuas. Las neuronas binarias (digitales) sólo admiten dos valores posibles. En general en este tipo de neurona se utilizan los siguientes dos alfabetos {0,1} o {-1,1}. Por su parte, las neuronas continuas (analógicas) admiten valores dentro de un determinado rango, que en general suele definirse como [-1, 1]. La selección del tipo de neurona a utilizar depende de la aplicación y del modelo a construir.

2.3.2. Pesos sinápticos

El peso sináptico wij define la fuerza de una conexión sináptica entre dos neuronas, la neurona presináptica i y la neurona postsináptica j. Los pesos sinápticos pueden tomar valores positivos, negativos o cero. En caso de una entrada positiva, un peso positivo actúa como excitador, mientras que un peso negativo actúa como inhibidor. En caso de que el peso sea cero, no existe comunicación entre el par de neuronas. Mediante el ajuste de los pesos sinápticos la red es capaz de adaptarse a cualquier entorno y realizar una determinada tarea.

2.3.3. Regla de propagación

La regla de propagación determina el potencial resultante de la interacción de la neurona i con las N neuronas vecinas. El potencial resultante hi se puede expresar de la siguiente manera: hi(t) =s i(wij,x j(t)) (2.2) La regla de propagación más simple y utilizada consiste en realizar una suma de las entradas ponderadas con sus pesos sinápticos correspondientes:

Entrenamiento de redes neuronales basado en algoritmos evolutivos L. Federico Bertona Redes neuronales 9 hi(t) =?wij *x j(t) j (2.3) 2.3.4. Función de activación

La función de activación determina el estado de activación actual de la neurona en base al potencial resultante hi y al estado de activación anterior de la neurona ai(t-1). El estado de activación de la neurona para un determinado instante de tiempo t puede ser expresado de la siguiente manera: ai(t) = fi(ai(t -1),hi(t)) (2.4) Sin embargo, en la mayoría de los modelos se suele ignorar el estado anterior de la neurona, definiéndose el estado de activación en función del potencial resultante hi: ai(t) = fi(hi(t)) (2.5) La tabla 2.1 muestra un listado de algunas de las funciones de activación más utilizadas en los distintos modelos de redes neuronales artificiales. Tabla 2.1. Funciones de activación

2.3.5. Función de salida

La función de salida proporciona el valor de salida de la neurona, en base al estado de activación de la neurona. En general se utiliza la función identidad, es decir: yi(t) = Fi(ai(t)) = ai(t) (2.6)

10 Redes neuronales L. Federico Bertona Entrenamiento de redes neuronales basado en algoritmos evolutivos

2.4. Arquitectura de una red neuronal

Una vez definida el tipo de neurona que se utilizará en un modelo de redes neuronales artificiales es necesario definir la topología de la misma. La organización y disposición de las neuronas dentro de una red neuronal se denomina topología, y viene dada por el número de capas, la cantidad de neuronas por capa, el grado de conectividad, y el tipo de conexión entre neuronas. Las neuronas suelen agruparse en unidades funcionales denominadas capas. Se denomina capa de entrada a aquella que esta compuesta por neuronas de entradas y por lo tanto recibe información procedente desde el exterior. Análogamente, se denomina capa oculta y capa de salida a aquellas capas que están compuestas por neuronas ocultas y de salida respectivamente. Una red neuronal artificial esta compuesta por una o más capas, las cuales se encuentran interconectadas entre sí. Entre un par de neuronas de la red neuronal artificial pueden existir conexiones. Estas conexiones son las sinapsis, tienen asociadas un peso sináptico, y son direccionales. Cuando la conexión se establece entre dos neuronas de una misma capa hablamos de conexiones laterales o conexiones intra-capa. Por el contrario, si la conexión se establece entre neuronas de distintas capas se la denomina conexión inter-capa. Si la conexión se produce en el sentido inverso al de entrada-salida la conexión se llama recurrente o realimentada. Una red puede estar formada por una única capa de neuronas. En este caso hablamos de redes monocapa, y las neuronas que conforman dicha capa cumplen la función de neuronas de entrada y salida simultáneamente. Cuando la red esta compuesta por dos o más capas hablamos de redes multicapa. A su vez, hablamos de redes neuronales con conexión hacia delante (redes feedforward) cuando las conexiones entre las distintas neuronas de la red siguen un único sentido, desde la entrada de la red hacia la salida de la misma. Cuando las conexiones pueden ser tanto hacia delante como hacia atrás hablamos de redes recurrentes (redes feedback).

2.5. Aprendizaje

Durante la operatoria de una red neuronal podemos distinguir claramente dos fases o modos de operación: la fase de aprendizaje o entrenamiento, y la fase de operación o ejecución. Durante la primera fase, la fase de aprendizaje, la red es entrenada para realizar un determinado tipo de procesamiento. Una vez alcanzado un nivel de entrenamiento adecuado, se pasa a la fase de operación, donde la red es utilizada para llevar a cabo la tarea para la cual fue entrenada.

2.5.1. Fase de entrenamiento.

Una vez seleccionada el tipo de neurona artificial que se utilizará en una red neuronal y determinada su topología es necesario entrenarla para que la red

L. Federico Bertona Redes neuronales 11 Entrenamiento de redes neuronales basado en algoritmos evolutivos

pueda ser utilizada. Partiendo de un conjunto de pesos sinápticos aleatorio, el proceso de aprendizaje busca un conjunto de pesos que permitan a la red desarrollar correctamente una determinada tarea. Durante el proceso de aprendizaje se va refinando iterativamente la solución hasta alcanzar un nivel de operación suficientemente bueno. El proceso de aprendizaje se puede dividir en tres grandes grupos de acuerdo a sus características [Isasi Viñuela y Galván León, 2004], [Yao, 1999]: •

•

• Aprendizaje supervisado. Se presenta a la red un conjunto de patrones de entrada junto con la salida esperada. Los pesos se van modificando de manera proporcional al error que se produce entre la salida real de la red y la salida esperada. Aprendizaje no supervisado. Se presenta ala red un conjunto de patrones de entrada. No hay información disponible sobre la salida esperada. El proceso de entrenamiento en este caso deberá ajustar sus pesos en base a la correlación existente entre los datos de entrada. Aprendizaje por refuerzo. Este tipo de aprendizaje se ubica entre medio de los dos anteriores. Se le presenta a la red un conjunto de patrones de entrada y se le indica a la red si la salida obtenida es o no correcta. Sin embargo, no se le proporciona el valor de la salida esperada. Este tipo de aprendizaje es muy útil en aquellos casos en que se desconoce cual es la salida exacta que debe proporcionar la red.

2.5.2. Fase de operación.

Una vez finalizada la fase de aprendizaje, la red puede ser utilizada para realizar la tarea para la que fue entrenada. Una de las principales ventajas que posee este modelo es que la red aprende la relación existente entre los datos, adquiriendo la capacidad de generalizar conceptos. De esta manera, una red neuronal puede tratar con información que no le fue presentada durante de la fase de entrenamiento.

2.6. Redes neuronales con conexión hacia delante

Las redes neuronales artificiales con conexión hacia delante son el tema central de esta tesis. Este tipo de red, que se caracteriza por su organización en capas y conexiones estrictamente hacia delante, utiliza algoritmos de entrenamiento del tipo supervisado. Este grupo de red es el más utilizado en aplicaciones prácticas que utilicen redes neuronales, obteniéndose muy buenos resultados fundamentalmente como clasificadores de patrones y estimadores de funciones. Dentro de este grupo de redes neuronales encontramos al perceptrón, la red ADALINE/MADALINE, y al perceptrón multicapa.

yi(t) = f(?wijx j -?i ) ?i, 1=i=m yi(t) =?wijx j -?i ?i, 1=i=m 12 Redes neuronales Entrenamiento de redes neuronales basado en algoritmos evolutivos

2.6.1. Perceptrón.

Este modelo tiene gran importancia histórica ya que fue el primer modelo en poseer un mecanismo de entrenamiento que permite determinar automáticamente los pesos sinápticos que clasifican correctamente a un conjunto de patrones a partir de un conjunto de ejemplos. La arquitectura del perceptrón esta compuesta por dos capas de neuronas, una de entrada y una de salida. La capa de entrada es la que recibe la información proveniente del exterior y la transmite a las neuronas sin realizar ningún tipo de operación sobre la señal de entrada. En general la información entrante es binaria. La función de activación de las neuronas de un perceptrón es del tipo escalón, dando de esta manera sólo salidas binarias. Cada neurona de salida del perceptrón representa a una clase. Una neurona de salida responde con 1 si el vector de entrada pertenece a la clase a la que representa y responde con 0 en caso contrario. La operación de un perceptrón con n neuronas de entrada y m neuronas de salidas puede ser resumida de la siguiente manera: n

j=1 (2.7) El algoritmo de entrenamiento del perceptrón se encuentra dentro de los denominados algoritmos por corrección de errores. Este tipo de algoritmos ajustan los pesos de manera proporcional a la diferencia entre la salida actual proporcionada por la red y la salida objetivo, con el fin de minimizar el error producido por la red. Se puede demostrar que este método de entrenamiento converge siempre en un tiempo finito y con independencia de los pesos de partida, siempre que la función a representar sea linealmente separable. El principal problema de este método de entrenamiento es que cuando la función a representar no es linealmente separable el proceso de entrenamiento oscilará y nunca alcanzará la solución. Las funciones no separables linealmente no pueden ser representadas por un perceptrón.

2.6.2. ADALINE / MADALINE

Otro de los modelos que tienen gran importancia es la red neuronal ADALINE. La topología de la red ADALINE es similar a la del perceptrón sólo que en este caso la función de salida de las neuronas es lineal. Dado que las señales de entrada pueden ser continuas, la red ADALINE es un dispositivo de entrada/salida analógica (continua) a diferencia del perceptrón que de acuerdo a lo dicho anteriormente es un dispositivo entrada/salida digital (binaria) La operación de una red ADALINE con n neuronas de entrada y m neuronas de salidas puede ser resumida de la siguiente manera: n

j=1 (2.8)

L. Federico Bertona

L. Federico Bertona Redes neuronales 13 Entrenamiento de redes neuronales basado en algoritmos evolutivos

Sin embargo, la principal diferencia entre la red ADALINE y el perceptrón consiste en la regla de aprendizaje que utilizan. En el caso de la red ADALINE implementa como método de aprendizaje la regla de Widrow-Hoff, también conocida como regla LMS (Least Mean Squares, mínimos cuadrados), que realiza una actualización continua de los pesos sinápticos de acuerdo a la contribución de cada neurona sobre el error total de la red. Este método produce un conjunto de pesos sinápticos óptimos desde el punto de vista de los mínimos cuadrados (un conjunto de pesos que minimiza el error cuadrático que comete la red), y en caso de que los vectores de entrada sean linealmente independientes produce una asociación perfecta entre entradas-salidas. Existe una versión multicapa de la ADALINE denominada MADALINE (Multiple ADALINE, múltiples Adalides) que consiste en una red neuronal con neuronas similares a las de la ADALINE pero que contiene capas de neuronas ocultas.

2.6.3. Perceptrón multicapa

El perceptrón multicapa es una extensión del perceptrón simple. La topología de un perceptrón multicapa esta definida por un conjunto de capas ocultas, una capa de entrada y una de salida. No existen restricciones sobre la función de activación aunque en general se suelen utilizar funciones sigmoideas. La operación de un perceptrón multicapa con una única capa oculta puede ser resumida de la siguiente manera: zk =?w'kj yi -?'i =?w'kj f (?wjixi -?i) -?'i j j i (2.9) Este modelo es el más utilizado en la actualidad. El espectro de aplicaciones del perceptrón multicapa es muy amplio lo que hace muy difícil enumerar sus aplicaciones más relevantes. Sin embargo, podemos mencionar algunas áreas de aplicación: • • • Codificación de información Traducción de texto en lenguaje hablado Reconocimiento óptico de caracteres (OCR) La popularidad de este modelo de redes neuronales no se debe únicamente al éxito obtenido en aplicaciones prácticas del mismo. Existen demostraciones teóricas que permiten explicar el éxito de dichas aplicaciones. En [Funahashi, 1989] se demuestra que un perceptrón multicapa cuya función de activación sea no constante, acotada y monótona creciente es un aproximador universal de funciones. En [Hornik et alt, 1989] se llega a un resultado similar utilizando funciones de activación sigmoideas, no necesariamente continuas.

L. Federico Bertona Entrenamiento de redes neuronales 15 Entrenamiento de redes neuronales basado en algoritmos evolutivos

Capítulo 3: Entrenamiento de redes neuronales

En el contexto de las redes neuronales el aprendizaje puede ser visto como el proceso de ajuste de los parámetros libres de la red [Yao, 1995]. Partiendo de un conjunto de pesos sinápticos aleatorio, el proceso de aprendizaje busca un conjunto de pesos que permitan a la red desarrollar correctamente una determinada tarea. El proceso de aprendizaje es un proceso iterativo, en el cual se va refinando la solución hasta alcanzar un nivel de operación suficientemente bueno. La mayoría de los métodos de entrenamiento utilizados en las redes neuronales con conexión hacia delante consisten en proponer una función de error que mida el rendimiento actual de la red en función de los pesos sinápticos. El objetivo del método de entrenamiento es encontrar el conjunto de pesos sinápticos que minimizan (o maximizan) la función. El método de optimización proporciona una regla de actualización de los pesos que en función de los patrones de entrada modifica iterativamente los pesos hasta alcanzar el punto óptimo de la red neuronal.

3.1. Métodos de gradiente descendente

El método de entrenamiento más utilizado es el método del gradiente descendente. Este método define una función E(W) que proporciona el error que comete la red en función del conjunto de pesos sinápticos W. El objetivo del aprendizaje será encontrar la configuración de pesos que corresponda al mínimo global de la función de error, aunque en muchos casos es suficiente encontrar un mínimo local lo suficientemente bueno [Cauwenberghs, 1993]. El principio general del método es el siguiente: dado un conjunto de pesos W(0) para el instante de tiempo t=0, se calcula la dirección de máxima variación del error. La dirección de máximo crecimiento de la función E(W) en W(0) viene dado por el gradiente ?E(W). Luego, se actualizan los pesos siguiendo el sentido contrario al indicado por el gradiente ?E(W), dirección que indica el sentido de máximo decrecimiento [Defalco, 1997]. De este modo se va produciendo un descenso por la superficie de error hasta alcanzar un mínimo local. W(t +1) =W(t)-a?E(W) (3.1) donde a indica el tamaño del paso tomado en cada iteración, pudiendo ser diferente para cada peso e idealmente debería ser infinitesimal. El tamaño del paso es un factor importante a la hora de diseñar un método de estas características. Si se toma un paso muy chico el proceso de entrenamiento resulta muy lento, mientras que si el tamaño del paso es muy grande se producen oscilaciones en torno al punto mínimo.

16 Entrenamiento de redes neuronales L. Federico Bertona Entrenamiento de redes neuronales basado en algoritmos evolutivos

3.2. El algoritmo Backpropagation

El algoritmo backpropagation es el método de entrenamiento más utilizado en redes con conexión hacia delante. Es un método de aprendizaje supervisado de gradiente descendente, en el que se distinguen claramente dos fases: primero se aplica un patrón de entrada, el cual se propaga por las distintas capas que componen la red hasta producir la salida de la misma. Esta salida se compara con la salida deseada y se calcula el error cometido por cada neurona de salida. Estos errores se transmiten hacia atrás, partiendo de la capa de salida, hacia todas las neuronas de las capas intermedias [Fritsch, 1996]. Cada neurona recibe un error que es proporcional a su contribución sobre el error total de la red. Basándose en el error recibido, se ajustan los errores de los pesos sinápticos de cada neurona.

3.2.1. Deducción del algoritmo Backpropagation

El algoritmo propone una actualización iterativa de los pesos de la siguiente manera: W(t +1) =W(t)+ ?W(t) (3.2) Si tomamos una variación proporcional al gradiente de una función de error E(W) tenemos que: W(t +1) =W(t)-a?E[W(t)] (3.3) Como se explico anteriormente el primer paso de este algoritmo consiste en propagar hacia delante un patrón de entrada Xp y obtener la salida de la red Yp. La salida de la neurona i viene dada según su estado de activación. Si consideramos la función de salida identidad tenemos que yi(t) = Fi(ai(t)) = ai(t) (3.4) Siendo ai(t) = fi(hi(t)) (3.5) La regla de propagación más simple y utilizada consiste en realizar una suma de las entradas ponderadas con sus pesos sinápticos correspondientes. hi(t) =?wij *x j(t) j (3.6) Se compara la salida obtenida Yp con la salida deseada Dp, obteniéndose un error que viene dado por

? = k 1(d pk – y pk)2 ?e Entrenamiento de redes neuronales basado en algoritmos evolutivos 17 ep = 1 M 2 (3.7) donde k es el índice de neurona para las neuronas de la última capa, y M el total de neuronas de la misma. El error total de la red esta dado por p e = P

p=1 P (3.8) siendo p el índice de ejemplo, y P el numero total de ejemplos. De acuerdo a la ecuación (3.3) la variación de los pesos sinápticos será proporcional al gradiente de la función de error: ?ep ?wji ?wji = -a (3.9) Si aplicamos la regla de la cadena a (3.9) obtenemos que ?ep ?hj ?hj ?wji = ?ep ?wji (3.10) La ecuación (3.10) expresa la derivada del error en función de dos derivadas. La derivada del error respecto al potencial resultante hj indica como varia el error al variar la entrada de la neurona j, mientras que la derivada con respecto al peso sináptico wji indica como varia la entrada de la neurona j al variar el peso de la conexión que va desde la neurona i hasta la neurona j. El segundo termino de la expresión (3.10) lo podemos expresar a partir de la ecuación (3.6) de la siguiente manera = y pi = ?hj ?wji ??wjiy pi i ?wji (3.11) Si escribimos al primer término de la ecuación (3.10) como = -d pj ?ep ?hj (3.12) tenemos que = -dp j y pi ?ep ?wji (3.13) y por lo tanto la ecuación (3.9) queda expresada de la siguiente manera

L. Federico Bertona Entrenamiento de redes neuronales

= -? ? ?ep ?y pj ? ??y ?hj ? ? ?(d pj – y pj)2 =?? k ? ?hk ?y pj ? ? Entrenamiento de redes neuronales basado en algoritmos evolutivos 18 Entrenamiento de redes neuronales L. Federico Bertona ?wji = -ad pj y pj (3.14) Para calcular el valor de delta se vuelve a aplicar la regla de la cadena ? ? pj ?ep ?hj d pj = – (3.15) El cálculo del segundo término de la ecuación (3.15) es simple si observamos las ecuaciones (3.4) y (3.5) ' = f j(hj) ?f j(hj) ?hj = ?y pj ?hj (3.16) sin embargo, para el cálculo del primer término de la ecuación (3.15) es necesario distinguir entre dos casos diferentes.

• La neurona j es una neurona de salida

En este caso podemos obtener el segundo término a partir de la ecuación (3.7) ya que el subíndice j es igual al subíndice k = -(d pj – y pj) ?y pj ? = ?ep ?y pj 1 M 2 j=1 (3.17) Así, la variación de los pesos de una conexión que va hacia la capa externa de la red se calcula como: ' ?wji =a(d pj – y pj) f j(hj)y pi (3.18) • La neurona j es una neurona oculta

En este caso es necesario aplicar nuevamente la regla de la cadena ? ? ??ep ?hk ? ?ep ?y pj (3.19) Donde k es el subíndice de las neuronas que pertenecen a la próxima capa. La ecuación (3.19) la podemos reescribir utilizando la ecuación (3.6)

? =?? ? ?? ??wkj y pj ? ?? ? =?? ? ? wkj ? ? siendo dpj = ?? ???dpkwkj ? f j(hj ) Entrenamiento de redes neuronales basado en algoritmos evolutivos L. Federico Bertona Entrenamiento de redes neuronales 19 ? ? ? ?? ? j ?? ??ep

? ?y pj ? k ? ?hk ? ??ep k ? ?hk ? ?ep ?y pj (3.20) y por la ecuación (3.12) tenemos que ?ep ?y pj =?-d pkwkj = -?d pjwkj k k (3.21) Así, la variación de los pesos de una conexión que va desde una capa hacia otra capa de la red que no sea la externa se calcula como: ' ?wji =a?(d pkwkj)f j(hj)y pi k (3.22) En la implementación del algoritmo, se toma una amplitud de paso que viene dado por la tasa de aprendizaje (a). A mayor tasa de aprendizaje el proceso será más rápido. Sin embargo, si la tasa de aprendizaje es muy alta puede dar lugar a oscilaciones en torno a un mínimo local. Es posible disminuir el impacto de dichas oscilaciones mediante la adición de un momento (ß), quedando la expresión (3.14) expresada de la siguiente manera: ?wji(t +1) =ad pj y pj + ß?wji(t) (3.23) si j es una neurona de salida

si j es una neurona oculta ' De esta manera el momento ß determina el efecto en el instante t+1 del cambio de los pesos realizado en el instante t. Con este momento se consigue la convergencia de la red en menor numero de iteraciones, ya que si la modificación de los pesos en los instantes t y t+1 es en la misma dirección, entonces el descenso por la superficie de error en t+1 es mayor. En cambio, si la modificación en los pesos en los instantes t y t+1 se produce en direcciones opuestas, el paso que se da en t+1 es más pequeño, lo que es adecuado, ya que esto significa que se a pasado por un mínimo. Resumiendo, el algoritmo backpropagation queda expresado de la siguiente manera: wji(t +1) = wji(t)+[adpj y pj + ß?w ji(t)] ?(d pj – y pj )f j(hj ) ? ? ' ?? k ?

3.2.2. Modos de entrenamiento

?e 20 Entrenamiento de redes neuronales L. Federico Bertona Entrenamiento de redes neuronales basado en algoritmos evolutivos

Durante la aplicación del algoritmo backpropagation, el aprendizaje se produce mediante la presentación sucesiva de un set de entrenamiento. Cada presentación completa al perceptrón multicapa del set de entrenamiento se denomina epoch. Así, el proceso de aprendizaje se repite epoch tras epoch hasta que los pesos sinápticos se estabilizan y la performance de la red converge a un valor aceptable. La forma en que se actualizan los pesos sinápticos da lugar a dos modos de entrenamientos distintos, cada uno con sus ventajas y desventajas. •

• Modo Secuencial

En este modo de entrenamiento la actualización de los pesos sinápticos se produce tras la presentación de cada ejemplo de entrenamiento [Yao, 1993a], de allí que también es conocido como modo por patrón. Si un set de entrenamientos posee N ejemplos, el modo secuencial de entrenamiento tiene como resultado N correcciones de pesos sinápticos durante cada epoch.

Modo Batch

En este modo de entrenamiento la actualización de los pesos sinápticos se produce una única vez, tras la presentación de todo el set de entrenamiento. Para cada epoch se calcula el error cuadrático medio (3.8) producido por la red. La variación de los peso sinápticos, para un set de entrenamiento de N ejemplos, se puede calcular a partir de las ecuaciones (3.7), (3.8) y (3.9) como: = – j ?e j ?wji ?e ?wji N

n=1 a N ?wji = -a (3.24) Luego, la derivada podemos definirla de la misma manera que la definimos previamente.

Si los patrones de entrenamiento se presentan a la red de manera aleatoria, el modo de entrenamiento secuencial convierte a la búsqueda en el espacio de pesos en estocástica por naturaleza, y disminuye la probabilidad de que el algoritmo backpropagation quede atrapado en un mínimo local. Sin embargo, la naturaleza estocástica del modo de entrenamiento secuencial dificulta el establecimiento de condiciones teóricas para la convergencia del algoritmo. Por su parte, el uso del modo de entrenamiento batch provee una estimación precisa del vector gradiente, garantizando de esta manera la convergencia hacia un mínimo local.

3.2.3. Aceleración del aprendizaje

Como se menciono previamente las redes el algoritmo backpropagation ha sido utilizado con éxito en gran cantidad de aplicaciones. Sin embargo, el éxito

L. Federico Bertona Entrenamiento de redes neuronales 21 Entrenamiento de redes neuronales basado en algoritmos evolutivos

y la velocidad de convergencia de este mecanismo de entrenamiento tienen un alto grado de dependencia de la configuración del mismo. Por ello se han realizado una serie de métodos que permiten mejorar significativamente la performance del algoritmo. •

•

•

•

•

•

• Modo de actualización. La actualización secuencial es más rápida computacionalmente y demanda menos recursos que la actualización batch. Esto es especialmente cierto cuando el set de datos es grande y altamente redundante [Chinrungrueng, 1993].

Set de datos. La calidad del set de datos es un factor muy importante a tener en cuenta. Cada ejemplo presentado a la red debe cumplir con las siguientes dos premisas:

o Maximizar el error de entrenamiento o Maximizar la información

Presentación de los ejemplos. El modo en que se presentan los ejemplos es otro factor importante a tener en cuenta. La aleatorización del orden en que se presentan los ejemplos en los distintos epochs evita que los resultados se vean distorsionados por el orden de los ejemplos

Función de activación. El uso de una función de activación adecuada puede acelerar notoriamente el tiempo de entrenamiento. El uso de funciones antisimétricas en general produce mejores tiempos que el uso de funciones no simétricas.

Valores objetivos. La selección de los valores objetivos debe hacerse de acuerdo a la función de activación seleccionada. Una técnica que permite acelerar el tiempo de aprendizaje es desplazar el valor objetivo del valor máximo de la función. El algoritmo backpropagation tiende a saturar las neuronas ocultas cuando el valor objetivo es igual al máximo de la función de activación. Cuando esto sucede se produce el efecto de parálisis, lo que produce un aumento en el tiempo total de entrenamiento. Desplazando el valor objetivo un offset e del valor máximo de la función se reduce el riesgo de que las neuronas ocultas se saturen.

Normalización de las entradas. Si bien el algoritmo backpropagation no exige que los valores de entrada a la red se encuentren normalizados, esta es una buena técnica para acelerar los tiempos de entrenamiento [Bishop, 1996]. La normalización de las entradas debe realizarse de manera tal que el valor medio de la misma se encuentre cercano a cero.

Preprocesamiento de los ejemplos. Se aplica en aquellos casos en que un atributo toma un conjunto discreto de valores. Si un atributo sólo puede tomar N valores diferentes, la entrada de la red puede

22 Entrenamiento de redes neuronales L. Federico Bertona Entrenamiento de redes neuronales basado en algoritmos evolutivos

subdividirse en N entradas, cada una de las cuales representa a una clase. Cada una de estas entradas ahora puede tomar dos valores, verdadero o falso. Esta técnica puede ayudar a mejorar los tiempos de entrenamiento de la red neuronal

3.3. Generalización

Una vez finalizada la fase de aprendizaje, la red puede ser utilizada para realizar la tarea para la que fue entrenada. Una de las principales ventajas que posee este modelo es que la red aprende la relación existente entre los datos, adquiriendo la capacidad de generalizar conceptos. De esta manera, una red neuronal puede tratar con información que no le fue presentada durante de la fase de entrenamiento [Chinrungrueng, 1988]. Cuando se evalúa una red neuronal no sólo es importante evaluar si la red ha sido capaz de aprender los patrones de entrenamiento. Es imprescindible también evaluar el comportamiento de la red ante patrones nunca antes vistos. Esta característica de las redes neuronales se la conoce como capacidad de generalización y es adquirida durante la fase de entrenamiento [Sanger, 1989]. Es necesario que durante el proceso de aprendizaje la red extraiga las características de las muestras, para poder luego responder correctamente a nuevos patrones. De lo dicho anteriormente surge la necesidad de evaluar durante la fase de entrenamiento dos tipos de errores. El error de aprendizaje, que indica la calidad de la respuesta de la red a los patrones de entrenamiento, y el error de generalización, que indica la calidad de la respuesta de la red a patrones nunca antes vistos. Para poder obtener una medida de ambos errores es necesario dividir el set de datos disponibles en dos, el set de datos de entrenamiento, y el set de datos de evaluación. El primero se utiliza durante la fase de entrenamiento para que la red pueda extraer las características de los mismos y, mediante el ajuste de sus pesos sinápticos, la red logre una representación interna de la función. El set de evaluación se utiliza para evaluar la capacidad de generalización de la red. La causa más común de la perdida de capacidad de generalización es el sobreaprendizaje. Esto sucede cuando la cantidad de ciclos de entrenamientos tiende a ser muy alta. Se observa que la respuesta de la red a los patrones de entrenamiento es muy buena mientras que la respuesta a nuevos patrones tiende a ser muy pobre. Al aumentar el número de ciclos la red tiende a sobreajustar la respuesta a los patrones de entrenamiento, a expensas de una menor capacidad de generalización. La figura 3.1 muestra una situación idealizada de lo dicho anteriormente. En la misma se observa que en un determinado punto la red comienza a perder capacidad de generalización como consecuencia del sobreaprendizaje de los patrones de entrenamiento.

Entrenamiento de redes neuronales basado en algoritmos evolutivos 23 Figura 3.1. Generalización. Situación idealizada

En la figura 3.2 se muestra una situación más real del mismo caso. A medida que transcurre el proceso de aprendizaje se obtienen varios mínimos sobre el conjunto de evaluación. Existen diversas técnicas de parada temprana (early stopping) aunque en la mayoría de los casos se deja que el proceso de aprendizaje avance hasta alcanzar una cota de error razonable, guardando periódicamente las distintas configuraciones intermedias para luego seleccionar la de menor error de evaluación. Figura 3.2. Generalización. Situación real

L. Federico Bertona Entrenamiento de redes neuronales

24 Entrenamiento de redes neuronales L. Federico Bertona Entrenamiento de redes neuronales basado en algoritmos evolutivos

En ocasiones la perdida de capacidad de generalización se produce por el uso excesivo de neuronas ocultas en la red neuronal. Esto hace que la red tienda a ajustar con mucha exactitud los patrones de entrenamiento, evitando que la red extraiga las características del conjunto. Este problema se ve agravado cuando los patrones de entrenamiento poseen ruido, ya que la red ajusta también el ruido de los mismos.

L. Federico Bertona Algoritmos genéticos 25 Entrenamiento de redes neuronales basado en algoritmos evolutivos

Capítulo 4: Algoritmos genéticos

Los algoritmos genéticos son una técnica de resolución de problemas inspirada en la naturaleza. Están basados en el principio darwiniano de reproducción y supervivencia de los individuos más aptos [Beasley et alt, 1993]

4.1. Introducción

La computación evolutiva es la rama de la inteligencia artificial que engloba a todas aquellas técnicas de resolución de problemas basadas en la evolución de las especies y la supervivencia del más apto [Joglekar y Tungare, 2001]. Dentro de ella encontramos a los algoritmos genéticos (genetic algorithms), las estrategias evolutivas (evolution strategies) y la programación evolutiva (evolutionary programming) entre otros [Yao, 1996]. Las técnicas evolutivas han sido aplicadas con éxito a distintos tipos de problemas como optimización de parámetros, planificación de tareas, diseño, etc. [Whitley, 2002] Estos algoritmos codifican las posibles soluciones en estructuras llamadas cromosomas (o individuos). A un conjunto de individuos se lo conoce como población y representan un conjunto de soluciones posibles al problema [Cantú-Paz, 1997]. Mediante la aplicación de un conjunto de operadores genéticos sobre la población se va refinando gradualmente la solución hasta alcanzar un resultado que cumpla con las condiciones requeridas. El primer paso en la aplicación de un algoritmo genético consiste en la generación de una población inicial. En general esta población se genera de manera aleatoria, y el tamaño de dicha población (la cantidad de individuos que la compone) es un parámetro que se define durante el diseño del algoritmo genético. Una vez generada esta población se debe evaluar la aptitud (fitness) de cada individuo [Deb, 2004]. El operador de selección es el encargado de decidir cuales individuos contribuirán en la formación de la próxima generación de individuos. Este mecanismo simula el proceso de selección natural, mediante el cual sólo los individuos más adaptados al ambiente se reproducen [Coello Coello, 2002]. El mecanismo de selección forma una población intermedia, que esta compuesta por los individuos con mayor aptitud de la generación actual. La siguiente fase del algoritmo consiste en la aplicación de los operadores genéticos. El primero de ellos es la cruza, y su función es recombinar el material genético. Se toman aleatoriamente dos individuos que hayan sobrevivido al proceso de selección y se recombina su material genético creando uno o más descendientes, que pasan a la siguiente población. Este operador se aplica tantas veces como sea necesario para formar la nueva población. El último paso consiste en la aplicación del operador de mutación. Este operador, que en general actúa con muy baja probabilidad, modifica algunos genes del cromosoma, posibilitando de esta manera la búsqueda de soluciones alternativas.

26 Algoritmos genéticos L. Federico Bertona Entrenamiento de redes neuronales basado en algoritmos evolutivos

Una vez finalizado el proceso de selección, cruza y mutación se obtiene la siguiente generación del algoritmo, la cual será evaluada, repitiéndose el ciclo descripto previamente. Tras cada iteración la calidad de la solución generalmente va incrementándose, y los individuos representan mejores soluciones al problema [Forrest 1996]. Al algoritmo genético detallado anteriormente se lo conoce como algoritmo genético canónico y es la forma más utilizada. Sin embargo, en algunas implementaciones particulares de algoritmos genéticos se puede agregar nuevos operadores. En todos los casos, la forma en que se implementen los operadores variará de acuerdo a las características propias del problema.

4.2. El cromosoma

Los algoritmos genéticos trabajan manipulando cromosomas, que son estructuras que codifican las distintas soluciones de un determinado problema. La forma en que se codifican los cromosomas es dependiente de cada problema en particular, y suele variar de problema en problema. Un cromosoma esta compuesto por un conjunto de genes. Cada gen representa una característica particular del individuo y ocupa una posición determinada en el cromosoma, llamada locus. A cada uno de los valores que puede tomar un gen se lo conoce como alelo. [Ilachinski, 1997] Es importante destacar dos conceptos que muchas veces suelen confundirse: genotipo y fenotipo. El genotipo es el conjunto de genes de un individuo, la descripción genética del individuo. El fenotipo es la forma en que se expresa el genotipo, como resultado de la interacción con su entorno [Morrison, 1998]. La morfogénesis es el proceso de decodificar el genotipo para producir un fenotipo [Biondi y Michel, 1995]. Una cuestión a resolver cuando se diseñan algoritmos evolutivos es la forma de codificar los genes. Estos se pueden representar como cadenas binarias, números enteros, números reales, etc. [Whitley, 2001]. En general se utilizan las cadenas binarias por varios motivos: •

•

• Cualquier parámetro se puede codificar como una cadena de bits. Una cadena de bits permite expresar valores booleanos, enteros, reales, etc.

La codificación binaria se puede ajustar a cualquier problema. Por este motivo la mayor parte de los trabajos teóricos se basa en este esquema de codificación. El uso de cadenas de bits permite contar con gran cantidad de herramientas de análisis.

Las cadenas de bits son fáciles de manipular. El desarrollo de operadores genéticos es simple y eficiente. Sin embargo, las características propias del problema podrían llevar a la utilización de otro esquema de codificación. En dicho caso será necesario desarrollar operadores genéticos que se adapten al esquema seleccionado.

? f L. Federico Bertona Algoritmos genéticos 27 Entrenamiento de redes neuronales basado en algoritmos evolutivos

En lo que sigue de este capítulo se supone el uso de cadenas binarias, debido a que estas son más fáciles de comprender.

4.3. Evaluación y aptitud

El uso de los conceptos de función de evaluación y función de aptitud se suelen utilizar como sinónimos. Sin embargo, ambos conceptos son diferentes, y es conveniente hacer una distinción entre ellos. La función de evaluación, o función objetivo, provee una medida de la performance de conjunto de parámetros. Indica que tan buena es la solución obtenida tras la aplicación de un conjunto de parámetros, independientemente de la aplicación de esta función sobre otro conjunto de parámetros [Whiltey, 1994]. En general, esta medida se obtiene tras la decodificación de un cromosoma en el conjunto de parámetros que representa. Por su parte, la función de adaptación siempre esta definida con respecto al resto de los individuos de la población. Indica que tan buena (o mala) es una solución comparada con el resto de las soluciones obtenidas hasta el momento. El valor obtenido por esta función se traduce, tras la aplicación del operador de selección, en oportunidades de reproducción. Aquellos que tengan mayor aptitud tendrán mayores posibilidades de reproducirse y transmitir su material genético a la próxima generación. En el algoritmo genético canónico, la función de adaptación se define como i i F =

f = fi f

N

i=1 N (4.1)

(4.2) donde fi es el valor de la función de evaluación para el cromosoma i

4.4. Población

Los algoritmos genéticos trabajan sobre una población de individuos [Bäck, 1992], donde cada uno de los cuales representa una posible solución. La población es un concepto muy importante en los algoritmos genéticos y existen dos cuestiones fundamentales a resolver: como generar la primera población, y cual debe ser el tamaño de la población. La población inicial debe poseer la mayor diversidad posible. Idealmente, la población inicial debería contener todos los posibles valores (alelos) que pueda tomar un gen. De esta manera se aseguraría una exploración completa del espacio de búsqueda. En la práctica, esta situación no suele ser factible por lo que la primera población se genera comúnmente de manera azarosa, asignándole aleatoriamente a cada gen uno de los posibles alelos. De esta manera se asegura la diversidad de alelo por gen. En algunos casos se pueden

R = Random(0,?Fi) ?Fi = R