Actividad de Programación 3: Algoritmo ID3

Medio Ambiente:
Nuestro medio ambiente será como un tipo calabozo con forma de laberinto (el cuál será dinámico), constará de una entrada y una salida Y tres tipos de agentes principales: buscador, guardián y espía. El agente buscador se encargará de buscar un objeto y huir hacia la salida, evitando lo más que pueda al agente guardián. El agente guardián se encargará de hacer rondas en el calabozo en diferentes zonas (mientras las va conociendo y aprendiendo) y en cuanto encuentre al agente buscador, seguirlo para capturarlo. El agente espía se encargará de ayudar al agente buscador para encontrar el objeto verdadero, indicándole dónde hay atajos e interfiriendo en las comunicaciones de los agentes guardianes (solo en el caso que exista más de un agente guardián). Puede que existan más buscadores y de ésta forma los agentes guardianes se confundirán.

En caso de que solo existiera una entrada, se tendría que conseguir el objeto único que podrá convertir la entrada en la salida, para esto, nuestro agente tendría que recordar el camino por el que vino, siempre tratando de evitar al agente guardia.

Existirán agentes guardias, los cuales estarán recorriendo todo el calabozo para conocer el terreno y estar haciendo guardia en algunas de las zonas del mismo. Dentro del calabozo existen diversos objetos, de los cuales hay uno que es el que le abrirá la puerta a la salida, pero hay objetos falsos, copias, que tratarán de confundir al agente buscador.

Actividad que aprende:
En este caso el agente aprenderá a moverse dentro del medio ambiente intentando no ser atrapado por los centinelas. Utilizando el algoritmo de ID3 este aprende en qué dirección moverse de acuerdo a la retroalimentación obtenida.



Patrones:
Los patrones de entrenamiento en este caso, se generan por 30 segundos a partir de que el programa corre. Los patrones cuentan con los siguientes datos:
a) [0, 1] Un valor booleano de si hay o no centinelas en su rango de visión.
b) [1 ,2, 3, 4] El valor de la dirección tomada para el movimiento.
c) [0, 1] Un valor booleano que determina si encontró un callejón sin salida o no en su camino.
d) [0, 1] Una evaluación de si la acción fue buena o mala.
Se escogieron estos valores ya que son los más importantes en este ambiente para poder moverse en el medio y cumplir la meta que se quiere aprender. Además de que son valores fáciles de evaluar para la utilización del algoritmo.

Los patrones se irán almacenando en un arreglo bidimensional.

Solución ID3:
i) Algoritmo utilizado:
a. ID3: Ya que fue interesante la implementación de este en el medio ambiente y porque es sencillo de comprender.
ii)
a. Aprendizaje: El número de patrones realmente no está definido ya que está delimitado por tiempo, en este caso se generan patrones, cada que el agente se mueve y que se repinta la pantalla durante 30 segundos. Terminando el lapso de 30 segundos el movimiento se determina de acuerdo al algoritmo.
b. Validación: En este caso no se utilizan patrones de validación ya que nosotros no tenemos control sobre el movimiento del agente, simplemente al ser movimientos aleatorios, el programa utiliza el árbol generado con los patrones de entrenamiento para ir evaluando paso por paso el movimiento del agente, en el caso de tener una retroalimentación buena sigue el camino, en caso de tener una retroalimentación mala, se mueve en dirección contraria.
c. Ejemplos:
iii) Este programa si funciona en tiempo real, ya que por eso se está corriendo por tiempo, durante un tiempo se entrena y todo lo que resta del tiempo está generando movimientos a partir de lo que aprendió con ID3 cada paso o movimiento que hace.
iv) No cuenta con overfitting ya que el movimiento del agente es aleatorio, entonces puede darse el caso de que muchos casos no estén considerados dentro del lapso de tiempo que se asignó para generar patrones de entrenamiento.
v) Mejorar el funcionamiento podría ser agregando más valores a los patrones de entrenamiento ya que en la forma que está ahorita sería una forma simple, pero en un ambiente más complicado podría llegar a no funcionar bien con tan pocos valores o patrones. También se podría aumentar el tiempo que genera patrones de entrenamiento.

Conclusiones:
Esta actividad nos ayudo a comprender mejor la forma en que se lleva a cabo la relación entre el árbol de decisiones generado por ID3 y el medio ambiente, llegando así a un aprendizaje. A la vez pudimos ver que no es un algoritmo muy complejo de programar, sino su dificultad está en adaptarse a un medio diferente por todas las variables que hay que tomar en cuenta, a la vez de que se deben decidir los patrones.
Probablemente la parte de la decisión de que valores utilizar para los patrones fue el más difícil ya que de esto dependía el funcionamiento completo del algoritmo.

Actividad ID3

Descripción del medio ambiente

En una playa, están naciendo varias tortugas, y para sobrevivir, deben de llegar al mar lo más rápido posible, sin embargo, puede que haya depredadores cerca queriendo alimentarse de ellas, lo que las hace más vulnerables. Las tortugas nacen a cierta distancia del mar, además de nacer con cierta velocidad propia y cierta resistencia a los ataques de los depredadores.

Descripción de la actividad que aprenderá el agente

Dadas las características de cada tortuga (su distancia al mar, si hay o no depredador cerca, su velocidad y su resistencia), el agente debe de decidir si una tortuga se salva sin ayuda de nadie, si es necesaria la intervención humana para salvarla o si es imposible salvarla.

Descripción detallada de los patrones

Un patrón está formado de la siguiente manera:

{ Distancia, Depredador, Velocidad, Resistencia} à ¿Se salva?

Donde:

Distancia mide si se encuentra entre 0-5 metros, 5-10 metros o más de 10 metros. Se eligió así para evitar que los patrones fueran continuos y se eligieron esos rangos porque creemos que son distancias que pueden hacer diferencia entre si la tortuga vive o no.

Depredador mide solamente si hay o no un depredador cerca de la tortuga, donde cerca se define dentro del área de sobrevivencia de la tortuga, que son de alrededor de 5 metros a la redonda. Nuevamente, creemos que este radio es el que puede hacer la diferencia entre si la tortuga sobrevive o no.

Velocidad, mide qué tan rápido se mueve la tortuga, y cae dentro de: Lento, Normal o Rápido.

Resistencia, mide que tanto la tortuga puede resistir a los ataques de los depredadores, y esta puede ser Alta, Media y Baja. Estos últimos dos atributos se discretizaron para poder trabajar con ellos y se escogieron ya que una tortuga rápida puede llegar al mar pese a estar lejos o viceversa, y ocurre similar con la resistencia.

Solución al problema

Elegimos utilizar ID3 porque es el que más se adapta a los patrones que creamos. Aunque utilizamos ciertos límites para no utilizar datos continuos, no utilizamos la poda del árbol que C4.5 ofrece, ya que consideramos el árbol generado no es tan grande como para necesitar la poda.

En cuanto a los patrones, debido a que sólo hay 54 patrones distintos para aprender, decidimos usar un conjunto de 20 patrones, 15 para aprendizaje y 5 para validación con el propósito de darle al programa una gran variedad de patrones distintos sin llegar a darle todos los existentes.

Ejemplos de patrones:

{5-10m, Hay depredador, Lento, Baja} à Muere

{0-5m, No hay depredador, Rápido, Alta} à Sobrevive solo

El programa es lo suficientemente rápido para ser utilizado en tiempo real, aunque debería de ser alimentado con datos reales obtenidos con la práctica y al momento de ser utilizado, que sea por alguien lo suficientemente rápido para crear los patrones.

Creemos que el programa no tiene overfitting porque no encontramos otro árbol que fuera más específico que el que nos dio el programa, además de que el porcentaje de patrones dados es considerablemente alto comparado con la totalidad.

El programa podría mejorarse si las diferentes posibilidades en las características fueran más específicas, de esa forma existirían más posibles patrones y el resultado podría ser más preciso.

Conclusiones

En conclusión, creemos que los programas de ID3 son buenos para clasificar patrones cuyas hipótesis pueden ser organizadas en forma de árbol, siempre y cuando no existan datos continuos. En cuanto a la programación, fue un poco más difícil que programas anteriores debido más que nada a la implementación dinámica del árbol.

Actividad de programación ID3 Biokterii

Breve descripción del medio ambiente.

El medio consiste una vez más en el interior de un cuerpo de un ser vivo (por tradición podemos decir que de un gato) en el que un virus debe aprender a reconocer a los diferentes tipos de células que existen dentro del dicho cuerpo. Existen tres tipos diferentes de células, unas de ellas son comestibles o de tipo Food, otras son aquellas que pueden atacar al virus o Enemy, por último nos encontramos con las células objetivo o de tipo Target. El virus deberá aprender, después de una muestra de 15 células, a determinar el tipo de las células que irán apareciendo y así poder sobrevivir dentro del cuerpo.

Descripción detallada de la actividad o acción que va a aprender tu agente.

El virus debe aprender a reconocer las células que irá encontrando dentro del cuerpo, para esto se basa en sus características físicas, es decir, su color, su forma, la dirección en la que rota y la figura que tiene la célula en su interior. Al comienzo se cuenta con una entrenamiento de 15 células, que el usuario puede acomodar en cualquiera de las tres categorías: Target, Enemy o Food. Es muy importante mencionar que dependiendo como el usuario haga esta clasificación, será la forma en que se realice el árbol de decisión.

Descripción detallada de los patrones obtenidos del medio ambiente para el entrenamiento. Explicar la razón por la que se escogieron cada uno de los atributos del patrón.

Como se mencionó anteriormente, el virus se basa en las características físicas de las células para poder determinar su tipo. Siendo más específicos, las características son las siguientes:
Color: rojo, azul o verde
Forma externa: círculo, círculo con una bolita, círculo con una bolita llena, cuadrado o doble cuadrado
Giro: derecha o izquierda
Forma interna: ninguna, círculo lleno, círculo vacío, cuadrado lleno o cuadrado vacío

La razón por la que se eligieron estos atributos fue porque esas son las características que definimos para la célula. Al ser nuestro programa más interactivo, el usuario puede clasificar los diferentes tipos de células como mejor le parezca, basándose en las características que su intuición le diga. Claro está, que si dicha clasificación se hace de forma aleatoria y sin seguir un patrón es posible que no se obtenga una buena clasificación o los resultados deseados.


Solución planteada

La solución planteada es realizar un árbol con ID3 basándose en las características ya mencionadas

Video



Conclusiones

ID3 es muy interesante y realmente es como mágica la forma en que logra hacer las clasificaciones, la codificación tuvo algunas complicaciones pues en la clase vimos el método intuitivo para poder hacer la clasificación y no el método formal, así que eso tomó un poco de tiempo al momento de realizar el programa. Sin embargo el problema se prestó mucho para una buena realización del mismo, pues las características eran muy definidas y los valores eran totalmente discretos.