* Faculty       * Staff       * Contact       * Institute Directory
* Undergraduate       * Graduate       * Institute Admissions: Undergraduate | Graduate      
* Events       * Institute Events      
* Lab Manual       * Institute Computing      
No Menu Selected

* Research

Ph.D. Theses

Reverse Engineering A Hidden Markov Model For Complex Social Systems

By Hung-Ching (Justin) Chen
Advisor: Malik Magdon-Ismail
May 5, 2008

We present a machine learning methodology (models, algorithms, and experimental data) to discover the agent dynamics that drives the evolution of the social groups in a community. There are a number of challenges, the first and foremost being the complex nature of the micro-laws, determining the behaviors of an agent, needed to represent even a very simple society -- agents may have discrete attributes together with continuous parameters, which inevitably leads to a mixed optimization problem, and each agent has its own attributes, which also interact with others attributes, suffering from combinatorial and dimensionality curses. Another challenge is that the data upon which to answer the question is not available -- typically social groups (especially online groups) do not announce their membership and one has to infer groups from observable macro-quantities such as communication statistics.

We set up the problem by introducing an agent-based hidden Markov model for the agent dynamics: the actions of an agent are determined by micro-laws with unknown parameters. Our approach is to identify the appropriate micro-laws corresponding to identifying the appropriate parameters in the model. The model identification problem is then formulated as a mixed optimization problem. To solve the problem, we develop a multistage learning process for determining the group structure, the group evolution, and the micro-laws of a community based on the observed set of communications between actors, without knowing the semantic contents.

Finally, to test the quality of our approximations and the feasibility of the approach, we present the results of extensive experiments on synthetic data as well as the results on real communities, e.g., Enron email and Movie news groups. Insight into agent dynamics helps us understand the driving forces behind social evolution.

* Return to main PhD Theses page