Método min-max

Un método estándar para que una computadora juegue un juego de 2 participantes, es hacer uso de un “árbol de juego”. En el mismo, cada nodo representa una posición posible en el juego, y los arcos representan una movida o jugada posible.

En este ejemplo se considerará un juego de damas en un tablero 4×4, para simplificar la explicación.

La siguiente imágen muestra el árbol de juego de nuestro tablero de damas. El primer nodo representa el punto inicial. Los nodos del segundo nivel representan las 3 posibles jugadas que realizamos “nosotros”, las fichas negras. Y los nodos del tercer nivel representan las posibles jugadas de las fichas rojas (en el gráfico, blancas).

arbolexpandido

Ahora supongamos que analizamos los hijos de cada nodo del tercer nivel para poder determinar qué pasa después. En el caso del hijo izquierdo del nodo que está a la izquierda, el negro está a punto de perder, por lo que le asignamos un -1. El del medio será un empate, por lo que le asignamos un 0. Y el derecho está a punto de ganar, por lo que le asignamos un 1. De la misma forma, asignamos números a cada nodo del tercer nivel.

A partir de estos numeros, podemos suponer que en el caso en que el negro mueva la ficha como el primer nodo del segundo nivel,  el rojo elegirá la opción que nos haga perder, es decir, el nodo con el valor -1. De esta forma asignamos el valor mínimo de los hijos a cada nodo del segundo nivel. Es decir, resultaría en una secuencia -1, 0, -1.

Por lo tanto, elegimos el nodo con el valor mayor, en este caso el del medio que tiene el valor 0. De esta forma en el peor de los casos empataríamos.

El procedimiento ilustrado es el conocido como método min-max. En 1962 Arthur Samuel escribió un programa que juega damas usando este método, y le pudo ganar a un campeón estatal.

Sin embargo, en juegos más complicados como el ajedrez, el método es ineficiente ya que el árbol crecería desmesuradamente. Para solucionar dicho problema, existen estrategias como el procedimiento alpha-beta, que permite reducir el numero de operaciones de forma significativa.

 

Fuente:

Dewdney, A. (2001). The (new) Turing omnibus : 66 excursions in computer science. New York: Henry Holt.

 

Teoría de Juegos

La teoría de juegos se se centra en el estudio estratégico de toma de desiciones. Específicamente, es el estudio de modelos matemáticos de conflicto o cooperación entre agentes racionales e inteligentes que toman desiciones. En un principio se desarrolló para entender la economía, pero se formalizó gracias a John von Neumman en 1944 y se popularizó gracias a su aplicación en estrategias militares. Un dato curioso es que ganó popularidad gracias a la película “Una mente brillante”, donde el protagonista es uno de los principales contribuidores a la teoría.

El dilema del prisionero es el ejemplo clásico para entender esta teoría. El mismo dice lo siguiente:

Dos personas cometieron un crimen, y se encuentran en dos cuartos separados en una estación policial. El fiscal se acerco a cada uno por separado y les dijo lo siguiente: “Si confiesas y delatas al otro prisionero, y el mismo no confiesa en contra tuyo, te dejaré ir. Si los dos confiesan, los enviaré a ambos a la prisión por 2 años. Si tu no confiesas y el otro prisionero si, te enviaré 3 años a prisión. Si ninguno confiesa, los enviare a ambos 1  año a prisión por un crimen menor”. ¿Cuál es la desicion más racional?

El problema se puede modelar en la siguiente tabla

Captura de pantalla 2014-04-26 a la(s) 21.04.57

La teoría de juegos nos da distintas estrategias para abordar dicho problema, por ejemplo el equilibrio de Nash nos indicaría que ambos prisioneros traicionarian al otro.

La teoría de juegos se ha convertido cada vez más importante en la lógica y la computación. Muchas teorías lógicas tienen de base la teoría, y la computación interactiva también se basa en la misma.

El internet ha propiciado el desarrollo de la teoría en el área computacional. Según Asuman Ozdaglar, una profesora de computación e ingeniería eléctrica en el MIT, antes los ingenieros en telecomunicaciones tenían que afrontar una serie de problemas técnicos, pero gracias al internet ahora tienen que lidiar con humanos. Debido a su naturaleza, la teoría de juegos permite encontrar el equilibrio entre partes en juegos, servicios p2p, y más.

En el siguiente post se ejemplificará la teoría en una estrategía aplicada a videojuegos.

Fuente:

Hardesty, L. (2013, junio 18). Game Theory Is No Longer Just for Economists. MIT Technology Review. Recuperado 27 de abril de 2014, a partir de http://www.technologyreview.com/article/515481/gaming-the-system/
Jackson, Matthew O., A Brief Introduction to the Basics of Game Theory (December 5, 2011). Available at SSRN: http://ssrn.com/abstract=1968579 or http://dx.doi.org/10.2139/ssrn.1968579

Clúster

Clúster o clustering son métodos estadísticos utilizados para agrupar casos que serán utilizados para medir diferentes variables o características.

Es el proceso de dividir un conjunto de datos en grupos mutuamente excluyentes de tal manera que cada miembro de un grupo esté lo más cercano posible al otro, al mismo tiempo que los grupos diferentes estén lo más alejados posible entre ellos.

No se puede definir con precisión que es un clúster. Por ello existen dos métodos de clustering los cuales son jerárquicos y no jerárquicos.

            Jerárquicos: Estar en un nivel condiciona la pertenencia a otro nivel jerárquico.

            No jerárquicos: Única partición de los datos mediante la optimización de alguna función adecuada.

El método de clúster es utilizado en casos cuando:

            Recopilar y clasificar a mano es costoso
            Los patrones cambian con el tiempo
            Es necesario encontrar características para crear clasificadores
 
Las aplicaciones que tiene en la vida real son en robótica para el aprendizaje y minería de datos buscando patrones que puedan ser expresados como un modelo.

En el siguiente video se puede ver cómo funciona el clúster

http://www.youtube.com/watch?v=yl_KZ86NT-A

Bibliografía:

Hartigan, John A. Clustering algorithms. John Wiley & Sons, Inc., 1975.

Jain, Anil K., and Richard C. Dubes. Algorithms for clustering data. Prentice-Hall, Inc., 1988.

Perceptrón (Red neuronal de una capa)

Perceptrón (Red neuronal de una capa)

El perceptrón simple es un tipo de red neuronal artificial desarrollado por Frank Rosenblatt en 1959. La razón de su auge en los años 60’s es que tiene capacidad de aprendizaje y reconocimiento de patrones linealmente separables. El perceptrón puede ser considerado como una neurona artificia, unidad de cálculo que intenta modelar el comportamiento de una neurona natural, como las que constituyen el cerebro humano. Es un algoritmo capaz de generar un criterio para hacer la selección de un grupo, entre un grupo de elementos más grandes.

El perceptrón puede ser entrenado para realizar alguna tarea mediante reglas de aprendizaje:
            Aprendizaje supervisado
            Aprendizaje no supervisado
            Aprendizaje por reforzamiento

Por si solo un perceptrón no tiene mucha utilizad, puesto que es como una neurona. Su capacidad y funcionalidad se genera cuando se relacionan con más para generar una red.

El perceptrón simple, dejó de ser considerado como una técnica útil, al igual que otros tipos de redes neuronales, cuando Marvin Minsky publicó un artículo en el cual expresaba las limitantes de estas técnicas.

De acuerdo a Marvin Minsky, el perceptrón simple sólo sirve para clasificar problemas linealmente separables, cosa que ya se podía hacer mediante métodos estadísticos, y de una forma mucho más eficiente. 

En el siguiente video se puede ver la aplicación de un perceptrón

http://www.youtube.com/watch?v=gKwar6nETqo

Bibliografía:
DEL, RIO, BONIFACIO MARTIN, and A. L. F. R. E. D. O. SANZ MOLINA. Redes neuronales y sistemas difusos. 2002.

Aldabas-Rubira, Emiliano. “Introducción al reconocimiento de patrones mediante redes neuronales.” IX Jornades de Conferències d’Enginyeria Electrònica del Campus de Terrassa, Terrassa, España, del 9 al 16 de Diciembre del 2002 (2002).

Árboles de Inducción ID3

Existen muchos tipos de árboles de inducción o decisión ya que el aprendizaje de árboles de decisión es una de las técnicas de inferencia inductiva más usadas, sin embargo los que nos interesan por sus aplicaciones en la Inteligencia Artificial son los arboles ID3.

Los árboles de inducción o decisión ID3 fueron desarrollados por J. Ross Quinlan en 1986. El modelo ID3 genera inducción mediante árboles de decisión. Este tipo de árboles son capaces de tomar  decisiones con una gran precisión. Utilizan un sistema de aprendizaje supervisado que aplica el algoritmo divide y vencerás, el cual se trata de reducir el problema en segmentos más pequeños para poder resolverlo con mayor facilidad, para poder hacer clasificaciones y realizar procesos inteligentes para automatizar tareas. La base del algoritmo es manera en la que se definen sus primeros nodos, por lo cual sería obsoleto si no se cuenta con un experto humano que los defina correctamente.

Las consideraciones que se deben al utilizar los árboles ID3 es que por cada iteración sobre el espacio sólo se puede contar con una hipótesis. Un ID3 básico no tiene la capacidad de reconsiderar su camino durante la búsqueda.

Bibliografía:
Moujahid, Abdelmalik, Inaki Inza, and Pedro Larranaga. “Tema 8. Árboles de Clasificación.”

Swarm Particle

Swarm Particle Optimization u optimización por enjambre de partículas OEP es un conjunto de algoritmos de optimización que resuelven problemas de manera natural como los seres vivos. Su origen fue gracias a los investigadores Kennedy y Ebarhart. Al principio la idea era utilizarlo para elaborar modelos de conductas sociales en grupos de animales. Después de comprobar su utilizad, terminó siendo un algoritmo para resolver problemas de optimización. En particular este tipo de algoritmos evocan la manera de resolver problemas de los enjambres de abejas.

OEP es utilizado cuando se tienen pocas o ninguna hipótesis sobre el problema que se quiere analizar, y se cuenta con muchas posibles soluciones. Para imaginar el funcionamiento se puede pensar en una caja que sólo tiene un agujero y se encuentra llena de partículas que quieren salir. Las partículas recorrerán el espacio de manera independiente siguiendo reglas matemáticas y recordando los espacios por los cuales han estado lo cual afectará su movimiento, y cuando una partícula encuentre la salida, esta les avisará a las demás y todas se desplazarán hacia el agüero. Por dicha razón se relaciona tanto a este tipo de algoritmos con enjambres de abejas. Cuando buscan algo, cada abeja hace su recorrido de manera individual, recordando cada cosa que va encontrando. Cuando encuentra lo mejor de lo que busca, le avisa al resto del enjambre.

Si bien se habla de que las OEP pueden ser aplicadas en problemas de optimización de manera general, son utilizados de mayor forma en optimizaciones de donde se cuenta con espacios de búsqueda continuos, un ejemplo sería encontrar la ruta óptima para la distribución de algún producto. Actualmente se están trabajando en adaptaciones para solucionar problemas discretos.

En el siguiente video se puede ver una demostración de cómo 40 mil partículas van recorriendo un espacio y se puede ver como a medida que lo conocen van alterando sus movimientos de tal manera que su espacio de inspección se va haciendo más chico a medida que tienden a la solución correcta.

http://www.youtube.com/watch?v=iM7VIxgLe5s

En el siguiente video se puede ver una aplicación real de OEP, donde se hace la réplica de una imagen.

http://www.youtube.com/watch?v=4bcJREArY_g

 Bibliografía:

Shi, Yuhui. “Particle swarm optimization: developments, applications and resources.” Evolutionary Computation, 2001. Proceedings of the 2001 Congress on. Vol. 1. IEEE, 2001.
Kennedy, J.; Eberhart, R. (1995). “Particle Swarm Optimization”. Proceedings of IEEE International Conference on Neural Networks Vol. IV: 1942–1948.

Máquinas Vectoriales

Mejor conocidas como Máquinas de Soporte Vectorial (MSV), se trata de un conjunto de algoritmos de aprendizaje supervisado. Es un plano en tres dimensiones, o conjunto de planos en tres dimensiones que se alberga en un espacio muy grande, que puede tender al infinito. Se utilizan para problemas de clasificación o regresión. Se utilizan planos tan grandes puesto que es conveniente que se tenga una buena separación entre los elementos para poderlos clasificar correctamente.

La característica más propia de las MSV es la separación óptima. Busca el plano tridimensional que tenga el mayor margen con los puntos que lo rodean. Existe una posibilidad infinita de hiperplanos para cada caso de MSV, pero la mejor solución siempre será la que permita un margen máximo entre los elementos de las diferentes categorías.

Las máquinas vectoriales cuentan con diversas limitantes que impiden su uso en el mundo real, como lo son más de dos variables predictores o situaciones donde los datos no pueden ser completamente separados.

Las máquinas vectoriales pueden llegar a ser parecidas a las redes neuronales (consultar entrada), sin embargo tienen muchas diferencias, siendo una de las más notorias el hecho de que entrenar a una MSV es muy eficiente, mientras que una red neuronal es muy costoso.

En el siguiente video se puede ver el funcionamiento de una máquina vectorial no lineal
https://www.youtube.com/watch?v=9wijQD8DPc4

En este video se puede ver el funcionamiento de una máquina vectorial no lineal que utiliza Kernel RBF
https://www.youtube.com/watch?v=UFnjV1E615I

Bibliografía:
Betancourt, Gustavo A. “Las máquinas de soporte vectorial (svms).” Scientia et Technica 1.27 (2005).

Pérez Cruz, Fernando. Máquina de vectores soporte adaptativa y compacta. Diss. Universidad Politécnica de Madrid, 2000.

Cadenas de Márkov

Para poder comenzar a hablar de cadenas de Márkov, es necesario primero definir un proceso estocástico. Es un concepto matemático que caracteriza sucesiones de variables aleatorias que son alteradas en función de otra variable. Cada variable aleatoria tiene una función de distribución de probabilidad. Entre dichas variables puede existir relación, o no.

Considerando dicha definición, ahora podemos decir que una cadena de Márkov es una modalidad de proceso estocástico, en el cual la probabilidad de un evento está directamente ligada con el evento anterior. Se puede decir que este tipo de cadenas tienen memoria, pues recuerdan el último evento y lo utilizan como condicional para eventos siguientes.

Las cadenas de Márkov se pueden dividir en homogéneas y no homogéneas, siendo las primeras las que sus cambios no están ligados con el tiempo.

Existen distintos tipos de cadenas de Márkov

  • Cadenas irreducibles
  • Cadenas positivo-recurrentes
  • Cadenas regulares
  • Cadenas absorbentes
  • Cadenas en tiempo continuo

Este tipo de cadenas tienen muchas aplicaciones, pero la que más se relaciona con la Inteligencia Artificial es su aplicación en juegos de azar. Utilizando este método se puede dar la probabilidad de que un apostador quede sin dinero.

Te invito a que veas el siguiente video sobre una simulación de cadenas de Márvov, para que veas una de sus tantas aplicaciones reales.
http://www.youtube.com/watch?v=bPBb4W2u8ks

También puedes visitar la siguiente página, que utiliza estas cadenas para decir la importancia de una página en internet
http://www.mipagerank.com/

Bibliografía:

Kijima, Masaaki (1997). Markov Processes for Stochastic Modeling (1st edición). Cambridge: Chapman & Hall.

Vega, Marıa Valentina. “Cadenas de Markov de tiempo continuo y aplicaciones.” Monografía. Licenciatura en matemática. Universidad de la República de Uruguay (2004).

Swarm Intelligence

Swarm Intelligence

Swarm Intelligence, o inteligencia de enjambre es una rama de la Inteligencia Artificial que analiza el comportamiento colectivo de sistemas descentralizados y auto-organizados. Fue presentada por primera vez en 1989 por Gerardo Beni y Jing Wang. Este tipo de sistemas funcionan con agentes (en caso de duda consultar la publicación sobre agentes) que interactúan entre ellos.

En la naturaleza, la inteligencia de enjambres se puede ver en colonias de hormigas, o en el comportamiento de rebaños. No se puede determinar con precisión cual será el comportamiento de cada individuo, pero si se puede ver el comportamiento de la especie como conjunto. De esto nace la inteligencia en enjambres, que trata de hacer que agentes se comporten de cierta manera en grupos mostrando un grado de comportamiento inteligente.

La inteligencia de enjambres, más que ser un solo tema, se divide en una rama muy grande de distintos algoritmos, como lo son el algoritmo de la colonia de abejas artificial, o la optimización de la colonia de hormigas. Por el momento no se entrará en detalle sobre esos algoritmos.

Las aplicaciones de la inteligencia en enjambre son muchas a pesar de ser una rama de la ciencia que todavía es relativamente nueva. Por citar algunos ejemplos, se puede mencionar que el ejército de los Estados Unidos está intentando utilizar esta rama de la IA para controlar vehículos sin necesidad de que sean tripulados.

El siguiente video puede explicar cómo en la naturaleza ya se aplica la inteligencia de enjambres para lograr cosas que en lo individual no serían posibles. Esto aplicado a la inteligencia artificial es lo que hace tan poderosa a esta rama de la ciencia. Permite lograr cosas que un agente por sí solo no sería capaz de completar debido a que esta fuera de sus capacidades individuales.

http://www.youtube.com/watch?v=egK2C1s4vSI

 Bibliografía:

Kennedy, James F., James Kennedy, and Russel C. Eberhart. Swarm intelligence. Morgan Kaufmann, 2001.

 

Algoritmos Genéticos

Se define como algoritmo genético a programas que tienen la capacidad que generar un comportamiento parecido a la evolución humana, utilizando procesos equivalentes a la selección natural. Dicha habilidad de adaptación permite a este tipo de algoritmos resolver problemas tan complejos que ni siquiera quienes los crearon comprenden plenamente.

En la naturaleza, cuando un organismo falla las pruebas de idoneidad, perece. Así es la selección natural, si un animal no es capaz de detectar la presencia de un depredador y no huye, perecerá por la selección natural. Es igual con los algoritmos convencionales, si un algoritmo no es lo suficiente eficiente o falla pruebas, será desechado.

La forma en la que se obtienen por evolución sistemas capaces de resolver problemas es la siguiente: Primeramente se debe considerar que tipo de problema se tratará resolver. Después de eso se consideran los criterios que se evalúan para considerar que el problema ha sido resuelto exitosamente. Cuando se tiene se tiene lo que se espera, se seleccionan cadenas de unos y ceros aleatorios y se evalúan en cada una su capacidad para resolver el problema. Las cadenas que cumplan los criterios con más alto nivel, se aparearán. Tal vez la parte más importante es la recombinación, lo cual simula a los cromosomas humanos. Las que no lo hagan perecerán. Con el tiempo el proceso se repetirá para que las soluciones cada vez sean más perfectas.

Los algoritmos genéticos son elitistas, y en cada iteración siempre se guarda al mejor elemento sin alterarlo. Esto quiere decir que aunque se utilicen métodos aleatorios, un algoritmo genético tiende a llegar a una sola solución óptima.

Si bien un algoritmo genético puede ser utilizado para resolver cualquier función, como las de optimización, su principal uso es para funciones no derivables o en las cuales la derivación es muy compleja.

Si quieres saber más sobre los algoritmos genéticos, te invito a ver el siguiente video de la universidad de San Carlos de Guatemala donde se explica más sobre el tema.
http://www.youtube.com/watch?v=qRehZZckG0I

 Bibliografía:
Holland, John H. “Algoritmos genéticos.” Investigación y Ciencia 192 (1992): 38-45.