Análisis de sentimientos en Twitter con HMM

Congresos No Comments »

emotions-371238_1280Es el título de mi charla en el Comunica 2: un congreso que se celebra todos los años por esas fechas en la EPS de Gandía sobre comunicación y redes sociales. En ella, hablé de un proyecto en el que estamos trabajando: analizar los sentimientos que aparecen en los mensajes en las redes sociales.

La hipótesis de partida es que los tuits no demuestran cual es el sentimiento real de los usuarios. Al menos no siempre. En ocasiones, yo puedo estar con un estado de ánimo determinado, pero escribir un mensaje que expresa una emoción distinta.

Para poder analizarlo, usamos modelos ocultos de Markov (HMM). En estos modelos hay dos tipos de estados: unos ocultos, que no podemos conocer, y otros observables. El ejemplo que se suele poner en estos casos es el siguiente: piensa que nuestro amigo vive en una ciudad distinta. Nosotros no sabemos qué tiempo hace allí (si llueve o hace sol -oculto-), pero sí qué es lo que ha hecho nuestro amigo ese día (correr, ir de compras o hacer las tarea de la casa -observable-). Si conocemos las probabilidades de que nuestro amigo corra o salga de compras en cada caso, podríamos tratar de estimar qué tiempo hace en su ciudad.

Eso mismo hacemos con los sentimientos: nosotros no vemos el sentimiento de la persona (oculto), pero si su expresión a través de un tuit (observable), así que tratamos de determinar el sentimiento de los usuarios a través de la secuencia de tuits que escribe.

El modelo que usamos para determinar el sentimiento es el modelo de Russell, que asocia dos valores: valencia (positivo o negativo) y arousal (activo/pasivo). Estos valores se pueden representar en un sistema de coordenadas y determinar el sentimiento que le corresponde según su posición.

Con todo eso, lo que hacemos es

  1. descargar los tuits de un determinado evento, es decir, los que contienen una determinada etiqueta (hashtag)
  2. extraer de cada tuit las palabras que tienen carga emocional y asignarles el valor de valencia y arousal que le corresponde (usamos el diccionario ANEW).
  3. crear la red que modela la conversación del evento. Si un mensaje es una mención, una respuesta (reply) o un retuit, creamos un enlace entre los dos usuarios (eso se usa luego para inicializar el HMM)
  4. construir las secuencias de tuits para cada usuario. Dividimos estas secuencias en dos partes: el 80% para entrenar el modelo y el 20% para validarlo
  5. entrenar el modelo usando el conjunto de secuencias de entrenamiento. Eso nos da unas probabilidades de pasar de un sentimiento a otro y de, dado un sentimiento, publicar un tuit con una emoción un otra.
  6. validar el modelo con las secuencias de test que quedan

El resultado obtenido muestra que, en general, los HMM funcionan mejor que los modelos de Markov "normales", sin estados ocultos. Es decir, que considerar por separado el sentimiento real del usuario de la emoción que muestra en un tuit explica mejor cómo evolucionan los sentimientos de los  usuarios y qué emoción aparece en los tuits. Además, esta diferencia es mayor en eventos en los que no hay un sentimiento mayoritario.

El artículo completo aparecerá en las actas del congreso. Mientras, te dejo las transparencias que usé en la charla

(imagen: Ryan McGuire, public domain)

La (poca) soledad del corredor de fondo

Divulgación Comentarios desactivados en La (poca) soledad del corredor de fondo

El pasado miércoles tuve la oportunidad de participar en el II Databeers VLC, compartiendo charla y cerveza con los que estuvisteis allí. En mi caso, hablé de una de los proyectos que tengo entre manos: analizar la evolución de una carrera como si fuera una red social.

La idea es considerar a los corredores como los nodos de una red y conectarlos si están a menos de una distancia determinada. Esta red va cambiando, ya que la posición relativa de los corredores entre sí varía también. Si la distancia es muy pequeña, no hay grupos y los corredores van en solitario. Pero a medida que aumentamos la distancia se van formando grupos a lo largo de la carrera. El número de grupos que se forman y la distancia a la que están sigue un patrón muy claro, independientemente de la distancia y del tipo de carrera.

Para comprobarlo, he ido recogiendo los datos de las carreras del Circuito DP de Carreras Populares de VLC, la 10K, media y maratón de Valencia, y algunas de montaña, como la Mamova, el maratón de Espadán o el Trail de Bronchales. Y en todos ellos (y alguna más) se observa el mismo comportamiento.

Te dejo aquí el material que usé en la charla... con un poco más de texto para que se entienda solo ;-)

También está disponible las trasparencias de La (poca) soledad del corredor de fondo, aunque más sosas porque no se ven los vídeos ;-)

AHP descentralizado en redes multicapa mediante consenso

Congresos Comentarios desactivados en AHP descentralizado en redes multicapa mediante consenso

ahp_groupMás o menos es la traducción del trabajo que he presentado esta semana en el PAAMS'16, que se está celebrando del 1 al 3 de junio en la Escuela de Informática de la Universidad de  Sevilla.

Los procesos analíticos jerárquicos se emplean para la toma de decisiones complejas en la que intervienen muchos factores (decisiones multi-criterio); por ejemplo, la valoración de jugadores de fútbol, pero también obras de arte, patentes, empresas... En nuestro caso, el problema se complica ya que

  • la decision no es individual, sino de un grupo que tiene que llegar a un acuerdo (la mejor solución para todos)
  • cada criterio tiene un valor distinto para cada persona, y se mantiene privado (nadie sabe qué es más importante o menos para el resto de miembros del grupo)
  • todos los miembros del grupo no se conocen entre sí, sino que cada persona solo conoce a algunos miembros. El grupo realmente es una red, como la que se forma en las redes sociales

Nuestra solución combina dos métodos: un proceso de consenso en cada uno de los criterios para tratar de llegar a la solución común, más un proceso de ascenso por gradiente que trata de compensar lo que cedo en uno de los criterios al grupo en algún otro criterio que sea importante para mi.

Al final, bajo determinadas condiciones (que son bastante razonables), se puede garantizar que el proceso converge a la mejor decisión posible, que es la que maximiza el valor.

Es importante remarcar que nadie sabe dónde está este valor, pero se aproximan a él en grupo al tratar de acercarse a los demás (consenso) pero tratando de mantener  los valores mejores para cada miembro del grupo.

Os dejo aquí las transparencias de la charla y la referencia al artículo

Rebollo, M., A. Palomares, C. Carrascosa. Decentralized Group Analytical Hierarchical Process on Multilayer Networks by Consensus. In Advances in Practical Applications of Scalable Multi-agent Systems, pp. 183-194. doi:10.1007/978-3-319-39324-7_16, 2016

Semantic Service Management for Service-Oriented MAS

Agentes, General, Servicios 2 Comments »

por Elena Del Val

El trabajo de tesis trata sobre cómo construir sistemas de agentes que se relacionan en redes complejas. Los resultados muestran que se pueden construir sistemas descentralizados, sin ningún tipo de control, donde los agentes son capaces de localizar los que necesitan realizando búsquedas activas. Los agentes se agrupan por similaridad (homofilia) y son capaces de adaptarse a cambios en el entorno (cambios en la demanda de los recursos) y también de superar situaciones en las que existan agentes que no colaboren en la tarea de búsqueda de información.

La revisión del estado del arte es complicada porque hay muchas áreas involucradas. Se organiza en torno a 3 preguntas clave:

  1. cómo se estructura la red -> sistemas centralizados, distribuidos y descentralizados
  2. comportamiento ante cambios en el entorno -> sistemas auto-organizados, emergencia
  3. comportamiento ante entidades que no cooperan -> aislamiento e incentivos Los resultados más usados en este campo son los que vienen de la teoría de juegos

El modelo formal del sistema es una red, donde los nodos son agentes u organizaciones complejas (que se ven como una única entidad) y las relaciones existentes entre ellas. Las entidades están definidas a través del conjunto de roles que desempeñan, cada uno de los cuales tiene asociado un conjunto de servicios que modelan qué es lo que el agente sabe hacer.

El caso más simple se produce cuando tenemos un sistema centralizado. Fue el principio de la tesis y en él simplemente se establece un sistema mediado por un Service Facilitator (SF). Se encarga de registrar los servicios de todos los agentes que forman el sistema y de resolver las consultas que se produzcan en el sistema, de forma semejante al rol del UDDI dentro de las plataformas orientadas a servicios. Si no se encuentran servicio adecuado, se trata de descubrir una composición de servicios que se ajuste a las necesidades. Pero esta no es una solución útil para sistemas dinámicos y abiertos, así que se ha optado por una

El primer problema es cómo crear las redes para que se puedan localizar los servicios sin tener un registro central que se encargue de organizar los servicios. Para eso se emplean redes basadas en un concepto llamado homofilia. Básicamente, resume la tendencia de las personas a interactuar con otros que son semejantes a ellos. Empleando esta idea, se crean redes en los que los nodos tienen tendencia a conectarse con otros agentes semejantes a sí mismos. De esta manera se obtiene una red con una estructura de growing network (los agentes se añaden a la red a medida que van llegando), con una distribución exponencial de grado. Una característica interesante es que de esta forma se consiguen redes navegables: es posible localizar un servicio teniendo en cuenta la información de los vecinos exclusivamente (racionalidad acotada). La estructura tienen ciertas características de small-world (caminos cortos e índice de clustering significativo).

Con esta formación, cuando se desea localizar un servicio, si nadie de nuestros contextos lo puede realizar le preguntaremos al vecino más prometedor que trate de localizar a un agente que sí lo proporcione. Para ello simplemente tenemos que localizar cuál de nuestros vecinos se parece lo suficiente al servicio que necesitamos y además se tiene en cuenta su grado (cuanto más conectado esté más probabilidades tendrá de encontrar el servicio que necesitamos). Este proceso se repite hasta que se localiza el servicio deseado. Aunque a priori puede parecer ineficiente tener que hacer un búsqueda cada vez que se necesita algo, en el caso de sistemas dinámicos, la sobrecarga de mantener actualizada la lista de servicios es mucho mayor. Y el problema se agrava si hablamos de sistemas distribuidos en los que los repositorios de servicios están replicados en la red.

Para evaluar el rendimiento, se ha comparado con distintas topología de red (random, scale-free, preferential attachment) y diferentes estrategias de búsqueda (random walk, degree, similaridad y homofilia). Se observa que la navegación por grado en redes de tipo scale-free y la basada en homofilia obtiene resultados simulares (en cuanto a las longitudes de los caminos que necesita en las búsquedas y la tasa de aciertos). Sin embargo, las redes scale-free son mucho más sensibles a sabotajes (provocar el fallo de un nodo muy conectado) y en el caso de las redes con homofilia se consigue una degradación mucho más lenta.

Esta alternativa funciona bien si se conoce la carga del sistema, es decir, si el número y el tipo de servicios que se piden en el sistema no cambia. Pero en el caso de sistemas dinámicos, en los que esta carga del sistema cambia, puede optimizarse el rendimiento del sistema adaptando la estructura de la red. Vamos a tratar de hacerlo también de forma descentralizada: cada agente toda la decisión de forma aislada sin conocer ni consultar el resto de lares, teniendo en cuenta únicamente el tráfico que pasa por él. Se plantean dos estrategias: modificar los enlaces o modificar los propios agentes. Para modificar los enlaces, se considera que éstos tienen una utilidad de decae con el tiempo, de manera que si un enlace no se ha usado durante mucho tiempo (y no es vital para el agente, éste puede decidir eliminarlo y tratar de conectarse con otro nodo. Para eso, mantiene una lista de candidatos a partir de los agentes que ha ido encontrando en la red que utiliza como posibles vecinos alternativos cuando cambia la situación. La segunda posibilidad es que si un nodo detecta que ya no es útil puede

Por último, podemos relajar la asunción de que todos los agentes quieran cooperar. En ese caso, podemos encontrarnos con el caso (muy real) de que agentes decidan no colaborar en la transmisión de las búsquedas. Esto puede afectar gravemente al rendimiento global del sistema, por lo que se trata de buscar una solución a este problema. De nuevo se plantean 2 posibilidades: aislar a los vecinos que no cooperan (ostracismo) o tratar de convencerlos de que cambien de comportamiento. En el primer caso se emplea un mecanismo semejante a la redirección de enlaces.. Se les asocia una utilidad que decae con el tiempo de forma si un agente no colabora de forma reiterada, en helase perderá importancia y finalmente se reemplazará. A la hora de redirigir en enlace, se ha comprobado que proporciona mejores resultados en enlazarse con un nodo semejante al nodo que se ha desconectado (usando el criterio de homofilia). SIn embargo, este mecanismo no funciona bien si el número de agentes que no colaboran es alto o éstos tienen un grado elevado. Por eso se trata de usar mecanismos basados en incentivos para tratar de que los agentes que no colaboran cambien de comportamiento. Los incentivos tratan de premiar el comportamiento de los agentes que colaboran de manera que el resto de agentes funcionen por imitación y adapten su comportamiento a de aquellos vecinos que obtienen mejores beneficios. Esto no garantiza la colaboración y de hecho los resultados son semejantes cuando no hay una masa crítica de agentes que comienzan colaborando. Sin embargo, la combinación de los dos métodos: incentivos para tratar de caminar el comportamiento de agentes y aislamiento cuando no se produce este cambio, permite que emerja un comportamiento general de colaboración incluso cuando el número inicial de agentes que colaboran está muy por debajo de los egoístas (inciso en una proporción de 30-70).

Y con esto acaba la presentación de la tesis. Os dejaré más información sobre los artículos que hemos publicado sobre estos temas

Actualización 8-mar-2013: Ya se puede descargar la tesis desde  http://hdl.handle.net/10251/27556 

WP Theme & Icons by N.Design Studio | Modified by M. Rebollo
RSS Entradas Acceder
Blog logo: MC MECHANIC-HAND FIXING HAND Homage to MC Escher. (c) Shane Willis