Implementación de compuerta XOR en Perceptrón PDF

Preview

Summary

Se busca explicar el funcionamiento del perceptrón y cómo implementar la compuerta XOR usando algebra booleana, etc. y su funcionamiento...

Description

Objetivos: El objetivo de este último proyecto es investigar, entender y familiarizarse con el concepto del perceptrón para que después se pueda implementar la compuerta XOR y comprobar su funcionamiento y comportamiento en EDA Playground en VHDL y el EPWave. Metas: Mediante la investigación aprende qué es un perceptrón, cómo es que se puede implementar la compuerta XOR, cómo entrenar el perceptrón y finalmente comprobarlo en EDA Playground. Especificaciones técnicas: • • • • • • •

Investigación sobre perceptrones Algebra booleana. Tablas de verdad Entrenar al perceptrón Compuertas lógicas VHDL EPWave

Justificación del proyecto: Esta práctica se realizó con el fin de aprender cómo se pueden elaborar las redes neuronales de una forma matemática como lo son los perceptrones, ya que esto es una herramienta usada para solucionar problemas de todo tipo de una forma más eficiente. Desarrollo del proyecto: En la investigación sobre los perceptrones se pudo recabar lo siguiente, primero se muestra como es una neurona biológica y sus partes para poder entender cómo se lleva a cabo el proceso de la información y como sería la representación matemática de esta. Núcleo

Terminales del Axón

Dendritas

Imagen 1: Representación de neurona biológica con sus partes

Las dendritas, que son las ramificaciones alrededor del núcleo, son las que se encargan de recibir la información que entra de otra neurona. Por lo que podemos decir que esta parte de la neurona es la entrada de la información y que será procesada por el núcleo, donde se lleva a cabo una serie de activaciones que es donde se permite o no, transmitir la información por el Axón. Una vez transmitido, la información sale por las terminales del Axón. Con esto se puede elaborar un pequeño esquema de cómo funciona una neurona y tomarlo como referencia para el perceptrón.

Entrada

Transmisión de información

Salida

Imagen 2: Representación gráfica del proceso de una neurona Si podemos observar el diagrama de la imagen 2, se puede observar el parecido con una compuerta (entrada y salida) y la parte de transmisión de información es donde verificamos cuando las entradas están en alto o en bajo para saber cuál será la salida. Una vez comprendido esto, podemos afirmar y comprobar que esta neurona puede ser representada matemáticamente, y es aquí donde entra el termino perceptrón. Se creó el perceptrón como una forma de recrear las redes neuronales del cerebro del ser humano, ya que este a diferencia de una computadora podía hacer varias tareas simultáneamente, cosa que las computadoras no pueden porque son secuenciales. Fue entonces que McCulloch y Pitts hicieron los modelos conexionistas en 1943 definiendo formalmente la neurona como una maquina binaria con entradas y salidas. Existen muchos otros científicos que hicieron muchas aportaciones a esta idea, pero principalmente fueron McCulloch y Pitts quienes comenzaron con este proyecto porque propusieron el diagrama y las ecuaciones de del perceptrón. La ecuación propuesta fue: 𝑁

𝐼 = ∑ 𝑤𝑖 𝑥𝑖 = 𝑤1 𝑥1 + 𝑤2 𝑥2 + ⋯ + 𝑤𝑁 𝑥𝑁 𝑖=1

Donde: 𝐼 = salida,

𝑥𝑖 = 𝑒𝑛𝑡𝑟𝑎𝑑𝑎𝑠,

𝑤𝑖 = 𝑝𝑒𝑠𝑜𝑠 𝑑𝑒 𝑙𝑎 𝑒𝑛𝑡𝑟𝑎𝑑𝑎

Donde, si la ecuación da como resultado un valor mayor o igual que cero entonces la señal de salida será 1, pero si el valor es menor que cero, entonces la señal de salida será 0. Y con esto el diagrama sería el siguiente:

Imagen 3: Diagrama de perceptrón según la neurona biológica Ahora bien, en este parcial se busa la implementación de la compuerta XOR con un perceptrón, para poder hacer esto se encontró que se tiene que aplicar un proceso de entrenamiento de un perceptrón para poder reconocer la compuerta requerida. Para la implementación de compuerta XOR con perceptrón primero se analiza el comportamiento de la compuerta deseada para después entrenar el perceptrón. A 0 0 1 1

B XOR 0 0 1 1 0 1 1 0

A B Gráficamente mapa-K

0

1

0

1

1

0

0 1

Imagen 4: tabla de verdad y mapa-K de la compuerta XOR Como se puede observar en el mapa de Karnaugh, la expresión obtenida seria: 𝐴 𝐴𝐵 + 𝐵 Y otro aspecto importante que se puede observar en el mapa-K es que la expresión resultante no es lineal, por lo que la compuerta XOR no puede ser representada por un perceptrón simple de una sola capa, será por un perceptrón multicapa. Por lo

que se debe buscar simplificar la expresión aplicando álgebra booleana para poder obtener la compuerta XOR en términos de compuertas básicas y después entrenar al perceptrón para cada una de las compuertas resultantes. 𝐴 𝐶𝑜𝑚𝑝𝑢𝑒𝑟𝑡𝑎 𝑋𝑂𝑅 = 𝐴𝐵 + 𝐵

 +𝐵  𝐵, esto se puede hacer porque el Entonces se le agrega a la expresión 𝐴𝐴 resultado de ambas multiplicaciones dará como resultado 0 sin afectará a la original.  𝐴 + 𝐴𝐴 + 𝐵 𝐵 𝐴𝐵 + 𝐵 Proseguimos a obtener factor común de A y de B, quedando la expresión siguiente  ) + 𝐵(𝐴𝐵 ) 𝐴(𝐴𝐵 Finalmente, se puede reescribir la expresión multiplicaciones negadas y juntándolas, obteniendo:

separando

𝐴𝑦𝐵

de

las

) (𝐴 + 𝐵)(𝐴𝐵 Y gracias a que se reformuló la expresión booleana de la XOR, ahora podemos notar que la nueva expresión está formada por las compuertas OR, AND y NAND. Una vez entendido esto procedemos a entrenar el perceptrón para cada una de estas compuertas. Para este entrenamiento se va a seguir un método de diseño formal del perceptrón el cual va a constar de la asignación de valores en la fórmula 𝑤𝑁 𝑋 + 𝑏 y observar en cuales valores se cumple el comportamiento original de cada una de las compuertas (OR, AND y NAND), para esto solo se tiene que observar si el resultado es mayor igual a cero entonces y=1 y y=0 si el resultado es menor que cero. 1. Entrenamiento del perceptrón de la compuerta OR Primero debemos entender su comportamiento y saber si es lineal, para esto usamos una tabla de verdad y lo observamos gráficamente. A 0 0 1 1

B OR 0 0 1 1 0 1 1 1

A 0

1

0

0

1

1

1

1

B Gráficamente mapa-K

Imagen 5: tabla de verdad y mapa-K de la compuerta OR Como podemos observar su comportamiento es lineal, por lo que solo falta entrenar al perceptrón. Para lograr entrenarlo y saber cuáles serán sus pesos y su error, vamos a usar la fórmula de comportamiento de un perceptrón mencionada anteriormente, la cual es:

𝑤1 𝐴 + 𝑤2 𝐵 + 𝑏.

Iniciamos a asignarle valores de 𝑤1 = 0; 𝑤2 = 0; 𝑏 = 0, una vez asignados los valores seguimos a sustituirlos en la formula. (0)𝐴 + (0)𝐵 + (0) Los valores que van a tener las variables A y B serán los de la tabla de verdad de la compuerta que se está entrenando, en este caso es la OR. Sustituyendo todo obtenemos que: (0)(0) + (0)(0) + (0) = 0 Al observar esto notamos que no se cumple la condición de que si 𝑦 = 0; 𝑠𝑖 → 𝑤𝑁 𝑋 + 𝑏 < 0, por lo que se hace un cambio para que la desigualdad se cumpla, así que se cambia el valor de b por -1 (0)(0) + (0)(0) + (−1) = −1 ∴ 𝑦 = 0 Ahora con esos valores se comporta correctamente y podemos seguir con la segunda fila de la tabla de verdad (los pesos y el error se quedan iguales a menos que se necesite hacer una corrección por si en algún momento deja de comportarse como debería). (0)(0) + (0)(1) + (−1) = −1 ∴ 𝑦 = 0 Podemos ver que el comportamiento ya no es correcto porque el resultado de la formula debería dar un número mayor o igual que cero, por lo que debemos hacer una modificación en los valores de los pesos a 𝑤1 = 1; 𝑤2 = 1; 𝑏 = −1 y se sustituye nuevamente la fórmula. (1)(0) + (1)(1) + (−1) = 0 ∴ 𝑦 = 1 Y ahora si se cumple y podemos pasar a la tercera fila de la tabla de verdad. (1)(1) + (1)(0) + (−1) = 0 ∴ 𝑦 = 1 Se observa que el comportamiento es correcto, así que continuamos con la cuarta y última fila con los mismos valores de pesos y error. (1)(1) + (1)(1) + (−1) = 1 ∴ 𝑦 = 1 Como se puede notar el comportamiento es correcto y no es necesario hacer cambios, con lo que se puede concluir que el perceptrón de la compuerta OR funciona con los valores de entrenamiento: 𝑤1 = 1; 𝑤2 = 1; 𝑏 = −1 Básicamente este es el proceso de entrenamiento del perceptrón para una compuerta, esto se tiene que hacer para las otras compuertas básicas que

conforman a la compuerta XOR y tener los pesos y el error de cada una y poder elaborar el perceptrón de la XOR. 2. Entrenamiento del perceptrón de la compuerta AND Al igual que en el ejemplo anterior se debe entender el comportamiento de la compuerta AND para observar su comportamiento y proseguir al entrenado del perceptrón A 0 0 1 1

B AND 0 0 1 0 0 0 1 1

A

0

1

0

0

0

1

0

1

B Gráficamente mapa-K

Imagen 6: tabla de verdad y mapa-K de la compuerta AND Una vez observado su comportamiento, solo falta entrenar al perceptrón. Para poder entrenarlo y saber el valor de sus pesos y su error, se usa la fórmula de comportamiento de un perceptrón: 𝑤1 𝐴 + 𝑤2 𝐵 + 𝑏.

Igual que en el anterior, los valores que les vamos a asignar de inicio serán 𝑤1 = 0; 𝑤2 = 0; 𝑏 = 0 y se sustituirán en la formula de comportamiento de un perceptrón. (0)𝐴 + (0)𝐵 + (0) = 0

Como ya sabemos, los valores de A y B serán los valores de las entradas de la tabla de verdad y el resultante de 𝑤𝑁 𝑋 + 𝑏 debe ser mayor o igual a cero para que y=1 y menor a cero para que y=0. Entonces analizamos la primera fila y la sustituimos en la formula y obtenemos que: (0)(0) + (0)(0) + (0) = 0 Y nos damos cuenta de que el resultado es cero por lo que Y seria 1 lo cual según nuestra tabla de verdad es un comportamiento incorrecto, así que se debe hacer una modificación, en este caso se cambiará el error b por -1. (0)(0) + (0)(0) + (−1) = −1

Dándonos 𝑤1 𝐴 + 𝑤2 𝐵 + 𝑏 < 0 lo que nos da 𝑦 = 0, y de esta forma se cumple el comportamiento de la compuerta para las entradas 00, seguimos con a siguiente fila de la tabla de verdad y los mismos valores de pesos y error. (0)(0) + (0)(1) + (−1) = −1

La formula nos da como resultado -1 que es menor que cero, por lo que 𝑦 = 0 cumpliendo con el comportamiento de la compuerta AND. Podemos seguir con la tercera fila. (0)(1) + (0)(0) + (−1) = −1 Al igual que en los casos pasados, el comportamiento es correcto ya que el resultado es menor que cero por lo que 𝑦 = 0 y sigue cumpliendo con el comportamiento original de la compuerta AND. Seguimos con la cuarta fila. (0)(1) + (0)(1) + (−1) = −1 Aquí el comportamiento no es correcto porque el resultado debería ser mayor o igual a cero, entonces se tiene que hacer una modificación en los valores de los pesos por 𝑤1 = 1; 𝑤2 = 1 y sustituyendo nos da como resultado lo siguiente: (1)(1) + (1)(1) + (−1) = 1

Con esta modificación se cumple satisfactoriamente el comportamiento original de la compuerta AND. Al haber un cambio en el último renglón se tiene que revisar todos los casos de las filas para verificar que se siga cumpliendo. Con el primer renglón: (1)(0) + (1)(0) + (−1) = −1 Si se cumple el primer renglón. Ahora con el segundo renglón: (1)(0) + (1)(1) + (−1) = 0 En este caso ya no se cumple el comportamiento, por lo que se debe modificar de nuevo, se modifica el error por 𝑏 = 1.5 y nos queda lo siguiente: (1)(0) + (1)(1) + (−1.5) = −0.5 Con la modificación ya se cumple el comportamiento requerido y seguimos con la tercera fila, con los nuevos valores. (1)(1) + (1)(0) + (−1.5) = −0.5 Se cumple el comportamiento, seguimos con el ultimo renglón: (1)(1) + (1)(1) + (−1.5) = 0.5 Se cumple el comportamiento original, como es mas conveniente trabajar con números enteros, se multiplican los valores de los pesos y el error por dos y así tener valores enteros y no decimales, teniendo los siguientes valores: 𝑤1 = 2; 𝑤2 = 2; 𝑏 = −3 3. Entrenamiento del perceptrón de la compuerta NAND

Primero se debe entender el comportamiento de la compuerta que se requiere para entrenar el perceptrón, en este ultimo caso será la compuerta NAND que como ya sabemos esta compuerta es igual a la AND, pero negada.

A 0 0 1 1

B NAND 0 1 1 1 0 1 1 0

B Gráficamente mapa-K

A 0

1

0

1

1

1

1

0

Imagen 7: tabla de verdad y mapa-K de la compuerta NAND Como se puede observar, su comportamiento es lineal, por lo que solo se va a entrenar un perceptrón. Para poder entrenarlo y saber cuáles serán sus pesos y su error, se usa la fórmula de comportamiento de un perceptrón mencionada anteriormente. 𝑤1 𝐴 + 𝑤2 𝐵 + 𝑏. Empezamos igual que las anteriores, asignando los primeros valores de los pesos y el error: 𝑤1 = 0; 𝑤2 = 0; 𝑏 = 0 y los sustituimos en la fórmula para ver que se cumpla el comportamiento original de la compuerta. (0)𝐴 + (0)𝐵 + (0) = 0 Y empezamos a sustituir los valores de la primera fila de la tabla de verdad (0)(0) + (0)(0) + (0) = 0 Como podemos observar el resultado es mayor o igual a cero, por lo que 𝑦 = 1 y, por ende, el comportamiento es correcto y podemos continuar con la segunda fila de la tabla y con los mismos valores de los pesos y el error. (0)(0) + (0)(1) + (0) = 0 Igualmente se cumple el comportamiento ya que y=1 porque el resultado es mayor o igual a cero. Y seguimos con la tercera fila de la tabla de verdad. (0)(1) + (0)(0) + (0) = 0 También en esta tercera configuración se cumple el comportamiento original de la compuerta NAND y seguimos con la última fila. (0)(1) + (0)(1) + (0) = 0 Y se puede notar que el comportamiento es incorrecto, por lo que se deben modificar algunos valores. En este caso se modifican tanto los pesos como el error y nos quedan 𝑤1 = −1; 𝑤2 = −1; 𝑏 = 1.5

(−1)(1) + (−1)(1) + (1.5) = −0.5 Ya con esta modificación se cumple el comportamiento, pero como se modifico la ultima fila se debe revisar que funcione con las demás filas pasadas. (−1)(0) + (−1)(0) + (1.5) = 1.5 Si se cumple el primer renglón, seguimos con el segundo (−1)(0) + (−1)(1) + (1.5) = 0.5 También se cumple y seguimos con el tercer renglón (−1)(1) + (−1)(0) + (1.5) = 0.5 Igual que el anterior se cumple y finalmente con el cuarto renglón. (−1)(1) + (−1)(1) + (1.5) = −0.5 Y queda comprobado que si se comporta como debería originalmente e igual que en la compuerta AND, los valores se multiplican por dos ya que es más fácil trabajar con números enteros que con números decimales, dejando los pesos y el error con los siguientes valores: 𝑤1 = −2; 𝑤2 = −2; 𝑏 = 3 Estos procedimientos son los que se deben llevar a cabo para entrenar el perceptrón de cada una de las compuertas que forman a la compuerta XOR. Se recuerda que se tuvo que entrenar más de un perceptrón ya que la compuerta XOR no es lineal, por lo que se debe hacer un perceptrón con multicapas. Una vez calculado los pesos y los errores de cada compuerta podemos diseñar el perceptrón de la compuerta XOR añadiendo las subcapas de las compuertas que forman a la XOR. Para poder hacer esto se debe tomar en cuenta el orden en que se presentan en la expresión obtenida anteriormente. ) (𝐴 + 𝐵)(𝐴𝐵 Como se puede notar, están las compuertas OR y la compuerta NAND unidas por una compuerta AND, cada una con sus pesos y errores. Por lo que, la orden seria: 1. Perceptrón OR; 𝑤1 = 1; 𝑤2 = 1; 𝑏 = −1 2. Perceptrón NAND; 𝑤1 = −2; 𝑤2 = −2; 𝑏 = 3 3. Perceptrón AND; 𝑤1 = 2; 𝑤2 = 2; 𝑏 = −3 Ya que tenemos el orden y los valores correspondientes podemos realizar le diseño del perceptrón de la compuerta XOR.

b

b

𝑥1

AND

OR

XOR

𝑥2 NAND

Imagen 8: Representación esquemática del perceptrón XOR Una vez elaborado el esquema del perceptrón, se le tienen que agregar los valores de los pesos calculados anteriormente, se debe asegurar que los valores sean colocados correctamente donde deben ir.

b

b

𝑥1

𝑥2

-3

-1 3 1

OR

2

AND

XOR

-2 1 -2

2 NAND

Imagen 8: Representación esquemática del perceptrón XOR con valores de pesos y errores correspondientes. Una vez que ya tenemos el aspecto del perceptrón de forma esquemática, podemos empezar a hacer el diseño del perceptrón en el lenguaje VHDL. Para esto se investigó y se realizo el programa en EDA Playground para poder observar y verificar que el comportamiento final sea igual que el de la compuerta XOR El diseño en VHDL fue el siguiente:

Imagen 9: Diseño de perceptrón XOR en VHDL Primero se declararon las entidades que se mostraran en nuestro EPWave, las señales de entrada fueron: 𝑥1 𝑦 𝑥2 y las señales de salida fueron 𝑦; 𝑦1 ; 𝑦2 ; 𝑦3 donde 𝑦 = va a representar el comportamiento de la compuerta XOR, 𝑦1 = es la compuerta NAND, 𝑦2 = es la compuerta OR y 𝑦3 = es la compuerta AND. En la arquitectura es donde se implementan los valores de los pesos y los errores, aplicando la formula que se vio en el entrenamiento para cada perceptrón. Y así poder obtener el comportamiento de cada uno. Finalmente, en el testbench es donde se agregan los valores obtenidos en la parte teórica del reporte y se usa el analizador de ondas EPWave para comprobar que el comportamiento sea correcto y verificar que nuestro proceso teórico sea el correcto.

Imagen 10: EPWave del perceptrón XOR Como podemos observar el comportamiento de cada compuerta se cumple correctamente, por lo que podemos afirmar que nuestro perceptrón fue elaborado correctamente. Resultados logrados: Se logró elaborar correctamente el perceptrón de la compuerta XOR mediante un procedimiento de entrenamiento para cada una de las compuertas que conforman a la XOR (OR, AND y NAND) y se comprobó en EDA Playground. Conclusiones: En conclusión, investigamos y aprendimos a cerca de los perceptrones y cómo es que estas neuronas representadas matemáticamente es que funcionan. Y se implementó la compuerta XOR en este. En el proceso de implementación nos dimos cuenta de que el comportamiento de la compuerta XOR no es lineal, por lo que no bastaba con un perceptrón simple de una sola capa. Sino que, se implementó un perceptrón multicapa donde en cada una de ellas estaría un perceptrón para cada compuerta que conforma a la XOR. Esto se hizo mediante un procedimiento donde nosotros asignábamos los pesos y el error empezando desde cero y l uso de la fórmula de comportamiento de un perceptrón para poder verificar que el comportamiento de cada compuerta se cumpla. Aunque existe otro método para el calculo de los pesos y el error, el cual es un método donde se asignan valores predeterminados, preferí hacer el otra ya que se llega al mismo resultado y no es necesario buscar o tener que saber los valores predeterminados. Y finalmente se elaboró el código en EDA Playground. Bibliografía y referencias: Katz, R. H. (1993). Contemporary logic design. Addision-Wesley. Stephen, I. (1990). Perceptron-based learning algorithms. IEEE Transactions on neural networks, 50(2), 179. Tabares, H., Branch, J., & Valencia, J. (2006). Generación dinámica de la topología de una red neuronal artificial del tipo perceptron multicapa. Revista Facultad de Ingeniería Universidad de Antioquia, (38), 146-162....