Strategy Games

Los juegos de tipo estrategia se han usado para el desarrollo de inteligencia artificial pero según lo que he encontrado no sé había dado un ambiente competitivo hasta ahora que esta surgiendo la competición AIIDE de Starcraft.

En trabajos previos se usa el ambiente ORTS (Open Real Time Strategy Game) para las pruebas puesto que es gratuito, el servidor actúa independientemente a los clientes que se conectan, se pueden unir de manera independiente y se da control total sobre los objetos en el campo.

Las principales áreas de investigación sobre este tipo de ambientes son:

• Planeación en tiempo real frente a un ambiente adverso
• Toma de decisiones bajo incertidumbre
• Modelado y aprendizaje del oponente
• Razonamiento espacial y temporal
• Administración de recursos
• Colaboración
• Búsqueda y establecimiento de rutas

El tipo de ambiente es propicio para utilizar sistemas multi-agentes y de hecho su mejora también se toma como parte del objetivo de hacer este tipo de investigaciones.

Otro tipo similar de juego es el de estrategia pero por turnos en el que cada participante tiene cierto tiempo para llevar a cabo sus movimientos. Este ambiente es más fácil de utilizar ya que se tiene más tiempo pero a la vez pierde cierto interés puesto que es más sencillo llevar a cabo el procesamiento de lo que se quiera estudiar debido a las pausas en el juego.

Natural Language Processing

Una forma mencionada para estudiar el uso de lenguaje natural es verlo como parte de un sistema más amplio de comunicación, uno que incluye lo que se dice literalmente, la intención que se tiene y la relación entre los dos aspectos.

El entendimiento de un lenguaje puede producir distintas aplicaciones como:

• Poder dar formato a un texto dependiendo de ciertos parámetros (adaptarlo a un estilo de escritura, a un lenguaje formal, etc.)
• Consultar información con preguntas en un lenguaje humano de modo que se pueda obtener solo los datos que se crean relevantes o más apegados a los que se busca.
• Comunicación entre computadoras y personas sin la necesidad de aprender un lenguaje nuevo y/o complicado que incluya comandos o procedimientos
• Traducción automática de textos entre idiomas
• Corrección de gramática y redacción
• Asistentes inteligentes que comprendan las preguntas de los usuarios
• Chatbox (persona artificial que logra mantener una conversación con un humano)
• Identificación de un locutor

Existen varios grupos alrededor del mundo que se enfocan en cuestiones del estudio del lenguaje natural como el Stanford NLP Group, The Turing Center (universidad de Washington) y el XRCE (Xerox Research Centre Europe) en los que se desarrollan varias investigaciones. Algunas de las áreas que siguen son:

• Machine Translation
• Recolección y extracción de información
• Respuestas a preguntas (Question Answering)
• Reconocimiento de habla
• Síntesis del habla
• Reconocimiento y verificación de un locutor
• Sistemas de diálogo

Más aplicaciones de Machine Learning

Entre algunas aplicaciones extra que he encontrado para ML se encuentran:

Reconocimiento de acciones: Mediante el análisis de imágenes (visión computacional) se crean árboles con prototipos en donde se clasifican y ramifican las acciones que puede estar llevando a cabo un individuo. Cada prototipo se puede considerar como una imagen que contiene la posición del sujeto a evaluar mientras que una acción es definida por una sucesión de varios prototipos. Un ejemplo de esto se encuentra en la siguiente figura:

Otras formas de llevar a cabo esta clasificación se pueden basar en otros métodos de aprendizaje como Slow Feature Analysis (SFA) que extrae características que cambian lentamente de una señal de entrada con cambios constantes.

Reconocimiento de eventos en un grupo: De nuevo mediante el uso de visión computacional se aprende de un grupo de imágenes o un video las características que acompañan a un grupo. Se determina su forma de interactuar dependiendo de lo que se detecte y se usa como medidas la distancia entre los involucrados, la velocidad a la que se mueven y otros elementos. Una ilustración se puede apreciar en la siguiente figura:

Análisis de proteínas: Tema dedicado completamente a la informática en el que se puede usar ML para crear algo conocido como Superfamily Level Classification que permite encontrar la relación estructural, evolucionaria y funcional de las proteínas.

Reconocimiento del habla: La mayor parte de esta área se lleva a cabo mediante comparaciones con palabras previamente etiquetadas que permiten la comparación entre lo que se tiene guardado y el audio obtenido al momento, sin embargo este método es costoso y depende de tener previamente etiquetadas las palabras para poder entenderlas. En algunos artículos se menciona el uso de aprendizaje semi-estructurado que permite reducir el costo del proceso ya que se puede incluir tanto datos etiquetados como no etiquetados.

Predicción de fallas en una planta: Hay un ejemplo que utiliza aprendizaje automático estadístico y técnicas de adquisición de conocimiento para la red eléctrica de la ciudad de Nueva York. Lo que se busca es poder analizar y predecir con la mayor precisión las áreas y componentes dentro de la planta que requieran un mantenimiento preventivo de forma que no haya fallas graves en el lugar.

Predicción de resultados en juegos de cartas: En este ejemplo se menciona el uso de aprendizaje supervisado para este tipo de dominios. Se habla de emplear ese tipo de técnicas para predecir los resultados futuros basados en juegos anteriores. Sin embargo, se menciona que por el tipo de juegos no se puede tener una completa fiabilidad ya que en la mayoría interviene un factor aleatorio (suerte).

Tráfico IP: Se utiliza minería de datos para conocer y facilitar el monitoreo del flujo de información. Se usa con motivo de mejorar la calidad del servicio y tan solo empleando C4.5 se logra una precisión del 95%.

Análisis harmónico de música: Se basa en la clasificación de canciones en base a un cromagrama (chromagram). Este toma en cuenta los acordes, llaves, notas graves y la percepción humana del ruido. No se requiere un experto para ajustar los parámetros del sistema debido a que todo se encuentra basado en machine learning.

Semantic Web Mining

La idea de la que surge semantic web mining se basa en el poder aprovechar el conocimiento que se encuentra actualmente en la red pero para lograrlo se requiere que las máquinas logren procesarlo. Para que el uso de minería de datos tenga éxito en la información recolectada en la red esta debe tener un sentido que pueda ser entendido de forma que puede ser necesario agregar información complementaria o descriptores para que pueda ser procesado y analizado por las máquinas.

El fin de lo anterior radica en poder proveer a los usuarios de la red mejores servicios y posiblemente explorar una nueva gama de servicios inteligentes creados a partir de la información recolectada.

Para que el análisis semántico pueda llevarse a cabo se requiere de pasar a lo largo de 7 fases que son expuestas en la siguiente figura:

Mientras que las últimas dos capas lidian con la confiabilidad y seguridad del sistema, el resto se enfoca a la obtención de datos y el proceso subsecuente que permite darles un sentido para que tengan una utilidad.

A la red semántica también se le conoce como Web 3.0 y aunque su nombre lo parezca en realidad no es una red nueva sino una extensión de la que actualmente existe. El área de interés dentro de esta extensión principalmente es el cambio de enfoque ya que mientras tradicionalmente se lidiaba con la forma en que una computadora pueda leer lo encontrado en la red a que ahora la computadora pueda entenderlo y lidiar con ello.

En todo este proceso el uso y manejo de ontologías se vuelve un tema de suma relevancia debido a que estas permiten crear y abarcar el contexto en el que se encuentran los datos de forma que no solo sean entendibles y agrupables para un humano sino para una computadora también.

Un modelo general del uso de las redes semánticas en web mining se presenta a continuación:

Como se puede apreciar en el contexto de la figura anterior, las ontologías juegan una parte muy importante dentro de semantic web mining ya que de su definición depende completamente la adquisición y administración de los recursos encontrados por lo que gran parte de las investigaciones realizadas sobre este tema son realmente enfocadas al desarrollo de ontologías.

Yong-gui, W., & Zhen, J. (2010). Research on semantic Web mining. 2010 International Conference On Computer Design and Applications (Vol. 1, pp. V1-67-V1-70). IEEE. doi:10.1109/ICCDA.2010.5541057

Web Usages Mining

Investigando un poco más sobre esta área de web mining encontré que algunas de las aplicaciones precisas de llevar a cabo web usage mining son:

• Web personalization
• Link prediction and analysis
• Web site evaluation or reorganization
• Web analytics and ecommerce data analysis
• Adaptive Web sites
• Web pre-fetching

Mientras cada uno de los usos previamente mencionados puede tener un fin distinto, el proceso que siguen para llevarlo a cabo sigue un patrón que en el análisis de los registros que existen en los servidores web. Los registros de los servidores no se encuentran abiertos a todo el público y la estructura interna que siguen varía dependiendo del contenido del sitio. Algunos ejemplos encontrados sobre la información contenida en los servidores y que fue empleada para algunos artículos se muestran a continuación:

Complementando la información sobre el acceso general a los servidores se cuenta también con los datos de las sesiones de cada usuario para hacer predicciones sobre individuos después de haber modelado su comportamiento, estas sesiones de igual forma dependen de la información que guarde el servidor y un ejemplo se encuentra en la siguiente figura:

Mientras que los métodos empleados para el análisis y clasificación son técnicas comunes en minería de datos (clustering, clasificadores, etc.) el principal problema con este tipo de investigaciones radica en la obtención y pre-procesamiento de los datos debido a que como se ha mencionado, la presentación de los datos no es uniforma y varia dependiendo del caso de estudio.

Otro problema ligado directamente a la obtención de los datos radica en el lugar de donde son obtenidos ya que la mayoría no se encuentran abiertos al público por lo que gran parte de los artículos emplea los servidores de la institución en la que se encuentran para realizar los análisis y pruebas de sus investigaciones.

Casale, G. (2005). Combining queueing networks and web usage mining techniques for web performance analysis. Proceedings of the 2005 ACM symposium on Applied computing - SAC ’05 (p. 1699). New York, New York, USA: ACM Press. doi:10.1145/1066677.1067061

Géry, M., & Haddad, H. (2003). Evaluation of web usage mining approaches for user’s next request prediction. Proceedings of the fifth ACM international workshop on Web information and data management - WIDM ’03 (p. 74). New York, New York, USA: ACM Press. doi:10.1145/956699.956716

Jin, X., Zhou, Y., & Mobasher, B. (2004). Web usage mining based on probabilistic latent semantic analysis. Proceedings of the 2004 ACM SIGKDD international conference on Knowledge discovery and data mining - KDD ’04 (p. 197). New York, New York, USA: ACM Press. doi:10.1145/1014052.1014076

Web data mining research: a survey

La minería de datos es un proceso por el cual se intenta descubrir conocimiento en base a una serie de datos (base de datos). Actualmente se puede dividir la minería de datos en data mining, text mining y web mining.

A causa del tipo de fuentes empleadas para obtener la información para cada tipo de minería de datos encontramos que data mining usa mayormente datos estructurados debido al uso de bases de datos, text mining por su parte emplea datos no estructurados ya que su descubrimiento de información lo hace a partir de texto plano y por último web mining tiene que lidiar tanto con información semi-estructurada como con información no estructurada.

En web mining se pueden emplear técnicas de data y text mining para descubrir conocimiento. Debido a la gran cantidad de información presentada y sus diversas presentaciones el poder llevar a cabo la adquisición de conocimiento se puede convertir en un gran reto.

Debido a la gran cantidad de datos que se encuentran distribuidos en la red se presentan algunos problemas o áreas de oportunidad donde web mining puede actuar como son:

• Encontrar información relevante: dentro del universo de datos contenido en la web no siempre es fácil encontrar la información que se requiere debido a que se puede confundir con datos irrelevantes además se suma al problema que radica en que lo que se busca no se encuentre indexado en los buscadores.
• Crear conocimiento a partir de la información disponible: mientras el área anterior se enfoca al proceso de búsqueda de información este se basa en encontrar un sentido útil a la información que ha sido encontrada y obtener conocimiento de ello.
• Personalización de la información: cada persona que interactúa con la red tiene gustos y preferencias distintos por lo que varía el contenido y la presentación que más les agrada.
• Aprendizaje sobre usuarios o grupo de usuarios: este problema trata sobre aprender lo que el usuario hace y quiere. Se pueden encontrar aplicaciones (marketing por ejemplo) que utilizan lo aprendido sobre el usuario para llegar a él.

La minería de datos fue planteada inicialmente como una serie de sub-tareas que se requieren para completar el proceso:

• Descubrimiento de recursos: se refiere a localizar documentos y servicios con los que no se es familiar en la web.
• Seleccionar información y pre-procesamiento: es el extraer y pre-procesar de manera automática información específica de los recursos que acaban de ser descubiertos.
• Generalización: descubrimiento de patrones a en sitios web (uno solo o varios).
• Análisis: Validación e interpretación de los patrones descubiertos.
• Visualización: presentación de los resultados de forma que sean útiles y entendibles.

Las áreas a las que se encuentra enfocada web mining se muestran en la siguiente figura y serán detalladas más adelante:

Web Content Mining

Esta área de web mining se centra en la búsqueda de información o conocimiento útil en los contenidos dentro de los sitios web. Se puede utilizar como una extensión de la labor llevada a cabo por los buscadores en internet en donde se analizan los recursos encontrados para organizar la relevancia de los mismos.

Principalmente se usan contenidos en texto para llevar a cabo este tipo de minería sin embargo se menciona que se está tratando de extender a otro tipo de contenidos como imágenes, videos, sonido, etc. El problema de extender el uso a ese tipo de formatos radica en la extracción de los datos de los mismos formatos para poder llevar a cabo una clasificación de los mismos.

Otro problema con el uso de este tipo de minería respecto a archivos multimedia radica en la misma percepción de las personas sobre estos medios. Se pone como ejemplo una fotografía que puede tener contenido relacionado a varios temas o que el entendimiento de su contenido puede variar de una persona a otra.

Sin embargo para el caso de las imágenes han nacido áreas de estudio como lo es el Content Based Image Retrieval (CBIR) que trata de automatizar el proceso de indexado de imágenes en bases de datos. Se lleva a cabo una clasificación en cuanto a contenidos visuales y trasladados a vectores los cuales se usan como punto de comparación al buscar imágenes similares.

El problema con CBIR vuelve a la gran distancia en cuanto a complejidad de almacenar, indexar y comparar contenidos simples de una imagen como lo es su histograma a los contenidos subjetivos que pueden detectar los humanos.

El objetivo de CBIR al final se encuentra en que en una búsqueda un humano pueda introducir una serie de palabras que describan el contenido no solo visual de las imágenes sino el mensaje de ellas o que se pueda buscar dando como parámetro otra imagen y que se encuentren algunas que tengan un contenido similar. En la siguiente imagen se muestra el proceso:

Otra área de estudio se presenta en la fase inicial de este proceso, esta área se basa en las anotaciones sobre el contenido de las imágenes. Esto se puede hacer de manera manual por humanos pero sería un proceso tedioso y largo. Para esto se han propuesto soluciones como la mencionada de H. J. Zhang. En su sistema se asume que se tiene una base de datos inicial con imágenes y anotaciones (esta base de datos puede ser llenada de la forma que sea) y mientras el usuario interactúa con el sistema, a base de una sesión de solicitudes o preguntas el sistema aprende y propaga las palabras clave para las anotaciones de las nuevas imágenes que vaya adquiriendo. De esta forma se crea la red semántica donde tiene mayo relevancia las palabras claves en donde el mayor número de usuarios coincida en sus anotaciones.

En general este campo de web mining se dedica como se ha mencionado a la búsqueda de información útil. La mayoría de los trabajos encuentra patrones y solo se emplean los más comunes ya que los que contienen una menor frecuencia de aparición posiblemente son los que contienen mayor ruido.

Web Structure Mining

Esta área de web mining se dedica a descubrir y modelar la estructura de los enlaces de la red. Se intenta crear un resumen estructural de los sitios y páginas web. El enfoque principal radica en la información que te pueden brindar los enlaces con información sobre hacia donde están conectados, cuantos sitios hacen referencia a otro, a que sitios se hace referencia, etc. Este tipo de acciones no es llevado acabo normalmente por los buscadores en internet.

Este tipo de minería ayuda a compañías a conocer su posicionamiento en el mercado. Si de antemano conocen que su sitio no se encuentra enlazado por otros sitios entonces deberán cambiar su enfoque en cuanto mercadotecnia, de igual forma pueden concluir a que sitios deberían enlazar a sus clientes para dar mejor soporte. También pueden servir como un estudio de mercado encontrando los enlaces hacia los sitios más populares o más referidos y así desarrollar alguna estrategia.

En la mayoría de los estudios se encuentra una representación en base a grafos de los sitios representando los vínculos como sus aristas. Esto permite aplicar técnicas de teoría de grafos y algunas más para descubrir patrones como lo son los caminos más utilizados, las conexiones entre nodos, etc.

Otra utilidad para este tipo de web mining radica en el descubrimiento de comunidades dentro de la red. Se denomina como comunidad al conjunto de sitios web que se enfocan a un mismo tema. Para asegurar la pertenencia a una comunidad se asume que se tienen más enlaces a sitios dentro de la misma comunidad que hacia sitios externos.

El uso de algoritmos de clustering en grafos es muy común en esta área de web mining. Estos algoritmos permiten agrupar y de cierta forma clasificar a los sitios de modo que el conocimiento sobre ellos pueda manejarse con mayor facilidad además de existir la posibilidad de encontrar nuevo conocimiento en la agrupación misma.

Web Usages Mining

Esta área lidia con entender el comportamiento de un usuario con un sitio web en particular o con toda la red. Algunas aplicaciones de este aprendizaje se encuentran dirigidas a la personalización de la navegación del usuario en base al conocimiento que se tiene sobre su navegación.

Algunas de las ventajas esperadas en el uso de este tipo de web mining son el reorganizar el sitio web para que el visitante tenga un acceso más rápido y sencillo, atraer empresas con una forma eficiente de colocar publicidad, convertir a visitantes en clientes debido a la buena arquitectura del sitio, mejora en la navegación y enlaces y monitoreo constante de la eficiencia del sitio.

Para esto se utilizan registros que contienen la actividad de los usuarios en un sitio y las acciones que toman como lo son secciones que visitan, búsquedas que llevan a cabo, etc. Esto se ve reflejado en un modelo general en la siguiente figura:

La información es obtenida comúnmente de servidores web, servidores de proxy o bases de datos de servidores. Como en los anteriores ejemplos es preferible que se elimine el ruido contenido en estos datos por lo que también es común llevar a cabo una fase de pre-procesamiento donde se intenta minimizar su impacto.

Existen aplicaciones que dirigen a los usuarios a secciones dentro de un solo sitio basadas en una predicción de la intención del usuario y su historial de comportamiento. La predicción sobre el próximo sitio a visitar se hace basada en el flujo de clics que ha hecho un usuario en el sistema.

Semantic Web Mining

Uno de los problemas presentes para web mining consiste en que muchos de los datos que se encuentran en la red son fácilmente interpretados por los humanos únicamente y el entendimiento a nivel de máquinas es limitado. El saber como lidiar con dicha información de forma que sea entendible y útil para una computadora es el enfoque que se busca con Semantic Web Mining.

Una semantic web es una red capaz de describir cosas de forma que una máquina lo pueda entender. Los enunciados son construidos con reglas sintácticas. Las redes semánticas describen relaciones entre cosas y sus propiedades. Semantic Web Mining trata de combinar los campos de redes semánticas con minería de datos. Esto puede ser posible ya sea mejorando los resultados de la minería de datos a través de las estructuras semánticas en la red para posteriormente hacer uso de técnicas de web mining para crear una red semántica. Por otra parte estas técnicas pueden ser utilizadas para hacer minería en las mismas redes semánticas.

El propósito de las redes semánticas intenta mejorar la forma en que se obtiene conocimiento de la red. Se da como ejemplo un caso en que un usuario quiera encontrar una respuesta no simplemente se deberá buscar palabras que coincidan sino tener la capacidad de combinar la información encontrada para ser capaz de dar una respuesta.

Los retos para lograr este objetivo radican en distintas áreas como la interoperabilidad entre sistemas, el lenguaje para el intercambio de información, la representación del conocimiento, la extracción del conocimiento, cuestionamiento inteligente y la capacidad de devolver una respuesta a diferencia de los queries actuales incluida la posibilidad de explotar el conocimiento adquirido en el proceso.

Se mencionan como las dos áreas principales de investigación en este campo al pre-procesamiento de la información (web log data) y a la identificación de patrones útiles en base a los datos pre-procesados utilizando técnicas de minería de datos.

Singh, B., & Singh, H. K. (2010). Web Data Mining research: A survey. 2010 IEEE International Conference on Computational Intelligence and Computing Research (pp. 1-10). IEEE. doi:10.1109/ICCIC.2010.5705856

Áreas de aplicación de machine learning

En la búsqueda por un tema de tesis decidí visitar algunas aplicaciones de machine learning que son usadas actualmente dándome como resultado los siguientes campos que me causan cierto interés:

• Procesamiento de texto:
  • Se utilizan aplicaciones de machine learning para extraer las ideas principales de un texto.
  • Se puede emplear para hacer una categorización del texto.
  • Se usa para encontrar textos que contengan ideas similares o relevantes que se puedan complementar con otros.
  • También se puede determinar la relevancia de cierto texto.
• Procesamiento de correo electrónico:
  • Detección de correos basura o spam.
  • Determinar la importancia del contenido un correo por su contenido y título.
• Reconocimiento de voz:
  • Se utiliza machine learning para entrenar al sistema para mejorar el reconocimiento de palabras y oraciones. Puede existir un entrenamiento previo y otro que se hace y se adapta ya que se desplego la aplicación.
• Visión computacional:
  • Reconocimiento de patrones (rostros como ejemplo).
  • Reconocimiento de escritura (por ejemplo a mano).
• Bio-surveillance:
  • Como ejemplo se encontró el RODS que es un sistema en Pennsylvania que toma los reportes de hospitales y los compara con patrones aprendidos con machine learning para poder predecir y prevenir posibles brotes de enfermedades contagiosas o raras detectando casos inconsistentes con los patrones normales.
• Control de robots:
  • Se usa comúnmente para definir sus acciones.
• Bioinformática:
  • Se emplean métodos de machine learning para descubrir patrones en genes.
• Aplicaciones comerciales (marketing):
  • Se utiliza para adaptar la publicidad presentada a un usuario respecto al perfil que se tiene de él y se puede llegar a tal grado de predecir que necesidades va a presentar en determinado tiempo para ofrecerle algún servicio o producto que las pueda satisfacer.
• Web mining:
  • Aprovechando el gran volumen de datos que existen en la red se ha creado una sub división de machine learning que lidia con ellos. El enfoque que se le da a esta área específicamente aprovecha dichos datos y busca encontrar información relevante que en ocasiones es posible solo obtener relacionando cada uno de los contenidos relacionados en la web. Algunas de las áreas se pueden observar en la siguiente figura: